lkml.org 
[lkml]   [2007]   [Jan]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    SubjectRe: [PATCH] Documentation/rbtree.txt (updated)
    Date
    On Friday 19 January 2007 5:41 pm, Randy Dunlap wrote:
    > On Thu, 18 Jan 2007 15:33:25 -0500 Rob Landley wrote:
    >
    > > Signed-off-by: Rob Landley <rob@landley.net>
    > >
    > > Documentation for lib/rbtree.c.
    > >
    > > --
    > >
    > > I'm not an expert on this but I was asked to write up some documentation
    > > for rbtree in the Linux kernel, and as long as it's there...
    > >
    > > I'm sure if I screwed something up somebody will point it out to me, loudly.
    > > :)
    >
    > Hi,
    >
    > Looks pretty good to me. I have a few minor nits (below).

    Thanks. Here it is with the nits de-nitted.

    Signed-off-by: Rob Landley <rob@landley.net>

    --- /dev/null 2006-05-30 21:33:22.000000000 -0400
    +++ linux-2.6.19.2/Documentation/rbtree.txt 2007-01-22 12:25:53.000000000 -0500
    @@ -0,0 +1,192 @@
    +Red-black Trees (rbtree) in Linux
    +January 18, 2007
    +Rob Landley <rob@landley.net>
    +=============================
    +
    +What are red-black trees, and what are they for?
    +------------------------------------------------
    +
    +Red-black trees are a type of self-balancing binary search tree, used for
    +storing sortable key/value data pairs. This differs from radix trees (which
    +are used to efficiently store sparse arrays and thus use long integer indexes
    +to insert/access/delete nodes) and hash tables (which are not kept sorted to
    +be easily traversed in order, and must be tuned for a specific size and
    +hash function where rbtrees scale gracefully storing arbitrary keys).
    +
    +Red-black trees are similar to AVL trees, but provide faster real-time bounded
    +worst case performance for insertion and deletion (at most two rotations and
    +three rotations, respectively, to balance the tree), with slightly slower
    +(but still O(log n)) lookup time.
    +
    +To quote Linux Weekly News:
    +
    + There are a number of red-black trees in use in the kernel.
    + The anticipatory, deadline, and CFQ I/O schedulers all employ
    + rbtrees to track requests; the packet CD/DVD driver does the same.
    + The high-resolution timer code uses an rbtree to organize outstanding
    + timer requests. The ext3 filesystem tracks directory entries in a
    + red-black tree. Virtual memory areas (VMAs) are tracked with red-black
    + trees, as are epoll file descriptors, cryptographic keys, and network
    + packets in the "hierarchical token bucket" scheduler.
    +
    +This document covers use of the Linux rbtree implementation. For more
    +information on the nature and implementation of Red Black Trees, see:
    +
    + Linux Weekly News article on red-black trees
    + http://lwn.net/Articles/184495/
    +
    + Wikipedia entry on red-black trees
    + http://en.wikipedia.org/wiki/Red-black_tree
    +
    +Linux implementation of red-black trees
    +---------------------------------------
    +
    +Linux's rbtree implementation lives in the file "lib/rbtree.c". To use it,
    +"#include <linux/rbtree.h>".
    +
    +The Linux rbtree implementation is optimized for speed, and thus has one
    +less layer of indirection (and better cache locality) than more traditional
    +tree implementations. Instead of using pointers to separate rb_node and data
    +structures, each instance of struct rb_node is embedded in the data structure
    +it organizes. And instead of using a comparison callback function pointer,
    +users are expected to write their own tree search and insert functions
    +which call the provided rbtree functions. Locking is also left up to the
    +user of the rbtree code.
    +
    +Creating a new rbtree
    +---------------------
    +
    +Data nodes in an rbtree tree are structures containing a struct rb_node member:
    +
    + struct mytype {
    + struct rb_node node;
    + char *keystring;
    + };
    +
    +When dealing with a pointer to the embedded struct rb_node, the containing data
    +structure may be accessed with the standard container_of() macro. In addition,
    +individual members may be accessed directly via rb_entry(node, type, member).
    +
    +At the root of each rbtree is an rb_root structure, which is initialized to be
    +empty via:
    +
    + struct rb_root mytree = RB_ROOT;
    +
    +Searching for a value in an rbtree
    +----------------------------------
    +
    +Writing a search function for your tree is fairly straightforward: start at the
    +root, compare each value, and follow the left or right branch as necessary.
    +
    +Example:
    +
    + struct mytype *my_search(struct rb_root *root, char *string)
    + {
    + struct rb_node *node = root->rb_node;
    +
    + while (node) {
    + struct mytype *data = container_of(node, struct mytype, node);
    + int result;
    +
    + result = strcmp(string, data->keystring);
    +
    + if (result < 0)
    + node = node->rb_left;
    + else if (result > 0)
    + node = node->rb_right;
    + else
    + return data;
    + }
    + return NULL;
    + }
    +
    +Inserting data into an rbtree
    +-----------------------------
    +
    +Inserting data in the tree involves first searching for the place to insert the
    +new node, then inserting the node and rebalancing ("recoloring") the tree.
    +
    +The search for insertion differs from the previous search by finding the
    +location of the pointer on which to graft the new node. The new node also
    +needs a link to its parent node for rebalancing purposes.
    +
    +Example:
    +
    + int my_insert(struct rb_root *root, struct mytype *data)
    + {
    + struct rb_node **new = &(root->rb_node), *parent = NULL;
    +
    + /* Figure out where to put new node */
    + while (*new) {
    + struct mytype *this = container_of(*new, struct mytype, node);
    + int result = strcmp(data->keystring, this->keystring);
    +
    + parent = *new;
    + if (result < 0)
    + new = &((*new)->rb_left);
    + else if (result > 0)
    + new = &((*new)->rb_right);
    + else
    + return FALSE;
    + }
    +
    + /* Add new node and rebalance tree. */
    + rb_link_node(data->node, parent, new);
    + rb_insert_color(data->node, root);
    +
    + return TRUE;
    + }
    +
    +Removing or replacing existing data in an rbtree
    +------------------------------------------------
    +
    +To remove an existing node from a tree, call:
    +
    + void rb_erase(struct rb_node *victim, struct rb_root *tree);
    +
    +Example:
    +
    + struct mytype *data = mysearch(mytree, "walrus");
    +
    + if (data) {
    + rb_erase(data->node, mytree);
    + myfree(data);
    + }
    +
    +To replace an existing node in a tree with a new one with the same key, call:
    +
    + void rb_replace_node(struct rb_node *old, struct rb_node *new,
    + struct rb_root *tree);
    +
    +Replacing a node this way does not re-sort the tree: If the new node doesn't
    +have the same key as the old node, the rbtree will probably become corrupted.
    +
    +Iterating through the elements stored in an rbtree (in sort order)
    +------------------------------------------------------------------
    +
    +Four functions are provided for iterating through an rbtree's contents in
    +sorted order. These work on arbitrary trees, and should not need to be
    +modified or wrapped (except for locking purposes):
    +
    + struct rb_node *rb_first(struct rb_root *tree);
    + struct rb_node *rb_last(struct rb_root *tree);
    + struct rb_node *rb_next(struct rb_node *node);
    + struct rb_node *rb_prev(struct rb_node *node);
    +
    +To start iterating, call rb_first() or rb_last() with a pointer to the root
    +of the tree, which will return a pointer to the node structure contained in
    +the first or last element in the tree. To continue, fetch the next or previous
    +node by calling rb_next() or rb_prev() on the current node. This will return
    +NULL when there are no more nodes left.
    +
    +The iterator functions return a pointer to the embedded struct rb_node, from
    +which the containing data structure may be accessed with the container_of()
    +macro, and individual members may be accessed directly via
    +rb_entry(node, type, member).
    +
    +Example:
    +
    + struct rb_node *node;
    + for (node = rb_first(&mytree); node; node = rb_next(node))
    + printk("key=%s\n", rb_entry(node, int, keystring));
    +

    --
    "Perfection is reached, not when there is no longer anything to add, but
    when there is no longer anything to take away." - Antoine de Saint-Exupery
    -
    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/

    \
     
     \ /
      Last update: 2007-01-22 18:59    [W:0.031 / U:0.768 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site