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