lkml.org 
[lkml]   [2010]   [Feb]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[PATCH 13/15] radixtree: speed up the search for hole
Replace the hole scan functions with more fast versions:
- radix_tree_next_hole(root, index, max_scan)
- radix_tree_prev_hole(root, index, max_scan)

Cc: Nick Piggin <nickpiggin@yahoo.com.au>
Signed-off-by: Wu Fengguang <fengguang.wu@intel.com>
---
lib/radix-tree.c | 67 +++++++++++++++++++++++++++++++++++++--------
1 file changed, 56 insertions(+), 11 deletions(-)
--- linux.orig/lib/radix-tree.c 2010-02-24 10:44:49.000000000 +0800
+++ linux/lib/radix-tree.c 2010-02-24 10:44:50.000000000 +0800
@@ -647,18 +647,41 @@ EXPORT_SYMBOL(radix_tree_tag_get);
* under rcu_read_lock.
*/
unsigned long radix_tree_next_hole(struct radix_tree_root *root,
- unsigned long index, unsigned long max_scan)
+ unsigned long index, unsigned long max_scan)
{
- unsigned long i;
+ struct radix_tree_node *node;
+ unsigned long origin = index;
+ int i;
+
+ node = rcu_dereference(root->rnode);
+ if (node == NULL)
+ return index;
+
+ if (!radix_tree_is_indirect_ptr(node))
+ return index ? index : 1;

- for (i = 0; i < max_scan; i++) {
- if (!radix_tree_lookup(root, index))
+ while (index - origin < max_scan) {
+ node = radix_tree_lookup_leaf_node(root, index);
+ if (!node)
break;
- index++;
- if (index == 0)
+
+ if (node->count == RADIX_TREE_MAP_SIZE) {
+ index = (index | RADIX_TREE_MAP_MASK) + 1;
+ goto check_overflow;
+ }
+
+ for (i = index & RADIX_TREE_MAP_MASK;
+ i < RADIX_TREE_MAP_SIZE;
+ i++, index++)
+ if (rcu_dereference(node->slots[i]) == NULL)
+ goto out;
+
+check_overflow:
+ if (unlikely(index == 0))
break;
}

+out:
return index;
}
EXPORT_SYMBOL(radix_tree_next_hole);
@@ -686,16 +709,38 @@ EXPORT_SYMBOL(radix_tree_next_hole);
unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
unsigned long index, unsigned long max_scan)
{
- unsigned long i;
+ struct radix_tree_node *node;
+ unsigned long origin = index;
+ int i;
+
+ node = rcu_dereference(root->rnode);
+ if (node == NULL)
+ return index;
+
+ if (!radix_tree_is_indirect_ptr(node))
+ return index ? index : ULONG_MAX;

- for (i = 0; i < max_scan; i++) {
- if (!radix_tree_lookup(root, index))
+ while (origin - index < max_scan) {
+ node = radix_tree_lookup_leaf_node(root, index);
+ if (!node)
break;
- index--;
- if (index == LONG_MAX)
+
+ if (node->count == RADIX_TREE_MAP_SIZE) {
+ index = (index - RADIX_TREE_MAP_SIZE) |
+ RADIX_TREE_MAP_MASK;
+ goto check_underflow;
+ }
+
+ for (i = index & RADIX_TREE_MAP_MASK; i >= 0; i--, index--)
+ if (rcu_dereference(node->slots[i]) == NULL)
+ goto out;
+
+check_underflow:
+ if (unlikely(index == ULONG_MAX))
break;
}

+out:
return index;
}
EXPORT_SYMBOL(radix_tree_prev_hole);



\
 
 \ /
  Last update: 2010-02-24 04:15    [from the cache]
©2003-2014 Jasper Spaans. hosted at Digital Ocean