1e2cc2976a330a6f371c748e8913e7d7408a7668
[kai/samba.git] / source4 / lib / util / idtree.c
1 /* 
2    Unix SMB/CIFS implementation.
3
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.
6
7    Copyright (C) Andrew Tridgell 2004
8
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
12     
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.
17    
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.
22    
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/>.
25 */
26
27 /*
28   see the section marked "public interface" below for documentation
29 */
30
31 /**
32  * @file
33  */
34
35 #include "includes.h"
36
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
49
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)))
53                                    
54 struct idr_layer {
55         uint32_t                 bitmap;
56         struct idr_layer        *ary[IDR_SIZE];
57         int                      count;
58 };
59
60 struct idr_context {
61         struct idr_layer *top;
62         struct idr_layer *id_free;
63         int               layers;
64         int               id_free_cnt;
65 };
66
67 static struct idr_layer *alloc_layer(struct idr_context *idp)
68 {
69         struct idr_layer *p;
70
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;
77 }
78
79 static int find_next_bit(uint32_t bm, int maxid, int n)
80 {
81         while (n<maxid && !test_bit(n, bm)) n++;
82         return n;
83 }
84
85 static void free_layer(struct idr_context *idp, struct idr_layer *p)
86 {
87         p->ary[0] = idp->id_free;
88         idp->id_free = p;
89         idp->id_free_cnt++;
90 }
91
92 static int idr_pre_get(struct idr_context *idp)
93 {
94         while (idp->id_free_cnt < IDR_FREE_MAX) {
95                 struct idr_layer *new = talloc_zero(idp, struct idr_layer);
96                 if(new == NULL)
97                         return (0);
98                 free_layer(idp, new);
99         }
100         return 1;
101 }
102
103 static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
104 {
105         int n, m, sh;
106         struct idr_layer *p, *new;
107         struct idr_layer *pa[MAX_LEVEL];
108         int l, id;
109         uint32_t bm;
110
111         memset(pa, 0, sizeof(pa));
112
113         id = *starting_id;
114         p = idp->top;
115         l = idp->layers;
116         pa[l--] = NULL;
117         while (1) {
118                 /*
119                  * We run around this while until we reach the leaf node...
120                  */
121                 n = (id >> (IDR_BITS*l)) & IDR_MASK;
122                 bm = ~p->bitmap;
123                 m = find_next_bit(bm, IDR_SIZE, n);
124                 if (m == IDR_SIZE) {
125                         /* no space available go back to previous layer. */
126                         l++;
127                         id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
128                         if (!(p = pa[l])) {
129                                 *starting_id = id;
130                                 return -2;
131                         }
132                         continue;
133                 }
134                 if (m != n) {
135                         sh = IDR_BITS*l;
136                         id = ((id >> sh) ^ n ^ m) << sh;
137                 }
138                 if ((id >= MAX_ID_BIT) || (id < 0))
139                         return -1;
140                 if (l == 0)
141                         break;
142                 /*
143                  * Create the layer below if it is missing.
144                  */
145                 if (!p->ary[m]) {
146                         if (!(new = alloc_layer(idp)))
147                                 return -1;
148                         p->ary[m] = new;
149                         p->count++;
150                 }
151                 pa[l--] = p;
152                 p = p->ary[m];
153         }
154         /*
155          * We have reached the leaf node, plant the
156          * users pointer and return the raw id.
157          */
158         p->ary[m] = (struct idr_layer *)ptr;
159         set_bit(m, p->bitmap);
160         p->count++;
161         /*
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
165          * up the radix tree.
166          */
167         n = id;
168         while (p->bitmap == IDR_FULL) {
169                 if (!(p = pa[++l]))
170                         break;
171                 n = n >> IDR_BITS;
172                 set_bit((n & IDR_MASK), p->bitmap);
173         }
174         return(id);
175 }
176
177 static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
178 {
179         struct idr_layer *p, *new;
180         int layers, v, id;
181
182         idr_pre_get(idp);
183         
184         id = starting_id;
185 build_up:
186         p = idp->top;
187         layers = idp->layers;
188         if (!p) {
189                 if (!(p = alloc_layer(idp)))
190                         return -1;
191                 layers = 1;
192         }
193         /*
194          * Add a new layer to the top of the tree if the requested
195          * id is larger than the currently allocated space.
196          */
197         while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
198                 layers++;
199                 if (!p->count)
200                         continue;
201                 if (!(new = alloc_layer(idp))) {
202                         /*
203                          * The allocation failed.  If we built part of
204                          * the structure tear it down.
205                          */
206                         for (new = p; p && p != idp->top; new = p) {
207                                 p = p->ary[0];
208                                 new->ary[0] = NULL;
209                                 new->bitmap = new->count = 0;
210                                 free_layer(idp, new);
211                         }
212                         return -1;
213                 }
214                 new->ary[0] = p;
215                 new->count = 1;
216                 if (p->bitmap == IDR_FULL)
217                         set_bit(0, new->bitmap);
218                 p = new;
219         }
220         idp->top = p;
221         idp->layers = layers;
222         v = sub_alloc(idp, ptr, &id);
223         if (v == -2)
224                 goto build_up;
225         return(v);
226 }
227
228 static int sub_remove(struct idr_context *idp, int shift, int id)
229 {
230         struct idr_layer *p = idp->top;
231         struct idr_layer **pa[MAX_LEVEL];
232         struct idr_layer ***paa = &pa[0];
233         int n;
234
235         *paa = NULL;
236         *++paa = &idp->top;
237
238         while ((shift > 0) && p) {
239                 n = (id >> shift) & IDR_MASK;
240                 clear_bit(n, p->bitmap);
241                 *++paa = &p->ary[n];
242                 p = p->ary[n];
243                 shift -= IDR_BITS;
244         }
245         n = id & IDR_MASK;
246         if (p != NULL && test_bit(n, p->bitmap)) {
247                 clear_bit(n, p->bitmap);
248                 p->ary[n] = NULL;
249                 while(*paa && ! --((**paa)->count)){
250                         free_layer(idp, **paa);
251                         **paa-- = NULL;
252                 }
253                 if ( ! *paa )
254                         idp->layers = 0;
255                 return 0;
256         }
257         return -1;
258 }
259
260 static void *_idr_find(struct idr_context *idp, int id)
261 {
262         int n;
263         struct idr_layer *p;
264
265         n = idp->layers * IDR_BITS;
266         p = idp->top;
267         /*
268          * This tests to see if bits outside the current tree are
269          * present.  If so, tain't one of ours!
270          */
271         if ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))
272              return NULL;
273
274         /* Mask off upper bits we don't use for the search. */
275         id &= MAX_ID_MASK;
276
277         while (n >= IDR_BITS && p) {
278                 n -= IDR_BITS;
279                 p = p->ary[(id >> n) & IDR_MASK];
280         }
281         return((void *)p);
282 }
283
284 static int _idr_remove(struct idr_context *idp, int id)
285 {
286         struct idr_layer *p;
287
288         /* Mask off upper bits we don't use for the search. */
289         id &= MAX_ID_MASK;
290
291         if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
292                 return -1;
293         }
294
295         if ( idp->top && idp->top->count == 1 && 
296              (idp->layers > 1) &&
297              idp->top->ary[0]) {
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);
302                 idp->top = p;
303                 --idp->layers;
304         }
305         while (idp->id_free_cnt >= IDR_FREE_MAX) {
306                 p = alloc_layer(idp);
307                 talloc_free(p);
308         }
309         return 0;
310 }
311
312 /************************************************************************
313   this is the public interface
314 **************************************************************************/
315
316 /**
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()
319   on this context
320  */
321 _PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
322 {
323         return talloc_zero(mem_ctx, struct idr_context);
324 }
325
326 /**
327   allocate the next available id, and assign 'ptr' into its slot.
328   you can retrieve later this pointer using idr_find()
329 */
330 _PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit)
331 {
332         int ret = idr_get_new_above_int(idp, ptr, 0);
333         if (ret > limit) {
334                 idr_remove(idp, ret);
335                 return -1;
336         }
337         return ret;
338 }
339
340 /**
341    allocate a new id, giving the first available value greater than or
342    equal to the given starting id
343 */
344 _PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
345 {
346         int ret = idr_get_new_above_int(idp, ptr, starting_id);
347         if (ret > limit) {
348                 idr_remove(idp, ret);
349                 return -1;
350         }
351         return ret;
352 }
353
354 /**
355   allocate a new id randomly in the given range
356 */
357 _PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit)
358 {
359         int id;
360
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);
365         if (id == -1) {
366                 id = idr_get_new_above(idp, ptr, 1+(generate_random()%(limit/2)), limit);
367         }
368         
369         return id;
370 }
371
372 /**
373   find a pointer value previously set with idr_get_new given an id
374 */
375 _PUBLIC_ void *idr_find(struct idr_context *idp, int id)
376 {
377         return _idr_find(idp, id);
378 }
379
380 /**
381   remove an id from the idr tree
382 */
383 _PUBLIC_ int idr_remove(struct idr_context *idp, int id)
384 {
385         int ret;
386         ret = _idr_remove((struct idr_context *)idp, id);
387         if (ret != 0) {
388                 DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));
389         }
390         return ret;
391 }