2 * Copyright (C) 2007 Oracle. All rights reserved.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
19 #include "kerncompat.h"
20 #include "radix-tree.h"
22 #define BIT_ARRAY_BYTES 256
23 #define BIT_RADIX_BITS_PER_ARRAY ((BIT_ARRAY_BYTES - sizeof(unsigned long)) * 8)
25 int set_radix_bit(struct radix_tree_root *radix, unsigned long bit)
32 slot = bit / BIT_RADIX_BITS_PER_ARRAY;
33 bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
35 bits = radix_tree_lookup(radix, slot);
37 bits = malloc(BIT_ARRAY_BYTES);
40 memset(bits + 1, 0, BIT_ARRAY_BYTES - sizeof(unsigned long));
42 radix_tree_preload(GFP_NOFS);
43 ret = radix_tree_insert(radix, slot, bits);
44 radix_tree_preload_end();
48 __set_bit(bit_slot, bits + 1);
52 int test_radix_bit(struct radix_tree_root *radix, unsigned long bit)
58 slot = bit / BIT_RADIX_BITS_PER_ARRAY;
59 bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
61 bits = radix_tree_lookup(radix, slot);
64 return test_bit(bit_slot, bits + 1);
67 int clear_radix_bit(struct radix_tree_root *radix, unsigned long bit)
74 slot = bit / BIT_RADIX_BITS_PER_ARRAY;
75 bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
77 bits = radix_tree_lookup(radix, slot);
80 __clear_bit(bit_slot, bits + 1);
81 for (i = 1; i < BIT_ARRAY_BYTES / sizeof(unsigned long); i++) {
88 bits = radix_tree_delete(radix, slot);
95 #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
98 * __ffs - find first bit in word.
99 * @word: The word to search
101 * Undefined if no bit exists, so code should check against 0 first.
103 static unsigned long __ffs(unsigned long word)
107 if (sizeof(long) == 8 && (word & 0xffffffff) == 0) {
109 word >>= sizeof(long) * 4;
111 if ((word & 0xffff) == 0) {
115 if ((word & 0xff) == 0) {
119 if ((word & 0xf) == 0) {
123 if ((word & 0x3) == 0) {
127 if ((word & 0x1) == 0)
133 * find_next_bit - find the next set bit in a memory region
134 * @addr: The address to base the search on
135 * @offset: The bitnumber to start searching at
136 * @size: The maximum size to search
138 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
139 unsigned long offset)
141 const unsigned long *p = addr + BITOP_WORD(offset);
142 unsigned long result = offset & ~(BITS_PER_LONG-1);
148 offset %= BITS_PER_LONG;
151 tmp &= (~0UL << offset);
152 if (size < BITS_PER_LONG)
156 size -= BITS_PER_LONG;
157 result += BITS_PER_LONG;
159 while (size & ~(BITS_PER_LONG-1)) {
162 result += BITS_PER_LONG;
163 size -= BITS_PER_LONG;
170 tmp &= (~0UL >> (BITS_PER_LONG - size));
171 if (tmp == 0UL) /* Are any bits set? */
172 return result + size; /* Nope. */
174 return result + __ffs(tmp);
177 int find_first_radix_bit(struct radix_tree_root *radix, unsigned long *retbits,
178 unsigned long start, int nr)
181 unsigned long *gang[4];
188 slot = start / BIT_RADIX_BITS_PER_ARRAY;
189 ret = radix_tree_gang_lookup(radix, (void *)gang, slot,
191 found = start % BIT_RADIX_BITS_PER_ARRAY;
192 for (i = 0; i < ret && nr > 0; i++) {
195 found = find_next_bit(bits + 1,
196 BIT_RADIX_BITS_PER_ARRAY,
198 if (found < BIT_RADIX_BITS_PER_ARRAY) {
200 BIT_RADIX_BITS_PER_ARRAY + found;