source: trunk/server/lib/util/idtree.c

Last change on this file was 745, checked in by Silvan Scherrer, 13 years ago

Samba Server: updated trunk to 3.6.0
File size: 9.6 KB
RevLine 
[745]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, 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
54struct idr_layer {
55 uint32_t bitmap;
56 struct idr_layer *ary[IDR_SIZE];
57 int count;
58};
59
60struct idr_context {
61 struct idr_layer *top;
62 struct idr_layer *id_free;
63 int layers;
64 int id_free_cnt;
65};
66
67static 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
79static 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
85static 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
92static int idr_pre_get(struct idr_context *idp)
93{
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);
99 }
100 return 1;
101}
102
103static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
104{
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;
110
111 memset(pa, 0, sizeof(pa));
112
113 id = *starting_id;
114restart:
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 oid = id;
129 id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
130
131 /* if already at the top layer, we need to grow */
132 if (!(p = pa[l])) {
133 *starting_id = id;
134 return -2;
135 }
136
137 /* If we need to go up one layer, continue the
138 * loop; otherwise, restart from the top.
139 */
140 sh = IDR_BITS * (l + 1);
141 if (oid >> sh == id >> sh)
142 continue;
143 else
144 goto restart;
145 }
146 if (m != n) {
147 sh = IDR_BITS*l;
148 id = ((id >> sh) ^ n ^ m) << sh;
149 }
150 if ((id >= MAX_ID_BIT) || (id < 0))
151 return -1;
152 if (l == 0)
153 break;
154 /*
155 * Create the layer below if it is missing.
156 */
157 if (!p->ary[m]) {
158 if (!(pn = alloc_layer(idp)))
159 return -1;
160 p->ary[m] = pn;
161 p->count++;
162 }
163 pa[l--] = p;
164 p = p->ary[m];
165 }
166 /*
167 * We have reached the leaf node, plant the
168 * users pointer and return the raw id.
169 */
170 p->ary[m] = (struct idr_layer *)ptr;
171 set_bit(m, p->bitmap);
172 p->count++;
173 /*
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.
178 */
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);
185 }
186 return(id);
187}
188
189static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
190{
191 struct idr_layer *p, *pn;
192 int layers, v, id;
193
194 idr_pre_get(idp);
195
196 id = starting_id;
197build_up:
198 p = idp->top;
199 layers = idp->layers;
200 if (!p) {
201 if (!(p = alloc_layer(idp)))
202 return -1;
203 layers = 1;
204 }
205 /*
206 * Add a new layer to the top of the tree if the requested
207 * id is larger than the currently allocated space.
208 */
209 while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
210 layers++;
211 if (!p->count)
212 continue;
213 if (!(pn = alloc_layer(idp))) {
214 /*
215 * The allocation failed. If we built part of
216 * the structure tear it down.
217 */
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);
223 }
224 return -1;
225 }
226 pn->ary[0] = p;
227 pn->count = 1;
228 if (p->bitmap == IDR_FULL)
229 set_bit(0, pn->bitmap);
230 p = pn;
231 }
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);
238}
239
240static int sub_remove(struct idr_context *idp, int shift, int id)
241{
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;
246
247 *paa = NULL;
248 *++paa = &idp->top;
249
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;
256 }
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;
264 }
265 if ( ! *paa )
266 idp->layers = 0;
267 return 0;
268 }
269 return -1;
270}
271
272static void *_idr_find(struct idr_context *idp, int id)
273{
274 int n;
275 struct idr_layer *p;
276
277 n = idp->layers * IDR_BITS;
278 p = idp->top;
279 /*
280 * This tests to see if bits outside the current tree are
281 * present. If so, tain't one of ours!
282 */
283 if (n + IDR_BITS < 31 &&
284 ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))) {
285 return NULL;
286 }
287
288 /* Mask off upper bits we don't use for the search. */
289 id &= MAX_ID_MASK;
290
291 while (n >= IDR_BITS && p) {
292 n -= IDR_BITS;
293 p = p->ary[(id >> n) & IDR_MASK];
294 }
295 return((void *)p);
296}
297
298static int _idr_remove(struct idr_context *idp, int id)
299{
300 struct idr_layer *p;
301
302 /* Mask off upper bits we don't use for the search. */
303 id &= MAX_ID_MASK;
304
305 if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
306 return -1;
307 }
308
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;
318 }
319 while (idp->id_free_cnt >= IDR_FREE_MAX) {
320 p = alloc_layer(idp);
321 talloc_free(p);
322 }
323 return 0;
324}
325
326/************************************************************************
327 this is the public interface
328**************************************************************************/
329
330/**
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
334 */
335_PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
336{
337 return talloc_zero(mem_ctx, struct idr_context);
338}
339
340/**
341 allocate the next available id, and assign 'ptr' into its slot.
342 you can retrieve later this pointer using idr_find()
343*/
344_PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit)
345{
346 int ret = idr_get_new_above_int(idp, ptr, 0);
347 if (ret > limit) {
348 idr_remove(idp, ret);
349 return -1;
350 }
351 return ret;
352}
353
354/**
355 allocate a new id, giving the first available value greater than or
356 equal to the given starting id
357*/
358_PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
359{
360 int ret = idr_get_new_above_int(idp, ptr, starting_id);
361 if (ret > limit) {
362 idr_remove(idp, ret);
363 return -1;
364 }
365 return ret;
366}
367
368/**
369 allocate a new id randomly in the given range
370*/
371_PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit)
372{
373 int id;
374
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);
382 }
383 if (id == -1) {
384 id = idr_get_new_above(idp, ptr, 1, limit);
385 }
386
387 return id;
388}
389
390/**
391 find a pointer value previously set with idr_get_new given an id
392*/
393_PUBLIC_ void *idr_find(struct idr_context *idp, int id)
394{
395 return _idr_find(idp, id);
396}
397
398/**
399 remove an id from the idr tree
400*/
401_PUBLIC_ int idr_remove(struct idr_context *idp, int id)
402{
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));
407 }
408 return ret;
409}
Note: See TracBrowser for help on using the repository browser.