From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756987Ab3HFWrk (ORCPT ); Tue, 6 Aug 2013 18:47:40 -0400 Received: from zene.cmpxchg.org ([85.214.230.12]:52307 "EHLO zene.cmpxchg.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756814Ab3HFWo7 (ORCPT ); Tue, 6 Aug 2013 18:44:59 -0400 From: Johannes Weiner To: linux-mm@kvack.org Cc: Andi Kleen , Andrea Arcangeli , Andrew Morton , Greg Thelen , Christoph Hellwig , Hugh Dickins , Jan Kara , KOSAKI Motohiro , Mel Gorman , Minchan Kim , Peter Zijlstra , Rik van Riel , Michel Lespinasse , Seth Jennings , Roman Gushchin , Ozgun Erdogan , Metin Doslu , linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [patch 1/9] lib: radix-tree: radix_tree_delete_item() Date: Tue, 6 Aug 2013 18:44:02 -0400 Message-Id: <1375829050-12654-2-git-send-email-hannes@cmpxchg.org> X-Mailer: git-send-email 1.8.3.2 In-Reply-To: <1375829050-12654-1-git-send-email-hannes@cmpxchg.org> References: <1375829050-12654-1-git-send-email-hannes@cmpxchg.org> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Provide a function that does not just delete an entry at a given index, but also allows passing in an expected item. Delete only if that item is still located at the specified index. This is handy when lockless tree traversals want to delete entries as well because they don't have to do an second, locked lookup to verify the slot has not changed under them before deleting the entry. Signed-off-by: Johannes Weiner --- include/linux/radix-tree.h | 1 + lib/radix-tree.c | 30 ++++++++++++++++++++++++++---- 2 files changed, 27 insertions(+), 4 deletions(-) diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 4039407..1bf0a9c 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -219,6 +219,7 @@ static inline void radix_tree_replace_slot(void **pslot, void *item) int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); void *radix_tree_lookup(struct radix_tree_root *, unsigned long); void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long); +void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *); void *radix_tree_delete(struct radix_tree_root *, unsigned long); unsigned int radix_tree_gang_lookup(struct radix_tree_root *root, void **results, diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 7811ed3..60b202b 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -1335,15 +1335,18 @@ static inline void radix_tree_shrink(struct radix_tree_root *root) } /** - * radix_tree_delete - delete an item from a radix tree + * radix_tree_delete_item - delete an item from a radix tree * @root: radix tree root * @index: index key + * @item: expected item * - * Remove the item at @index from the radix tree rooted at @root. + * Remove @item at @index from the radix tree rooted at @root. * - * Returns the address of the deleted item, or NULL if it was not present. + * Returns the address of the deleted item, or NULL if it was not present + * or the entry at the given @index was not @item. */ -void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) +void *radix_tree_delete_item(struct radix_tree_root *root, + unsigned long index, void *item) { struct radix_tree_node *node = NULL; struct radix_tree_node *slot = NULL; @@ -1378,6 +1381,11 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) if (slot == NULL) goto out; + if (item && slot != item) { + slot = NULL; + goto out; + } + /* * Clear all tags associated with the item to be deleted. * This way of doing it would be inefficient, but seldom is any set. @@ -1422,6 +1430,20 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) out: return slot; } + +/** + * radix_tree_delete - delete an item from a radix tree + * @root: radix tree root + * @index: index key + * + * Remove the item at @index from the radix tree rooted at @root. + * + * Returns the address of the deleted item, or NULL if it was not present. + */ +void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) +{ + return radix_tree_delete_item(root, index, NULL); +} EXPORT_SYMBOL(radix_tree_delete); /** -- 1.8.3.2 From mboxrd@z Thu Jan 1 00:00:00 1970 From: Johannes Weiner Subject: [patch 1/9] lib: radix-tree: radix_tree_delete_item() Date: Tue, 6 Aug 2013 18:44:02 -0400 Message-ID: <1375829050-12654-2-git-send-email-hannes@cmpxchg.org> References: <1375829050-12654-1-git-send-email-hannes@cmpxchg.org> Cc: Andi Kleen , Andrea Arcangeli , Andrew Morton , Greg Thelen , Christoph Hellwig , Hugh Dickins , Jan Kara , KOSAKI Motohiro , Mel Gorman , Minchan Kim , Peter Zijlstra , Rik van Riel , Michel Lespinasse , Seth Jennings , Roman Gushchin , Ozgun Erdogan , Metin Doslu , linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org To: linux-mm@kvack.org Return-path: In-Reply-To: <1375829050-12654-1-git-send-email-hannes@cmpxchg.org> Sender: owner-linux-mm@kvack.org List-Id: linux-fsdevel.vger.kernel.org Provide a function that does not just delete an entry at a given index, but also allows passing in an expected item. Delete only if that item is still located at the specified index. This is handy when lockless tree traversals want to delete entries as well because they don't have to do an second, locked lookup to verify the slot has not changed under them before deleting the entry. Signed-off-by: Johannes Weiner --- include/linux/radix-tree.h | 1 + lib/radix-tree.c | 30 ++++++++++++++++++++++++++---- 2 files changed, 27 insertions(+), 4 deletions(-) diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 4039407..1bf0a9c 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -219,6 +219,7 @@ static inline void radix_tree_replace_slot(void **pslot, void *item) int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); void *radix_tree_lookup(struct radix_tree_root *, unsigned long); void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long); +void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *); void *radix_tree_delete(struct radix_tree_root *, unsigned long); unsigned int radix_tree_gang_lookup(struct radix_tree_root *root, void **results, diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 7811ed3..60b202b 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -1335,15 +1335,18 @@ static inline void radix_tree_shrink(struct radix_tree_root *root) } /** - * radix_tree_delete - delete an item from a radix tree + * radix_tree_delete_item - delete an item from a radix tree * @root: radix tree root * @index: index key + * @item: expected item * - * Remove the item at @index from the radix tree rooted at @root. + * Remove @item at @index from the radix tree rooted at @root. * - * Returns the address of the deleted item, or NULL if it was not present. + * Returns the address of the deleted item, or NULL if it was not present + * or the entry at the given @index was not @item. */ -void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) +void *radix_tree_delete_item(struct radix_tree_root *root, + unsigned long index, void *item) { struct radix_tree_node *node = NULL; struct radix_tree_node *slot = NULL; @@ -1378,6 +1381,11 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) if (slot == NULL) goto out; + if (item && slot != item) { + slot = NULL; + goto out; + } + /* * Clear all tags associated with the item to be deleted. * This way of doing it would be inefficient, but seldom is any set. @@ -1422,6 +1430,20 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) out: return slot; } + +/** + * radix_tree_delete - delete an item from a radix tree + * @root: radix tree root + * @index: index key + * + * Remove the item at @index from the radix tree rooted at @root. + * + * Returns the address of the deleted item, or NULL if it was not present. + */ +void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) +{ + return radix_tree_delete_item(root, index, NULL); +} EXPORT_SYMBOL(radix_tree_delete); /** -- 1.8.3.2 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org