git.ozlabs.org Git - ccan/blob - 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 }