The patch titled
radixtree: introduce radix_tree_next_hole()
has been removed from the -mm tree. Its filename was
radixtree-introduce-radix_tree_scan_hole.patch
This patch was dropped because it isn't in the present -mm lineup
------------------------------------------------------
Subject: radixtree: introduce radix_tree_next_hole()
From: Fengguang Wu <wfg@xxxxxxxxxxxxxxxx>
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@xxxxxxxxxxxx>
Signed-off-by: Fengguang Wu <wfg@xxxxxxxxxxxxxxxx>
Cc: Rusty Russell <rusty@xxxxxxxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
include/linux/radix-tree.h | 2 +
lib/radix-tree.c | 36 +++++++++++++++++++++++++++++++++++
2 files changed, 38 insertions(+)
diff -puN include/linux/radix-tree.h~radixtree-introduce-radix_tree_scan_hole include/linux/radix-tree.h
--- a/include/linux/radix-tree.h~radixtree-introduce-radix_tree_scan_hole
+++ a/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,
diff -puN lib/radix-tree.c~radixtree-introduce-radix_tree_scan_hole lib/radix-tree.c
--- a/lib/radix-tree.c~radixtree-introduce-radix_tree_scan_hole
+++ a/lib/radix-tree.c
@@ -599,6 +599,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)
_
Patches currently in -mm which might be from wfg@xxxxxxxxxxxxxxxx are
origin.patch
readahead-compacting-file_ra_state.patch
readahead-mmap-read-around-simplification.patch
readahead-combine-file_ra_stateprev_index-prev_offset-into-prev_pos.patch
readahead-combine-file_ra_stateprev_index-prev_offset-into-prev_pos-fix.patch
readahead-combine-file_ra_stateprev_index-prev_offset-into-prev_pos-fix-2.patch
radixtree-introduce-radix_tree_next_hole.patch
readahead-basic-support-of-interleaved-reads.patch
readahead-remove-the-local-copy-of-ra-in-do_generic_mapping_read.patch
readahead-remove-several-readahead-macros.patch
readahead-remove-the-limit-max_sectors_kb-imposed-on-max_readahead_kb.patch
filemap-trivial-code-cleanups.patch
filemap-convert-some-unsigned-long-to-pgoff_t.patch
make-swappiness-safer-to-use.patch
convert-ill-defined-log2-to-ilog2.patch
seqfile-merge-duplite-code-to-seq_open_private.patch
-
To unsubscribe from this list: send the line "unsubscribe mm-commits" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
