2 Unix SMB/CIFS implementation.
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, write to the Free Software
25 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
29 see the section marked "public interface" below for documentation
35 #define IDR_FULL 0xfffffffful
36 #define TOP_LEVEL_FULL (IDR_FULL >> 30)
37 #define IDR_SIZE (1 << IDR_BITS)
38 #define IDR_MASK ((1 << IDR_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 + IDR_BITS - 1) / IDR_BITS
43 #define IDR_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 idr_layer *ary[IDR_SIZE];
56 struct idr_layer *top;
57 struct idr_layer *id_free;
62 static struct idr_layer *alloc_layer(struct idr_context *idp)
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 idr_context *idp, struct idr_layer *p)
82 p->ary[0] = idp->id_free;
87 static int idr_pre_get(struct idr_context *idp)
89 while (idp->id_free_cnt < IDR_FREE_MAX) {
90 struct idr_layer *new = talloc_zero(idp, struct idr_layer);
98 static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
101 struct idr_layer *p, *new;
102 struct idr_layer *pa[MAX_LEVEL];
112 * We run around this while until we reach the leaf node...
114 n = (id >> (IDR_BITS*l)) & IDR_MASK;
116 m = find_next_bit(bm, IDR_SIZE, n);
118 /* no space available go back to previous layer. */
120 id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
129 id = ((id >> sh) ^ n ^ m) << sh;
131 if ((id >= MAX_ID_BIT) || (id < 0))
136 * Create the layer below if it is missing.
139 if (!(new = alloc_layer(idp)))
148 * We have reached the leaf node, plant the
149 * users pointer and return the raw id.
151 p->ary[m] = (struct idr_layer *)ptr;
152 set_bit(m, p->bitmap);
155 * If this layer is full mark the bit in the layer above
156 * to show that this part of the radix tree is full.
157 * This may complete the layer above and require walking
161 while (p->bitmap == IDR_FULL) {
165 set_bit((n & IDR_MASK), p->bitmap);
170 static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
172 struct idr_layer *p, *new;
180 layers = idp->layers;
182 if (!(p = alloc_layer(idp)))
187 * Add a new layer to the top of the tree if the requested
188 * id is larger than the currently allocated space.
190 while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
194 if (!(new = alloc_layer(idp))) {
196 * The allocation failed. If we built part of
197 * the structure tear it down.
199 for (new = p; p && p != idp->top; new = p) {
202 new->bitmap = new->count = 0;
203 free_layer(idp, new);
209 if (p->bitmap == IDR_FULL)
210 set_bit(0, new->bitmap);
214 idp->layers = layers;
215 v = sub_alloc(idp, ptr, &id);
221 static int sub_remove(struct idr_context *idp, int shift, int id)
223 struct idr_layer *p = idp->top;
224 struct idr_layer **pa[MAX_LEVEL];
225 struct idr_layer ***paa = &pa[0];
231 while ((shift > 0) && p) {
232 n = (id >> shift) & IDR_MASK;
233 clear_bit(n, p->bitmap);
239 if (p != NULL && test_bit(n, p->bitmap)) {
240 clear_bit(n, p->bitmap);
242 while(*paa && ! --((**paa)->count)){
243 free_layer(idp, **paa);
253 static void *_idr_find(struct idr_context *idp, int id)
258 n = idp->layers * IDR_BITS;
261 * This tests to see if bits outside the current tree are
262 * present. If so, tain't one of ours!
264 if ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))
267 /* Mask off upper bits we don't use for the search. */
272 p = p->ary[(id >> n) & IDR_MASK];
277 static int _idr_remove(struct idr_context *idp, int id)
281 /* Mask off upper bits we don't use for the search. */
284 if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
288 if ( idp->top && idp->top->count == 1 &&
291 /* We can drop a layer */
292 p = idp->top->ary[0];
293 idp->top->bitmap = idp->top->count = 0;
294 free_layer(idp, idp->top);
298 while (idp->id_free_cnt >= IDR_FREE_MAX) {
299 p = alloc_layer(idp);
305 /************************************************************************
306 this is the public interface
307 **************************************************************************/
310 initialise a idr tree. The context return value must be passed to
311 all subsequent idr calls. To destroy the idr tree use talloc_free()
314 struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
316 return talloc_zero(mem_ctx, struct idr_context);
320 allocate the next available id, and assign 'ptr' into its slot.
321 you can retrieve later this pointer using idr_find()
323 int idr_get_new(struct idr_context *idp, void *ptr, int limit)
325 int ret = idr_get_new_above_int(idp, ptr, 0);
327 idr_remove(idp, ret);
334 allocate a new id, giving the first available value greater than or
335 equal to the given starting id
337 int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
339 int ret = idr_get_new_above_int(idp, ptr, starting_id);
341 idr_remove(idp, ret);
348 allocate a new id randomly in the given range
350 int idr_get_new_random(struct idr_context *idp, void *ptr, int limit)
354 /* first try a random starting point in the whole range, and if that fails,
355 then start randomly in the bottom half of the range. This can only
356 fail if the range is over half full */
357 id = idr_get_new_above(idp, ptr, 1+(generate_random() % limit), limit);
359 id = idr_get_new_above(idp, ptr, 1+(generate_random()%(limit/2)), limit);
366 find a pointer value previously set with idr_get_new given an id
368 void *idr_find(struct idr_context *idp, int id)
370 return _idr_find(idp, id);
374 remove an id from the idr tree
376 int idr_remove(struct idr_context *idp, int id)
379 ret = _idr_remove((struct idr_context *)idp, id);
381 DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));