Introduce radix_tree_scan_hole(root, index, max_scan) to scan radix tree for the first hole. It will be used in interleaved readahead. The implementation is dumb and obviously correct. It can help debug(and document) the possible smart one in future. Cc: Nick Piggin Signed-off-by: Fengguang Wu --- include/linux/radix-tree.h | 2 ++ lib/radix-tree.c | 34 ++++++++++++++++++++++++++++++++++ 2 files changed, 36 insertions(+) --- linux-2.6.22-git15.orig/include/linux/radix-tree.h +++ linux-2.6.22-git15/include/linux/radix-tree.h @@ -155,6 +155,8 @@ void *radix_tree_delete(struct radix_tre unsigned int radix_tree_gang_lookup(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items); +unsigned long radix_tree_scan_hole(struct radix_tree_root *root, + unsigned long index, unsigned long max_scan); int radix_tree_preload(gfp_t gfp_mask); void radix_tree_init(void); void *radix_tree_tag_set(struct radix_tree_root *root, --- linux-2.6.22-git15.orig/lib/radix-tree.c +++ linux-2.6.22-git15/lib/radix-tree.c @@ -599,6 +599,40 @@ int radix_tree_tag_get(struct radix_tree EXPORT_SYMBOL(radix_tree_tag_get); #endif +static unsigned long +radix_tree_scan_hole_dumb(struct radix_tree_root *root, + unsigned long index, unsigned long max_scan) +{ + unsigned long i; + + for (i = 0; i < max_scan; i++) { + if (!radix_tree_lookup(root, index)) + break; + if (++index == 0) + break; + } + + return index; +} + +/** + * radix_tree_scan_hole - scan for hole + * @root: radix tree root + * @index: index key + * @max_scan: advice on max items to scan (it may scan a little more) + * + * Scan forward from @index for a hole/empty item, stop when + * - hit hole + * - wrap-around to index 0 + * - @max_scan or more items scanned + */ +unsigned long radix_tree_scan_hole(struct radix_tree_root *root, + unsigned long index, unsigned long max_scan) +{ + return radix_tree_scan_hole_dumb(root, index, max_scan); +} +EXPORT_SYMBOL(radix_tree_scan_hole); + static unsigned int __lookup(struct radix_tree_node *slot, void **results, unsigned long index, unsigned int max_items, unsigned long *next_index) -- - 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/