Commit | Line | Data |
---|---|---|
6cbd5570 CM |
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 | ||
8ef97622 CM |
19 | #include "bit-radix.h" |
20 | ||
21 | #define BIT_ARRAY_BYTES 256 | |
22 | #define BIT_RADIX_BITS_PER_ARRAY ((BIT_ARRAY_BYTES - sizeof(unsigned long)) * 8) | |
23 | ||
2c90e5d6 | 24 | extern struct kmem_cache *btrfs_bit_radix_cachep; |
8ef97622 CM |
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) { | |
2c90e5d6 | 37 | bits = kmem_cache_alloc(btrfs_bit_radix_cachep, GFP_NOFS); |
8ef97622 CM |
38 | if (!bits) |
39 | return -ENOMEM; | |
40 | memset(bits + 1, 0, BIT_ARRAY_BYTES - sizeof(unsigned long)); | |
41 | bits[0] = slot; | |
42 | ret = radix_tree_insert(radix, slot, bits); | |
43 | if (ret) | |
44 | return ret; | |
45 | } | |
be744175 CM |
46 | ret = test_and_set_bit(bit_slot, bits + 1); |
47 | if (ret < 0) | |
48 | ret = 1; | |
49 | return ret; | |
8ef97622 CM |
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 | ||
75 | slot = bit / BIT_RADIX_BITS_PER_ARRAY; | |
76 | bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY; | |
77 | ||
78 | bits = radix_tree_lookup(radix, slot); | |
79 | if (!bits) | |
80 | return 0; | |
81 | clear_bit(bit_slot, bits + 1); | |
8ef97622 CM |
82 | for (i = 1; i < BIT_ARRAY_BYTES / sizeof(unsigned long); i++) { |
83 | if (bits[i]) { | |
84 | empty = 0; | |
85 | break; | |
86 | } | |
87 | } | |
8ef97622 CM |
88 | if (empty) { |
89 | bits = radix_tree_delete(radix, slot); | |
90 | BUG_ON(!bits); | |
2c90e5d6 | 91 | kmem_cache_free(btrfs_bit_radix_cachep, bits); |
8ef97622 CM |
92 | } |
93 | return 0; | |
94 | } | |
95 | ||
96 | int find_first_radix_bit(struct radix_tree_root *radix, unsigned long *retbits, | |
e37c9e69 | 97 | unsigned long start, int nr) |
8ef97622 CM |
98 | { |
99 | unsigned long *bits; | |
100 | unsigned long *gang[4]; | |
101 | int found; | |
102 | int ret; | |
103 | int i; | |
104 | int total_found = 0; | |
e37c9e69 | 105 | unsigned long slot; |
8ef97622 | 106 | |
e37c9e69 CM |
107 | slot = start / BIT_RADIX_BITS_PER_ARRAY; |
108 | ret = radix_tree_gang_lookup(radix, (void **)gang, slot, | |
109 | ARRAY_SIZE(gang)); | |
110 | found = start % BIT_RADIX_BITS_PER_ARRAY; | |
8ef97622 | 111 | for (i = 0; i < ret && nr > 0; i++) { |
8ef97622 CM |
112 | bits = gang[i]; |
113 | while(nr > 0) { | |
114 | found = find_next_bit(bits + 1, | |
115 | BIT_RADIX_BITS_PER_ARRAY, | |
116 | found); | |
117 | if (found < BIT_RADIX_BITS_PER_ARRAY) { | |
118 | *retbits = bits[0] * | |
119 | BIT_RADIX_BITS_PER_ARRAY + found; | |
120 | retbits++; | |
121 | nr--; | |
122 | total_found++; | |
123 | found++; | |
124 | } else | |
125 | break; | |
126 | } | |
e37c9e69 | 127 | found = 0; |
8ef97622 CM |
128 | } |
129 | return total_found; | |
130 | } |