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 3 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/>.
28 see the section marked "public interface" below for documentation
38 #define IDR_FULL 0xfffffffful
40 #define TOP_LEVEL_FULL (IDR_FULL >> 30)
42 #define IDR_SIZE (1 << IDR_BITS)
43 #define IDR_MASK ((1 << IDR_BITS)-1)
44 #define MAX_ID_SHIFT (sizeof(int)*8 - 1)
45 #define MAX_ID_BIT (1U << MAX_ID_SHIFT)
46 #define MAX_ID_MASK (MAX_ID_BIT - 1)
47 #define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS
48 #define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL
50 #define set_bit(bit, v) (v) |= (1<<(bit))
51 #define clear_bit(bit, v) (v) &= ~(1<<(bit))
52 #define test_bit(bit, v) ((v) & (1<<(bit)))
56 struct idr_layer *ary[IDR_SIZE];
61 struct idr_layer *top;
62 struct idr_layer *id_free;
67 static struct idr_layer *alloc_layer(struct idr_context *idp)
71 if (!(p = idp->id_free))
73 idp->id_free = p->ary[0];
79 static int find_next_bit(uint32_t bm, int maxid, int n)
81 while (n<maxid && !test_bit(n, bm)) n++;
85 static void free_layer(struct idr_context *idp, struct idr_layer *p)
87 p->ary[0] = idp->id_free;
92 static int idr_pre_get(struct idr_context *idp)
94 while (idp->id_free_cnt < IDR_FREE_MAX) {
95 struct idr_layer *new = talloc_zero(idp, struct idr_layer);
103 static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
106 struct idr_layer *p, *new;
107 struct idr_layer *pa[MAX_LEVEL];
111 memset(pa, 0, sizeof(pa));
119 * We run around this while until we reach the leaf node...
121 n = (id >> (IDR_BITS*l)) & IDR_MASK;
123 m = find_next_bit(bm, IDR_SIZE, n);
125 /* no space available go back to previous layer. */
127 id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
136 id = ((id >> sh) ^ n ^ m) << sh;
138 if ((id >= MAX_ID_BIT) || (id < 0))
143 * Create the layer below if it is missing.
146 if (!(new = alloc_layer(idp)))
155 * We have reached the leaf node, plant the
156 * users pointer and return the raw id.
158 p->ary[m] = (struct idr_layer *)ptr;
159 set_bit(m, p->bitmap);
162 * If this layer is full mark the bit in the layer above
163 * to show that this part of the radix tree is full.
164 * This may complete the layer above and require walking
168 while (p->bitmap == IDR_FULL) {
172 set_bit((n & IDR_MASK), p->bitmap);
177 static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
179 struct idr_layer *p, *new;
187 layers = idp->layers;
189 if (!(p = alloc_layer(idp)))
194 * Add a new layer to the top of the tree if the requested
195 * id is larger than the currently allocated space.
197 while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
201 if (!(new = alloc_layer(idp))) {
203 * The allocation failed. If we built part of
204 * the structure tear it down.
206 for (new = p; p && p != idp->top; new = p) {
209 new->bitmap = new->count = 0;
210 free_layer(idp, new);
216 if (p->bitmap == IDR_FULL)
217 set_bit(0, new->bitmap);
221 idp->layers = layers;
222 v = sub_alloc(idp, ptr, &id);
228 static int sub_remove(struct idr_context *idp, int shift, int id)
230 struct idr_layer *p = idp->top;
231 struct idr_layer **pa[MAX_LEVEL];
232 struct idr_layer ***paa = &pa[0];
238 while ((shift > 0) && p) {
239 n = (id >> shift) & IDR_MASK;
240 clear_bit(n, p->bitmap);
246 if (p != NULL && test_bit(n, p->bitmap)) {
247 clear_bit(n, p->bitmap);
249 while(*paa && ! --((**paa)->count)){
250 free_layer(idp, **paa);
260 static void *_idr_find(struct idr_context *idp, int id)
265 n = idp->layers * IDR_BITS;
268 * This tests to see if bits outside the current tree are
269 * present. If so, tain't one of ours!
271 if ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))
274 /* Mask off upper bits we don't use for the search. */
277 while (n >= IDR_BITS && p) {
279 p = p->ary[(id >> n) & IDR_MASK];
284 static int _idr_remove(struct idr_context *idp, int id)
288 /* Mask off upper bits we don't use for the search. */
291 if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
295 if ( idp->top && idp->top->count == 1 &&
298 /* We can drop a layer */
299 p = idp->top->ary[0];
300 idp->top->bitmap = idp->top->count = 0;
301 free_layer(idp, idp->top);
305 while (idp->id_free_cnt >= IDR_FREE_MAX) {
306 p = alloc_layer(idp);
312 /************************************************************************
313 this is the public interface
314 **************************************************************************/
317 initialise a idr tree. The context return value must be passed to
318 all subsequent idr calls. To destroy the idr tree use talloc_free()
321 _PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
323 return talloc_zero(mem_ctx, struct idr_context);
327 allocate the next available id, and assign 'ptr' into its slot.
328 you can retrieve later this pointer using idr_find()
330 _PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit)
332 int ret = idr_get_new_above_int(idp, ptr, 0);
334 idr_remove(idp, ret);
341 allocate a new id, giving the first available value greater than or
342 equal to the given starting id
344 _PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
346 int ret = idr_get_new_above_int(idp, ptr, starting_id);
348 idr_remove(idp, ret);
355 allocate a new id randomly in the given range
357 _PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit)
361 /* first try a random starting point in the whole range, and if that fails,
362 then start randomly in the bottom half of the range. This can only
363 fail if the range is over half full */
364 id = idr_get_new_above(idp, ptr, 1+(generate_random() % limit), limit);
366 id = idr_get_new_above(idp, ptr, 1+(generate_random()%(limit/2)), limit);
373 find a pointer value previously set with idr_get_new given an id
375 _PUBLIC_ void *idr_find(struct idr_context *idp, int id)
377 return _idr_find(idp, id);
381 remove an id from the idr tree
383 _PUBLIC_ int idr_remove(struct idr_context *idp, int id)
386 ret = _idr_remove((struct idr_context *)idp, id);
388 DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));