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

Last change on this file since 667 was 414, checked in by Herwig Bauernfeind, 16 years ago

Samba 3.5.0: Initial import
File size: 9.2 KB
Line 
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];
108 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[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 ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))
284 return NULL;
285
286 /* Mask off upper bits we don't use for the search. */
287 id &= MAX_ID_MASK;
288
289 while (n >= IDR_BITS && p) {
290 n -= IDR_BITS;
291 p = p->ary[(id >> n) & IDR_MASK];
292 }
293 return((void *)p);
294}
295
296static int _idr_remove(struct idr_context *idp, int id)
297{
298 struct idr_layer *p;
299
300 /* Mask off upper bits we don't use for the search. */
301 id &= MAX_ID_MASK;
302
303 if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
304 return -1;
305 }
306
307 if ( idp->top && idp->top->count == 1 &&
308 (idp->layers > 1) &&
309 idp->top->ary[0]) {
310 /* We can drop a layer */
311 p = idp->top->ary[0];
312 idp->top->bitmap = idp->top->count = 0;
313 free_layer(idp, idp->top);
314 idp->top = p;
315 --idp->layers;
316 }
317 while (idp->id_free_cnt >= IDR_FREE_MAX) {
318 p = alloc_layer(idp);
319 talloc_free(p);
320 }
321 return 0;
322}
323
324/************************************************************************
325 this is the public interface
326**************************************************************************/
327
328/**
329 initialise a idr tree. The context return value must be passed to
330 all subsequent idr calls. To destroy the idr tree use talloc_free()
331 on this context
332 */
333_PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
334{
335 return talloc_zero(mem_ctx, struct idr_context);
336}
337
338/**
339 allocate the next available id, and assign 'ptr' into its slot.
340 you can retrieve later this pointer using idr_find()
341*/
342_PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit)
343{
344 int ret = idr_get_new_above_int(idp, ptr, 0);
345 if (ret > limit) {
346 idr_remove(idp, ret);
347 return -1;
348 }
349 return ret;
350}
351
352/**
353 allocate a new id, giving the first available value greater than or
354 equal to the given starting id
355*/
356_PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
357{
358 int ret = idr_get_new_above_int(idp, ptr, starting_id);
359 if (ret > limit) {
360 idr_remove(idp, ret);
361 return -1;
362 }
363 return ret;
364}
365
366/**
367 allocate a new id randomly in the given range
368*/
369_PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit)
370{
371 int id;
372
373 /* first try a random starting point in the whole range, and if that fails,
374 then start randomly in the bottom half of the range. This can only
375 fail if the range is over half full, and finally fallback to any
376 free id */
377 id = idr_get_new_above(idp, ptr, 1+(generate_random() % limit), limit);
378 if (id == -1) {
379 id = idr_get_new_above(idp, ptr, 1+(generate_random()%(limit/2)), limit);
380 }
381 if (id == -1) {
382 id = idr_get_new_above(idp, ptr, 1, limit);
383 }
384
385 return id;
386}
387
388/**
389 find a pointer value previously set with idr_get_new given an id
390*/
391_PUBLIC_ void *idr_find(struct idr_context *idp, int id)
392{
393 return _idr_find(idp, id);
394}
395
396/**
397 remove an id from the idr tree
398*/
399_PUBLIC_ int idr_remove(struct idr_context *idp, int id)
400{
401 int ret;
402 ret = _idr_remove((struct idr_context *)idp, id);
403 if (ret != 0) {
404 DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));
405 }
406 return ret;
407}
Note: See TracBrowser for help on using the repository browser.