2 Based on SAMBA 7ce1356c9f571c55af70bd6b966fe50898c1582d.
4 very efficient functions to manage mapping a id (such as a fnum) to
5 a pointer. This is used for fnum and search id allocation.
7 Copyright (C) Andrew Tridgell 2004
9 This code is derived from lib/idr.c in the 2.6 Linux kernel, which was
10 written by Jim Houston jim.houston@ccur.com, and is
11 Copyright (C) 2002 by Concurrent Computer Corporation
13 This program is free software; you can redistribute it and/or modify
14 it under the terms of the GNU General Public License as published by
15 the Free Software Foundation; either version 2 of the License, or
16 (at your option) any later version.
18 This program is distributed in the hope that it will be useful,
19 but WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 GNU General Public License for more details.
23 You should have received a copy of the GNU General Public License
24 along with this program. If not, see <http://www.gnu.org/licenses/>.
27 #include <ccan/idtree/idtree.h>
28 #include <ccan/talloc/talloc.h>
33 #define IDTREE_FULL 0xfffffffful
35 #define TOP_LEVEL_FULL (IDTREE_FULL >> 30)
37 #define IDTREE_SIZE (1 << IDTREE_BITS)
38 #define IDTREE_MASK ((1 << IDTREE_BITS)-1)
39 #define MAX_ID_SHIFT (sizeof(int)*8 - 1)
40 #define MAX_ID_BIT (1U << MAX_ID_SHIFT)
41 #define MAX_ID_MASK (MAX_ID_BIT - 1)
42 #define MAX_LEVEL (MAX_ID_SHIFT + IDTREE_BITS - 1) / IDTREE_BITS
43 #define IDTREE_FREE_MAX MAX_LEVEL + MAX_LEVEL
45 #define set_bit(bit, v) (v) |= (1<<(bit))
46 #define clear_bit(bit, v) (v) &= ~(1<<(bit))
47 #define test_bit(bit, v) ((v) & (1<<(bit)))
51 struct idtree_layer *ary[IDTREE_SIZE];
56 struct idtree_layer *top;
57 struct idtree_layer *id_free;
62 static struct idtree_layer *alloc_layer(struct idtree *idp)
64 struct idtree_layer *p;
66 if (!(p = idp->id_free))
68 idp->id_free = p->ary[0];
74 static int find_next_bit(uint32_t bm, int maxid, int n)
76 while (n<maxid && !test_bit(n, bm)) n++;
80 static void free_layer(struct idtree *idp, struct idtree_layer *p)
82 p->ary[0] = idp->id_free;
87 static int idtree_pre_get(struct idtree *idp)
89 while (idp->id_free_cnt < IDTREE_FREE_MAX) {
90 struct idtree_layer *pn = talloc_zero(idp, struct idtree_layer);
98 static int sub_alloc(struct idtree *idp, const void *ptr, int *starting_id)
101 struct idtree_layer *p, *pn;
102 struct idtree_layer *pa[MAX_LEVEL+1];
103 unsigned int l, id, oid;
106 memset(pa, 0, sizeof(pa));
115 * We run around this while until we reach the leaf node...
117 n = (id >> (IDTREE_BITS*l)) & IDTREE_MASK;
119 m = find_next_bit(bm, IDTREE_SIZE, n);
120 if (m == IDTREE_SIZE) {
121 /* no space available go back to previous layer. */
124 id = (id | ((1 << (IDTREE_BITS*l))-1)) + 1;
126 /* if already at the top layer, we need to grow */
132 /* If we need to go up one layer, continue the
133 * loop; otherwise, restart from the top.
135 sh = IDTREE_BITS * (l + 1);
136 if (oid >> sh == id >> sh)
143 id = ((id >> sh) ^ n ^ m) << sh;
145 if ((id >= MAX_ID_BIT) || (id < 0))
150 * Create the layer below if it is missing.
153 if (!(pn = alloc_layer(idp)))
162 * We have reached the leaf node, plant the
163 * users pointer and return the raw id.
165 p->ary[m] = (struct idtree_layer *)ptr;
166 set_bit(m, p->bitmap);
169 * If this layer is full mark the bit in the layer above
170 * to show that this part of the radix tree is full.
171 * This may complete the layer above and require walking
175 while (p->bitmap == IDTREE_FULL) {
178 n = n >> IDTREE_BITS;
179 set_bit((n & IDTREE_MASK), p->bitmap);
184 static int idtree_get_new_above_int(struct idtree *idp,
185 const void *ptr, int starting_id)
187 struct idtree_layer *p, *pn;
195 layers = idp->layers;
197 if (!(p = alloc_layer(idp)))
202 * Add a new layer to the top of the tree if the requested
203 * id is larger than the currently allocated space.
205 while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDTREE_BITS)))) {
209 if (!(pn = alloc_layer(idp))) {
211 * The allocation failed. If we built part of
212 * the structure tear it down.
214 for (pn = p; p && p != idp->top; pn = p) {
217 pn->bitmap = pn->count = 0;
224 if (p->bitmap == IDTREE_FULL)
225 set_bit(0, pn->bitmap);
229 idp->layers = layers;
230 v = sub_alloc(idp, ptr, &id);
236 static int sub_remove(struct idtree *idp, int shift, int id)
238 struct idtree_layer *p = idp->top;
239 struct idtree_layer **pa[1+MAX_LEVEL];
240 struct idtree_layer ***paa = &pa[0];
246 while ((shift > 0) && p) {
247 n = (id >> shift) & IDTREE_MASK;
248 clear_bit(n, p->bitmap);
251 shift -= IDTREE_BITS;
253 n = id & IDTREE_MASK;
254 if (p != NULL && test_bit(n, p->bitmap)) {
255 clear_bit(n, p->bitmap);
257 while(*paa && ! --((**paa)->count)){
258 free_layer(idp, **paa);
268 void *idtree_lookup(const struct idtree *idp, int id)
271 struct idtree_layer *p;
273 n = idp->layers * IDTREE_BITS;
276 * This tests to see if bits outside the current tree are
277 * present. If so, tain't one of ours!
279 if (n + IDTREE_BITS < 31 &&
280 (id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDTREE_BITS))
283 /* Mask off upper bits we don't use for the search. */
286 while (n >= IDTREE_BITS && p) {
288 p = p->ary[(id >> n) & IDTREE_MASK];
293 bool idtree_remove(struct idtree *idp, int id)
295 struct idtree_layer *p;
297 /* Mask off upper bits we don't use for the search. */
300 if (sub_remove(idp, (idp->layers - 1) * IDTREE_BITS, id) == -1) {
304 if ( idp->top && idp->top->count == 1 &&
307 /* We can drop a layer */
308 p = idp->top->ary[0];
309 idp->top->bitmap = idp->top->count = 0;
310 free_layer(idp, idp->top);
314 while (idp->id_free_cnt >= IDTREE_FREE_MAX) {
315 p = alloc_layer(idp);
321 struct idtree *idtree_new(void *mem_ctx)
323 return talloc_zero(mem_ctx, struct idtree);
326 int idtree_add(struct idtree *idp, const void *ptr, int limit)
328 int ret = idtree_get_new_above_int(idp, ptr, 0);
330 idtree_remove(idp, ret);
336 int idtree_add_above(struct idtree *idp, const void *ptr,
337 int starting_id, int limit)
339 int ret = idtree_get_new_above_int(idp, ptr, starting_id);
341 idtree_remove(idp, ret);