On Thu, 18 Jan 2007 15:33:25 -0500 Rob Landley wrote:
> Signed-off-by: Rob Landley <[email protected]>
>
> 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).
> --- /dev/null 2006-05-30 21:33:22.000000000 -0400
> +++ linux-2.6.19.2/Documentation/rbtree.txt 2007-01-18 11:57:50.000000000 -0500
> @@ -0,0 +1,186 @@
> +Red-black Trees (rbtree) in Linux
> +January 18, 2007
> +Rob Landley <[email protected]>
> +=============================
> +
> +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 realtime bounded
real-time
> +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:
> +
...
> +
> +This document covers use of the Linux rbtree implementation. For more
> +information on the nature and implementation of Red Black Trees, see:
> +
...
> +
> +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 a rb_root structure, which is initialized to be
> +empty via:
an rb_root
> +
> + 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.
its
> +
> +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;
> + }
Please use kernel CodingStyle in the kernel Documentation/ directory.
That would mean /*...*/ comments instead of //
and expanding the if/else lines to have their statements on separate
lines....
> +Removing or replacing existing data in an rbtree
> +------------------------------------------------
> +
...
> +
> +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
> +fo the tree, which will return a pointer to the node structure contained in
of
> +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).
Thanks.
---
~Randy
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
