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