Remove unneeded initializations (we already talloc_zero).
[Samba.git] / lib / util / idtree.c
blob364876106929a545441eb3c165e31cc5024a7082
1 /*
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, see <http://www.gnu.org/licenses/>.
28 see the section marked "public interface" below for documentation
31 /**
32 * @file
35 #include "includes.h"
37 #define IDR_BITS 5
38 #define IDR_FULL 0xfffffffful
39 #if 0 /* unused */
40 #define TOP_LEVEL_FULL (IDR_FULL >> 30)
41 #endif
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)))
54 struct idr_layer {
55 uint32_t bitmap;
56 struct idr_layer *ary[IDR_SIZE];
57 int count;
60 struct idr_context {
61 struct idr_layer *top;
62 struct idr_layer *id_free;
63 int layers;
64 int id_free_cnt;
67 static struct idr_layer *alloc_layer(struct idr_context *idp)
69 struct idr_layer *p;
71 if (!(p = idp->id_free))
72 return NULL;
73 idp->id_free = p->ary[0];
74 idp->id_free_cnt--;
75 p->ary[0] = NULL;
76 return p;
79 static int find_next_bit(uint32_t bm, int maxid, int n)
81 while (n<maxid && !test_bit(n, bm)) n++;
82 return n;
85 static void free_layer(struct idr_context *idp, struct idr_layer *p)
87 p->ary[0] = idp->id_free;
88 idp->id_free = p;
89 idp->id_free_cnt++;
92 static int idr_pre_get(struct idr_context *idp)
94 while (idp->id_free_cnt < IDR_FREE_MAX) {
95 struct idr_layer *pn = talloc_zero(idp, struct idr_layer);
96 if(pn == NULL)
97 return (0);
98 free_layer(idp, pn);
100 return 1;
103 static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
105 int n, m, sh;
106 struct idr_layer *p, *pn;
107 struct idr_layer *pa[MAX_LEVEL+1];
108 unsigned int l, id, oid;
109 uint32_t bm;
111 memset(pa, 0, sizeof(pa));
113 id = *starting_id;
114 restart:
115 p = idp->top;
116 l = idp->layers;
117 pa[l--] = NULL;
118 while (1) {
120 * We run around this while until we reach the leaf node...
122 n = (id >> (IDR_BITS*l)) & IDR_MASK;
123 bm = ~p->bitmap;
124 m = find_next_bit(bm, IDR_SIZE, n);
125 if (m == IDR_SIZE) {
126 /* no space available go back to previous layer. */
127 l++;
128 oid = id;
129 id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
131 /* if already at the top layer, we need to grow */
132 if (!(p = pa[l])) {
133 *starting_id = id;
134 return -2;
137 /* If we need to go up one layer, continue the
138 * loop; otherwise, restart from the top.
140 sh = IDR_BITS * (l + 1);
141 if (oid >> sh == id >> sh)
142 continue;
143 else
144 goto restart;
146 if (m != n) {
147 sh = IDR_BITS*l;
148 id = ((id >> sh) ^ n ^ m) << sh;
150 if ((id >= MAX_ID_BIT) || (id < 0))
151 return -1;
152 if (l == 0)
153 break;
155 * Create the layer below if it is missing.
157 if (!p->ary[m]) {
158 if (!(pn = alloc_layer(idp)))
159 return -1;
160 p->ary[m] = pn;
161 p->count++;
163 pa[l--] = p;
164 p = p->ary[m];
167 * We have reached the leaf node, plant the
168 * users pointer and return the raw id.
170 p->ary[m] = (struct idr_layer *)ptr;
171 set_bit(m, p->bitmap);
172 p->count++;
174 * If this layer is full mark the bit in the layer above
175 * to show that this part of the radix tree is full.
176 * This may complete the layer above and require walking
177 * up the radix tree.
179 n = id;
180 while (p->bitmap == IDR_FULL) {
181 if (!(p = pa[++l]))
182 break;
183 n = n >> IDR_BITS;
184 set_bit((n & IDR_MASK), p->bitmap);
186 return(id);
189 static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
191 struct idr_layer *p, *pn;
192 int layers, v, id;
194 idr_pre_get(idp);
196 id = starting_id;
197 build_up:
198 p = idp->top;
199 layers = idp->layers;
200 if (!p) {
201 if (!(p = alloc_layer(idp)))
202 return -1;
203 layers = 1;
206 * Add a new layer to the top of the tree if the requested
207 * id is larger than the currently allocated space.
209 while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
210 layers++;
211 if (!p->count)
212 continue;
213 if (!(pn = alloc_layer(idp))) {
215 * The allocation failed. If we built part of
216 * the structure tear it down.
218 for (pn = p; p && p != idp->top; pn = p) {
219 p = p->ary[0];
220 pn->ary[0] = NULL;
221 pn->bitmap = pn->count = 0;
222 free_layer(idp, pn);
224 return -1;
226 pn->ary[0] = p;
227 pn->count = 1;
228 if (p->bitmap == IDR_FULL)
229 set_bit(0, pn->bitmap);
230 p = pn;
232 idp->top = p;
233 idp->layers = layers;
234 v = sub_alloc(idp, ptr, &id);
235 if (v == -2)
236 goto build_up;
237 return(v);
240 static int sub_remove(struct idr_context *idp, int shift, int id)
242 struct idr_layer *p = idp->top;
243 struct idr_layer **pa[1+MAX_LEVEL];
244 struct idr_layer ***paa = &pa[0];
245 int n;
247 *paa = NULL;
248 *++paa = &idp->top;
250 while ((shift > 0) && p) {
251 n = (id >> shift) & IDR_MASK;
252 clear_bit(n, p->bitmap);
253 *++paa = &p->ary[n];
254 p = p->ary[n];
255 shift -= IDR_BITS;
257 n = id & IDR_MASK;
258 if (p != NULL && test_bit(n, p->bitmap)) {
259 clear_bit(n, p->bitmap);
260 p->ary[n] = NULL;
261 while(*paa && ! --((**paa)->count)){
262 free_layer(idp, **paa);
263 **paa-- = NULL;
265 if ( ! *paa )
266 idp->layers = 0;
267 return 0;
269 return -1;
272 static void *_idr_find(struct idr_context *idp, int id)
274 int n;
275 struct idr_layer *p;
277 n = idp->layers * IDR_BITS;
278 p = idp->top;
280 * This tests to see if bits outside the current tree are
281 * present. If so, tain't one of ours!
283 if (n + IDR_BITS < 31 &&
284 ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))) {
285 return NULL;
288 /* Mask off upper bits we don't use for the search. */
289 id &= MAX_ID_MASK;
291 while (n >= IDR_BITS && p) {
292 n -= IDR_BITS;
293 p = p->ary[(id >> n) & IDR_MASK];
295 return((void *)p);
298 static int _idr_remove(struct idr_context *idp, int id)
300 struct idr_layer *p;
302 /* Mask off upper bits we don't use for the search. */
303 id &= MAX_ID_MASK;
305 if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
306 return -1;
309 if ( idp->top && idp->top->count == 1 &&
310 (idp->layers > 1) &&
311 idp->top->ary[0]) {
312 /* We can drop a layer */
313 p = idp->top->ary[0];
314 idp->top->bitmap = idp->top->count = 0;
315 free_layer(idp, idp->top);
316 idp->top = p;
317 --idp->layers;
319 while (idp->id_free_cnt >= IDR_FREE_MAX) {
320 p = alloc_layer(idp);
321 talloc_free(p);
323 return 0;
326 /************************************************************************
327 this is the public interface
328 **************************************************************************/
331 initialise a idr tree. The context return value must be passed to
332 all subsequent idr calls. To destroy the idr tree use talloc_free()
333 on this context
335 _PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
337 return talloc_zero(mem_ctx, struct idr_context);
341 allocate the next available id, and assign 'ptr' into its slot.
342 you can retrieve later this pointer using idr_find()
344 _PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit)
346 int ret = idr_get_new_above_int(idp, ptr, 0);
347 if (ret > limit) {
348 idr_remove(idp, ret);
349 return -1;
351 return ret;
355 allocate a new id, giving the first available value greater than or
356 equal to the given starting id
358 _PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
360 int ret = idr_get_new_above_int(idp, ptr, starting_id);
361 if (ret > limit) {
362 idr_remove(idp, ret);
363 return -1;
365 return ret;
369 allocate a new id randomly in the given range
371 _PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit)
373 int id;
375 /* first try a random starting point in the whole range, and if that fails,
376 then start randomly in the bottom half of the range. This can only
377 fail if the range is over half full, and finally fallback to any
378 free id */
379 id = idr_get_new_above(idp, ptr, 1+(generate_random() % limit), limit);
380 if (id == -1) {
381 id = idr_get_new_above(idp, ptr, 1+(generate_random()%(limit/2)), limit);
383 if (id == -1) {
384 id = idr_get_new_above(idp, ptr, 1, limit);
387 return id;
391 find a pointer value previously set with idr_get_new given an id
393 _PUBLIC_ void *idr_find(struct idr_context *idp, int id)
395 return _idr_find(idp, id);
399 remove an id from the idr tree
401 _PUBLIC_ int idr_remove(struct idr_context *idp, int id)
403 int ret;
404 ret = _idr_remove((struct idr_context *)idp, id);
405 if (ret != 0) {
406 DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));
408 return ret;