1 files changed, 91 insertions, 85 deletions

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 10bed1c8c3c3..b972dd29289d 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -1,6 +1,7 @@
 /*
  * Copyright (C) 2001 Momchil Velikov
  * Portions Copyright (C) 2001 Christoph Hellwig
+ * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com>
  *
  * This program is free software; you can redistribute it and/or
  * modify it under the terms of the GNU General Public License as
@@ -51,7 +52,7 @@ struct radix_tree_node {
 };
 
 struct radix_tree_path {
-        struct radix_tree_node *node, **slot;
+        struct radix_tree_node *node;
         int offset;
 };
 
@@ -227,7 +228,7 @@ out:
 int radix_tree_insert(struct radix_tree_root *root,
                         unsigned long index, void *item)
 {
-        struct radix_tree_node *node = NULL, *tmp, **slot;
+        struct radix_tree_node *node = NULL, *slot;
         unsigned int height, shift;
         int offset;
         int error;
@@ -240,38 +241,42 @@ int radix_tree_insert(struct radix_tree_root *root,
                         return error;
         }
 
-        slot = &root->rnode;
+        slot = root->rnode;
         height = root->height;
         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 
         offset = 0;                     /* uninitialised var warning */
         while (height > 0) {
-                if (*slot == NULL) {
+                if (slot == NULL) {
                         /* Have to add a child node.  */
-                        if (!(tmp = radix_tree_node_alloc(root)))
+                        if (!(slot = radix_tree_node_alloc(root)))
                                 return -ENOMEM;
-                        *slot = tmp;
-                        if (node)
+                        if (node) {
+                                node->slots[offset] = slot;
                                 node->count++;
+                        } else
+                                root->rnode = slot;
                 }
 
                 /* Go a level down */
                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
-                node = *slot;
-                slot = (struct radix_tree_node **)(node->slots + offset);
+                node = slot;
+                slot = node->slots[offset];
                 shift -= RADIX_TREE_MAP_SHIFT;
                 height--;
         }
 
-        if (*slot != NULL)
+        if (slot != NULL)
                 return -EEXIST;
+
         if (node) {
                 node->count++;
+                node->slots[offset] = item;
                 BUG_ON(tag_get(node, 0, offset));
                 BUG_ON(tag_get(node, 1, offset));
-        }
+        } else
+                root->rnode = item;
 
-        *slot = item;
         return 0;
 }
 EXPORT_SYMBOL(radix_tree_insert);
@@ -286,27 +291,25 @@ EXPORT_SYMBOL(radix_tree_insert);
 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
 {
         unsigned int height, shift;
-        struct radix_tree_node **slot;
+        struct radix_tree_node *slot;
 
         height = root->height;
         if (index > radix_tree_maxindex(height))
                 return NULL;
 
         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
-        slot = &root->rnode;
+        slot = root->rnode;
 
         while (height > 0) {
-                if (*slot == NULL)
+                if (slot == NULL)
                         return NULL;
 
-                slot = (struct radix_tree_node **)
-                        ((*slot)->slots +
-                                ((index >> shift) & RADIX_TREE_MAP_MASK));
+                slot = slot->slots[(index >> shift) & RADIX_TREE_MAP_MASK];
                 shift -= RADIX_TREE_MAP_SHIFT;
                 height--;
         }
 
-        return *slot;
+        return slot;
 }
 EXPORT_SYMBOL(radix_tree_lookup);
 
@@ -326,27 +329,27 @@ void *radix_tree_tag_set(struct radix_tree_root *root,
                         unsigned long index, int tag)
 {
         unsigned int height, shift;
-        struct radix_tree_node **slot;
+        struct radix_tree_node *slot;
 
         height = root->height;
         if (index > radix_tree_maxindex(height))
                 return NULL;
 
         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
-        slot = &root->rnode;
+        slot = root->rnode;
 
         while (height > 0) {
                 int offset;
 
                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
-                tag_set(*slot, tag, offset);
-                slot = (struct radix_tree_node **)((*slot)->slots + offset);
-                BUG_ON(*slot == NULL);
+                tag_set(slot, tag, offset);
+                slot = slot->slots[offset];
+                BUG_ON(slot == NULL);
                 shift -= RADIX_TREE_MAP_SHIFT;
                 height--;
         }
 
-        return *slot;
+        return slot;
 }
 EXPORT_SYMBOL(radix_tree_tag_set);
 
