Lely core libraries  2.2.5
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 struct rbnode *
322 rbtree_first(const struct rbtree *tree)
323 {
324  assert(tree);
325 
326  return tree->root ? rbnode_min(tree->root) : NULL;
327 }
328 
329 struct rbnode *
330 rbtree_last(const struct rbtree *tree)
331 {
332  assert(tree);
333 
334  return tree->root ? rbnode_max(tree->root) : NULL;
335 }
336 
337 static inline struct rbnode *
338 rbnode_get_parent(const struct rbnode *node)
339 {
340  return node ? (struct rbnode *)(node->parent & ~(uintptr_t)1) : NULL;
341 }
342 
343 static void
344 rbnode_set_parent(struct rbnode *node, const struct rbnode *parent)
345 {
346  if (!node)
347  return;
348 
349  node->parent = (uintptr_t)parent | rbnode_get_color(node);
350 }
351 
352 static inline int
353 rbnode_get_color(const struct rbnode *node)
354 {
355  return node ? node->parent & (uintptr_t)1 : 0;
356 }
357 
358 static inline void
359 rbnode_set_color(struct rbnode *node, int color)
360 {
361  if (!node)
362  return;
363 
364  if (color)
365  node->parent |= (uintptr_t)1;
366  else
367  node->parent &= ~(uintptr_t)1;
368 }
369 
370 static struct rbnode *
371 rbnode_min(struct rbnode *node)
372 {
373  assert(node);
374 
375  while (node->left)
376  node = node->left;
377  return node;
378 }
379 
380 static struct rbnode *
381 rbnode_max(struct rbnode *node)
382 {
383  assert(node);
384 
385  while (node->right)
386  node = node->right;
387  return node;
388 }
389 
390 static void
391 rbtree_rol(struct rbtree *tree, struct rbnode *node)
392 {
393  assert(tree);
394  assert(node);
395  assert(node->right);
396 
397  struct rbnode *tmp = node->right;
398  node->right = tmp->left;
399  rbnode_set_parent(tmp->left, node);
400  tmp->left = node;
401  struct rbnode *parent = rbnode_get_parent(node);
402  rbnode_set_parent(node, tmp);
404  if (!parent)
405  tree->root = tmp;
406  else if (node == parent->left)
407  parent->left = tmp;
408  else
409  parent->right = tmp;
410 }
411 
412 static void
413 rbtree_ror(struct rbtree *tree, struct rbnode *node)
414 {
415  assert(tree);
416  assert(node);
417  assert(node->left);
418 
419  struct rbnode *tmp = node->left;
420  node->left = tmp->right;
421  rbnode_set_parent(tmp->right, node);
422  tmp->right = node;
423  struct rbnode *parent = rbnode_get_parent(node);
424  rbnode_set_parent(node, tmp);
426  if (!parent)
427  tree->root = tmp;
428  else if (node == parent->right)
429  parent->right = tmp;
430  else
431  parent->left = tmp;
432 }
433 
434 static void
435 rbtree_replace(struct rbtree *tree, struct rbnode *old_node,
436  struct rbnode *new_node)
437 {
438  struct rbnode *parent = rbnode_get_parent(old_node);
439  if (!parent)
440  tree->root = new_node;
441  else if (old_node == parent->left)
442  parent->left = new_node;
443  else
444  parent->right = new_node;
445  rbnode_set_parent(new_node, parent);
446 }
static struct rbnode * rbnode_max(struct rbnode *node)
Returns the rightmost descendant of node.
Definition: rbtree.c:381
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:330
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:413
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:435
static int rbnode_get_color(const struct rbnode *node)
Returns the color of node, or 0 (black) if node is NULL.
Definition: rbtree.c:353
static struct rbnode * rbnode_get_parent(const struct rbnode *node)
Returns the parent of node, or NULL if node is NULL.
Definition: rbtree.c:338
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:359
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:391
static void rbnode_set_parent(struct rbnode *node, const struct rbnode *parent)
Sets the parent of node to parent.
Definition: rbtree.c:344
static struct rbnode * rbnode_min(struct rbnode *node)
Returns the leftmost descendant of node.
Definition: rbtree.c:371
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:322
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:52
struct rbnode * left
A pointer to the left child node.
Definition: rbtree.h:65
struct rbnode * right
A pointer to the right child node.
Definition: rbtree.h:67
const void * key
A pointer to the key for this node.
Definition: rbtree.h:58
uintptr_t parent
A pointer to the parent node.
Definition: rbtree.h:63
A red-black tree.
Definition: rbtree.h:90
rbtree_cmp_t * cmp
A pointer to the function used to compare two keys.
Definition: rbtree.h:92
size_t num_nodes
The number of nodes stored in the tree.
Definition: rbtree.h:96
struct rbnode * root
A pointer to the root node of the tree.
Definition: rbtree.h:94