taskrambler  0.1.9
Web server and task management solution.
rbtree.c
Go to the documentation of this file.
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 
5 #define NVALUES 10
6 
7 enum rbColor {rbBlack=1, rbRed=2};
8 
9 
10 struct element
11 {
12  size_t size;
13  void * ptr;
14 
15  enum rbColor color;
16 
17  struct element * next;
18  struct element * last;
19 
20  struct element * parent;
21  struct element * left;
22  struct element * right;
23 };
24 
25 struct element *
27 {
28  struct element * element = malloc(size + sizeof(struct element));
29 
30  element->size = size;
31  element->ptr = element + sizeof(struct element);
32 
33  element->next = NULL;
34  element->last = NULL;
35 
36  element->color = rbRed;
37  element->parent = NULL;
38  element->left = NULL;
39  element->right = NULL;
40 
41  return element;
42 }
43 
44 /**
45  * find element in tree
46  */
47 struct element *
48 findElement(struct element * tree, size_t size)
49 {
50  struct element * fitting = NULL;
51 
52  while (NULL != tree) {
53  if (tree->size == size) {
54  fitting = tree;
55  break;
56  }
57 
58  if (size > tree->size) {
59  tree = tree->right;
60  } else {
61  fitting = tree;
62  tree = tree->left;
63  }
64  }
65 
66  return fitting;
67 }
68 
69 /*
70  * function to get specific elements needed for
71  * rb handling, grandparent, uncle and sibbling
72  */
73 struct element *
74 grandparent(struct element * node)
75 {
76  if (NULL != node && NULL != node->parent) {
77  return node->parent->parent;
78  }
79 
80  return NULL;
81 }
82 
83 struct element *
84 uncle(struct element * node)
85 {
86  struct element * gp = grandparent(node);
87 
88  if (NULL == gp) {
89  return NULL;
90  }
91 
92  if (node->parent == gp->left) {
93  return gp->right;
94  }
95 
96  return gp->left;
97 }
98 
99 struct element *
100 sibling(struct element * node)
101 {
102  if (NULL == node) {
103  return NULL;
104  }
105 
106  if (NULL == node->parent->left || node == node->parent->left) {
107  return node->parent->right;
108  } else {
109  return node->parent->left;
110  }
111 }
112 
113 /*
114  * tree modifications...needed for rb handling.
115  */
116 void
117 rotateLeft(struct element ** tree, struct element * node)
118 {
119  struct element * rightChild = node->right;
120  struct element * rcLeftSub = node->right->left;
121 
122  rightChild->left = node;
123  rightChild->parent = node->parent;
124  node->right = rcLeftSub;
125  if (NULL != rcLeftSub) {
126  rcLeftSub->parent = node;
127  }
128 
129  if (node->parent) {
130  if (node->parent->left == node) {
131  node->parent->left = rightChild;
132  } else {
133  node->parent->right = rightChild;
134  }
135  } else {
136  *tree = rightChild;
137  }
138 
139  node->parent = rightChild;
140 }
141 
142 void
143 rotateRight(struct element ** tree, struct element * node)
144 {
145  struct element * leftChild = node->left;
146  struct element * lcRightSub = node->left->right;
147 
148  leftChild->right = node;
149  leftChild->parent = node->parent;
150  node->left = lcRightSub;
151  if (NULL != lcRightSub) {
152  lcRightSub->parent = node;
153  }
154 
155  if (node->parent) {
156  if (node->parent->left == node) {
157  node->parent->left = leftChild;
158  } else {
159  node->parent->right = leftChild;
160  }
161  } else {
162  *tree = leftChild;
163  }
164 
165  node->parent = leftChild;
166 }
167 
168 void
170  struct element ** tree,
171  struct element * node1,
172  struct element * node2)
173 {
174  if (NULL != node1->parent) {
175  if (node1 == node1->parent->left) {
176  node1->parent->left = node2;
177  } else {
178  node1->parent->right = node2;
179  }
180  } else {
181  *tree = node2;
182  }
183 
184  if (NULL != node2) {
185  node2->parent = node1->parent;
186  }
187 }
188 
189 
190 /**
191  * insert element in tree
192  */
193 struct element *
194 insertElement(struct element ** tree, struct element * element)
195 {
196  struct element * node = *tree;
197  struct element * new_node = NULL;
198  struct element * u;
199  struct element * g;
200 
201  element->next = NULL;
202  element->last = NULL;
203 
204  element->color = rbRed;
205  element->parent = NULL;
206  element->left = NULL;
207  element->right = NULL;
208 
209  // if tree is empty it's simple... :)
210  if (NULL == node) {
211  *tree = node = new_node = element;
212  } else {
213  // normal binary tree add....
214  while (NULL != node) {
215  if (element->size < node->size) {
216  if (NULL == node->left) {
217  node->left = element;
218  node->left->parent = node;
219  new_node = node = node->left;
220  break;
221  } else {
222  node = node->left;
223  }
224  } else if (element->size > node->size) {
225  if (NULL == node->right) {
226  node->right = element;
227  node->right->parent = node;
228  new_node = node = node->right;
229  break;
230  } else {
231  node = node->right;
232  }
233  } else {
234  if (NULL == node->next) {
235  node->next = element;
236  node->last = element;
237  } else {
238  node->last->next = element;
239  node->last = element;
240  }
241  return node;
242  }
243  }
244  }
245 
246  if (NULL != new_node) {
247  /*
248  * handle reballancing rb style
249  */
250  while (1) {
251  // case 1
252  if (node->parent == NULL) {
253  node->color = rbBlack;
254  // we're done.... :)
255  break;
256  }
257 
258  // case 2
259  if (node->parent->color == rbBlack) {
260  // Tree is still valid ... wow, again we're done... :)
261  break;
262  }
263 
264  // case 3
265  u = uncle(node);
266  g = grandparent(node);
267 
268  if (u != NULL && u->color == rbRed) {
269  node->parent->color = rbBlack;
270  u->color = rbBlack;
271  g->color = rbRed;
272 
273  node = g;
274  continue;
275  }
276 
277  // case 4
278  if (node == node->parent->right && node->parent == g->left) {
279  rotateLeft(tree, node->parent);
280  node = node->left;
281  } else if (node == node->parent->left && node->parent == g->right) {
282 
283  rotateRight(tree, node->parent);
284  node = node->right;
285  }
286 
287  // case 5
288  g = grandparent(node);
289 
290  node->parent->color = rbBlack;
291  g->color = rbRed;
292 
293  if (node == node->parent->left) {
294  rotateRight(tree, g);
295  } else {
296  rotateLeft(tree, g);
297  }
298 
299  // we're done..
300  break;
301  }
302  }
303 
304  return new_node;
305 }
306 
307 /**
308  * delete element from tree
309  * here multiple functions are involved....
310  * =======================================================================
311  */
312 /**
313  * find minimum of the right subtree aka leftmost leaf of right subtree
314  * aka left in-order successor.
315  * We return the parent of the element in the out argument parent.
316  * This can be NULL wenn calling.
317  *
318  * 2: *successor = {size = 80, ptr = 0x603ae0, color = rbRed, parent = 0x603160,
319  * left = 0x0, right = 0x0}
320  * 1: *node = {size = 70, ptr = 0x603a60, color = rbBlack, parent = 0x603070,
321  * left = 0x6030e0, right = 0x6031e0}
322  *
323  */
324 struct element *
326 {
327  struct element * node = tree->right;
328 
329  while (NULL != node->left) {
330  node = node->left;
331  }
332 
333  return node;
334 }
335 
336 struct element * deleteOneChild(struct element **, struct element *);
337 
338 struct element *
339 deleteElement(struct element ** tree, struct element * element)
340 {
341  struct element * node = *tree;
342  struct element * del_node;
343  struct element * child;
344  struct element * s;
345 
346  // find the relevant node and it's parent
347  while (NULL != node) {
348 
349  if (element->size < node->size) {
350  node = node->left;
351  } else if (element->size > node->size) {
352  node = node->right;
353  } else {
354  if (NULL != node->next) {
355  if (NULL != node->parent) {
356  if (node == node->parent->left) {
357  node->parent->left = node->next;
358  } else {
359  node->parent->right = node->next;
360  }
361  } else {
362  *tree = node->next;
363  }
364 
365  if (NULL != node->left) {
366  node->left->parent = node->next;
367  }
368 
369  if (NULL != node->right) {
370  node->right->parent = node->next;
371  }
372 
373  node->next->last = node->last;
374  node->next->color = node->color;
375  node->next->parent = node->parent;
376  node->next->left = node->left;
377  node->next->right = node->right;
378 
379  return node;
380  }
381  break;
382  }
383  }
384 
385  // element not found
386  if (NULL == node) {
387  return node;
388  }
389 
390  del_node = node;
391 
392  // now our cases follows...the first one is the same as with
393  // simple binary search trees. Two non null children.
394 
395  // case 1: two children
396  if (NULL != node->left && NULL != node->right) {
397  struct element * successor = findInOrderSuccessor(node);
398 
399  enum rbColor tmpcolor = successor->color;
400  struct element * tmpparent = successor->parent;
401  struct element * tmpleft = successor->left;
402  struct element * tmpright = successor->right;
403 
404  replaceNode(tree, node, successor);
405 
406  successor->color = node->color;
407  successor->left = node->left;
408  successor->left->parent = successor;
409  // the right one might be successor...
410  if (node->right == successor) {
411  successor->right = node;
412  node->parent = successor;
413  } else {
414  successor->right = node->right;
415  node->right->parent = successor;
416  node->parent = tmpparent;
417  tmpparent->left = node;
418  }
419 
420  node->color = tmpcolor;
421  node->left = tmpleft;
422  node->right = tmpright;
423  }
424 
425  // Precondition: n has at most one non-null child.
426  child = (NULL == node->right) ? node->left : node->right;
427  replaceNode(tree, node, child);
428 
429  // delete one child case
430  // TODO this is overly complex as simply derived from the function...
431  // maybe this can be simplified. Maybe not...check.
432  if (node->color == rbBlack) {
433  if (NULL != child && child->color == rbRed) {
434  child->color = rbBlack;
435  // done despite modifying tree itself if neccessary..
436  return del_node;
437  } else {
438  if (NULL != child) {
439  node = child;
440  } else {
441  node->color = rbBlack;
442  node->left = NULL;
443  node->right = NULL;
444  }
445  }
446  } else {
447  return del_node;
448  }
449 
450  // delete and rb rebalance...
451  while(1) {
452  // case 1
453  if (NULL == node->parent) {
454  // done again
455  break;
456  }
457 
458  // case 2
459  s = sibling(node);
460 
461  if (NULL != s && s->color == rbRed) {
462  node->parent->color = rbRed;
463  s->color = rbBlack;
464 
465  /*
466  * detect which child we are...assumption
467  * if we are not parent->right and parent->right is not
468  * null we must be left, even if its set to NULL previously
469  */
470  if (NULL != node->parent->right && node != node->parent->right) {
471  rotateLeft(tree, node->parent);
472  } else {
473  rotateRight(tree, node->parent);
474  }
475  }
476 
477  s = sibling(node);
478  // case 3 / 4
479  if (NULL == s || ((s->color == rbBlack) &&
480  (NULL == s->left || s->left->color == rbBlack) &&
481  (NULL == s->right || s->right->color == rbBlack))) {
482 
483  if (NULL != s) {
484  s->color = rbRed;
485  }
486 
487  if (node->parent->color == rbBlack) {
488  // case 3
489  node = node->parent;
490  continue;
491  } else {
492  // case 4
493  node->parent->color = rbBlack;
494  // and done again...
495  break;
496  }
497  }
498 
499  // case 5
500  if (NULL != s && s->color == rbBlack) {
501  // this if statement is trivial,
502  // due to case 2 (even though case 2 changed the sibling to a
503  // sibling's child,
504  // the sibling's child can't be red, since no red parent can
505  // have a red child).
506  //
507  // the following statements just force the red to be on the
508  // left of the left of the parent,
509  // or right of the right, so case 6 will rotate correctly.
510  if ((node == node->parent->left) &&
511  (NULL == s->right || s->right->color == rbBlack) &&
512  (NULL != s->left && s->left->color == rbRed)) {
513 
514  // this last test is trivial too due to cases 2-4.
515  s->color = rbRed;
516  s->left->color = rbBlack;
517 
518  rotateRight(tree, s);
519  } else if ((node == node->parent->right) &&
520  (NULL == s->left || s->left->color == rbBlack) &&
521  (NULL != s->right && s->right->color == rbRed)) {
522  // this last test is trivial too due to cases 2-4.
523  s->color = rbRed;
524  s->right->color = rbBlack;
525 
526  rotateLeft(tree, s);
527  }
528  }
529 
530  s = sibling(node);
531  // case 6
532  if (NULL != s) {
533  s->color = node->parent->color;
534  }
535 
536  if (NULL != node && NULL != node->parent) {
537  node->parent->color = rbBlack;
538 
539  /*
540  * detect which child we are...assumption
541  * if we are not parent->right and parent->right is not
542  * null we must be left, even if its set to NULL previously
543  */
544  if (NULL != node->parent->right && node != node->parent->right) {
545  if (NULL != s->right) {
546  s->right->color = rbBlack;
547  }
548  rotateLeft(tree, node->parent);
549  } else {
550  if (NULL != s->left) {
551  s->left->color = rbBlack;
552  }
553  rotateRight(tree, node->parent);
554  }
555  }
556 
557  // done...
558  break;
559  }
560 
561  //deleteOneChild(tree, node);
562 
563  return del_node;
564 }
565 
566 
567 void
568 traverse(struct element * tree, void (*cb)(struct element *, int))
569 {
570  struct element * previous = tree;
571  struct element * node = tree;
572  int depth = 1;
573 
574  /*
575  * I think this has something like O(n+log(n)) on a ballanced
576  * tree because I have to traverse back the rightmost leaf to
577  * the root to get a break condition.
578  */
579  while (node) {
580  /*
581  * If we come from the right so nothing and go to our
582  * next parent.
583  */
584  if (previous == node->right) {
585  previous = node;
586  node = node->parent;
587  depth--;
588  continue;
589  }
590 
591  if ((NULL == node->left || previous == node->left)) {
592  /*
593  * If there are no more elements to the left or we
594  * came from the left, process data.
595  */
596  cb(node, depth);
597  previous = node;
598 
599  if (NULL != node->right) {
600  node = node->right;
601  depth++;
602  } else {
603  node = node->parent;
604  depth--;
605  }
606  } else {
607  /*
608  * if there are more elements to the left go there.
609  */
610  previous = node;
611  node = node->left;
612  depth++;
613  }
614  }
615 }
616 
617 void
618 post(struct element * tree, void (*cb)(struct element *, int))
619 {
620  struct element * previous = tree;
621  struct element * node = tree;
622  int depth = 1;
623 
624  /*
625  * I think this has something like O(n+log(n)) on a ballanced
626  * tree because I have to traverse back the rightmost leaf to
627  * the root to get a break condition.
628  */
629  while (node) {
630  /*
631  * If we come from the right so nothing and go to our
632  * next parent.
633  */
634  if ((NULL == node->left && NULL == node->right)
635  || previous == node->right) {
636 
637  struct element * parent = node->parent;
638 
639  cb(node, depth);
640 
641  previous = node;
642  node = parent;
643  depth--;
644  continue;
645  }
646 
647  if ((NULL == node->left || previous == node->left)) {
648  /*
649  * If there are no more elements to the left or we
650  * came from the left, process data.
651  */
652  previous = node;
653 
654  if (NULL != node->right) {
655  node = node->right;
656  depth++;
657  } else {
658  node = node->parent;
659  depth--;
660  }
661  } else {
662  /*
663  * if there are more elements to the left go there.
664  */
665  previous = node;
666  node = node->left;
667  depth++;
668  }
669  }
670 }
671 
672 void printElement(struct element * node, int depth)
673 {
674  int i;
675 
676  printf("%s %010zu:%p(%02d)",
677  (node->color==rbRed)?"R":"B",
678  node->size,
679  node->ptr,
680  depth);
681  for (i=0; i<depth; i++) printf("-");
682  puts("");
683 
684  node = node->next;
685  while (NULL != node) {
686  printf(" %s %010zu:%p(%02d)",
687  (node->color==rbRed)?"R":"B",
688  node->size,
689  node->ptr,
690  depth);
691  for (i=0; i<depth; i++) printf("-");
692  puts("");
693  node = node->next;
694  }
695 }
696 
697 void cleanup(struct element * node, int depth)
698 {
699  while (NULL != node) {
700  printf("free node: ");
701  printElement(node, 0);
702  struct element * next = node->next;
703  free(node);
704  node = next;
705  }
706 }
707 
708 /**
709  * =======================================================================
710  */
711 int
712 main(int argc, char * argv[])
713 {
714  struct element * root = NULL;
715  struct element * found = NULL;
716 
717  insertElement(&root, newElement(40));
718  insertElement(&root, newElement(50));
719  insertElement(&root, newElement(60));
720  insertElement(&root, newElement(70));
721  insertElement(&root, newElement(80));
722  insertElement(&root, newElement(45));
723  insertElement(&root, newElement(75));
724  insertElement(&root, newElement(85));
725  puts("traverse");
726  traverse(root, printElement);
727  puts("");
728 
729  insertElement(&root, newElement(70));
730  puts("traverse");
731  traverse(root, printElement);
732  puts("");
733 
734  found = findElement(root, 10);
735  if (NULL == found) {
736  printf("can't find segmenet of minimum size: %d\n", 10);
737  } else {
738  printElement(found, 0);
739  }
740  puts("");
741 
742  found = findElement(root, 64);
743  if (NULL == found) {
744  printf("can't find segmenet of minimum size: %d\n", 64);
745  } else {
746  printElement(found, 0);
747  }
748  puts("");
749 
750  found = findElement(root, 90);
751  if (NULL == found) {
752  printf("can't find segmenet of minimum size: %d\n", 90);
753  } else {
754  printElement(found, 0);
755  }
756  puts("");
757 
758  free(deleteElement(&root, findElement(root, 70)));
759  puts("traverse");
760  traverse(root, printElement);
761  puts("");
762 
763  insertElement(&root, newElement(80));
764  insertElement(&root, newElement(50));
765  insertElement(&root, newElement(80));
766 
767  puts("traverse");
768  traverse(root, printElement);
769  puts("");
770 
771  found = deleteElement(&root, findElement(root, 80));
772  printf("up to free: %p\n", found);
773  free(found);
774  puts("traverse");
775  traverse(root, printElement);
776  puts("");
777 
778  found = deleteElement(&root, findElement(root, 50));
779  printf("up to free: %p\n", found);
780  free(found);
781  puts("traverse");
782  traverse(root, printElement);
783  puts("");
784 
785  found = deleteElement(&root, findElement(root, 70));
786  printf("up to free: %p\n", found);
787  free(found);
788  puts("traverse");
789  traverse(root, printElement);
790  puts("");
791 
792 // post(root, cleanup);
793 //
794  return 0;
795 }
796 
797 // vim: set et ts=4 sw=4:
struct element * newElement(size_t size)
Definition: rbtree.c:26
void post(struct element *tree, void(*cb)(struct element *, int))
Definition: rbtree.c:618
int main(int argc, char *argv[])
Definition: rbtree.c:712
struct element * deleteOneChild(struct element **, struct element *)
struct element * right
Definition: binarytree.c:11
Definition: rbtree.c:7
void rotateRight(struct element **tree, struct element *node)
Definition: rbtree.c:143
struct element * grandparent(struct element *node)
Definition: rbtree.c:74
struct element * insertElement(struct element **tree, struct element *element)
Definition: rbtree.c:194
void traverse(struct element *tree, void(*cb)(struct element *, int))
Definition: rbtree.c:568
static void(* cb)(const void *)
Definition: each.c:27
struct element * left
Definition: binarytree.c:10
enum rbColor color
Definition: rbtree.c:15
Definition: rbtree.c:7
struct element * next
Definition: rbtree.c:17
struct element * findInOrderSuccessor(struct element *tree)
Definition: rbtree.c:325
void cleanup(struct element *node, int depth)
Definition: rbtree.c:697
struct element * deleteElement(struct element **tree, struct element *element)
Definition: rbtree.c:339
void replaceNode(struct element **tree, struct element *node1, struct element *node2)
Definition: rbtree.c:169
void rotateLeft(struct element **tree, struct element *node)
Definition: rbtree.c:117
struct element * parent
Definition: binarytree.c:9
rbColor
Definition: tree.h:115
struct element * last
Definition: rbtree.c:18
static size_t size
struct element * sibling(struct element *node)
Definition: rbtree.c:100
struct element * uncle(struct element *node)
Definition: rbtree.c:84
struct element * findElement(struct element *tree, size_t size)
Definition: rbtree.c:48
void printElement(struct element *node, int depth)
Definition: rbtree.c:672
size_t size
Definition: rbtree.c:12
void * ptr
Definition: rbtree.c:13