Commit | Line | Data |
---|---|---|
8ef97622 CM |
1 | #include <linux/module.h> |
2 | #include "bit-radix.h" | |
3 | ||
4 | #define BIT_ARRAY_BYTES 256 | |
5 | #define BIT_RADIX_BITS_PER_ARRAY ((BIT_ARRAY_BYTES - sizeof(unsigned long)) * 8) | |
6 | ||
2c90e5d6 | 7 | extern struct kmem_cache *btrfs_bit_radix_cachep; |
8ef97622 CM |
8 | int set_radix_bit(struct radix_tree_root *radix, unsigned long bit) |
9 | { | |
10 | unsigned long *bits; | |
11 | unsigned long slot; | |
12 | int bit_slot; | |
13 | int ret; | |
14 | ||
15 | slot = bit / BIT_RADIX_BITS_PER_ARRAY; | |
16 | bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY; | |
17 | ||
18 | bits = radix_tree_lookup(radix, slot); | |
19 | if (!bits) { | |
2c90e5d6 | 20 | bits = kmem_cache_alloc(btrfs_bit_radix_cachep, GFP_NOFS); |
8ef97622 CM |
21 | if (!bits) |
22 | return -ENOMEM; | |
23 | memset(bits + 1, 0, BIT_ARRAY_BYTES - sizeof(unsigned long)); | |
24 | bits[0] = slot; | |
25 | ret = radix_tree_insert(radix, slot, bits); | |
26 | if (ret) | |
27 | return ret; | |
28 | } | |
be744175 CM |
29 | ret = test_and_set_bit(bit_slot, bits + 1); |
30 | if (ret < 0) | |
31 | ret = 1; | |
32 | return ret; | |
8ef97622 CM |
33 | } |
34 | ||
35 | int test_radix_bit(struct radix_tree_root *radix, unsigned long bit) | |
36 | { | |
37 | unsigned long *bits; | |
38 | unsigned long slot; | |
39 | int bit_slot; | |
40 | ||
41 | slot = bit / BIT_RADIX_BITS_PER_ARRAY; | |
42 | bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY; | |
43 | ||
44 | bits = radix_tree_lookup(radix, slot); | |
45 | if (!bits) | |
46 | return 0; | |
47 | return test_bit(bit_slot, bits + 1); | |
48 | } | |
49 | ||
50 | int clear_radix_bit(struct radix_tree_root *radix, unsigned long bit) | |
51 | { | |
52 | unsigned long *bits; | |
53 | unsigned long slot; | |
54 | int bit_slot; | |
55 | int i; | |
56 | int empty = 1; | |
57 | ||
58 | slot = bit / BIT_RADIX_BITS_PER_ARRAY; | |
59 | bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY; | |
60 | ||
61 | bits = radix_tree_lookup(radix, slot); | |
62 | if (!bits) | |
63 | return 0; | |
64 | clear_bit(bit_slot, bits + 1); | |
8ef97622 CM |
65 | for (i = 1; i < BIT_ARRAY_BYTES / sizeof(unsigned long); i++) { |
66 | if (bits[i]) { | |
67 | empty = 0; | |
68 | break; | |
69 | } | |
70 | } | |
8ef97622 CM |
71 | if (empty) { |
72 | bits = radix_tree_delete(radix, slot); | |
73 | BUG_ON(!bits); | |
2c90e5d6 | 74 | kmem_cache_free(btrfs_bit_radix_cachep, bits); |
8ef97622 CM |
75 | } |
76 | return 0; | |
77 | } | |
78 | ||
79 | int find_first_radix_bit(struct radix_tree_root *radix, unsigned long *retbits, | |
80 | int nr) | |
81 | { | |
82 | unsigned long *bits; | |
83 | unsigned long *gang[4]; | |
84 | int found; | |
85 | int ret; | |
86 | int i; | |
87 | int total_found = 0; | |
88 | ||
0f7d52f4 | 89 | ret = radix_tree_gang_lookup(radix, (void **)gang, 0, ARRAY_SIZE(gang)); |
8ef97622 CM |
90 | for (i = 0; i < ret && nr > 0; i++) { |
91 | found = 0; | |
92 | bits = gang[i]; | |
93 | while(nr > 0) { | |
94 | found = find_next_bit(bits + 1, | |
95 | BIT_RADIX_BITS_PER_ARRAY, | |
96 | found); | |
97 | if (found < BIT_RADIX_BITS_PER_ARRAY) { | |
98 | *retbits = bits[0] * | |
99 | BIT_RADIX_BITS_PER_ARRAY + found; | |
100 | retbits++; | |
101 | nr--; | |
102 | total_found++; | |
103 | found++; | |
104 | } else | |
105 | break; | |
106 | } | |
107 | } | |
108 | return total_found; | |
109 | } |