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 "bit-radix.h"
21 #define BIT_ARRAY_BYTES 256
22 #define BIT_RADIX_BITS_PER_ARRAY ((BIT_ARRAY_BYTES - sizeof(unsigned long)) * 8)
24 extern struct kmem_cache
*btrfs_bit_radix_cachep
;
25 int set_radix_bit(struct radix_tree_root
*radix
, unsigned long bit
)
32 slot
= bit
/ BIT_RADIX_BITS_PER_ARRAY
;
33 bit_slot
= bit
% BIT_RADIX_BITS_PER_ARRAY
;
35 bits
= radix_tree_lookup(radix
, slot
);
37 bits
= kmem_cache_alloc(btrfs_bit_radix_cachep
, GFP_NOFS
);
40 memset(bits
+ 1, 0, BIT_ARRAY_BYTES
- sizeof(unsigned long));
42 ret
= radix_tree_insert(radix
, slot
, bits
);
46 ret
= test_and_set_bit(bit_slot
, bits
+ 1);
52 int test_radix_bit(struct radix_tree_root
*radix
, unsigned long bit
)
58 slot
= bit
/ BIT_RADIX_BITS_PER_ARRAY
;
59 bit_slot
= bit
% BIT_RADIX_BITS_PER_ARRAY
;
61 bits
= radix_tree_lookup(radix
, slot
);
64 return test_bit(bit_slot
, bits
+ 1);
67 int clear_radix_bit(struct radix_tree_root
*radix
, unsigned long bit
)
75 slot
= bit
/ BIT_RADIX_BITS_PER_ARRAY
;
76 bit_slot
= bit
% BIT_RADIX_BITS_PER_ARRAY
;
78 bits
= radix_tree_lookup(radix
, slot
);
81 clear_bit(bit_slot
, bits
+ 1);
82 for (i
= 1; i
< BIT_ARRAY_BYTES
/ sizeof(unsigned long); i
++) {
89 bits
= radix_tree_delete(radix
, slot
);
91 kmem_cache_free(btrfs_bit_radix_cachep
, bits
);
96 int find_first_radix_bit(struct radix_tree_root
*radix
, unsigned long *retbits
,
97 unsigned long start
, int nr
)
100 unsigned long *gang
[4];
107 slot
= start
/ BIT_RADIX_BITS_PER_ARRAY
;
108 ret
= radix_tree_gang_lookup(radix
, (void **)gang
, slot
,
110 found
= start
% BIT_RADIX_BITS_PER_ARRAY
;
111 for (i
= 0; i
< ret
&& nr
> 0; i
++) {
114 found
= find_next_bit(bits
+ 1,
115 BIT_RADIX_BITS_PER_ARRAY
,
117 if (found
< BIT_RADIX_BITS_PER_ARRAY
) {
119 BIT_RADIX_BITS_PER_ARRAY
+ found
;