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 
31 static inline struct rbnode *rbnode_get_parent(const struct rbnode *node);
32 
37 static void rbnode_set_parent(struct rbnode *node, const struct rbnode *parent);
38 
40 static inline int rbnode_get_color(const struct rbnode *node);
41 
46 static inline void rbnode_set_color(struct rbnode *node, int color);
47 
49 static struct rbnode *rbnode_min(struct rbnode *node);
50 
52 static struct rbnode *rbnode_max(struct rbnode *node);
53 
58 static void rbtree_rol(struct rbtree *tree, struct rbnode *node);
59 
64 static void rbtree_ror(struct rbtree *tree, struct rbnode *node);
65 
70 static void rbtree_replace(struct rbtree *tree, struct rbnode *old_node,
71  struct rbnode *new_node);
72 
73 struct rbnode *
74 rbnode_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;
85  parent = rbnode_get_parent(node);
86  }
87  return parent;
88 }
89 
90 struct rbnode *
91 rbnode_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;
102  parent = rbnode_get_parent(node);
103  }
104  return parent;
105 }
106 
107 void
108 rbtree_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.
133  rbnode_set_parent(node, parent);
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);
152  parent = rbnode_get_parent(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);
172  parent = rbnode_get_parent(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  }
181  parent = rbnode_get_parent(node);
182  }
183  rbnode_set_color(tree->root, 0);
184 }
185 
186 void
187 rbtree_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);
213  rbnode_set_color(next, rbnode_get_color(node));
214  struct rbnode *tmp = next->right;
215  if (rbnode_get_parent(next) == node) {
216  parent = next;
217  } else {
218  parent = rbnode_get_parent(next);
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;
253  parent = rbnode_get_parent(node);
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;
283  parent = rbnode_get_parent(node);
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 
305 struct rbnode *
306 rbtree_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 
321 int
322 rbtree_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 
334 struct rbnode *
335 rbtree_first(const struct rbtree *tree)
336 {
337  assert(tree);
338 
339  return tree->root ? rbnode_min(tree->root) : NULL;
340 }
341 
342 struct rbnode *
343 rbtree_last(const struct rbtree *tree)
344 {
345  assert(tree);
346 
347  return tree->root ? rbnode_max(tree->root) : NULL;
348 }
349 
350 static inline struct rbnode *
351 rbnode_get_parent(const struct rbnode *node)
352 {
353  assert(node);
354 
355  return (struct rbnode *)(node->parent & ~(uintptr_t)1);
356 }
357 
358 static void
359 rbnode_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 
367 static inline int
368 rbnode_get_color(const struct rbnode *node)
369 {
370  return node ? node->parent & (uintptr_t)1 : 0;
371 }
372 
373 static inline void
374 rbnode_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 
385 static struct rbnode *
386 rbnode_min(struct rbnode *node)
387 {
388  assert(node);
389 
390  while (node->left)
391  node = node->left;
392  return node;
393 }
394 
395 static struct rbnode *
396 rbnode_max(struct rbnode *node)
397 {
398  assert(node);
399 
400  while (node->right)
401  node = node->right;
402  return node;
403 }
404 
405 static void
406 rbtree_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 
427 static void
428 rbtree_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 
449 static void
450 rbtree_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 * 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
void rbtree_insert(struct rbtree *tree, struct rbnode *node)
Inserts a node into a red-black tree.
Definition: rbtree.c:108
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
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
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
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
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
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 * 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
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