lkml.org 
[lkml]   [2007]   [Jul]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [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/

    \
     
     \ /
      Last update: 2007-07-23 10:03    [W:6.598 / U:0.052 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site