This will be used by the pagecache context based read-ahead/read-around heuristic to quickly check one pagecache range: - if there is any hole - if there is any pages Cc: Nick Piggin Signed-off-by: Wu Fengguang --- include/linux/radix-tree.h | 2 ++ lib/radix-tree.c | 27 ++++++++++++++++++++++----- 2 files changed, 24 insertions(+), 5 deletions(-) --- linux.orig/lib/radix-tree.c 2010-02-24 10:44:23.000000000 +0800 +++ linux/lib/radix-tree.c 2010-02-24 10:44:49.000000000 +0800 @@ -359,7 +359,7 @@ EXPORT_SYMBOL(radix_tree_insert); * is_slot == 0 : search for the node. */ static void *radix_tree_lookup_element(struct radix_tree_root *root, - unsigned long index, int is_slot) + unsigned long index, int is_slot, int level) { unsigned int height, shift; struct radix_tree_node *node, **slot; @@ -369,7 +369,7 @@ static void *radix_tree_lookup_element(s return NULL; if (!radix_tree_is_indirect_ptr(node)) { - if (index > 0) + if (index > 0 || level > 0) return NULL; return is_slot ? (void *)&root->rnode : node; } @@ -390,7 +390,7 @@ static void *radix_tree_lookup_element(s shift -= RADIX_TREE_MAP_SHIFT; height--; - } while (height > 0); + } while (height > level); return is_slot ? (void *)slot:node; } @@ -410,7 +410,7 @@ static void *radix_tree_lookup_element(s */ void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) { - return (void **)radix_tree_lookup_element(root, index, 1); + return (void **)radix_tree_lookup_element(root, index, 1, 0); } EXPORT_SYMBOL(radix_tree_lookup_slot); @@ -428,11 +428,28 @@ EXPORT_SYMBOL(radix_tree_lookup_slot); */ void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) { - return radix_tree_lookup_element(root, index, 0); + return radix_tree_lookup_element(root, index, 0, 0); } EXPORT_SYMBOL(radix_tree_lookup); /** + * radix_tree_lookup_leaf_node - lookup leaf node on a radix tree + * @root: radix tree root + * @index: index key + * + * Lookup the leaf node that covers @index in the radix tree @root. + * Return NULL if the node does not exist, or is the special root node. + * + * The typical usage is to check the value of node->count, which shall be + * performed inside rcu_read_lock to prevent the node from being freed. + */ +struct radix_tree_node * +radix_tree_lookup_leaf_node(struct radix_tree_root *root, unsigned long index) +{ + return radix_tree_lookup_element(root, index, 0, 1); +} + +/** * radix_tree_tag_set - set a tag on a radix tree node * @root: radix tree root * @index: index key --- linux.orig/include/linux/radix-tree.h 2010-02-24 10:44:23.000000000 +0800 +++ linux/include/linux/radix-tree.h 2010-02-24 10:44:49.000000000 +0800 @@ -158,6 +158,8 @@ static inline void radix_tree_replace_sl int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); void *radix_tree_lookup(struct radix_tree_root *, unsigned long); void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long); +struct radix_tree_node * +radix_tree_lookup_leaf_node(struct radix_tree_root *root, unsigned long index); void *radix_tree_delete(struct radix_tree_root *, unsigned long); unsigned int radix_tree_gang_lookup(struct radix_tree_root *root, void **results, -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/