@@ -367,6 +370,7 @@ void *radix_tree_tag_clear(struct radix_tree_root *root,
                         unsigned long index, int tag)
 {
         struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
+        struct radix_tree_node *slot;
         unsigned int height, shift;
         void *ret = NULL;
 
@@ -376,38 +380,37 @@ void *radix_tree_tag_clear(struct radix_tree_root *root,
 
         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
         pathp->node = NULL;
-        pathp->slot = &root->rnode;
+        slot = root->rnode;
 
         while (height > 0) {
                 int offset;
 
-                if (*pathp->slot == NULL)
+                if (slot == NULL)
                         goto out;
 
                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
                 pathp[1].offset = offset;
-                pathp[1].node = *pathp[0].slot;
-                pathp[1].slot = (struct radix_tree_node **)
-                                (pathp[1].node->slots + offset);
+                pathp[1].node = slot;
+                slot = slot->slots[offset];
                 pathp++;
                 shift -= RADIX_TREE_MAP_SHIFT;
                 height--;
         }
 
-        ret = *pathp[0].slot;
+        ret = slot;
         if (ret == NULL)
                 goto out;
 
         do {
                 int idx;
 
-                tag_clear(pathp[0].node, tag, pathp[0].offset);
+                tag_clear(pathp->node, tag, pathp->offset);
                 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
-                        if (pathp[0].node->tags[tag][idx])
+                        if (pathp->node->tags[tag][idx])
                                 goto out;
                 }
                 pathp--;
-        } while (pathp[0].node);
+        } while (pathp->node);
 out:
         return ret;
 }
