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 <linux/module.h>
20 #include "bit-radix.h"
22 #define BIT_ARRAY_BYTES 256
23 #define BIT_RADIX_BITS_PER_ARRAY ((BIT_ARRAY_BYTES - sizeof(unsigned long)) * 8)
25 extern struct kmem_cache *btrfs_bit_radix_cachep;
26 int set_radix_bit(struct radix_tree_root *radix, unsigned long bit)
33 slot = bit / BIT_RADIX_BITS_PER_ARRAY;
34 bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
36 bits = radix_tree_lookup(radix, slot);
38 bits = kmem_cache_alloc(btrfs_bit_radix_cachep, GFP_NOFS);
41 memset(bits + 1, 0, BIT_ARRAY_BYTES - sizeof(unsigned long));
43 ret = radix_tree_insert(radix, slot, bits);
47 ret = test_and_set_bit(bit_slot, bits + 1);
53 int test_radix_bit(struct radix_tree_root *radix, unsigned long bit)
59 slot = bit / BIT_RADIX_BITS_PER_ARRAY;
60 bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
62 bits = radix_tree_lookup(radix, slot);
65 return test_bit(bit_slot, bits + 1);
68 int clear_radix_bit(struct radix_tree_root *radix, unsigned long bit)
76 slot = bit / BIT_RADIX_BITS_PER_ARRAY;
77 bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY;
79 bits = radix_tree_lookup(radix, slot);
82 clear_bit(bit_slot, bits + 1);
83 for (i = 1; i < BIT_ARRAY_BYTES / sizeof(unsigned long); i++) {
90 bits = radix_tree_delete(radix, slot);
92 kmem_cache_free(btrfs_bit_radix_cachep, bits);
97 int find_first_radix_bit(struct radix_tree_root *radix, unsigned long *retbits,
98 unsigned long start, int nr)
101 unsigned long *gang[4];
108 slot = start / BIT_RADIX_BITS_PER_ARRAY;
109 ret = radix_tree_gang_lookup(radix, (void **)gang, slot,
111 found = start % BIT_RADIX_BITS_PER_ARRAY;
112 for (i = 0; i < ret && nr > 0; i++) {
115 found = find_next_bit(bits + 1,
116 BIT_RADIX_BITS_PER_ARRAY,
118 if (found < BIT_RADIX_BITS_PER_ARRAY) {
120 BIT_RADIX_BITS_PER_ARRAY + found;