Rabbit Tree
Radix bit tries for implementing associative arrays and sets in C.
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
wrapper.h
Go to the documentation of this file.
1 
41 #include "common.h"
42 #include "debug.h"
43 
44 #ifdef ONLY_FOR_DOXYGEN
45 #include "node.h"
46 #endif //ONLY_FOR_DOXYGEN
47 
48 
53 #ifndef RBT_WRAPPER_H_PREFIX_
54 #error RBT_WRAPPER_H_PREFIX_ is not defined.
55 #endif // RBT_WRAPPER_H_PREFIX_
56 
57 #ifndef RBT_KEY_T
58 #error RBT_KEY_T is not defined.
59 #endif // RBT_KEY_T
60 
61 #ifndef RBT_KEY_COUNT_BITS
62 #error RBT_KEY_COUNT_BITS is not defined.
63 #endif // RBT_KEY_COUNT_BITS
64 
65 #ifndef RBT_KEY_PTR
66 #error RBT_KEY_PTR is not defined.
67 #endif // RBT_KEY_PTR
68 
69 #ifndef RBT_KEY_FPRINT
70 #error RBT_KEY_FPRINT is not defined.
71 #endif // RBT_KEY_FPRINT
72 
76 typedef RBT_KEY_T RBT_TOKEN_2_W(RBT_WRAPPER_H_PREFIX_, key_t);
77 
78 #undef RBT_NODE_QUERY_WRAPPER
79 #define RBT_NODE_QUERY_WRAPPER RBT_TOKEN_2_W(RBT_WRAPPER_H_PREFIX_, node_query_wrapper)
80 
81 #undef RBT_DELETE
82 #define RBT_DELETE RBT_TOKEN_2_W(RBT_WRAPPER_H_PREFIX_, delete)
83 
84 #undef RBT_HAS_KEY
85 #define RBT_HAS_KEY RBT_TOKEN_2_W(RBT_WRAPPER_H_PREFIX_, has_key)
86 
87 #undef RBT_INSERT
88 #define RBT_INSERT RBT_TOKEN_2_W(RBT_WRAPPER_H_PREFIX_, insert)
89 
90 #undef RBT_RETRIEVE
91 #define RBT_RETRIEVE RBT_TOKEN_2_W(RBT_WRAPPER_H_PREFIX_, retrieve)
92 
93 #undef RBT_SWAP
94 #define RBT_SWAP RBT_TOKEN_2_W(RBT_WRAPPER_H_PREFIX_, swap)
95 
96 /*
97  When a given key type is cast into the internal key type, care must be taken
98  to prevent reads past the boundary of allocated memory. This is best
99  illustrated with an example, however contrived.
100 
101  If the user chooses an internal key type that uses arrays of `unsigned int`s
102  (either by explicit choice or by using e.g. uint_fast8_t on some platform),
103  but then chooses a key type of "char", then the following situation would
104  arise, where "x" represents an allocated byte and "." an unallocated byte, and
105  `int`s are 32 bits:
106 
107  key: x...
108  internal key: xxxx
109 
110  Even if the various functions will only ever compare the first 8 bits, casting
111  the key to an internal key will dereference 3 unallocated bytes. The behavior
112  is undefined. If there were a guarantee that it would never segfault then it
113  would not be a problem, because the value of those bits will never be directly
114  accessed.
115 
116  Unfortunately, segfaults may occur, so the best solution is to allocate memory
117  and copy over the allocated bytes from the key. The rest of the bytes can be
118  left uninitialized as they have no effect.
119 
120  Of course, if the internal key is an array of single-byte elements then this
121  is never a concern, nor is it a concern if the two types share a common factor
122  greater than 1, as a cast will not run past the bountary in that case.
123 */
124 
125 #undef RBT_PINS_FIXED
126 
129 #undef RBT_PINS_FIXED
130 #define RBT_PINS_FIXED ((RBT_KEY_SIZE_FIXED + (RBT_PIN_SIZE - 1)) / RBT_PIN_SIZE)
131 
150 #undef _RBT_NODE_QUERY_WITH_CAST_KEY
151 #ifdef RBT_KEY_SIZE_FIXED
152  #define _RBT_NODE_QUERY_WITH_CAST_KEY(node, key, bits, action, value) \
153  do \
154  { \
155  if (RBT_PIN_SIZE != 1) \
156  { \
157  if (RBT_KEY_SIZE_FIXED % RBT_PIN_SIZE) \
158  { \
159  RBT_PIN_T cast_key[RBT_PINS_FIXED]; \
160  memset(cast_key, 0, sizeof(cast_key)); \
161  memcpy(cast_key, RBT_KEY_PTR(key), RBT_KEY_SIZE_FIXED); \
162  bits = sizeof(cast_key) * BITS_PER_BYTE; \
163  return RBT_NODE_QUERY(node, cast_key, bits, action, value); \
164  } \
165  else \
166  { \
167  return RBT_NODE_QUERY(node, (RBT_PIN_T *) RBT_KEY_PTR(key), bits, action, value); \
168  } \
169  } \
170  else \
171  { \
172  return RBT_NODE_QUERY(node, (RBT_PIN_T *) RBT_KEY_PTR(key), bits, action, value); \
173  } \
174  } \
175  while (0)
176 
177 #else
178  #define _RBT_NODE_QUERY_WITH_CAST_KEY(node, key, bits, action, value) \
179  do \
180  { \
181  if (RBT_PIN_SIZE != 1) \
182  { \
183  int q; \
184  int r; \
185  RBT_DIVMOD(bits, RBT_PIN_SIZE_BITS, q, r); \
186  if (r) \
187  { \
188  q ++; \
189  RBT_PIN_T cast_key[q]; \
190  memset(cast_key, 0, sizeof(cast_key)); \
191  memcpy(cast_key, RBT_KEY_PTR(key), (bits + (BITS_PER_BYTE - 1)) / BITS_PER_BYTE); \
192  bits = q * RBT_PIN_SIZE_BITS; \
193  return RBT_NODE_QUERY(node, cast_key, bits, action, value); \
194  } \
195  else \
196  { \
197  return RBT_NODE_QUERY(node, (RBT_PIN_T *) RBT_KEY_PTR(key), bits, action, value); \
198  } \
199  } \
200  else \
201  { \
202  return RBT_NODE_QUERY(node, (RBT_PIN_T *) RBT_KEY_PTR(key), bits, action, value); \
203  } \
204  } \
205  while (0)
206 #endif //RBT_KEY_SIZE_FIXED
207 
234  RBT_NODE_T * node,
235  RBT_KEY_T key,
236  rbt_query_action_t action,
237  RBT_VALUE_T value
238 )
239 {
240  RBT_KEY_SIZE_T bits;
241  bits = RBT_KEY_COUNT_BITS(key);
242 // _RBT_NODE_QUERY_WITH_CAST_KEY(cast_key, key, bits);
243 // return RBT_NODE_QUERY(node, cast_key, bits, action, value);
244  _RBT_NODE_QUERY_WITH_CAST_KEY(node, key, bits, action, value);
245 }
246 
247 
248 
266  RBT_NODE_T * node,
267  RBT_KEY_T key,
268  RBT_VALUE_T value
269 )
270 {
271  return RBT_NODE_QUERY_WRAPPER(node, key, RBT_QUERY_ACTION_INSERT, value);
272 }
273 
274 
275 
290  RBT_NODE_T * node,
291  RBT_KEY_T key
292 )
293 {
294  return RBT_NODE_QUERY_WRAPPER(node, key, RBT_QUERY_ACTION_RETRIEVE, RBT_VALUE_NULL);
295 }
296 
297 
298 
313  RBT_NODE_T * node,
314  RBT_KEY_T key
315 )
316 {
317  return RBT_NODE_QUERY_WRAPPER(node, key, RBT_QUERY_ACTION_DELETE, RBT_VALUE_NULL);
318 }
319 
320 
321 
339  RBT_NODE_T * node,
340  RBT_KEY_T key,
341  RBT_VALUE_T value
342 )
343 {
344  return RBT_NODE_QUERY_WRAPPER(node, key, RBT_QUERY_ACTION_SWAP, value);
345 }
346 
347 
348 
349 
351 
356 int
357 RBT_HAS_KEY(RBT_NODE_T * node, RBT_KEY_T key)
358 {
359  return !RBT_VALUE_IS_NULL(RBT_RETRIEVE(node, key));
360 }
rbt_query_action_t
Query action for RBT_NODE_QUERY().
Definition: common.h:407
RBT_VALUE_T RBT_DELETE(RBT_NODE_T *node, RBT_KEY_T key)
Definition: wrapper.h:312
RBT_VALUE_T RBT_SWAP(RBT_NODE_T *node, RBT_KEY_T key, RBT_VALUE_T value)
Definition: wrapper.h:338
int RBT_HAS_KEY(RBT_NODE_T *node, RBT_KEY_T key)
Definition: wrapper.h:357
RBT_VALUE_T RBT_VALUE_T
The node's value type.
Definition: node.h:409
#define RBT_TOKEN_2_W(a, b)
A wrapper for RBT_TOKEN_2() to ensure macro expansion.
Definition: common.h:240
RBT_NODE_T * node
The node on the stack.
Definition: node.h:3260
Definition: common.h:412
Definition: common.h:417
RBT_VALUE_T RBT_INSERT(RBT_NODE_T *node, RBT_KEY_T key, RBT_VALUE_T value)
Definition: wrapper.h:265
#define RBT_VALUE_IS_NULL(value)
Definition: node.h:395
Rabbit Tree node type.
Definition: node.h:418
RBT_VALUE_T RBT_NODE_QUERY_WRAPPER(RBT_NODE_T *node, RBT_KEY_T key, rbt_query_action_t action, RBT_VALUE_T value)
Definition: wrapper.h:233
Definition: common.h:422
RBT_VALUE_T RBT_RETRIEVE(RBT_NODE_T *node, RBT_KEY_T key)
Definition: wrapper.h:289
Definition: common.h:435