]>
Commit | Line | Data |
---|---|---|
1 | ================================= | |
2 | Red-black Trees (rbtree) in Linux | |
3 | ================================= | |
4 | ||
5 | ||
6 | :Date: January 18, 2007 | |
7 | :Author: Rob Landley <rob@landley.net> | |
8 | ||
9 | What are red-black trees, and what are they for? | |
10 | ------------------------------------------------ | |
11 | ||
12 | Red-black trees are a type of self-balancing binary search tree, used for | |
13 | storing sortable key/value data pairs. This differs from radix trees (which | |
14 | are used to efficiently store sparse arrays and thus use long integer indexes | |
15 | to insert/access/delete nodes) and hash tables (which are not kept sorted to | |
16 | be easily traversed in order, and must be tuned for a specific size and | |
17 | hash function where rbtrees scale gracefully storing arbitrary keys). | |
18 | ||
19 | Red-black trees are similar to AVL trees, but provide faster real-time bounded | |
20 | worst case performance for insertion and deletion (at most two rotations and | |
21 | three rotations, respectively, to balance the tree), with slightly slower | |
22 | (but still O(log n)) lookup time. | |
23 | ||
24 | To quote Linux Weekly News: | |
25 | ||
26 | There are a number of red-black trees in use in the kernel. | |
27 | The deadline and CFQ I/O schedulers employ rbtrees to | |
28 | track requests; the packet CD/DVD driver does the same. | |
29 | The high-resolution timer code uses an rbtree to organize outstanding | |
30 | timer requests. The ext3 filesystem tracks directory entries in a | |
31 | red-black tree. Virtual memory areas (VMAs) are tracked with red-black | |
32 | trees, as are epoll file descriptors, cryptographic keys, and network | |
33 | packets in the "hierarchical token bucket" scheduler. | |
34 | ||
35 | This document covers use of the Linux rbtree implementation. For more | |
36 | information on the nature and implementation of Red Black Trees, see: | |
37 | ||
38 | Linux Weekly News article on red-black trees | |
39 | http://lwn.net/Articles/184495/ | |
40 | ||
41 | Wikipedia entry on red-black trees | |
42 | http://en.wikipedia.org/wiki/Red-black_tree | |
43 | ||
44 | Linux implementation of red-black trees | |
45 | --------------------------------------- | |
46 | ||
47 | Linux's rbtree implementation lives in the file "lib/rbtree.c". To use it, | |
48 | "#include <linux/rbtree.h>". | |
49 | ||
50 | The Linux rbtree implementation is optimized for speed, and thus has one | |
51 | less layer of indirection (and better cache locality) than more traditional | |
52 | tree implementations. Instead of using pointers to separate rb_node and data | |
53 | structures, each instance of struct rb_node is embedded in the data structure | |
54 | it organizes. And instead of using a comparison callback function pointer, | |
55 | users are expected to write their own tree search and insert functions | |
56 | which call the provided rbtree functions. Locking is also left up to the | |
57 | user of the rbtree code. | |
58 | ||
59 | Creating a new rbtree | |
60 | --------------------- | |
61 | ||
62 | Data nodes in an rbtree tree are structures containing a struct rb_node member:: | |
63 | ||
64 | struct mytype { | |
65 | struct rb_node node; | |
66 | char *keystring; | |
67 | }; | |
68 | ||
69 | When dealing with a pointer to the embedded struct rb_node, the containing data | |
70 | structure may be accessed with the standard container_of() macro. In addition, | |
71 | individual members may be accessed directly via rb_entry(node, type, member). | |
72 | ||
73 | At the root of each rbtree is an rb_root structure, which is initialized to be | |
74 | empty via: | |
75 | ||
76 | struct rb_root mytree = RB_ROOT; | |
77 | ||
78 | Searching for a value in an rbtree | |
79 | ---------------------------------- | |
80 | ||
81 | Writing a search function for your tree is fairly straightforward: start at the | |
82 | root, compare each value, and follow the left or right branch as necessary. | |
83 | ||
84 | Example:: | |
85 | ||
86 | struct mytype *my_search(struct rb_root *root, char *string) | |
87 | { | |
88 | struct rb_node *node = root->rb_node; | |
89 | ||
90 | while (node) { | |
91 | struct mytype *data = container_of(node, struct mytype, node); | |
92 | int result; | |
93 | ||
94 | result = strcmp(string, data->keystring); | |
95 | ||
96 | if (result < 0) | |
97 | node = node->rb_left; | |
98 | else if (result > 0) | |
99 | node = node->rb_right; | |
100 | else | |
101 | return data; | |
102 | } | |
103 | return NULL; | |
104 | } | |
105 | ||
106 | Inserting data into an rbtree | |
107 | ----------------------------- | |
108 | ||
109 | Inserting data in the tree involves first searching for the place to insert the | |
110 | new node, then inserting the node and rebalancing ("recoloring") the tree. | |
111 | ||
112 | The search for insertion differs from the previous search by finding the | |
113 | location of the pointer on which to graft the new node. The new node also | |
114 | needs a link to its parent node for rebalancing purposes. | |
115 | ||
116 | Example:: | |
117 | ||
118 | int my_insert(struct rb_root *root, struct mytype *data) | |
119 | { | |
120 | struct rb_node **new = &(root->rb_node), *parent = NULL; | |
121 | ||
122 | /* Figure out where to put new node */ | |
123 | while (*new) { | |
124 | struct mytype *this = container_of(*new, struct mytype, node); | |
125 | int result = strcmp(data->keystring, this->keystring); | |
126 | ||
127 | parent = *new; | |
128 | if (result < 0) | |
129 | new = &((*new)->rb_left); | |
130 | else if (result > 0) | |
131 | new = &((*new)->rb_right); | |
132 | else | |
133 | return FALSE; | |
134 | } | |
135 | ||
136 | /* Add new node and rebalance tree. */ | |
137 | rb_link_node(&data->node, parent, new); | |
138 | rb_insert_color(&data->node, root); | |
139 | ||
140 | return TRUE; | |
141 | } | |
142 | ||
143 | Removing or replacing existing data in an rbtree | |
144 | ------------------------------------------------ | |
145 | ||
146 | To remove an existing node from a tree, call:: | |
147 | ||
148 | void rb_erase(struct rb_node *victim, struct rb_root *tree); | |
149 | ||
150 | Example:: | |
151 | ||
152 | struct mytype *data = mysearch(&mytree, "walrus"); | |
153 | ||
154 | if (data) { | |
155 | rb_erase(&data->node, &mytree); | |
156 | myfree(data); | |
157 | } | |
158 | ||
159 | To replace an existing node in a tree with a new one with the same key, call:: | |
160 | ||
161 | void rb_replace_node(struct rb_node *old, struct rb_node *new, | |
162 | struct rb_root *tree); | |
163 | ||
164 | Replacing a node this way does not re-sort the tree: If the new node doesn't | |
165 | have the same key as the old node, the rbtree will probably become corrupted. | |
166 | ||
167 | Iterating through the elements stored in an rbtree (in sort order) | |
168 | ------------------------------------------------------------------ | |
169 | ||
170 | Four functions are provided for iterating through an rbtree's contents in | |
171 | sorted order. These work on arbitrary trees, and should not need to be | |
172 | modified or wrapped (except for locking purposes):: | |
173 | ||
174 | struct rb_node *rb_first(struct rb_root *tree); | |
175 | struct rb_node *rb_last(struct rb_root *tree); | |
176 | struct rb_node *rb_next(struct rb_node *node); | |
177 | struct rb_node *rb_prev(struct rb_node *node); | |
178 | ||
179 | To start iterating, call rb_first() or rb_last() with a pointer to the root | |
180 | of the tree, which will return a pointer to the node structure contained in | |
181 | the first or last element in the tree. To continue, fetch the next or previous | |
182 | node by calling rb_next() or rb_prev() on the current node. This will return | |
183 | NULL when there are no more nodes left. | |
184 | ||
185 | The iterator functions return a pointer to the embedded struct rb_node, from | |
186 | which the containing data structure may be accessed with the container_of() | |
187 | macro, and individual members may be accessed directly via | |
188 | rb_entry(node, type, member). | |
189 | ||
190 | Example:: | |
191 | ||
192 | struct rb_node *node; | |
193 | for (node = rb_first(&mytree); node; node = rb_next(node)) | |
194 | printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring); | |
195 | ||
196 | Support for Augmented rbtrees | |
197 | ----------------------------- | |
198 | ||
199 | Augmented rbtree is an rbtree with "some" additional data stored in | |
200 | each node, where the additional data for node N must be a function of | |
201 | the contents of all nodes in the subtree rooted at N. This data can | |
202 | be used to augment some new functionality to rbtree. Augmented rbtree | |
203 | is an optional feature built on top of basic rbtree infrastructure. | |
204 | An rbtree user who wants this feature will have to call the augmentation | |
205 | functions with the user provided augmentation callback when inserting | |
206 | and erasing nodes. | |
207 | ||
208 | C files implementing augmented rbtree manipulation must include | |
209 | <linux/rbtree_augmented.h> instead of <linux/rbtree.h>. Note that | |
210 | linux/rbtree_augmented.h exposes some rbtree implementations details | |
211 | you are not expected to rely on; please stick to the documented APIs | |
212 | there and do not include <linux/rbtree_augmented.h> from header files | |
213 | either so as to minimize chances of your users accidentally relying on | |
214 | such implementation details. | |
215 | ||
216 | On insertion, the user must update the augmented information on the path | |
217 | leading to the inserted node, then call rb_link_node() as usual and | |
218 | rb_augment_inserted() instead of the usual rb_insert_color() call. | |
219 | If rb_augment_inserted() rebalances the rbtree, it will callback into | |
220 | a user provided function to update the augmented information on the | |
221 | affected subtrees. | |
222 | ||
223 | When erasing a node, the user must call rb_erase_augmented() instead of | |
224 | rb_erase(). rb_erase_augmented() calls back into user provided functions | |
225 | to updated the augmented information on affected subtrees. | |
226 | ||
227 | In both cases, the callbacks are provided through struct rb_augment_callbacks. | |
228 | 3 callbacks must be defined: | |
229 | ||
230 | - A propagation callback, which updates the augmented value for a given | |
231 | node and its ancestors, up to a given stop point (or NULL to update | |
232 | all the way to the root). | |
233 | ||
234 | - A copy callback, which copies the augmented value for a given subtree | |
235 | to a newly assigned subtree root. | |
236 | ||
237 | - A tree rotation callback, which copies the augmented value for a given | |
238 | subtree to a newly assigned subtree root AND recomputes the augmented | |
239 | information for the former subtree root. | |
240 | ||
241 | The compiled code for rb_erase_augmented() may inline the propagation and | |
242 | copy callbacks, which results in a large function, so each augmented rbtree | |
243 | user should have a single rb_erase_augmented() call site in order to limit | |
244 | compiled code size. | |
245 | ||
246 | ||
247 | Sample usage | |
248 | ^^^^^^^^^^^^ | |
249 | ||
250 | Interval tree is an example of augmented rb tree. Reference - | |
251 | "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. | |
252 | More details about interval trees: | |
253 | ||
254 | Classical rbtree has a single key and it cannot be directly used to store | |
255 | interval ranges like [lo:hi] and do a quick lookup for any overlap with a new | |
256 | lo:hi or to find whether there is an exact match for a new lo:hi. | |
257 | ||
258 | However, rbtree can be augmented to store such interval ranges in a structured | |
259 | way making it possible to do efficient lookup and exact match. | |
260 | ||
261 | This "extra information" stored in each node is the maximum hi | |
262 | (max_hi) value among all the nodes that are its descendants. This | |
263 | information can be maintained at each node just be looking at the node | |
264 | and its immediate children. And this will be used in O(log n) lookup | |
265 | for lowest match (lowest start address among all possible matches) | |
266 | with something like:: | |
267 | ||
268 | struct interval_tree_node * | |
269 | interval_tree_first_match(struct rb_root *root, | |
270 | unsigned long start, unsigned long last) | |
271 | { | |
272 | struct interval_tree_node *node; | |
273 | ||
274 | if (!root->rb_node) | |
275 | return NULL; | |
276 | node = rb_entry(root->rb_node, struct interval_tree_node, rb); | |
277 | ||
278 | while (true) { | |
279 | if (node->rb.rb_left) { | |
280 | struct interval_tree_node *left = | |
281 | rb_entry(node->rb.rb_left, | |
282 | struct interval_tree_node, rb); | |
283 | if (left->__subtree_last >= start) { | |
284 | /* | |
285 | * Some nodes in left subtree satisfy Cond2. | |
286 | * Iterate to find the leftmost such node N. | |
287 | * If it also satisfies Cond1, that's the match | |
288 | * we are looking for. Otherwise, there is no | |
289 | * matching interval as nodes to the right of N | |
290 | * can't satisfy Cond1 either. | |
291 | */ | |
292 | node = left; | |
293 | continue; | |
294 | } | |
295 | } | |
296 | if (node->start <= last) { /* Cond1 */ | |
297 | if (node->last >= start) /* Cond2 */ | |
298 | return node; /* node is leftmost match */ | |
299 | if (node->rb.rb_right) { | |
300 | node = rb_entry(node->rb.rb_right, | |
301 | struct interval_tree_node, rb); | |
302 | if (node->__subtree_last >= start) | |
303 | continue; | |
304 | } | |
305 | } | |
306 | return NULL; /* No match */ | |
307 | } | |
308 | } | |
309 | ||
310 | Insertion/removal are defined using the following augmented callbacks:: | |
311 | ||
312 | static inline unsigned long | |
313 | compute_subtree_last(struct interval_tree_node *node) | |
314 | { | |
315 | unsigned long max = node->last, subtree_last; | |
316 | if (node->rb.rb_left) { | |
317 | subtree_last = rb_entry(node->rb.rb_left, | |
318 | struct interval_tree_node, rb)->__subtree_last; | |
319 | if (max < subtree_last) | |
320 | max = subtree_last; | |
321 | } | |
322 | if (node->rb.rb_right) { | |
323 | subtree_last = rb_entry(node->rb.rb_right, | |
324 | struct interval_tree_node, rb)->__subtree_last; | |
325 | if (max < subtree_last) | |
326 | max = subtree_last; | |
327 | } | |
328 | return max; | |
329 | } | |
330 | ||
331 | static void augment_propagate(struct rb_node *rb, struct rb_node *stop) | |
332 | { | |
333 | while (rb != stop) { | |
334 | struct interval_tree_node *node = | |
335 | rb_entry(rb, struct interval_tree_node, rb); | |
336 | unsigned long subtree_last = compute_subtree_last(node); | |
337 | if (node->__subtree_last == subtree_last) | |
338 | break; | |
339 | node->__subtree_last = subtree_last; | |
340 | rb = rb_parent(&node->rb); | |
341 | } | |
342 | } | |
343 | ||
344 | static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new) | |
345 | { | |
346 | struct interval_tree_node *old = | |
347 | rb_entry(rb_old, struct interval_tree_node, rb); | |
348 | struct interval_tree_node *new = | |
349 | rb_entry(rb_new, struct interval_tree_node, rb); | |
350 | ||
351 | new->__subtree_last = old->__subtree_last; | |
352 | } | |
353 | ||
354 | static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) | |
355 | { | |
356 | struct interval_tree_node *old = | |
357 | rb_entry(rb_old, struct interval_tree_node, rb); | |
358 | struct interval_tree_node *new = | |
359 | rb_entry(rb_new, struct interval_tree_node, rb); | |
360 | ||
361 | new->__subtree_last = old->__subtree_last; | |
362 | old->__subtree_last = compute_subtree_last(old); | |
363 | } | |
364 | ||
365 | static const struct rb_augment_callbacks augment_callbacks = { | |
366 | augment_propagate, augment_copy, augment_rotate | |
367 | }; | |
368 | ||
369 | void interval_tree_insert(struct interval_tree_node *node, | |
370 | struct rb_root *root) | |
371 | { | |
372 | struct rb_node **link = &root->rb_node, *rb_parent = NULL; | |
373 | unsigned long start = node->start, last = node->last; | |
374 | struct interval_tree_node *parent; | |
375 | ||
376 | while (*link) { | |
377 | rb_parent = *link; | |
378 | parent = rb_entry(rb_parent, struct interval_tree_node, rb); | |
379 | if (parent->__subtree_last < last) | |
380 | parent->__subtree_last = last; | |
381 | if (start < parent->start) | |
382 | link = &parent->rb.rb_left; | |
383 | else | |
384 | link = &parent->rb.rb_right; | |
385 | } | |
386 | ||
387 | node->__subtree_last = last; | |
388 | rb_link_node(&node->rb, rb_parent, link); | |
389 | rb_insert_augmented(&node->rb, root, &augment_callbacks); | |
390 | } | |
391 | ||
392 | void interval_tree_remove(struct interval_tree_node *node, | |
393 | struct rb_root *root) | |
394 | { | |
395 | rb_erase_augmented(&node->rb, root, &augment_callbacks); | |
396 | } |