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

    \
     
     \ /
      Last update: 2007-07-23 10:19    [W:0.027 / U:1.424 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site