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 }