bit-radix.c

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