libbanshee/libcompat/radix-tree.c

   1 /*
   2  * Modified to work in GCC in 2003 by Daniel Berlin
   3  * Copyright (C) 2001 Momchil Velikov
   4  * Portions Copyright (C) 2001 Christoph Hellwig
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License as
   8  * published by the Free Software Foundation; either version 2, or (at
   9  * your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19  */
  20 #include <unistd.h>
  21 #include <stdio.h>
  22 #include <errno.h>
  23 #include <stdlib.h>
  24 #include  "radix-tree.h"
  25 #define ARRAY_SIZE(a) (sizeof (a) / sizeof ((a)[0]))
  26 /*
  27  * Radix tree node definition.
  28  */
  29 #define RADIX_TREE_MAP_SHIFT  6
  30 #define RADIX_TREE_MAP_SIZE  (1UL << RADIX_TREE_MAP_SHIFT)
  31 #define RADIX_TREE_MAP_MASK  (RADIX_TREE_MAP_SIZE-1)
  32
  33 struct radix_tree_node {
  34   unsigned int  count;
  35   void          *slots[RADIX_TREE_MAP_SIZE];
  36 };
  37
  38 struct radix_tree_path {
  39   struct radix_tree_node *node, **slot;
  40 };
  41
  42 #define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
  43 #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
  44
  45 static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH];
  46
  47
  48 /*
  49  * This assumes that the caller has performed appropriate preallocation, and
  50  * that the caller has pinned this thread of control to the current CPU.
  51  */
  52 static struct radix_tree_node *
  53 radix_tree_node_alloc(struct radix_tree_root *root)
  54 {
  55   struct radix_tree_node *ret;
  56
  57   ret = (struct radix_tree_node *)
  58     calloc (1, sizeof (struct radix_tree_node));
  59   if (!ret)
  60     abort ();
  61   return ret;
  62 }
  63
  64 static inline void
  65 radix_tree_node_free(struct radix_tree_node *node)
  66 {
  67   free (node);
  68 }
  69
  70
  71 /*
  72  *      Return the maximum key which can be store into a
  73  *      radix tree with height HEIGHT.
  74  */
  75 static inline unsigned long radix_tree_maxindex(unsigned int height)
  76 {
  77   return height_to_maxindex[height];
  78 }
  79
  80 /*
  81  *      Extend a radix tree so it can store key @index.
  82  */
  83 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
  84 {
  85   struct radix_tree_node *node;
  86   unsigned int height;
  87
  88   /* Figure out what the height should be.  */
  89   height = root->height + 1;
  90   while (index > radix_tree_maxindex(height))
  91     height++;
  92
  93   if (root->rnode) {
  94     do {
  95       if (!(node = radix_tree_node_alloc(root)))
  96         return -ENOMEM;
  97
  98       /* Increase the height.  */
  99       node->slots[0] = root->rnode;
 100       node->count = 1;
 101       root->rnode = node;
 102       root->height++;
 103     } while (height > root->height);
 104   } else
 105     root->height = height;
 106
 107   return 0;
 108 }
 109
 110 /**
 111  *      radix_tree_insert    -    insert into a radix tree
 112  *      @root:          radix tree root
 113  *      @index:         index key
 114  *      @item:          item to insert
 115  *
 116  *      Insert an item into the radix tree at position @index.
 117  */
 118 int radix_tree_insert(struct radix_tree_root *root, unsigned long index,
 119                       void *item)
 120 {
 121   struct radix_tree_node *node = NULL, *tmp, **slot;
 122   unsigned int height, shift;
 123   int error;
 124
 125   /* Make sure the tree is high enough.  */
 126   if (index > radix_tree_maxindex(root->height)) {
 127     error = radix_tree_extend(root, index);
 128     if (error)
 129       return error;
 130   }
 131
 132   slot = &root->rnode;
 133   height = root->height;
 134   shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 135
 136   while (height > 0) {
 137     if (*slot == NULL) {
 138       /* Have to add a child node.  */
 139       if (!(tmp = radix_tree_node_alloc(root)))
 140         return -ENOMEM;
 141       *slot = tmp;
 142       if (node)
 143         node->count++;
 144     }
 145
 146     /* Go a level down.  */
 147     node = *slot;
 148     slot = (struct radix_tree_node **)
 149       (node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
 150     shift -= RADIX_TREE_MAP_SHIFT;
 151     height--;
 152   }
 153
 154   if (*slot != NULL)
 155     return -EEXIST;
 156   if (node)
 157     node->count++;
 158
 159   *slot = item;
 160   return 0;
 161 }
 162
 163 /**
 164  *      radix_tree_lookup    -    perform lookup operation on a radix tree
 165  *      @root:          radix tree root
 166  *      @index:         index key
 167  *
 168  *      Lookup them item at the position @index in the radix tree @root.
 169  */
 170 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
 171 {
 172   unsigned int height, shift;
 173   struct radix_tree_node **slot;
 174
 175   height = root->height;
 176   if (index > radix_tree_maxindex(height))
 177     return NULL;
 178
 179   shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 180   slot = &root->rnode;
 181
 182   while (height > 0) {
 183     if (*slot == NULL)
 184       return NULL;
 185
 186     slot = (struct radix_tree_node **)
 187       ((*slot)->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
 188     shift -= RADIX_TREE_MAP_SHIFT;
 189     height--;
 190   }
 191
 192   return (void *) *slot;
 193 }
 194
 195 static /* inline */ unsigned int
 196 __lookup(struct radix_tree_root *root, void **results, unsigned long index,
 197          unsigned int max_items, unsigned long *next_index)
 198 {
 199   unsigned int nr_found = 0;
 200   unsigned int shift;
 201   unsigned int height = root->height;
 202   struct radix_tree_node *slot;
 203
 204   shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 205   slot = root->rnode;
 206
 207   while (height > 0) {
 208     unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;
 209
 210     for ( ; i < RADIX_TREE_MAP_SIZE; i++) {
 211       if (slot->slots[i] != NULL)
 212         break;
 213       index &= ~((1 << shift) - 1);
 214       index += 1 << shift;
 215       if (index == 0)
 216         goto out;       /* 32-bit wraparound */
 217     }
 218     if (i == RADIX_TREE_MAP_SIZE)
 219       goto out;
 220     height--;
 221     if (height == 0) {  /* Bottom level: grab some items */
 222       unsigned long j = index & RADIX_TREE_MAP_MASK;
 223
 224       for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
 225         index++;
 226         if (slot->slots[j]) {
 227           results[nr_found++] = slot->slots[j];
 228           if (nr_found == max_items)
 229             goto out;
 230         }
 231       }
 232     }
 233     shift -= RADIX_TREE_MAP_SHIFT;
 234     slot = slot->slots[i];
 235   }
 236  out:
 237   *next_index = index;
 238   return nr_found;
 239 }
 240
 241 /**
 242  *      radix_tree_gang_lookup - perform multiple lookup on a radix tree
 243  *      @root:          radix tree root
 244  *      @results:       where the results of the lookup are placed
 245  *      @first_index:   start the lookup from this key
 246  *      @max_items:     place up to this many items at *results
 247  *
 248  *      Performs an index-ascending scan of the tree for present items.  Places
 249  *      them at *@results and returns the number of items which were placed at
 250  *      *@results.
 251  *
 252  *      The implementation is naive.
 253  */
 254 unsigned int
 255 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
 256                        unsigned long first_index, unsigned int max_items)
 257 {
 258   const unsigned long max_index = radix_tree_maxindex(root->height);
 259   unsigned long cur_index = first_index;
 260   unsigned int ret = 0;
 261
 262   if (root->rnode == NULL)
 263     goto out;
 264   if (max_index == 0) {                 /* Bah.  Special case */
 265     if (first_index == 0) {
 266       if (max_items > 0) {
 267         *results = root->rnode;
 268         ret = 1;
 269       }
 270     }
 271     goto out;
 272   }
 273   while (ret < max_items) {
 274     unsigned int nr_found;
 275     unsigned long next_index;   /* Index of next search */
 276
 277     if (cur_index > max_index)
 278       break;
 279     nr_found = __lookup(root, results + ret, cur_index,
 280                         max_items - ret, &next_index);
 281     ret += nr_found;
 282     if (next_index == 0)
 283       break;
 284     cur_index = next_index;
 285   }
 286  out:
 287   return ret;
 288 }
 289
 290 /**
 291  *      radix_tree_delete    -    delete an item from a radix tree
 292  *      @root:          radix tree root
 293  *      @index:         index key
 294  *
 295  *      Remove the item at @index from the radix tree rooted at @root.
 296  *
 297  *      Returns the address of the deleted item, or NULL if it was not present.
 298  */
 299 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
 300 {
 301   struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
 302   unsigned int height, shift;
 303   void *ret = NULL;
 304
 305   height = root->height;
 306   if (index > radix_tree_maxindex(height))
 307     goto out;
 308
 309   shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 310   pathp->node = NULL;
 311   pathp->slot = &root->rnode;
 312
 313   while (height > 0) {
 314     if (*pathp->slot == NULL)
 315       goto out;
 316
 317     pathp[1].node = *pathp[0].slot;
 318     pathp[1].slot = (struct radix_tree_node **)
 319       (pathp[1].node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
 320     pathp++;
 321     shift -= RADIX_TREE_MAP_SHIFT;
 322     height--;
 323   }
 324
 325   ret = *pathp[0].slot;
 326   if (ret == NULL)
 327     goto out;
 328
 329   *pathp[0].slot = NULL;
 330   while (pathp[0].node && --pathp[0].node->count == 0) {
 331     pathp--;
 332     *pathp[0].slot = NULL;
 333     radix_tree_node_free(pathp[1].node);
 334   }
 335
 336   if (root->rnode == NULL)
 337     root->height = 0;  /* Empty tree, we can reset the height */
 338  out:
 339   return ret;
 340 }
 341
 342
 343 static unsigned long __maxindex(unsigned int height)
 344 {
 345   unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
 346   unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
 347
 348   if (tmp >= RADIX_TREE_INDEX_BITS)
 349     index = ~0UL;
 350   return index;
 351 }
 352
 353 static void radix_tree_init_maxindex(void)
 354 {
 355   unsigned int i;
 356
 357   for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
 358     height_to_maxindex[i] = __maxindex(i);
 359 }
 360
 361 void radix_tree_init(void)
 362 {
 363   radix_tree_init_maxindex();
 364 }