lkml.org 
[lkml]   [2005]   [Sep]   [2]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subject[PATCH 2.6.13] lockless pagecache 4/7
    4/7

    --
    SUSE Labs, Novell Inc.

    From: Hans Reiser <reiser@namesys.com>

    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.

    Index: linux-2.6/include/linux/radix-tree.h
    ===================================================================
    --- linux-2.6.orig/include/linux/radix-tree.h
    +++ linux-2.6/include/linux/radix-tree.h
    @@ -46,6 +46,7 @@ do { \

    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(struct radix_tree_root *, unsigned long);
    unsigned int
    radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
    Index: linux-2.6/lib/radix-tree.c
    ===================================================================
    --- linux-2.6.orig/lib/radix-tree.c
    +++ linux-2.6/lib/radix-tree.c
    @@ -276,14 +276,8 @@ int radix_tree_insert(struct radix_tree_
    }
    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;
    @@ -306,7 +300,36 @@ void *radix_tree_lookup(struct radix_tre
    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);
    \
     
     \ /
      Last update: 2005-09-02 08:34    [W:0.022 / U:16.636 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site