]> git.ozlabs.org Git - ccan/blob - ccan/idtree/idtree.c
failtest: add --show-slowest
[ccan] / ccan / idtree / idtree.c
1 /*
2    Based on SAMBA 7ce1356c9f571c55af70bd6b966fe50898c1582d.
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, see <http://www.gnu.org/licenses/>.
25 */
26
27 #include <ccan/idtree/idtree.h>
28 #include <ccan/talloc/talloc.h>
29 #include <stdint.h>
30 #include <string.h>
31
32 #define IDTREE_BITS 5
33 #define IDTREE_FULL 0xfffffffful
34 #if 0 /* unused */
35 #define TOP_LEVEL_FULL (IDTREE_FULL >> 30)
36 #endif
37 #define IDTREE_SIZE (1 << IDTREE_BITS)
38 #define IDTREE_MASK ((1 << IDTREE_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 + IDTREE_BITS - 1) / IDTREE_BITS
43 #define IDTREE_FREE_MAX MAX_LEVEL + MAX_LEVEL
44
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)))
48
49 struct idtree_layer {
50         uint32_t                 bitmap;
51         struct idtree_layer     *ary[IDTREE_SIZE];
52         int                      count;
53 };
54
55 struct idtree {
56         struct idtree_layer *top;
57         struct idtree_layer *id_free;
58         int               layers;
59         int               id_free_cnt;
60 };
61
62 static struct idtree_layer *alloc_layer(struct idtree *idp)
63 {
64         struct idtree_layer *p;
65
66         if (!(p = idp->id_free))
67                 return NULL;
68         idp->id_free = p->ary[0];
69         idp->id_free_cnt--;
70         p->ary[0] = NULL;
71         return p;
72 }
73
74 static int find_next_bit(uint32_t bm, int maxid, int n)
75 {
76         while (n<maxid && !test_bit(n, bm)) n++;
77         return n;
78 }
79
80 static void free_layer(struct idtree *idp, struct idtree_layer *p)
81 {
82         p->ary[0] = idp->id_free;
83         idp->id_free = p;
84         idp->id_free_cnt++;
85 }
86
87 static int idtree_pre_get(struct idtree *idp)
88 {
89         while (idp->id_free_cnt < IDTREE_FREE_MAX) {
90                 struct idtree_layer *pn = talloc_zero(idp, struct idtree_layer);
91                 if(pn == NULL)
92                         return (0);
93                 free_layer(idp, pn);
94         }
95         return 1;
96 }
97
98 static int sub_alloc(struct idtree *idp, const void *ptr, int *starting_id)
99 {
100         int n, m, sh;
101         struct idtree_layer *p, *pn;
102         struct idtree_layer *pa[MAX_LEVEL+1];
103         unsigned int l, id, oid;
104         uint32_t bm;
105
106         memset(pa, 0, sizeof(pa));
107
108         id = *starting_id;
109 restart:
110         p = idp->top;
111         l = idp->layers;
112         pa[l--] = NULL;
113         while (1) {
114                 /*
115                  * We run around this while until we reach the leaf node...
116                  */
117                 n = (id >> (IDTREE_BITS*l)) & IDTREE_MASK;
118                 bm = ~p->bitmap;
119                 m = find_next_bit(bm, IDTREE_SIZE, n);
120                 if (m == IDTREE_SIZE) {
121                         /* no space available go back to previous layer. */
122                         l++;
123                         oid = id;
124                         id = (id | ((1 << (IDTREE_BITS*l))-1)) + 1;
125
126                         /* if already at the top layer, we need to grow */
127                         if (!(p = pa[l])) {
128                                 *starting_id = id;
129                                 return -2;
130                         }
131
132                         /* If we need to go up one layer, continue the
133                          * loop; otherwise, restart from the top.
134                          */
135                         sh = IDTREE_BITS * (l + 1);
136                         if (oid >> sh == id >> sh)
137                         continue;
138                         else
139                                 goto restart;
140                 }
141                 if (m != n) {
142                         sh = IDTREE_BITS*l;
143                         id = ((id >> sh) ^ n ^ m) << sh;
144                 }
145                 if ((id >= MAX_ID_BIT) || (id < 0))
146                         return -1;
147                 if (l == 0)
148                         break;
149                 /*
150                  * Create the layer below if it is missing.
151                  */
152                 if (!p->ary[m]) {
153                         if (!(pn = alloc_layer(idp)))
154                                 return -1;
155                         p->ary[m] = pn;
156                         p->count++;
157                 }
158                 pa[l--] = p;
159                 p = p->ary[m];
160         }
161         /*
162          * We have reached the leaf node, plant the
163          * users pointer and return the raw id.
164          */
165         p->ary[m] = (struct idtree_layer *)ptr;
166         set_bit(m, p->bitmap);
167         p->count++;
168         /*
169          * If this layer is full mark the bit in the layer above
170          * to show that this part of the radix tree is full.
171          * This may complete the layer above and require walking
172          * up the radix tree.
173          */
174         n = id;
175         while (p->bitmap == IDTREE_FULL) {
176                 if (!(p = pa[++l]))
177                         break;
178                 n = n >> IDTREE_BITS;
179                 set_bit((n & IDTREE_MASK), p->bitmap);
180         }
181         return(id);
182 }
183
184 static int idtree_get_new_above_int(struct idtree *idp,
185                                     const void *ptr, int starting_id)
186 {
187         struct idtree_layer *p, *pn;
188         int layers, v, id;
189
190         idtree_pre_get(idp);
191
192         id = starting_id;
193 build_up:
194         p = idp->top;
195         layers = idp->layers;
196         if (!p) {
197                 if (!(p = alloc_layer(idp)))
198                         return -1;
199                 layers = 1;
200         }
201         /*
202          * Add a new layer to the top of the tree if the requested
203          * id is larger than the currently allocated space.
204          */
205         while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDTREE_BITS)))) {
206                 layers++;
207                 if (!p->count)
208                         continue;
209                 if (!(pn = alloc_layer(idp))) {
210                         /*
211                          * The allocation failed.  If we built part of
212                          * the structure tear it down.
213                          */
214                         for (pn = p; p && p != idp->top; pn = p) {
215                                 p = p->ary[0];
216                                 pn->ary[0] = NULL;
217                                 pn->bitmap = pn->count = 0;
218                                 free_layer(idp, pn);
219                         }
220                         return -1;
221                 }
222                 pn->ary[0] = p;
223                 pn->count = 1;
224                 if (p->bitmap == IDTREE_FULL)
225                         set_bit(0, pn->bitmap);
226                 p = pn;
227         }
228         idp->top = p;
229         idp->layers = layers;
230         v = sub_alloc(idp, ptr, &id);
231         if (v == -2)
232                 goto build_up;
233         return(v);
234 }
235
236 static int sub_remove(struct idtree *idp, int shift, int id)
237 {
238         struct idtree_layer *p = idp->top;
239         struct idtree_layer **pa[1+MAX_LEVEL];
240         struct idtree_layer ***paa = &pa[0];
241         int n;
242
243         *paa = NULL;
244         *++paa = &idp->top;
245
246         while ((shift > 0) && p) {
247                 n = (id >> shift) & IDTREE_MASK;
248                 clear_bit(n, p->bitmap);
249                 *++paa = &p->ary[n];
250                 p = p->ary[n];
251                 shift -= IDTREE_BITS;
252         }
253         n = id & IDTREE_MASK;
254         if (p != NULL && test_bit(n, p->bitmap)) {
255                 clear_bit(n, p->bitmap);
256                 p->ary[n] = NULL;
257                 while(*paa && ! --((**paa)->count)){
258                         free_layer(idp, **paa);
259                         **paa-- = NULL;
260                 }
261                 if ( ! *paa )
262                         idp->layers = 0;
263                 return 0;
264         }
265         return -1;
266 }
267
268 void *idtree_lookup(const struct idtree *idp, int id)
269 {
270         int n;
271         struct idtree_layer *p;
272
273         n = idp->layers * IDTREE_BITS;
274         p = idp->top;
275         /*
276          * This tests to see if bits outside the current tree are
277          * present.  If so, tain't one of ours!
278          */
279         if (n + IDTREE_BITS < 31 &&
280             (id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDTREE_BITS))
281              return NULL;
282
283         /* Mask off upper bits we don't use for the search. */
284         id &= MAX_ID_MASK;
285
286         while (n >= IDTREE_BITS && p) {
287                 n -= IDTREE_BITS;
288                 p = p->ary[(id >> n) & IDTREE_MASK];
289         }
290         return((void *)p);
291 }
292
293 bool idtree_remove(struct idtree *idp, int id)
294 {
295         struct idtree_layer *p;
296
297         /* Mask off upper bits we don't use for the search. */
298         id &= MAX_ID_MASK;
299
300         if (sub_remove(idp, (idp->layers - 1) * IDTREE_BITS, id) == -1) {
301                 return false;
302         }
303
304         if ( idp->top && idp->top->count == 1 &&
305              (idp->layers > 1) &&
306              idp->top->ary[0]) {
307                 /* We can drop a layer */
308                 p = idp->top->ary[0];
309                 idp->top->bitmap = idp->top->count = 0;
310                 free_layer(idp, idp->top);
311                 idp->top = p;
312                 --idp->layers;
313         }
314         while (idp->id_free_cnt >= IDTREE_FREE_MAX) {
315                 p = alloc_layer(idp);
316                 talloc_free(p);
317         }
318         return true;
319 }
320
321 struct idtree *idtree_new(void *mem_ctx)
322 {
323         return talloc_zero(mem_ctx, struct idtree);
324 }
325
326 int idtree_add(struct idtree *idp, const void *ptr, int limit)
327 {
328         int ret = idtree_get_new_above_int(idp, ptr, 0);
329         if (ret > limit) {
330                 idtree_remove(idp, ret);
331                 return -1;
332         }
333         return ret;
334 }
335
336 int idtree_add_above(struct idtree *idp, const void *ptr,
337                      int starting_id, int limit)
338 {
339         int ret = idtree_get_new_above_int(idp, ptr, starting_id);
340         if (ret > limit) {
341                 idtree_remove(idp, ret);
342                 return -1;
343         }
344         return ret;
345 }