bit-radix.c

   1 #include "kerncompat.h"
   2 #include "radix-tree.h"
   3
   4 #define BIT_ARRAY_BYTES 256
   5 #define BIT_RADIX_BITS_PER_ARRAY ((BIT_ARRAY_BYTES - sizeof(unsigned long)) * 8)
   6
   7 int set_radix_bit(struct radix_tree_root *radix, unsigned long bit)
   8 {
   9         unsigned long *bits;
  10         unsigned long slot;
  11         int bit_slot;
  12         int ret;
  13
  14         slot = bit / BIT_RADIX_BITS_PER_ARRAY;
  15         bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
  16
  17         bits = radix_tree_lookup(radix, slot);
  18         if (!bits) {
  19                 bits = malloc(BIT_ARRAY_BYTES);
  20                 if (!bits)
  21                         return -ENOMEM;
  22                 memset(bits + 1, 0, BIT_ARRAY_BYTES - sizeof(unsigned long));
  23                 bits[0] = slot;
  24                 radix_tree_preload(GFP_NOFS);
  25                 ret = radix_tree_insert(radix, slot, bits);
  26                 radix_tree_preload_end();
  27                 if (ret)
  28                         return ret;
  29         }
  30         __set_bit(bit_slot, bits + 1);
  31         return 0;
  32 }
  33
  34 int test_radix_bit(struct radix_tree_root *radix, unsigned long bit)
  35 {
  36         unsigned long *bits;
  37         unsigned long slot;
  38         int bit_slot;
  39
  40         slot = bit / BIT_RADIX_BITS_PER_ARRAY;
  41         bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
  42
  43         bits = radix_tree_lookup(radix, slot);
  44         if (!bits)
  45                 return 0;
  46         return test_bit(bit_slot, bits + 1);
  47 }
  48
  49 int clear_radix_bit(struct radix_tree_root *radix, unsigned long bit)
  50 {
  51         unsigned long *bits;
  52         unsigned long slot;
  53         int bit_slot;
  54         int i;
  55         int empty = 1;
  56         slot = bit / BIT_RADIX_BITS_PER_ARRAY;
  57         bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
  58
  59         bits = radix_tree_lookup(radix, slot);
  60         if (!bits)
  61                 return 0;
  62         __clear_bit(bit_slot, bits + 1);
  63         for (i = 1; i < BIT_ARRAY_BYTES / sizeof(unsigned long); i++) {
  64                 if (bits[i]) {
  65                         empty = 0;
  66                         break;
  67                 }
  68         }
  69         if (empty) {
  70                 bits = radix_tree_delete(radix, slot);
  71                 BUG_ON(!bits);
  72                 free(bits);
  73         }
  74         return 0;
  75 }
  76
  77 #define BITOP_WORD(nr)          ((nr) / BITS_PER_LONG)
  78
  79 /**
  80  * __ffs - find first bit in word.
  81  * @word: The word to search
  82  *
  83  * Undefined if no bit exists, so code should check against 0 first.
  84  */
  85 static unsigned long __ffs(unsigned long word)
  86 {
  87         int num = 0;
  88
  89         if (sizeof(long) == 8 && (word & 0xffffffff) == 0) {
  90                 num += 32;
  91                 word >>= sizeof(long) * 4;
  92         }
  93         if ((word & 0xffff) == 0) {
  94                 num += 16;
  95                 word >>= 16;
  96         }
  97         if ((word & 0xff) == 0) {
  98                 num += 8;
  99                 word >>= 8;
 100         }
 101         if ((word & 0xf) == 0) {
 102                 num += 4;
 103                 word >>= 4;
 104         }
 105         if ((word & 0x3) == 0) {
 106                 num += 2;
 107                 word >>= 2;
 108         }
 109         if ((word & 0x1) == 0)
 110                 num += 1;
 111         return num;
 112 }
 113
 114 /**
 115  * find_next_bit - find the next set bit in a memory region
 116  * @addr: The address to base the search on
 117  * @offset: The bitnumber to start searching at
 118  * @size: The maximum size to search
 119  */
 120 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
 121                 unsigned long offset)
 122 {
 123         const unsigned long *p = addr + BITOP_WORD(offset);
 124         unsigned long result = offset & ~(BITS_PER_LONG-1);
 125         unsigned long tmp;
 126
 127         if (offset >= size)
 128                 return size;
 129         size -= result;
 130         offset %= BITS_PER_LONG;
 131         if (offset) {
 132                 tmp = *(p++);
 133                 tmp &= (~0UL << offset);
 134                 if (size < BITS_PER_LONG)
 135                         goto found_first;
 136                 if (tmp)
 137                         goto found_middle;
 138                 size -= BITS_PER_LONG;
 139                 result += BITS_PER_LONG;
 140         }
 141         while (size & ~(BITS_PER_LONG-1)) {
 142                 if ((tmp = *(p++)))
 143                         goto found_middle;
 144                 result += BITS_PER_LONG;
 145                 size -= BITS_PER_LONG;
 146         }
 147         if (!size)
 148                 return result;
 149         tmp = *p;
 150
 151 found_first:
 152         tmp &= (~0UL >> (BITS_PER_LONG - size));
 153         if (tmp == 0UL)         /* Are any bits set? */
 154                 return result + size;   /* Nope. */
 155 found_middle:
 156         return result + __ffs(tmp);
 157 }
 158
 159 int find_first_radix_bit(struct radix_tree_root *radix, unsigned long *retbits,
 160                          unsigned long start, int nr)
 161 {
 162         unsigned long *bits;
 163         unsigned long *gang[4];
 164         int found;
 165         int ret;
 166         int i;
 167         int total_found = 0;
 168         unsigned long slot;
 169
 170         slot = start / BIT_RADIX_BITS_PER_ARRAY;
 171         ret = radix_tree_gang_lookup(radix, (void **)gang, slot,
 172                                      ARRAY_SIZE(gang));
 173         found = start % BIT_RADIX_BITS_PER_ARRAY;
 174         for (i = 0; i < ret && nr > 0; i++) {
 175                 bits = gang[i];
 176                 while(nr > 0) {
 177                         found = find_next_bit(bits + 1,
 178                                               BIT_RADIX_BITS_PER_ARRAY,
 179                                               found);
 180                         if (found < BIT_RADIX_BITS_PER_ARRAY) {
 181                                 *retbits = bits[0] *
 182                                         BIT_RADIX_BITS_PER_ARRAY + found;
 183                                 retbits++;
 184                                 nr--;
 185                                 total_found++;
 186                                 found++;
 187                         } else
 188                                 break;
 189                 }
 190                 found = 0;
 191         }
 192         return total_found;
 193 }