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 BITS_PER_LONG == 64
  90         if ((word & 0xffffffff) == 0) {
  91                 num += 32;
  92                 word >>= 32;
  93         }
  94 #endif
  95         if ((word & 0xffff) == 0) {
  96                 num += 16;
  97                 word >>= 16;
  98         }
  99         if ((word & 0xff) == 0) {
 100                 num += 8;
 101                 word >>= 8;
 102         }
 103         if ((word & 0xf) == 0) {
 104                 num += 4;
 105                 word >>= 4;
 106         }
 107         if ((word & 0x3) == 0) {
 108                 num += 2;
 109                 word >>= 2;
 110         }
 111         if ((word & 0x1) == 0)
 112                 num += 1;
 113         return num;
 114 }
 115
 116 /**
 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
 121  */
 122 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
 123                 unsigned long offset)
 124 {
 125         const unsigned long *p = addr + BITOP_WORD(offset);
 126         unsigned long result = offset & ~(BITS_PER_LONG-1);
 127         unsigned long tmp;
 128
 129         if (offset >= size)
 130                 return size;
 131         size -= result;
 132         offset %= BITS_PER_LONG;
 133         if (offset) {
 134                 tmp = *(p++);
 135                 tmp &= (~0UL << offset);
 136                 if (size < BITS_PER_LONG)
 137                         goto found_first;
 138                 if (tmp)
 139                         goto found_middle;
 140                 size -= BITS_PER_LONG;
 141                 result += BITS_PER_LONG;
 142         }
 143         while (size & ~(BITS_PER_LONG-1)) {
 144                 if ((tmp = *(p++)))
 145                         goto found_middle;
 146                 result += BITS_PER_LONG;
 147                 size -= BITS_PER_LONG;
 148         }
 149         if (!size)
 150                 return result;
 151         tmp = *p;
 152
 153 found_first:
 154         tmp &= (~0UL >> (BITS_PER_LONG - size));
 155         if (tmp == 0UL)         /* Are any bits set? */
 156                 return result + size;   /* Nope. */
 157 found_middle:
 158         return result + __ffs(tmp);
 159 }
 160
 161 int find_first_radix_bit(struct radix_tree_root *radix, unsigned long *retbits,
 162                          unsigned long start, int nr)
 163 {
 164         unsigned long *bits;
 165         unsigned long *gang[4];
 166         int found;
 167         int ret;
 168         int i;
 169         int total_found = 0;
 170         unsigned long slot;
 171
 172         slot = start / BIT_RADIX_BITS_PER_ARRAY;
 173         ret = radix_tree_gang_lookup(radix, (void **)gang, slot,
 174                                      ARRAY_SIZE(gang));
 175         found = start % BIT_RADIX_BITS_PER_ARRAY;
 176         for (i = 0; i < ret && nr > 0; i++) {
 177                 bits = gang[i];
 178                 while(nr > 0) {
 179                         found = find_next_bit(bits + 1,
 180                                               BIT_RADIX_BITS_PER_ARRAY,
 181                                               found);
 182                         if (found < BIT_RADIX_BITS_PER_ARRAY) {
 183                                 *retbits = bits[0] *
 184                                         BIT_RADIX_BITS_PER_ARRAY + found;
 185                                 retbits++;
 186                                 nr--;
 187                                 total_found++;
 188                                 found++;
 189                         } else
 190                                 break;
 191                 }
 192                 found = 0;
 193         }
 194         return total_found;
 195 }