diff options
author | Hans Reiser <reiser@namesys.com> | 2005-11-07 00:59:29 -0800 |
---|---|---|
committer | Linus Torvalds <torvalds@g5.osdl.org> | 2005-11-07 07:53:37 -0800 |
commit | a43313668f62a06e14c915b8c8994fc8a1257394 (patch) | |
tree | ae02e1ae145b3f277ead948c32b8b6d06a4e23d9 /lib | |
parent | 7361f4d8ca65d23a18ba009b4484612183332c2f (diff) | |
download | lwn-a43313668f62a06e14c915b8c8994fc8a1257394.tar.gz lwn-a43313668f62a06e14c915b8c8994fc8a1257394.zip |
[PATCH] reiser4: add radix_tree_lookup_slot()
Reiser4 uses radix trees to solve a trouble reiser4_readdir has serving nfs
requests.
Unfortunately, radix tree api lacks an operation suitable for modifying
existing entry. This patch adds radix_tree_lookup_slot which returns pointer
to found item within the tree. That location can be then updated.
Both Nick and Christoph Lameter have patches which need this as well.
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'lib')
-rw-r--r-- | lib/radix-tree.c | 51 |
1 files changed, 38 insertions, 13 deletions
diff --git a/lib/radix-tree.c b/lib/radix-tree.c index d1c057e71b68..88511c3805ad 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -281,35 +281,60 @@ int radix_tree_insert(struct radix_tree_root *root, } EXPORT_SYMBOL(radix_tree_insert); -/** - * radix_tree_lookup - perform lookup operation on a radix tree - * @root: radix tree root - * @index: index key - * - * Lookup the item at the position @index in the radix tree @root. - */ -void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) +static inline void **__lookup_slot(struct radix_tree_root *root, + unsigned long index) { unsigned int height, shift; - struct radix_tree_node *slot; + struct radix_tree_node **slot; height = root->height; if (index > radix_tree_maxindex(height)) return NULL; shift = (height-1) * RADIX_TREE_MAP_SHIFT; - slot = root->rnode; + slot = &root->rnode; while (height > 0) { - if (slot == NULL) + if (*slot == NULL) return NULL; - slot = slot->slots[(index >> shift) & RADIX_TREE_MAP_MASK]; + slot = (struct radix_tree_node **) + ((*slot)->slots + + ((index >> shift) & RADIX_TREE_MAP_MASK)); shift -= RADIX_TREE_MAP_SHIFT; height--; } - return slot; + return (void **)slot; +} + +/** + * radix_tree_lookup_slot - lookup a slot in a radix tree + * @root: radix tree root + * @index: index key + * + * Lookup the slot corresponding to the position @index in the radix tree + * @root. This is useful for update-if-exists operations. + */ +void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) +{ + return __lookup_slot(root, index); +} +EXPORT_SYMBOL(radix_tree_lookup_slot); + +/** + * radix_tree_lookup - perform lookup operation on a radix tree + * @root: radix tree root + * @index: index key + * + * Lookup the item at the position @index in the radix tree @root. + */ +void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) +{ + void **slot; + + slot = __lookup_slot(root, index); + return slot != NULL ? *slot : NULL; } EXPORT_SYMBOL(radix_tree_lookup); |