Leptonica  1.83.1
Image processing and image analysis suite
rbtree.c
Go to the documentation of this file.
1 /*====================================================================*
2  - Copyright (C) 2001 Leptonica. All rights reserved.
3  -
4  - Redistribution and use in source and binary forms, with or without
5  - modification, are permitted provided that the following conditions
6  - are met:
7  - 1. Redistributions of source code must retain the above copyright
8  - notice, this list of conditions and the following disclaimer.
9  - 2. Redistributions in binary form must reproduce the above
10  - copyright notice, this list of conditions and the following
11  - disclaimer in the documentation and/or other materials
12  - provided with the distribution.
13  -
14  - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15  - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16  - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17  - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18  - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23  - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24  - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  *====================================================================*/
26 
27 /*
28  * Modified from the excellent code here:
29  * http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567
30  * which has been placed in the public domain under the Creative Commons
31  * CC0 1.0 waiver (http://creativecommons.org/publicdomain/zero/1.0/).
32  */
33 
74 #ifdef HAVE_CONFIG_H
75 #include <config_auto.h>
76 #endif /* HAVE_CONFIG_H */
77 
78 #include "allheaders.h"
79 
80  /* The node color enum is only needed in the rbtree implementation */
81 enum {
82  L_RED_NODE = 1,
83  L_BLACK_NODE = 2
84 };
85 
86  /* This makes it simpler to read the code */
87 typedef L_RBTREE_NODE node;
88 
89  /* Lots of static helper functions */
90 static void destroy_helper(node *n);
91 static void count_helper(node *n, l_int32 *pcount);
92 static void print_tree_helper(FILE *fp, node *n, l_int32 keytype,
93  l_int32 indent);
94 
95 static l_int32 compareKeys(l_int32 keytype, RB_TYPE left, RB_TYPE right);
96 
97 static node *grandparent(node *n);
98 static node *sibling(node *n);
99 static node *uncle(node *n);
100 static l_int32 node_color(node *n);
101 static node *new_node(RB_TYPE key, RB_TYPE value, l_int32 node_color,
102  node *left, node *right);
103 static node *lookup_node(L_RBTREE *t, RB_TYPE key);
104 static void rotate_left(L_RBTREE *t, node *n);
105 static void rotate_right(L_RBTREE *t, node *n);
106 static void replace_node(L_RBTREE *t, node *oldn, node *newn);
107 static void insert_case1(L_RBTREE *t, node *n);
108 static void insert_case2(L_RBTREE *t, node *n);
109 static void insert_case3(L_RBTREE *t, node *n);
110 static void insert_case4(L_RBTREE *t, node *n);
111 static void insert_case5(L_RBTREE *t, node *n);
112 static node *maximum_node(node *root);
113 static void delete_case1(L_RBTREE *t, node *n);
114 static void delete_case2(L_RBTREE *t, node *n);
115 static void delete_case3(L_RBTREE *t, node *n);
116 static void delete_case4(L_RBTREE *t, node *n);
117 static void delete_case5(L_RBTREE *t, node *n);
118 static void delete_case6(L_RBTREE *t, node *n);
119 static void verify_properties(L_RBTREE *t);
120 
121 #ifndef NO_CONSOLE_IO
122 #define VERIFY_RBTREE 0 /* only for debugging */
123 #endif /* ~NO_CONSOLE_IO */
124 
125 /* ------------------------------------------------------------- *
126  * Interface to Red-black Tree *
127  * ------------------------------------------------------------- */
134 L_RBTREE *
135 l_rbtreeCreate(l_int32 keytype)
136 {
137 L_RBTREE *t;
138 
139  if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
140  keytype != L_FLOAT_TYPE && keytype)
141  return (L_RBTREE *)ERROR_PTR("invalid keytype", __func__, NULL);
142 
143  t = (L_RBTREE *)LEPT_CALLOC(1, sizeof(L_RBTREE));
144  t->keytype = keytype;
145  verify_properties(t);
146  return t;
147 }
148 
156 RB_TYPE *
158  RB_TYPE key)
159 {
160 node *n;
161 
162  if (!t)
163  return (RB_TYPE *)ERROR_PTR("tree is null\n", __func__, NULL);
164 
165  n = lookup_node(t, key);
166  return n == NULL ? NULL : &n->value;
167 }
168 
183 void
185  RB_TYPE key,
186  RB_TYPE value)
187 {
188 node *n, *inserted_node;
189 
190  if (!t) {
191  L_ERROR("tree is null\n", __func__);
192  return;
193  }
194 
195  inserted_node = new_node(key, value, L_RED_NODE, NULL, NULL);
196  if (t->root == NULL) {
197  t->root = inserted_node;
198  } else {
199  n = t->root;
200  while (1) {
201  int comp_result = compareKeys(t->keytype, key, n->key);
202  if (comp_result == 0) {
203  n->value = value;
204  LEPT_FREE(inserted_node);
205  return;
206  } else if (comp_result < 0) {
207  if (n->left == NULL) {
208  n->left = inserted_node;
209  break;
210  } else {
211  n = n->left;
212  }
213  } else { /* comp_result > 0 */
214  if (n->right == NULL) {
215  n->right = inserted_node;
216  break;
217  } else {
218  n = n->right;
219  }
220  }
221  }
222  inserted_node->parent = n;
223  }
224  insert_case1(t, inserted_node);
225  verify_properties(t);
226 }
227 
235 void
237  RB_TYPE key)
238 {
239 node *n, *child;
240 
241  if (!t) {
242  L_ERROR("tree is null\n", __func__);
243  return;
244  }
245 
246  n = lookup_node(t, key);
247  if (n == NULL) return; /* Key not found, do nothing */
248  if (n->left != NULL && n->right != NULL) {
249  /* Copy key/value from predecessor and then delete it instead */
250  node *pred = maximum_node(n->left);
251  n->key = pred->key;
252  n->value = pred->value;
253  n = pred;
254  }
255 
256  /* n->left == NULL || n->right == NULL */
257  child = n->right == NULL ? n->left : n->right;
258  if (node_color(n) == L_BLACK_NODE) {
259  n->color = node_color(child);
260  delete_case1(t, n);
261  }
262  replace_node(t, n, child);
263  if (n->parent == NULL && child != NULL) /* root should be black */
264  child->color = L_BLACK_NODE;
265  LEPT_FREE(n);
266 
267  verify_properties(t);
268 }
269 
281 void
283 {
284 node *n;
285 
286  if (!pt) return;
287  if (*pt == NULL) return;
288  n = (*pt)->root;
289  destroy_helper(n);
290  LEPT_FREE(*pt);
291  *pt = NULL;
292 }
293 
294  /* postorder DFS */
295 static void
296 destroy_helper(node *n)
297 {
298  if (!n) return;
299  destroy_helper(n->left);
300  destroy_helper(n->right);
301  LEPT_FREE(n);
302 }
303 
317 {
318 node *n;
319 
320  if (!t)
321  return (L_RBTREE_NODE *)ERROR_PTR("tree is null", __func__, NULL);
322  if (t->root == NULL) {
323  L_INFO("tree is empty\n", __func__);
324  return NULL;
325  }
326 
327  /* Just go down the left side as far as possible */
328  n = t->root;
329  while (n && n->left)
330  n = n->left;
331  return n;
332 }
333 
350 {
351  if (!n)
352  return (L_RBTREE_NODE *)ERROR_PTR("n not defined", __func__, NULL);
353 
354  /* If there is a right child, go to it, and then go left all the
355  * way to the end. Otherwise go up to the parent; continue upward
356  * as long as you're on the right branch, but stop at the parent
357  * when you hit it from the left branch. */
358  if (n->right) {
359  n = n->right;
360  while (n->left)
361  n = n->left;
362  return n;
363  } else {
364  while (n->parent && n->parent->right == n)
365  n = n->parent;
366  return n->parent;
367  }
368 }
369 
383 {
384 node *n;
385 
386  if (!t)
387  return (L_RBTREE_NODE *)ERROR_PTR("tree is null", __func__, NULL);
388  if (t->root == NULL) {
389  L_INFO("tree is empty\n", __func__);
390  return NULL;
391  }
392 
393  /* Just go down the right side as far as possible */
394  n = t->root;
395  while (n && n->right)
396  n = n->right;
397  return n;
398 }
399 
416 {
417  if (!n)
418  return (L_RBTREE_NODE *)ERROR_PTR("n not defined", __func__, NULL);
419 
420  /* If there is a left child, go to it, and then go right all the
421  * way to the end. Otherwise go up to the parent; continue upward
422  * as long as you're on the left branch, but stop at the parent
423  * when you hit it from the right branch. */
424  if (n->left) {
425  n = n->left;
426  while (n->right)
427  n = n->right;
428  return n;
429  } else {
430  while (n->parent && n->parent->left == n)
431  n = n->parent;
432  return n->parent;
433  }
434 }
435 
442 l_int32
444 {
445 l_int32 count = 0;
446 node *n;
447 
448  if (!t) return 0;
449  n = t->root;
450  count_helper(n, &count);
451  return count;
452 }
453 
454  /* preorder DFS */
455 static void
456 count_helper(node *n, l_int32 *pcount)
457 {
458  if (n)
459  (*pcount)++;
460  else
461  return;
462 
463  count_helper(n->left, pcount);
464  count_helper(n->right, pcount);
465 }
466 
467 
475 void
476 l_rbtreePrint(FILE *fp,
477  L_RBTREE *t)
478 {
479  if (!fp) {
480  L_ERROR("stream not defined\n", __func__);
481  return;
482  }
483  if (!t) {
484  L_ERROR("tree not defined\n", __func__);
485  return;
486  }
487 
488  print_tree_helper(fp, t->root, t->keytype, 0);
489  fprintf(fp, "\n");
490 }
491 
492 #define INDENT_STEP 4
493 
494 static void
495 print_tree_helper(FILE *fp,
496  node *n,
497  l_int32 keytype,
498  l_int32 indent)
499 {
500 l_int32 i;
501 
502  if (n == NULL) {
503  fprintf(fp, "<empty tree>");
504  return;
505  }
506  if (n->right != NULL) {
507  print_tree_helper(fp, n->right, keytype, indent + INDENT_STEP);
508  }
509  for (i = 0; i < indent; i++)
510  fprintf(fp, " ");
511  if (n->color == L_BLACK_NODE) {
512  if (keytype == L_INT_TYPE)
513  fprintf(fp, "%lld\n", n->key.itype);
514  else if (keytype == L_UINT_TYPE)
515  fprintf(fp, "%llx\n", n->key.utype);
516  else if (keytype == L_FLOAT_TYPE)
517  fprintf(fp, "%f\n", n->key.ftype);
518  } else {
519  if (keytype == L_INT_TYPE)
520  fprintf(fp, "<%lld>\n", n->key.itype);
521  else if (keytype == L_UINT_TYPE)
522  fprintf(fp, "<%llx>\n", n->key.utype);
523  else if (keytype == L_FLOAT_TYPE)
524  fprintf(fp, "<%f>\n", n->key.ftype);
525  }
526  if (n->left != NULL) {
527  print_tree_helper(fp, n->left, keytype, indent + INDENT_STEP);
528  }
529 }
530 
531 
532 /* ------------------------------------------------------------- *
533  * Static key comparison function *
534  * ------------------------------------------------------------- */
535 static l_int32
536 compareKeys(l_int32 keytype,
537  RB_TYPE left,
538  RB_TYPE right)
539 {
540  if (keytype == L_INT_TYPE) {
541  if (left.itype < right.itype)
542  return -1;
543  else if (left.itype > right.itype)
544  return 1;
545  else { /* equality */
546  return 0;
547  }
548  } else if (keytype == L_UINT_TYPE) {
549  if (left.utype < right.utype)
550  return -1;
551  else if (left.utype > right.utype)
552  return 1;
553  else { /* equality */
554  return 0;
555  }
556  } else if (keytype == L_FLOAT_TYPE) {
557  if (left.ftype < right.ftype)
558  return -1;
559  else if (left.ftype > right.ftype)
560  return 1;
561  else { /* equality */
562  return 0;
563  }
564  } else {
565  L_ERROR("unknown keytype %d\n", __func__, keytype);
566  return 0;
567  }
568 }
569 
570 
571 /* ------------------------------------------------------------- *
572  * Static red-black tree helpers *
573  * ------------------------------------------------------------- */
574 static node *grandparent(node *n) {
575  if (!n || !n->parent || !n->parent->parent) {
576  L_ERROR("root and child of root have no grandparent\n", "grandparent");
577  return NULL;
578  }
579  return n->parent->parent;
580 }
581 
582 static node *sibling(node *n) {
583  if (!n || !n->parent) {
584  L_ERROR("root has no sibling\n", "sibling");
585  return NULL;
586  }
587  if (n == n->parent->left)
588  return n->parent->right;
589  else
590  return n->parent->left;
591 }
592 
593 static node *uncle(node *n) {
594  if (!n || !n->parent || !n->parent->parent) {
595  L_ERROR("root and child of root have no uncle\n", "uncle");
596  return NULL;
597  }
598  return sibling(n->parent);
599 }
600 
601 static l_int32 node_color(node *n) {
602  return n == NULL ? L_BLACK_NODE : n->color;
603 }
604 
605 
606 static node *new_node(RB_TYPE key, RB_TYPE value, l_int32 node_color,
607  node *left, node *right) {
608  node *result = (node *)LEPT_CALLOC(1, sizeof(node));
609  result->key = key;
610  result->value = value;
611  result->color = node_color;
612  result->left = left;
613  result->right = right;
614  if (left != NULL) left->parent = result;
615  if (right != NULL) right->parent = result;
616  result->parent = NULL;
617  return result;
618 }
619 
620 static node *lookup_node(L_RBTREE *t, RB_TYPE key) {
621  node *n = t->root;
622  while (n != NULL) {
623  int comp_result = compareKeys(t->keytype, key, n->key);
624  if (comp_result == 0) {
625  return n;
626  } else if (comp_result < 0) {
627  n = n->left;
628  } else { /* comp_result > 0 */
629  n = n->right;
630  }
631  }
632  return n;
633 }
634 
635 static void rotate_left(L_RBTREE *t, node *n) {
636  node *r = n->right;
637  replace_node(t, n, r);
638  n->right = r->left;
639  if (r->left != NULL) {
640  r->left->parent = n;
641  }
642  r->left = n;
643  n->parent = r;
644 }
645 
646 static void rotate_right(L_RBTREE *t, node *n) {
647  node *L = n->left;
648  replace_node(t, n, L);
649  n->left = L->right;
650  if (L->right != NULL) {
651  L->right->parent = n;
652  }
653  L->right = n;
654  n->parent = L;
655 }
656 
657 static void replace_node(L_RBTREE *t, node *oldn, node *newn) {
658  if (oldn->parent == NULL) {
659  t->root = newn;
660  } else {
661  if (oldn == oldn->parent->left)
662  oldn->parent->left = newn;
663  else
664  oldn->parent->right = newn;
665  }
666  if (newn != NULL) {
667  newn->parent = oldn->parent;
668  }
669 }
670 
671 static void insert_case1(L_RBTREE *t, node *n) {
672  if (n->parent == NULL)
673  n->color = L_BLACK_NODE;
674  else
675  insert_case2(t, n);
676 }
677 
678 static void insert_case2(L_RBTREE *t, node *n) {
679  if (node_color(n->parent) == L_BLACK_NODE)
680  return; /* Tree is still valid */
681  else
682  insert_case3(t, n);
683 }
684 
685 static void insert_case3(L_RBTREE *t, node *n) {
686  if (node_color(uncle(n)) == L_RED_NODE) {
687  n->parent->color = L_BLACK_NODE;
688  uncle(n)->color = L_BLACK_NODE;
689  grandparent(n)->color = L_RED_NODE;
690  insert_case1(t, grandparent(n));
691  } else {
692  insert_case4(t, n);
693  }
694 }
695 
696 static void insert_case4(L_RBTREE *t, node *n) {
697  if (n == n->parent->right && n->parent == grandparent(n)->left) {
698  rotate_left(t, n->parent);
699  n = n->left;
700  } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
701  rotate_right(t, n->parent);
702  n = n->right;
703  }
704  insert_case5(t, n);
705 }
706 
707 static void insert_case5(L_RBTREE *t, node *n) {
708  n->parent->color = L_BLACK_NODE;
709  grandparent(n)->color = L_RED_NODE;
710  if (n == n->parent->left && n->parent == grandparent(n)->left) {
711  rotate_right(t, grandparent(n));
712  } else if (n == n->parent->right && n->parent == grandparent(n)->right) {
713  rotate_left(t, grandparent(n));
714  } else {
715  L_ERROR("identity confusion\n", "insert_case5");
716  }
717 }
718 
719 static node *maximum_node(node *n) {
720  if (!n) {
721  L_ERROR("n not defined\n", "maximum_node");
722  return NULL;
723  }
724  while (n->right != NULL) {
725  n = n->right;
726  }
727  return n;
728 }
729 
730 static void delete_case1(L_RBTREE *t, node *n) {
731  if (n->parent == NULL)
732  return;
733  else
734  delete_case2(t, n);
735 }
736 
737 static void delete_case2(L_RBTREE *t, node *n) {
738  if (node_color(sibling(n)) == L_RED_NODE) {
739  n->parent->color = L_RED_NODE;
740  sibling(n)->color = L_BLACK_NODE;
741  if (n == n->parent->left)
742  rotate_left(t, n->parent);
743  else
744  rotate_right(t, n->parent);
745  }
746  delete_case3(t, n);
747 }
748 
749 static void delete_case3(L_RBTREE *t, node *n) {
750  if (node_color(n->parent) == L_BLACK_NODE &&
751  node_color(sibling(n)) == L_BLACK_NODE &&
752  node_color(sibling(n)->left) == L_BLACK_NODE &&
753  node_color(sibling(n)->right) == L_BLACK_NODE) {
754  sibling(n)->color = L_RED_NODE;
755  delete_case1(t, n->parent);
756  } else {
757  delete_case4(t, n);
758  }
759 }
760 
761 static void delete_case4(L_RBTREE *t, node *n) {
762  if (node_color(n->parent) == L_RED_NODE &&
763  node_color(sibling(n)) == L_BLACK_NODE &&
764  node_color(sibling(n)->left) == L_BLACK_NODE &&
765  node_color(sibling(n)->right) == L_BLACK_NODE) {
766  sibling(n)->color = L_RED_NODE;
767  n->parent->color = L_BLACK_NODE;
768  } else {
769  delete_case5(t, n);
770  }
771 }
772 
773 static void delete_case5(L_RBTREE *t, node *n) {
774  if (n == n->parent->left &&
775  node_color(sibling(n)) == L_BLACK_NODE &&
776  node_color(sibling(n)->left) == L_RED_NODE &&
777  node_color(sibling(n)->right) == L_BLACK_NODE) {
778  sibling(n)->color = L_RED_NODE;
779  sibling(n)->left->color = L_BLACK_NODE;
780  rotate_right(t, sibling(n));
781  } else if (n == n->parent->right &&
782  node_color(sibling(n)) == L_BLACK_NODE &&
783  node_color(sibling(n)->right) == L_RED_NODE &&
784  node_color(sibling(n)->left) == L_BLACK_NODE) {
785  sibling(n)->color = L_RED_NODE;
786  sibling(n)->right->color = L_BLACK_NODE;
787  rotate_left(t, sibling(n));
788  }
789  delete_case6(t, n);
790 }
791 
792 static void delete_case6(L_RBTREE *t, node *n) {
793  sibling(n)->color = node_color(n->parent);
794  n->parent->color = L_BLACK_NODE;
795  if (n == n->parent->left) {
796  if (node_color(sibling(n)->right) != L_RED_NODE) {
797  L_ERROR("right sibling is not RED", "delete_case6");
798  return;
799  }
800  sibling(n)->right->color = L_BLACK_NODE;
801  rotate_left(t, n->parent);
802  } else {
803  if (node_color(sibling(n)->left) != L_RED_NODE) {
804  L_ERROR("left sibling is not RED", "delete_case6");
805  return;
806  }
807  sibling(n)->left->color = L_BLACK_NODE;
808  rotate_right(t, n->parent);
809  }
810 }
811 
812 
813 /* ------------------------------------------------------------- *
814  * Debugging: verify if tree is valid *
815  * ------------------------------------------------------------- */
816 #if VERIFY_RBTREE
817 static void verify_property_1(node *root);
818 static void verify_property_2(node *root);
819 static void verify_property_4(node *root);
820 static void verify_property_5(node *root);
821 static void verify_property_5_helper(node *n, int black_count,
822  int* black_count_path);
823 #endif
824 
825 static void verify_properties(L_RBTREE *t) {
826 #if VERIFY_RBTREE
827  verify_property_1(t->root);
828  verify_property_2(t->root);
829  /* Property 3 is implicit */
830  verify_property_4(t->root);
831  verify_property_5(t->root);
832 #endif
833 }
834 
835 #if VERIFY_RBTREE
836 static void verify_property_1(node *n) {
837  if (node_color(n) != L_RED_NODE && node_color(n) != L_BLACK_NODE) {
838  L_ERROR("color neither RED nor BLACK\n", "verify_property_1");
839  return;
840  }
841  if (n == NULL) return;
842  verify_property_1(n->left);
843  verify_property_1(n->right);
844 }
845 
846 static void verify_property_2(node *root) {
847  if (node_color(root) != L_BLACK_NODE)
848  L_ERROR("root is not black!\n", "verify_property_2");
849 }
850 
851 static void verify_property_4(node *n) {
852  if (node_color(n) == L_RED_NODE) {
853  if (node_color(n->left) != L_BLACK_NODE ||
854  node_color(n->right) != L_BLACK_NODE ||
855  node_color(n->parent) != L_BLACK_NODE) {
856  L_ERROR("children & parent not all BLACK", "verify_property_4");
857  return;
858  }
859  }
860  if (n == NULL) return;
861  verify_property_4(n->left);
862  verify_property_4(n->right);
863 }
864 
865 static void verify_property_5(node *root) {
866  int black_count_path = -1;
867  verify_property_5_helper(root, 0, &black_count_path);
868 }
869 
870 static void verify_property_5_helper(node *n, int black_count,
871  int* path_black_count) {
872  if (node_color(n) == L_BLACK_NODE) {
873  black_count++;
874  }
875  if (n == NULL) {
876  if (*path_black_count == -1) {
877  *path_black_count = black_count;
878  } else if (*path_black_count != black_count) {
879  L_ERROR("incorrect black count", "verify_property_5_helper");
880  }
881  return;
882  }
883  verify_property_5_helper(n->left, black_count, path_black_count);
884  verify_property_5_helper(n->right, black_count, path_black_count);
885 }
886 #endif
void l_rbtreeDelete(L_RBTREE *t, RB_TYPE key)
l_rbtreeDelete()
Definition: rbtree.c:236
void l_rbtreePrint(FILE *fp, L_RBTREE *t)
l_rbtreePrint()
Definition: rbtree.c:476
L_RBTREE_NODE * l_rbtreeGetLast(L_RBTREE *t)
l_rbtreeGetLast()
Definition: rbtree.c:382
RB_TYPE * l_rbtreeLookup(L_RBTREE *t, RB_TYPE key)
l_rbtreeLookup()
Definition: rbtree.c:157
L_RBTREE_NODE * l_rbtreeGetPrev(L_RBTREE_NODE *n)
l_rbtreeGetPrev()
Definition: rbtree.c:415
L_RBTREE * l_rbtreeCreate(l_int32 keytype)
l_rbtreeCreate()
Definition: rbtree.c:135
L_RBTREE_NODE * l_rbtreeGetNext(L_RBTREE_NODE *n)
l_rbtreeGetNext()
Definition: rbtree.c:349
void l_rbtreeDestroy(L_RBTREE **pt)
l_rbtreeDestroy()
Definition: rbtree.c:282
L_RBTREE_NODE * l_rbtreeGetFirst(L_RBTREE *t)
l_rbtreeGetFirst()
Definition: rbtree.c:316
l_int32 l_rbtreeGetCount(L_RBTREE *t)
l_rbtreeGetCount()
Definition: rbtree.c:443
void l_rbtreeInsert(L_RBTREE *t, RB_TYPE key, RB_TYPE value)
l_rbtreeInsert()
Definition: rbtree.c:184
Definition: rbtree.h:62