diff options
author | Chris Mason <chris.mason@oracle.com> | 2007-03-26 10:15:30 -0400 |
---|---|---|
committer | David Woodhouse <dwmw2@hera.kernel.org> | 2007-03-26 10:15:30 -0400 |
commit | 8ef97622caa2d5f78d1dc58ab918e2fbfa9b357a (patch) | |
tree | 6ae74ce8ff1ba7a6b8a522ed0ea3b37f17a6b305 /fs/btrfs/bit-radix.c | |
parent | f7922033efe957f79ae57f6026e93c8148e7f7ed (diff) | |
download | linux-stable-8ef97622caa2d5f78d1dc58ab918e2fbfa9b357a.tar.gz linux-stable-8ef97622caa2d5f78d1dc58ab918e2fbfa9b357a.tar.bz2 linux-stable-8ef97622caa2d5f78d1dc58ab918e2fbfa9b357a.zip |
Btrfs: add a radix back bit tree
Signed-off-by: Chris Mason <chris.mason@oracle.com>
Diffstat (limited to 'fs/btrfs/bit-radix.c')
-rw-r--r-- | fs/btrfs/bit-radix.c | 107 |
1 files changed, 107 insertions, 0 deletions
diff --git a/fs/btrfs/bit-radix.c b/fs/btrfs/bit-radix.c new file mode 100644 index 000000000000..43807cc3cce7 --- /dev/null +++ b/fs/btrfs/bit-radix.c @@ -0,0 +1,107 @@ +#include <linux/module.h> +#include "bit-radix.h" + +#define BIT_ARRAY_BYTES 256 +#define BIT_RADIX_BITS_PER_ARRAY ((BIT_ARRAY_BYTES - sizeof(unsigned long)) * 8) + +int set_radix_bit(struct radix_tree_root *radix, unsigned long bit) +{ + unsigned long *bits; + unsigned long slot; + int bit_slot; + int ret; + + slot = bit / BIT_RADIX_BITS_PER_ARRAY; + bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY; + + bits = radix_tree_lookup(radix, slot); + if (!bits) { + bits = kmalloc(BIT_ARRAY_BYTES, GFP_NOIO); + if (!bits) + return -ENOMEM; + memset(bits + 1, 0, BIT_ARRAY_BYTES - sizeof(unsigned long)); + bits[0] = slot; + ret = radix_tree_insert(radix, slot, bits); + if (ret) + return ret; + } + set_bit(bit_slot, bits + 1); + return 0; +} + +int test_radix_bit(struct radix_tree_root *radix, unsigned long bit) +{ + unsigned long *bits; + unsigned long slot; + int bit_slot; + + slot = bit / BIT_RADIX_BITS_PER_ARRAY; + bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY; + + bits = radix_tree_lookup(radix, slot); + if (!bits) + return 0; + return test_bit(bit_slot, bits + 1); +} + +int clear_radix_bit(struct radix_tree_root *radix, unsigned long bit) +{ + unsigned long *bits; + unsigned long slot; + int bit_slot; + int i; + int empty = 1; + + slot = bit / BIT_RADIX_BITS_PER_ARRAY; + bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY; + + bits = radix_tree_lookup(radix, slot); + if (!bits) + return 0; + clear_bit(bit_slot, bits + 1); + + for (i = 1; i < BIT_ARRAY_BYTES / sizeof(unsigned long); i++) { + if (bits[i]) { + empty = 0; + break; + } + } + + if (empty) { + bits = radix_tree_delete(radix, slot); + BUG_ON(!bits); + } + return 0; +} + +int find_first_radix_bit(struct radix_tree_root *radix, unsigned long *retbits, + int nr) +{ + unsigned long *bits; + unsigned long *gang[4]; + int found; + int ret; + int i; + int total_found = 0; + + ret = radix_tree_gang_lookup(radix, (void *)&gang, 0, ARRAY_SIZE(gang)); + for (i = 0; i < ret && nr > 0; i++) { + found = 0; + bits = gang[i]; + while(nr > 0) { + found = find_next_bit(bits + 1, + BIT_RADIX_BITS_PER_ARRAY, + found); + if (found < BIT_RADIX_BITS_PER_ARRAY) { + *retbits = bits[0] * + BIT_RADIX_BITS_PER_ARRAY + found; + retbits++; + nr--; + total_found++; + found++; + } else + break; + } + } + return total_found; +} |