Leptonica  1.82.0
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  PROCNAME("l_rbtreeCreate");
140 
141  if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
142  keytype != L_FLOAT_TYPE && keytype)
143  return (L_RBTREE *)ERROR_PTR("invalid keytype", procName, NULL);
144 
145  t = (L_RBTREE *)LEPT_CALLOC(1, sizeof(L_RBTREE));
146  t->keytype = keytype;
147  verify_properties(t);
148  return t;
149 }
150 
158 RB_TYPE *
160  RB_TYPE key)
161 {
162 node *n;
163 
164  PROCNAME("l_rbtreeLookup");
165 
166  if (!t)
167  return (RB_TYPE *)ERROR_PTR("tree is null\n", procName, NULL);
168 
169  n = lookup_node(t, key);
170  return n == NULL ? NULL : &n->value;
171 }
172 
187 void
189  RB_TYPE key,
190  RB_TYPE value)
191 {
192 node *n, *inserted_node;
193 
194  PROCNAME("l_rbtreeInsert");
195 
196  if (!t) {
197  L_ERROR("tree is null\n", procName);
198  return;
199  }
200 
201  inserted_node = new_node(key, value, L_RED_NODE, NULL, NULL);
202  if (t->root == NULL) {
203  t->root = inserted_node;
204  } else {
205  n = t->root;
206  while (1) {
207  int comp_result = compareKeys(t->keytype, key, n->key);
208  if (comp_result == 0) {
209  n->value = value;
210  LEPT_FREE(inserted_node);
211  return;
212  } else if (comp_result < 0) {
213  if (n->left == NULL) {
214  n->left = inserted_node;
215  break;
216  } else {
217  n = n->left;
218  }
219  } else { /* comp_result > 0 */
220  if (n->right == NULL) {
221  n->right = inserted_node;
222  break;
223  } else {
224  n = n->right;
225  }
226  }
227  }
228  inserted_node->parent = n;
229  }
230  insert_case1(t, inserted_node);
231  verify_properties(t);
232 }
233 
241 void
243  RB_TYPE key)
244 {
245 node *n, *child;
246 
247  PROCNAME("l_rbtreeDelete");
248 
249  if (!t) {
250  L_ERROR("tree is null\n", procName);
251  return;
252  }
253 
254  n = lookup_node(t, key);
255  if (n == NULL) return; /* Key not found, do nothing */
256  if (n->left != NULL && n->right != NULL) {
257  /* Copy key/value from predecessor and then delete it instead */
258  node *pred = maximum_node(n->left);
259  n->key = pred->key;
260  n->value = pred->value;
261  n = pred;
262  }
263 
264  /* n->left == NULL || n->right == NULL */
265  child = n->right == NULL ? n->left : n->right;
266  if (node_color(n) == L_BLACK_NODE) {
267  n->color = node_color(child);
268  delete_case1(t, n);
269  }
270  replace_node(t, n, child);
271  if (n->parent == NULL && child != NULL) /* root should be black */
272  child->color = L_BLACK_NODE;
273  LEPT_FREE(n);
274 
275  verify_properties(t);
276 }
277 
289 void
291 {
292 node *n;
293 
294  if (!pt) return;
295  if (*pt == NULL) return;
296  n = (*pt)->root;
297  destroy_helper(n);
298  LEPT_FREE(*pt);
299  *pt = NULL;
300 }
301 
302  /* postorder DFS */
303 static void
304 destroy_helper(node *n)
305 {
306  if (!n) return;
307  destroy_helper(n->left);
308  destroy_helper(n->right);
309  LEPT_FREE(n);
310 }
311 
325 {
326 node *n;
327 
328  PROCNAME("l_rbtreeGetFirst");
329 
330  if (!t)
331  return (L_RBTREE_NODE *)ERROR_PTR("tree is null", procName, NULL);
332  if (t->root == NULL) {
333  L_INFO("tree is empty\n", procName);
334  return NULL;
335  }
336 
337  /* Just go down the left side as far as possible */
338  n = t->root;
339  while (n && n->left)
340  n = n->left;
341  return n;
342 }
343 
360 {
361  PROCNAME("l_rbtreeGetNext");
362 
363  if (!n)
364  return (L_RBTREE_NODE *)ERROR_PTR("n not defined", procName, NULL);
365 
366  /* If there is a right child, go to it, and then go left all the
367  * way to the end. Otherwise go up to the parent; continue upward
368  * as long as you're on the right branch, but stop at the parent
369  * when you hit it from the left branch. */
370  if (n->right) {
371  n = n->right;
372  while (n->left)
373  n = n->left;
374  return n;
375  } else {
376  while (n->parent && n->parent->right == n)
377  n = n->parent;
378  return n->parent;
379  }
380 }
381 
395 {
396 node *n;
397 
398  PROCNAME("l_rbtreeGetLast");
399 
400  if (!t)
401  return (L_RBTREE_NODE *)ERROR_PTR("tree is null", procName, NULL);
402  if (t->root == NULL) {
403  L_INFO("tree is empty\n", procName);
404  return NULL;
405  }
406 
407  /* Just go down the right side as far as possible */
408  n = t->root;
409  while (n && n->right)
410  n = n->right;
411  return n;
412 }
413 
430 {
431  PROCNAME("l_rbtreeGetPrev");
432 
433  if (!n)
434  return (L_RBTREE_NODE *)ERROR_PTR("n not defined", procName, NULL);
435 
436  /* If there is a left child, go to it, and then go right all the
437  * way to the end. Otherwise go up to the parent; continue upward
438  * as long as you're on the left branch, but stop at the parent
439  * when you hit it from the right branch. */
440  if (n->left) {
441  n = n->left;
442  while (n->right)
443  n = n->right;
444  return n;
445  } else {
446  while (n->parent && n->parent->left == n)
447  n = n->parent;
448  return n->parent;
449  }
450 }
451 
458 l_int32
460 {
461 l_int32 count = 0;
462 node *n;
463 
464  if (!t) return 0;
465  n = t->root;
466  count_helper(n, &count);
467  return count;
468 }
469 
470  /* preorder DFS */
471 static void
472 count_helper(node *n, l_int32 *pcount)
473 {
474  if (n)
475  (*pcount)++;
476  else
477  return;
478 
479  count_helper(n->left, pcount);
480  count_helper(n->right, pcount);
481 }
482 
483 
491 void
492 l_rbtreePrint(FILE *fp,
493  L_RBTREE *t)
494 {
495  PROCNAME("l_rbtreePrint");
496  if (!fp) {
497  L_ERROR("stream not defined\n", procName);
498  return;
499  }
500  if (!t) {
501  L_ERROR("tree not defined\n", procName);
502  return;
503  }
504 
505  print_tree_helper(fp, t->root, t->keytype, 0);
506  fprintf(fp, "\n");
507 }
508 
509 #define INDENT_STEP 4
510 
511 static void
512 print_tree_helper(FILE *fp,
513  node *n,
514  l_int32 keytype,
515  l_int32 indent)
516 {
517 l_int32 i;
518 
519  if (n == NULL) {
520  fprintf(fp, "<empty tree>");
521  return;
522  }
523  if (n->right != NULL) {
524  print_tree_helper(fp, n->right, keytype, indent + INDENT_STEP);
525  }
526  for (i = 0; i < indent; i++)
527  fprintf(fp, " ");
528  if (n->color == L_BLACK_NODE) {
529  if (keytype == L_INT_TYPE)
530  fprintf(fp, "%lld\n", n->key.itype);
531  else if (keytype == L_UINT_TYPE)
532  fprintf(fp, "%llx\n", n->key.utype);
533  else if (keytype == L_FLOAT_TYPE)
534  fprintf(fp, "%f\n", n->key.ftype);
535  } else {
536  if (keytype == L_INT_TYPE)
537  fprintf(fp, "<%lld>\n", n->key.itype);
538  else if (keytype == L_UINT_TYPE)
539  fprintf(fp, "<%llx>\n", n->key.utype);
540  else if (keytype == L_FLOAT_TYPE)
541  fprintf(fp, "<%f>\n", n->key.ftype);
542  }
543  if (n->left != NULL) {
544  print_tree_helper(fp, n->left, keytype, indent + INDENT_STEP);
545  }
546 }
547 
548 
549 /* ------------------------------------------------------------- *
550  * Static key comparison function *
551  * ------------------------------------------------------------- */
552 static l_int32
553 compareKeys(l_int32 keytype,
554  RB_TYPE left,
555  RB_TYPE right)
556 {
557 static char procName[] = "compareKeys";
558 
559  if (keytype == L_INT_TYPE) {
560  if (left.itype < right.itype)
561  return -1;
562  else if (left.itype > right.itype)
563  return 1;
564  else { /* equality */
565  return 0;
566  }
567  } else if (keytype == L_UINT_TYPE) {
568  if (left.utype < right.utype)
569  return -1;
570  else if (left.utype > right.utype)
571  return 1;
572  else { /* equality */
573  return 0;
574  }
575  } else if (keytype == L_FLOAT_TYPE) {
576  if (left.ftype < right.ftype)
577  return -1;
578  else if (left.ftype > right.ftype)
579  return 1;
580  else { /* equality */
581  return 0;
582  }
583  } else {
584  L_ERROR("unknown keytype %d\n", procName, keytype);
585  return 0;
586  }
587 }
588 
589 
590 /* ------------------------------------------------------------- *
591  * Static red-black tree helpers *
592  * ------------------------------------------------------------- */
593 static node *grandparent(node *n) {
594  if (!n || !n->parent || !n->parent->parent) {
595  L_ERROR("root and child of root have no grandparent\n", "grandparent");
596  return NULL;
597  }
598  return n->parent->parent;
599 }
600 
601 static node *sibling(node *n) {
602  if (!n || !n->parent) {
603  L_ERROR("root has no sibling\n", "sibling");
604  return NULL;
605  }
606  if (n == n->parent->left)
607  return n->parent->right;
608  else
609  return n->parent->left;
610 }
611 
612 static node *uncle(node *n) {
613  if (!n || !n->parent || !n->parent->parent) {
614  L_ERROR("root and child of root have no uncle\n", "uncle");
615  return NULL;
616  }
617  return sibling(n->parent);
618 }
619 
620 static l_int32 node_color(node *n) {
621  return n == NULL ? L_BLACK_NODE : n->color;
622 }
623 
624 
625 static node *new_node(RB_TYPE key, RB_TYPE value, l_int32 node_color,
626  node *left, node *right) {
627  node *result = (node *)LEPT_CALLOC(1, sizeof(node));
628  result->key = key;
629  result->value = value;
630  result->color = node_color;
631  result->left = left;
632  result->right = right;
633  if (left != NULL) left->parent = result;
634  if (right != NULL) right->parent = result;
635  result->parent = NULL;
636  return result;
637 }
638 
639 static node *lookup_node(L_RBTREE *t, RB_TYPE key) {
640  node *n = t->root;
641  while (n != NULL) {
642  int comp_result = compareKeys(t->keytype, key, n->key);
643  if (comp_result == 0) {
644  return n;
645  } else if (comp_result < 0) {
646  n = n->left;
647  } else { /* comp_result > 0 */
648  n = n->right;
649  }
650  }
651  return n;
652 }
653 
654 static void rotate_left(L_RBTREE *t, node *n) {
655  node *r = n->right;
656  replace_node(t, n, r);
657  n->right = r->left;
658  if (r->left != NULL) {
659  r->left->parent = n;
660  }
661  r->left = n;
662  n->parent = r;
663 }
664 
665 static void rotate_right(L_RBTREE *t, node *n) {
666  node *L = n->left;
667  replace_node(t, n, L);
668  n->left = L->right;
669  if (L->right != NULL) {
670  L->right->parent = n;
671  }
672  L->right = n;
673  n->parent = L;
674 }
675 
676 static void replace_node(L_RBTREE *t, node *oldn, node *newn) {
677  if (oldn->parent == NULL) {
678  t->root = newn;
679  } else {
680  if (oldn == oldn->parent->left)
681  oldn->parent->left = newn;
682  else
683  oldn->parent->right = newn;
684  }
685  if (newn != NULL) {
686  newn->parent = oldn->parent;
687  }
688 }
689 
690 static void insert_case1(L_RBTREE *t, node *n) {
691  if (n->parent == NULL)
692  n->color = L_BLACK_NODE;
693  else
694  insert_case2(t, n);
695 }
696 
697 static void insert_case2(L_RBTREE *t, node *n) {
698  if (node_color(n->parent) == L_BLACK_NODE)
699  return; /* Tree is still valid */
700  else
701  insert_case3(t, n);
702 }
703 
704 static void insert_case3(L_RBTREE *t, node *n) {
705  if (node_color(uncle(n)) == L_RED_NODE) {
706  n->parent->color = L_BLACK_NODE;
707  uncle(n)->color = L_BLACK_NODE;
708  grandparent(n)->color = L_RED_NODE;
709  insert_case1(t, grandparent(n));
710  } else {
711  insert_case4(t, n);
712  }
713 }
714 
715 static void insert_case4(L_RBTREE *t, node *n) {
716  if (n == n->parent->right && n->parent == grandparent(n)->left) {
717  rotate_left(t, n->parent);
718  n = n->left;
719  } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
720  rotate_right(t, n->parent);
721  n = n->right;
722  }
723  insert_case5(t, n);
724 }
725 
726 static void insert_case5(L_RBTREE *t, node *n) {
727  n->parent->color = L_BLACK_NODE;
728  grandparent(n)->color = L_RED_NODE;
729  if (n == n->parent->left && n->parent == grandparent(n)->left) {
730  rotate_right(t, grandparent(n));
731  } else if (n == n->parent->right && n->parent == grandparent(n)->right) {
732  rotate_left(t, grandparent(n));
733  } else {
734  L_ERROR("identity confusion\n", "insert_case5");
735  }
736 }
737 
738 static node *maximum_node(node *n) {
739  if (!n) {
740  L_ERROR("n not defined\n", "maximum_node");
741  return NULL;
742  }
743  while (n->right != NULL) {
744  n = n->right;
745  }
746  return n;
747 }
748 
749 static void delete_case1(L_RBTREE *t, node *n) {
750  if (n->parent == NULL)
751  return;
752  else
753  delete_case2(t, n);
754 }
755 
756 static void delete_case2(L_RBTREE *t, node *n) {
757  if (node_color(sibling(n)) == L_RED_NODE) {
758  n->parent->color = L_RED_NODE;
759  sibling(n)->color = L_BLACK_NODE;
760  if (n == n->parent->left)
761  rotate_left(t, n->parent);
762  else
763  rotate_right(t, n->parent);
764  }
765  delete_case3(t, n);
766 }
767 
768 static void delete_case3(L_RBTREE *t, node *n) {
769  if (node_color(n->parent) == L_BLACK_NODE &&
770  node_color(sibling(n)) == L_BLACK_NODE &&
771  node_color(sibling(n)->left) == L_BLACK_NODE &&
772  node_color(sibling(n)->right) == L_BLACK_NODE) {
773  sibling(n)->color = L_RED_NODE;
774  delete_case1(t, n->parent);
775  } else {
776  delete_case4(t, n);
777  }
778 }
779 
780 static void delete_case4(L_RBTREE *t, node *n) {
781  if (node_color(n->parent) == L_RED_NODE &&
782  node_color(sibling(n)) == L_BLACK_NODE &&
783  node_color(sibling(n)->left) == L_BLACK_NODE &&
784  node_color(sibling(n)->right) == L_BLACK_NODE) {
785  sibling(n)->color = L_RED_NODE;
786  n->parent->color = L_BLACK_NODE;
787  } else {
788  delete_case5(t, n);
789  }
790 }
791 
792 static void delete_case5(L_RBTREE *t, node *n) {
793  if (n == n->parent->left &&
794  node_color(sibling(n)) == L_BLACK_NODE &&
795  node_color(sibling(n)->left) == L_RED_NODE &&
796  node_color(sibling(n)->right) == L_BLACK_NODE) {
797  sibling(n)->color = L_RED_NODE;
798  sibling(n)->left->color = L_BLACK_NODE;
799  rotate_right(t, sibling(n));
800  } else if (n == n->parent->right &&
801  node_color(sibling(n)) == L_BLACK_NODE &&
802  node_color(sibling(n)->right) == L_RED_NODE &&
803  node_color(sibling(n)->left) == L_BLACK_NODE) {
804  sibling(n)->color = L_RED_NODE;
805  sibling(n)->right->color = L_BLACK_NODE;
806  rotate_left(t, sibling(n));
807  }
808  delete_case6(t, n);
809 }
810 
811 static void delete_case6(L_RBTREE *t, node *n) {
812  sibling(n)->color = node_color(n->parent);
813  n->parent->color = L_BLACK_NODE;
814  if (n == n->parent->left) {
815  if (node_color(sibling(n)->right) != L_RED_NODE) {
816  L_ERROR("right sibling is not RED", "delete_case6");
817  return;
818  }
819  sibling(n)->right->color = L_BLACK_NODE;
820  rotate_left(t, n->parent);
821  } else {
822  if (node_color(sibling(n)->left) != L_RED_NODE) {
823  L_ERROR("left sibling is not RED", "delete_case6");
824  return;
825  }
826  sibling(n)->left->color = L_BLACK_NODE;
827  rotate_right(t, n->parent);
828  }
829 }
830 
831 
832 /* ------------------------------------------------------------- *
833  * Debugging: verify if tree is valid *
834  * ------------------------------------------------------------- */
835 #if VERIFY_RBTREE
836 static void verify_property_1(node *root);
837 static void verify_property_2(node *root);
838 static void verify_property_4(node *root);
839 static void verify_property_5(node *root);
840 static void verify_property_5_helper(node *n, int black_count,
841  int* black_count_path);
842 #endif
843 
844 static void verify_properties(L_RBTREE *t) {
845 #if VERIFY_RBTREE
846  verify_property_1(t->root);
847  verify_property_2(t->root);
848  /* Property 3 is implicit */
849  verify_property_4(t->root);
850  verify_property_5(t->root);
851 #endif
852 }
853 
854 #if VERIFY_RBTREE
855 static void verify_property_1(node *n) {
856  if (node_color(n) != L_RED_NODE && node_color(n) != L_BLACK_NODE) {
857  L_ERROR("color neither RED nor BLACK\n", "verify_property_1");
858  return;
859  }
860  if (n == NULL) return;
861  verify_property_1(n->left);
862  verify_property_1(n->right);
863 }
864 
865 static void verify_property_2(node *root) {
866  if (node_color(root) != L_BLACK_NODE)
867  L_ERROR("root is not black!\n", "verify_property_2");
868 }
869 
870 static void verify_property_4(node *n) {
871  if (node_color(n) == L_RED_NODE) {
872  if (node_color(n->left) != L_BLACK_NODE ||
873  node_color(n->right) != L_BLACK_NODE ||
874  node_color(n->parent) != L_BLACK_NODE) {
875  L_ERROR("children & parent not all BLACK", "verify_property_4");
876  return;
877  }
878  }
879  if (n == NULL) return;
880  verify_property_4(n->left);
881  verify_property_4(n->right);
882 }
883 
884 static void verify_property_5(node *root) {
885  int black_count_path = -1;
886  verify_property_5_helper(root, 0, &black_count_path);
887 }
888 
889 static void verify_property_5_helper(node *n, int black_count,
890  int* path_black_count) {
891  if (node_color(n) == L_BLACK_NODE) {
892  black_count++;
893  }
894  if (n == NULL) {
895  if (*path_black_count == -1) {
896  *path_black_count = black_count;
897  } else if (*path_black_count != black_count) {
898  L_ERROR("incorrect black count", "verify_property_5_helper");
899  }
900  return;
901  }
902  verify_property_5_helper(n->left, black_count, path_black_count);
903  verify_property_5_helper(n->right, black_count, path_black_count);
904 }
905 #endif
void l_rbtreeDelete(L_RBTREE *t, RB_TYPE key)
l_rbtreeDelete()
Definition: rbtree.c:242
void l_rbtreePrint(FILE *fp, L_RBTREE *t)
l_rbtreePrint()
Definition: rbtree.c:492
L_RBTREE_NODE * l_rbtreeGetLast(L_RBTREE *t)
l_rbtreeGetLast()
Definition: rbtree.c:394
RB_TYPE * l_rbtreeLookup(L_RBTREE *t, RB_TYPE key)
l_rbtreeLookup()
Definition: rbtree.c:159
L_RBTREE_NODE * l_rbtreeGetPrev(L_RBTREE_NODE *n)
l_rbtreeGetPrev()
Definition: rbtree.c:429
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:359
void l_rbtreeDestroy(L_RBTREE **pt)
l_rbtreeDestroy()
Definition: rbtree.c:290
L_RBTREE_NODE * l_rbtreeGetFirst(L_RBTREE *t)
l_rbtreeGetFirst()
Definition: rbtree.c:324
l_int32 l_rbtreeGetCount(L_RBTREE *t)
l_rbtreeGetCount()
Definition: rbtree.c:459
void l_rbtreeInsert(L_RBTREE *t, RB_TYPE key, RB_TYPE value)
l_rbtreeInsert()
Definition: rbtree.c:188
Definition: rbtree.h:62