kernel-lib/radix-tree.c

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