[PATCH 17/30] radix-tree: Rewrite __radix_tree_lookup

[Matthew Wilcox]

Use the new multi-order support functions to rewrite __radix_tree_lookup()

Signed-off-by: Matthew Wilcox <wi...@linux.intel.com>
Reviewed-by: Ross Zwisler <ross.zwis...@linux.intel.com>
---
 lib/radix-tree.c | 45 +++++++++++++++++----------------------------
 1 file changed, 17 insertions(+), 28 deletions(-)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 3dc52433a9cc..2ca2b416b476 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -634,44 +634,33 @@ void *__radix_tree_lookup(struct radix_tree_root *root, 
unsigned long index,
                          struct radix_tree_node **nodep, void ***slotp)
 {
        struct radix_tree_node *node, *parent;
-       unsigned int height, shift;
+       unsigned long maxindex;
+       unsigned int shift;
        void **slot;
 
-       node = rcu_dereference_raw(root->rnode);
-       if (node == NULL)
+ restart:
+       parent = NULL;
+       slot = (void **)&root->rnode;
+       shift = radix_tree_load_root(root, &node, &maxindex);
+       if (index > maxindex)
                return NULL;
 
-       if (!radix_tree_is_indirect_ptr(node)) {
-               if (index > 0)
-                       return NULL;
-
-               if (nodep)
-                       *nodep = NULL;
-               if (slotp)
-                       *slotp = (void **)&root->rnode;
-               return node;
-       }
-       node = indirect_to_ptr(node);
-
-       height = node->path & RADIX_TREE_HEIGHT_MASK;
-       if (index > radix_tree_maxindex(height))
-               return NULL;
-
-       shift = (height-1) * RADIX_TREE_MAP_SHIFT;
+       for (;;) {
+               unsigned offset;
 
-       do {
-               parent = node;
-               slot = node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK);
-               node = rcu_dereference_raw(*slot);
-               if (node == NULL)
+               if (!node)
                        return NULL;
+               if (node == RADIX_TREE_RETRY)
+                       goto restart;
                if (!radix_tree_is_indirect_ptr(node))
                        break;
-               node = indirect_to_ptr(node);
 
+               parent = indirect_to_ptr(node);
                shift -= RADIX_TREE_MAP_SHIFT;
-               height--;
-       } while (height > 0);
+               offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+               offset = radix_tree_descend(parent, &node, offset);
+               slot = parent->slots + offset;
+       }
 
        if (nodep)
                *nodep = parent;
-- 
2.8.0.rc3