Rabbit Tree
Radix bit tries for implementing associative arrays and sets in C.
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
traverse_with_key.h
Go to the documentation of this file.
1 
42 #ifdef ONLY_FOR_DOXYGEN
43 #include "node.h"
44 #endif //ONLY_FOR_DOXYGEN
45 
50 #ifndef RBT_TRAVERSE_H_PREFIX_
51 #define RBT_TRAVERSE_H_PREFIX_ RBT_NODE_H_PREFIX_
52 #endif
53 
54 #undef RBT_NODE_TRAVERSE_WITH_KEY
55 #define RBT_NODE_TRAVERSE_WITH_KEY RBT_TOKEN_2_W(RBT_TRAVERSE_H_PREFIX_, node_traverse_with_key)
56 
57 #undef RBT_NODE_FILTER_WITH_KEY
58 #define RBT_NODE_FILTER_WITH_KEY RBT_TOKEN_2_W(RBT_TRAVERSE_H_PREFIX_, node_filter_with_key)
59 
91 #ifndef RBT_RESIZE_TO_FIT_KEY
92 #define RBT_RESIZE_TO_FIT_KEY(current_size, required_size, fail) \
93 do \
94 { \
95  current_size = required_size * 2; \
96  if (current_size < required_size) \
97  { \
98  current_size = -1; \
99  if (current_size < required_size) \
100  { \
101  fail; \
102  } \
103  } \
104 } \
105 while(0)
106 #endif // RBT_RESIZE_TO_FIT_KEY
107 
108 
109 
110 
111 
112 
113 /*
114  Use a linked list to track right nodes while descending into left nodes. The
115  linked list is constructed in such a way that the bit order (as determined by
116  the endianess of RBT_PIN_T) is respected when traversing the tree. The order
117  may vary across systems and should not be relied on for e.g. sorting.
118 
119  stack_unused is used to track allocated list elements to avoid unnecessary
120  reallocation of memory (i.e. free -> malloc).
121 
122 */
137 void
139  RBT_NODE_T * node,
141  ...
142 )
143 {
144  int rc;
145  _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T * stack, * stack_tmp, * stack_unused;
146  RBT_KEY_SIZE_T size, pins, bytes, tmp, height;
147  RBT_KEY_DATA_T key_data;
148 
149  va_list func_args;
150 
151  errno = 0;
152 
153  if (node == NULL)
154  {
155  return;
156  }
157 
158  key_data.bytes = 0;
159  height = 0;
160  stack = NULL;
161  stack_unused = NULL;
162  rc = 0;
163 
165  /*
166  If the key size is fixed then we can use an array and avoid dynamic
167  allocation.
168  */
169 #ifdef RBT_KEY_SIZE_FIXED
170  RBT_PIN_T key[RBT_KEY_SIZE_FIXED/RBT_PIN_SIZE];
171  key_data.key = (RBT_PIN_T *) key;
172  size = RBT_KEY_SIZE_FIXED;
173 #else
174  key_data.key = NULL;
175  size = 0;
176 #endif //RBT_KEY_SIZE_FIXED
177 
178  while (1)
179  {
180  key_data.node = node;
181  RBT_DIVMOD(node->bits, RBT_PIN_SIZE_BITS, pins, key_data.bits);
182  bytes = pins * RBT_PIN_SIZE;
183  if (key_data.bits)
184  {
185  bytes += RBT_PIN_SIZE;
186  }
187  tmp = key_data.bytes + bytes;
188 #ifndef RBT_KEY_SIZE_FIXED
189  if (tmp > size)
190  {
191  RBT_RESIZE_TO_FIT_KEY(size, tmp, errno = EOVERFLOW; break);
192  key_data.key = realloc(key_data.key, size);
193  if (key_data.key == NULL)
194  {
195  rc = errno;
196  break;
197  }
198  }
199 #endif //RBT_KEY_SIZE_FIXED
200  memcpy(((uint8_t *) key_data.key) + key_data.bytes, node->key, bytes);
201  key_data.bytes += bytes;
202  if (key_data.bits)
203  {
204  key_data.bytes -= RBT_PIN_SIZE;
205  }
206  key_data.bits += (key_data.bytes * RBT_PIN_SIZE_BITS);
208 
209  va_start(func_args, func_v);
210  if (func_v(&key_data, height, func_args) || errno)
211  {
212  rc = errno;
213  break;
214  }
215  va_end(func_args);
216 
217  if (node->right == NULL)
218  {
219  if (node->left == NULL)
220  {
221  if (stack == NULL)
222  {
223  break;
224  }
225  else
226  {
227  node = stack->node;
228  key_data.bytes = stack->bytes_in_key_prefix;
229  height = stack->height;
230  _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
231  continue;
232  }
233  }
234  else
235  {
236  node = node->left;
237  height ++;
238  }
239  }
240  else if (node->left == NULL)
241  {
242  node = node->right;
243  height ++;
244  }
245  else
246  {
247  _RBT_NODE_STACK_ALLOCATE(stack, stack_tmp, stack_unused, _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T);
248  height ++;
249  stack->node = node->right;
250  stack->height = height;
251  stack->bytes_in_key_prefix = key_data.bytes;
252  node = node->left;
253  }
254  }
255 #ifndef RBT_KEY_SIZE_FIXED
256 // if (! (RBT_KEY_SIZE_FIXED || key == NULL))
257  if (key_data.key != NULL)
258  {
259  free(key_data.key);
260  }
261 #endif
262  _RBT_NODE_STACK_FREE(stack, stack_tmp, stack_unused);
263  errno = rc;
264 }
265 
266 
267 
268 
269 
270 
271 
272 
273 
274 
275 
276 
277 
278 
279 
280 
281 
324 void
326  RBT_NODE_T * node,
328  int include_empty,
329  ...
330 )
331 {
332  int rc, unwanted, is_left, placeholder;
333  RBT_NODE_T * tmp_node, * sibling_node;
334  RBT_NODE_STACK_T * parent_stack, * parent_stack_tmp, * parent_stack_unused;
335  RBT_KEY_SIZE_T size, pins, bytes, tmp;
336  _RBT_NODE_FILTER_WITH_KEY_STACK_T * stack, * stack_tmp, * stack_unused;
337  RBT_KEY_DATA_T key_data;
338  va_list func_args;
339 
340  errno = 0;
341 
342  if (node == NULL)
343  {
344  return;
345  }
346 
347  key_data.bytes = 0;
348  stack = NULL;
349  stack_unused = NULL;
350  parent_stack = NULL;
351  parent_stack_unused = NULL;
352  rc = 0;
353 
355  /*
356  If the key size is fixed then we can use an array and avoid dynamic
357  allocation.
358  */
359 #ifdef RBT_KEY_SIZE_FIXED
360  RBT_PIN_T key[RBT_KEY_SIZE_FIXED/RBT_PIN_SIZE];
361  key_data.key = (RBT_PIN_T *) key;
362  size = RBT_KEY_SIZE_FIXED;
363 #else
364  key_data.key = NULL;
365  size = 0;
366 #endif //RBT_KEY_SIZE_FIXED
367 
368  while (1)
369  {
370  key_data.node = node;
371  RBT_DIVMOD(node->bits, RBT_PIN_SIZE_BITS, pins, key_data.bits);
372  bytes = pins * RBT_PIN_SIZE;
373  if (key_data.bits)
374  {
375  bytes += RBT_PIN_SIZE;
376  }
377  tmp = key_data.bytes + bytes;
378 #ifndef RBT_KEY_SIZE_FIXED
379  if (tmp > size)
380  {
381  RBT_RESIZE_TO_FIT_KEY(size, tmp, errno = EOVERFLOW; break);
382  key_data.key = realloc(key_data.key, size);
383  if (key_data.key == NULL)
384  {
385  rc = errno;
386  break;
387  }
388  }
389 #endif //RBT_KEY_SIZE_FIXED
390  memcpy(((uint8_t *) key_data.key) + key_data.bytes, node->key, bytes);
391  key_data.bytes += bytes;
392  if (key_data.bits)
393  {
394  key_data.bytes -= RBT_PIN_SIZE;
395  }
396  key_data.bits += (key_data.bytes * RBT_PIN_SIZE_BITS);
398 
399  if (node != NULL)
400  {
401  if (parent_stack != NULL)
402  {
403  debug_printf("filtering node: %p (parent: %p)\n", node, parent_stack->node);
404  }
405  else
406  {
407  debug_printf("filtering node: %p (no parent)\n", node);
408  }
409  if (include_empty || !RBT_VALUE_IS_NULL(node->value))
410  {
411  va_start(func_args, include_empty);
412  /*
413  This would purge superfluous nodes:
414  */
415 // unwanted = func_v(node->value, func_args) || RBT_VALUE_IS_NULL(node->value);
416  unwanted = func_v(&key_data, func_args);
417  va_end(func_args);
418  if (errno)
419  {
420  rc = errno;
421  break;
422  }
423  if (unwanted)
424  {
425  if (parent_stack != NULL)
426  {
427  is_left = parent_stack->node->left == node;
428  /*
429  The node will not be removed if it has any children. If it has
430  two then it will be left as a placeholder node. If it has only
431  one then it will be merged and we will need to continue the loop.
432  */
433  placeholder = (node->left != NULL) && (node->right != NULL);
434  if (is_left)
435  {
436  sibling_node = parent_stack->node->right;
437  }
438  else
439  {
440  sibling_node = parent_stack->node->left;
441  }
442  tmp_node = RBT_NODE_REMOVE(node, parent_stack->node);
443  if (errno)
444  {
445  rc = errno;
446  break;
447  }
448  /*
449  If the node has been completely removed then the sibling may have
450  been merged into the parent. Go back to the parent in that case.
451  */
452  if (tmp_node != node)
453  {
454  if (is_left)
455  {
456  /*
457  Jump directly to the sibling node if it has not changed.
458  */
459  if (parent_stack->node->right == sibling_node)
460  {
461  node = sibling_node;
462  key_data.bytes -= bytes;
463  }
464  /*
465  Otherwise jump to the parent.
466  */
467  else
468  {
469  node = parent_stack->node;
470  _RBT_NODE_STACK_POP(parent_stack, parent_stack_tmp, parent_stack_unused);
471  if (stack != NULL && stack->parent_stack->node == node)
472  {
473  _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
474  }
475  if (stack != NULL)
476  {
477  key_data.bytes = stack->bytes_in_key_prefix;
478  }
479  else
480  {
481  // TODO: break instead?
482  key_data.bytes = 0;
483  }
484  }
485  }
486  /*
487  If the node was the right child, then jump back to the last
488  right child.
489  */
490  else
491  {
492  if (stack != NULL)
493  {
494  node = stack->node;
495  key_data.bytes = stack->bytes_in_key_prefix;
496  while (parent_stack != NULL && parent_stack != stack->parent_stack)
497  {
498  _RBT_NODE_STACK_POP(parent_stack, parent_stack_tmp, parent_stack_unused);
499  }
500  _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
501  }
502  else
503  {
504  break;
505  }
506  }
507  continue;
508  }
509  /*
510  If the node remains, it is either a placeholder or it has been
511  merged with a child. In the latter case, continue to filter the
512  new value of the node.
513  */
514  if (! placeholder)
515  {
516  continue;
517  }
518  }
519  else
520  {
521  RBT_NODE_REMOVE(node, NULL);
522  if (errno)
523  {
524  rc = errno;
525  break;
526  }
527  }
528  }
529  }
530  if (node->left != NULL)
531  {
532  _RBT_NODE_STACK_ALLOCATE(parent_stack, parent_stack_tmp, parent_stack_unused, RBT_NODE_STACK_T);
533  parent_stack->node = node;
534  if (node->right != NULL)
535  {
536  _RBT_NODE_STACK_ALLOCATE(stack, stack_tmp, stack_unused, _RBT_NODE_FILTER_WITH_KEY_STACK_T);
537  stack->node = node->right;
538  stack->bytes_in_key_prefix = key_data.bytes;
539  stack->parent_stack = parent_stack;
540  }
541  node = node->left;
542  continue;
543  }
544  else if (node->right != NULL)
545  {
546  _RBT_NODE_STACK_ALLOCATE(parent_stack, parent_stack_tmp, parent_stack_unused, RBT_NODE_STACK_T);
547  parent_stack->node = node;
548  node = node->right;
549  continue;
550  }
551  }
552  if (stack != NULL)
553  {
554  node = stack->node;
555  key_data.bytes = stack->bytes_in_key_prefix;
556  while (parent_stack != NULL && parent_stack != stack->parent_stack)
557  {
558  _RBT_NODE_STACK_POP(parent_stack, parent_stack_tmp, parent_stack_unused);
559  }
560  _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
561  }
562  else
563  {
564  break;
565  }
566  }
567 #ifndef RBT_KEY_SIZE_FIXED
568 // if (! (RBT_KEY_SIZE_FIXED || key == NULL))
569  if (key_data.key != NULL)
570  {
571  free(key_data.key);
572  }
573 #endif
574  _RBT_NODE_STACK_FREE(parent_stack, parent_stack_tmp, parent_stack_unused);
575  _RBT_NODE_STACK_FREE(stack, stack_tmp, stack_unused);
576  errno = rc;
577 }
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
#define RBT_PIN_SIZE
Definition: key.h:128
RBT_PIN_T * key
The key.
Definition: node.h:486
RBT_VALUE_T value
Value associated with the node.
Definition: node.h:446
RBT_NODE_T * node
The node on the stack.
Definition: node.h:3260
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
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
RBT_KEY_SIZE_T bytes_in_key_prefix
The number of bytes in the key prefix for this node.
Definition: node.h:3266
void RBT_NODE_FILTER_WITH_KEY(RBT_NODE_T *node, RBT_NODE_FILTER_WITH_KEY_FUNCTION_T func_v, int include_empty,...)
Filter tree nodes.
Definition: traverse_with_key.h:325
#define debug_printf(fmt,...)
Definition: debug.h:138
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
Rabbit Tree key data type with associated node.
Definition: node.h:476
void RBT_NODE_TRAVERSE_WITH_KEY(RBT_NODE_T *node, RBT_NODE_TRAVERSE_WITH_KEY_FUNCTION_T func_v,...)
Definition: traverse_with_key.h:138
Linked list of nodes.
Definition: node.h:615
#define RBT_RESIZE_TO_FIT_KEY(current_size, required_size, fail)
Definition: traverse_with_key.h:92
RBT_KEY_SIZE_T bits
Number of significant bits in the key.
Definition: node.h:438
RBT_PIN_T * key
Key segment associated with this node.
Definition: node.h:428
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
RBT_NODE_T * node
Definition: node.h:621