Rabbit Tree
Radix bit tries for implementing associative arrays and sets in C.
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
key.h
Go to the documentation of this file.
1 
76 #include <stdio.h>
77 
78 #include "common.h"
79 #include "debug.h"
80 
85 #ifndef RBT_KEY_H_PREFIX_
86 #error RBT_KEY_H_PREFIX_ is not defined.
87 #endif // RBT_KEY_H_PREFIX_
88 
89 #ifndef RBT_PIN_T
90 #error RBT_PIN_T is not defined.
91 #endif // RBT_PIN_T
92 
93 #ifndef RBT_KEY_SIZE_T
94 #error RBT_KEY_SIZE_T is not defined.
95 #endif // RBT_KEY_SIZE_T
96 
97 #ifndef RBT_KEY_SIZE_T_FORMAT
98 #error RBT_KEY_SIZE_T_FORMAT is not defined.
99 #endif // RBT_KEY_SIZE_T_FORMAT
100 
101 
102 /*
103  Typedef these so that they are not lost if the preceding macros are redefined
104  for another inclusion.
105 */
106 typedef RBT_PIN_T RBT_TOKEN_2_W(RBT_KEY_H_PREFIX_, pin_t);
107 typedef RBT_KEY_SIZE_T RBT_TOKEN_2_W(RBT_KEY_H_PREFIX_, key_size_t);
108 
109 #undef RBT_FPRINT_BITS
110 #define RBT_FPRINT_BITS RBT_TOKEN_2_W(RBT_KEY_H_PREFIX_, fprint_bits)
111 
112 #undef RBT_COMMON_BIT_PREFIX_LEN
113 #define RBT_COMMON_BIT_PREFIX_LEN RBT_TOKEN_2_W(RBT_KEY_H_PREFIX_, common_bit_prefix_len)
114 
119 /*
120  The conditional definitions may be unnecessary if multiplication by 1 would be
121  optimized by the compiler, but it does not hurt and it assures that the more
122  efficient method is used.
123 */
127 #undef RBT_PIN_SIZE
128 #define RBT_PIN_SIZE sizeof(RBT_PIN_T)
129 
132 #undef RBT_PIN_SIZE_BITS
133 #define RBT_PIN_SIZE_BITS (RBT_PIN_SIZE * BITS_PER_BYTE)
134 
141 #undef BITS_TO_PINS
142 #define BITS_TO_PINS(x) DIV_UP(x, RBT_PIN_SIZE_BITS)
143 
150 #undef PINS_TO_BYTES
151 #define PINS_TO_BYTES(x) ((x) * RBT_PIN_SIZE)
152 
161 #undef BITS_TO_PINS_TO_BYTES
162 #define BITS_TO_PINS_TO_BYTES(x) PINS_TO_BYTES(BITS_TO_PINS(x))
163 
164 
165 
166 
167 
168 
169 
170 
171 
188 void
189 RBT_FPRINT_BITS(FILE * fd, RBT_PIN_T * key, RBT_KEY_SIZE_T n, RBT_KEY_SIZE_T skip)
190 {
191  int i;
192  for (i = skip; n > 0; i++,n--)
193  {
194  while (i >= RBT_PIN_SIZE_BITS)
195  {
196  i -= RBT_PIN_SIZE_BITS;
197  key ++;
198  }
199  fprintf(fd, "%d", (MOST_SIGNIFICANT_BIT(typeof(key[0])) & (key[0] << i)) > 0);
200  }
201 }
202 
203 
204 
205 
206 
223 #undef RBT_DIVMOD
224 #define RBT_DIVMOD(a,b,c,d) \
225 c = a / b; \
226 d = a % b
227 
228 
229 
230 
249 RBT_KEY_SIZE_T
251  RBT_PIN_T * a,
252  RBT_PIN_T * b,
253  RBT_KEY_SIZE_T max
254 )
255 {
256  RBT_PIN_T c;
257  RBT_KEY_SIZE_T length;
258 
259  length = 0;
260 
261  while (length < max && * a == * b)
262  {
263  length += RBT_PIN_SIZE_BITS;
264  a ++;
265  b ++;
266  }
267  if (length < max)
268  {
269  c = *a ^ *b;
270 #ifdef __GNUC__
271  /*
272  Make use of the GCC builtins:
273  http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
274 
275  TODO
276  At some point check if this is even worth it. Also consider checking
277  compatibility of the returned int with RBT_KEY_SIZE_T. Under normal operation
278  RBT_KEY_SIZE_T will be able to hold the value, but there may be overhead due
279  to conversion between types.
280  */
281  if (__builtin_types_compatible_p(RBT_PIN_T, unsigned int))
282  {
283  debug_print("__builtin_clz\n");
284  length += (RBT_KEY_SIZE_T) __builtin_clz(c);
285  }
286  else if (__builtin_types_compatible_p(RBT_PIN_T, unsigned long int))
287  {
288  debug_print("__builtin_clzl\n");
289  length += (RBT_KEY_SIZE_T) __builtin_clzl(c);
290  }
291  else if (__builtin_types_compatible_p(RBT_PIN_T, unsigned long long int))
292  {
293  debug_print("__builtin_clzll\n");
294  length += (RBT_KEY_SIZE_T) __builtin_clzll(c);
295  }
296  else
297  {
298 #endif // __GNUC__
299 // debug_print("loop\n");
300  /*
301  The condition above ensures that the length is less than the max, so it
302  cannot be exceeded here and there is no need to check before returning it.
303 
304  The leading 0's represent common bits due to the XOR operation above. The
305  previous loop ensures that *a and *b are not identical so there must be
306  at least one bit in c. By shifting it left and checking if the value is
307  less than MOST_SIGNIFICANT_BIT we can count the leading zeros and thus the
308  number of common bits.
309  */
310  while (c < MOST_SIGNIFICANT_BIT_W(RBT_PIN_T) && length < max)
311  {
312  c <<= 1;
313  length += 1;
314  }
315  return length;
316 #ifdef __GNUC__
317  }
318  return (length > max) ? max : length;
319 #endif // __GNUC__
320  }
321  else
322  {
323  return max;
324  }
325 }
#define MOST_SIGNIFICANT_BIT_W(x)
A wrapper for MOST_SIGNIFICANT_BIT() to ensure macro expansion.
Definition: common.h:283
#define RBT_PIN_SIZE_BITS
Definition: key.h:133
#define RBT_TOKEN_2_W(a, b)
A wrapper for RBT_TOKEN_2() to ensure macro expansion.
Definition: common.h:240
void RBT_FPRINT_BITS(FILE *fd, RBT_PIN_T *key, RBT_KEY_SIZE_T n, RBT_KEY_SIZE_T skip)
Definition: key.h:189
#define MOST_SIGNIFICANT_BIT(x)
The most significant bit of the given integer's type.
Definition: common.h:274
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
#define debug_print(msg)
Definition: debug.h:160