Messages in this thread | | | Date | Mon, 23 Jul 2007 17:58:02 +1000 | From | Nick Piggin <> | Subject | Re: [PATCH 6/7] radixtree: introduce radix_tree_scan_hole() |
| |
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?)
> > 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 | 34 ++++++++++++++++++++++++++++++++++ > 2 files changed, 36 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_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-rc6-mm1.orig/lib/radix-tree.c > +++ linux-2.6.22-rc6-mm1/lib/radix-tree.c > @@ -601,6 +601,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;
Minor nit: I think it is preferred to have index++; on its own line.
> + } > + > + 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 > + */
Some suggestions on the comment:
/** * radix_tree_next_hole - find the next hole (not-present entry) * @root: radix 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_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);
Don't do this scan_hole_dumb thing. Just implement it in place.
-- SUSE Labs, Novell Inc. - 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/
| |