1 #include "kerncompat.h"
2 #include "radix-tree.h"
4 #define BIT_ARRAY_BYTES 256
5 #define BIT_RADIX_BITS_PER_ARRAY ((BIT_ARRAY_BYTES - sizeof(unsigned long)) * 8)
7 int set_radix_bit(struct radix_tree_root *radix, unsigned long bit)
14 slot = bit / BIT_RADIX_BITS_PER_ARRAY;
15 bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
17 bits = radix_tree_lookup(radix, slot);
19 bits = malloc(BIT_ARRAY_BYTES);
22 memset(bits + 1, 0, BIT_ARRAY_BYTES - sizeof(unsigned long));
24 radix_tree_preload(GFP_NOFS);
25 ret = radix_tree_insert(radix, slot, bits);
26 radix_tree_preload_end();
30 __set_bit(bit_slot, bits + 1);
34 int test_radix_bit(struct radix_tree_root *radix, unsigned long bit)
40 slot = bit / BIT_RADIX_BITS_PER_ARRAY;
41 bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
43 bits = radix_tree_lookup(radix, slot);
46 return test_bit(bit_slot, bits + 1);
49 int clear_radix_bit(struct radix_tree_root *radix, unsigned long bit)
56 slot = bit / BIT_RADIX_BITS_PER_ARRAY;
57 bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
59 bits = radix_tree_lookup(radix, slot);
62 __clear_bit(bit_slot, bits + 1);
63 for (i = 1; i < BIT_ARRAY_BYTES / sizeof(unsigned long); i++) {
70 bits = radix_tree_delete(radix, slot);
77 #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
80 * __ffs - find first bit in word.
81 * @word: The word to search
83 * Undefined if no bit exists, so code should check against 0 first.
85 static unsigned long __ffs(unsigned long word)
89 #if BITS_PER_LONG == 64
90 if ((word & 0xffffffff) == 0) {
95 if ((word & 0xffff) == 0) {
99 if ((word & 0xff) == 0) {
103 if ((word & 0xf) == 0) {
107 if ((word & 0x3) == 0) {
111 if ((word & 0x1) == 0)
117 * find_next_bit - find the next set bit in a memory region
118 * @addr: The address to base the search on
119 * @offset: The bitnumber to start searching at
120 * @size: The maximum size to search
122 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
123 unsigned long offset)
125 const unsigned long *p = addr + BITOP_WORD(offset);
126 unsigned long result = offset & ~(BITS_PER_LONG-1);
132 offset %= BITS_PER_LONG;
135 tmp &= (~0UL << offset);
136 if (size < BITS_PER_LONG)
140 size -= BITS_PER_LONG;
141 result += BITS_PER_LONG;
143 while (size & ~(BITS_PER_LONG-1)) {
146 result += BITS_PER_LONG;
147 size -= BITS_PER_LONG;
154 tmp &= (~0UL >> (BITS_PER_LONG - size));
155 if (tmp == 0UL) /* Are any bits set? */
156 return result + size; /* Nope. */
158 return result + __ffs(tmp);
161 int find_first_radix_bit(struct radix_tree_root *radix, unsigned long *retbits,
162 unsigned long start, int nr)
165 unsigned long *gang[4];
172 slot = start / BIT_RADIX_BITS_PER_ARRAY;
173 ret = radix_tree_gang_lookup(radix, (void **)gang, slot,
175 found = start % BIT_RADIX_BITS_PER_ARRAY;
176 for (i = 0; i < ret && nr > 0; i++) {
179 found = find_next_bit(bits + 1,
180 BIT_RADIX_BITS_PER_ARRAY,
182 if (found < BIT_RADIX_BITS_PER_ARRAY) {
184 BIT_RADIX_BITS_PER_ARRAY + found;