Introduce a pair of functions to scan radix tree for hole/empty item.
include/linux/radix-tree.h | 4 +
lib/radix-tree.c | 104 +++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 108 insertions(+)
Signed-off-by: Wu Fengguang <[email protected]>
---
--- linux-2.6.17-rc4-mm3.orig/include/linux/radix-tree.h
+++ linux-2.6.17-rc4-mm3/include/linux/radix-tree.h
@@ -74,6 +74,10 @@ unsigned int radix_tree_cache_count(stru
void *radix_tree_cache_lookup_parent(struct radix_tree_root *root,
struct radix_tree_cache *cache,
unsigned long index, unsigned int level);
+unsigned long radix_tree_scan_hole_backward(struct radix_tree_root *root,
+ unsigned long index, unsigned long max_scan);
+unsigned long radix_tree_scan_hole(struct radix_tree_root *root,
+ unsigned long index, unsigned long max_scan);
unsigned int
radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
unsigned long first_index, unsigned int max_items);
--- linux-2.6.17-rc4-mm3.orig/lib/radix-tree.c
+++ linux-2.6.17-rc4-mm3/lib/radix-tree.c
@@ -427,6 +427,110 @@ unsigned int radix_tree_cache_count(stru
EXPORT_SYMBOL(radix_tree_cache_count);
/**
+ * radix_tree_scan_hole_backward - scan backward for hole
+ * @root: radix tree root
+ * @index: index key
+ * @max_scan: advice on max items to scan (it may scan a little more)
+ *
+ * Scan backward from @index for a hole/empty item, stop when
+ * - hit hole
+ * - @max_scan or more items scanned
+ * - hit index 0
+ *
+ * Return the correponding index.
+ */
+unsigned long radix_tree_scan_hole_backward(struct radix_tree_root *root,
+ unsigned long index, unsigned long max_scan)
+{
+ struct radix_tree_cache cache;
+ struct radix_tree_node *node;
+ unsigned long origin;
+ int i;
+
+ origin = index;
+ radix_tree_cache_init(&cache);
+
+ while (origin - index < max_scan) {
+ node = radix_tree_cache_lookup_parent(root, &cache, index, 1);
+ if (!node)
+ break;
+
+ if (node->count == RADIX_TREE_MAP_SIZE) {
+ index = (index - RADIX_TREE_MAP_SIZE) |
+ RADIX_TREE_MAP_MASK;
+ goto check_underflow;
+ }
+
+ for (i = index & RADIX_TREE_MAP_MASK; i >= 0; i--, index--) {
+ if (!node->slots[i])
+ goto out;
+ }
+
+check_underflow:
+ if (unlikely(index == ULONG_MAX)) {
+ index = 0;
+ break;
+ }
+ }
+
+out:
+ return index;
+}
+EXPORT_SYMBOL(radix_tree_scan_hole_backward);
+
+/**
+ * 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
+ * - hit EOF
+ * - hit index ULONG_MAX
+ * - @max_scan or more items scanned
+ *
+ * Return the correponding index.
+ */
+unsigned long radix_tree_scan_hole(struct radix_tree_root *root,
+ unsigned long index, unsigned long max_scan)
+{
+ struct radix_tree_cache cache;
+ struct radix_tree_node *node;
+ unsigned long origin;
+ int i;
+
+ origin = index;
+ radix_tree_cache_init(&cache);
+
+ while (index - origin < max_scan) {
+ node = radix_tree_cache_lookup_parent(root, &cache, index, 1);
+ if (!node)
+ break;
+
+ if (node->count == RADIX_TREE_MAP_SIZE) {
+ index = (index | RADIX_TREE_MAP_MASK) + 1;
+ goto check_overflow;
+ }
+
+ for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE;
+ i++, index++) {
+ if (!node->slots[i])
+ goto out;
+ }
+
+check_overflow:
+ if (unlikely(!index)) {
+ index = ULONG_MAX;
+ break;
+ }
+ }
+out:
+ return index;
+}
+EXPORT_SYMBOL(radix_tree_scan_hole);
+
+/**
* radix_tree_tag_set - set a tag on a radix tree node
* @root: radix tree root
* @index: index key
--
Wu Fengguang <[email protected]> wrote:
>
> Introduce a pair of functions to scan radix tree for hole/empty item.
>
There's a userspace radix-tree test harness at
http://www.zip.com.au/~akpm/linux/patches/stuff/rtth.tar.gz.
If/when these new features are merged up, it would be good to have new
testcases added to that suite, please.
In the meanwhile you may care to develop those tests anwyway, see if you
can trip up the new features.
On Thu, May 25, 2006 at 09:19:46AM -0700, Andrew Morton wrote:
> Wu Fengguang <[email protected]> wrote:
> >
> > Introduce a pair of functions to scan radix tree for hole/empty item.
> >
>
> There's a userspace radix-tree test harness at
> http://www.zip.com.au/~akpm/linux/patches/stuff/rtth.tar.gz.
>
> If/when these new features are merged up, it would be good to have new
> testcases added to that suite, please.
>
> In the meanwhile you may care to develop those tests anwyway, see if you
> can trip up the new features.
Handy tool.
I'll update it with the newly introduced functions, and write
corresponding test cases.
Thanks,
Wu
On Thu, May 25, 2006 at 09:19:46AM -0700, Andrew Morton wrote:
> Wu Fengguang <[email protected]> wrote:
> >
> > Introduce a pair of functions to scan radix tree for hole/empty item.
> >
>
> There's a userspace radix-tree test harness at
> http://www.zip.com.au/~akpm/linux/patches/stuff/rtth.tar.gz.
>
> If/when these new features are merged up, it would be good to have new
> testcases added to that suite, please.
>
> In the meanwhile you may care to develop those tests anwyway, see if you
> can trip up the new features.
The new radix-tree.c/.h breaks compiling terribly.
Are there any particular reason not to implement it as a module?
Wu Fengguang <[email protected]> wrote:
>
> On Thu, May 25, 2006 at 09:19:46AM -0700, Andrew Morton wrote:
> > Wu Fengguang <[email protected]> wrote:
> > >
> > > Introduce a pair of functions to scan radix tree for hole/empty item.
> > >
> >
> > There's a userspace radix-tree test harness at
> > http://www.zip.com.au/~akpm/linux/patches/stuff/rtth.tar.gz.
> >
> > If/when these new features are merged up, it would be good to have new
> > testcases added to that suite, please.
> >
> > In the meanwhile you may care to develop those tests anwyway, see if you
> > can trip up the new features.
>
> The new radix-tree.c/.h breaks compiling terribly.
Sprinkling more stub header files in there usually fixes that.
> Are there any particular reason not to implement it as a module?
Well. It's a heck of a lot more convenient to throw testcases at a
userspace app, and to debug it and to performance analyse it.