Rabbit Tree
Radix bit tries for implementing associative arrays and sets in C.
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
set.h
Go to the documentation of this file.
1 
54 #include <stdint.h>
55 
56 #include "common.h"
57 #include "debug.h"
58 
59 #ifdef ONLY_FOR_DOXYGEN
60 #include "key.h"
61 #endif //ONLY_FOR_DOXYGEN
62 
67 #ifndef RBT_SET_H_PREFIX_
68 #error RBT_SET_H_PREFIX_ is not defined.
69 #endif // RBT_SET_H_PREFIX_
70 
71 #ifndef RBT_KEY_T
72 #error RBT_KEY_T is not defined.
73 #endif // RBT_KEY_T
74 
75 #ifndef RBT_KEY_COUNT_BITS
76 #error RBT_KEY_COUNT_BITS is not defined.
77 #endif // RBT_KEY_COUNT_BITS
78 
79 #ifndef RBT_KEY_PTR
80 #error RBT_KEY_PTR is not defined.
81 #endif // RBT_KEY_PTR
82 
83 #ifndef RBT_KEY_FPRINT
84 #error RBT_KEY_FPRINT is not defined.
85 #endif // RBT_KEY_FPRINT
86 
87 
88 #undef RBT_SET_ADD
89 #define RBT_SET_ADD RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_add)
90 
91 #undef RBT_SET_DIFFERENCE
92 #define RBT_SET_DIFFERENCE RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_difference)
93 
94 #undef RBT_SET_EXCLUSIVE_DISJUNCTION
95 #define RBT_SET_EXCLUSIVE_DISJUNCTION RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_exclusive_disjunction)
96 
97 #undef RBT_SET_INCLUDES
98 #define RBT_SET_INCLUDES RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_includes)
99 
100 #undef RBT_SET_INTERSECTION
101 #define RBT_SET_INTERSECTION RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_intersection)
102 
103 #undef RBT_SET_IS_SUBSET
104 #define RBT_SET_IS_SUBSET RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_is_subset)
105 
106 #undef RBT_SET_REMOVE
107 #define RBT_SET_REMOVE RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_remove)
108 
109 #undef RBT_SET_UNION
110 #define RBT_SET_UNION RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_union)
111 
112 #undef RBT_SET_MODIFY_DIFFERENCE
113 #define RBT_SET_MODIFY_DIFFERENCE RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_difference)
114 
115 #undef RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION
116 #define RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_exclusive_disjunction)
117 
118 #undef RBT_SET_MODIFY_INTERSECTION
119 #define RBT_SET_MODIFY_INTERSECTION RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_intersection)
120 
121 #undef RBT_SET_MODIFY_UNION
122 #define RBT_SET_MODIFY_UNION RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_union)
123 
124 
125 
126 /*
127  Internal definitions.
128 */
129 #undef _RBT_SET_DIFFERENCE_TRAVERSE
130 #define _RBT_SET_DIFFERENCE_TRAVERSE _RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_difference_traverse)
131 
132 #undef _RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION_TRAVERSE
133 #define _RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION_TRAVERSE _RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_exclusive_disjunction_traverse)
134 
135 #undef _RBT_SET_MODIFY_INTERSECTION_FILTER
136 #define _RBT_SET_MODIFY_INTERSECTION_FILTER _RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_intersection_filter)
137 
138 #undef _RBT_SET_MODIFY_INTERSECTION_TRAVERSE
139 #define _RBT_SET_MODIFY_INTERSECTION_TRAVERSE _RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_intersection_traverse)
140 
141 #undef _RBT_SET_MODIFY_IS_SUBSET_TRAVERSE
142 #define _RBT_SET_MODIFY_IS_SUBSET_TRAVERSE _RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_subset_traverse)
143 
144 #undef _RBT_SET_MODIFY_UNION_TRAVERSE
145 #define _RBT_SET_MODIFY_UNION_TRAVERSE _RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_union_traverse)
146 
147 #undef _RBT_SET_MODIFY_DIFFERENCE_TRAVERSE
148 #define _RBT_SET_MODIFY_DIFFERENCE_TRAVERSE _RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_difference_traverse)
149 
150 
151 
152 
157 #undef RBT_NODE_H_PREFIX_
158 #define RBT_NODE_H_PREFIX_ RBT_SET_H_PREFIX_
159 
164 #undef RBT_VALUE_T
165 #define RBT_VALUE_T int
166 
171 #undef RBT_VALUE_NULL
172 #define RBT_VALUE_NULL 0
173 
178 #undef RBT_VALUE_IS_EQUAL
179 #define RBT_VALUE_IS_EQUAL(a, b) (a == b)
180 
185 #undef RBT_VALUE_COPY
186 #define RBT_VALUE_COPY(var,val,fail) var = val
187 
192 #undef RBT_VALUE_FREE
193 #define RBT_VALUE_FREE(val)
194 
199 #undef RBT_VALUE_FPRINT
200 #define RBT_VALUE_FPRINT(fd, val) \
201 do \
202 { \
203  if (val != RBT_VALUE_NULL) \
204  { \
205  fprintf(fd, "%d", val); \
206  } \
207 } while(0)
208 
209 #include "node.h"
210 #include "traverse_with_key.h"
211 
216 #undef RBT_WRAPPER_H_PREFIX_
217 #define RBT_WRAPPER_H_PREFIX_ RBT_SET_H_PREFIX_
218 #include "wrapper.h"
219 
220 
227 
237 int
238 _RBT_SET_MODIFY_UNION_TRAVERSE(
239  RBT_KEY_DATA_T * key_data,
240  RBT_KEY_SIZE_T height,
241  va_list args
242 )
243 {
244  RBT_NODE_T * target;
245 
246  if (! RBT_VALUE_IS_NULL(key_data->node->value))
247  {
248  target = va_arg(args, RBT_NODE_T *);
249 
251  target, key_data->key, key_data->bits, RBT_RETRIEVE_ACTION_INSERT, 1, NULL
252  );
253  }
254  return 0;
255 }
256 
273 void
275 {
276  RBT_NODE_TRAVERSE_WITH_KEY(b, _RBT_SET_MODIFY_UNION_TRAVERSE, a);
277 }
278 
279 
295 RBT_NODE_T *
297 {
298  RBT_NODE_T * c;
299 
300  c = RBT_NODE_COPY(a);
301  RBT_NODE_TRAVERSE_WITH_KEY(b, _RBT_SET_MODIFY_UNION_TRAVERSE, c);
302  return c;
303 }
304 
305 
306 
307 
308 
310 
319 int
320 _RBT_SET_MODIFY_DIFFERENCE_TRAVERSE(
321  RBT_KEY_DATA_T * key_data,
322  RBT_KEY_SIZE_T height,
323  va_list args
324 )
325 {
326  RBT_NODE_T * target, * parent;
327 
328  if (! RBT_VALUE_IS_NULL(key_data->node->value))
329  {
330  target = va_arg(args, RBT_NODE_T *);
331 
332  target = RBT_NODE_RETRIEVE(
333  target, key_data->key, key_data->bits, RBT_RETRIEVE_ACTION_NOTHING, RBT_VALUE_NULL, &parent
334  );
335  if (target != NULL)
336  {
337  RBT_NODE_REMOVE(target, parent);
338  }
339  }
340  return 0;
341 }
342 
359 void
361 {
362  RBT_NODE_TRAVERSE_WITH_KEY(b, _RBT_SET_MODIFY_DIFFERENCE_TRAVERSE, a);
363 }
364 
373 int
374 _RBT_SET_DIFFERENCE_TRAVERSE(
375  RBT_KEY_DATA_T * key_data,
376  RBT_KEY_SIZE_T height,
377  va_list args
378 )
379 {
380  RBT_NODE_T * b, * c;
381 
382  if (! RBT_VALUE_IS_NULL(key_data->node->value))
383  {
384  b = va_arg(args, RBT_NODE_T *);
385  c = va_arg(args, RBT_NODE_T *);
386 
387  b = RBT_NODE_RETRIEVE(
388  b, key_data->key, key_data->bits, RBT_RETRIEVE_ACTION_NOTHING, RBT_VALUE_NULL, NULL
389  );
390  /*
391  If the value does not exist in b, insert it.
392  */
393  if (b == NULL)
394  {
396  c, key_data->key, key_data->bits, RBT_RETRIEVE_ACTION_INSERT_OR_REPLACE, b->value, NULL
397  );
398  }
399  }
400  return 0;
401 }
402 
422 RBT_NODE_T *
424 {
425  RBT_NODE_T * c;
426 
427  c = RBT_NODE_NEW();
428  RBT_NODE_TRAVERSE_WITH_KEY(a, _RBT_SET_DIFFERENCE_TRAVERSE, b, c);
429  return c;
430 }
431 
432 
433 
435 
444 int
445 _RBT_SET_MODIFY_INTERSECTION_FILTER(
446  RBT_KEY_DATA_T * key_data,
447  va_list args
448 )
449 {
450  RBT_NODE_T * target;
451 
452  if (! RBT_VALUE_IS_NULL(key_data->node->value))
453  {
454  target = va_arg(args, RBT_NODE_T *);
455 
456  target = RBT_NODE_RETRIEVE(
457  target, key_data->key, key_data->bits, RBT_RETRIEVE_ACTION_NOTHING, RBT_VALUE_NULL, NULL
458  );
459  return (target == NULL);
460  }
461  return 1;
462 }
463 
481 void
483 {
484  RBT_NODE_FILTER_WITH_KEY(a, _RBT_SET_MODIFY_INTERSECTION_FILTER, 0, b);
485 }
486 
502 RBT_NODE_T *
504 {
505  RBT_NODE_T * c;
506  c = RBT_NODE_COPY(a);
508  return c;
509 }
510 
511 
513 
522 int
523 _RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION_TRAVERSE(
524  RBT_KEY_DATA_T * key_data,
525  RBT_KEY_SIZE_T height,
526  va_list args
527 )
528 {
529  RBT_NODE_T * target, * parent;
530 
531  if (! RBT_VALUE_IS_NULL(key_data->node->value))
532  {
533  target = va_arg(args, RBT_NODE_T *);
534 
535  target = RBT_NODE_RETRIEVE(
536  target, key_data->key, key_data->bits, RBT_QUERY_ACTION_INSERT, RBT_VALUE_NULL, &parent
537  );
538  if (target->value)
539  {
540  RBT_NODE_REMOVE(target, parent);
541  }
542  else
543  {
544  target->value = 1;
545  }
546  }
547  return 0;
548 }
549 
566 void
568 {
569  RBT_NODE_TRAVERSE_WITH_KEY(b, _RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION_TRAVERSE, a);
570 }
571 
586 RBT_NODE_T *
588 {
589  RBT_NODE_T * c;
590  c = RBT_NODE_COPY(a);
591  RBT_NODE_TRAVERSE_WITH_KEY(b, _RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION_TRAVERSE, c);
592  return c;
593 }
594 
595 
597 
606 int
607 _RBT_SET_IS_SUBSET_TRAVERSE(
608  RBT_KEY_DATA_T * key_data,
609  RBT_KEY_SIZE_T height,
610  va_list args
611 )
612 {
613  int * is_subset;
614  RBT_NODE_T * target;
615 
616  if (! RBT_VALUE_IS_NULL(key_data->node->value))
617  {
618  target = va_arg(args, RBT_NODE_T *);
619  is_subset = va_arg(args, int *);
620 
621  target = RBT_NODE_RETRIEVE(
622  target, key_data->key, key_data->bits, RBT_RETRIEVE_ACTION_NOTHING, RBT_VALUE_NULL, NULL
623  );
624  if (target == NULL)
625  {
626  * is_subset = 0;
627  return 1;
628  }
629  }
630  return 0;
631 }
632 
652 int
654 {
655  int is_subset;
656  is_subset = 1;
657  /*
658  a and b are "switched" here compared to previous functions because each node
659  in `a` must be found in `b`, i.e. `a` is traversed.
660  */
661  RBT_NODE_TRAVERSE_WITH_KEY(a, _RBT_SET_IS_SUBSET_TRAVERSE, b, &is_subset);
662  return is_subset;
663 }
664 
665 
666 
668 
678 void
679 RBT_SET_ADD(RBT_NODE_T * set, RBT_KEY_T item)
680 {
681  RBT_INSERT(set, item, 1);
682 }
683 
693 void
694 RBT_SET_REMOVE(RBT_NODE_T * set, RBT_KEY_T item)
695 {
696  RBT_DELETE(set, item);
697 }
698 
708 int
709 RBT_SET_INCLUDES(RBT_NODE_T * set, RBT_KEY_T item)
710 {
711  return RBT_HAS_KEY(set, item);
712 }
713 
RBT_VALUE_T RBT_DELETE(RBT_NODE_T *node, RBT_KEY_T key)
Definition: wrapper.h:312
void RBT_SET_MODIFY_UNION(RBT_NODE_T *a, RBT_NODE_T *b)
Definition: set.h:274
RBT_KEY_SIZE_T bits
Number of significant bits in the key.
Definition: node.h:492
int RBT_HAS_KEY(RBT_NODE_T *node, RBT_KEY_T key)
Definition: wrapper.h:357
RBT_NODE_T * node
The associated node.
Definition: node.h:508
int RBT_SET_IS_SUBSET(RBT_NODE_T *a, RBT_NODE_T *b)
Definition: set.h:653
void RBT_SET_MODIFY_DIFFERENCE(RBT_NODE_T *a, RBT_NODE_T *b)
Definition: set.h:360
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
int RBT_SET_INCLUDES(RBT_NODE_T *set, RBT_KEY_T item)
Definition: set.h:709
void RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION(RBT_NODE_T *a, RBT_NODE_T *b)
Definition: set.h:567
Definition: common.h:417
Definition: common.h:340
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
void RBT_SET_MODIFY_INTERSECTION(RBT_NODE_T *a, RBT_NODE_T *b)
Definition: set.h:482
void RBT_SET_REMOVE(RBT_NODE_T *set, RBT_KEY_T item)
Definition: set.h:694
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_NODE_T * RBT_NODE_NEW()
Create a new tree.
Definition: node.h:1759
RBT_NODE_T * RBT_SET_INTERSECTION(RBT_NODE_T *a, RBT_NODE_T *b)
Definition: set.h:503
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
RBT_VALUE_T RBT_INSERT(RBT_NODE_T *node, RBT_KEY_T key, RBT_VALUE_T value)
Definition: wrapper.h:265
RBT_NODE_T * RBT_SET_DIFFERENCE(RBT_NODE_T *a, RBT_NODE_T *b)
Definition: set.h:423
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
#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_SET_ADD(RBT_NODE_T *set, RBT_KEY_T item)
Definition: set.h:679
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
RBT_NODE_T * RBT_SET_UNION(RBT_NODE_T *a, RBT_NODE_T *b)
Definition: set.h:296
RBT_NODE_T * RBT_SET_EXCLUSIVE_DISJUNCTION(RBT_NODE_T *a, RBT_NODE_T *b)
Definition: set.h:587