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
;