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