Messages in this thread Patch in this message | | | Date | Mon, 23 Jul 2007 16:04:05 +0800 | From | Fengguang Wu <> | Subject | Re: [PATCH 6/7] radixtree: introduce radix_tree_scan_hole() |
| |
On Mon, Jul 23, 2007 at 05:58:02PM +1000, Nick Piggin wrote: > Fengguang Wu wrote: > >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. > > Reasonable function to want. Is radix_tree_scan_hole the best name? > What about radix_tree_next_hole or _find_next_hole? (Andrew, any > suggestions?)
Thank you!
All comments seems reasonable, so I simply attach the updated patch.
Fengguang --- Subject: radixtree: introduce radix_tree_next_hole() Cc: Nick Piggin <nickpiggin@yahoo.com.au>
Introduce radix_tree_next_hole(root, index, max_scan) to scan radix tree for the first hole. It will be used in interleaved readahead.
Cc: Nick Piggin <nickpiggin@yahoo.com.au> Signed-off-by: Fengguang Wu <wfg@mail.ustc.edu.cn> ---
include/linux/radix-tree.h | 2 + lib/radix-tree.c | 36 +++++++++++++++++++++++++++++++++++ 2 files changed, 38 insertions(+)
--- linux-2.6.22-rc6-mm1.orig/include/linux/radix-tree.h +++ linux-2.6.22-rc6-mm1/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_next_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-rc6-mm1.orig/lib/radix-tree.c +++ linux-2.6.22-rc6-mm1/lib/radix-tree.c @@ -601,6 +601,42 @@ int radix_tree_tag_get(struct radix_tree EXPORT_SYMBOL(radix_tree_tag_get); #endif +/** + * radix_tree_next_hole - find the next hole (not-present entry) + * @root: tree root + * @index: index key + * @max_scan: maximum range to search + * + * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest + * indexed hole. + * + * Returns: the index of the hole if found, otherwise returns an index + * outside of the set specified (in which case 'return - index >= max_scan' + * will be true). + * + * radix_tree_next_hole may be called under rcu_read_lock. However, like + * radix_tree_gang_lookup, this will not atomically search a snapshot of the + * tree at a single point in time. For example, if a hole is created at index + * 5, then subsequently a hole is created at index 10, radix_tree_next_hole + * covering both indexes may return 10 if called under rcu_read_lock. + */ +unsigned long radix_tree_next_hole(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; + index++; + if (index == 0) + break; + } + + return index; +} +EXPORT_SYMBOL(radix_tree_next_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/
| |