The FreeRADIUS server  $Id: 15bac2a4c627c01d1aa2047687b3418955ac7f00 $
trie.c
Go to the documentation of this file.
1 /*
2  * This library is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU Lesser General Public
4  * License as published by the Free Software Foundation; either
5  * version 2.1 of the License, or (at your option) any later version.
6  *
7  * This library is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
10  * Lesser General Public License for more details.
11  *
12  * You should have received a copy of the GNU Lesser General Public
13  * License along with this library; if not, write to the Free Software
14  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
15  */
16 
17 /** Path-compressed prefix tries
18  *
19  * @file src/lib/util/trie.c
20  *
21  * @copyright 2017 Alan DeKok (aland@freeradius.org)
22  */
23 RCSID("$Id: 344a24564536764b47335f1d1158506b1711c981 $")
24 
25 #include <freeradius-devel/util/dict.h>
26 #include <freeradius-devel/util/misc.h>
27 #include <freeradius-devel/util/syserror.h>
28 #include <freeradius-devel/util/trie.h>
29 
30 
31 /*
32  * This file implements path-compressed, level-compressed
33  * patricia tries. The original research paper is:
34  *
35  * https://www.nada.kth.se/~snilsson/publications/Dynamic-trie-compression-implementation/
36  *
37  * The functionality has been extended to include intermediate
38  * nodes which consume 0 bits, but which hold user context data.
39  * These intermediate nodes allow for "longest prefix" matching.
40  * For example, in networking, you can have a routing table entry
41  * with 0/0 leading to one destination, and 10/8 leading to a
42  * different one. Looking up an address in the 10/8 network will
43  * return the 10/8 destination. Looking up any other address
44  * will return the default destination.
45  *
46  * In addition, we desire the ability to add and delete nodes
47  * dynamically. In the example given above, this means that
48  * after deleting 10/8, the trie should contain only the 0/0
49  * network and associated destination.
50  *
51  * As of yet, it does not do level compression. This can be
52  * added without (hopefully) too much work. That would require
53  * an additional step to "normalize" the trie.
54  *
55  * This code could be extended to do packet matching, through the
56  * inclusion of "don't care" paths. e.g. parsing an IP header,
57  * where the src/dst IP addresses are 32-bit "don't care" fields.
58  *
59  * It could also be extended via "count" paths, where the path
60  * holds a count that is used in another part of the trie. For
61  * example, in RADIUS. The attribute encoding is one byte
62  * attribute, one byte length, followed by "length - 2" bytes of
63  * data. At that point though, you might as well just use Ragel.
64  */
65 
66 /** Enable path compression (or not)
67  *
68  * With path compression, long sequences of bits are stored as a
69  * path, e.g. "abcdef". Without path compression, we would have to
70  * create a large number of intermediate 2^N-way nodes, all of which
71  * would have only one edge.
72  */
73 #if !defined(NO_PATH_COMPRESSION) && !defined(WITH_PATH_COMPRESSION)
74 #define WITH_PATH_COMPRESSION
75 #endif
76 
77 //#define WITH_NODE_COMPRESSION
78 
79 #ifdef WITH_NODE_COMPRESSION
80 #ifndef WITH_PATH_COMPRESSION
81 #define WITH_PATH_COMPRESSION
82 #endif
83 
84 #ifndef MAX_COMP_BITS
85 #define MAX_COMP_BITS (8)
86 #endif
87 
88 #ifndef MAX_COMP_EDGES
89 #define MAX_COMP_EDGES (4)
90 #endif
91 
92 #endif /* WITH_NODE_COMPRESSION */
93 
94 #define MAX_KEY_BYTES (256)
95 #define MAX_KEY_BITS (MAX_KEY_BYTES * 8)
96 
97 #ifndef MAX_NODE_BITS
98 #define MAX_NODE_BITS (4)
99 #endif
100 
101 /** Internal sanity checks for debugging.
102  *
103  * Tries are complex. So we have verification routines for every
104  * type of node. These routines are called from within the trie
105  * manipulation functions. If the trie manipulation has a bug, the
106  * verification routines are likely to catch some of the more
107  * egregious issues.
108  */
109 DIAG_OFF(unused-macros)
110 #ifdef TESTING
111 #define WITH_TRIE_VERIFY (1)
112 # define MPRINT(...) fprintf(stderr, ## __VA_ARGS__)
113 
114  /* define this to be MPRINT for additional debugging */
115 # define MPRINT2(...)
116 # define MPRINT3(...)
117 static void trie_sprint(fr_trie_t *trie, uint8_t const *key, int start_bit, int lineno);
118 #else
119 # define MPRINT(...)
120 # define MPRINT2(...)
121 # define MPRINT3(...)
122 #define trie_sprint(_trie, _key, _start_bit, _lineno)
123 #endif
124 
125 #ifdef WITH_TRIE_VERIFY
126 static int trie_verify(fr_trie_t *trie);
127 //#define VERIFY(_x) fr_cond_assert(trie_verify((fr_trie_t *) _x) == 0)
128 #define VERIFY(_x) if (trie_verify((fr_trie_t *) _x) < 0) do { fprintf(stderr, "FAIL VERIFY at %d - %s\n", __LINE__, fr_strerror()); fr_cond_assert(0); } while (0)
129 #else
130 #define VERIFY(_x)
131 #endif
132 
133 /*
134  * Macros to swap one for the other.
135  */
136 #define BITSOF(_x) ((_x) * 8)
137 #define BYTEOF(_x) ((_x) >> 3)
138 #define BYTES(_x) (((_x) + 0x07) >> 3)
139 DIAG_ON(unused-macros)
140 
141 
142 // @todo - do level compression
143 // stop merging nodes if a key ends at the top of the level
144 // otherwise merge so we have at least 2^4 way fan-out, but no more than 2^8
145 // that should be a decent trade-off between memory and speed
146 
147 // @todo - generalized function to normalize the trie.
148 
149 
150 static uint8_t start_bit_mask[8] = {
151  0xff, 0x7f, 0x3f, 0x1f,
152  0x0f, 0x07, 0x03, 0x01
153 };
154 
155 static uint8_t used_bit_mask[8] = {
156  0x80, 0xc0, 0xe0, 0xf0,
157  0xf8, 0xfc, 0xfe, 0xff,
158 };
159 
160 #if 0
161 /*
162  * For testing and debugging.
163  */
164 static char const *spaces = " ";
165 #endif
166 
167 
168 #if defined(WITH_PATH_COMPRESSION) || defined(TESTING)
169 /*
170  * Table of how many leading bits there are in KEY1^KEY2.
171  */
172 static uint8_t xor2lcp[256] = {
173  8, 7, 6, 6,
174  5, 5, 5, 5, /* 4x 5 */
175  4, 4, 4, 4, /* 8x 4 */
176  4, 4, 4, 4,
177  3, 3, 3, 3, /* 16x 3 */
178  3, 3, 3, 3,
179  3, 3, 3, 3,
180  3, 3, 3, 3,
181  2, 2, 2, 2, /* 32x 2 */
182  2, 2, 2, 2,
183  2, 2, 2, 2,
184  2, 2, 2, 2,
185  2, 2, 2, 2,
186  2, 2, 2, 2,
187  2, 2, 2, 2,
188  2, 2, 2, 2,
189  1, 1, 1, 1, /* 64x 1 */
190  1, 1, 1, 1,
191  1, 1, 1, 1,
192  1, 1, 1, 1,
193  1, 1, 1, 1,
194  1, 1, 1, 1,
195  1, 1, 1, 1,
196  1, 1, 1, 1,
197  1, 1, 1, 1,
198  1, 1, 1, 1,
199  1, 1, 1, 1,
200  1, 1, 1, 1,
201  1, 1, 1, 1,
202  1, 1, 1, 1,
203  1, 1, 1, 1,
204  1, 1, 1, 1,
205  0, 0, 0, 0, /* 128x 0 */
206  0, 0, 0, 0,
207  0, 0, 0, 0,
208  0, 0, 0, 0,
209  0, 0, 0, 0,
210  0, 0, 0, 0,
211  0, 0, 0, 0,
212  0, 0, 0, 0,
213  0, 0, 0, 0,
214  0, 0, 0, 0,
215  0, 0, 0, 0,
216  0, 0, 0, 0,
217  0, 0, 0, 0,
218  0, 0, 0, 0,
219  0, 0, 0, 0,
220  0, 0, 0, 0,
221 };
222 
223 
224 /** Get the longest prefix of the two keys.
225  *
226  */
227 static int fr_trie_key_lcp(uint8_t const *key1, int keylen1, uint8_t const *key2, int keylen2, int start_bit)
228 {
229  int lcp, end_bit;
230 
231  if (!keylen1 || !keylen2) return 0;
232  fr_cond_assert((start_bit & 0x07) == start_bit);
233 
234  end_bit = keylen1;
235  if (end_bit > keylen2) end_bit = keylen2;
236  end_bit += start_bit;
237 
238  MPRINT2("%.*sLCP %02x%02x %02x%02x start %d length %d, %d\n",
239  start_bit, spaces, key1[0], key1[1], key2[0], key2[1], start_bit, keylen1, keylen2);
240 
241  lcp = 0;
242 
243  while (end_bit > 0) {
244  int num_bits;
245  uint8_t cmp1, cmp2, xor;
246 
247  MPRINT2("END %d\n", end_bit);
248 
249  /*
250  * Default to grabbing the whole byte.
251  */
252  cmp1 = key1[0];
253  cmp2 = key2[0];
254  num_bits = 8;
255 
256  /*
257  * The LCP ends in this byte. Mask off the
258  * trailing bits so that they don't affect the
259  * result.
260  */
261  if (end_bit < 8) {
262  cmp1 &= used_bit_mask[end_bit - 1];
263  cmp2 &= used_bit_mask[end_bit - 1];
264  num_bits = end_bit;
265  }
266 
267  /*
268  * The key doesn't start on the leading bit.
269  * Shift the data left until it does start there.
270  */
271  if ((start_bit & 0x07) != 0) {
272  cmp1 <<= start_bit;
273  cmp2 <<= start_bit;
274  num_bits -= start_bit;
275  end_bit -= start_bit;
276 
277  /*
278  * For subsequent bytes we start on a
279  * byte boundary.
280  */
281  start_bit = 0;
282  }
283 
284  xor = cmp1 ^ cmp2;
285 
286  /*
287  * A table lookup is faster than looping through
288  * the bits. If the LCP is smaller than the
289  * number of bits we're looking up, we can stop.
290  *
291  * On the other hand, if it returns the same or
292  * too many bits, just do another round through
293  * the loop, so that we can update the pointers
294  * and check the exit conditions.
295  */
296  if (xor2lcp[xor] < num_bits) {
297  MPRINT2("RETURN %d + %d\n", lcp, xor2lcp[xor]);
298  return lcp + xor2lcp[xor];
299  }
300 
301  /*
302  * The LCP may be longer than num_bits if we're
303  * checking the first byte, which has only
304  * "start_bit" things we care about. Ignore that
305  * case, and just keep going.
306  */
307 
308  lcp += num_bits;
309  end_bit -= num_bits;
310  key1++;
311  key2++;
312  }
313 
314  return lcp;
315 }
316 #endif
317 
318 //#define HEX_DUMP
319 
320 #ifdef HEX_DUMP
321 static void hex_dump(FILE *fp, char const *msg, uint8_t const *key, int start_bit, int end_bit)
322 {
323  int i;
324 
325  fprintf(fp, "%s\ts=%zd e=%zd\t\t", msg, start_bit, end_bit);
326 
327  for (i = 0; i < BYTES(end_bit); i++) {
328  fprintf(fp, "%02x ", key[i]);
329  }
330  fprintf(fp, "\n");
331 }
332 #endif
333 
334 /** Return a chunk of a key (in the low bits) for use in 2^N node de-indexing
335  *
336  */
337 static CC_HINT(nonnull) uint16_t get_chunk(uint8_t const *key, uint32_t start_bit, uint32_t num_bits)
338 {
339  uint16_t chunk;
340  int end_bit;
341 
342  fr_cond_assert(num_bits > 0);
343  fr_cond_assert(num_bits <= 16);
344 
345  /*
346  * Normalize it so that the caller doesn't have to.
347  */
348  if (start_bit > 7) {
349  key += BYTEOF(start_bit);
350  start_bit &= 0x07;
351  }
352 
353  /*
354  * Special-case 1-bit lookups.
355  */
356  if (num_bits == 1) {
357  chunk = key[0] >> (7 - start_bit);
358  chunk &= 0x01;
359  return chunk;
360  }
361 
362  /*
363  * Catch some simple use-cases.
364  */
365  if (start_bit == 0) {
366  if (num_bits < 7) return key[0] >> (8 - num_bits);
367  if (num_bits == 8) return key[0];
368 
369  chunk = (key[0] << 8) | key[1];
370  if (num_bits < 16) chunk >>= (16 - num_bits);
371  fr_cond_assert(chunk < (1 << num_bits));
372  return chunk;
373  }
374 
375  /*
376  * Load the first byte and mask off the bits we don't
377  * want.
378  */
379  chunk = key[0] & start_bit_mask[start_bit & 0x07];
380 
381  fr_cond_assert(BYTEOF(start_bit + num_bits - 1) <= 1);
382 
383  if (BYTEOF(start_bit + num_bits - 1) != 0) {
384  chunk <<= 8;
385  chunk |= key[1];
386  }
387 
388  /*
389  * The bits we want are now all in the higher bits
390  * of "chunk". But we only want some of them.
391  *
392  * Shift the chunk so that the bits we want are now in
393  * the low bits.
394  */
395  end_bit = (start_bit + num_bits) & 0x07;
396  if (end_bit != 0) chunk >>= 8 - end_bit;
397 
398  fr_cond_assert(chunk < (1 << num_bits));
399 
400  return chunk;
401 }
402 
403 
404 static void write_chunk(uint8_t *out, int start_bit, int num_bits, uint16_t chunk) CC_HINT(nonnull);
405 
406 /** Write a chunk to an output buffer
407  *
408  */
409 static void write_chunk(uint8_t *out, int start_bit, int num_bits, uint16_t chunk)
410 {
411  fr_cond_assert(chunk < (1 << num_bits));
412 
413  /*
414  * Normalize it so that the caller doesn't have to.
415  */
416  if (start_bit > 7) {
417  out += BYTEOF(start_bit);
418  start_bit &= 0x07;
419  }
420 
421  /*
422  * Special-case 1-bit writes.
423  */
424  if (num_bits == 1) {
425  out[0] &= ~((1 << (7 - start_bit)) - 1);
426  out[0] |= chunk << (7 - start_bit);
427  return;
428  }
429 
430  /*
431  * Ensure that we don't write to more than 2 octets at
432  * the same time.
433  */
434  fr_cond_assert((start_bit + num_bits) <= 16);
435 
436  /*
437  * Shift the chunk to the high bits, but leave room for
438  * start_bit
439  */
440  if ((start_bit + num_bits) < 16) chunk <<= (16 - (start_bit + num_bits));
441 
442  /*
443  * Mask off the first bits that are already in the
444  * output. Then OR in the relevant bits of "chunk".
445  */
446  out[0] &= (used_bit_mask[start_bit] << 1);
447  out[0] |= chunk >> 8;
448 
449  if ((start_bit + num_bits) > 8) {
450  out[1] = chunk & 0xff;
451  }
452 }
453 
454 typedef enum fr_trie_type_t {
455  FR_TRIE_INVALID = 0,
456  FR_TRIE_USER,
457 #ifdef WITH_PATH_COMPRESSION
458  FR_TRIE_PATH,
459 #endif
460 #ifdef WITH_NODE_COMPRESSION
461  FR_TRIE_COMP, /* 4-way, N bits deep */
462 #endif
463  FR_TRIE_NODE,
464 } fr_trie_type_t;
465 
466 #define FR_TRIE_MAX (FR_TRIE_NODE + 1)
467 
468 #ifdef TESTING
469 static int trie_number = 0;
470 
471 #define TRIE_HEADER uint8_t type; uint8_t bits; int number
472 #define TRIE_TYPE_CHECK(_x, _r) do { if ((trie->type == FR_TRIE_INVALID) || \
473  (trie->type >= FR_TRIE_MAX) || \
474  !trie_ ## _x ##_table [trie->type]) { \
475  fr_strerror_printf("unknown trie type %d", trie->type); \
476  return _r; \
477  } } while (0)
478 
479 #else
480 #define TRIE_HEADER uint8_t type; uint8_t bits
481 #define TRIE_TYPE_CHECK(_x, _r)
482 #endif
483 
484 struct fr_trie_s {
485  TRIE_HEADER;
486 
487  fr_trie_t *trie; /* for USER and PATH nodes*/
488 };
489 
490 typedef struct {
491  TRIE_HEADER;
492 
493  int used;
494  fr_trie_t *trie[];
495 } fr_trie_node_t;
496 
497 typedef struct {
498  TRIE_HEADER;
499 
500  fr_trie_t *trie;
501  void *data;
502 } fr_trie_user_t;
503 
504 #ifdef WITH_PATH_COMPRESSION
505 typedef struct {
506  TRIE_HEADER;
507 
508  fr_trie_t *trie;
509 
510  uint16_t chunk;
511  uint8_t key[2];
512 } fr_trie_path_t;
513 #endif
514 
515 #ifdef WITH_NODE_COMPRESSION
516 typedef struct {
517  TRIE_HEADER;
518 
519  int used; //!< number of used entries
520  uint8_t index[MAX_COMP_EDGES];
521  fr_trie_t *trie[MAX_COMP_EDGES];
522 } fr_trie_comp_t;
523 #endif
524 
525 
526 /* ALLOC FUNCTIONS */
527 
528 static fr_trie_node_t *trie_node_alloc(TALLOC_CTX *ctx, int bits)
529 {
530  fr_trie_node_t *node;
531  int size;
532 
533  if ((bits <= 0) || (bits > 8)) {
534  fr_strerror_printf("Invalid bit size %d passed to node alloc", bits);
535  return NULL;
536  }
537 
538  size = 1 << bits;
539 
540  node = (fr_trie_node_t *) talloc_zero_array(ctx, uint8_t, sizeof(fr_trie_node_t) + sizeof(node->trie[0]) * size);
541  if (!node) {
542  fr_strerror_const("failed allocating node trie");
543  return NULL;
544  }
545 
546  talloc_set_name_const(node, "fr_trie_node_t");
547  node->type = FR_TRIE_NODE;
548  node->bits = bits;
549 
550 #ifdef TESTING
551  node->number = trie_number++;
552 #endif
553  return node;
554 }
555 
556 /** Free a fr_trie_t
557  *
558  * We can't use talloc_free(), because we can't talloc_parent the
559  * nodes from each other, as talloc_steal() is O(N). So, we just
560  * recurse manually.
561  */
562 static void trie_free(fr_trie_t *trie)
563 {
564  if (!trie) return;
565 
566  if (trie->type == FR_TRIE_USER) {
567  fr_trie_user_t *user = (fr_trie_user_t *) trie;
568 
569  trie_free(user->trie);
570  talloc_free(user);
571  return;
572  }
573 
574  if (trie->type == FR_TRIE_NODE) {
575  fr_trie_node_t *node = (fr_trie_node_t *) trie;
576  int i;
577 
578  for (i = 0; i < (1 << node->bits); i++) {
579  if (!node->trie[i]) continue; /* save a function call in the common case */
580 
581  trie_free(node->trie[i]);
582  }
583 
584  talloc_free(node);
585  return;
586  }
587 
588 #ifdef WITH_PATH_COMPRESSION
589  if (trie->type == FR_TRIE_PATH) {
590  fr_trie_path_t *path = (fr_trie_path_t *) trie;
591 
592  trie_free(path->trie);
593  talloc_free(path);
594  return;
595  }
596 #endif
597 
598 #ifdef WITH_NODE_COMPRESSION
599  if (trie->type == FR_TRIE_COMP) {
600  fr_trie_comp_t *comp = (fr_trie_comp_t *) trie;
601  int i;
602 
603  for (i = 0; i < comp->used; i++) {
604  trie_free(comp->trie[i]);
605  }
606 
607  talloc_free(comp);
608  return;
609  }
610 #endif
611 }
612 
613 static CC_HINT(nonnull(2)) fr_trie_user_t *fr_trie_user_alloc(TALLOC_CTX *ctx, void const *data)
614 {
615  fr_trie_user_t *user;
616 
617  user = talloc_zero(ctx, fr_trie_user_t);
618  if (!user) {
619  fr_strerror_const("failed allocating user trie");
620  return NULL;
621  }
622 
623  user->type = FR_TRIE_USER;
624  user->data = UNCONST(void *, data);
625 
626 #ifdef TESTING
627  user->number = trie_number++;
628 #endif
629 
630  return user;
631 }
632 
633 #ifdef WITH_PATH_COMPRESSION
634 static CC_HINT(nonnull(2)) fr_trie_path_t *fr_trie_path_alloc(TALLOC_CTX *ctx, uint8_t const *key, int start_bit, int end_bit)
635 {
636  fr_trie_path_t *path;
637 
638  if (end_bit <= start_bit) {
639  fr_strerror_printf("path asked for start >= end, %d >= %d", start_bit, end_bit);
640  return NULL;
641  }
642 
643  /*
644  * Normalize it so that the caller doesn't have to.
645  */
646  if (start_bit > 7) {
647  key += (start_bit >> 3);
648  end_bit -= 8 * (start_bit >> 3);
649  start_bit -= 8 * (start_bit >> 3);
650  }
651 
652  if ((end_bit - start_bit) > 16) {
653  fr_strerror_printf("path asked for too many bits (%d)", end_bit - start_bit);
654  return NULL;
655  }
656 
657  /*
658  * The "end_bit" is the bit we're not using, so it's
659  * allowed to point past the end of path->key.
660  */
661  if ((BYTEOF(start_bit) - BYTEOF(end_bit - 1)) > 1) {
662  fr_strerror_printf("path asked for too many bits / bytes (%d)", end_bit - start_bit);
663  return NULL;
664  }
665 
666  path = talloc_zero(ctx, fr_trie_path_t);
667  if (!path) {
668  fr_strerror_const("failed allocating path trie");
669  return NULL;
670  }
671 
672  path->type = FR_TRIE_PATH;
673  path->bits = end_bit - start_bit;
674  path->chunk = get_chunk(key, start_bit, path->bits);
675 
676  /*
677  * Write the chunk back to the key.
678  */
679  write_chunk(&path->key[0], start_bit, path->bits, path->chunk);
680 
681 #if 0
682  fprintf(stderr, "PATH ALLOC key %02x%02x start %d end %d bits %d == chunk %04x key %02x%02x\n",
683  key[0], key[1],
684  start_bit, end_bit, path->bits,
685  path->chunk, path->key[0], path->key[1]);
686 #endif
687 
688 #ifdef TESTING
689  path->number = trie_number++;
690 #endif
691 
692  return path;
693 }
694 #endif /* WITH_PATH_COMPRESSION */
695 
696 #ifdef WITH_NODE_COMPRESSION
697 static fr_trie_comp_t *fr_trie_comp_alloc(TALLOC_CTX *ctx, int bits)
698 {
699  fr_trie_comp_t *comp;
700 
701  /*
702  * For 1 && 2 bits, just allocate fr_trie_node_t.
703  */
704  if ((bits <= 2) || (bits > MAX_COMP_BITS)) {
705  fr_strerror_printf("Invalid bit size %d passed to comp alloc", bits);
706  return NULL;
707  }
708 
709  comp = talloc_zero(ctx, fr_trie_comp_t);
710  if (!comp) {
711  fr_strerror_const("failed allocating comp trie");
712  return NULL;
713  }
714 
715  comp->type = FR_TRIE_COMP;
716  comp->bits = bits;
717  comp->used = 0;
718 
719 #ifdef TESTING
720  comp->number = trie_number++;
721 #endif
722  return comp;
723 }
724 #endif /* WITH_NODE_COMPRESSION */
725 
726 typedef struct {
727  uint8_t buffer[16]; /* for get_key callbacks */
728  fr_trie_key_t get_key;
729  fr_free_t free_data;
730 } fr_trie_ctx_t;
731 
732 /** Allocate a trie
733  *
734  * @param ctx The talloc ctx.
735  * @param get_key The "get key from object" function.
736  * @param free_data Callback to free data.
737  * @return
738  * - NULL on error
739  * - fr_trie_node_t on success
740  */
741 fr_trie_t *fr_trie_alloc(TALLOC_CTX *ctx, fr_trie_key_t get_key, fr_free_t free_data)
742 {
743  fr_trie_user_t *user;
744  fr_trie_ctx_t *uctx;
745 
746  /*
747  * The trie itself is just a user node with user data
748  * that is the get_key function.
749  */
750  user = (fr_trie_user_t *) fr_trie_user_alloc(ctx, "");
751  if (!user) return NULL;
752 
753  /*
754  * Only the top-level node here can have 'user->data == NULL'
755  */
756  user->data = uctx = talloc_zero(user, fr_trie_ctx_t);
757  if (!user->data) {
758  talloc_free(user);
759  return NULL;
760  }
761 
762  uctx->get_key = get_key;
763  uctx->free_data = free_data;
764 
765  return (fr_trie_t *) user;
766 }
767 
768 /* SPLIT FUNCTIONS */
769 
770 /** Split a node at bits
771  *
772  */
773 static CC_HINT(nonnull(2)) fr_trie_node_t *trie_node_split(TALLOC_CTX *ctx, fr_trie_node_t *node, int bits)
774 {
775  fr_trie_node_t *split;
776  int i, remaining_bits;
777 
778  /*
779  * Can't split zero bits, more bits than the node has, or
780  * a node which has 1 bit.
781  */
782  if ((bits == 0) || (bits >= node->bits) || (node->bits == 1)) {
783  fr_strerror_printf("invalid value for node split (%d / %d)", bits, node->bits);
784  return NULL;
785  }
786 
787  split = trie_node_alloc(ctx, bits);
788  if (!split) return NULL;
789 
790  remaining_bits = node->bits - bits;
791 
792  /*
793  * Allocate the children. For now, just brute-force all
794  * of the children. We take a later pass at optimizing this.
795  */
796  for (i = 0; i < (1 << bits); i++) {
797  int j;
798  fr_trie_node_t *child;
799 
800  child = trie_node_alloc(ctx, remaining_bits);
801  if (!child) {
802  trie_free((fr_trie_t *) split);
803  return NULL;
804  }
805 
806  for (j = 0; j < (1 << remaining_bits); j++) {
807  if (!node->trie[(i << remaining_bits) + j]) continue;
808 
809  child->trie[j] = node->trie[(i << remaining_bits) + j];
810  node->trie[(i << remaining_bits) + j] = NULL; /* so we don't free it when freeing 'node' */
811  child->used++;
812  }
813 
814  if (!child->used) {
815  talloc_free(child); /* no children, so no need to recurse */
816  continue;
817  }
818 
819  split->trie[i] = (fr_trie_t *) child;
820  split->used++;
821  }
822 
823  /*
824  * Note that we do NOT free "node". The caller still
825  * needs it for some activities.
826  */
827  return split;
828 }
829 
830 #ifdef WITH_PATH_COMPRESSION
831 static CC_HINT(nonnull(2)) fr_trie_path_t *trie_path_split(TALLOC_CTX *ctx, fr_trie_path_t *path, int start_bit, int lcp)
832 {
833  fr_trie_path_t *split, *child;
834 #ifdef TESTING
835  uint8_t key[2] = { 0, 0 };
836 #endif
837 
838  if ((lcp <= 0) || (lcp > path->bits) || (start_bit < 0)) {
839  fr_strerror_printf("invalid parameter %d %d to path split", lcp, start_bit);
840  return NULL;
841  }
842 
843  MPRINT3("%.*sSPLIT start %d\n", start_bit, spaces, start_bit);
844  start_bit &= 0x07;
845 
846  split = fr_trie_path_alloc(ctx, &path->key[0], start_bit, start_bit + lcp);
847  if (!split) return NULL;
848 
849  child = fr_trie_path_alloc(ctx, &path->key[0], start_bit + lcp, start_bit + path->bits);
850  if (!child) return NULL;
851 
852  split->trie = (fr_trie_t *) child;
853  child->trie = (fr_trie_t *) path->trie;
854 
855  /*
856  * Don't free "path" until we've successfully inserted
857  * the new key.
858  */
859 
860 #ifdef TESTING
861  /*
862  * Check that the two chunks add up to the parent chunk.
863  */
864  fr_cond_assert(path->chunk == ((split->chunk << (path->bits - lcp)) | child->chunk));
865 
866  /*
867  * Check that the two keys match the parent key.
868  */
869 
870  write_chunk(&key[0], start_bit, split->bits, split->chunk);
871  write_chunk(&key[0], start_bit + split->bits, child->bits, child->chunk);
872 
873  fr_cond_assert(key[0] == path->key[0]);
874  fr_cond_assert(key[1] == path->key[1]);
875 
876  MPRINT3("%.*ssplit %02x%02x start %d split %d -> %02x%02x %02x%02x\n",
877  start_bit, spaces,
878  path->key[0], path->key[1],
879  start_bit, split->bits,
880  split->key[0], split->key[1],
881  child->key[0], child->key[1]);
882 #endif
883 
884  return split;
885 }
886 
887 static CC_HINT(nonnull(2)) fr_trie_t *trie_key_alloc(TALLOC_CTX *ctx, uint8_t const *key, int start_bit, int end_bit, void *data)
888 {
889  fr_trie_path_t *path;
890  int next_bit;
891 
892  if (start_bit == end_bit) return (fr_trie_t *) fr_trie_user_alloc(ctx, data);
893 
894  if (start_bit > end_bit) {
895  fr_strerror_printf("key_alloc asked for start >= end, %d >= %d", start_bit, end_bit);
896  return NULL;
897  }
898 
899  /*
900  * Grab some more bits. Try to grab 16 bits at a time.
901  */
902  next_bit = start_bit + 16 - (start_bit & 0x07);
903 
904  if (next_bit >= end_bit) {
905  path = fr_trie_path_alloc(ctx, key, start_bit, end_bit);
906  if (!path) return NULL;
907 
908  path->trie = (fr_trie_t *) fr_trie_user_alloc(ctx, data);
909  return (fr_trie_t *) path;
910  }
911 
912 
913  path = fr_trie_path_alloc(ctx, key, start_bit, next_bit);
914  if (!path) return NULL;
915 
916  path->trie = (fr_trie_t *) trie_key_alloc(ctx, key, next_bit, end_bit, data);
917  if (!path->trie) {
918  talloc_free(path); /* no children */
919  return NULL;
920  }
921 
922  return (fr_trie_t *) path;
923 }
924 #else /* WITH_PATH_COMPRESSION */
925 static CC_HINT(nonnull(2)) fr_trie_t *trie_key_alloc(TALLOC_CTX *ctx, uint8_t const *key, int start_bit, int end_bit, void *data)
926 {
927  fr_trie_node_t *node;
928  uint16_t chunk;
929  int bits = MAX_NODE_BITS;
930 
931  if (start_bit == end_bit) {
932  return (fr_trie_t *) fr_trie_user_alloc(ctx, data);
933  }
934 
935  bits = end_bit - start_bit;
936  if (bits > MAX_NODE_BITS) bits = MAX_NODE_BITS;
937 
938  /*
939  * We only want one edge here.
940  */
941  node = trie_node_alloc(ctx, bits);
942  if (!node) return NULL;
943 
944  chunk = get_chunk(key, start_bit, node->bits);
945  node->trie[chunk] = trie_key_alloc(ctx, key, start_bit + node->bits, end_bit, data);
946  if (!node->trie[chunk]) {
947  talloc_free(node); /* no children */
948  return NULL;
949  }
950  node->used++;
951 
952  return (fr_trie_t *) node;
953 }
954 #endif
955 
956 
957 #if 0
958 /** Split a compressed at bits
959  *
960  */
961 #ifdef WITH_NODE_COMPRESSION
962 static fr_trie_t *trie_comp_split(TALLOC_CTX *ctx, fr_trie_comp_t *comp, int start_bit, int bits)
963 {
964  int i;
965  fr_trie_comp_t *split;
966 
967  /*
968  * Can't split zero bits, more bits than the node has, or
969  * a node which has 1 bit.
970  */
971  if ((bits == 0) || (bits >= comp->bits)) {
972  fr_strerror_printf("invalid value for comp split (%d / %d)", bits, comp->bits);
973  return NULL;
974  }
975 
976  split = fr_trie_comp_alloc(ctx, bits);
977  if (!split) return NULL;
978 
979  if (start_bit > 7) start_bit &= 0x07;
980 
981  // walk over the edges, seeing how many edges have the same before bits
982  //
983  // if all have the same bits, then split by creating a path
984  // node, and then a child split node.
985 
986  /*
987  * Walk over each edge, inserting the first chunk into
988  * the new node, and the split node...
989  */
990  for (i = 0; i < comp->used; i++) {
991  int j, where;
992  uint16_t before, after;
993  uint8_t key[2];
994  fr_trie_path_t *path;
995 
996  before = i >> (comp->bits - bits);
997  after = i & ((1 << bits) - 1);
998 
999  write_chunk(&key[0], start_bit, comp->bits, i);
1000 
1001  // see if "before" was already used in the newly created node.
1002 
1003  where = 0;
1004 
1005  for (j = 0; j < split->used; j++) {
1006  if (before == split->index[j]) {
1007  where = j;
1008  break;
1009  }
1010  }
1011 
1012  if (split->index[where]) {
1013  // the children MUST be different
1014  // create another compressed node as a child, and go from there.
1015 
1016  } else {
1017  split->index[split->used] = before;
1018  path = fr_trie_path_alloc(ctx, &key[0], start_bit, start_bit + bits);
1019  if (!path) goto fail;
1020 
1021  split->trie[split->used++] = (fr_trie_t *) path;
1022  path->trie = comp->trie[i];
1023  }
1024  }
1025 
1026  return (fr_trie_t *) split;
1027 
1028 fail:
1029  for (i = 0; i < split->used; i++) {
1030  talloc_free(split->trie[i]);
1031  }
1032  talloc_free(split);
1033  return NULL;
1034 }
1035 #endif /* WITH_NODE_COMPRESSION */
1036 #endif
1037 
1038 /* ADD EDGES */
1039 
1040 #ifdef WITH_PATH_COMPRESSION
1041 /** Add an edge to a node.
1042  *
1043  * This function is so that we can abstract 2^N-way nodes, or
1044  * compressed edge nodes.
1045  */
1046 static int trie_add_edge(fr_trie_t *trie, uint16_t chunk, fr_trie_t *child)
1047 {
1048  fr_trie_node_t *node;
1049 
1050 #ifdef WITH_NODE_COMPRESSION
1051  if (trie->type == FR_TRIE_COMP) {
1052  fr_trie_comp_t *comp = (fr_trie_comp_t *) trie;
1053  int i, edge;
1054 
1055  if (chunk >= (1 << comp->bits)) return -1;
1056 
1057  if (comp->used >= MAX_COMP_EDGES) return -1;
1058 
1059  edge = comp->used;
1060  for (i = 0; i < comp->used; i++) {
1061  if (comp->index[i] < chunk) continue;
1062 
1063  if (comp->index[edge] == chunk) return -1;
1064 
1065  edge = i;
1066  break;
1067  }
1068 
1069  if (edge == MAX_COMP_EDGES) return -1;
1070 
1071  /*
1072  * Move the nodes up so that we have room for the
1073  * new edge.
1074  */
1075  for (i = edge; i < comp->used; i++) {
1076  comp->index[i + 1] = comp->index[i];
1077  comp->trie[i + 1] = comp->trie[i];
1078  }
1079 
1080  comp->index[edge] = chunk;
1081  comp->trie[edge] = child;
1082 
1083  comp->used++;
1084  VERIFY(comp);
1085  return 0;
1086  }
1087 #endif
1088 
1089  if (trie->type != FR_TRIE_NODE) return -1;
1090 
1091  node = (fr_trie_node_t *) trie;
1092 
1093  if (chunk >= (1 << node->bits)) return -1;
1094 
1095  if (node->trie[chunk] != NULL) return -1;
1096 
1097  node->used++;
1098  node->trie[chunk] = child;
1099 
1100  return 0;
1101 }
1102 #endif
1103 
1104 /* MATCH FUNCTIONS */
1105 
1106 typedef void *(*trie_key_match_t)(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact);
1107 
1108 static void *trie_key_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact);
1109 
1110 static void *trie_user_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
1111 {
1112  fr_trie_user_t *user = (fr_trie_user_t *) trie;
1113  void *data;
1114 
1115  /*
1116  * We've matched the input exactly. Return the
1117  * user data.
1118  */
1119  if (start_bit == end_bit) return user->data;
1120 
1121  /*
1122  * We're not at the end of the input. Go find a
1123  * deeper match. If a match is found, return
1124  * that.
1125  */
1126  data = trie_key_match(user->trie, key, start_bit, end_bit, exact);
1127  if (data) return data;
1128 
1129  /*
1130  * We didn't find anything deeper in the trie,
1131  * AND we require an exact match. That's a
1132  * failure.
1133  */
1134  if (exact) {
1135  MPRINT2("no exact match at %d\n", __LINE__);
1136  return NULL;
1137  }
1138 
1139  /*
1140  * Return the closest (i.e. inexact) match.
1141  */
1142  return user->data;
1143 }
1144 
1145 static void *trie_node_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
1146 {
1147  uint16_t chunk;
1148  fr_trie_node_t *node = (fr_trie_node_t *) trie;
1149 
1150  chunk = get_chunk(key, start_bit, node->bits);
1151  if (!node->trie[chunk]) {
1152  MPRINT2("no match for node chunk %02x at %d\n", chunk, __LINE__);
1153  return NULL;
1154  }
1155 
1156  return trie_key_match(node->trie[chunk], key, start_bit + node->bits, end_bit, exact);
1157 }
1158 
1159 #ifdef WITH_PATH_COMPRESSION
1160 static void *trie_path_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
1161 {
1162  uint16_t chunk;
1163  fr_trie_path_t *path = (fr_trie_path_t *) trie;
1164 
1165  chunk = get_chunk(key, start_bit, path->bits);
1166  if (chunk != path->chunk) return NULL;
1167 
1168  return trie_key_match(path->trie, key, start_bit + path->bits, end_bit, exact);
1169 }
1170 #endif
1171 
1172 #ifdef WITH_NODE_COMPRESSION
1173 static void *trie_comp_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
1174 {
1175  int i;
1176  uint16_t chunk;
1177  fr_trie_comp_t *comp = (fr_trie_comp_t *) trie;
1178 
1179  chunk = get_chunk(key, start_bit, comp->bits);
1180 
1181  for (i = 0; i < comp->used; i++) {
1182  if (comp->index[i] < chunk) continue;
1183 
1184  if (comp->index[i] == chunk) {
1185  return trie_key_match(comp->trie[i], key, start_bit + comp->bits, end_bit, exact);
1186  }
1187 
1188  /*
1189  * The edges are ordered smallest to largest. So
1190  * if the edge is larger than the chunk, NO edge
1191  * will match the chunk.
1192  */
1193  return NULL;
1194  }
1195 
1196  return NULL;
1197 }
1198 #endif
1199 
1200 static trie_key_match_t trie_match_table[FR_TRIE_MAX] = {
1201  [ FR_TRIE_USER ] = trie_user_match,
1202  [ FR_TRIE_NODE ] = trie_node_match,
1203 #ifdef WITH_PATH_COMPRESSION
1204  [ FR_TRIE_PATH ] = trie_path_match,
1205 #endif
1206 #ifdef WITH_NODE_COMPRESSION
1207  [ FR_TRIE_COMP ] = trie_comp_match,
1208 #endif
1209 };
1210 
1211 
1212 /** Match a key in a trie and return user ctx, if any
1213  *
1214  * The key may be LONGER than entries in the trie. In which case the
1215  * closest match is returned.
1216  *
1217  * @param trie the trie
1218  * @param key the key
1219  * @param start_bit the start bit
1220  * @param end_bit the end bit
1221  * @param exact do we return an exact match, or the shortest one.
1222  * @return
1223  * - NULL on not found
1224  * - void* user ctx on found
1225  */
1226 static void *trie_key_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
1227 {
1228  if (!trie) return NULL;
1229 
1230  /*
1231  * We've run out of trie, so it's not a match.
1232  */
1233  if ((start_bit + trie->bits) > end_bit) {
1234  MPRINT2("%d + %d = %d > %d\n",
1235  start_bit, trie->bits, start_bit + trie->bits, end_bit);
1236 #ifdef TESTING
1237  MPRINT2("no match for key too short for trie NODE-%d at %d\n", trie->number, __LINE__);
1238 #endif
1239  return NULL;
1240  }
1241 
1242  TRIE_TYPE_CHECK(match, NULL);
1243 
1244  /*
1245  * Recursively match each type.
1246  */
1247  return trie_match_table[trie->type](trie, key, start_bit, end_bit, exact);
1248 }
1249 
1250 /** Lookup a key in a trie and return user ctx, if any
1251  *
1252  * The key may be LONGER than entries in the trie. In which case the
1253  * closest match is returned.
1254  *
1255  * @param ft the trie
1256  * @param key the key bytes
1257  * @param keylen length in bits of the key
1258  * @return
1259  * - NULL on not found
1260  * - void* user ctx on found
1261  */
1262 void *fr_trie_lookup_by_key(fr_trie_t const *ft, void const *key, size_t keylen)
1263 {
1264  fr_trie_user_t *user;
1265 
1266  if (keylen > MAX_KEY_BITS) return NULL;
1267 
1268  if (!ft->trie) return NULL;
1269 
1270  user = UNCONST(fr_trie_user_t *, ft);
1271 
1272  return trie_key_match(user->trie, key, 0, keylen, false);
1273 }
1274 
1275 /** Match a key and length in a trie and return user ctx, if any
1276  *
1277  * Only the exact match is returned.
1278  *
1279  * @param ft the trie
1280  * @param key the key bytes
1281  * @param keylen length in bits of the key
1282  * @return
1283  * - NULL on not found
1284  * - void* user ctx on found
1285  */
1286 void *fr_trie_match_by_key(fr_trie_t const *ft, void const *key, size_t keylen)
1287 {
1288  fr_trie_user_t *user;
1289 
1290  if (keylen > MAX_KEY_BITS) return NULL;
1291 
1292  if (!ft->trie) return NULL;
1293 
1294  user = UNCONST(fr_trie_user_t *, ft);
1295 
1296  return trie_key_match(user->trie, key, 0, keylen, true);
1297 }
1298 
1299 /* INSERT FUNCTIONS */
1300 
1301 #ifdef TESTING
1302 static void trie_check(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, void *data, int lineno)
1303 {
1304  void *answer;
1305 
1306  trie_sprint(trie, key, start_bit, lineno);
1307 
1308  answer = trie_key_match(trie, key, start_bit, end_bit, true);
1309  if (!answer) {
1310  fr_strerror_printf("Failed trie check answer at %d", lineno);
1311 
1312  // print out the current trie!
1313  MPRINT3("%.*sFailed to find user data %s from start %d end %d at %d\n", start_bit, spaces, data,
1314  start_bit, end_bit, lineno);
1315  fr_cond_assert(0);
1316  }
1317 
1318  if (answer != data) {
1319  fr_strerror_printf("Failed trie check answer == data at %d", lineno);
1320 
1321  MPRINT3("%.*sFound wrong user data %s != %s, from start %d end %d at %d\n", start_bit, spaces,
1322  answer, data, start_bit, end_bit, lineno);
1323  fr_cond_assert(0);
1324  }
1325 }
1326 #else
1327 #define trie_check(_trie, _key, _start_bit, _end_bit, _data, _lineno)
1328 #endif
1329 
1330 static int trie_key_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data) CC_HINT(nonnull(2,3,6));
1331 
1332 typedef int (*trie_key_insert_t)(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data);
1333 
1334 static int trie_user_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)
1335 {
1336  fr_trie_t *trie = *trie_p;
1337  fr_trie_user_t *user = (fr_trie_user_t *) trie;
1338 
1339  MPRINT3("user insert to start %d end %d with data %s\n", start_bit, end_bit, (char *) data);
1340 
1341  /*
1342  * Just insert the key into user->trie.
1343  */
1344  MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
1345  return trie_key_insert(ctx, &user->trie, key, start_bit, end_bit, data);
1346 }
1347 
1348 static int trie_node_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)
1349 {
1350  fr_trie_t *trie = *trie_p;
1351  fr_trie_node_t *node = (fr_trie_node_t *) trie;
1352  fr_trie_t *trie_to_free = NULL;
1353  uint32_t chunk;
1354 
1355  MPRINT3("%.*snode insert end %d with data %s\n",
1356  start_bit, spaces, end_bit, (char *) data);
1357 
1358  /*
1359  * The current node is longer than the input bits
1360  * for the key. Split the node into a smaller
1361  * N-way node, and insert the key into the (now
1362  * fitting) node.
1363  */
1364  if ((start_bit + node->bits) > end_bit) {
1365  fr_trie_node_t *split;
1366 
1367  MPRINT3("%.*snode insert splitting %d at %d start %d end %d with data %s\n",
1368  start_bit, spaces,
1369  node->bits, start_bit - end_bit,
1370  start_bit, end_bit, (char *) data);
1371 
1372  split = trie_node_split(ctx, node, end_bit - start_bit);
1373  if (!split) {
1374  fr_strerror_printf("Failed splitting node at %d\n", __LINE__);
1375  return -1;
1376  }
1377 
1378  trie_to_free = (fr_trie_t *) node;
1379  node = split;
1380  }
1381 
1382  chunk = get_chunk(key, start_bit, node->bits);
1383 
1384  /*
1385  * No existing trie, create a brand new trie from
1386  * the key.
1387  */
1388  if (!node->trie[chunk]) {
1389  node->trie[chunk] = trie_key_alloc(ctx, key, start_bit + node->bits, end_bit, data);
1390  if (!node->trie[chunk]) {
1391  fr_strerror_printf("Failed key_alloc at %d\n", __LINE__);
1392  if (trie_to_free) trie_free(trie_to_free);
1393  return -1;
1394  }
1395  node->used++;
1396 
1397  } else {
1398  /*
1399  * Recurse in order to insert the key
1400  * into the current node.
1401  */
1402  MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
1403  if (trie_key_insert(ctx, &node->trie[chunk], key, start_bit + node->bits, end_bit, data) < 0) {
1404  MPRINT("Failed recursing at %d\n", __LINE__);
1405  if (trie_to_free) trie_free(trie_to_free);
1406  return -1;
1407  }
1408  }
1409 
1410  trie_check((fr_trie_t *) node, key, start_bit, end_bit, data, __LINE__);
1411 
1412  MPRINT3("%.*snode insert returning at %d\n",
1413  start_bit, spaces, __LINE__);
1414 
1415  if (trie_to_free) trie_free(trie_to_free);
1416  *trie_p = (fr_trie_t *) node;
1417  VERIFY(node);
1418  return 0;
1419 }
1420 
1421 #ifdef WITH_PATH_COMPRESSION
1422 static CC_HINT(nonnull(2,3,6)) int trie_path_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)
1423 {
1424  fr_trie_t *trie = *trie_p;
1425  fr_trie_path_t *path = (fr_trie_path_t *) trie;
1426  uint32_t chunk;
1427  int lcp, bits;
1428  uint8_t const *key2;
1429  int start_bit2;
1430  fr_trie_t *node;
1431  fr_trie_t *child;
1432 
1433  MPRINT3("%.*spath insert start %d end %d with key %02x%02x data %s\n",
1434  start_bit, spaces, start_bit, end_bit, key[0], key[1], (char *) data);
1435 
1436  VERIFY(path);
1437  trie_sprint((fr_trie_t *) path, key, start_bit, __LINE__);
1438 
1439  /*
1440  * The key exactly matches the path. Recurse.
1441  */
1442  if (start_bit + path->bits <= end_bit) {
1443  chunk = get_chunk(key, start_bit, path->bits);
1444 
1445  /*
1446  * The chunk matches exactly. Recurse to
1447  * insert the key into the child trie.
1448  */
1449  if (chunk == path->chunk) {
1450  MPRINT3("%.*spath chunk matches %04x bits of %d\n",
1451  start_bit, spaces, chunk, path->bits);
1452  MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
1453  if (trie_key_insert(ctx, &path->trie, key, start_bit + path->bits, end_bit, data) < 0) {
1454  return -1;
1455  }
1456 
1457  trie_check((fr_trie_t *) path, key, start_bit, end_bit, data, __LINE__);
1458 
1459  MPRINT3("%.*spath returning at %d\n", start_bit, spaces, __LINE__);
1460  VERIFY(path);
1461  return 0;
1462  }
1463 
1464  bits = path->bits;
1465  MPRINT3("%.*spath using %d\n", start_bit, spaces, path->bits);
1466 
1467  } else {
1468  /*
1469  * Limit the number of bits we check to
1470  * the number of bits left in the key.
1471  */
1472  bits = end_bit - start_bit;
1473  MPRINT3("%.*spath limiting %d to %d\n", start_bit, spaces, path->bits, bits);
1474  }
1475 
1476  /*
1477  * Figure out what part of the key we need to
1478  * look at for LCP.
1479  */
1480  key2 = key;
1481  start_bit2 = start_bit;
1482  if (start_bit2 > 7) {
1483  key2 += (start_bit2 >> 3);
1484  start_bit2 -= 8 * (start_bit2 >> 3);
1485  }
1486 
1487  /*
1488  * Get the LCP. If we have one, split the path
1489  * node at the LCP. Replace the parent with the
1490  * first half of the path, and build an N-way
1491  * node for the second half.
1492  */
1493  lcp = fr_trie_key_lcp(&path->key[0], bits, key2, bits, start_bit2);
1494  MPRINT3("%.*spath lcp %d\n", start_bit, spaces, lcp);
1495 
1496  /*
1497  * This should have been caught above.
1498  */
1499  if (lcp == path->bits) {
1500  fr_strerror_const("found lcp which should have been previously found");
1501  return -1;
1502  }
1503 
1504  if (lcp > 0) {
1505  fr_trie_path_t *split;
1506 
1507  /*
1508  * Note that "path" is still valid after this
1509  * call. We will rewrite things on the way back
1510  * up the stack.
1511  */
1512  MPRINT3("%.*spath split depth %d bits %d at lcp %d with data %s\n",
1513  start_bit, spaces, start_bit, path->bits, lcp, (char *) data);
1514 
1515  MPRINT3("%.*spath key %02x%02x input key %02x%02x, offset %d\n",
1516  start_bit, spaces,
1517  path->key[0],path->key[1],
1518  key[0], key[1],
1519  start_bit2);
1520 
1521  split = trie_path_split(ctx, path, start_bit2, lcp);
1522  if (!split) {
1523  fr_strerror_printf("failed path split at %d\n", __LINE__);
1524  return -1;
1525  }
1526 
1527  trie_sprint((fr_trie_t *) path, key, start_bit, __LINE__);
1528  trie_sprint((fr_trie_t *) split, key, start_bit, __LINE__);
1529  trie_sprint((fr_trie_t *) split->trie, key, start_bit + split->bits, __LINE__);
1530 
1531  /*
1532  * Recurse to insert the key into the child node.
1533  * Note that if "bits > MAX_NODE_BITS", we will
1534  * have to split "path" again.
1535  */
1536  MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
1537  if (trie_key_insert(ctx, &split->trie, key, start_bit + split->bits, end_bit, data) < 0) {
1538  talloc_free(split->trie);
1539  talloc_free(split);
1540  return -1;
1541  }
1542 
1543  /*
1544  * We can't have two LCPs in a row here, as we
1545  * SHOULD have found the LCP above!
1546  */
1547  fr_cond_assert(split->type == FR_TRIE_PATH);
1548  fr_cond_assert(split->trie->type != FR_TRIE_PATH);
1549 
1550  trie_check((fr_trie_t *) split, key, start_bit, end_bit, data, __LINE__);
1551 
1552  MPRINT3("%.*spath returning at %d\n", start_bit, spaces, __LINE__);
1553  talloc_free(path);
1554  *trie_p = (fr_trie_t *) split;
1555  VERIFY(split);
1556  return 0;
1557  }
1558 
1559  /*
1560  * Else there's no common prefix. Just create an
1561  * fanout node.
1562  */
1563  /*
1564  * We only want two edges here. Try to create a
1565  * compressed N-way node if possible.
1566  */
1567 #ifdef WITH_NODE_COMPRESSION
1568  if (bits > 2) {
1569  if (bits > MAX_COMP_BITS) bits = MAX_COMP_BITS;
1570 
1571  MPRINT3("%.*sFanout to comp %d at depth %d data %s\n", start_bit, spaces, bits, start_bit, (char *) data);
1572  node = (fr_trie_t *) fr_trie_comp_alloc(ctx, bits);
1573  } else
1574 #endif
1575  {
1576  /*
1577  * Without path compression create no more than a
1578  * 16-way node.
1579  */
1580  if (bits > MAX_NODE_BITS) bits = MAX_NODE_BITS;
1581 
1582  MPRINT3("%.*sFanout to node %d at depth %d data %s\n", start_bit, spaces, bits, start_bit, (char *) data);
1583  node = (fr_trie_t *) trie_node_alloc(ctx, bits);
1584  }
1585  if (!node) return -1;
1586 
1587  /*
1588  * Get the chunk from the path, and insert the child trie
1589  * into the node at that chunk.
1590  */
1591  chunk = get_chunk(&path->key[0], start_bit2, node->bits);
1592 
1593  if (node->bits == path->bits) {
1594  child = path->trie;
1595 
1596  } else {
1597  /*
1598  * Skip the common prefix.
1599  */
1600  child = (fr_trie_t *) fr_trie_path_alloc(ctx, &path->key[0], start_bit2 + node->bits, start_bit2 + path->bits);
1601  if (!child) {
1602  fr_strerror_printf("failed allocating path child at %d", __LINE__);
1603  return -1;
1604  }
1605 
1606  /*
1607  * Patch in the child trie.
1608  */
1609  ((fr_trie_path_t *)child)->trie = path->trie;
1610 
1611  VERIFY(child);
1612  }
1613 
1614  trie = NULL;
1615 
1616  /*
1617  * Recurse to insert the key into the second edge. If
1618  * this fails, then we haven't changed anything. So just
1619  * free memory and return.
1620  *
1621  * Note that if "bits > DEFAULT_BITS", we will have to
1622  * split "path" again.
1623  */
1624  MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
1625  if (trie_key_insert(ctx, &trie, key, start_bit + node->bits, end_bit, data) < 0) {
1626  talloc_free(node);
1627  if (child != path->trie) talloc_free(child);
1628  return -1;
1629  }
1630 
1631  /*
1632  * Copy the first edge over to the first chunk.
1633  */
1634  if (trie_add_edge(node, chunk, child) < 0) {
1635  fr_strerror_printf("chunk failure in insert node %d at %d", node->bits, __LINE__);
1636  talloc_free(node);
1637  if (child != path->trie) talloc_free(child);
1638  return -1;
1639  }
1640 
1641  /*
1642  * Copy the second edge from the new chunk.
1643  */
1644  chunk = get_chunk(key, start_bit, node->bits);
1645  if (trie_add_edge(node, chunk, trie) < 0) {
1646  fr_strerror_printf("chunk failure in insert node %d at %d", node->bits, __LINE__);
1647  talloc_free(node);
1648  trie_free(trie);
1649  return -1;
1650  }
1651 
1652  trie_check((fr_trie_t *) node, key, start_bit, end_bit, data, __LINE__);
1653 
1654  MPRINT3("%.*spath returning at %d\n", start_bit, spaces, __LINE__);
1655 
1656  /*
1657  * Only update the answer if the insert succeeded.
1658  */
1659  *trie_p = node;
1660  talloc_free(path);
1661  VERIFY(node);
1662  return 0;
1663 }
1664 #endif
1665 
1666 #ifdef WITH_NODE_COMPRESSION
1667 static CC_HINT(nonnull(2,3,6)) int trie_comp_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)
1668 {
1669  int i, bits;
1670  fr_trie_t *trie = *trie_p;
1671  fr_trie_comp_t *comp = (fr_trie_comp_t *) trie;
1672  fr_trie_node_t *node;
1673  uint16_t chunk;
1674 
1675  MPRINT3("%.*scomp insert start %d end %d with key %02x%02x data %s\n",
1676  start_bit, spaces, start_bit, end_bit, key[0], key[1], (char *) data);
1677 
1678  if ((end_bit - start_bit) < comp->bits) {
1679  fr_strerror_printf("Not implemented at %d", __LINE__);
1680  return -1;
1681  }
1682 
1683  chunk = get_chunk(key, start_bit, comp->bits);
1684 
1685  /*
1686  * Search for a matching edge. If found, recurse and
1687  * insert the key there.
1688  */
1689  for (i = 0; i < comp->used; i++) {
1690  if (comp->index[i] < chunk) continue;
1691 
1692  /*
1693  * We've found a matching chunk, recurse.
1694  */
1695  if (comp->index[i] == chunk) {
1696  MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
1697  if (trie_key_insert(ctx, &comp->trie[i], key, start_bit + comp->bits, end_bit, data) < 0) {
1698  MPRINT3("%.*scomp failed recursing at %d", start_bit, spaces, __LINE__);
1699  return -1;
1700  }
1701 
1702  trie_check((fr_trie_t *) comp, key, start_bit, end_bit, data, __LINE__);
1703 
1704  MPRINT3("%.*scomp returning at %d", start_bit, spaces, __LINE__);
1705  VERIFY(comp);
1706  return 0;
1707  }
1708 
1709  /*
1710  * The chunk is larger than the current edge,
1711  * stop.
1712  */
1713  break;
1714  }
1715 
1716  /*
1717  * No edge matches the chunk from the key. Insert the
1718  * child trie into a place-holder entry, so that we don't
1719  * modify the current node on failure.
1720  */
1721  if (comp->used < MAX_COMP_EDGES) {
1722  MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
1723  trie = NULL;
1724  if (trie_key_insert(ctx, &trie, key, start_bit + comp->bits, end_bit, data) < 0) {
1725  MPRINT3("%.*scomp failed recursing at %d", start_bit, spaces, __LINE__);
1726  return -1;
1727  }
1728  fr_cond_assert(trie != NULL);
1729 
1730  if (trie_add_edge((fr_trie_t *) comp, chunk, trie) < 0) {
1731  talloc_free(trie); // @todo - there may be multiple nodes here?
1732  return -1;
1733  }
1734 
1735  trie_check((fr_trie_t *) comp, key, start_bit, end_bit, data, __LINE__);
1736 
1737  VERIFY(comp);
1738  return 0;
1739  }
1740 
1741  /*
1742  * All edges are used. Create an N-way node.
1743  */
1744 
1745  /*
1746  * @todo - limit bits by calling
1747  * trie_comp_split()?
1748  */
1749  bits = comp->bits;
1750 
1751  MPRINT3("%.*scomp swapping to node bits %d at %d\n", start_bit, spaces, bits, __LINE__);
1752 
1753  node = trie_node_alloc(ctx, bits);
1754  if (!node) return -1;
1755 
1756  for (i = 0; i < comp->used; i++) {
1757  fr_cond_assert(node->trie[comp->index[i]] == NULL);
1758  node->trie[comp->index[i]] = comp->trie[i];
1759  }
1760  node->used = comp->used;
1761  node->used += (node->trie[chunk] == NULL); /* will get set if the recursive insert succeeds */
1762 
1763  /*
1764  * Insert the new chunk, which may or may not overlap
1765  * with an existing one.
1766  */
1767  MPRINT3("%.*srecurse at %d\n", start_bit, spaces, __LINE__);
1768  if (trie_key_insert(ctx, &node->trie[chunk], key, start_bit + node->bits, end_bit, data) < 0) {
1769  MPRINT3("%.*scomp failed recursing at %d", start_bit, spaces, __LINE__);
1770  talloc_free(node);
1771  return -1;
1772  }
1773 
1774  trie_check((fr_trie_t *) node, key, start_bit, end_bit, data, __LINE__);
1775 
1776  MPRINT3("%.*scomp returning at %d", start_bit, spaces, __LINE__);
1777 
1778  talloc_free(comp);
1779  *trie_p = (fr_trie_t *) node;
1780  VERIFY(node);
1781  return 0;
1782 }
1783 #endif
1784 
1785 static trie_key_insert_t trie_insert_table[FR_TRIE_MAX] = {
1786  [ FR_TRIE_USER ] = trie_user_insert,
1787  [ FR_TRIE_NODE ] = trie_node_insert,
1788 #ifdef WITH_PATH_COMPRESSION
1789  [ FR_TRIE_PATH ] = trie_path_insert,
1790 #endif
1791 #ifdef WITH_NODE_COMPRESSION
1792  [ FR_TRIE_COMP ] = trie_comp_insert,
1793 #endif
1794 };
1795 
1796 /** Insert a binary key into the trie
1797  *
1798  * The key must have at least ((start_bit + keylen) >> 3) bytes
1799  *
1800  * @param ctx the talloc ctx
1801  * @param[in,out] trie_p the trie where things are inserted
1802  * @param key the binary key
1803  * @param start_bit the start bit
1804  * @param end_bit the end bit
1805  * @param data user data to insert
1806  * @return
1807  * - <0 on error
1808  * - 0 on success
1809  */
1810 static int trie_key_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)
1811 {
1812  fr_trie_t *trie = *trie_p;
1813 
1814  /*
1815  * We've reached the end of the trie, but may still have
1816  * key bits to insert.
1817  */
1818  if (!trie) {
1819  *trie_p = trie_key_alloc(ctx, key, start_bit, end_bit, data);
1820  if (!*trie_p) return -1;
1821  return 0;
1822  }
1823 
1824  MPRINT3("%.*sIN recurse at %d\n", start_bit, spaces, __LINE__);
1825  trie_sprint(trie, key, start_bit, __LINE__);
1826 
1827  /*
1828  * We've reached the end of the key. Insert a user node
1829  * here, and push the remaining bits of the trie to after
1830  * the user node.
1831  */
1832  if (start_bit == end_bit) {
1833  fr_trie_user_t *user;
1834 
1835  if (trie->type == FR_TRIE_USER) {
1836  fr_strerror_printf("already has a user node at %d\n", __LINE__);
1837  return -1;
1838  }
1839 
1840  user = fr_trie_user_alloc(ctx, data);
1841  if (!user) return -1;
1842 
1843  user->trie = trie;
1844  *trie_p = (fr_trie_t *) user;
1845  return 0;
1846  }
1847 
1848  TRIE_TYPE_CHECK(insert, -1);
1849 
1850 #ifndef TESTING
1851  return trie_insert_table[trie->type](ctx, trie_p, key, start_bit, end_bit, data);
1852 #else
1853  MPRINT3("%.*srecurse at start %d end %d with data %s\n", start_bit, spaces, start_bit, end_bit, (char *) data);
1854 
1855  if (trie_insert_table[trie->type](ctx, trie_p, key, start_bit, end_bit, data) < 0) {
1856  return -1;
1857  }
1858 
1859  trie_check(*trie_p, key, start_bit, end_bit, data, __LINE__);
1860 
1861  return 0;
1862 #endif
1863 }
1864 
1865 /** Insert a key and user ctx into a trie
1866  *
1867  * @param ft the trie
1868  * @param key the key
1869  * @param keylen key length in bits
1870  * @param data user ctx information to associated with the key
1871  * @return
1872  * - <0 on error
1873  * - 0 on success
1874  */
1875 int fr_trie_insert_by_key(fr_trie_t *ft, void const *key, size_t keylen, void const *data)
1876 {
1877  void *my_data;
1878  fr_trie_user_t *user;
1879 
1880  if (keylen > MAX_KEY_BITS) {
1881  fr_strerror_printf("keylen too long (%u > %d)", (unsigned int) keylen, MAX_KEY_BITS);
1882  return -1;
1883  }
1884 
1885  user = (fr_trie_user_t *) ft;
1886 
1887  /*
1888  * Do a lookup before insertion. If we tried to insert
1889  * the key with new nodes and then discovered a conflict,
1890  * we would not be able to undo the process. This check
1891  * ensures that the insertion can modify the trie in
1892  * place without worry.
1893  */
1894  if (trie_key_match(user->trie, key, 0, keylen, true) != NULL) {
1895  fr_strerror_const("Cannot insert due to pre-existing key");
1896  return -1;
1897  }
1898 
1899  my_data = UNCONST(void *, data);
1900  MPRINT2("No match for data, inserting...\n");
1901 
1902  MPRINT3("%.*srecurse STARTS at %d with %.*s=%s\n", 0, spaces, __LINE__,
1903  (int) keylen, key, my_data);
1904  return trie_key_insert(user->data, &user->trie, key, 0, keylen, my_data);
1905 }
1906 
1907 /* REMOVE FUNCTIONS */
1908 static void *trie_key_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit);
1909 
1910 typedef void *(*trie_key_remove_t)(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit);
1911 
1912 static void *trie_user_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
1913 {
1914  fr_trie_t *trie = *trie_p;
1915  fr_trie_user_t *user = (fr_trie_user_t *) trie;
1916 
1917  /*
1918  * We're at the end of the key, return the data
1919  * given here, and free the node that we're
1920  * removing.
1921  */
1922  if (start_bit == end_bit) {
1923  void *data = user->data;
1924 
1925  *trie_p = user->trie;
1926  talloc_free(user);
1927 
1928  return data;
1929  }
1930 
1931  return trie_key_remove(ctx, &user->trie, key, start_bit, end_bit);
1932 }
1933 
1934 static void *trie_node_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
1935 {
1936  fr_trie_t *trie = *trie_p;
1937  fr_trie_node_t *node = (fr_trie_node_t *) trie;
1938  uint32_t chunk;
1939  void *data;
1940 
1941  chunk = get_chunk(key, start_bit, node->bits);
1942  if (!node->trie[chunk]) return NULL;
1943 
1944  data = trie_key_remove(ctx, &node->trie[chunk], key, start_bit + node->bits, end_bit);
1945  if (!data) return NULL;
1946 
1947  /*
1948  * The trie still has a subtrie. Just return the data.
1949  */
1950  if (node->trie[chunk]) return data;
1951 
1952  /*
1953  * One less used edge.
1954  */
1955  node->used--;
1956  if (node->used > 0) return data;
1957 
1958  /*
1959  * @todo - if we have path compression, and
1960  * node->used==1, then create a fr_trie_path_t from the
1961  * chunk, and concatenate it (if necessary) to any
1962  * trailing path compression node.
1963  */
1964 
1965  /*
1966  * Our entire node is empty. Delete it as we walk back up the trie.
1967  */
1968  *trie_p = NULL;
1969  talloc_free(node); /* no children */
1970  return data;
1971 }
1972 
1973 #ifdef WITH_PATH_COMPRESSION
1974 static void *trie_path_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
1975 {
1976  fr_trie_t *trie = *trie_p;
1977  fr_trie_path_t *path = (fr_trie_path_t *) trie;
1978  uint32_t chunk;
1979  void *data;
1980 
1981  chunk = get_chunk(key, start_bit, path->bits);
1982 
1983  /*
1984  * No match, can't remove it.
1985  */
1986  if (path->chunk != chunk) return NULL;
1987 
1988  data = trie_key_remove(ctx, &path->trie, key, start_bit + path->bits, end_bit);
1989  if (!data) return NULL;
1990 
1991  /*
1992  * The trie still has a subtrie. Just return the data.
1993  */
1994  if (path->trie) return data;
1995 
1996  /*
1997  * Our entire path is empty. Delete it as we walk back up the trie.
1998  */
1999  *trie_p = NULL;
2000  talloc_free(path); /* no children */
2001  return data;
2002 }
2003 #endif
2004 
2005 #ifdef WITH_NODE_COMPRESSION
2006 static void *trie_comp_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
2007 {
2008  int i, j;
2009  uint16_t chunk;
2010  void *data;
2011  fr_trie_comp_t *comp = *(fr_trie_comp_t **) trie_p;
2012  fr_trie_path_t *path;
2013 
2014  chunk = get_chunk(key, start_bit, comp->bits);
2015 
2016  MPRINT3("%.*sremove at %d\n", start_bit, spaces, __LINE__);
2017  trie_sprint(*trie_p, key, start_bit, __LINE__);
2018 
2019  for (i = 0; i < comp->used; i++) {
2020  if (comp->index[i] < chunk) continue;
2021 
2022  if (comp->index[i] == chunk) {
2023  break;
2024  }
2025 
2026  /*
2027  * The edges are ordered smallest to largest. So
2028  * if the edge is larger than the chunk, NO edge
2029  * will match the chunk.
2030  */
2031  if (comp->index[i] > chunk) return NULL;
2032  }
2033 
2034  /*
2035  * Didn't find it, fail.
2036  */
2037  if (i >= comp->used) return NULL;
2038 
2039  fr_cond_assert(chunk == comp->index[i]);
2040 
2041  data = trie_key_remove(ctx, &comp->trie[i], key, start_bit + comp->bits, end_bit);
2042  if (!data) return NULL;
2043 
2044  /*
2045  * The trie still has a subtrie. Just return the data.
2046  */
2047  if (comp->trie[i]) {
2048  MPRINT3("%.*sremove at %d\n", start_bit, spaces, __LINE__);
2049  trie_sprint((fr_trie_t *) comp, key, start_bit, __LINE__);
2050  VERIFY(comp);
2051  return data;
2052  }
2053 
2054  /*
2055  * Shrinking at the end is easy, we don't need to do
2056  * anything. For shrinking in the middle, we just copy
2057  * the entries down.
2058  */
2059  for (j = i; j < comp->used - 1; j++) {
2060  comp->index[j] = comp->index[j + 1];
2061  comp->trie[j] = comp->trie[j + 1];
2062  }
2063  comp->used--;
2064 
2065  if (comp->used >= 2) {
2066  VERIFY(comp);
2067  return data;
2068  }
2069 
2070  /*
2071  * Our entire path is empty. Delete it as we walk back
2072  * up the trie. We hope that this doesn't happen.
2073  */
2074  if (!comp->used) {
2075  *trie_p = NULL;
2076  talloc_free(comp); /* no children */
2077  MPRINT3("%.*sremove at %d\n", start_bit, spaces, __LINE__);
2078  return data;
2079  }
2080 
2081  /*
2082  * Only one edge. Turn it back into a path node. Note
2083  * that we pass "key" here, which is wrong... that's the
2084  * key we're removing, not the key left in the node. But
2085  * we fix that later.
2086  *
2087  * @todo - check the child. If it's also a path node, try
2088  * to concatenate the nodes together.
2089  */
2090  path = fr_trie_path_alloc(ctx, key, start_bit, start_bit + comp->bits);
2091  if (!path) return data;
2092 
2093  /*
2094  * Tie the new node in.
2095  */
2096  path->trie = comp->trie[0];
2097 
2098  /*
2099  * Fix up the chunk and key to be the one left in the
2100  * trie, not the one which was removed.
2101  */
2102  path->chunk = comp->index[0];
2103  write_chunk(&path->key[0], start_bit & 0x07, path->bits, path->chunk);
2104 
2105  *trie_p = (fr_trie_t *) path;
2106  talloc_free(comp);
2107  VERIFY(path);
2108  return data;
2109 }
2110 #endif
2111 
2112 static trie_key_remove_t trie_remove_table[FR_TRIE_MAX] = {
2113  [ FR_TRIE_USER ] = trie_user_remove,
2114  [ FR_TRIE_NODE ] = trie_node_remove,
2115 #ifdef WITH_PATH_COMPRESSION
2116  [ FR_TRIE_PATH ] = trie_path_remove,
2117 #endif
2118 #ifdef WITH_NODE_COMPRESSION
2119  [ FR_TRIE_COMP ] = trie_comp_remove,
2120 #endif
2121 };
2122 
2123 /** Remove a key from a trie, and return the user data.
2124  *
2125  */
2126 static void *trie_key_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
2127 {
2128  fr_trie_t *trie = *trie_p;
2129 
2130  if (!trie) return NULL;
2131 
2132  /*
2133  * We can't remove a key which is shorter than the
2134  * current trie.
2135  */
2136  if ((start_bit + trie->bits) > end_bit) return NULL;
2137 
2138  TRIE_TYPE_CHECK(remove, NULL);
2139 
2140  return trie_remove_table[trie->type](ctx, trie_p, key, start_bit, end_bit);
2141 }
2142 
2143 /** Remove a key and return the associated user ctx
2144  *
2145  * The key must match EXACTLY. This is not a prefix match.
2146  *
2147  * @param ft the trie
2148  * @param key the key
2149  * @param keylen key length in bits
2150  * @return
2151  * - NULL on not found
2152  * - user ctx data on success
2153  */
2154 void *fr_trie_remove_by_key(fr_trie_t *ft, void const *key, size_t keylen)
2155 {
2156  fr_trie_user_t *user;
2157 
2158  if (keylen > MAX_KEY_BITS) return NULL;
2159 
2160  if (!ft->trie) return NULL;
2161 
2162  user = (fr_trie_user_t *) ft;
2163 
2164  /*
2165  * Remove the user trie, not ft->trie.
2166  */
2167  return trie_key_remove(user->data, &user->trie, key, 0, (int) keylen);
2168 }
2169 
2170 /* WALK FUNCTIONS */
2171 
2172 typedef struct fr_trie_callback_s fr_trie_callback_t;
2173 
2174 typedef int (*fr_trie_key_walk_t)(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more);
2175 
2176 static int trie_key_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more);
2177 
2178 struct fr_trie_callback_s {
2179  uint8_t *start;
2180  uint8_t const *end;
2181 
2182  void *ctx;
2183 
2184  fr_trie_key_walk_t callback;
2185  fr_trie_walk_t user_callback;
2186 };
2187 
2188 static int trie_user_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
2189 {
2190  fr_trie_user_t *user = (fr_trie_user_t *) trie;
2191 
2192  if (!user->trie) return 0;
2193 
2194  return trie_key_walk(user->trie, cb, depth, more);
2195 }
2196 
2197 static int trie_node_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
2198 {
2199  int i, used;
2200  fr_trie_node_t *node = (fr_trie_node_t *) trie;
2201 
2202  used = 0;
2203  for (i = 0; i < (1 << node->bits); i++) {
2204  if (!node->trie[i]) continue;
2205 
2206  write_chunk(cb->start, depth, node->bits, (uint16_t) i);
2207  used++;
2208 
2209  if (trie_key_walk(node->trie[i], cb, depth + node->bits,
2210  more || (used < node->used)) < 0) {
2211  return -1;
2212  }
2213  }
2214 
2215  return 0;
2216 }
2217 
2218 #ifdef WITH_PATH_COMPRESSION
2219 static int trie_path_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
2220 {
2221  fr_trie_path_t *path = (fr_trie_path_t *) trie;
2222 
2223  write_chunk(cb->start, depth, path->bits, path->chunk);
2224 
2225  fr_cond_assert(path->trie != NULL);
2226  return trie_key_walk(path->trie, cb, depth + path->bits, more);
2227 }
2228 #endif
2229 
2230 #ifdef WITH_NODE_COMPRESSION
2231 static int trie_comp_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
2232 {
2233  int i, used;
2234  fr_trie_comp_t *comp = (fr_trie_comp_t *) trie;
2235 
2236  used = 0;
2237  for (i = 0; i < comp->used; i++) {
2238  write_chunk(cb->start, depth, comp->bits, comp->index[i]);
2239 
2240  fr_cond_assert(comp->trie[i] != NULL);
2241 
2242  used++;
2243  if (trie_key_walk(comp->trie[i], cb, depth + comp->bits,
2244  more || (used < comp->used)) < 0) {
2245  return -1;
2246  }
2247  }
2248 
2249  return 0;
2250 }
2251 #endif
2252 
2253 static fr_trie_key_walk_t trie_walk_table[FR_TRIE_MAX] = {
2254  [ FR_TRIE_USER ] = trie_user_walk,
2255  [ FR_TRIE_NODE ] = trie_node_walk,
2256 #ifdef WITH_PATH_COMPRESSION
2257  [ FR_TRIE_PATH ] = trie_path_walk,
2258 #endif
2259 #ifdef WITH_NODE_COMPRESSION
2260  [ FR_TRIE_COMP ] = trie_comp_walk,
2261 #endif
2262 };
2263 
2264 static int trie_key_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
2265 {
2266  /*
2267  * Do the callback before anything else.
2268  */
2269  if (cb->callback(trie, cb, depth, more) < 0) return -1;
2270 
2271  if (!trie) {
2272  fr_cond_assert(depth == 0);
2273  return 0;
2274  }
2275 
2276  TRIE_TYPE_CHECK(walk, -1);
2277 
2278  /*
2279  * No more buffer space, stop.
2280  */
2281  if ((cb->start + BYTEOF(depth + trie->bits + 8)) >= cb->end) return 0;
2282 
2283  return trie_walk_table[trie->type](trie, cb, depth, more);
2284 }
2285 
2286 #ifdef WITH_TRIE_VERIFY
2287 /* VERIFY FUNCTIONS */
2288 
2289 typedef int (*trie_verify_t)(fr_trie_t *trie);
2290 
2291 static int trie_user_verify(fr_trie_t *trie)
2292 {
2293  fr_trie_user_t *user = (fr_trie_user_t *) trie;
2294 
2295  if (!user->data) {
2296  fr_strerror_const("user node has no user data");
2297  return -1;
2298  }
2299 
2300  if (!user->trie) return 0;
2301 
2302  return trie_verify(user->trie);
2303 }
2304 
2305 static int trie_node_verify(fr_trie_t *trie)
2306 {
2307  fr_trie_node_t *node = (fr_trie_node_t *) trie;
2308  int i, used;
2309 
2310  if ((node->bits == 0) || (node->bits > MAX_NODE_BITS)) {
2311  fr_strerror_printf("N-way node has invalid bits %d",
2312  node->bits);
2313  return -1;
2314  }
2315 
2316  if ((node->used == 0) || (node->used > (1 << node->bits))) {
2317  fr_strerror_printf("N-way node has invalid used %d for bits %d",
2318  node->used, node->bits);
2319  return -1;
2320  }
2321 
2322  used = 0;
2323  for (i = 0; i < (1 << node->bits); i++) {
2324  if (!node->trie[i]) continue;
2325 
2326  if (trie_verify(node->trie[i]) < 0) return -1;
2327 
2328  used++;
2329  }
2330 
2331  if (used != node->used) {
2332  fr_strerror_printf("N-way node has incorrect used %d when actually used %d",
2333  node->used, used);
2334  return -1;
2335  }
2336 
2337  return 0;
2338 }
2339 
2340 #ifdef WITH_PATH_COMPRESSION
2341 static int trie_path_verify(fr_trie_t *trie)
2342 {
2343  fr_trie_path_t *path = (fr_trie_path_t *) trie;
2344 
2345  if ((path->bits == 0) || (path->bits > 16)) {
2346  fr_strerror_printf("path node has invalid bits %d",
2347  path->bits);
2348  return -1;
2349  }
2350 
2351  if (!path->trie) {
2352  fr_strerror_const("path node has no child trie");
2353  return -1;
2354  }
2355 
2356  return trie_verify(path->trie);
2357 }
2358 #endif
2359 
2360 #ifdef WITH_NODE_COMPRESSION
2361 static int trie_comp_verify(fr_trie_t *trie)
2362 {
2363  int i, used;
2364  fr_trie_comp_t *comp = (fr_trie_comp_t *) trie;
2365 
2366  if ((comp->bits == 0) || (comp->bits > MAX_COMP_BITS)) {
2367  fr_strerror_printf("comp node has invalid bits %d",
2368  comp->bits);
2369  return -1;
2370  }
2371 
2372  used = 0;
2373  for (i = 0; i < comp->used; i++) {
2374  if (!comp->trie[i]) {
2375  fr_strerror_printf("comp node has no child trie at %d", i);
2376  return -1;
2377  }
2378 
2379  if ((i + 1) < comp->used) {
2380  if (comp->index[i] >= comp->index[i + 1]) {
2381  fr_strerror_printf("comp node has inverted edges at %d (%04x >= %04x)",
2382  i, comp->index[i], comp->index[i + 1]);
2383  return -1;
2384  }
2385  }
2386 
2387  if (trie_verify(comp->trie[i]) < 0) return -1;
2388  used++;
2389  }
2390 
2391  if (used != comp->used) {
2392  fr_strerror_printf("Compressed node has incorrect used %d when actually used %d",
2393  comp->used, used);
2394  return -1;
2395  }
2396 
2397  return 0;
2398 }
2399 #endif
2400 
2401 static trie_verify_t trie_verify_table[FR_TRIE_MAX] = {
2402  [ FR_TRIE_USER ] = trie_user_verify,
2403  [ FR_TRIE_NODE ] = trie_node_verify,
2404 #ifdef WITH_PATH_COMPRESSION
2405  [ FR_TRIE_PATH ] = trie_path_verify,
2406 #endif
2407 #ifdef WITH_NODE_COMPRESSION
2408  [ FR_TRIE_COMP ] = trie_comp_verify,
2409 #endif
2410 };
2411 
2412 
2413 /** Verify the trie nodes
2414  *
2415  */
2416 static int trie_verify(fr_trie_t *trie)
2417 {
2418  if (!trie) return 0;
2419 
2420  TRIE_TYPE_CHECK(verify, -1);
2421 
2422  return trie_verify_table[trie->type](trie);
2423 }
2424 #endif /* WITH_TRIE_VERIFY */
2425 
2426 /* MISCELLANEOUS FUNCTIONS */
2427 
2428 #ifdef TESTING
2429 /** Dump a trie edge in canonical form.
2430  *
2431  */
2432 static void trie_dump_edge(FILE *fp, fr_trie_t *trie)
2433 {
2434  fr_cond_assert(trie != NULL);
2435 
2436  fprintf(fp, "NODE-%d\n", trie->number);
2437  return;
2438 }
2439 
2440 
2441 typedef void (*fr_trie_dump_t)(FILE *fp, fr_trie_t *trie, char const *key, int keylen);
2442 
2443 static void trie_user_dump(FILE *fp, fr_trie_t *trie, char const *key, int keylen)
2444 {
2445  fr_trie_user_t *user = (fr_trie_user_t *) trie;
2446  int bytes = BYTES(keylen);
2447 
2448  fprintf(fp, "{ NODE-%d\n", user->number);
2449  fprintf(fp, "\ttype\tUSER\n");
2450  fprintf(fp, "\tinput\t{%d}%.*s\n", keylen, bytes, key);
2451 
2452  fprintf(fp, "\tdata\t\"%s\"\n", (char const *) user->data);
2453  if (!user->trie) {
2454  fprintf(fp, "}\n\n");
2455  return;
2456  }
2457 
2458  fprintf(fp, "\tnext\t");
2459  trie_dump_edge(fp, user->trie);
2460  fprintf(fp, "}\n\n");
2461 }
2462 
2463 static void trie_node_dump(FILE *fp, fr_trie_t *trie, char const *key, int keylen)
2464 {
2465  fr_trie_node_t *node = (fr_trie_node_t *) trie;
2466  int i;
2467  int bytes = BYTES(keylen);
2468 
2469  fprintf(fp, "{ NODE-%d\n", node->number);
2470  fprintf(fp, "\ttype\tNODE\n");
2471  fprintf(fp, "\tinput\t{%d}%.*s\n", keylen, bytes, key);
2472 
2473  fprintf(fp, "\tbits\t%d\n", node->bits);
2474  fprintf(fp, "\tused\t%d\n", node->used);
2475 
2476  for (i = 0; i < (1 << node->bits); i++) {
2477  if (!node->trie[i]) continue;
2478 
2479  fprintf(fp, "\t%02x\t", (int) i);
2480  trie_dump_edge(fp, node->trie[i]);
2481  }
2482  fprintf(fp, "}\n\n");
2483 }
2484 
2485 #ifdef WITH_PATH_COMPRESSION
2486 static void trie_path_dump(FILE *fp, fr_trie_t *trie, char const *key, int keylen)
2487 {
2488  fr_trie_path_t *path = (fr_trie_path_t *) trie;
2489  int bytes = BYTES(keylen);
2490 
2491  fprintf(fp, "{ NODE-%d\n", path->number);
2492  fprintf(fp, "\ttype\tPATH\n");
2493  fprintf(fp, "\tinput\t{%d}%.*s\n", keylen, bytes, key);
2494 
2495  fprintf(fp, "\tbits\t%d\n", (int) path->bits);
2496  fprintf(fp, "\tpath\t");
2497 
2498  fprintf(fp, "%02x %02x", path->key[0], path->key[1]);
2499 
2500  fprintf(fp, "\n");
2501 
2502  fprintf(fp, "\tnext\t");
2503  trie_dump_edge(fp, path->trie);
2504 
2505  fprintf(fp, "}\n\n");
2506 }
2507 #endif
2508 
2509 #ifdef WITH_NODE_COMPRESSION
2510 static void trie_comp_dump(FILE *fp, fr_trie_t *trie, char const *key, int keylen)
2511 {
2512  fr_trie_comp_t *comp = (fr_trie_comp_t *) trie;
2513  int i;
2514  int bytes = BYTES(keylen);
2515 
2516  fprintf(fp, "{ NODE-%d\n", comp->number);
2517  fprintf(fp, "\ttype\tCOMP\n");
2518  fprintf(fp, "\tinput\t{%d}%.*s\n", keylen, bytes, key);
2519 
2520  fprintf(fp, "\tbits\t%d\n", comp->bits);
2521  fprintf(fp, "\tused\t%d\n", comp->used);
2522 
2523  for (i = 0; i < comp->used; i++) {
2524  fprintf(fp, "\t%d = %02x\t", i, comp->index[i]);
2525  trie_dump_edge(fp, comp->trie[i]);
2526  }
2527  fprintf(fp, "}\n\n");
2528 }
2529 
2530 #endif
2531 
2532 static fr_trie_dump_t trie_dump_table[FR_TRIE_MAX] = {
2533  [ FR_TRIE_USER ] = trie_user_dump,
2534  [ FR_TRIE_NODE ] = trie_node_dump,
2535 #ifdef WITH_PATH_COMPRESSION
2536  [ FR_TRIE_PATH ] = trie_path_dump,
2537 #endif
2538 #ifdef WITH_NODE_COMPRESSION
2539  [ FR_TRIE_COMP ] = trie_comp_dump,
2540 #endif
2541 };
2542 
2543 
2544 /** Dump the trie nodes
2545  *
2546  */
2547 static int _trie_dump_cb(fr_trie_t *trie, fr_trie_callback_t *cb, int keylen, UNUSED bool more)
2548 {
2549  FILE *fp = cb->ctx;
2550 
2551  if (!trie) return 0;
2552 
2553  TRIE_TYPE_CHECK(dump, -1);
2554 
2555  trie_dump_table[trie->type](fp, trie, (char const *) cb->start, keylen);
2556  return 0;
2557 }
2558 
2559 /** Print the strings accepted by a trie to a file
2560  *
2561  */
2562 static int _trie_print_cb(fr_trie_t *trie, fr_trie_callback_t *cb, int keylen, UNUSED bool more)
2563 {
2564  int bytes;
2565  FILE *fp = cb->ctx;
2566  fr_trie_user_t *user;
2567 
2568  if (!trie || (trie->type != FR_TRIE_USER)) {
2569  return 0;
2570  }
2571 
2572  bytes = BYTES(keylen);
2573  user = (fr_trie_user_t *) trie;
2574 
2575  if ((keylen & 0x07) != 0) {
2576  fprintf(fp, "{%d}%.*s\t%s\n", keylen, bytes, cb->start, (char const *) user->data);
2577  } else {
2578  fprintf(fp, "%.*s\t%s\n", bytes, cb->start, (char const *) user->data);
2579  }
2580 
2581  return 0;
2582 }
2583 #endif /* TESTING */
2584 
2585 
2586 /** Implement the user-visible side of the walk callback.
2587  *
2588  */
2589 static int _trie_user_cb(fr_trie_t *trie, fr_trie_callback_t *cb, int keylen, UNUSED bool more)
2590 {
2591  fr_trie_user_t *user;
2592 
2593  if (!trie || (trie->type != FR_TRIE_USER)) return 0;
2594 
2595  user = (fr_trie_user_t *) trie;
2596 
2597  /*
2598  * Call the user function with the key, key length, and data.
2599  */
2600  if (cb->user_callback(cb->start, keylen, UNCONST(void *, user->data), cb->ctx) < 0) {
2601  return -1;
2602  }
2603 
2604  return 0;
2605 }
2606 
2607 int fr_trie_walk(fr_trie_t *ft, void *ctx, fr_trie_walk_t callback)
2608 {
2609  uint8_t buffer[MAX_KEY_BYTES + 1];
2610  fr_trie_callback_t my_cb = {
2611  .start = buffer,
2612  .end = buffer + sizeof(buffer),
2613  .callback = _trie_user_cb,
2614  .user_callback = callback,
2615  .ctx = ctx
2616  };
2617 
2618  memset(buffer, 0, sizeof(buffer));
2619 
2620  /*
2621  * Call the internal walk function to do the work.
2622  */
2623  return trie_key_walk(ft->trie, &my_cb, 0, false);
2624 }
2625 
2626 
2627 /**********************************************************************/
2628 
2629 /*
2630  * Object API.
2631  */
2632 
2633 /** Find an element in the trie, returning the data.
2634  *
2635  * @param[in] ft to search in.
2636  * @param[in] data to find.
2637  * @return
2638  * - User data matching the data passed in.
2639  * - NULL if nothing matched passed data.
2640  */
2641 CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
2642 void *fr_trie_find(fr_trie_t *ft, void const *data)
2643 {
2644  fr_trie_user_t *user = (fr_trie_user_t *) ft;
2645  fr_trie_ctx_t *uctx = talloc_get_type_abort(user->data, fr_trie_ctx_t);
2646  uint8_t *key;
2647  size_t keylen;
2648 
2649  key = &uctx->buffer[0];
2650  keylen = sizeof(uctx->buffer) * 8;
2651 
2652  if (!uctx->get_key) return false;
2653 
2654  if (uctx->get_key(&key, &keylen, data) < 0) return false;
2655 
2656  return fr_trie_lookup_by_key(ft, key, keylen);
2657 }
2658 
2659 /** Match an element exactly in the trie, returning the data.
2660  *
2661  * @param[in] ft to search in.
2662  * @param[in] data to find.
2663  * @return
2664  * - User data matching the data passed in.
2665  * - NULL if nothing matched passed data.
2666  */
2667 CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
2668 void *fr_trie_match(fr_trie_t *ft, void const *data)
2669 {
2670  fr_trie_user_t *user = (fr_trie_user_t *) ft;
2671  fr_trie_ctx_t *uctx = talloc_get_type_abort(user->data, fr_trie_ctx_t);
2672  uint8_t *key;
2673  size_t keylen;
2674 
2675  key = &uctx->buffer[0];
2676  keylen = sizeof(uctx->buffer) * 8;
2677 
2678  if (!uctx->get_key) return false;
2679 
2680  if (uctx->get_key(&key, &keylen, data) < 0) return false;
2681 
2682  return fr_trie_match_by_key(ft, key, keylen);
2683 }
2684 
2685 /** Insert data into a trie
2686  *
2687  * @param[in] ft to insert data into.
2688  * @param[in] data to insert.
2689  * @return
2690  * - true if data was inserted.
2691  * - false if data already existed and was not inserted.
2692  */
2693 CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
2694 bool fr_trie_insert(fr_trie_t *ft, void const *data)
2695 {
2696  fr_trie_user_t *user = (fr_trie_user_t *) ft;
2697  fr_trie_ctx_t *uctx = talloc_get_type_abort(user->data, fr_trie_ctx_t);
2698  uint8_t *key;
2699  size_t keylen;
2700 
2701  key = &uctx->buffer[0];
2702  keylen = sizeof(uctx->buffer) * 8;
2703 
2704  if (!uctx->get_key) return false;
2705 
2706  if (uctx->get_key(&key, &keylen, data) < 0) return false;
2707 
2708  if (fr_trie_insert_by_key(ft, key, keylen, data) < 0) return false;
2709 
2710  return true;
2711 }
2712 
2713 /** Replace old data with new data, OR insert if there is no old
2714  *
2715  * @param[out] old data that was replaced. If this argument
2716  * is not NULL, then the old data will not
2717  * be freed, even if a free function is
2718  * configured.
2719  * @param[in] ft to insert data into.
2720  * @param[in] data to replace.
2721  * @return
2722  * - 1 if data was replaced.
2723  * - 0 if data was inserted.
2724  * - -1 if we failed to replace data
2725  */
2726 CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
2727 int fr_trie_replace(void **old, fr_trie_t *ft, void const *data)
2728 {
2729  fr_trie_user_t *user = (fr_trie_user_t *) ft;
2730  fr_trie_ctx_t *uctx = talloc_get_type_abort(user->data, fr_trie_ctx_t);
2731  uint8_t *key;
2732  size_t keylen;
2733  void *found;
2734 
2735  key = &uctx->buffer[0];
2736  keylen = sizeof(uctx->buffer) * 8;
2737 
2738  if (!uctx->get_key) return -1;
2739 
2740  if (uctx->get_key(&key, &keylen, data) < 0) return -1;
2741 
2742  found = trie_key_match(ft, key, 0, keylen, true); /* do exact match */
2743  if (found) {
2744  if (old) *old = found;
2745  if (fr_trie_remove_by_key(ft, key, keylen) != found) return -1;
2746  } else {
2747  if (old) *old = NULL;
2748  }
2749 
2750  /*
2751  * Insert the new key.
2752  */
2753  if (fr_trie_insert_by_key(ft, key, keylen, data) < 0) return -1;
2754 
2755  return found ? 1 : 0;
2756 }
2757 
2758 /** Remove an entry, without freeing the data
2759  *
2760  * @param[in] ft to remove data from.
2761  * @param[in] data to remove.
2762  * @return
2763  * - The user data we removed.
2764  * - NULL if we couldn't find any matching data.
2765  */
2766 CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
2767 void *fr_trie_remove(fr_trie_t *ft, void const *data)
2768 {
2769  fr_trie_user_t *user = (fr_trie_user_t *) ft;
2770  fr_trie_ctx_t *uctx = talloc_get_type_abort(user->data, fr_trie_ctx_t);
2771  uint8_t *key;
2772  size_t keylen;
2773 
2774  key = &uctx->buffer[0];
2775  keylen = sizeof(uctx->buffer) * 8;
2776 
2777  if (!uctx->get_key) return NULL;
2778 
2779  if (uctx->get_key(&key, &keylen, data) < 0) return NULL;
2780 
2781  return fr_trie_remove_by_key(ft, key, keylen);
2782 }
2783 
2784 /** Remove node and free data (if a free function was specified)
2785  *
2786  * @param[in] ft to remove data from.
2787  * @param[in] data to remove/free.
2788  * @return
2789  * - true if we removed data.
2790  * - false if we couldn't find any matching data.
2791  */
2792 CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
2793 bool fr_trie_delete(fr_trie_t *ft, void const *data)
2794 {
2795  fr_trie_user_t *user = (fr_trie_user_t *) ft;
2796  fr_trie_ctx_t *uctx = talloc_get_type_abort(user->data, fr_trie_ctx_t);
2797  uint8_t *key;
2798  size_t keylen;
2799  void *found;
2800 
2801  key = &uctx->buffer[0];
2802  keylen = sizeof(uctx->buffer) * 8;
2803 
2804  if (!uctx->get_key) return false;
2805 
2806  if (uctx->get_key(&key, &keylen, data) < 0) return false;
2807 
2808  found = fr_trie_remove_by_key(ft, key, keylen);
2809  if (!found) return false;
2810 
2811  if (!uctx->free_data) return true;
2812 
2813  uctx->free_data(found);
2814  return true;
2815 }
2816 
2817 /** Return how many nodes there are in a trie
2818  *
2819  * @param[in] ft to return node count for.
2820  */
2821 CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
2822 unsigned int fr_trie_num_elements(UNUSED fr_trie_t *ft)
2823 {
2824  return 0;
2825 }
2826 
2827 #ifdef TESTING
2828 static bool print_lineno = false;
2829 
2830 typedef struct {
2831  char *start;
2832  char *buffer;
2833  size_t buflen;
2834 } trie_sprint_ctx_t;
2835 
2836 
2837 /** Print the strings accepted by a trie to one line
2838  */
2839 static int _trie_sprint_cb(fr_trie_t *trie, fr_trie_callback_t *cb, int keylen, bool more)
2840 {
2841  int bytes, len;
2842  trie_sprint_ctx_t *ctx;
2843  fr_trie_user_t *user;
2844 
2845  ctx = cb->ctx;
2846 
2847  if (!trie) {
2848  len = snprintf(ctx->buffer, ctx->buflen, "{}");
2849  goto done;
2850  }
2851 
2852  if (trie->type != FR_TRIE_USER) return 0;
2853 
2854  bytes = BYTES(keylen);
2855  user = (fr_trie_user_t *) trie;
2856 
2857  if (!user->trie && !more) {
2858  len = snprintf(ctx->buffer, ctx->buflen, "%.*s=%s",
2859  bytes, cb->start, (char const *) user->data);
2860  } else {
2861  len = snprintf(ctx->buffer, ctx->buflen, "%.*s=%s,",
2862  bytes, cb->start, (char const *) user->data);
2863  }
2864 
2865 done:
2866  ctx->buffer += len;
2867  ctx->buflen -= len;
2868 
2869  return 0;
2870 }
2871 
2872 
2873 static void trie_sprint(fr_trie_t *trie, uint8_t const *key, int start_bit, UNUSED int lineno)
2874 {
2875  fr_trie_callback_t my_cb;
2876  trie_sprint_ctx_t my_sprint;
2877  uint8_t buffer[MAX_KEY_BYTES + 1];
2878  char out[8192];
2879 
2880  /*
2881  * Initialize the buffer
2882  */
2883  memset(buffer, 0, sizeof(buffer));
2884  memset(out, 0, sizeof(out));
2885  if (key) {
2886  memcpy(buffer, key, BYTES(start_bit) + 1);
2887  }
2888 
2889  /*
2890  * Where the output data goes.
2891  */
2892  my_sprint.start = out;
2893  my_sprint.buffer = out;
2894  my_sprint.buflen = sizeof(out);
2895 
2896  /*
2897  * Where the keys are built.
2898  */
2899  my_cb.start = buffer;
2900  my_cb.end = buffer + sizeof(buffer);
2901  my_cb.callback = _trie_sprint_cb;
2902  my_cb.user_callback = NULL;
2903  my_cb.ctx = &my_sprint;
2904 
2905  /*
2906  * Call the internal walk function to do the work.
2907  */
2908  (void) trie_key_walk(trie, &my_cb, start_bit, false);
2909 
2910  MPRINT3("%.*s%s at %d\n", start_bit, spaces, out, lineno);
2911 }
2912 
2913 
2914 /** Parse a string into bits + key
2915  *
2916  * The format is one of:
2917  *
2918  * - string such as "abcdef"
2919  * - string prefixed with a bit length, {4}a
2920  */
2921 static int arg2key(char *arg, char **key, int *length)
2922 {
2923  char *p;
2924  int bits, size;
2925 
2926  if (*arg != '{') {
2927  *key = arg;
2928  *length = BITSOF(strlen(arg));
2929  return 0;
2930  }
2931 
2932  p = strchr(arg, '}');
2933  if (!p) {
2934  MPRINT("Failed to find end '}' for {bits}\n");
2935  return -1;
2936  }
2937 
2938  bits = BITSOF(strlen(p + 1));
2939  if (!bits) {
2940  MPRINT("No key found in in '%s'\n", arg);
2941  return -1;
2942  }
2943 
2944  size = atoi(arg + 1); /* ignore end character... */
2945  if (size > bits) {
2946  MPRINT("Length '%d' is longer than bits in key %s",
2947  size, p + 1);
2948  }
2949 
2950  *key = p + 1;
2951  *length = size;
2952 
2953  return 0;
2954 }
2955 
2956 /** Our TALLOC_CTX for the data we put into the trie.
2957  *
2958  * Most people don't need to do this, they can just insert their own
2959  * data.
2960  */
2961 static void *data_ctx = NULL;
2962 
2963 /** Insert a key + data into a trie.
2964  *
2965  */
2966 static int command_insert(fr_trie_t *ft, UNUSED int argc, char **argv, UNUSED char *out, UNUSED size_t outlen)
2967 {
2968  int bits;
2969  void *data;
2970  char *key;
2971 
2972  if (arg2key(argv[0], &key, &bits) < 0) {
2973  return -1;
2974  }
2975 
2976  /*
2977  * This has to stick around in between command
2978  * invocations.
2979  */
2980  data = talloc_strdup(data_ctx, argv[1]);
2981  if (!data) {
2982  MPRINT("OOM\n");
2983  return -1;
2984  }
2985 
2986  if (fr_trie_insert_by_key(ft, key, bits, data) < 0) {
2987  MPRINT("Failed inserting key %s=%s - %s\n", key, argv[1], fr_strerror());
2988  return -1;
2989  }
2990 
2991  return 0;
2992 }
2993 
2994 /** Verify a trie recursively
2995  *
2996  * For sanity reasons, this command runs but doesn't do anything if
2997  * the code is built with no trie verification.
2998  */
2999 static int command_verify(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, UNUSED char *out, UNUSED size_t outlen)
3000 {
3001  fr_cond_assert(ft != NULL);
3002 
3003  /*
3004  * The top-level node may have a NULL talloc ctx, which
3005  * is OK. So we skip that.
3006  */
3007  if (ft->type != FR_TRIE_USER) {
3008  fprintf(stderr, "Verify failed: trie is malformed\n");
3009  return -1;
3010  }
3011 
3012  if (trie_verify(ft->trie) < 0) {
3013  fprintf(stderr, "Verify failed: %s\n", fr_strerror());
3014  return -1;
3015  }
3016 
3017  return 0;
3018 }
3019 
3020 /** Print the keys accepted by a trie
3021  *
3022  * The strings are printed to stdout.
3023  *
3024  * @todo - allow printing to a file.
3025  */
3026 static int command_keys(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, char *out, size_t outlen)
3027 {
3028  fr_trie_callback_t my_cb;
3029 
3030  my_cb.start = (uint8_t *) out;
3031  my_cb.end = (uint8_t *) (out + outlen);
3032  my_cb.callback = _trie_print_cb;
3033  my_cb.user_callback = NULL;
3034  my_cb.ctx = stdout;
3035 
3036  /*
3037  * Call the internal walk function to do the work.
3038  */
3039  return trie_key_walk(ft->trie, &my_cb, 0, false);
3040 }
3041 
3042 
3043 /** Dump the trie in internal format
3044  *
3045  * The information is printed to stdout.
3046  *
3047  * For sanity reasons, this command runs but doesn't do anything if
3048  * the code is built with no trie dumping.
3049  *
3050  * @todo - allow printing to a file.
3051  */
3052 static int command_dump(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, char *out, size_t outlen)
3053 {
3054  fr_trie_callback_t my_cb;
3055 
3056  my_cb.start = (uint8_t *) out;
3057  my_cb.end = (uint8_t *) (out + outlen);
3058  my_cb.callback = _trie_dump_cb;
3059  my_cb.user_callback = NULL;
3060  my_cb.ctx = stdout;
3061 
3062  /*
3063  * Call the internal walk function to do the work.
3064  */
3065  return trie_key_walk(ft->trie, &my_cb, 0, false);
3066 }
3067 
3068 
3069 /** Clear the entire trie without caring what's in it.
3070  *
3071  */
3072 static int command_clear(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, UNUSED char *out, UNUSED size_t outlen)
3073 {
3074  if (!ft->trie) return 0;
3075 
3076  trie_free(ft->trie);
3077  ft->trie = NULL;
3078 
3079  /*
3080  * Clean up our internal data ctx, too.
3081  */
3082  talloc_free(data_ctx);
3083  data_ctx = talloc_init_const("data_ctx");
3084 
3085  return 0;
3086 }
3087 
3088 
3089 /** Turn on line number debugging.
3090  *
3091  * @todo - add general "debug" functionality.
3092  */
3093 static int command_lineno(UNUSED fr_trie_t *ft, UNUSED int argc, char **argv, UNUSED char *out, UNUSED size_t outlen)
3094 {
3095  if (strcmp(argv[0], "true") == 0) {
3096  print_lineno = true;
3097  } else {
3098  print_lineno = false;
3099  }
3100 
3101  return 0;
3102 }
3103 
3104 
3105 /** Match an exact key + length
3106  *
3107  * Normally, the "lookup" returns the longest prefix match, so that
3108  * *long* key lookups can return *short* matches.
3109  *
3110  * In some cases, we want to know if an exact key is in the trie.
3111  * For those cases, we use this function.
3112  */
3113 static int command_match(fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen)
3114 {
3115  int bits;
3116  void *answer;
3117  char *key;
3118 
3119  if (arg2key(argv[0], &key, &bits) < 0) {
3120  return -1;
3121  }
3122 
3123  answer = trie_key_match(ft->trie, (uint8_t *) key, 0, bits, true);
3124  if (!answer) {
3125  strlcpy(out, "{}", outlen);
3126  return 0;
3127  }
3128 
3129  strlcpy(out, answer, outlen);
3130 
3131  return 0;
3132 }
3133 
3134 
3135 /** Look up a key and return user ctx data.
3136  *
3137  * This is done by longest prefix match, not exact match.
3138  */
3139 static int command_lookup(fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen)
3140 {
3141  int bits;
3142  void *answer;
3143  char *key;
3144 
3145  if (arg2key(argv[0], &key, &bits) < 0) {
3146  return -1;
3147  }
3148 
3149  answer = fr_trie_lookup_by_key(ft, key, bits);
3150  if (!answer) {
3151  strlcpy(out, "{}", outlen);
3152  return 0;
3153  }
3154 
3155  strlcpy(out, answer, outlen);
3156 
3157  return 0;
3158 }
3159 
3160 
3161 /** Remove a key from the trie.
3162  *
3163  * The key has to match exactly.
3164  */
3165 static int command_remove(fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen)
3166 {
3167  int bits;
3168  void *answer;
3169  char *key;
3170 
3171  if (arg2key(argv[0], &key, &bits) < 0) {
3172  return -1;
3173  }
3174 
3175  answer = fr_trie_remove_by_key(ft, key, bits);
3176  if (!answer) {
3177  MPRINT("Could not remove key %s\n", key);
3178  return -1;
3179  }
3180 
3181  strlcpy(out, answer, outlen);
3182 
3183  talloc_free(answer);
3184 
3185  /*
3186  * We now try to find an exact match. i.e. we don't want
3187  * to find a shorter prefix.
3188  */
3189  answer = trie_key_match(ft->trie, (uint8_t *) key, 0, bits, true);
3190  if (answer) {
3191  MPRINT("Still in trie after 'remove' for key %s, found data %s\n", key, (char const *) answer);
3192  return -1;
3193  }
3194 
3195  return 0;
3196 }
3197 
3198 
3199 /** Remove a key from the trie.
3200  *
3201  * Try to remove a key, but don't error if we can't.
3202  */
3203 static int command_try_to_remove(fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen)
3204 {
3205  int bits;
3206  void *answer;
3207  char *key;
3208 
3209  if (arg2key(argv[0], &key, &bits) < 0) {
3210  return -1;
3211  }
3212 
3213  answer = fr_trie_remove_by_key(ft, key, bits);
3214  if (!answer) {
3215  strlcpy(out, ".", outlen);
3216  return 0;
3217  }
3218 
3219  strlcpy(out, answer, outlen);
3220 
3221  talloc_free(answer);
3222 
3223  /*
3224  * We now try to find an exact match. i.e. we don't want
3225  * to find a shorter prefix.
3226  */
3227  answer = trie_key_match(ft->trie, (uint8_t *) key, 0, bits, true);
3228  if (answer) {
3229  MPRINT("Still in trie after 'remove' for key %s, found data %s\n", key, (char const *) answer);
3230  return -1;
3231  }
3232 
3233  return 0;
3234 }
3235 
3236 
3237 /** Print a trie to a string
3238  *
3239  * The trie is printed one one line. If the trie contains keys which
3240  * are not on a byte boundary, well... too bad. It gets printed
3241  * terribly.
3242  */
3243 static int command_print(fr_trie_t *ft, UNUSED int argc, UNUSED char **argv, char *out, size_t outlen)
3244 {
3245  fr_trie_callback_t my_cb;
3246  trie_sprint_ctx_t my_sprint;
3247  uint8_t buffer[MAX_KEY_BYTES + 1];
3248 
3249  /*
3250  * Where the output data goes.
3251  */
3252  my_sprint.start = out;
3253  my_sprint.buffer = out;
3254  my_sprint.buflen = outlen;
3255 
3256  /*
3257  * Where the keys are built.
3258  */
3259  my_cb.start = buffer;
3260  my_cb.end = buffer + sizeof(buffer);
3261  my_cb.callback = _trie_sprint_cb;
3262  my_cb.user_callback = NULL;
3263  my_cb.ctx = &my_sprint;
3264 
3265  memset(buffer, 0, sizeof(buffer));
3266 
3267  /*
3268  * Call the internal walk function to do the work.
3269  */
3270  return trie_key_walk(ft->trie, &my_cb, 0, false);
3271 }
3272 
3273 
3274 /** Do insert / lookup / remove all at once.
3275  *
3276  * Sometimes it's more useful to do insert / lookup / remove for
3277  * simple keys.
3278  */
3279 static int command_path(fr_trie_t *ft, int argc, char **argv, char *out, size_t outlen)
3280 {
3281  void *data;
3282  void *answer;
3283 
3284  data = talloc_strdup(ft, argv[1]); /* has to be malloc'd data, sorry */
3285  if (!data) {
3286  MPRINT("OOM\n");
3287  return -1;
3288  }
3289 
3290  if (fr_trie_insert_by_key(ft, argv[0], BITSOF(strlen(argv[0])), data) < 0) {
3291  MPRINT("Could not insert key %s=%s - %s\n", argv[0], argv[1], fr_strerror());
3292  return -1;
3293  }
3294 
3295  answer = fr_trie_lookup_by_key(ft, argv[0], BITSOF(strlen(argv[0])));
3296  if (!answer) {
3297  MPRINT("Could not look up key %s\n", argv[0]);
3298  return -1;
3299  }
3300 
3301  if (answer != data) {
3302  MPRINT("Expected to find %s, got %s\n", argv[1], (char const *) answer);
3303  return -1;
3304  }
3305 
3306  /*
3307  * Call the command 'print' to print out the key.
3308  */
3309  (void) command_print(ft, argc, argv, out, outlen);
3310 
3311  answer = fr_trie_remove_by_key(ft, (uint8_t const *) argv[0], BITSOF(strlen(argv[0])));
3312  if (!answer) {
3313  MPRINT("Could not remove key %s\n", argv[0]);
3314  return -1;
3315  }
3316 
3317  if (answer != data) {
3318  MPRINT("Expected to remove %s, got %s\n", argv[1], (char const *) answer);
3319  return -1;
3320  }
3321 
3322  talloc_free(answer);
3323 
3324  return 0;
3325 }
3326 
3327 
3328 /** Return the longest common prefix of two bit strings.
3329  *
3330  */
3331 static int command_lcp(UNUSED fr_trie_t *ft, int argc, char **argv, char *out, size_t outlen)
3332 {
3333  int lcp;
3334  int keylen1, keylen2;
3335  int start_bit;
3336  uint8_t const *key1, *key2;
3337 
3338  if (argc == 2) {
3339  key1 = (uint8_t const *) argv[0];
3340  keylen1 = BITSOF(strlen(argv[0]));
3341 
3342  key2 = (uint8_t const *) argv[1];
3343  keylen2 = BITSOF(strlen(argv[1]));
3344  start_bit = 0;
3345 
3346  } else if (argc == 5) {
3347  key1 = (uint8_t const *) argv[0];
3348  keylen1 = atoi(argv[1]);
3349  if ((keylen1 < 0) || (keylen1 > (int) BITSOF(strlen(argv[0])))) {
3350  MPRINT("length of key1 %s is larger than string length %ld\n",
3351  argv[1], BITSOF(strlen(argv[0])));
3352  return -1;
3353  }
3354 
3355  key2 = (uint8_t const *) argv[2];
3356  keylen2 = atoi(argv[3]);
3357  if ((keylen2 < 0) || (keylen2 > (int) BITSOF(strlen(argv[2])))) {
3358  MPRINT("length of key2 %s is larger than string length %ld\n",
3359  argv[3], BITSOF(strlen(argv[2])));
3360  return -1;
3361  }
3362 
3363  start_bit = atoi(argv[4]);
3364  if ((start_bit < 0) || (start_bit > 7)) {
3365  MPRINT("start_bit has invalid value %s\n", argv[4]);
3366  return -1;
3367  }
3368 
3369  } else {
3370  MPRINT("Invalid number of arguments\n");
3371  return -1;
3372  }
3373 
3374  lcp = fr_trie_key_lcp(key1, keylen1, key2, keylen2, start_bit);
3375 
3376  snprintf(out, outlen, "%d", lcp);
3377  return 0;
3378 }
3379 
3380 /** Get chunks from raw data
3381  *
3382  */
3383 static int command_chunk(UNUSED fr_trie_t *ft, UNUSED int argc, char **argv, char *out, size_t outlen)
3384 {
3385  int start_bit, num_bits;
3386  uint16_t chunk;
3387 
3388  start_bit = atoi(argv[1]);
3389  num_bits = atoi(argv[2]);
3390 
3391  chunk = get_chunk((uint8_t const *) argv[0], start_bit, num_bits);
3392 
3393  snprintf(out, outlen, "%04x", chunk);
3394  return 0;
3395 }
3396 
3397 /** A function to parse a trie command line.
3398  *
3399  */
3400 typedef int (*fr_trie_function_t)(fr_trie_t *ft, int argc, char **argv, char *out, size_t outlen);
3401 
3402 /** Data structure which holds the trie command name, function, etc.
3403  *
3404  */
3405 typedef struct {
3406  char const *name;
3407  fr_trie_function_t function;
3408  int min_argc;
3409  int max_argc;
3410  bool output;
3411 } fr_trie_command_t;
3412 
3413 
3414 /** The trie commands for debugging.
3415  *
3416  */
3417 static fr_trie_command_t commands[] = {
3418  { "lcp", command_lcp, 2, 5, true },
3419  { "chunk", command_chunk, 3, 3, true },
3420  { "path", command_path, 2, 2, true },
3421  { "insert", command_insert, 2, 2, false },
3422  { "match", command_match, 1, 1, true },
3423  { "lookup", command_lookup, 1, 1, true },
3424  { "remove", command_remove, 1, 1, true },
3425  { "-remove", command_try_to_remove, 1, 1, true },
3426  { "print", command_print, 0, 0, true },
3427  { "dump", command_dump, 0, 0, false },
3428  { "keys", command_keys, 0, 0, false },
3429  { "verify", command_verify, 0, 0, false },
3430  { "lineno", command_lineno, 1, 1, false },
3431  { "clear", command_clear, 0, 0, false },
3432  { NULL, NULL, 0, 0}
3433 };
3434 
3435 #define MAX_ARGC (16)
3436 int main(int argc, char **argv)
3437 {
3438  int lineno = 0;
3439  int ret = 0;
3440  fr_trie_t *ft;
3441  FILE *fp;
3442  int my_argc;
3443  char *my_argv[MAX_ARGC];
3444  char buffer[8192];
3445  char output[8192];
3446 
3447  if (argc < 2) {
3448  fprintf(stderr, "Please specify filename\n");
3449  fr_exit_now(EXIT_SUCCESS);
3450  }
3451 
3452  fp = fopen(argv[1], "r");
3453  if (!fp) {
3454  fprintf(stderr, "Failed opening %s: %s\n", argv[1], fr_syserror(errno));
3455  fr_exit_now(1);
3456  }
3457 
3458  /*
3459  * Tell us if we leaked memory.
3460  */
3461  talloc_enable_null_tracking();
3462 
3463  data_ctx = talloc_init_const("data_ctx");
3464 
3465  ft = fr_trie_alloc(NULL, NULL, NULL);
3466  if (!ft) {
3467  fprintf(stderr, "Failed creating trie\n");
3468  fr_exit_now(1);
3469  }
3470 
3471  while (fgets(buffer, sizeof(buffer), fp) != NULL) {
3472  int i, cmd;
3473  char *p;
3474 
3475  lineno++;
3476 
3477  /*
3478  * Remove comments.
3479  */
3480  for (p = buffer; *p != '\0'; p++) {
3481  if (*p == '#') {
3482  *p = '\0';
3483  break;
3484  }
3485  }
3486 
3487  /*
3488  * Skip leading whitespace.
3489  */
3490  p = buffer;
3491  fr_skip_whitespace(p);
3492 
3493  /*
3494  * Skip (now) blank lines.
3495  */
3496  if (!*p) continue;
3497 
3498  my_argc = fr_dict_str_to_argv(p, my_argv, MAX_ARGC);
3499 
3500  cmd = -1;
3501  for (i = 0; commands[i].name != NULL; i++) {
3502  if (strcmp(my_argv[0], commands[i].name) != 0) continue;
3503 
3504  cmd = i;
3505  break;
3506  }
3507 
3508  if (cmd < 0) {
3509  fprintf(stderr, "Unknown command '%s' at line %d\n",
3510  my_argv[0], lineno);
3511  ret = 1;
3512  break;
3513  }
3514 
3515  /*
3516  * argv[0] is the command.
3517  * argv[argc-1] is the output.
3518  */
3519  if (((commands[cmd].min_argc + 1 + commands[cmd].output) > my_argc) ||
3520  ((commands[cmd].max_argc + 1 + commands[cmd].output) < my_argc)) {
3521  fprintf(stderr, "Invalid number of arguments to %s at line %d. Expected %d, got %d\n",
3522  my_argv[0], lineno, commands[cmd].min_argc + 1, my_argc - 1);
3523  fr_exit_now(1);
3524  }
3525 
3526  if (print_lineno) {
3527  printf("%d ", lineno);
3528  fflush(stdout);
3529  }
3530 
3531  MPRINT3("[%d] %s\n", lineno, my_argv[0]);
3532  if (commands[cmd].function(ft, my_argc - 1 - commands[cmd].output, &my_argv[1], output, sizeof(output)) < 0) {
3533  fprintf(stderr, "Failed running %s at line %d\n",
3534  my_argv[0], lineno);
3535  fr_exit_now(1);
3536  }
3537 
3538  if (!commands[cmd].output) continue;
3539 
3540  if (strcmp(output, my_argv[my_argc - 1]) != 0) {
3541  fprintf(stderr, "Failed running %s at line %d: Expected '%s' got '%s'\n",
3542  my_argv[0], lineno, my_argv[my_argc - 1], output);
3543  fr_exit_now(1);
3544  }
3545  }
3546 
3547  fclose(fp);
3548 
3549  trie_free(ft);
3550  talloc_free(data_ctx);
3551 
3552  talloc_report_full(NULL, stdout); /* Print details of any leaked memory */
3553  talloc_disable_null_tracking(); /* Cleanup talloc null tracking context */
3554 
3555  return ret;
3556 }
3557 #endif
buffer
static int const char char buffer[256]
Definition: acutest.h:574
msg
log_entry msg
Definition: acutest.h:794
UNCONST
#define UNCONST(_type, _ptr)
Remove const qualification from a pointer.
Definition: build.h:165
RCSID
#define RCSID(id)
Definition: build.h:481
DIAG_ON
#define DIAG_ON(_x)
Definition: build.h:456
UNUSED
#define UNUSED
Definition: build.h:313
DIAG_OFF
#define DIAG_OFF(_x)
Definition: build.h:455
split
static int split(char **input, char **output, bool syntax_string)
Definition: command.c:385
uctx
fr_dcursor_eval_t void const * uctx
Definition: dcursor.h:546
fr_cond_assert
#define fr_cond_assert(_x)
Calls panic_action ifndef NDEBUG, else logs error and evaluates to value of _x.
Definition: debug.h:139
fr_exit_now
#define fr_exit_now(_x)
Exit without calling atexit() handlers, producing a log message in debug builds.
Definition: debug.h:234
spaces
static char const * spaces
Definition: dependency.c:371
main
int main(int argc, char **argv)
Definition: dhcpclient.c:521
fr_dict_str_to_argv
int fr_dict_str_to_argv(char *str, char **argv, int max_argc)
Definition: dict_tokenize.c:86
talloc_free
talloc_free(reap)
uint16_t
unsigned short uint16_t
Definition: merged_model.c:31
uint32_t
unsigned int uint32_t
Definition: merged_model.c:33
bool
unsigned char bool
Definition: merged_model.c:19
uint8_t
unsigned char uint8_t
Definition: merged_model.c:30
used
static size_t used
Definition: message_set_test.c:51
depth
static uint8_t depth(fr_minmax_heap_index_t i)
Definition: minmax_heap.c:83
fr_skip_whitespace
#define fr_skip_whitespace(_p)
Skip whitespace ('\t', '\n', '\v', '\f', '\r', ' ')
Definition: misc.h:59
fr_free_t
void(* fr_free_t)(void *)
Definition: misc.h:39
done
static bool done
Definition: radclient.c:80
comp
static int8_t comp(void const *a, void const *b)
Definition: rbmonkey.c:13
name
static char const * name
Definition: rlm_redis_ippool_tool.c:156
xor
static void xor(char *out, char *in1, char *in2, int n)
Definition: smbdes.c:183
snprintf
PUBLIC int snprintf(char *string, size_t length, char *format, va_alist)
Definition: snprintf.c:689
strlcpy
size_t strlcpy(char *dst, char const *src, size_t siz)
Definition: strlcpy.c:34
fr_syserror
char const * fr_syserror(int num)
Guaranteed to be thread-safe version of strerror.
Definition: syserror.c:243
fr_table_ptr_sorted_t::name
fr_table_elem_name_t name
Definition: table.h:66
talloc_init_const
static TALLOC_CTX * talloc_init_const(char const *name)
Allocate a top level chunk with a constant name.
Definition: talloc.h:112
fr_trie_key_walk_t
int(* fr_trie_key_walk_t)(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
Definition: trie.c:2174
fr_trie_alloc
fr_trie_t * fr_trie_alloc(TALLOC_CTX *ctx, fr_trie_key_t get_key, fr_free_t free_data)
Allocate a trie.
Definition: trie.c:741
MPRINT
#define MPRINT(...)
Internal sanity checks for debugging.
Definition: trie.c:119
trie_match_table
static trie_key_match_t trie_match_table[FR_TRIE_MAX]
Definition: trie.c:1200
trie_user_remove
static void * trie_user_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
Definition: trie.c:1912
trie_check
#define trie_check(_trie, _key, _start_bit, _end_bit, _data, _lineno)
Definition: trie.c:1327
trie_remove_table
static trie_key_remove_t trie_remove_table[FR_TRIE_MAX]
Definition: trie.c:2112
MAX_KEY_BITS
#define MAX_KEY_BITS
Definition: trie.c:95
trie_key_match
static void * trie_key_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
Match a key in a trie and return user ctx, if any.
Definition: trie.c:1226
trie_walk_table
static fr_trie_key_walk_t trie_walk_table[FR_TRIE_MAX]
Definition: trie.c:2253
fr_trie_node_t::used
int used
Definition: trie.c:493
TRIE_HEADER
#define TRIE_HEADER
Definition: trie.c:480
trie_node_alloc
static fr_trie_node_t * trie_node_alloc(TALLOC_CTX *ctx, int bits)
Definition: trie.c:528
fr_trie_path_alloc
static fr_trie_path_t * fr_trie_path_alloc(TALLOC_CTX *ctx, uint8_t const *key, int start_bit, int end_bit)
Definition: trie.c:634
trie_key_match_t
void *(* trie_key_match_t)(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
Definition: trie.c:1106
trie_node_remove
static void * trie_node_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
Definition: trie.c:1934
fr_trie_path_t::chunk
uint16_t chunk
Definition: trie.c:510
trie_key_walk
static int trie_key_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
Definition: trie.c:2264
BYTEOF
#define BYTEOF(_x)
Definition: trie.c:137
trie_key_alloc
static fr_trie_t * trie_key_alloc(TALLOC_CTX *ctx, uint8_t const *key, int start_bit, int end_bit, void *data)
Definition: trie.c:887
MAX_KEY_BYTES
#define MAX_KEY_BYTES
Definition: trie.c:94
get_chunk
static uint16_t get_chunk(uint8_t const *key, uint32_t start_bit, uint32_t num_bits)
Return a chunk of a key (in the low bits) for use in 2^N node de-indexing.
Definition: trie.c:337
fr_trie_ctx_t::free_data
fr_free_t free_data
Definition: trie.c:729
fr_trie_node_t::trie
fr_trie_t * trie[]
Definition: trie.c:494
trie_key_remove
static void * trie_key_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
Remove a key from a trie, and return the user data.
Definition: trie.c:2126
fr_trie_remove_by_key
void * fr_trie_remove_by_key(fr_trie_t *ft, void const *key, size_t keylen)
Remove a key and return the associated user ctx.
Definition: trie.c:2154
fr_trie_user_alloc
static fr_trie_user_t * fr_trie_user_alloc(TALLOC_CTX *ctx, void const *data)
Definition: trie.c:613
fr_trie_path_t::trie
fr_trie_t * trie
Definition: trie.c:508
fr_trie_walk
int fr_trie_walk(fr_trie_t *ft, void *ctx, fr_trie_walk_t callback)
Definition: trie.c:2607
BYTES
#define BYTES(_x)
Definition: trie.c:138
MPRINT3
#define MPRINT3(...)
Definition: trie.c:121
fr_trie_match_by_key
void * fr_trie_match_by_key(fr_trie_t const *ft, void const *key, size_t keylen)
Match a key and length in a trie and return user ctx, if any.
Definition: trie.c:1286
fr_trie_callback_s::user_callback
fr_trie_walk_t user_callback
Definition: trie.c:2185
_trie_user_cb
static int _trie_user_cb(fr_trie_t *trie, fr_trie_callback_t *cb, int keylen, UNUSED bool more)
Implement the user-visible side of the walk callback.
Definition: trie.c:2589
fr_trie_callback_s::start
uint8_t * start
Definition: trie.c:2179
xor2lcp
static uint8_t xor2lcp[256]
Definition: trie.c:172
trie_key_remove_t
void *(* trie_key_remove_t)(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
Definition: trie.c:1910
trie_path_remove
static void * trie_path_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
Definition: trie.c:1974
fr_trie_user_t::data
void * data
Definition: trie.c:501
trie_path_insert
static int trie_path_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)
Definition: trie.c:1422
trie_node_insert
static int trie_node_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)
Definition: trie.c:1348
fr_trie_callback_s::callback
fr_trie_key_walk_t callback
Definition: trie.c:2184
trie_sprint
#define trie_sprint(_trie, _key, _start_bit, _lineno)
Definition: trie.c:122
VERIFY
#define VERIFY(_x)
Definition: trie.c:130
BITSOF
#define BITSOF(_x)
Definition: trie.c:136
trie_insert_table
static trie_key_insert_t trie_insert_table[FR_TRIE_MAX]
Definition: trie.c:1785
trie_node_walk
static int trie_node_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
Definition: trie.c:2197
fr_trie_type_t
fr_trie_type_t
Definition: trie.c:454
FR_TRIE_PATH
@ FR_TRIE_PATH
Definition: trie.c:458
FR_TRIE_NODE
@ FR_TRIE_NODE
Definition: trie.c:463
FR_TRIE_INVALID
@ FR_TRIE_INVALID
Definition: trie.c:455
FR_TRIE_USER
@ FR_TRIE_USER
Definition: trie.c:456
FR_TRIE_MAX
#define FR_TRIE_MAX
Definition: trie.c:466
TRIE_TYPE_CHECK
#define TRIE_TYPE_CHECK(_x, _r)
Definition: trie.c:481
MPRINT2
#define MPRINT2(...)
Definition: trie.c:120
write_chunk
static void write_chunk(uint8_t *out, int start_bit, int num_bits, uint16_t chunk)
Write a chunk to an output buffer.
Definition: trie.c:409
fr_trie_key_lcp
static int fr_trie_key_lcp(uint8_t const *key1, int keylen1, uint8_t const *key2, int keylen2, int start_bit)
Get the longest prefix of the two keys.
Definition: trie.c:227
fr_trie_user_t::trie
fr_trie_t * trie
Definition: trie.c:500
trie_user_walk
static int trie_user_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
Definition: trie.c:2188
trie_node_split
static fr_trie_node_t * trie_node_split(TALLOC_CTX *ctx, fr_trie_node_t *node, int bits)
Split a node at bits.
Definition: trie.c:773
trie_add_edge
static int trie_add_edge(fr_trie_t *trie, uint16_t chunk, fr_trie_t *child)
Add an edge to a node.
Definition: trie.c:1046
trie_key_insert
static int trie_key_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data))
Insert a binary key into the trie.
Definition: trie.c:1810
fr_trie_s::TRIE_HEADER
TRIE_HEADER
Definition: trie.c:485
trie_path_split
static fr_trie_path_t * trie_path_split(TALLOC_CTX *ctx, fr_trie_path_t *path, int start_bit, int lcp)
Definition: trie.c:831
fr_trie_path_t::key
uint8_t key[2]
Definition: trie.c:511
CC_NO_UBSAN
CC_NO_UBSAN(function)
Find an element in the trie, returning the data.
Definition: trie.c:2641
fr_trie_s::trie
fr_trie_t * trie
Definition: trie.c:487
trie_path_match
static void * trie_path_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
Definition: trie.c:1160
MAX_NODE_BITS
#define MAX_NODE_BITS
Definition: trie.c:98
fr_trie_callback_s::end
uint8_t const * end
Definition: trie.c:2180
trie_user_match
static void * trie_user_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
Definition: trie.c:1110
fr_trie_insert_by_key
int fr_trie_insert_by_key(fr_trie_t *ft, void const *key, size_t keylen, void const *data)
Insert a key and user ctx into a trie.
Definition: trie.c:1875
fr_trie_ctx_t::get_key
fr_trie_key_t get_key
Definition: trie.c:728
fr_trie_lookup_by_key
void * fr_trie_lookup_by_key(fr_trie_t const *ft, void const *key, size_t keylen)
Lookup a key in a trie and return user ctx, if any.
Definition: trie.c:1262
trie_path_walk
static int trie_path_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
Definition: trie.c:2219
start_bit_mask
static uint8_t start_bit_mask[8]
Definition: trie.c:150
trie_user_insert
static int trie_user_insert(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)
Definition: trie.c:1334
used_bit_mask
static uint8_t used_bit_mask[8]
Definition: trie.c:155
trie_key_insert_t
int(* trie_key_insert_t)(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)
Definition: trie.c:1332
trie_node_match
static void * trie_node_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
Definition: trie.c:1145
trie_free
static void trie_free(fr_trie_t *trie)
Free a fr_trie_t.
Definition: trie.c:562
fr_trie_callback_s
Definition: trie.c:2178
fr_trie_ctx_t
Definition: trie.c:726
fr_trie_node_t
Definition: trie.c:490
fr_trie_path_t
Definition: trie.c:505
fr_trie_s
Definition: trie.c:484
fr_trie_user_t
Definition: trie.c:497
fr_trie_key_t
int(* fr_trie_key_t)(uint8_t **out, size_t *outlen, void const *data)
Definition: trie.h:56
fr_trie_delete
bool fr_trie_delete(fr_trie_t *ft, void const *data)
fr_trie_insert
bool fr_trie_insert(fr_trie_t *ft, void const *data)
fr_trie_find
void * fr_trie_find(fr_trie_t *ft, void const *data)
fr_trie_remove
void * fr_trie_remove(fr_trie_t *ft, void const *data)
fr_trie_match
void * fr_trie_match(fr_trie_t *ft, void const *data)
fr_trie_num_elements
unsigned int fr_trie_num_elements(fr_trie_t *ft)
fr_trie_walk_t
int(* fr_trie_walk_t)(uint8_t const *key, size_t keylen, void *data, void *uctx)
Walk over a trie.
Definition: trie.h:43
fr_trie_replace
int fr_trie_replace(void **old, fr_trie_t *ft, void const *data))
commands
static fr_table_ptr_sorted_t commands[]
Definition: unit_test_attribute.c:3003
command_print
static void command_print(void)
Definition: unit_test_attribute.c:1119
command_match
static size_t command_match(command_result_t *result, command_file_ctx_t *cc, char *data, size_t data_used, char *in, size_t inlen)
Compare the data buffer to an expected value.
Definition: unit_test_attribute.c:2295
command_clear
static size_t command_clear(command_result_t *result, UNUSED command_file_ctx_t *cc, char *data, size_t UNUSED data_used, UNUSED char *in, UNUSED size_t inlen)
Definition: unit_test_attribute.c:1375
fr_strerror
char const * fr_strerror(void)
Get the last library error.
Definition: strerror.c:554
fr_strerror_printf
#define fr_strerror_printf(_fmt,...)
Log to thread local error buffer.
Definition: strerror.h:64
fr_strerror_const
#define fr_strerror_const(_msg)
Definition: strerror.h:223
data
static fr_slen_t data
Definition: value.h:1265
nonnull
int nonnull(2, 5))
out
static size_t char ** out
Definition: value.h:997
Generated by   doxygen 1.9.1