Messages in this thread | | | Date | Fri, 10 Apr 2009 21:29:03 +0800 | From | Wu Fengguang <> | Subject | Re: [PATCH 1/3] radix-tree: add radix_tree_next_hole() |
| |
Heh silly mistake: the title should say radix_tree_prev_hole() and the changelog should be 'counterpart of radix_tree_next_hole()'.
Will resubmit this one...
On Fri, Apr 10, 2009 at 09:12:48PM +0800, Wu, Fengguang wrote: > The counterpart of radix_tree_prev_hole(). To be used by context readahead. > > Signed-off-by: Wu Fengguang <fengguang.wu@intel.com> > --- > --- > include/linux/radix-tree.h | 2 + > lib/radix-tree.c | 37 +++++++++++++++++++++++++++++++++++ > 2 files changed, 39 insertions(+) > > --- mm.orig/lib/radix-tree.c > +++ mm/lib/radix-tree.c > @@ -666,6 +666,43 @@ unsigned long radix_tree_next_hole(struc > } > EXPORT_SYMBOL(radix_tree_next_hole); > > +/** > + * radix_tree_prev_hole - find the prev hole (not-present entry) > + * @root: tree root > + * @index: index key > + * @max_scan: maximum range to search > + * > + * Search backwards in the range [max(index-max_scan+1, 0), index] > + * for the first hole. > + * > + * Returns: the index of the hole if found, otherwise returns an index > + * outside of the set specified (in which case 'index - return >= max_scan' > + * will be true). In rare cases of wrap-around, LONG_MAX will be returned. > + * > + * 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 10, then subsequently a hole is created at index 5, > + * radix_tree_prev_hole covering both indexes may return 5 if called under > + * rcu_read_lock. > + */ > +unsigned long radix_tree_prev_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 == LONG_MAX) > + break; > + } > + > + return index; > +} > +EXPORT_SYMBOL(radix_tree_prev_hole); > + > static unsigned int > __lookup(struct radix_tree_node *slot, void ***results, unsigned long index, > unsigned int max_items, unsigned long *next_index) > --- mm.orig/include/linux/radix-tree.h > +++ mm/include/linux/radix-tree.h > @@ -167,6 +167,8 @@ radix_tree_gang_lookup_slot(struct radix > 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); > +unsigned long radix_tree_prev_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, > > --
| |