libfrog/radix-tree.c

   1 /*
   2  * Copyright (C) 2001 Momchil Velikov
   3  * Portions Copyright (C) 2001 Christoph Hellwig
   4  * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com>
   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 <stdlib.h>
  21 #include <string.h>
  22 #include <errno.h>
  23 #include <stdint.h>
  24 #include "platform_defs.h"
  25 #include "radix-tree.h"
  26
  27 #ifndef ARRAY_SIZE
  28 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
  29 #endif
  30
  31 #define RADIX_TREE_MAP_SHIFT    6
  32 #define RADIX_TREE_MAP_SIZE     (1UL << RADIX_TREE_MAP_SHIFT)
  33 #define RADIX_TREE_MAP_MASK     (RADIX_TREE_MAP_SIZE-1)
  34
  35 #ifdef RADIX_TREE_TAGS
  36 #define RADIX_TREE_TAG_LONGS    \
  37         ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
  38 #endif
  39
  40 struct radix_tree_node {
  41         unsigned int    count;
  42         void            *slots[RADIX_TREE_MAP_SIZE];
  43 #ifdef RADIX_TREE_TAGS
  44         unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
  45 #endif
  46 };
  47
  48 struct radix_tree_path {
  49         struct radix_tree_node *node;
  50         int offset;
  51 };
  52
  53 #define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
  54 #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
  55
  56 static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH];
  57
  58 /*
  59  * Radix tree node cache.
  60  */
  61
  62 #define radix_tree_node_alloc(r)        ((struct radix_tree_node *) \
  63                 calloc(1, sizeof(struct radix_tree_node)))
  64 #define radix_tree_node_free(n)         free(n)
  65
  66 #ifdef RADIX_TREE_TAGS
  67
  68 static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
  69                 int offset)
  70 {
  71         *((uint32_t *)node->tags[tag] + (offset >> 5)) |= (1 << (offset & 31));
  72 }
  73
  74 static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
  75                 int offset)
  76 {
  77         uint32_t        *p = (uint32_t*)node->tags[tag] + (offset >> 5);
  78         uint32_t        m = 1 << (offset & 31);
  79         *p &= ~m;
  80 }
  81
  82 static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
  83                 int offset)
  84 {
  85         return 1 & (((const uint32_t *)node->tags[tag])[offset >> 5] >> (offset & 31));
  86 }
  87
  88 /*
  89  * Returns 1 if any slot in the node has this tag set.
  90  * Otherwise returns 0.
  91  */
  92 static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
  93 {
  94         int idx;
  95         for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
  96                 if (node->tags[tag][idx])
  97                         return 1;
  98         }
  99         return 0;
 100 }
 101
 102 #endif
 103
 104 /*
 105  *      Return the maximum key which can be store into a
 106  *      radix tree with height HEIGHT.
 107  */
 108 static inline unsigned long radix_tree_maxindex(unsigned int height)
 109 {
 110         return height_to_maxindex[height];
 111 }
 112
 113 /*
 114  *      Extend a radix tree so it can store key @index.
 115  */
 116 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
 117 {
 118         struct radix_tree_node *node;
 119         unsigned int height;
 120 #ifdef RADIX_TREE_TAGS
 121         char tags[RADIX_TREE_MAX_TAGS];
 122         int tag;
 123 #endif
 124
 125         /* Figure out what the height should be.  */
 126         height = root->height + 1;
 127         while (index > radix_tree_maxindex(height))
 128                 height++;
 129
 130         if (root->rnode == NULL) {
 131                 root->height = height;
 132                 goto out;
 133         }
 134
 135 #ifdef RADIX_TREE_TAGS
 136         /*
 137          * Prepare the tag status of the top-level node for propagation
 138          * into the newly-pushed top-level node(s)
 139          */
 140         for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
 141                 tags[tag] = 0;
 142                 if (any_tag_set(root->rnode, tag))
 143                         tags[tag] = 1;
 144         }
 145 #endif
 146         do {
 147                 if (!(node = radix_tree_node_alloc(root)))
 148                         return -ENOMEM;
 149
 150                 /* Increase the height.  */
 151                 node->slots[0] = root->rnode;
 152
 153 #ifdef RADIX_TREE_TAGS
 154                 /* Propagate the aggregated tag info into the new root */
 155                 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
 156                         if (tags[tag])
 157                                 tag_set(node, tag, 0);
 158                 }
 159 #endif
 160                 node->count = 1;
 161                 root->rnode = node;
 162                 root->height++;
 163         } while (height > root->height);
 164 out:
 165         return 0;
 166 }
 167
 168 /**
 169  *      radix_tree_insert    -    insert into a radix tree
 170  *      @root:          radix tree root
 171  *      @index:         index key
 172  *      @item:          item to insert
 173  *
 174  *      Insert an item into the radix tree at position @index.
 175  */
 176 int radix_tree_insert(struct radix_tree_root *root,
 177                         unsigned long index, void *item)
 178 {
 179         struct radix_tree_node *node = NULL, *slot;
 180         unsigned int height, shift;
 181         int offset;
 182         int error;
 183
 184         /* Make sure the tree is high enough.  */
 185         if ((!index && !root->rnode) ||
 186                         index > radix_tree_maxindex(root->height)) {
 187                 error = radix_tree_extend(root, index);
 188                 if (error)
 189                         return error;
 190         }
 191
 192         slot = root->rnode;
 193         height = root->height;
 194         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 195
 196         offset = 0;                     /* uninitialised var warning */
 197         do {
 198                 if (slot == NULL) {
 199                         /* Have to add a child node.  */
 200                         if (!(slot = radix_tree_node_alloc(root)))
 201                                 return -ENOMEM;
 202                         if (node) {
 203                                 node->slots[offset] = slot;
 204                                 node->count++;
 205                         } else
 206                                 root->rnode = slot;
 207                 }
 208
 209                 /* Go a level down */
 210                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
 211                 node = slot;
 212                 slot = node->slots[offset];
 213                 shift -= RADIX_TREE_MAP_SHIFT;
 214                 height--;
 215         } while (height > 0);
 216
 217         if (slot != NULL)
 218                 return -EEXIST;
 219
 220         ASSERT(node);
 221         node->count++;
 222         node->slots[offset] = item;
 223 #ifdef RADIX_TREE_TAGS
 224         ASSERT(!tag_get(node, 0, offset));
 225         ASSERT(!tag_get(node, 1, offset));
 226 #endif
 227         return 0;
 228 }
 229
 230 static inline void **__lookup_slot(struct radix_tree_root *root,
 231                                    unsigned long index)
 232 {
 233         unsigned int height, shift;
 234         struct radix_tree_node **slot;
 235
 236         height = root->height;
 237         if (index > radix_tree_maxindex(height))
 238                 return NULL;
 239
 240         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 241         slot = &root->rnode;
 242
 243         while (height > 0) {
 244                 if (*slot == NULL)
 245                         return NULL;
 246
 247                 slot = (struct radix_tree_node **)
 248                         ((*slot)->slots +
 249                                 ((index >> shift) & RADIX_TREE_MAP_MASK));
 250                 shift -= RADIX_TREE_MAP_SHIFT;
 251                 height--;
 252         }
 253
 254         return (void **)slot;
 255 }
 256
 257 /**
 258  *      radix_tree_lookup_slot    -    lookup a slot in a radix tree
 259  *      @root:          radix tree root
 260  *      @index:         index key
 261  *
 262  *      Lookup the slot corresponding to the position @index in the radix tree
 263  *      @root. This is useful for update-if-exists operations.
 264  */
 265 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
 266 {
 267         return __lookup_slot(root, index);
 268 }
 269
 270 /**
 271  *      radix_tree_lookup    -    perform lookup operation on a radix tree
 272  *      @root:          radix tree root
 273  *      @index:         index key
 274  *
 275  *      Lookup the item at the position @index in the radix tree @root.
 276  */
 277 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
 278 {
 279         void **slot;
 280
 281         slot = __lookup_slot(root, index);
 282         return slot != NULL ? *slot : NULL;
 283 }
 284
 285 /**
 286  *      raid_tree_first_key - find the first index key in the radix tree
 287  *      @root:          radix tree root
 288  *      @index:         where the first index will be placed
 289  *
 290  *      Returns the first entry and index key in the radix tree @root.
 291  */
 292 void *radix_tree_lookup_first(struct radix_tree_root *root, unsigned long *index)
 293 {
 294         unsigned int height, shift;
 295         struct radix_tree_node *slot;
 296         unsigned long i;
 297
 298         height = root->height;
 299         *index = 0;
 300         if (height == 0)
 301                 return NULL;
 302
 303         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 304         slot = root->rnode;
 305
 306         for (; height > 1; height--) {
 307                 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
 308                         if (slot->slots[i] != NULL)
 309                                 break;
 310                 }
 311                 ASSERT(i < RADIX_TREE_MAP_SIZE);
 312
 313                 *index |= (i << shift);
 314                 shift -= RADIX_TREE_MAP_SHIFT;
 315                 slot = slot->slots[i];
 316         }
 317         for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
 318                 if (slot->slots[i] != NULL) {
 319                         *index |= i;
 320                         return slot->slots[i];
 321                 }
 322         }
 323         return NULL;
 324 }
 325
 326 #ifdef RADIX_TREE_TAGS
 327
 328 /**
 329  *      radix_tree_tag_set - set a tag on a radix tree node
 330  *      @root:          radix tree root
 331  *      @index:         index key
 332  *      @tag:           tag index
 333  *
 334  *      Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
 335  *      corresponding to @index in the radix tree.  From
 336  *      the root all the way down to the leaf node.
 337  *
 338  *      Returns the address of the tagged item.   Setting a tag on a not-present
 339  *      item is a bug.
 340  */
 341 void *radix_tree_tag_set(struct radix_tree_root *root,
 342                         unsigned long index, unsigned int tag)
 343 {
 344         unsigned int height, shift;
 345         struct radix_tree_node *slot;
 346
 347         height = root->height;
 348         if (index > radix_tree_maxindex(height))
 349                 return NULL;
 350
 351         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 352         slot = root->rnode;
 353
 354         while (height > 0) {
 355                 int offset;
 356
 357                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
 358                 if (!tag_get(slot, tag, offset))
 359                         tag_set(slot, tag, offset);
 360                 slot = slot->slots[offset];
 361                 ASSERT(slot != NULL);
 362                 shift -= RADIX_TREE_MAP_SHIFT;
 363                 height--;
 364         }
 365
 366         return slot;
 367 }
 368
 369 /**
 370  *      radix_tree_tag_clear - clear a tag on a radix tree node
 371  *      @root:          radix tree root
 372  *      @index:         index key
 373  *      @tag:           tag index
 374  *
 375  *      Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
 376  *      corresponding to @index in the radix tree.  If
 377  *      this causes the leaf node to have no tags set then clear the tag in the
 378  *      next-to-leaf node, etc.
 379  *
 380  *      Returns the address of the tagged item on success, else NULL.  ie:
 381  *      has the same return value and semantics as radix_tree_lookup().
 382  */
 383 void *radix_tree_tag_clear(struct radix_tree_root *root,
 384                         unsigned long index, unsigned int tag)
 385 {
 386         struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
 387         struct radix_tree_node *slot;
 388         unsigned int height, shift;
 389         void *ret = NULL;
 390
 391         height = root->height;
 392         if (index > radix_tree_maxindex(height))
 393                 goto out;
 394
 395         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 396         pathp->node = NULL;
 397         slot = root->rnode;
 398
 399         while (height > 0) {
 400                 int offset;
 401
 402                 if (slot == NULL)
 403                         goto out;
 404
 405                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
 406                 pathp[1].offset = offset;
 407                 pathp[1].node = slot;
 408                 slot = slot->slots[offset];
 409                 pathp++;
 410                 shift -= RADIX_TREE_MAP_SHIFT;
 411                 height--;
 412         }
 413
 414         ret = slot;
 415         if (ret == NULL)
 416                 goto out;
 417
 418         do {
 419                 if (!tag_get(pathp->node, tag, pathp->offset))
 420                         goto out;
 421                 tag_clear(pathp->node, tag, pathp->offset);
 422                 if (any_tag_set(pathp->node, tag))
 423                         goto out;
 424                 pathp--;
 425         } while (pathp->node);
 426 out:
 427         return ret;
 428 }
 429
 430 #endif
 431
 432 static unsigned int
 433 __lookup(struct radix_tree_root *root, void **results, unsigned long index,
 434         unsigned int max_items, unsigned long *next_index)
 435 {
 436         unsigned int nr_found = 0;
 437         unsigned int shift, height;
 438         struct radix_tree_node *slot;
 439         unsigned long i;
 440
 441         height = root->height;
 442         if (height == 0)
 443                 goto out;
 444
 445         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 446         slot = root->rnode;
 447
 448         for ( ; height > 1; height--) {
 449
 450                 for (i = (index >> shift) & RADIX_TREE_MAP_MASK ;
 451                                 i < RADIX_TREE_MAP_SIZE; i++) {
 452                         if (slot->slots[i] != NULL)
 453                                 break;
 454                         index &= ~((1UL << shift) - 1);
 455                         index += 1UL << shift;
 456                         if (index == 0)
 457                                 goto out;       /* 32-bit wraparound */
 458                 }
 459                 if (i == RADIX_TREE_MAP_SIZE)
 460                         goto out;
 461
 462                 shift -= RADIX_TREE_MAP_SHIFT;
 463                 slot = slot->slots[i];
 464         }
 465
 466         /* Bottom level: grab some items */
 467         for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
 468                 index++;
 469                 if (slot->slots[i]) {
 470                         results[nr_found++] = slot->slots[i];
 471                         if (nr_found == max_items)
 472                                 goto out;
 473                 }
 474         }
 475 out:
 476         *next_index = index;
 477         return nr_found;
 478 }
 479
 480 /**
 481  *      radix_tree_gang_lookup - perform multiple lookup on a radix tree
 482  *      @root:          radix tree root
 483  *      @results:       where the results of the lookup are placed
 484  *      @first_index:   start the lookup from this key
 485  *      @max_items:     place up to this many items at *results
 486  *
 487  *      Performs an index-ascending scan of the tree for present items.  Places
 488  *      them at *@results and returns the number of items which were placed at
 489  *      *@results.
 490  *
 491  *      The implementation is naive.
 492  */
 493 unsigned int
 494 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
 495                         unsigned long first_index, unsigned int max_items)
 496 {
 497         const unsigned long max_index = radix_tree_maxindex(root->height);
 498         unsigned long cur_index = first_index;
 499         unsigned int ret = 0;
 500
 501         while (ret < max_items) {
 502                 unsigned int nr_found;
 503                 unsigned long next_index;       /* Index of next search */
 504
 505                 if (cur_index > max_index)
 506                         break;
 507                 nr_found = __lookup(root, results + ret, cur_index,
 508                                         max_items - ret, &next_index);
 509                 ret += nr_found;
 510                 if (next_index == 0)
 511                         break;
 512                 cur_index = next_index;
 513         }
 514         return ret;
 515 }
 516
 517 /**
 518  *      radix_tree_gang_lookup_ex - perform multiple lookup on a radix tree
 519  *      @root:          radix tree root
 520  *      @results:       where the results of the lookup are placed
 521  *      @first_index:   start the lookup from this key
 522  *      @last_index:    don't lookup past this key
 523  *      @max_items:     place up to this many items at *results
 524  *
 525  *      Performs an index-ascending scan of the tree for present items starting
 526  *      @first_index until @last_index up to as many as @max_items.  Places
 527  *      them at *@results and returns the number of items which were placed
 528  *      at *@results.
 529  *
 530  *      The implementation is naive.
 531  */
 532 unsigned int
 533 radix_tree_gang_lookup_ex(struct radix_tree_root *root, void **results,
 534                         unsigned long first_index, unsigned long last_index,
 535                         unsigned int max_items)
 536 {
 537         const unsigned long max_index = radix_tree_maxindex(root->height);
 538         unsigned long cur_index = first_index;
 539         unsigned int ret = 0;
 540
 541         while (ret < max_items && cur_index < last_index) {
 542                 unsigned int nr_found;
 543                 unsigned long next_index;       /* Index of next search */
 544
 545                 if (cur_index > max_index)
 546                         break;
 547                 nr_found = __lookup(root, results + ret, cur_index,
 548                                         max_items - ret, &next_index);
 549                 ret += nr_found;
 550                 if (next_index == 0)
 551                         break;
 552                 cur_index = next_index;
 553         }
 554         return ret;
 555 }
 556
 557 #ifdef RADIX_TREE_TAGS
 558
 559 static unsigned int
 560 __lookup_tag(struct radix_tree_root *root, void **results, unsigned long index,
 561         unsigned int max_items, unsigned long *next_index, unsigned int tag)
 562 {
 563         unsigned int nr_found = 0;
 564         unsigned int shift;
 565         unsigned int height = root->height;
 566         struct radix_tree_node *slot;
 567
 568         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 569         slot = root->rnode;
 570
 571         while (height > 0) {
 572                 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;
 573
 574                 for ( ; i < RADIX_TREE_MAP_SIZE; i++) {
 575                         if (tag_get(slot, tag, i)) {
 576                                 ASSERT(slot->slots[i] != NULL);
 577                                 break;
 578                         }
 579                         index &= ~((1UL << shift) - 1);
 580                         index += 1UL << shift;
 581                         if (index == 0)
 582                                 goto out;       /* 32-bit wraparound */
 583                 }
 584                 if (i == RADIX_TREE_MAP_SIZE)
 585                         goto out;
 586                 height--;
 587                 if (height == 0) {      /* Bottom level: grab some items */
 588                         unsigned long j = index & RADIX_TREE_MAP_MASK;
 589
 590                         for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
 591                                 index++;
 592                                 if (tag_get(slot, tag, j)) {
 593                                         ASSERT(slot->slots[j] != NULL);
 594                                         results[nr_found++] = slot->slots[j];
 595                                         if (nr_found == max_items)
 596                                                 goto out;
 597                                 }
 598                         }
 599                 }
 600                 shift -= RADIX_TREE_MAP_SHIFT;
 601                 slot = slot->slots[i];
 602         }
 603 out:
 604         *next_index = index;
 605         return nr_found;
 606 }
 607
 608 /**
 609  *      radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
 610  *                                   based on a tag
 611  *      @root:          radix tree root
 612  *      @results:       where the results of the lookup are placed
 613  *      @first_index:   start the lookup from this key
 614  *      @max_items:     place up to this many items at *results
 615  *      @tag:           the tag index (< RADIX_TREE_MAX_TAGS)
 616  *
 617  *      Performs an index-ascending scan of the tree for present items which
 618  *      have the tag indexed by @tag set.  Places the items at *@results and
 619  *      returns the number of items which were placed at *@results.
 620  */
 621 unsigned int
 622 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
 623                 unsigned long first_index, unsigned int max_items,
 624                 unsigned int tag)
 625 {
 626         const unsigned long max_index = radix_tree_maxindex(root->height);
 627         unsigned long cur_index = first_index;
 628         unsigned int ret = 0;
 629
 630         while (ret < max_items) {
 631                 unsigned int nr_found;
 632                 unsigned long next_index;       /* Index of next search */
 633
 634                 if (cur_index > max_index)
 635                         break;
 636                 nr_found = __lookup_tag(root, results + ret, cur_index,
 637                                         max_items - ret, &next_index, tag);
 638                 ret += nr_found;
 639                 if (next_index == 0)
 640                         break;
 641                 cur_index = next_index;
 642         }
 643         return ret;
 644 }
 645
 646 #endif
 647
 648 /**
 649  *      radix_tree_shrink    -    shrink height of a radix tree to minimal
 650  *      @root           radix tree root
 651  */
 652 static inline void radix_tree_shrink(struct radix_tree_root *root)
 653 {
 654         /* try to shrink tree height */
 655         while (root->height > 1 &&
 656                         root->rnode->count == 1 &&
 657                         root->rnode->slots[0]) {
 658                 struct radix_tree_node *to_free = root->rnode;
 659
 660                 root->rnode = to_free->slots[0];
 661                 root->height--;
 662                 /* must only free zeroed nodes into the slab */
 663 #ifdef RADIX_TREE_TAGS
 664                 tag_clear(to_free, 0, 0);
 665                 tag_clear(to_free, 1, 0);
 666 #endif
 667                 to_free->slots[0] = NULL;
 668                 to_free->count = 0;
 669                 radix_tree_node_free(to_free);
 670         }
 671 }
 672
 673 /**
 674  *      radix_tree_delete    -    delete an item from a radix tree
 675  *      @root:          radix tree root
 676  *      @index:         index key
 677  *
 678  *      Remove the item at @index from the radix tree rooted at @root.
 679  *
 680  *      Returns the address of the deleted item, or NULL if it was not present.
 681  */
 682 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
 683 {
 684         struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
 685         struct radix_tree_path *orig_pathp;
 686         struct radix_tree_node *slot;
 687         unsigned int height, shift;
 688         void *ret = NULL;
 689 #ifdef RADIX_TREE_TAGS
 690         char tags[RADIX_TREE_MAX_TAGS];
 691         int nr_cleared_tags;
 692         int tag;
 693 #endif
 694         int offset;
 695
 696         height = root->height;
 697         if (index > radix_tree_maxindex(height))
 698                 goto out;
 699
 700         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 701         pathp->node = NULL;
 702         slot = root->rnode;
 703
 704         for ( ; height > 0; height--) {
 705                 if (slot == NULL)
 706                         goto out;
 707
 708                 pathp++;
 709                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
 710                 pathp->offset = offset;
 711                 pathp->node = slot;
 712                 slot = slot->slots[offset];
 713                 shift -= RADIX_TREE_MAP_SHIFT;
 714         }
 715
 716         ret = slot;
 717         if (ret == NULL)
 718                 goto out;
 719
 720         orig_pathp = pathp;
 721
 722 #ifdef RADIX_TREE_TAGS
 723         /*
 724          * Clear all tags associated with the just-deleted item
 725          */
 726         nr_cleared_tags = 0;
 727         for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
 728                 tags[tag] = 1;
 729                 if (tag_get(pathp->node, tag, pathp->offset)) {
 730                         tag_clear(pathp->node, tag, pathp->offset);
 731                         if (!any_tag_set(pathp->node, tag)) {
 732                                 tags[tag] = 0;
 733                                 nr_cleared_tags++;
 734                         }
 735                 }
 736         }
 737
 738         for (pathp--; nr_cleared_tags && pathp->node; pathp--) {
 739                 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
 740                         if (tags[tag])
 741                                 continue;
 742
 743                         tag_clear(pathp->node, tag, pathp->offset);
 744                         if (any_tag_set(pathp->node, tag)) {
 745                                 tags[tag] = 1;
 746                                 nr_cleared_tags--;
 747                         }
 748                 }
 749         }
 750 #endif
 751         /* Now free the nodes we do not need anymore */
 752         for (pathp = orig_pathp; pathp->node; pathp--) {
 753                 pathp->node->slots[pathp->offset] = NULL;
 754                 pathp->node->count--;
 755
 756                 if (pathp->node->count) {
 757                         if (pathp->node == root->rnode)
 758                                 radix_tree_shrink(root);
 759                         goto out;
 760                 }
 761
 762                 /* Node with zero slots in use so free it */
 763                 radix_tree_node_free(pathp->node);
 764         }
 765         root->rnode = NULL;
 766         root->height = 0;
 767 out:
 768         return ret;
 769 }
 770
 771 #ifdef RADIX_TREE_TAGS
 772 /**
 773  *      radix_tree_tagged - test whether any items in the tree are tagged
 774  *      @root:          radix tree root
 775  *      @tag:           tag to test
 776  */
 777 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
 778 {
 779         struct radix_tree_node *rnode;
 780         rnode = root->rnode;
 781         if (!rnode)
 782                 return 0;
 783         return any_tag_set(rnode, tag);
 784 }
 785 #endif
 786
 787 static unsigned long __maxindex(unsigned int height)
 788 {
 789         unsigned int width = height * RADIX_TREE_MAP_SHIFT;
 790         int shift = RADIX_TREE_INDEX_BITS - width;
 791
 792         if (shift < 0)
 793                 return ~0UL;
 794         if (shift >= BITS_PER_LONG)
 795                 return 0UL;
 796         return ~0UL >> shift;
 797 }
 798
 799 static void radix_tree_init_maxindex(void)
 800 {
 801         unsigned int i;
 802
 803         for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
 804                 height_to_maxindex[i] = __maxindex(i);
 805 }
 806
 807 void radix_tree_init(void)
 808 {
 809         radix_tree_init_maxindex();
 810 }