fs/btrfs/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 <linux/module.h>
  20 #include "bit-radix.h"
  21
  22 #define BIT_ARRAY_BYTES 256
  23 #define BIT_RADIX_BITS_PER_ARRAY ((BIT_ARRAY_BYTES - sizeof(unsigned long)) * 8)
  24
  25 extern struct kmem_cache *btrfs_bit_radix_cachep;
  26 int set_radix_bit(struct radix_tree_root *radix, unsigned long bit)
  27 {
  28         unsigned long *bits;
  29         unsigned long slot;
  30         int bit_slot;
  31         int ret;
  32
  33         slot = bit / BIT_RADIX_BITS_PER_ARRAY;
  34         bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
  35
  36         bits = radix_tree_lookup(radix, slot);
  37         if (!bits) {
  38                 bits = kmem_cache_alloc(btrfs_bit_radix_cachep, GFP_NOFS);
  39                 if (!bits)
  40                         return -ENOMEM;
  41                 memset(bits + 1, 0, BIT_ARRAY_BYTES - sizeof(unsigned long));
  42                 bits[0] = slot;
  43                 ret = radix_tree_insert(radix, slot, bits);
  44                 if (ret)
  45                         return ret;
  46         }
  47         ret = test_and_set_bit(bit_slot, bits + 1);
  48         if (ret < 0)
  49                 ret = 1;
  50         return ret;
  51 }
  52
  53 int test_radix_bit(struct radix_tree_root *radix, unsigned long bit)
  54 {
  55         unsigned long *bits;
  56         unsigned long slot;
  57         int bit_slot;
  58
  59         slot = bit / BIT_RADIX_BITS_PER_ARRAY;
  60         bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
  61
  62         bits = radix_tree_lookup(radix, slot);
  63         if (!bits)
  64                 return 0;
  65         return test_bit(bit_slot, bits + 1);
  66 }
  67
  68 int clear_radix_bit(struct radix_tree_root *radix, unsigned long bit)
  69 {
  70         unsigned long *bits;
  71         unsigned long slot;
  72         int bit_slot;
  73         int i;
  74         int empty = 1;
  75
  76         slot = bit / BIT_RADIX_BITS_PER_ARRAY;
  77         bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
  78
  79         bits = radix_tree_lookup(radix, slot);
  80         if (!bits)
  81                 return 0;
  82         clear_bit(bit_slot, bits + 1);
  83         for (i = 1; i < BIT_ARRAY_BYTES / sizeof(unsigned long); i++) {
  84                 if (bits[i]) {
  85                         empty = 0;
  86                         break;
  87                 }
  88         }
  89         if (empty) {
  90                 bits = radix_tree_delete(radix, slot);
  91                 BUG_ON(!bits);
  92                 kmem_cache_free(btrfs_bit_radix_cachep, bits);
  93         }
  94         return 0;
  95 }
  96
  97 int find_first_radix_bit(struct radix_tree_root *radix, unsigned long *retbits,
  98                          unsigned long start, int nr)
  99 {
 100         unsigned long *bits;
 101         unsigned long *gang[4];
 102         int found;
 103         int ret;
 104         int i;
 105         int total_found = 0;
 106         unsigned long slot;
 107
 108         slot = start / BIT_RADIX_BITS_PER_ARRAY;
 109         ret = radix_tree_gang_lookup(radix, (void **)gang, slot,
 110                                      ARRAY_SIZE(gang));
 111         found = start % BIT_RADIX_BITS_PER_ARRAY;
 112         for (i = 0; i < ret && nr > 0; i++) {
 113                 bits = gang[i];
 114                 while(nr > 0) {
 115                         found = find_next_bit(bits + 1,
 116                                               BIT_RADIX_BITS_PER_ARRAY,
 117                                               found);
 118                         if (found < BIT_RADIX_BITS_PER_ARRAY) {
 119                                 *retbits = bits[0] *
 120                                         BIT_RADIX_BITS_PER_ARRAY + found;
 121                                 retbits++;
 122                                 nr--;
 123                                 total_found++;
 124                                 found++;
 125                         } else
 126                                 break;
 127                 }
 128                 found = 0;
 129         }
 130         return total_found;
 131 }