Blender  V3.3
DLRB_tree.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2009 Blender Foundation, Joshua Leung. All rights reserved. */
3 
8 #include "MEM_guardedalloc.h"
9 
10 #include "BLI_dlrbTree.h"
11 #include "BLI_listbase.h"
12 
13 /* *********************************************** */
14 /* Tree API */
15 
17 {
18  /* just allocate for now */
19  return MEM_callocN(sizeof(DLRBT_Tree), "DLRBT_Tree");
20 }
21 
23 {
24  if (tree == NULL) {
25  return;
26  }
27 
28  tree->first = tree->last = tree->root = NULL;
29 }
30 
31 /* Helper for traversing tree and freeing sub-nodes */
33 {
34  /* sanity check */
35  if (node == NULL) {
36  return;
37  }
38 
39  /* free child nodes + subtrees */
40  recursive_tree_free_nodes(node->left, free_cb);
41  recursive_tree_free_nodes(node->right, free_cb);
42 
43  /* free self */
44  if (free_cb) {
45  free_cb(node);
46  }
47 }
48 
50 {
51  if (tree == NULL) {
52  return;
53  }
54 
55  /* if the list-base stuff is set, just use that (and assume its set),
56  * otherwise, we'll need to traverse the tree...
57  */
58  if (tree->first) {
59  /* free list */
60  if (free_cb) {
62  free_cb(node);
63  }
65  }
66  else {
68  }
69  }
70  else {
71  /* traverse tree, freeing sub-nodes */
72  recursive_tree_free_nodes(tree->root, free_cb);
73  }
74 
75  /* clear pointers */
76  tree->first = tree->last = tree->root = NULL;
77 }
78 
79 /* ------- */
80 
81 /* Helper function - used for traversing down the tree from the root to add nodes in order */
83 {
84  /* sanity checks */
85  if ((tree == NULL) || (node == NULL)) {
86  return;
87  }
88 
89  /* add left-node (and its subtree) */
91 
92  /* now add self
93  * - must remove detach from other links first
94  * (for now, only clear own pointers)
95  */
96  node->prev = node->next = NULL;
98 
99  /* finally, add right node (and its subtree) */
101 }
102 
104 {
105  /* sanity checks */
106  if (tree == NULL) {
107  return;
108  }
109 
110  /* clear list-base pointers so that the new list can be added properly */
111  tree->first = tree->last = NULL;
112 
113  /* start adding items from the root */
115 }
116 
117 /* *********************************************** */
118 /* Tree Search Utilities */
119 
121  DLRBT_Comparator_FP cmp_cb,
122  void *search_data)
123 {
124  DLRBT_Node *node = (tree) ? tree->root : NULL;
125  short found = 0;
126 
127  /* check that there is a comparator to use */
128  /* TODO: if no comparator is supplied, try using the one supplied with the tree... */
129  if (cmp_cb == NULL) {
130  return NULL;
131  }
132 
133  /* iteratively perform this search */
134  while (node && found == 0) {
135  /* check if traverse further or not
136  * NOTE: it is assumed that the values will be unit values only
137  */
138  switch (cmp_cb(node, search_data)) {
139  case -1: /* data less than node */
140  if (node->left) {
141  node = node->left;
142  }
143  else {
144  found = 1;
145  }
146  break;
147 
148  case 1: /* data greater than node */
149  if (node->right) {
150  node = node->right;
151  }
152  else {
153  found = 1;
154  }
155  break;
156 
157  default: /* data equals node */
158  found = 1;
159  break;
160  }
161  }
162 
163  /* return the nearest matching node */
164  return node;
165 }
166 
168  DLRBT_Comparator_FP cmp_cb,
169  void *search_data)
170 {
171  DLRBT_Node *node = (tree) ? tree->root : NULL;
172  short found = 0;
173 
174  /* check that there is a comparator to use */
175  /* TODO: if no comparator is supplied, try using the one supplied with the tree... */
176  if (cmp_cb == NULL) {
177  return NULL;
178  }
179 
180  /* iteratively perform this search */
181  while (node && found == 0) {
182  /* check if traverse further or not
183  * NOTE: it is assumed that the values will be unit values only
184  */
185  switch (cmp_cb(node, search_data)) {
186  case -1: /* data less than node */
187  if (node->left) {
188  node = node->left;
189  }
190  else {
191  found = -1;
192  }
193  break;
194 
195  case 1: /* data greater than node */
196  if (node->right) {
197  node = node->right;
198  }
199  else {
200  found = -1;
201  }
202  break;
203 
204  default: /* data equals node */
205  found = 1;
206  break;
207  }
208  }
209 
210  /* return the exactly matching node */
211  return (found == 1) ? (node) : (NULL);
212 }
213 
215  DLRBT_Comparator_FP cmp_cb,
216  void *search_data)
217 {
218  DLRBT_Node *node;
219 
220  /* check that there is a comparator to use */
221  /* TODO: if no comparator is supplied, try using the one supplied with the tree... */
222  if (cmp_cb == NULL) {
223  return NULL;
224  }
225 
226  /* get the node which best matches this description */
227  node = BLI_dlrbTree_search(tree, cmp_cb, search_data);
228 
229  if (node) {
230  /* if the item we're searching for is greater than the node found, we've found the match */
231  if (cmp_cb(node, search_data) > 0) {
232  return node;
233  }
234 
235  /* return the previous node otherwise */
236  /* NOTE: what happens if there is no previous node? */
237  return node->prev;
238  }
239 
240  /* nothing matching was found */
241  return NULL;
242 }
243 
245  DLRBT_Comparator_FP cmp_cb,
246  void *search_data)
247 {
248  DLRBT_Node *node;
249 
250  /* check that there is a comparator to use */
251  /* TODO: if no comparator is supplied, try using the one supplied with the tree... */
252  if (cmp_cb == NULL) {
253  return NULL;
254  }
255 
256  /* get the node which best matches this description */
257  node = BLI_dlrbTree_search(tree, cmp_cb, search_data);
258 
259  if (node) {
260  /* if the item we're searching for is less than the node found, we've found the match */
261  if (cmp_cb(node, search_data) < 0) {
262  return node;
263  }
264 
265  /* return the previous node otherwise */
266  /* NOTE: what happens if there is no previous node? */
267  return node->next;
268  }
269 
270  /* nothing matching was found */
271  return NULL;
272 }
273 
274 short BLI_dlrbTree_contains(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
275 {
276  /* check if an exact search throws up anything... */
277  return (BLI_dlrbTree_search_exact(tree, cmp_cb, search_data) != NULL);
278 }
279 
280 /* *********************************************** */
281 /* Tree Relationships Utilities */
282 
283 /* get the 'grandparent' - the parent of the parent - of the given node */
285 {
286  if (node && node->parent) {
287  return node->parent->parent;
288  }
289  return NULL;
290 }
291 
292 /* get the sibling node (e.g. if node is left child of parent, return right child of parent) */
294 {
295  if (node && node->parent) {
296  if (node == node->parent->left) {
297  return node->parent->right;
298  }
299  return node->parent->left;
300  }
301 
302  /* sibling not found */
303  return NULL;
304 }
305 
306 /* get the 'uncle' - the sibling of the parent - of the given node */
308 {
309  if (node) {
310  /* return the child of the grandparent which isn't the node's parent */
311  return get_sibling(node->parent);
312  }
313 
314  /* uncle not found */
315  return NULL;
316 }
317 
318 /* *********************************************** */
319 /* Tree Rotation Utilities */
320 
321 /* make right child of 'root' the new root */
322 static void rotate_left(DLRBT_Tree *tree, DLRBT_Node *root)
323 {
324  DLRBT_Node **root_slot, *pivot;
325 
326  /* pivot is simply the root's right child, to become the root's parent */
327  pivot = root->right;
328  if (pivot == NULL) {
329  return;
330  }
331 
332  if (root->parent) {
333  if (root == root->parent->left) {
334  root_slot = &root->parent->left;
335  }
336  else {
337  root_slot = &root->parent->right;
338  }
339  }
340  else {
341  root_slot = ((DLRBT_Node **)&tree->root); /* &((DLRBT_Node *)tree->root); */
342  }
343 
344  /* - pivot's left child becomes root's right child
345  * - root now becomes pivot's left child
346  */
347  root->right = pivot->left;
348  if (pivot->left) {
349  pivot->left->parent = root;
350  }
351 
352  pivot->left = root;
353  pivot->parent = root->parent;
354  root->parent = pivot;
355 
356  /* make the pivot the new root */
357  if (root_slot) {
358  *root_slot = pivot;
359  }
360 }
361 
362 /* make the left child of the 'root' the new root */
364 {
365  DLRBT_Node **root_slot, *pivot;
366 
367  /* pivot is simply the root's left child, to become the root's parent */
368  pivot = root->left;
369  if (pivot == NULL) {
370  return;
371  }
372 
373  if (root->parent) {
374  if (root == root->parent->left) {
375  root_slot = &root->parent->left;
376  }
377  else {
378  root_slot = &root->parent->right;
379  }
380  }
381  else {
382  root_slot = ((DLRBT_Node **)&tree->root); /* &((DLRBT_Node *)tree->root); */
383  }
384 
385  /* - pivot's right child becomes root's left child
386  * - root now becomes pivot's right child
387  */
388  root->left = pivot->right;
389  if (pivot->right) {
390  pivot->right->parent = root;
391  }
392 
393  pivot->right = root;
394  pivot->parent = root->parent;
395  root->parent = pivot;
396 
397  /* make the pivot the new root */
398  if (root_slot) {
399  *root_slot = pivot;
400  }
401 }
402 
403 /* *********************************************** */
404 /* Post-Insertion Balancing */
405 
406 /* forward defines for insertion checks */
410 
411 /* ----- */
412 
413 /* W. 1) Root must be black (so that the 2nd-generation can have a black parent) */
415 {
416  if (node) {
417  /* if this is the root, just ensure that it is black */
418  if (node->parent == NULL) {
419  node->tree_col = DLRBT_BLACK;
420  }
421  else {
423  }
424  }
425 }
426 
427 /* W. 2+3) Parent of node must be black, otherwise recolor and flush */
429 {
430  /* if the parent is not black, we need to change that... */
431  if (node && node->parent && node->parent->tree_col) {
432  DLRBT_Node *unc = get_uncle(node);
433 
434  /* if uncle and parent are both red, need to change them to black and make
435  * the parent black in order to satisfy the criteria of each node having the
436  * same number of black nodes to its leaves
437  */
438  if (unc && unc->tree_col) {
440 
441  /* make the n-1 generation nodes black */
442  node->parent->tree_col = unc->tree_col = DLRBT_BLACK;
443 
444  /* - make the grandparent red, so that we maintain alternating red/black property
445  * (it must exist, so no need to check for NULL here),
446  * - as the grandparent may now cause inconsistencies with the rest of the tree,
447  * we must flush up the tree and perform checks/re-balancing/re-painting, using the
448  * grandparent as the node of interest
449  */
450  gp->tree_col = DLRBT_RED;
451  insert_check_1(tree, gp);
452  }
453  else {
454  /* we've got an unbalanced branch going down the grandparent to the parent,
455  * so need to perform some rotations to re-balance the tree
456  */
458  }
459  }
460 }
461 
462 /* W. 4+5) Perform rotation on sub-tree containing the 'new' node, then do any. */
464 {
466 
467  /* check that grandparent and node->parent exist
468  * (jut in case... really shouldn't happen on a good tree) */
469  if (node && node->parent && gp) {
470  /* a left rotation will switch the roles of node and its parent, assuming that
471  * the parent is the left child of the grandparent... otherwise, rotation direction
472  * should be swapped
473  */
474  if ((node == node->parent->right) && (node->parent == gp->left)) {
476  node = node->left;
477  }
478  else if ((node == node->parent->left) && (node->parent == gp->right)) {
480  node = node->right;
481  }
482 
483  /* fix old parent's color-tagging, and perform rotation on the old parent in the
484  * opposite direction if needed for the current situation
485  * NOTE: in the code above, node pointer is changed to point to the old parent
486  */
487  if (node) {
488  /* get 'new' grandparent (i.e. grandparent for old-parent (node)) */
489  gp = get_grandparent(node);
490 
491  /* modify the coloring of the grandparent and parent
492  * so that they still satisfy the constraints */
493  node->parent->tree_col = DLRBT_BLACK;
494  gp->tree_col = DLRBT_RED;
495 
496  /* if there are several nodes that all form a left chain, do a right rotation to correct
497  * this (or a rotation in the opposite direction if they all form a right chain) */
498  if ((node == node->parent->left) && (node->parent == gp->left)) {
499  rotate_right(tree, gp);
500  }
501  else { // if ((node == node->parent->right) && (node->parent == gp->right))
502  rotate_left(tree, gp);
503  }
504  }
505  }
506 }
507 
508 /* ----- */
509 
511 {
512  /* sanity checks */
513  if ((tree == NULL) || (node == NULL)) {
514  return;
515  }
516 
517  /* firstly, the node we just added should be red by default */
518  node->tree_col = DLRBT_RED;
519 
520  /* start from case 1, an trek through the tail-recursive insertion checks */
522 }
523 
524 /* ----- */
525 
527  DLRBT_Comparator_FP cmp_cb,
528  DLRBT_NAlloc_FP new_cb,
530  void *data)
531 {
532  DLRBT_Node *parNode, *node = NULL;
533  short new_node = 0;
534 
535  /* sanity checks */
536  if (tree == NULL) {
537  return NULL;
538  }
539 
540  /* TODO: if no comparator is supplied, try using the one supplied with the tree... */
541  if (cmp_cb == NULL) {
542  return NULL;
543  }
544  /* TODO: if no allocator is supplied, try using the one supplied with the tree... */
545  if (new_cb == NULL) {
546  return NULL;
547  }
548  /* TODO: if no updater is supplied, try using the one supplied with the tree... */
549 
550  /* try to find the nearest node to this one */
551  parNode = BLI_dlrbTree_search(tree, cmp_cb, data);
552 
553  /* add new node to the BST in the 'standard way' as appropriate
554  * NOTE: we do not support duplicates in our tree...
555  */
556  if (parNode) {
557  /* check how this new node compares with the existing ones
558  * NOTE: it is assumed that the values will be unit values only
559  */
560  switch (cmp_cb(parNode, data)) {
561  case -1: /* add new node as left child */
562  {
563  node = new_cb(data);
564  new_node = 1;
565 
566  parNode->left = node;
567  node->parent = parNode;
568  break;
569  }
570  case 1: /* add new node as right child */
571  {
572  node = new_cb(data);
573  new_node = 1;
574 
575  parNode->right = node;
576  node->parent = parNode;
577  break;
578  }
579  default: /* update the duplicate node as appropriate */
580  {
581  /* Return the updated node after calling the callback. */
582  node = parNode;
583  if (update_cb) {
584  update_cb(node, data);
585  }
586  break;
587  }
588  }
589  }
590  else {
591  /* no nodes in the tree yet... add a new node as the root */
592  node = new_cb(data);
593  new_node = 1;
594 
595  tree->root = node;
596  }
597 
598  /* if a new node was added, it should be tagged as red, and then balanced as appropriate */
599  if (new_node) {
600  /* tag this new node as being 'red' */
601  node->tree_col = DLRBT_RED;
602 
603  /* perform BST balancing steps:
604  * start from case 1, an trek through the tail-recursive insertion checks
605  */
607  }
608 
609  /* return the node added */
610  return node;
611 }
612 
613 /* *********************************************** */
614 /* Remove */
615 
616 /* TODO: this hasn't been coded yet, since this functionality was not needed by the author */
617 
618 /* *********************************************** */
DLRBT_Node *(* DLRBT_NAlloc_FP)(void *data)
Definition: BLI_dlrbTree.h:76
void(* DLRBT_NFree_FP)(void *node)
Definition: BLI_dlrbTree.h:90
void(* DLRBT_NUpdate_FP)(void *node, void *data)
Definition: BLI_dlrbTree.h:84
short(* DLRBT_Comparator_FP)(void *node, void *data)
Definition: BLI_dlrbTree.h:70
@ DLRBT_BLACK
Definition: BLI_dlrbTree.h:42
@ DLRBT_RED
Definition: BLI_dlrbTree.h:43
#define LISTBASE_FOREACH_MUTABLE(type, var, list)
Definition: BLI_listbase.h:354
BLI_INLINE void BLI_listbase_clear(struct ListBase *lb)
Definition: BLI_listbase.h:273
void void BLI_freelistN(struct ListBase *listbase) ATTR_NONNULL(1)
Definition: listbase.c:466
void BLI_addtail(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:80
void BLI_dlrbTree_init(DLRBT_Tree *tree)
Definition: DLRB_tree.c:22
DLRBT_Tree * BLI_dlrbTree_new(void)
Definition: DLRB_tree.c:16
static void rotate_left(DLRBT_Tree *tree, DLRBT_Node *root)
Definition: DLRB_tree.c:322
DLRBT_Node * BLI_dlrbTree_search_exact(const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
Definition: DLRB_tree.c:167
static void recursive_tree_free_nodes(DLRBT_Node *node, DLRBT_NFree_FP free_cb)
Definition: DLRB_tree.c:32
DLRBT_Node * BLI_dlrbTree_add(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, DLRBT_NAlloc_FP new_cb, DLRBT_NUpdate_FP update_cb, void *data)
Definition: DLRB_tree.c:526
DLRBT_Node * BLI_dlrbTree_search_prev(const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
Definition: DLRB_tree.c:214
static void insert_check_1(DLRBT_Tree *tree, DLRBT_Node *node)
Definition: DLRB_tree.c:414
void BLI_dlrbTree_linkedlist_sync(DLRBT_Tree *tree)
Definition: DLRB_tree.c:103
DLRBT_Node * BLI_dlrbTree_search(const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
Definition: DLRB_tree.c:120
static void rotate_right(DLRBT_Tree *tree, DLRBT_Node *root)
Definition: DLRB_tree.c:363
static DLRBT_Node * get_uncle(DLRBT_Node *node)
Definition: DLRB_tree.c:307
short BLI_dlrbTree_contains(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
Definition: DLRB_tree.c:274
void BLI_dlrbTree_free(DLRBT_Tree *tree, DLRBT_NFree_FP free_cb)
Definition: DLRB_tree.c:49
void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node)
Definition: DLRB_tree.c:510
static void insert_check_2(DLRBT_Tree *tree, DLRBT_Node *node)
Definition: DLRB_tree.c:428
DLRBT_Node * BLI_dlrbTree_search_next(const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
Definition: DLRB_tree.c:244
static void insert_check_3(DLRBT_Tree *tree, DLRBT_Node *node)
Definition: DLRB_tree.c:463
static void linkedlist_sync_add_node(DLRBT_Tree *tree, DLRBT_Node *node)
Definition: DLRB_tree.c:82
static DLRBT_Node * get_grandparent(DLRBT_Node *node)
Definition: DLRB_tree.c:284
static DLRBT_Node * get_sibling(DLRBT_Node *node)
Definition: DLRB_tree.c:293
Read Guarded memory(de)allocation.
OperationNode * node
void * tree
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
static void update_cb(PBVHNode *node, void *rebuild)
Definition: sculpt_undo.c:133
struct DLRBT_Node * parent
Definition: BLI_dlrbTree.h:34
struct DLRBT_Node * left
Definition: BLI_dlrbTree.h:33
struct DLRBT_Node * right
Definition: BLI_dlrbTree.h:33
char tree_col
Definition: BLI_dlrbTree.h:36