Lely core libraries 2.3.4
rbtree.c
Go to the documentation of this file.
1
24#include "util.h"
25#define LELY_UTIL_RBTREE_INLINE extern inline
26#include <lely/util/rbtree.h>
27
28#include <assert.h>
29
31static inline struct rbnode *rbnode_get_parent(const struct rbnode *node);
32
37static void rbnode_set_parent(struct rbnode *node, const struct rbnode *parent);
38
40static inline int rbnode_get_color(const struct rbnode *node);
41
46static inline void rbnode_set_color(struct rbnode *node, int color);
47
49static struct rbnode *rbnode_min(struct rbnode *node);
50
52static struct rbnode *rbnode_max(struct rbnode *node);
53
58static void rbtree_rol(struct rbtree *tree, struct rbnode *node);
59
64static void rbtree_ror(struct rbtree *tree, struct rbnode *node);
65
70static void rbtree_replace(struct rbtree *tree, struct rbnode *old_node,
71 struct rbnode *new_node);
72
73struct rbnode *
74rbnode_prev(const struct rbnode *node)
75{
76 assert(node);
77
78 // If the node has a left subtree, find its rightmost descendant.
79 if (node->left)
80 return rbnode_max(node->left);
81 // Find the lowest ancestor that has the node in its right subtree.
82 struct rbnode *parent = rbnode_get_parent(node);
83 while (parent && node == parent->left) {
84 node = parent;
86 }
87 return parent;
88}
89
90struct rbnode *
91rbnode_next(const struct rbnode *node)
92{
93 assert(node);
94
95 // If the node has a right subtree, find its leftmost descendant.
96 if (node->right)
97 return rbnode_min(node->right);
98 // Find the lowest ancestor that has the node in its left subtree.
99 struct rbnode *parent = rbnode_get_parent(node);
100 while (parent && node == parent->right) {
101 node = parent;
103 }
104 return parent;
105}
106
107void
108rbtree_insert(struct rbtree *tree, struct rbnode *node)
109{
110 assert(tree);
111 assert(tree->cmp);
112 assert(node);
113
114 // Find the parent of the new node.
115 struct rbnode *parent = NULL;
116 struct rbnode *next = tree->root;
117 while (next) {
118 parent = next;
119 // clang-format off
120 next = tree->cmp(node->key, next->key) < 0
121 ? next->left : next->right;
122 // clang-format on
123 }
124 // Attach the node to its parent.
125 if (!parent)
126 tree->root = node;
127 else if (tree->cmp(node->key, parent->key) < 0)
128 parent->left = node;
129 else
130 parent->right = node;
131 tree->num_nodes++;
132 // Initialize the node.
134 rbnode_set_color(node, 1);
135 node->left = NULL;
136 node->right = NULL;
137 // Fix violations of the red-black properties.
138 while (rbnode_get_color(parent)) {
139 struct rbnode *gparent = rbnode_get_parent(parent);
140 if (parent == gparent->left) {
141 if (rbnode_get_color(gparent->right)) {
142 // Case 1: flip colors.
143 rbnode_set_color(gparent, 1);
145 rbnode_set_color(gparent->right, 0);
146 node = gparent;
147 } else {
148 if (node == parent->right) {
149 // Case 2: left rotate at grandparent.
150 node = parent;
151 rbtree_rol(tree, node);
153 gparent = rbnode_get_parent(parent);
154 }
155 // Case 3: right rotate at grandparent.
156 rbnode_set_color(gparent, 1);
158 rbtree_ror(tree, gparent);
159 }
160 } else {
161 if (rbnode_get_color(gparent->left)) {
162 // Case 1: flip colors.
163 rbnode_set_color(gparent, 1);
165 rbnode_set_color(gparent->left, 0);
166 node = gparent;
167 } else {
168 if (node == parent->left) {
169 // Case 2: right rotate at grandparent.
170 node = parent;
171 rbtree_ror(tree, node);
173 gparent = rbnode_get_parent(parent);
174 }
175 // Case 3: left rotate at grandparent.
176 rbnode_set_color(gparent, 1);
178 rbtree_rol(tree, gparent);
179 }
180 }
182 }
183 rbnode_set_color(tree->root, 0);
184}
185
186void
187rbtree_remove(struct rbtree *tree, struct rbnode *node)
188{
189 assert(tree);
190 assert(node);
191
192 int color = rbnode_get_color(node);
193 struct rbnode *parent = rbnode_get_parent(node);
194 // Remove the node from the tree. After removal, node points to the
195 // subtree in which we might have introduced red-black property
196 // violations.
197 if (!node->left) {
198 // There is no left subtree, so we can replace the node by its
199 // right subtree.
200 rbtree_replace(tree, node, node->right);
201 node = node->right;
202 } else if (!node->right) {
203 // There is no right subtree, so we can replace the node by its
204 // left subtree.
205 rbtree_replace(tree, node, node->left);
206 node = node->left;
207 } else {
208 // There is both a left and a right subtree, so we replace the
209 // node by its successor. First, find the successor and give it
210 // the same color as the node to be removed.
211 struct rbnode *next = rbnode_min(node->right);
212 color = rbnode_get_color(next);
214 struct rbnode *tmp = next->right;
215 if (rbnode_get_parent(next) == node) {
216 parent = next;
217 } else {
219 // If the successor is not a child of the node to be
220 // removed, we remove it from its parent.
221 rbtree_replace(tree, next, next->right);
222 next->right = node->right;
223 rbnode_set_parent(next->right, next);
224 }
225 // Replace the node to be removed by its successor.
226 rbtree_replace(tree, node, next);
227 // The successor has no left subtree (by definition). Attach the
228 // left subtree of the node to be removed to the successor.
229 next->left = node->left;
230 rbnode_set_parent(next->left, next);
231 node = tmp;
232 }
233 tree->num_nodes--;
234 // Fix violations of the red-black properties. This can only occur if
235 // the removed node (or its successor) was black.
236 if (color)
237 return;
238 while (node != tree->root && !rbnode_get_color(node)) {
239 if (node == parent->left) {
240 struct rbnode *tmp = parent->right;
241 if (rbnode_get_color(tmp)) {
242 // Case 1: left rotate at parent.
244 rbnode_set_color(tmp, 0);
245 rbtree_rol(tree, parent);
246 tmp = parent->right;
247 }
248 if (!rbnode_get_color(tmp->left)
249 && !rbnode_get_color(tmp->right)) {
250 // Case 2: color flip at sibling.
251 rbnode_set_color(tmp, 1);
252 node = parent;
254 } else {
255 if (!rbnode_get_color(tmp->right)) {
256 // Case 3: right rotate at sibling.
257 rbnode_set_color(tmp, 1);
258 rbnode_set_color(tmp->left, 0);
259 rbtree_ror(tree, tmp);
260 tmp = parent->right;
261 }
262 // Case 4: left rotate at parent and color flip.
265 rbnode_set_color(tmp->right, 0);
266 rbtree_rol(tree, parent);
267 node = tree->root;
268 }
269 } else {
270 struct rbnode *tmp = parent->left;
271 if (rbnode_get_color(tmp)) {
272 // Case 1: right rotate at parent.
274 rbnode_set_color(tmp, 0);
275 rbtree_ror(tree, parent);
276 tmp = parent->left;
277 }
278 if (!rbnode_get_color(tmp->right)
279 && !rbnode_get_color(tmp->left)) {
280 // Case 2: color flip at sibling.
281 rbnode_set_color(tmp, 1);
282 node = parent;
284 } else {
285 if (!rbnode_get_color(tmp->left)) {
286 // Case 3: left rotate at sibling.
287 rbnode_set_color(tmp, 1);
288 rbnode_set_color(tmp->right, 0);
289 rbtree_rol(tree, tmp);
290 tmp = parent->left;
291 }
292 // Case 4: right rotate at parent and color
293 // flip.
296 rbnode_set_color(tmp->left, 0);
297 rbtree_ror(tree, parent);
298 node = tree->root;
299 }
300 }
301 }
302 rbnode_set_color(node, 0);
303}
304
305struct rbnode *
306rbtree_find(const struct rbtree *tree, const void *key)
307{
308 assert(tree);
309 assert(tree->cmp);
310
311 struct rbnode *node = tree->root;
312 while (node) {
313 int cmp = tree->cmp(key, node->key);
314 if (!cmp)
315 break;
316 node = cmp < 0 ? node->left : node->right;
317 }
318 return node;
319}
320
321int
322rbtree_contains(const struct rbtree *tree, const struct rbnode *node)
323{
324 assert(tree);
325
326 while (node) {
327 if (node == tree->root)
328 return 1;
329 node = rbnode_get_parent(node);
330 }
331 return 0;
332}
333
334struct rbnode *
335rbtree_first(const struct rbtree *tree)
336{
337 assert(tree);
338
339 return tree->root ? rbnode_min(tree->root) : NULL;
340}
341
342struct rbnode *
343rbtree_last(const struct rbtree *tree)
344{
345 assert(tree);
346
347 return tree->root ? rbnode_max(tree->root) : NULL;
348}
349
350static inline struct rbnode *
351rbnode_get_parent(const struct rbnode *node)
352{
353 assert(node);
354
355 return (struct rbnode *)(node->parent & ~(uintptr_t)1);
356}
357
358static void
359rbnode_set_parent(struct rbnode *node, const struct rbnode *parent)
360{
361 if (!node)
362 return;
363
364 node->parent = (uintptr_t)parent | rbnode_get_color(node);
365}
366
367static inline int
368rbnode_get_color(const struct rbnode *node)
369{
370 return node ? node->parent & (uintptr_t)1 : 0;
371}
372
373static inline void
374rbnode_set_color(struct rbnode *node, int color)
375{
376 if (!node)
377 return;
378
379 if (color)
380 node->parent |= (uintptr_t)1;
381 else
382 node->parent &= ~(uintptr_t)1;
383}
384
385static struct rbnode *
386rbnode_min(struct rbnode *node)
387{
388 assert(node);
389
390 while (node->left)
391 node = node->left;
392 return node;
393}
394
395static struct rbnode *
396rbnode_max(struct rbnode *node)
397{
398 assert(node);
399
400 while (node->right)
401 node = node->right;
402 return node;
403}
404
405static void
406rbtree_rol(struct rbtree *tree, struct rbnode *node)
407{
408 assert(tree);
409 assert(node);
410 assert(node->right);
411
412 struct rbnode *tmp = node->right;
413 node->right = tmp->left;
414 rbnode_set_parent(tmp->left, node);
415 tmp->left = node;
416 struct rbnode *parent = rbnode_get_parent(node);
417 rbnode_set_parent(node, tmp);
419 if (!parent)
420 tree->root = tmp;
421 else if (node == parent->left)
422 parent->left = tmp;
423 else
424 parent->right = tmp;
425}
426
427static void
428rbtree_ror(struct rbtree *tree, struct rbnode *node)
429{
430 assert(tree);
431 assert(node);
432 assert(node->left);
433
434 struct rbnode *tmp = node->left;
435 node->left = tmp->right;
436 rbnode_set_parent(tmp->right, node);
437 tmp->right = node;
438 struct rbnode *parent = rbnode_get_parent(node);
439 rbnode_set_parent(node, tmp);
441 if (!parent)
442 tree->root = tmp;
443 else if (node == parent->right)
444 parent->right = tmp;
445 else
446 parent->left = tmp;
447}
448
449static void
450rbtree_replace(struct rbtree *tree, struct rbnode *old_node,
451 struct rbnode *new_node)
452{
453 struct rbnode *parent = rbnode_get_parent(old_node);
454 if (!parent)
455 tree->root = new_node;
456 else if (old_node == parent->left)
457 parent->left = new_node;
458 else
459 parent->right = new_node;
460 rbnode_set_parent(new_node, parent);
461}
static struct rbnode * rbnode_max(struct rbnode *node)
Returns the rightmost descendant of node.
Definition: rbtree.c:396
struct rbnode * rbtree_last(const struct rbtree *tree)
Returns a pointer to the last (rightmost) node in a red-black tree.
Definition: rbtree.c:343
void rbtree_insert(struct rbtree *tree, struct rbnode *node)
Inserts a node into a red-black tree.
Definition: rbtree.c:108
struct rbnode * rbtree_find(const struct rbtree *tree, const void *key)
Finds a node in a red-black tree.
Definition: rbtree.c:306
struct rbnode * rbtree_first(const struct rbtree *tree)
Returns a pointer to the first (leftmost) node in a red-black tree.
Definition: rbtree.c:335
static void rbtree_ror(struct rbtree *tree, struct rbnode *node)
Rotates node clockwise (right), i.e., it is replaced in the tree by its left child,...
Definition: rbtree.c:428
static void rbtree_replace(struct rbtree *tree, struct rbnode *old_node, struct rbnode *new_node)
Replaces old_node by new_node in tree by updating its parent.
Definition: rbtree.c:450
static int rbnode_get_color(const struct rbnode *node)
Returns the color of node, or 0 (black) if node is NULL.
Definition: rbtree.c:368
struct rbnode * rbnode_next(const struct rbnode *node)
Returns a pointer to the next (in-order) node in a red-black tree with respect to node.
Definition: rbtree.c:91
int rbtree_contains(const struct rbtree *tree, const struct rbnode *node)
Checks if a node is part of a red-black tree.
Definition: rbtree.c:322
static struct rbnode * rbnode_get_parent(const struct rbnode *node)
Returns the parent of node. node MUST NOT be NULL.
Definition: rbtree.c:351
static void rbnode_set_color(struct rbnode *node, int color)
Sets the color of node to 0 (black) if color is 0, or to 1 (red) otherwise.
Definition: rbtree.c:374
static void rbtree_rol(struct rbtree *tree, struct rbnode *node)
Rotates node counter-clockwise (left), i.e., it is replaced in the tree by its right child,...
Definition: rbtree.c:406
struct rbnode * rbnode_prev(const struct rbnode *node)
Returns a pointer to the previous (in-order) node in a red-black tree with respect to node.
Definition: rbtree.c:74
static void rbnode_set_parent(struct rbnode *node, const struct rbnode *parent)
Sets the parent of node to parent.
Definition: rbtree.c:359
static struct rbnode * rbnode_min(struct rbnode *node)
Returns the leftmost descendant of node.
Definition: rbtree.c:386
void rbtree_remove(struct rbtree *tree, struct rbnode *node)
Removes a node from a red-black tree.
Definition: rbtree.c:187
This header file is part of the utilities library; it contains the red-black tree declarations.
This is the internal header file of the utilities library.
A node in a red-black tree.
Definition: rbtree.h:53
struct rbnode * left
A pointer to the left child node.
Definition: rbtree.h:66
struct rbnode * right
A pointer to the right child node.
Definition: rbtree.h:68
const void * key
A pointer to the key for this node.
Definition: rbtree.h:59
uintptr_t parent
A pointer to the parent node.
Definition: rbtree.h:64
A red-black tree.
Definition: rbtree.h:91
rbtree_cmp_t * cmp
A pointer to the function used to compare two keys.
Definition: rbtree.h:93
size_t num_nodes
The number of nodes stored in the tree.
Definition: rbtree.h:97
struct rbnode * root
A pointer to the root node of the tree.
Definition: rbtree.h:95