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