Lines Matching refs:rbtree

2 Red-black Trees (rbtree) in Linux
29     The high-resolution timer code uses an rbtree to organize outstanding
35 This document covers use of the Linux rbtree implementation.  For more
47 Linux's rbtree implementation lives in the file "lib/rbtree.c".  To use it,
48 "#include <linux/rbtree.h>".
50 The Linux rbtree implementation is optimized for speed, and thus has one
56 which call the provided rbtree functions.  Locking is also left up to the
57 user of the rbtree code.
59 Creating a new rbtree
62 Data nodes in an rbtree tree are structures containing a struct rb_node member::
73 At the root of each rbtree is an rb_root structure, which is initialized to be
78 Searching for a value in an rbtree
106 Inserting data into an rbtree
143 Removing or replacing existing data in an rbtree
165 have the same key as the old node, the rbtree will probably become corrupted.
167 Iterating through the elements stored in an rbtree (in sort order)
170 Four functions are provided for iterating through an rbtree's contents in
211 Cached rbtree is simply a regular rb_root with an extra pointer to cache the
232 Augmented rbtree is an rbtree with "some" additional data stored in
235 be used to augment some new functionality to rbtree. Augmented rbtree
236 is an optional feature built on top of basic rbtree infrastructure.
237 An rbtree user who wants this feature will have to call the augmentation
241 C files implementing augmented rbtree manipulation must include
242 <linux/rbtree_augmented.h> instead of <linux/rbtree.h>. Note that
243 linux/rbtree_augmented.h exposes some rbtree implementations details
252 If rb_augment_inserted() rebalances the rbtree, it will callback into
275 copy callbacks, which results in a large function, so each augmented rbtree
287 Classical rbtree has a single key and it cannot be directly used to store
291 However, rbtree can be augmented to store such interval ranges in a structured