Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758029AbZDLHXM (ORCPT ); Sun, 12 Apr 2009 03:23:12 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1755925AbZDLHW3 (ORCPT ); Sun, 12 Apr 2009 03:22:29 -0400 Received: from mga03.intel.com ([143.182.124.21]:54123 "EHLO mga03.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756621AbZDLHW2 (ORCPT ); Sun, 12 Apr 2009 03:22:28 -0400 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="4.40,174,1239001200"; d="scan'208";a="130525061" Message-Id: <20090412072052.457214378@intel.com> References: <20090412071950.166891982@intel.com> User-Agent: quilt/0.46-1 Date: Sun, 12 Apr 2009 15:19:51 +0800 From: Wu Fengguang To: Andrew Morton Cc: Vladislav Bolkhovitin , Wu Fengguang Cc: LKML Subject: [PATCH 1/3] radix-tree: add radix_tree_prev_hole() Content-Disposition: inline; filename=radixtree-prev-hole.patch Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 2609 Lines: 73 The counterpart of radix_tree_next_hole(). To be used by context readahead. Signed-off-by: Wu Fengguang --- 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, -- -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/