Rabbit Tree
Radix bit tries for implementing associative arrays and sets in C.
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
node.h
Go to the documentation of this file.
1 
152 /*
153  # TODO
154 
155  * Consider creating a central traversal function that can track keys and
156  handle insertions/deletions. Such a function should be implemented if it can
157  be done without the introduction of unreasonable complexity and overhead.
158 */
159 
160 #include <errno.h>
161 #include <limits.h>
162 #include <stdarg.h>
163 #include <stdlib.h>
164 #include <string.h>
165 
166 #include "common.h"
167 #include "debug.h"
168 
169 #ifdef ONLY_FOR_DOXYGEN
170 #include "key.h"
171 #endif //ONLY_FOR_DOXYGEN
172 
177 #ifndef RBT_NODE_H_PREFIX_
178 #error RBT_NODE_H_PREFIX_ is not defined.
179 #endif // RBT_NODE_H_PREFIX_
180 
181 #ifndef RBT_VALUE_T
182 #error RBT_VALUE_T is not defined.
183 #endif // RBT_VALUE_T
184 
185 #ifndef RBT_VALUE_NULL
186 #error RBT_VALUE_NULL is not defined.
187 #endif // RBT_VALUE_NULL
188 
189 #ifndef RBT_VALUE_IS_EQUAL
190 #error RBT_VALUE_IS_EQUAL is not defined.
191 #endif // RBT_VALUE_IS_EQUAL
192 
193 #ifndef RBT_VALUE_COPY
194 #error RBT_VALUE_COPY is not defined.
195 #endif // RBT_VALUE_COPY
196 
197 #ifndef RBT_VALUE_FREE
198 #error RBT_VALUE_FREE is not defined.
199 #endif // RBT_VALUE_FREE
200 
201 #ifndef RBT_VALUE_FPRINT
202 #error RBT_VALUE_FPRINT is not defined.
203 #endif // RBT_VALUE_FPRINT
204 
205 /*
206  This is mostly for doxygen output when macro exansion is enabled, but it may
207  be convenient in some cases.
208 */
209 // #ifndef RBT_NODE_H_PREFIX_
210 // #define RBT_NODE_H_PREFIX_ rbt_
211 // #endif
212 
213 
214 typedef RBT_VALUE_T RBT_TOKEN_2_W(RBT_KEY_H_PREFIX_, value_t);
215 
216 
217 #undef RBT_NODE_COPY
218 #define RBT_NODE_COPY RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_copy)
219 
220 #undef RBT_NODE_COUNT
221 #define RBT_NODE_COUNT RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_count)
222 
223 #undef RBT_NODE_CREATE
224 #define RBT_NODE_CREATE RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_create)
225 
226 #undef RBT_NODE_FILTER
227 #define RBT_NODE_FILTER RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_filter)
228 
229 #undef RBT_NODE_FPRINT
230 #define RBT_NODE_FPRINT RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_fprint)
231 
232 #undef RBT_NODE_FPRINT_INTERNAL
233 #define RBT_NODE_FPRINT_INTERNAL RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_fprint_internal)
234 
235 #undef RBT_NODE_FREE
236 #define RBT_NODE_FREE RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_free)
237 
238 #undef RBT_KEY_DATA_T
239 #define RBT_KEY_DATA_T RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, key_data_t)
240 
241 #undef RBT_NODE_INSERT_CHILD
242 #define RBT_NODE_INSERT_CHILD RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_insert_child)
243 
244 #undef RBT_NODE_INSERT_PARENT
245 #define RBT_NODE_INSERT_PARENT RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_insert_parent)
246 
247 #undef RBT_NODE_INSERT_SIBLING
248 #define RBT_NODE_INSERT_SIBLING RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_insert_sibling)
249 
250 #undef RBT_NODE_IS_COPY
251 #define RBT_NODE_IS_COPY RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_is_copy)
252 
253 #undef RBT_NODE_MERGE_CHILD
254 #define RBT_NODE_MERGE_CHILD RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_merge_child)
255 
256 #undef RBT_NODE_NEW
257 #define RBT_NODE_NEW RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_new)
258 
259 #undef RBT_NODE_REMOVE
260 #define RBT_NODE_REMOVE RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_remove)
261 
262 #undef RBT_NODE_RETRIEVE
263 #define RBT_NODE_RETRIEVE RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_retrieve)
264 
265 #undef RBT_NODE_QUERY
266 #define RBT_NODE_QUERY RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_query)
267 
268 #undef RBT_NODE_TRAVERSE
269 #define RBT_NODE_TRAVERSE RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_traverse)
270 
271 #undef RBT_NODE_STACK_T
272 #define RBT_NODE_STACK_T RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_stack_t)
273 
274 #undef RBT_NODE_T
275 #define RBT_NODE_T RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_t)
276 
277 #undef RBT_VALUE_T
278 #define RBT_VALUE_T RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, value_t)
279 
280 #undef RBT_NODE_WITH_PREFIX_SUBTREE_DO
281 #define RBT_NODE_WITH_PREFIX_SUBTREE_DO RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, with_prefix_subtree_do)
282 
283 #undef RBT_NODE_FILTER_FUNCTION_T
284 #define RBT_NODE_FILTER_FUNCTION_T RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_filter_function_t)
285 
286 #undef RBT_NODE_FILTER_WITH_KEY_FUNCTION_T
287 #define RBT_NODE_FILTER_WITH_KEY_FUNCTION_T RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_filter_with_key_function_t)
288 
289 #undef RBT_NODE_TRAVERSE_FUNCTION_T
290 #define RBT_NODE_TRAVERSE_FUNCTION_T RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_traverse_function_t)
291 
292 #undef RBT_NODE_TRAVERSE_WITH_KEY_FUNCTION_T
293 #define RBT_NODE_TRAVERSE_WITH_KEY_FUNCTION_T RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_traverse_with_key_function_t)
294 
295 
296 #undef _RBT_NODE_PRINT_STACK_T
297 #define _RBT_NODE_PRINT_STACK_T _RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_print_stack_t)
298 
299 #undef _RBT_NODE_COPY_STACK_T
300 #define _RBT_NODE_COPY_STACK_T _RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_copy_stack_t)
301 
302 #undef _RBT_NODE_IS_COPY_STACK_T
303 #define _RBT_NODE_IS_COPY_STACK_T _RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_is_copy_stack_t)
304 
305 #undef _RBT_NODE_TRAVERSE_STACK_T
306 #define _RBT_NODE_TRAVERSE_STACK_T _RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_traverse_stack_t)
307 
308 #undef _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T
309 #define _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T _RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_traverse_with_key_stack_t)
310 
311 #undef _RBT_NODE_FILTER_STACK_T
312 #define _RBT_NODE_FILTER_STACK_T _RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_filter_stack_t)
313 
314 #undef _RBT_NODE_FILTER_WITH_KEY_STACK_T
315 #define _RBT_NODE_FILTER_WITH_KEY_STACK_T _RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_filter_with_key_stack_t)
316 
317 
318 
319 /*
320  The following are internal convencience macros for managing a stack using a
321  linked list. To prevent unnecessary cycles of allocation and freeing as the
322  stack changes, previously allocated elements are reused.
323 */
324 #undef _RBT_NODE_STACK_ALLOCATE
325 #define _RBT_NODE_STACK_ALLOCATE(stack, stack_tmp, stack_unused, stack_t) \
326 do \
327 { \
328  if (stack_unused != NULL) \
329  { \
330  stack_tmp = stack_unused->next; \
331  stack_unused->next = stack; \
332  stack = stack_unused; \
333  stack_unused = stack_tmp; \
334  } \
335  else \
336  { \
337  stack_tmp = malloc(sizeof(stack_t)); \
338  if (stack_tmp == NULL) \
339  { \
340  rc = errno; \
341  break; \
342  } \
343  stack_tmp->next = stack; \
344  stack = stack_tmp; \
345  } \
346 } \
347 while(0)
348 
349 
350 #undef _RBT_NODE_STACK_POP
351 #define _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused) \
352 do \
353 { \
354  stack_tmp = stack->next; \
355  stack->next = stack_unused; \
356  stack_unused = stack; \
357  stack = stack_tmp; \
358 } \
359 while(0)
360 
361 #undef _RBT_NODE_STACK_FREE
362 #define _RBT_NODE_STACK_FREE(stack, stack_tmp, stack_unused) \
363 do \
364 { \
365  while (stack != NULL) \
366  { \
367  stack_tmp = stack->next; \
368  free(stack); \
369  stack = stack_tmp; \
370  } \
371  while (stack_unused != NULL) \
372  { \
373  stack_tmp = stack_unused->next; \
374  free(stack_unused); \
375  stack_unused = stack_tmp; \
376  } \
377 } \
378 while(0)
379 
394 #undef RBT_VALUE_IS_NULL
395 #define RBT_VALUE_IS_NULL(value) RBT_VALUE_IS_EQUAL(value, RBT_VALUE_NULL)
396 
397 
398 
399 
400 
401 
402 
403 
408 typedef
410 
411 
412 
418 typedef
419 struct RBT_NODE_T
420 {
428  RBT_PIN_T * key;
429 
438  RBT_KEY_SIZE_T bits;
439 
447 
454  struct RBT_NODE_T * left;
455 
462  struct RBT_NODE_T * right;
463 }
464 RBT_NODE_T;
465 
466 
467 
476 typedef
477 struct RBT_KEY_DATA_T
478 {
486  RBT_PIN_T * key;
487 
492  RBT_KEY_SIZE_T bits;
493 
502  RBT_KEY_SIZE_T bytes;
503 
509 }
511 
512 
513 
514 
515 
516 #ifdef RBT_NODE_CACHE_SIZE
517 #undef RBT_NODE_CACHE
518 #define RBT_NODE_CACHE RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_cache)
519 #undef RBT_NODE_CACHE_T
520 #define RBT_NODE_CACHE_T RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_cache_t)
521 #undef RBT_NODE_CACHE_FREE
522 #define RBT_NODE_CACHE_FREE RBT_TOKEN_2_W(RBT_NODE_H_PREFIX_, node_cache_free)
523 
528 typedef
529 struct RBT_NODE_CACHE_T
530 {
531 
539  RBT_NODE_T * node;
540 
550  unsigned int n;
551 }
552 RBT_NODE_CACHE_T;
553 
558 RBT_NODE_CACHE_T RBT_NODE_CACHE = {.node=NULL, .n=0};
559 
560 #endif //RBT_NODE_CACHE_SIZE
561 
562 
563 
565 #ifdef RBT_CONCURRENCY_PTHREAD
566 # include "concurrency/pthread.h"
567 #endif //RBT_CONCURRENCY_PTHREAD
568 
569 
570 
571 #ifdef RBT_NODE_CACHE_SIZE
572 # ifndef RBT_NODE_CACHE_LOCK
573 # define RBT_NODE_CACHE_LOCK
574 # endif //RBT_NODE_CACHE_LOCK
575 
576 # ifndef RBT_NODE_CACHE_UNLOCK
577 # define RBT_NODE_CACHE_UNLOCK
578 # endif //RBT_NODE_CACHE_UNLOCK
579 
580 
586 void
587 RBT_NODE_CACHE_FREE()
588 {
589  RBT_NODE_T * node_tmp;
590  RBT_NODE_CACHE_LOCK
591  while (RBT_NODE_CACHE.node != NULL)
592  {
593  node_tmp = (RBT_NODE_CACHE.node)->left;
594  free(RBT_NODE_CACHE.node);
595  RBT_NODE_CACHE.node = node_tmp;
596  }
597  RBT_NODE_CACHE.n = 0;
598  RBT_NODE_CACHE_UNLOCK
599 }
600 #endif //RBT_NODE_CACHE_SIZE
601 
602 
603 
604 
605 
606 
615 typedef
616 struct RBT_NODE_STACK_T
617 {
622 
627 }
629 
630 
631 
632 /*
633  Print a node and its descendents to a file descriptor in a simple format.
634  This is mostly for debugging but may be expanded later.
635 void
636 RBT_NODE_FPRINT(FILE * fd, RBT_NODE_T * node, int indent, int skip)
637 {
638  int i = indent;
639  while(i--)
640  {
641 // fprintf(fd, " ");
642  fputc('.', fd);
643  }
644  RBT_FPRINT_BITS(fd, node->key, node->bits - skip, skip);
645  fprintf(fd, " ");
646  fprintf(fd, " (%p) ", node);
647  RBT_VALUE_FPRINT(fd, node->value);
648  fprintf(fd, "\n");
649  indent += node->bits - skip;
650  skip = node->bits % RBT_PIN_SIZE_BITS;
651  if (node->left != NULL)
652  {
653  RBT_NODE_FPRINT(fd, node->left, indent, skip);
654  }
655  if (node->right != NULL)
656  {
657  RBT_NODE_FPRINT(fd, node->right, indent, skip);
658  }
659 }
660 */
661 
662 
663 /*
664  The original recursive version that I wrote for initial testing.
665 
666 void
667 RBT_NODE_FPRINT_INTERNAL(FILE * fd, RBT_NODE_T * node, int print_bits, RBT_KEY_SIZE_T indent, unsigned long vert, int end, int skip)
668 {
669  RBT_KEY_SIZE_T i;
670  unsigned long shifted_vert;
671 
672 #ifdef RBT_USE_COLOR
673  fprintf(fd, "\033[32m");
674 #endif
675 
676  fprintf(fd, "%10p ", node);
677 
678 #ifdef RBT_USE_COLOR
679  fprintf(fd, "\033[34m");
680 #endif
681 
682  if (indent)
683  {
684  for (i = indent - 1; i; i--)
685  {
686  shifted_vert = (vert >> i);
687  if (shifted_vert & 1)
688  {
689  fprintf(fd, "│");
690  }
691  else
692  {
693  fprintf(fd, " ");
694  }
695  }
696  if (indent)
697  {
698  if (end)
699  {
700  fprintf(fd, "└");
701  }
702  else
703  {
704  fprintf(fd, "├");
705  }
706  }
707  }
708 
709 #ifdef RBT_USE_COLOR
710  fprintf(fd, "\033[35m");
711 #endif
712 
713 
714  if (print_bits)
715  {
716  RBT_FPRINT_BITS(fd, node->key, node->bits - skip, skip);
717  fprintf(fd, " ");
718  i = node->bits - skip;
719  }
720  else
721  {
722  fprintf(fd, "● ");
723  i = 1;
724  }
725 
726  indent += i;
727  vert <<= i;
728  vert ++;
729 
730 #ifdef RBT_USE_COLOR
731  fprintf(fd, "\033[36m");
732 #endif
733 
734  RBT_VALUE_FPRINT(fd, node->value);
735  fprintf(fd, "\n");
736 
737 #ifdef RBT_USE_COLOR
738  fprintf(fd, "\033[0m");
739 #endif
740 
741 
742  skip = node->bits % RBT_PIN_SIZE_BITS;
743  if (node->left != NULL)
744  {
745  RBT_NODE_FPRINT_INTERNAL(fd, node->left, print_bits, indent, vert, (node->right == NULL), skip);
746  }
747  if (node->right != NULL)
748  {
749  vert --;
750  RBT_NODE_FPRINT_INTERNAL(fd, node->right, print_bits, indent, vert, 1, skip);
751  }
752 }
753 */
754 
767 typedef
768 struct _RBT_NODE_PRINT_STACK_T
769 {
774  RBT_NODE_T * node;
775 
780  RBT_KEY_SIZE_T indent;
781 
791  RBT_KEY_SIZE_T vert;
792 
797  int is_last_child;
798 
803  int skip;
804 
809  struct _RBT_NODE_PRINT_STACK_T * next;
810 }
811 _RBT_NODE_PRINT_STACK_T;
812 
858 void
860  FILE * fd,
861  RBT_NODE_T * node,
862  int print_bits,
863  int print_pointer,
864  RBT_KEY_SIZE_T indent,
865  RBT_KEY_SIZE_T vert,
866  int is_last_child,
867  int skip
868 )
869 {
870  RBT_KEY_SIZE_T i;
871  _RBT_NODE_PRINT_STACK_T * stack, * stack_tmp, * stack_unused;
872  int rc;
873  unsigned long shifted_vert;
874 
875  errno = 0;
876 
877  if (node == NULL)
878  {
879  return;
880  }
881 
882  stack = NULL;
883  stack_unused = NULL;
884  rc = 0;
885 
886  while (1)
887  {
888  if (print_pointer)
889  {
890 #ifdef RBT_USE_COLOR
891  fprintf(fd, "\033[32m");
892 #endif
893  fprintf(fd, "%*p ", print_pointer, node);
894  }
895 
896 #ifdef RBT_USE_COLOR
897  fprintf(fd, "\033[34m");
898 #endif
899 
900  if (indent)
901  {
902  for (i = indent - 1; i; i--)
903  {
904  shifted_vert = (vert >> i);
905  if (shifted_vert & 1)
906  {
907  fprintf(fd, "│");
908  }
909  else
910  {
911  fprintf(fd, " ");
912  }
913  }
914  if (indent)
915  {
916  if (is_last_child)
917  {
918  fprintf(fd, "└");
919  }
920  else
921  {
922  fprintf(fd, "├");
923  }
924  }
925  }
926 
927 #ifdef RBT_USE_COLOR
928  fprintf(fd, "\033[35m");
929 #endif
930 
931 
932  if (print_bits)
933  {
934  RBT_FPRINT_BITS(fd, node->key, node->bits - skip, skip);
935  fprintf(fd, " ");
936  i = node->bits - skip;
937  }
938  else
939  {
940  fprintf(fd, "● ");
941  i = 1;
942  }
943 
944  indent += i;
945  vert <<= i;
946  vert ++;
947 
948 #ifdef RBT_USE_COLOR
949  fprintf(fd, "\033[36m");
950 #endif
951 
952  RBT_VALUE_FPRINT(fd, node->value);
953  fprintf(fd, "\n");
954 
955 
956  skip = node->bits % RBT_PIN_SIZE_BITS;
957  if (node->left != NULL)
958  {
959  is_last_child = (node->right == NULL);
960  if (!is_last_child)
961  {
962  /*
963  errno and rc may be set to non-zero values here, in which case the
964  loop will also be broken.
965  */
966  _RBT_NODE_STACK_ALLOCATE(stack, stack_tmp, stack_unused, _RBT_NODE_PRINT_STACK_T);
967  stack->node = node->right;
968  stack->indent = indent;
969  stack->vert = vert - 1;
970  stack->is_last_child = 1;
971  stack->skip = skip;
972  }
973  node = node->left;
974  }
975  else if (node->right != NULL)
976  {
977  vert --;
978  is_last_child = 1;
979  node = node->right;
980  }
981  else if (stack != NULL)
982  {
983  node = stack->node;
984  indent = stack->indent;
985  vert = stack->vert;
986  is_last_child = stack->is_last_child;
987  skip = stack->skip;
988  _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
989  }
990  else
991  {
992  break;
993  }
994  }
995 
996 #ifdef RBT_USE_COLOR
997  fprintf(fd, "\033[0m");
998 #endif
999 
1000  _RBT_NODE_STACK_FREE(stack, stack_tmp, stack_unused);
1001  errno = rc;
1002 }
1003 
1004 
1005 
1006 
1035 void
1037  FILE * fd,
1038  RBT_NODE_T * node,
1039  int print_bits,
1040  int print_pointer
1041 )
1042 {
1043  RBT_NODE_FPRINT_INTERNAL(fd, node, print_bits, print_pointer, 0, 0, 0, 0);
1044 }
1045 
1046 
1047 
1081 RBT_NODE_T *
1083  RBT_PIN_T * key,
1084  RBT_KEY_SIZE_T bits,
1085  RBT_VALUE_T value,
1086  RBT_NODE_T * left,
1087  RBT_NODE_T * right
1088 )
1089 {
1090  RBT_NODE_T * node;
1091  RBT_KEY_SIZE_T bytes;
1092 
1093 #ifdef RBT_NODE_CACHE_SIZE
1094  RBT_NODE_CACHE_LOCK
1095  node = RBT_NODE_CACHE.node;
1096  if (node != NULL)
1097  {
1098  RBT_NODE_CACHE.node = node->left;
1099  RBT_NODE_CACHE.n --;
1100  RBT_NODE_CACHE_UNLOCK
1101  }
1102  else
1103  {
1104  RBT_NODE_CACHE_UNLOCK
1105 #endif
1106 
1107  debug_print("creating node\n");
1108  node = malloc(sizeof(RBT_NODE_T));
1109  if (node == NULL)
1110  {
1111  debug_print("failed to allocate memory for node\n");
1112  return NULL;
1113  }
1114 
1115 #ifdef RBT_NODE_CACHE_SIZE
1116  }
1117 #endif
1118 
1119  bytes = BITS_TO_PINS_TO_BYTES(bits);
1120  node->key = malloc(bytes);
1121  if (node->key == NULL)
1122  {
1123  debug_printf("failed to allocate %" RBT_KEY_SIZE_T_FORMAT " bytes for key\n", bits);
1124  free(node);
1125  return NULL;
1126  }
1127  memcpy(node->key, key, bytes);
1128  node->bits = bits;
1129  node->value = RBT_VALUE_NULL;
1130  RBT_VALUE_COPY(node->value, value, free(node->key);free(node);return NULL);
1131  node->left = left;
1132  node->right = right;
1133  debug_printf("created node %p\n", node);
1134  debug_print_func(RBT_FPRINT_BITS, 1, node->key, node->bits, 0);
1135  return node;
1136 }
1137 
1138 
1139 
1144 #ifdef RBT_NODE_CACHE_SIZE
1145 
1148  #undef RBT_NODE_CACHE_OR_FREE
1149  #define RBT_NODE_CACHE_OR_FREE(node) \
1150  do \
1151  { \
1152  RBT_NODE_CACHE_LOCK \
1153  if ( \
1154  ! RBT_NODE_CACHE_SIZE || \
1155  RBT_NODE_CACHE.n <= RBT_NODE_CACHE_SIZE \
1156  ) \
1157  { \
1158  node->left = RBT_NODE_CACHE.node; \
1159  RBT_NODE_CACHE.node = node; \
1160  RBT_NODE_CACHE.n ++; \
1161  RBT_NODE_CACHE_UNLOCK \
1162  } \
1163  else \
1164  { \
1165  RBT_NODE_CACHE_UNLOCK \
1166  free(node); \
1167  } \
1168  } \
1169  while (0)
1170 #else
1171 
1174  #undef RBT_NODE_CACHE_OR_FREE
1175  #define RBT_NODE_CACHE_OR_FREE(node) free(node)
1176 #endif
1177 
1189 void
1191  RBT_NODE_T * node
1192 )
1193 {
1194 // debug_printf("freeing node %p\n", node);
1195  RBT_NODE_T * orphan, * heir, * descendent;
1196 
1197  errno = 0;
1198 
1199  if (node == NULL)
1200  {
1201  return;
1202  }
1203 
1204  descendent = NULL;
1205 
1206  /*
1207  Do it this way to avoid recursion, which would require two calls per
1208  invocation to handle both child nodes.
1209 
1210  The idea here is to free the top node then append the right tree to the
1211  bottom of the left tree. The left tree's top node then replaces the current
1212  node. The path to the bottom of the left tree will grow for every node
1213  with two children. To avoid descending the tree from the top each time,
1214  the last leftmost descendent is tracked.
1215 
1216  Tree traversal is thus reduces to traversing a linked list.
1217  */
1218  while (1)
1219  {
1220 // debug_print_func(RBT_FPRINT_BITS, 1, node->key, node->bits, 0);
1221  debug_printf("freeing node: %p\n", node);
1222 // debug_printf("node key pointer: %p\n", node->key);
1223  free(node->key);
1224  RBT_VALUE_FREE(node->value);
1225  if (node->right == NULL)
1226  {
1227  if (node->left == NULL)
1228  {
1229  RBT_NODE_CACHE_OR_FREE(node);
1230 // debug_print("freed\n");
1231  return;
1232  }
1233  else
1234  {
1235  heir = node->left;
1236  RBT_NODE_CACHE_OR_FREE(node);
1237  node = heir;
1238  }
1239  }
1240  else if (node->left == NULL)
1241  {
1242  heir = node->right;
1243  RBT_NODE_CACHE_OR_FREE(node);
1244  node = heir;
1245  }
1246  else
1247  {
1248  orphan = node->right;
1249  heir = node->left;
1250  RBT_NODE_CACHE_OR_FREE(node);
1251  node = heir;
1252  if (descendent == NULL)
1253  {
1254  descendent = heir;
1255  while (descendent->left !=NULL)
1256  {
1257  descendent = descendent->left;
1258  }
1259  }
1260  descendent->left = orphan;
1261  descendent = orphan;
1262  while (descendent->left !=NULL)
1263  {
1264  descendent = descendent->left;
1265  }
1266  }
1267  }
1268  debug_print("freed\n");
1269 }
1270 
1271 
1272 
1291 void
1293  RBT_NODE_T * parent_node,
1294  RBT_NODE_T * child_node
1295 )
1296 {
1297  debug_printf("merging child node %p (parent: %p)\n", child_node, parent_node);
1298  RBT_PIN_T * tmp_key;
1299  RBT_KEY_SIZE_T parent_bytes, child_bytes;
1300  RBT_VALUE_T tmp_value;
1301  RBT_NODE_T * tmp_node;
1302 
1303  errno = 0;
1304 
1305  /*
1306  Flooring division is required for parent to truncate overlap.
1307  */
1308  parent_bytes = PINS_TO_BYTES(parent_node->bits / RBT_PIN_SIZE_BITS);
1309  child_bytes = BITS_TO_PINS_TO_BYTES(child_node->bits);
1310  tmp_key = realloc(parent_node->key, parent_bytes + child_bytes);
1311  if (tmp_key == NULL)
1312  {
1313  debug_printf("failed to realloc key (%s)\n", strerror(errno));
1314  return;
1315  }
1316 
1317  parent_node->key = tmp_key;
1318  memcpy(((BYTE_T *) parent_node->key) + parent_bytes, child_node->key, child_bytes);
1319  parent_node->bits = (parent_bytes * BITS_PER_BYTE) + child_node->bits;
1320 
1321  /*
1322  Swap the values around so the value can be freed if necessary when freeing
1323  the child node. Do *not* use RBT_VALUE_COPY here.
1324  */
1325  tmp_value = parent_node->value;
1326  parent_node->value = child_node->value;
1327  child_node->value = tmp_value;
1328 
1329  /*
1330  Give the unexpected sibling to the child so that it can be freed along with
1331  the sibling.
1332  */
1333  if (parent_node->left == child_node)
1334  {
1335  tmp_node = parent_node->right;
1336  }
1337  else
1338  {
1339  tmp_node = parent_node->left;
1340  }
1341  parent_node->left = child_node->left;
1342  parent_node->right = child_node->right;
1343  // Prefer the left node because of the left bias in RBT_NODE_FREE
1344  child_node->left = tmp_node;
1345  child_node->right = NULL;
1346 
1347  RBT_NODE_FREE(child_node);
1348  debug_print("merged\n");
1349 }
1350 
1351 
1352 
1353 
1378 RBT_NODE_T *
1380  RBT_NODE_T * node,
1381  RBT_NODE_T * parent_node
1382 )
1383 {
1384  debug_printf("removing node %p (parent: %p)\n", node, parent_node);
1385 
1386  if (node->left == NULL)
1387  {
1388  if (node->right == NULL)
1389  {
1390  debug_print("no children\n");
1391  /*
1392  If the parent is null then this is a childless root node. It cannot be
1393  removed, but it can be emptied.
1394  */
1395  if (parent_node == NULL)
1396  {
1397  debug_print("root node\n");
1398  RBT_VALUE_COPY(node->value, RBT_VALUE_NULL, );
1399  free(node->key);
1400  node->key = NULL;
1401  node->bits = 0;
1402  }
1403  /*
1404  This node can be removed from the parent if it has no children. If the
1405  parent value is empty (i.e. the parent is a placeholder node) then the
1406  parent needs to be merged with the sibling node.
1407  */
1408  else
1409  {
1410  if (RBT_VALUE_IS_NULL(parent_node->value))
1411  {
1412  if (parent_node->left == node)
1413  {
1414  RBT_NODE_MERGE_CHILD(parent_node, parent_node->right);
1415  }
1416  else
1417  {
1418  RBT_NODE_MERGE_CHILD(parent_node, parent_node->left);
1419  }
1420  }
1421  else
1422  {
1423  if (parent_node->left == node)
1424  {
1425  parent_node->left = NULL;
1426  }
1427  else
1428  {
1429  parent_node->right = NULL;
1430  }
1431  RBT_NODE_FREE(node);
1432  }
1433  node = parent_node;
1434  }
1435  }
1436  /*
1437  A single child should be merged into this node.
1438  */
1439  else
1440  {
1441  debug_print("right child\n");
1442  RBT_NODE_MERGE_CHILD(node, node->right);
1443  }
1444  }
1445  /*
1446  A single child should be merged into this node.
1447  */
1448  else if (node->right == NULL)
1449  {
1450  debug_print("left child\n");
1451  RBT_NODE_MERGE_CHILD(node, node->left);
1452  }
1453  /*
1454  If the node has two children then the value needs to be emptied and key
1455  information must be kept.
1456  */
1457  else
1458  {
1459  debug_print("two children\n");
1460  RBT_VALUE_COPY(node->value, RBT_VALUE_NULL, );
1461  }
1462  debug_print("removed\n");
1463  return node;
1464 }
1465 
1466 
1490 void
1492  RBT_NODE_T * node,
1493  RBT_KEY_SIZE_T bits,
1494  RBT_VALUE_T value
1495 )
1496 {
1497  debug_print("inserting parent\n");
1498  RBT_KEY_SIZE_T pins, staggered_bits, parent_pins;
1499  RBT_NODE_T * child;
1500  RBT_PIN_T * tmp_key;
1501 
1502  RBT_DIVMOD(bits, RBT_PIN_SIZE_BITS, pins, staggered_bits);
1503 
1504  /*
1505  RBT_NODE_CREATE will copy the value passed to it, so pass it the new value
1506  and then swap the values of the parent and child below, instead of using
1507  superfluous RBT_VALUE_COPY statements.
1508  */
1509  child = RBT_NODE_CREATE(
1510  node->key + pins,
1511  node->bits - bits + staggered_bits,
1512  value,
1513  node->left,
1514  node->right
1515  );
1516  if (child == NULL)
1517  {
1518  debug_printf("failed to create child node (%s)\n", strerror(errno));
1519  return;
1520  }
1521 
1522  parent_pins = pins;
1523  if (staggered_bits > 0)
1524  {
1525  parent_pins ++;
1526  }
1527  tmp_key = realloc(node->key, parent_pins * RBT_PIN_SIZE);
1528  if (tmp_key == NULL && parent_pins)
1529  {
1530  debug_printf("failed to realloc key (%s)\n", strerror(errno));
1531  return;
1532  }
1533  node->key = tmp_key;
1534  node->bits = bits;
1535  /*
1536  Swap the values. Do *not* use RBT_VALUE_COPY.
1537  */
1538  value = child->value;
1539  child->value = node->value;
1540  node->value = value;
1541 
1542  if (N_BIT_IS_1(child->key[0], staggered_bits))
1543  {
1544  node->right = child;
1545  node->left = NULL;
1546  }
1547  else
1548  {
1549  node->left = NULL;
1550  node->right = child;
1551  }
1552  debug_print("inserted\n");
1553 }
1554 
1581 void
1583  RBT_NODE_T * * child_node_ptr,
1584  RBT_PIN_T * key,
1585  RBT_KEY_SIZE_T bits,
1586  RBT_VALUE_T value
1587 )
1588 {
1589  debug_print("inserting child\n");
1590  RBT_NODE_T * node;
1591  node = RBT_NODE_CREATE(key, bits, value, NULL, NULL);
1592  * child_node_ptr = node;
1593  debug_print("inserted\n");
1594 }
1595 
1596 
1649 RBT_NODE_T *
1651  RBT_NODE_T * node,
1652  RBT_PIN_T * key,
1653  RBT_KEY_SIZE_T bits,
1654  RBT_KEY_SIZE_T common_bits,
1655  RBT_KEY_SIZE_T common_pins,
1656  RBT_KEY_SIZE_T common_staggered_bits,
1657  RBT_VALUE_T value
1658 )
1659 {
1660  RBT_KEY_SIZE_T parent_pins;
1661  RBT_NODE_T * sibling, * baby;
1662  RBT_PIN_T * tmp_key;
1663 
1664  /*
1665  `sibling` is the node to which the existing data is moved.
1666  `baby` is the new node used to hold the new value.
1667  */
1668 
1669  debug_printf(
1670  "inserting sibling (%"
1671  RBT_KEY_SIZE_T_FORMAT ", %"
1672  RBT_KEY_SIZE_T_FORMAT ", %"
1673  RBT_KEY_SIZE_T_FORMAT ", %"
1674  RBT_KEY_SIZE_T_FORMAT ")\n",
1675  bits, common_bits, common_pins, common_staggered_bits
1676  );
1677 
1678  baby = RBT_NODE_CREATE(
1679  key + common_pins,
1680  bits - common_bits + common_staggered_bits,
1681  value,
1682  NULL,
1683  NULL
1684  );
1685 
1686  if (baby == NULL)
1687  {
1688  debug_printf("failed to create baby node (%s)\n", strerror(errno));
1689  return NULL;
1690  }
1691 
1692  /*
1693  Insert a null value here and then swap it with the current node's value to
1694  avoid redundant copying. The `value` variable above can be used as a
1695  placeholder.
1696  */
1697  sibling = RBT_NODE_CREATE(
1698  node->key + common_pins,
1699  node->bits - common_bits + common_staggered_bits,
1700  RBT_VALUE_NULL,
1701  node->left,
1702  node->right
1703  );
1704 
1705  if (sibling == NULL)
1706  {
1707  debug_printf("failed to create sibling node (%s)\n", strerror(errno));
1708  RBT_NODE_FREE(baby);
1709  return NULL;
1710  }
1711 
1712 
1713  parent_pins = common_pins;
1714  if (common_staggered_bits > 0)
1715  {
1716  parent_pins ++;
1717  }
1718  tmp_key = realloc(node->key, parent_pins * RBT_PIN_SIZE);
1719  // parent_pins may be 0, in which case realloc should return NULL.
1720  if (tmp_key == NULL && parent_pins)
1721  {
1722  debug_printf("failed to realloc key (%s)\n", strerror(errno));
1723  RBT_NODE_FREE(sibling);
1724  RBT_NODE_FREE(baby);
1725  return NULL;
1726  }
1727 
1728  node->key = tmp_key;
1729  node->bits = common_bits;
1730 
1731  value = node->value;
1732  node->value = sibling->value;
1733  sibling->value = value;
1734 
1735  if (N_BIT_IS_1(baby->key[0], common_staggered_bits))
1736  {
1737  node->right = baby;
1738  node->left = sibling;
1739  }
1740  else
1741  {
1742  node->left = baby;
1743  node->right = sibling;
1744  }
1745  debug_print("inserted\n");
1746  return baby;
1747 }
1748 
1749 
1750 
1758 RBT_NODE_T *
1760 {
1761  return RBT_NODE_CREATE(NULL, 0, RBT_VALUE_NULL, NULL, NULL);
1762 }
1763 
1764 
1765 
1766 
1767 
1768 
1769 
1770 
1772 
1785 typedef
1786 struct _RBT_NODE_COPY_STACK_T
1787 {
1792  RBT_NODE_T * node;
1793 
1800  RBT_NODE_T * * ptr;
1801 
1806  struct _RBT_NODE_COPY_STACK_T * next;
1807 }
1808 _RBT_NODE_COPY_STACK_T;
1809 
1835 RBT_NODE_T *
1837  RBT_NODE_T * node
1838 )
1839 {
1840  RBT_NODE_T * new_root, * new_node;
1841  RBT_NODE_T * * child_ptr;
1842  _RBT_NODE_COPY_STACK_T * stack, * stack_tmp, * stack_unused;
1843  int rc;
1844 
1845  errno = 0;
1846 
1847  if (node == NULL)
1848  {
1849  return NULL;
1850  }
1851 
1852 
1853  child_ptr = &new_root;
1854  stack = NULL;
1855  stack_unused = NULL;
1856  rc = 0;
1857 
1858  while (node != NULL)
1859  {
1860  new_node = RBT_NODE_CREATE(node->key, node->bits, node->value, NULL, NULL);
1861  * child_ptr = new_node;
1862 
1863  if (node->left != NULL)
1864  {
1865  if (node->right != NULL)
1866  {
1867  _RBT_NODE_STACK_ALLOCATE(stack, stack_tmp, stack_unused, _RBT_NODE_COPY_STACK_T);
1868  stack->node = node->right;
1869  stack->ptr = &(new_node->right);
1870  }
1871  child_ptr = &(new_node->left);
1872  node = node->left;
1873  }
1874  else if (node->right != NULL)
1875  {
1876  child_ptr = &(new_node->right);
1877  node = node->right;
1878  }
1879  else if (stack != NULL)
1880  {
1881  node = stack->node;
1882  child_ptr = stack->ptr;
1883  _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
1884  }
1885  else
1886  {
1887  break;
1888  }
1889  }
1890  if (rc)
1891  {
1892  RBT_NODE_FREE(new_root);
1893  }
1894  _RBT_NODE_STACK_FREE(stack, stack_tmp, stack_unused);
1895  errno = rc;
1896  return new_root;
1897 }
1898 
1899 
1900 
1901 
1902 
1904 
1917 typedef
1918 struct _RBT_NODE_FILTER_STACK_T
1919 {
1924  RBT_NODE_T * node;
1925 
1930  RBT_NODE_STACK_T * parent_stack;
1931 
1936  struct _RBT_NODE_FILTER_STACK_T * next;
1937 }
1938 _RBT_NODE_FILTER_STACK_T;
1939 
1960 typedef
1961 int
1963  RBT_VALUE_T * value,
1964  va_list args
1965 );
1966 
2000 void
2002  RBT_NODE_T * node,
2004  int include_empty,
2005  ...
2006 )
2007 {
2008  int rc, unwanted, is_left, placeholder;
2009  RBT_NODE_T * tmp_node, * sibling_node;
2010  RBT_NODE_STACK_T * parent_stack, * parent_stack_tmp, * parent_stack_unused;
2011  _RBT_NODE_FILTER_STACK_T * stack, * stack_tmp, * stack_unused;
2012  va_list func_args;
2013 
2014  errno = 0;
2015 
2016  if (node == NULL)
2017  {
2018  return;
2019  }
2020 
2021  stack = NULL;
2022  stack_unused = NULL;
2023  parent_stack = NULL;
2024  parent_stack_unused = NULL;
2025  rc = 0;
2026 
2027 // RBT_NODE_T * root
2028 // root = node;
2029 
2030  while (1)
2031  {
2032 // if (RBT_DEBUG)
2033 // {
2034 // RBT_NODE_FPRINT(RBT_DEBUG_FD, root, 0, 1);
2035 // }
2036  if (node != NULL)
2037  {
2038  if (parent_stack != NULL)
2039  {
2040  debug_printf("filtering node: %p (parent: %p)\n", node, parent_stack->node);
2041  }
2042  else
2043  {
2044  debug_printf("filtering node: %p (no parent)\n", node);
2045  }
2046  if (include_empty || !RBT_VALUE_IS_NULL(node->value))
2047  {
2048  va_start(func_args, include_empty);
2049  /*
2050  This would purge superfluous nodes:
2051  */
2052 // unwanted = func_v(node->value, func_args) || RBT_VALUE_IS_NULL(node->value);
2053  unwanted = func_v(&(node->value), func_args);
2054  va_end(func_args);
2055  if (errno)
2056  {
2057  rc = errno;
2058  break;
2059  }
2060  if (unwanted)
2061  {
2062  if (parent_stack != NULL)
2063  {
2064  is_left = parent_stack->node->left == node;
2065  /*
2066  The node will not be removed if it has any children. If it has
2067  two then it will be left as a placeholder node. If it has only
2068  one then it will be merged and we will need to continue the loop.
2069  */
2070  placeholder = (node->left != NULL) && (node->right != NULL);
2071  if (is_left)
2072  {
2073  sibling_node = parent_stack->node->right;
2074  }
2075  else
2076  {
2077  sibling_node = parent_stack->node->left;
2078  }
2079  tmp_node = RBT_NODE_REMOVE(node, parent_stack->node);
2080  if (errno)
2081  {
2082  rc = errno;
2083  break;
2084  }
2085  /*
2086  If the node has been completely removed then the sibling may have
2087  been merged into the parent. Go back to the parent in that case.
2088  */
2089  if (tmp_node != node)
2090  {
2091  if (is_left)
2092  {
2093  /*
2094  Jump directly to the sibling node if it has not changed.
2095  */
2096  if (parent_stack->node->right == sibling_node)
2097  {
2098  node = sibling_node;
2099  }
2100  /*
2101  Otherwise jump to the parent.
2102  */
2103  else
2104  {
2105  node = parent_stack->node;
2106  _RBT_NODE_STACK_POP(parent_stack, parent_stack_tmp, parent_stack_unused);
2107  if (stack != NULL && stack->parent_stack->node == node)
2108  {
2109  _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
2110  }
2111  }
2112  }
2113  /*
2114  If the node was the right child, then jump back to the last
2115  right child.
2116  */
2117  else
2118  {
2119  if (stack != NULL)
2120  {
2121  node = stack->node;
2122  while (parent_stack != NULL && parent_stack != stack->parent_stack)
2123  {
2124  _RBT_NODE_STACK_POP(parent_stack, parent_stack_tmp, parent_stack_unused);
2125  }
2126  _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
2127  }
2128  else
2129  {
2130  break;
2131  }
2132  }
2133  continue;
2134  }
2135  /*
2136  If the node remains, it is either a placeholder or it has been
2137  merged with a child. In the latter case, continue to filter the
2138  new value of the node.
2139  */
2140  if (! placeholder)
2141  {
2142  continue;
2143  }
2144  }
2145  else
2146  {
2147  RBT_NODE_REMOVE(node, NULL);
2148  if (errno)
2149  {
2150  rc = errno;
2151  break;
2152  }
2153  }
2154  }
2155  }
2156  if (node->left != NULL)
2157  {
2158  _RBT_NODE_STACK_ALLOCATE(parent_stack, parent_stack_tmp, parent_stack_unused, RBT_NODE_STACK_T);
2159  parent_stack->node = node;
2160  if (node->right != NULL)
2161  {
2162  _RBT_NODE_STACK_ALLOCATE(stack, stack_tmp, stack_unused, _RBT_NODE_FILTER_STACK_T);
2163  stack->node = node->right;
2164  stack->parent_stack = parent_stack;
2165  }
2166  node = node->left;
2167  continue;
2168  }
2169  else if (node->right != NULL)
2170  {
2171  _RBT_NODE_STACK_ALLOCATE(parent_stack, parent_stack_tmp, parent_stack_unused, RBT_NODE_STACK_T);
2172  parent_stack->node = node;
2173  node = node->right;
2174  continue;
2175  }
2176  }
2177  if (stack != NULL)
2178  {
2179  node = stack->node;
2180  while (parent_stack != NULL && parent_stack != stack->parent_stack)
2181  {
2182  _RBT_NODE_STACK_POP(parent_stack, parent_stack_tmp, parent_stack_unused);
2183  }
2184  _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
2185  }
2186  else
2187  {
2188  break;
2189  }
2190  }
2191  _RBT_NODE_STACK_FREE(parent_stack, parent_stack_tmp, parent_stack_unused);
2192  _RBT_NODE_STACK_FREE(stack, stack_tmp, stack_unused);
2193  errno = rc;
2194 }
2195 
2196 
2197 
2199 
2212 typedef
2213 struct _RBT_NODE_IS_COPY_STACK_T
2214 {
2219  RBT_NODE_T * a;
2220 
2225  RBT_NODE_T * b;
2226 
2231  struct _RBT_NODE_IS_COPY_STACK_T * next;
2232 }
2233 _RBT_NODE_IS_COPY_STACK_T;
2234 
2259 int
2261  RBT_NODE_T * a,
2262  RBT_NODE_T * b
2263 )
2264 {
2265  _RBT_NODE_IS_COPY_STACK_T * stack, * stack_tmp, * stack_unused;
2266  int rc;
2267 
2268  errno = 0;
2269 
2270  if (a == NULL)
2271  {
2272  if (b == NULL)
2273  {
2274  return 1;
2275  }
2276  else
2277  {
2278  return 0;
2279  }
2280  }
2281  else if (b == NULL)
2282  {
2283  return 0;
2284  }
2285 
2286  stack = NULL;
2287  stack_unused = NULL;
2288 
2289  rc = 1;
2290  while (rc)
2291  {
2292  if (
2293  a->bits != b->bits ||
2294  (a->left == NULL) != (b->left == NULL) ||
2295  (a->right == NULL) != (b->right == NULL) ||
2296  ! RBT_VALUE_IS_EQUAL(a->value, b->value) ||
2297  RBT_COMMON_BIT_PREFIX_LEN(a->key, b->key, a->bits) != a->bits
2298  )
2299  {
2300  rc = 0;
2301  break;
2302  }
2303  if (a->left != NULL)
2304  {
2305  if (a->right != NULL)
2306  {
2307  _RBT_NODE_STACK_ALLOCATE(stack, stack_tmp, stack_unused, _RBT_NODE_IS_COPY_STACK_T);
2308  stack->a = a->right;
2309  stack->b = b->right;
2310  }
2311  a = a->left;
2312  b = b->left;
2313  }
2314  else if (a->right != NULL)
2315  {
2316  a = a->right;
2317  b = b->right;
2318  }
2319  else if (stack != NULL)
2320  {
2321  a = stack->a;
2322  b = stack->b;
2323  _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
2324  }
2325  else
2326  {
2327  break;
2328  }
2329  }
2330  _RBT_NODE_STACK_FREE(stack, stack_tmp, stack_unused);
2331  return rc;
2332 }
2333 
2334 
2335 
2336 
2337 
2338 
2339 
2340 
2342 /*
2343  @cond INTERNAL
2344  Use a macro to avoid repetition in the function. This is strictly internal
2345  and independent of user-defined macros.
2346 */
2347 
2348 #ifndef _RBT_RETRIEVE_RETURN_WITH_PARENT
2349  #define _RBT_RETRIEVE_RETURN_WITH_PARENT(node, parent_node_ptr) \
2350  do \
2351  { \
2352  if (parent_node_ptr != NULL) \
2353  { \
2354  * parent_node_ptr = parent_node; \
2355  } \
2356  return node; \
2357  } \
2358  while (0)
2359 #endif
2360 
2440 RBT_NODE_T *
2442  RBT_NODE_T * node,
2443  RBT_PIN_T * key,
2444  RBT_KEY_SIZE_T bits,
2445  rbt_retrieve_action_t action,
2446  RBT_VALUE_T value,
2447  RBT_NODE_T * * parent_node_ptr
2448 )
2449 {
2450  debug_print_func(RBT_FPRINT_BITS, 1, key, bits, 0);
2451  debug_printf("bits: %" RBT_KEY_SIZE_T_FORMAT "\n", bits);
2452  debug_printf("action: %s\n", rbt_retrieve_action_string(action));
2453  /*
2454  The "pin" is the unit of the key array in the node. If the array is a byte
2455  array then the pin is a byte, etc. The name is from the pins in a tumbler
2456  lock.
2457  */
2458  int rc;
2459  RBT_KEY_SIZE_T common_bits, common_staggered_bits, common_pins;
2460  RBT_NODE_T * parent_node;
2461  RBT_NODE_T * * child_node_ptr;
2462  RBT_PIN_T * tmp_key;
2463 
2464  errno = rc = 0;
2465  parent_node = NULL;
2466  child_node_ptr = NULL;
2467 
2468  /*
2469  The root node is the only node that may have 0 bits in its key and which
2470  cannot be deleted. Handle it as a special case.
2471  */
2472  if (node->bits == 0)
2473  {
2474  debug_print("keyless root node\n");
2475  /*
2476  The key has no bits. This should be uncommon but there is no reason to
2477  prevent it.
2478  */
2479  if (bits == 0)
2480  {
2481  debug_print("received empty key\n");
2482  switch (action)
2483  {
2485  RBT_VALUE_COPY(node->value, value, return NULL);
2486 
2487  default:
2488  _RBT_RETRIEVE_RETURN_WITH_PARENT(node, parent_node_ptr);
2489  break;
2490  }
2491  }
2492  /*
2493  The requested key is non-zero here whereas the root node is zero. If the
2494  root node has no children then there are two possibilities: it is empty
2495  and can be used to hold a new value, or it is not empty and a new child
2496  would be required to hold the value.
2497  */
2498  else if (node->left == NULL && node->right == NULL)
2499  {
2500  debug_print("root node has no children\n");
2501  switch (action)
2502  {
2505  if (RBT_VALUE_IS_NULL(node->value))
2506  {
2507  debug_print("root node is empty\n");
2508  /*
2509  common_pins is a misnomer here (variable re-use).
2510  */
2511  common_pins = BITS_TO_PINS_TO_BYTES(bits);
2512  /*
2513  Use tmp key to preserve node if malloc fails.
2514  */
2515  tmp_key = malloc(common_pins);
2516  if (tmp_key == NULL)
2517  {
2518  debug_printf(
2519  "failed to malloc %" RBT_KEY_SIZE_T_FORMAT " bytes for key (error: %s)\n",
2520  common_pins,
2521  strerror(errno)
2522  );
2523  return NULL;
2524  }
2525  free(node->key);
2526  node->key = tmp_key;
2527  memcpy(node->key, key, common_pins);
2528  node->bits = bits;
2529  RBT_VALUE_COPY(node->value, value, return NULL);
2530  debug_print("target is root node\n");
2531  }
2532  else
2533  {
2534  parent_node = node;
2535  node = RBT_NODE_CREATE(key, bits, value, NULL, NULL);
2536  if (node == NULL)
2537  {
2538  debug_printf("failed to create node (%s)\n", strerror(errno));
2539  return NULL;
2540  }
2541  if (FIRST_BIT_IS_1(key[0]))
2542  {
2543  parent_node->right = node;
2544  }
2545  else
2546  {
2547  parent_node->left = node;
2548  }
2549  debug_print("target is child of root node\n");
2550  }
2551  _RBT_RETRIEVE_RETURN_WITH_PARENT(node, parent_node_ptr);
2552  break;
2553 
2554  default:
2555  return NULL;
2556  break;
2557  }
2558  }
2559  /*
2560  If the root node has children and no key, then a non-zero key must lead
2561  to one of the children.
2562  */
2563  else
2564  {
2565  debug_print("root node has at least one child\n");
2566  parent_node = node;
2567  if (FIRST_BIT_IS_1(key[0]))
2568  {
2569  debug_print("checking right child\n");
2570  child_node_ptr = &node->right;
2571  }
2572  else
2573  {
2574  debug_print("checking left child\n");
2575  child_node_ptr = &node->left;
2576  }
2577  parent_node = node;
2578  /*
2579  The target child is missing.
2580  */
2581  if (* child_node_ptr == NULL)
2582  {
2583  debug_print("target child of root node is missing\n");
2584  switch (action)
2585  {
2588  node = RBT_NODE_CREATE(key, bits, value, NULL, NULL);
2589  if (node == NULL)
2590  {
2591  debug_printf("failed to create node (%s)\n", strerror(errno));
2592  return NULL;
2593  }
2594  * child_node_ptr = node;
2595  debug_print("inserted missing child\n");
2596  _RBT_RETRIEVE_RETURN_WITH_PARENT(node, parent_node_ptr);
2597  break;
2598 
2599  default:
2600  return NULL;
2601  break;
2602  }
2603  }
2604  else
2605  {
2606  node = * child_node_ptr;
2607  }
2608  }
2609  }
2610 
2611  /*
2612  Walk along the nodes until:
2613  a) we find a matching node (all bits are common)
2614  b) we run out of nodes (a new child is needed)
2615  c) we run out of key bits (a new parent is needed)
2616  d) we find mismatched bits (a new sibling is needed)
2617  */
2618 // while (node != NULL)
2619  while (1)
2620  {
2621  common_bits = RBT_COMMON_BIT_PREFIX_LEN(key, node->key, MIN(bits, node->bits));
2622  debug_print_func(RBT_FPRINT_BITS, 1, key, bits, 0);
2623  debug_printf("node %p\n", node);
2624  debug_print_func(RBT_FPRINT_BITS, 1, node->key, node->bits, 0);
2625  debug_printf("common bits: %" RBT_KEY_SIZE_T_FORMAT "\n", common_bits);
2626  /*
2627  If the common bits match the remaining bits then we have matched our
2628  input key. The matching node is either this one or a missing parent.
2629  */
2630  if (common_bits == bits)
2631  {
2632  /*
2633  If all of the node bits are also common then this node matches.
2634  */
2635  if (common_bits == node->bits)
2636  {
2637  debug_print("matched\n");
2638  switch (action)
2639  {
2641  if (parent_node_ptr != NULL)
2642  {
2643  (* parent_node_ptr)->bits = 0;
2644  }
2645  return node;
2646  break;
2647 
2649  RBT_VALUE_COPY(node->value, value, return NULL);
2650 
2651  default:
2652  _RBT_RETRIEVE_RETURN_WITH_PARENT(node, parent_node_ptr);
2653  break;
2654  }
2655  }
2656  /*
2657  Else the node contains more bits and does not match. The matching node
2658  is a missing parent node. Inserting the parent node will update the
2659  current node, so it and the parent node remain valid.
2660  */
2661  else
2662  {
2663  debug_print("target is parent\n");
2664  switch (action)
2665  {
2667  if (parent_node_ptr != NULL)
2668  {
2669  (* parent_node_ptr)->bits = node->bits - common_bits;
2670  }
2671  return node;
2672  break;
2673 
2676  RBT_NODE_INSERT_PARENT(node, bits, value);
2677  if (errno)
2678  {
2679  return NULL;
2680  }
2681  _RBT_RETRIEVE_RETURN_WITH_PARENT(node, parent_node_ptr);
2682  break;
2683 
2684  default:
2685  return NULL;
2686  break;
2687  }
2688  }
2689  }
2690  else
2691  {
2692  RBT_DIVMOD(common_bits, RBT_PIN_SIZE_BITS, common_pins, common_staggered_bits);
2693  /*
2694  If the node bits are common then the key contains more bits than
2695  the node. The matching node will be a child.
2696  */
2697  if (common_bits == node->bits)
2698  {
2699  key += common_pins;
2700  bits += common_staggered_bits - common_bits;
2701  debug_print("found parent\n");
2702  parent_node = node;
2703  if (N_BIT_IS_1(key[0], common_staggered_bits))
2704  {
2705  debug_print("right\n");
2706  child_node_ptr = &(node->right);
2707  }
2708  else
2709  {
2710  debug_print("left\n");
2711  child_node_ptr = &(node->left);
2712  }
2713  /*
2714  The child node does not exist.
2715  */
2716  if (* child_node_ptr == NULL)
2717  {
2718  debug_print("missing child\n");
2719  switch (action)
2720  {
2723  RBT_NODE_INSERT_CHILD(child_node_ptr, key, bits, value);
2724  if (errno)
2725  {
2726  return NULL;
2727  }
2728  parent_node = node;
2729  node = * child_node_ptr;
2730  _RBT_RETRIEVE_RETURN_WITH_PARENT(node, parent_node_ptr);
2731  break;
2732 
2733  default:
2734  return NULL;
2735  break;
2736  }
2737  }
2738  else
2739  {
2740  debug_print("checking child\n");
2741  node = * child_node_ptr;
2742  }
2743  }
2744  /*
2745  If there are common bits followed by divergent bits then the missing
2746  node is a sibling node and a new parent is required to hold both.
2747  */
2748  else
2749  {
2750  debug_print("target is sibling\n");
2751  switch (action)
2752  {
2755  parent_node = node;
2756  node = RBT_NODE_INSERT_SIBLING(
2757  node,
2758  key,
2759  bits,
2760  common_bits,
2761  common_pins,
2762  common_staggered_bits,
2763  value
2764  );
2765  _RBT_RETRIEVE_RETURN_WITH_PARENT(node, parent_node_ptr);
2766  break;
2767 
2768  default:
2769  return NULL;
2770  break;
2771  }
2772  }
2773  }
2774  }
2775  /*
2776  This should be unreachable. It is included to prevent compiler warnings.
2777  */
2778 // errno = ENOTSUP;
2779  errno = ENOTRECOVERABLE;
2780  error_print("control has escaped loop\n");
2781  return NULL;
2782 }
2783 
2784 
2785 
2786 
2787 
2788 
2790 
2836  RBT_NODE_T * root_node,
2837  RBT_PIN_T * key,
2838  RBT_KEY_SIZE_T bits,
2839  rbt_query_action_t action,
2840  RBT_VALUE_T value
2841 )
2842 {
2843  RBT_NODE_T * target_node, * parent_node;
2844  RBT_VALUE_T target_value;
2845  int effective_deletion;
2846 
2847  /*
2848  Inserting an empty value is effectively a deletion.
2849 
2850  Store the value here to avoid possible overhead from multiple calls.
2851  */
2852  effective_deletion = RBT_VALUE_IS_NULL(value);
2853 
2854  switch (action)
2855  {
2857  if (effective_deletion)
2858  {
2859  action = RBT_QUERY_ACTION_DELETE;
2860  }
2861  break;
2862 
2863  default:
2864  break;
2865  }
2866 
2867  /*
2868  # TODO
2869  Consider mergine the following switch statements. They were separated to
2870  centralize the call to RBT_NODE_RETRIEVE.
2871  */
2872 
2873  switch (action)
2874  {
2876  target_node = RBT_NODE_RETRIEVE(
2877  root_node,
2878  key,
2879  bits,
2881  RBT_VALUE_NULL,
2882  &parent_node
2883  );
2884  if (errno)
2885  {
2886  return RBT_VALUE_NULL;
2887  }
2888  if (target_node != NULL && ! RBT_VALUE_IS_NULL(target_node->value))
2889  {
2890  RBT_NODE_REMOVE(target_node, parent_node);
2891  }
2892  return RBT_VALUE_NULL;
2893  break;
2894 
2895 
2896 
2898  target_node = RBT_NODE_RETRIEVE(
2899  root_node,
2900  key,
2901  bits,
2903  RBT_VALUE_NULL,
2904  &parent_node
2905  );
2906  if (errno || target_node == NULL)
2907  {
2908  return RBT_VALUE_NULL;
2909  }
2910  else
2911  {
2912  return target_node->value;
2913  }
2914  break;
2915 
2916 
2917 
2919  target_node = RBT_NODE_RETRIEVE(
2920  root_node,
2921  key,
2922  bits,
2924  value,
2925  &parent_node
2926  );
2927  if (errno)
2928  {
2929  return RBT_VALUE_NULL;
2930  }
2931  return value;
2932  break;
2933 
2934 
2935 
2937  target_node = RBT_NODE_RETRIEVE(
2938  root_node,
2939  key,
2940  bits,
2942  RBT_VALUE_NULL,
2943  &parent_node
2944  );
2945  if (errno)
2946  {
2947  return RBT_VALUE_NULL;
2948  }
2949  /*
2950  There is no need to copy this value as it would be overwritten when
2951  the updated with the new value.
2952  */
2953  target_value = target_node->value;
2954  target_node->value = RBT_VALUE_NULL;
2955  if (effective_deletion)
2956  {
2957  RBT_NODE_REMOVE(target_node, parent_node);
2958  if (errno)
2959  {
2960  return RBT_VALUE_NULL;
2961  }
2962  }
2963  else
2964  {
2965  /*
2966  If something goes wrong, restore the value and return the input value.
2967  */
2968  RBT_VALUE_COPY(target_node->value, value, target_node->value = target_value; return value);
2969  }
2970  return target_value;
2971  break;
2972 
2973 
2974 
2975  case RBT_QUERY_ACTION_SWAP:
2976  target_node = RBT_NODE_RETRIEVE(
2977  root_node,
2978  key,
2979  bits,
2981  RBT_VALUE_NULL,
2982  &parent_node
2983  );
2984  if (errno)
2985  {
2986  return RBT_VALUE_NULL;
2987  }
2988  target_value = target_node->value;
2989  if (effective_deletion)
2990  {
2991  /*
2992  Prevent target_value from being freed.
2993  */
2994  target_node->value = RBT_VALUE_NULL;
2995  RBT_NODE_REMOVE(target_node, parent_node);
2996  if (errno)
2997  {
2998  return RBT_VALUE_NULL;
2999  }
3000  }
3001  else
3002  {
3003  target_node->value = value;
3004  }
3005  return target_value;
3006  break;
3007  }
3008  /*
3009  This should be unreachable, but compile complains if there is not return
3010  statement.
3011  */
3012  return RBT_VALUE_NULL;
3013 }
3014 
3015 
3016 
3017 
3018 
3019 
3020 
3022 
3023 
3036 typedef struct _RBT_NODE_TRAVERSE_STACK_T
3037 {
3042  RBT_NODE_T * node;
3043 
3049  RBT_KEY_SIZE_T height;
3050 
3055  struct _RBT_NODE_TRAVERSE_STACK_T * next;
3056 }
3057 _RBT_NODE_TRAVERSE_STACK_T;
3058 
3087 typedef
3088 int
3090  RBT_NODE_T * node,
3091  RBT_KEY_SIZE_T height,
3092  va_list args
3093 );
3094 
3095 
3096 
3114 void
3116  RBT_NODE_T * node,
3118  ...
3119 )
3120 {
3121  int rc;
3122  _RBT_NODE_TRAVERSE_STACK_T * stack, * stack_tmp, * stack_unused;
3123  RBT_KEY_SIZE_T height;
3124  va_list func_args;
3125 
3126  errno = 0;
3127 
3128  if (node == NULL)
3129  {
3130  return;
3131  }
3132 
3133  height = 0;
3134  stack = NULL;
3135  stack_unused = NULL;
3136  rc = 0;
3137 
3138  while (1)
3139  {
3140  va_start(func_args, func_v);
3141  if (func_v(node, height, func_args) || errno)
3142  {
3143  rc = errno;
3144  break;
3145  }
3146  va_end(func_args);
3147 
3148  if (node->right == NULL)
3149  {
3150  if (node->left == NULL)
3151  {
3152  if (stack == NULL)
3153  {
3154  break;
3155  }
3156  else
3157  {
3158  node = stack->node;
3159  height = stack->height;
3160  _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
3161  continue;
3162  }
3163  }
3164  else
3165  {
3166  node = node->left;
3167  height ++;
3168  }
3169  }
3170  else if (node->left == NULL)
3171  {
3172  node = node->right;
3173  height ++;
3174  }
3175  else
3176  {
3177  _RBT_NODE_STACK_ALLOCATE(stack, stack_tmp, stack_unused, _RBT_NODE_TRAVERSE_STACK_T);
3178  height ++;
3179  stack->node = node->right;
3180  stack->height = height;
3181  node = node->left;
3182  }
3183  }
3184  _RBT_NODE_STACK_FREE(stack, stack_tmp, stack_unused);
3185  errno = rc;
3186 }
3187 
3188 
3189 
3190 
3191 
3192 
3193 
3194 
3195 /*
3196  This is unaffected by fixed length keys, so keep it here.
3197 */
3198 
3212 typedef struct _RBT_NODE_FILTER_WITH_KEY_STACK_T
3213 {
3218  RBT_NODE_T * node;
3219 
3224  RBT_KEY_SIZE_T bytes_in_key_prefix;
3225 
3230  RBT_NODE_STACK_T * parent_stack;
3231 
3236  struct _RBT_NODE_FILTER_WITH_KEY_STACK_T * next;
3237 }
3238 _RBT_NODE_FILTER_WITH_KEY_STACK_T;
3239 
3255 {
3261 
3266  RBT_KEY_SIZE_T bytes_in_key_prefix;
3267 
3273  RBT_KEY_SIZE_T height;
3274 
3280 }
3282 
3283 
3284 
3300 typedef
3301 int
3303  RBT_KEY_DATA_T * key_data,
3304  va_list args
3305 );
3306 
3307 
3308 
3333 typedef
3334 int
3336  RBT_KEY_DATA_T * key_data,
3337  RBT_KEY_SIZE_T height,
3338  va_list args
3339 );
3340 
3341 
3343 
3349 RBT_KEY_SIZE_T
3351  RBT_NODE_T * node
3352 )
3353 {
3354  int rc;
3355  RBT_NODE_STACK_T * stack, * stack_tmp, * stack_unused;
3356  RBT_KEY_SIZE_T n;
3357 
3358  errno = 0;
3359 
3360  if (node == NULL)
3361  {
3362  return 0;
3363  }
3364 
3365  n = 0;
3366  stack = NULL;
3367  stack_unused = NULL;
3368  rc = 0;
3369 
3370  while (1)
3371  {
3372  if (! RBT_VALUE_IS_NULL(node->value))
3373  {
3374  n ++;
3375  }
3376 
3377  if (node->right == NULL)
3378  {
3379  if (node->left == NULL)
3380  {
3381  if (stack == NULL)
3382  {
3383  break;
3384  }
3385  else
3386  {
3387  node = stack->node;
3388  _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
3389  continue;
3390  }
3391  }
3392  else
3393  {
3394  node = node->left;
3395  }
3396  }
3397  else if (node->left == NULL)
3398  {
3399  node = node->right;
3400  }
3401  else
3402  {
3403  _RBT_NODE_STACK_ALLOCATE(stack, stack_tmp, stack_unused, _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T);
3404  stack->node = node->right;
3405  node = node->left;
3406  }
3407  }
3408  _RBT_NODE_STACK_FREE(stack, stack_tmp, stack_unused);
3409  errno = rc;
3410  return n;
3411 }
3412 
3413 
3415 
3444 int
3446  RBT_NODE_T * node,
3447  RBT_PIN_T * key,
3448  RBT_KEY_SIZE_T bits,
3449  void (* func_v)(RBT_NODE_T * subtree, va_list args),
3450  ...
3451 )
3452 {
3453  RBT_NODE_T subroot_node, * tmp_node, * node_ptr;
3454  RBT_KEY_SIZE_T bytes, prefix_bytes, total_bits, extra_bits;
3455  va_list func_args;
3456 
3457  node_ptr = & subroot_node;
3458 
3459  tmp_node = RBT_NODE_RETRIEVE(
3460  node, key, bits,
3462  RBT_VALUE_NULL,
3463  & node_ptr
3464  );
3465 
3466  if (tmp_node == NULL)
3467  {
3468  return 0;
3469  }
3470 
3471  extra_bits = subroot_node.bits;
3472  total_bits = bits + extra_bits;
3473  bytes = BITS_TO_PINS_TO_BYTES(total_bits);
3474  subroot_node.key = malloc(bytes);
3475  if (subroot_node.key == NULL)
3476  {
3477  debug_printf("failed to allocate memory for key (%s)\n", strerror(errno));
3478  return 0;
3479  }
3480  prefix_bytes = (bits + extra_bits - tmp_node->bits) / BITS_PER_BYTE;
3481  memcpy(subroot_node.key, key, prefix_bytes);
3482  memcpy(subroot_node.key + prefix_bytes, tmp_node->key, bytes - prefix_bytes);
3483  subroot_node.bits = total_bits;
3484  subroot_node.value = tmp_node->value;
3485  subroot_node.left = tmp_node->left;
3486  subroot_node.right = tmp_node->right;
3487 
3488 
3489  va_start(func_args, func_v);
3490  func_v(&subroot_node, func_args);
3491  va_end(func_args);
3492 
3493  free(subroot_node.key);
3494  return 1;
3495 }
3496 
Definition: common.h:364
rbt_query_action_t
Query action for RBT_NODE_QUERY().
Definition: common.h:407
void RBT_NODE_FPRINT(FILE *fd, RBT_NODE_T *node, int print_bits, int print_pointer)
Print trees using box-drawing characters.
Definition: node.h:1036
RBT_KEY_SIZE_T bits
Number of significant bits in the key.
Definition: node.h:492
RBT_KEY_SIZE_T bytes
Number of significant bits in the key.
Definition: node.h:502
#define RBT_PIN_SIZE_BITS
Definition: key.h:133
#define RBT_DIVMOD(a, b, c, d)
Definition: key.h:224
RBT_NODE_T * node
The associated node.
Definition: node.h:508
RBT_VALUE_T RBT_VALUE_T
The node's value type.
Definition: node.h:409
rbt_retrieve_action_t
Retrieval action for RBT_NODE_RETRIEVE().
Definition: common.h:329
struct _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T
Linked list for implementing RBT_NODE_TRAVERSE_WITH_KEY's dynamic stack.
#define FIRST_BIT_IS_1(x)
Determine if the most significant bit is 1.
Definition: common.h:292
void RBT_NODE_FREE(RBT_NODE_T *node)
Definition: node.h:1190
#define debug_print_func(func, print_newline,...)
Definition: debug.h:190
#define RBT_PIN_SIZE
Definition: key.h:128
#define RBT_TOKEN_2_W(a, b)
A wrapper for RBT_TOKEN_2() to ensure macro expansion.
Definition: common.h:240
RBT_PIN_T * key
The key.
Definition: node.h:486
RBT_VALUE_T value
Value associated with the node.
Definition: node.h:446
Definition: common.h:334
const char * rbt_retrieve_action_string(rbt_retrieve_action_t action)
Return a string representing a retrieval action.
Definition: common.h:377
RBT_NODE_T * node
The node on the stack.
Definition: node.h:3260
struct RBT_KEY_DATA_T RBT_KEY_DATA_T
Rabbit Tree key data type with associated node.
struct _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T * next
The next item in the stack.
Definition: node.h:3279
void RBT_NODE_INSERT_CHILD(RBT_NODE_T **child_node_ptr, RBT_PIN_T *key, RBT_KEY_SIZE_T bits, RBT_VALUE_T value)
Insert a child node.
Definition: node.h:1582
#define BITS_TO_PINS_TO_BYTES(x)
Definition: key.h:162
int RBT_NODE_IS_COPY(RBT_NODE_T *a, RBT_NODE_T *b)
Check if a tree is a copy.
Definition: node.h:2260
#define BYTE_T
A byte type.
Definition: common.h:184
void RBT_FPRINT_BITS(FILE *fd, RBT_PIN_T *key, RBT_KEY_SIZE_T n, RBT_KEY_SIZE_T skip)
Definition: key.h:189
RBT_NODE_T * RBT_NODE_INSERT_SIBLING(RBT_NODE_T *node, RBT_PIN_T *key, RBT_KEY_SIZE_T bits, RBT_KEY_SIZE_T common_bits, RBT_KEY_SIZE_T common_pins, RBT_KEY_SIZE_T common_staggered_bits, RBT_VALUE_T value)
Insert a sibling node.
Definition: node.h:1650
Definition: common.h:412
Definition: common.h:417
Definition: common.h:340
int(* RBT_NODE_FILTER_WITH_KEY_FUNCTION_T)(RBT_KEY_DATA_T *key_data, va_list args)
The function type accepted by RBT_NODE_FILTER_WITH_KEY().
Definition: node.h:3302
int(* RBT_NODE_TRAVERSE_FUNCTION_T)(RBT_NODE_T *node, RBT_KEY_SIZE_T height, va_list args)
A tree traversal function.
Definition: node.h:3089
RBT_KEY_SIZE_T height
The height of the node above the root node (or the depth, depending on how you look at it)...
Definition: node.h:3273
Linked list for implementing RBT_NODE_TRAVERSE_WITH_KEY's dynamic stack.
Definition: node.h:3254
RBT_NODE_T * RBT_NODE_REMOVE(RBT_NODE_T *node, RBT_NODE_T *parent_node)
Remove a node from a tree.
Definition: node.h:1379
#define error_print(msg)
Definition: debug.h:234
RBT_NODE_T * RBT_NODE_CREATE(RBT_PIN_T *key, RBT_KEY_SIZE_T bits, RBT_VALUE_T value, RBT_NODE_T *left, RBT_NODE_T *right)
Create a node.
Definition: node.h:1082
RBT_NODE_T * RBT_NODE_NEW()
Create a new tree.
Definition: node.h:1759
#define BITS_PER_BYTE
The number of bits in a byte.
Definition: common.h:190
RBT_KEY_SIZE_T RBT_COMMON_BIT_PREFIX_LEN(RBT_PIN_T *a, RBT_PIN_T *b, RBT_KEY_SIZE_T max)
Definition: key.h:250
Definition: common.h:427
RBT_KEY_SIZE_T bytes_in_key_prefix
The number of bytes in the key prefix for this node.
Definition: node.h:3266
int(* RBT_NODE_FILTER_FUNCTION_T)(RBT_VALUE_T *value, va_list args)
The function type accepted by RBT_NODE_FILTER().
Definition: node.h:1962
#define PINS_TO_BYTES(x)
Definition: key.h:151
#define debug_printf(fmt,...)
Definition: debug.h:138
RBT_NODE_T * RBT_NODE_COPY(RBT_NODE_T *node)
Copy a tree.
Definition: node.h:1836
RBT_NODE_T * RBT_NODE_RETRIEVE(RBT_NODE_T *node, RBT_PIN_T *key, RBT_KEY_SIZE_T bits, rbt_retrieve_action_t action, RBT_VALUE_T value, RBT_NODE_T **parent_node_ptr)
Retrieve a node matching the given key.
Definition: node.h:2441
void RBT_NODE_FPRINT_INTERNAL(FILE *fd, RBT_NODE_T *node, int print_bits, int print_pointer, RBT_KEY_SIZE_T indent, RBT_KEY_SIZE_T vert, int is_last_child, int skip)
Definition: node.h:859
void RBT_NODE_INSERT_PARENT(RBT_NODE_T *node, RBT_KEY_SIZE_T bits, RBT_VALUE_T value)
Insert a parent node.
Definition: node.h:1491
int RBT_NODE_WITH_PREFIX_SUBTREE_DO(RBT_NODE_T *node, RBT_PIN_T *key, RBT_KEY_SIZE_T bits, void(*func_v)(RBT_NODE_T *subtree, va_list args),...)
Perform some action on the subtree defined by a common prefix.
Definition: node.h:3445
struct RBT_NODE_T * left
Left child node.
Definition: node.h:454
struct RBT_NODE_T * right
Right child node.
Definition: node.h:462
#define RBT_VALUE_IS_NULL(value)
Definition: node.h:395
Rabbit Tree node type.
Definition: node.h:418
struct RBT_NODE_STACK_T * next
Definition: node.h:626
Rabbit Tree key data type with associated node.
Definition: node.h:476
Definition: common.h:422
void RBT_NODE_FILTER(RBT_NODE_T *node, RBT_NODE_FILTER_FUNCTION_T func_v, int include_empty,...)
Filter tree nodes.
Definition: node.h:2001
void RBT_NODE_MERGE_CHILD(RBT_NODE_T *parent_node, RBT_NODE_T *child_node)
Definition: node.h:1292
RBT_VALUE_T RBT_NODE_QUERY(RBT_NODE_T *root_node, RBT_PIN_T *key, RBT_KEY_SIZE_T bits, rbt_query_action_t action, RBT_VALUE_T value)
Query a tree.
Definition: node.h:2835
RBT_KEY_SIZE_T RBT_NODE_COUNT(RBT_NODE_T *node)
Definition: node.h:3350
struct RBT_NODE_STACK_T RBT_NODE_STACK_T
Linked list of nodes.
struct RBT_NODE_T RBT_NODE_T
Rabbit Tree node type.
void RBT_NODE_TRAVERSE(RBT_NODE_T *node, RBT_NODE_TRAVERSE_FUNCTION_T func_v,...)
Definition: node.h:3115
Linked list of nodes.
Definition: node.h:615
RBT_KEY_SIZE_T bits
Number of significant bits in the key.
Definition: node.h:438
#define N_BIT_IS_1(x, n)
Determine if the nth bit is 1.
Definition: common.h:304
RBT_PIN_T * key
Key segment associated with this node.
Definition: node.h:428
#define debug_print(msg)
Definition: debug.h:160
int(* RBT_NODE_TRAVERSE_WITH_KEY_FUNCTION_T)(RBT_KEY_DATA_T *key_data, RBT_KEY_SIZE_T height, va_list args)
A tree traversal function.
Definition: node.h:3335
#define MIN(a, b)
Return the minimum of a or b.
Definition: common.h:203
RBT_NODE_T * node
Definition: node.h:621
#define RBT_NODE_CACHE_OR_FREE(node)
Definition: node.h:1175
Definition: common.h:435