@@ -415,21 +418,22 @@ EXPORT_SYMBOL(radix_tree_tag_clear);
 
 #ifndef __KERNEL__      /* Only the test harness uses this at present */
 /**
- *      radix_tree_tag_get - get a tag on a radix tree node
- *      @root:          radix tree root
- *      @index:         index key
- *      @tag:           tag index
+ * radix_tree_tag_get - get a tag on a radix tree node
+ * @root:               radix tree root
+ * @index:              index key
+ * @tag:                tag index
  *
- *      Return the search tag corresponging to @index in the radix tree.
+ * Return values:
  *
- *      Returns zero if the tag is unset, or if there is no corresponding item
- *      in the tree.
+ *  0: tag not present
+ *  1: tag present, set
+ * -1: tag present, unset
  */
 int radix_tree_tag_get(struct radix_tree_root *root,
                         unsigned long index, int tag)
 {
         unsigned int height, shift;
-        struct radix_tree_node **slot;
+        struct radix_tree_node *slot;
         int saw_unset_tag = 0;
 
         height = root->height;
@@ -437,12 +441,12 @@ int radix_tree_tag_get(struct radix_tree_root *root,
                 return 0;
 
         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
-        slot = &root->rnode;
+        slot = root->rnode;
 
         for ( ; ; ) {
                 int offset;
 
-                if (*slot == NULL)
+                if (slot == NULL)
                         return 0;
 
                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
@@ -451,15 +455,15 @@ int radix_tree_tag_get(struct radix_tree_root *root,
                  * This is just a debug check.  Later, we can bale as soon as
                  * we see an unset tag.
                  */
-                if (!tag_get(*slot, tag, offset))
+                if (!tag_get(slot, tag, offset))
                         saw_unset_tag = 1;
                 if (height == 1) {
-                        int ret = tag_get(*slot, tag, offset);
+                        int ret = tag_get(slot, tag, offset);
 
                         BUG_ON(ret && saw_unset_tag);
-                        return ret;
+                        return ret ? 1 : -1;
                 }
-                slot = (struct radix_tree_node **)((*slot)->slots + offset);
+                slot = slot->slots[offset];
                 shift -= RADIX_TREE_MAP_SHIFT;
                 height--;
         }
@@ -472,17 +476,21 @@ __lookup(struct radix_tree_root *root, void **results, unsigned long index,
         unsigned int max_items, unsigned long *next_index)
 {
         unsigned int nr_found = 0;
-        unsigned int shift;
-        unsigned int height = root->height;
+        unsigned int shift, height;
         struct radix_tree_node *slot;
+        unsigned long i;
+
+        height = root->height;
+        if (height == 0)
+                goto out;
 
         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
         slot = root->rnode;
 
-        while (height > 0) {
-                unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;
+        for ( ; height > 1; height--) {
 
-                for ( ; i < RADIX_TREE_MAP_SIZE; i++) {
+                for (i = (index >> shift) & RADIX_TREE_MAP_MASK ;
+                                i < RADIX_TREE_MAP_SIZE; i++) {
                         if (slot->slots[i] != NULL)
                                 break;
                         index &= ~((1UL << shift) - 1);
@@ -492,22 +500,20 @@ __lookup(struct radix_tree_root *root, void **results, unsigned long index,
                 }
                 if (i == RADIX_TREE_MAP_SIZE)
                         goto out;
-                height--;
-                if (height == 0) {      /* Bottom level: grab some items */
-                        unsigned long j = index & RADIX_TREE_MAP_MASK;
 
-                        for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
-                                index++;
-                                if (slot->slots[j]) {
-                                        results[nr_found++] = slot->slots[j];
-                                        if (nr_found == max_items)
-                                                goto out;
-                                }
-                        }
-                }
                 shift -= RADIX_TREE_MAP_SHIFT;
                 slot = slot->slots[i];
         }
+
+        /* Bottom level: grab some items */
+        for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
+                index++;
+                if (slot->slots[i]) {
+                        results[nr_found++] = slot->slots[i];
+                        if (nr_found == max_items)
+                                goto out;
+                }
+        }
 out:
         *next_index = index;
         return nr_found;
@@ -655,6 +661,7 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
 {
         struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
         struct radix_tree_path *orig_pathp;
+        struct radix_tree_node *slot;
         unsigned int height, shift;
         void *ret = NULL;
         char tags[RADIX_TREE_TAGS];
@@ -666,25 +673,23 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
 
         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
         pathp->node = NULL;
-        pathp->slot = &root->rnode;
+        slot = root->rnode;
 
-        while (height > 0) {
+        for ( ; height > 0; height--) {
                 int offset;
 
-                if (*pathp->slot == NULL)
+                if (slot == NULL)
                         goto out;
 
                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
                 pathp[1].offset = offset;
-                pathp[1].node = *pathp[0].slot;
-                pathp[1].slot = (struct radix_tree_node **)
-                                (pathp[1].node->slots + offset);
+                pathp[1].node = slot;
+                slot = slot->slots[offset];
                 pathp++;
                 shift -= RADIX_TREE_MAP_SHIFT;
-                height--;
         }
 
-        ret = *pathp[0].slot;
+        ret = slot;
         if (ret == NULL)
                 goto out;
 
@@ -704,10 +709,10 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
                         if (tags[tag])
                                 continue;
 
-                        tag_clear(pathp[0].node, tag, pathp[0].offset);
+                        tag_clear(pathp->node, tag, pathp->offset);
 
                         for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
-                                if (pathp[0].node->tags[tag][idx]) {
+                                if (pathp->node->tags[tag][idx]) {
                                         tags[tag] = 1;
                                         nr_cleared_tags--;
                                         break;
@@ -715,18 +720,19 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
                         }
                 }
                 pathp--;
-        } while (pathp[0].node && nr_cleared_tags);
+        } while (pathp->node && nr_cleared_tags);
 
-        pathp = orig_pathp;
-        *pathp[0].slot = NULL;
-        while (pathp[0].node && --pathp[0].node->count == 0) {
-                pathp--;
-                BUG_ON(*pathp[0].slot == NULL);
-                *pathp[0].slot = NULL;
-                radix_tree_node_free(pathp[1].node);
+        /* Now free the nodes we do not need anymore */
+        for (pathp = orig_pathp; pathp->node; pathp--) {
+                pathp->node->slots[pathp->offset] = NULL;
+                if (--pathp->node->count)
+                        goto out;
+
+                /* Node with zero slots in use so free it */
+                radix_tree_node_free(pathp->node);
         }
-        if (root->rnode == NULL)
-                root->height = 0;
+        root->rnode = NULL;
+        root->height = 0;
 out:
         return ret;
 }