Lines Matching refs:rbtree

1 Red-black Trees (rbtree) in Linux
26     The high-resolution timer code uses an rbtree to organize outstanding
32 This document covers use of the Linux rbtree implementation.  For more
44 Linux's rbtree implementation lives in the file "lib/rbtree.c".  To use it,
45 "#include <linux/rbtree.h>".
47 The Linux rbtree implementation is optimized for speed, and thus has one
53 which call the provided rbtree functions.  Locking is also left up to the
54 user of the rbtree code.
56 Creating a new rbtree
59 Data nodes in an rbtree tree are structures containing a struct rb_node member:
70 At the root of each rbtree is an rb_root structure, which is initialized to be
75 Searching for a value in an rbtree
103 Inserting data into an rbtree
140 Removing or replacing existing data in an rbtree
162 have the same key as the old node, the rbtree will probably become corrupted.
164 Iterating through the elements stored in an rbtree (in sort order)
167 Four functions are provided for iterating through an rbtree's contents in
196 Augmented rbtree is an rbtree with "some" additional data stored in
199 be used to augment some new functionality to rbtree. Augmented rbtree
200 is an optional feature built on top of basic rbtree infrastructure.
201 An rbtree user who wants this feature will have to call the augmentation
205 C files implementing augmented rbtree manipulation must include
206 <linux/rbtree_augmented.h> instead of <linux/rbtree.h>. Note that
207 linux/rbtree_augmented.h exposes some rbtree implementations details
216 If rb_augment_inserted() rebalances the rbtree, it will callback into
239 copy callbacks, which results in a large function, so each augmented rbtree
250 Classical rbtree has a single key and it cannot be directly used to store
254 However, rbtree can be augmented to store such interval ranges in a structured