Gitweb:     
http://git.kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=6df8ba4f8a4c4abca9ccad10441d0dddbdff301c
Commit:     6df8ba4f8a4c4abca9ccad10441d0dddbdff301c
Parent:     f4e6b498d6e06742d72706ef50593a9c4dd72214
Author:     Fengguang Wu <[EMAIL PROTECTED]>
AuthorDate: Tue Oct 16 01:24:33 2007 -0700
Committer:  Linus Torvalds <[EMAIL PROTECTED]>
CommitDate: Tue Oct 16 09:42:52 2007 -0700

    radixtree: introduce radix_tree_next_hole()
    
    Introduce radix_tree_next_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 <[EMAIL PROTECTED]>
    Signed-off-by: Fengguang Wu <[EMAIL PROTECTED]>
    Cc: Rusty Russell <[EMAIL PROTECTED]>
    Signed-off-by: Andrew Morton <[EMAIL PROTECTED]>
    Signed-off-by: Linus Torvalds <[EMAIL PROTECTED]>
---
 include/linux/radix-tree.h |    2 ++
 lib/radix-tree.c           |   36 ++++++++++++++++++++++++++++++++++++
 2 files changed, 38 insertions(+), 0 deletions(-)

diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index f9e77d2..430e4a8 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -155,6 +155,8 @@ void *radix_tree_delete(struct radix_tree_root *, unsigned 
long);
 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,
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 514efb2..7af368a 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -599,6 +599,42 @@ int radix_tree_tag_get(struct radix_tree_root *root,
 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 git-commits-head" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to