aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorFengguang Wu <wfg@mail.ustc.edu.cn>2007-10-16 04:24:33 -0400
committerLinus Torvalds <torvalds@woody.linux-foundation.org>2007-10-16 12:42:52 -0400
commit6df8ba4f8a4c4abca9ccad10441d0dddbdff301c (patch)
tree6ac5cd48d3400a9d32f8affd31106f7942df9547 /lib
parentf4e6b498d6e06742d72706ef50593a9c4dd72214 (diff)
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 <nickpiggin@yahoo.com.au> Signed-off-by: Fengguang Wu <wfg@mail.ustc.edu.cn> Cc: Rusty Russell <rusty@rustcorp.com.au> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib')
-rw-r--r--lib/radix-tree.c36
1 files changed, 36 insertions, 0 deletions
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 514efb200be6..7af368a4401b 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,
599EXPORT_SYMBOL(radix_tree_tag_get); 599EXPORT_SYMBOL(radix_tree_tag_get);
600#endif 600#endif
601 601
602/**
603 * radix_tree_next_hole - find the next hole (not-present entry)
604 * @root: tree root
605 * @index: index key
606 * @max_scan: maximum range to search
607 *
608 * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest
609 * indexed hole.
610 *
611 * Returns: the index of the hole if found, otherwise returns an index
612 * outside of the set specified (in which case 'return - index >= max_scan'
613 * will be true).
614 *
615 * radix_tree_next_hole may be called under rcu_read_lock. However, like
616 * radix_tree_gang_lookup, this will not atomically search a snapshot of the
617 * tree at a single point in time. For example, if a hole is created at index
618 * 5, then subsequently a hole is created at index 10, radix_tree_next_hole
619 * covering both indexes may return 10 if called under rcu_read_lock.
620 */
621unsigned long radix_tree_next_hole(struct radix_tree_root *root,
622 unsigned long index, unsigned long max_scan)
623{
624 unsigned long i;
625
626 for (i = 0; i < max_scan; i++) {
627 if (!radix_tree_lookup(root, index))
628 break;
629 index++;
630 if (index == 0)
631 break;
632 }
633
634 return index;
635}
636EXPORT_SYMBOL(radix_tree_next_hole);
637
602static unsigned int 638static unsigned int
603__lookup(struct radix_tree_node *slot, void **results, unsigned long index, 639__lookup(struct radix_tree_node *slot, void **results, unsigned long index,
604 unsigned int max_items, unsigned long *next_index) 640 unsigned int max_items, unsigned long *next_index)