23 RCSID(
"$Id: 237c42ab6edc7280b38a8a0214250d17802925d5 $")
25 #include <freeradius-devel/util/dict.h>
26 #include <freeradius-devel/util/misc.h>
27 #include <freeradius-devel/util/syserror.h>
28 #include <freeradius-devel/util/trie.h>
73 #if !defined(NO_PATH_COMPRESSION) && !defined(WITH_PATH_COMPRESSION)
74 #define WITH_PATH_COMPRESSION
79 #ifdef WITH_NODE_COMPRESSION
80 #ifndef WITH_PATH_COMPRESSION
81 #define WITH_PATH_COMPRESSION
85 #define MAX_COMP_BITS (8)
88 #ifndef MAX_COMP_EDGES
89 #define MAX_COMP_EDGES (4)
94 #define MAX_KEY_BYTES (256)
95 #define MAX_KEY_BITS (MAX_KEY_BYTES * 8)
98 #define MAX_NODE_BITS (4)
111 #define WITH_TRIE_VERIFY (1)
112 # define MPRINT(...) fprintf(stderr, ## __VA_ARGS__)
115 # define MPRINT2(...)
116 # define MPRINT3(...)
120 # define MPRINT2(...)
121 # define MPRINT3(...)
122 #define trie_sprint(_trie, _key, _start_bit, _lineno)
125 #ifdef WITH_TRIE_VERIFY
128 #define VERIFY(_x) if (trie_verify((fr_trie_t *) _x) < 0) do { fprintf(stderr, "FAIL VERIFY at %d - %s\n", __LINE__, fr_strerror()); fr_cond_assert(0); } while (0)
136 #define BITSOF(_x) ((_x) * 8)
137 #define BYTEOF(_x) ((_x) >> 3)
138 #define BYTES(_x) (((_x) + 0x07) >> 3)
151 0xff, 0x7f, 0x3f, 0x1f,
152 0x0f, 0x07, 0x03, 0x01
156 0x80, 0xc0, 0xe0, 0xf0,
157 0xf8, 0xfc, 0xfe, 0xff,
164 static char const *
spaces =
" ";
168 #if defined(WITH_PATH_COMPRESSION) || defined(TESTING)
231 if (!keylen1 || !keylen2)
return 0;
235 if (end_bit > keylen2) end_bit = keylen2;
236 end_bit += start_bit;
238 MPRINT2(
"%.*sLCP %02x%02x %02x%02x start %d length %d, %d\n",
239 start_bit,
spaces, key1[0], key1[1], key2[0], key2[1], start_bit, keylen1, keylen2);
243 while (end_bit > 0) {
271 if ((start_bit & 0x07) != 0) {
274 num_bits -= start_bit;
275 end_bit -= start_bit;
321 static void hex_dump(FILE *fp,
char const *
msg,
uint8_t const *key,
int start_bit,
int end_bit)
325 fprintf(fp,
"%s\ts=%zd e=%zd\t\t",
msg, start_bit, end_bit);
327 for (i = 0; i <
BYTES(end_bit); i++) {
328 fprintf(fp,
"%02x ", key[i]);
359 chunk = key[0] >> (7 - start_bit);
367 if (start_bit == 0) {
368 if (num_bits < 7)
return key[0] >> (8 - num_bits);
369 if (num_bits == 8)
return key[0];
371 chunk = (key[0] << 8) | key[1];
372 if (num_bits < 16) chunk >>= (16 - num_bits);
385 if (
BYTEOF(start_bit + num_bits - 1) != 0) {
397 end_bit = (start_bit + num_bits) & 0x07;
398 if (end_bit != 0) chunk >>= 8 - end_bit;
427 out[0] &= ~((1 << (7 - start_bit)) - 1);
428 out[0] |= chunk << (7 - start_bit);
442 if ((start_bit + num_bits) < 16) chunk <<= (16 - (start_bit + num_bits));
449 out[0] |= chunk >> 8;
451 if ((start_bit + num_bits) > 8) {
452 out[1] = chunk & 0xff;
459 #ifdef WITH_PATH_COMPRESSION
462 #ifdef WITH_NODE_COMPRESSION
468 #define FR_TRIE_MAX (FR_TRIE_NODE + 1)
471 static int trie_number = 0;
473 #define TRIE_HEADER uint8_t type; uint8_t bits; int number
474 #define TRIE_TYPE_CHECK(_x, _r) do { if ((trie->type == FR_TRIE_INVALID) || \
475 (trie->type >= FR_TRIE_MAX) || \
476 !trie_ ## _x ##_table [trie->type]) { \
477 fr_strerror_printf("unknown trie type %d", trie->type); \
482 #define TRIE_HEADER uint8_t type; uint8_t bits
483 #define TRIE_TYPE_CHECK(_x, _r)
506 #ifdef WITH_PATH_COMPRESSION
517 #ifdef WITH_NODE_COMPRESSION
535 if ((bits <= 0) || (bits > 8)) {
548 talloc_set_name_const(node,
"fr_trie_node_t");
553 node->number = trie_number++;
580 for (i = 0; i < (1 << node->bits); i++) {
581 if (!node->
trie[i])
continue;
590 #ifdef WITH_PATH_COMPRESSION
600 #ifdef WITH_NODE_COMPRESSION
601 if (trie->type == FR_TRIE_COMP) {
602 fr_trie_comp_t *
comp = (fr_trie_comp_t *) trie;
605 for (i = 0; i <
comp->used; i++) {
629 user->number = trie_number++;
635 #ifdef WITH_PATH_COMPRESSION
640 if (end_bit <= start_bit) {
649 key += (start_bit >> 3);
650 end_bit -= 8 * (start_bit >> 3);
651 start_bit -= 8 * (start_bit >> 3);
654 if ((end_bit - start_bit) > 16) {
675 path->bits = end_bit - start_bit;
684 fprintf(stderr,
"PATH ALLOC key %02x%02x start %d end %d bits %d == chunk %04x key %02x%02x\n",
686 start_bit, end_bit, path->bits,
691 path->number = trie_number++;
698 #ifdef WITH_NODE_COMPRESSION
699 static fr_trie_comp_t *fr_trie_comp_alloc(TALLOC_CTX *ctx,
int bits)
701 fr_trie_comp_t *
comp;
706 if ((bits <= 2) || (bits > MAX_COMP_BITS)) {
711 comp = talloc_zero(ctx, fr_trie_comp_t);
717 comp->type = FR_TRIE_COMP;
722 comp->number = trie_number++;
753 if (!user)
return NULL;
778 int i, remaining_bits;
784 if ((bits == 0) || (bits >= node->bits) || (node->bits == 1)) {
790 if (!
split)
return NULL;
792 remaining_bits = node->bits - bits;
798 for (i = 0; i < (1 << bits); i++) {
808 for (j = 0; j < (1 << remaining_bits); j++) {
809 if (!node->trie[(i << remaining_bits) + j])
continue;
811 child->
trie[j] = node->
trie[(i << remaining_bits) + j];
812 node->
trie[(i << remaining_bits) + j] = NULL;
832 #ifdef WITH_PATH_COMPRESSION
840 if ((lcp <= 0) || (lcp > path->bits) || (start_bit < 0)) {
845 MPRINT3(
"%.*sSPLIT start %d\n", start_bit,
spaces, start_bit);
849 if (!
split)
return NULL;
851 child =
fr_trie_path_alloc(ctx, &path->key[0], start_bit + lcp, start_bit + path->bits);
852 if (!child)
return NULL;
878 MPRINT3(
"%.*ssplit %02x%02x start %d split %d -> %02x%02x %02x%02x\n",
880 path->key[0], path->key[1],
881 start_bit,
split->bits,
883 child->
key[0], child->
key[1]);
896 if (start_bit > end_bit) {
904 next_bit = start_bit + 16 - (start_bit & 0x07);
906 if (next_bit >= end_bit) {
908 if (!path)
return NULL;
916 if (!path)
return NULL;
933 if (start_bit == end_bit) {
937 bits = end_bit - start_bit;
944 if (!node)
return NULL;
946 chunk =
get_chunk(key, start_bit, node->bits);
948 if (!node->
trie[chunk]) {
963 #ifdef WITH_NODE_COMPRESSION
964 static fr_trie_t *trie_comp_split(TALLOC_CTX *ctx, fr_trie_comp_t *
comp,
int start_bit,
int bits)
967 fr_trie_comp_t *
split;
973 if ((bits == 0) || (bits >=
comp->bits)) {
978 split = fr_trie_comp_alloc(ctx, bits);
979 if (!
split)
return NULL;
981 if (start_bit > 7) start_bit &= 0x07;
992 for (i = 0; i <
comp->used; i++) {
998 before = i >> (
comp->bits - bits);
999 after = i & ((1 << bits) - 1);
1007 for (j = 0; j <
split->used; j++) {
1008 if (before ==
split->index[j]) {
1014 if (
split->index[where]) {
1021 if (!path)
goto fail;
1031 for (i = 0; i <
split->used; i++) {
1042 #ifdef WITH_PATH_COMPRESSION
1052 #ifdef WITH_NODE_COMPRESSION
1053 if (trie->type == FR_TRIE_COMP) {
1054 fr_trie_comp_t *
comp = (fr_trie_comp_t *) trie;
1057 if (chunk >= (1 <<
comp->bits))
return -1;
1059 if (
comp->used >= MAX_COMP_EDGES)
return -1;
1062 for (i = 0; i <
comp->used; i++) {
1063 if (
comp->index[i] < chunk)
continue;
1065 if (
comp->index[edge] == chunk)
return -1;
1071 if (edge == MAX_COMP_EDGES)
return -1;
1077 for (i = edge; i <
comp->used; i++) {
1078 comp->index[i + 1] =
comp->index[i];
1082 comp->index[edge] = chunk;
1083 comp->trie[edge] = child;
1095 if (chunk >= (1 << node->bits))
return -1;
1097 if (node->
trie[chunk] != NULL)
return -1;
1100 node->
trie[chunk] = child;
1108 typedef void *(*trie_key_match_t)(
fr_trie_t *trie,
uint8_t const *key,
int start_bit,
int end_bit,
bool exact);
1121 if (start_bit == end_bit)
return user->
data;
1137 MPRINT2(
"no exact match at %d\n", __LINE__);
1152 chunk =
get_chunk(key, start_bit, node->bits);
1153 if (!node->
trie[chunk]) {
1154 MPRINT2(
"no match for node chunk %02x at %d\n", chunk, __LINE__);
1158 return trie_key_match(node->
trie[chunk], key, start_bit + node->bits, end_bit, exact);
1161 #ifdef WITH_PATH_COMPRESSION
1167 chunk =
get_chunk(key, start_bit, path->bits);
1168 if (chunk != path->
chunk)
return NULL;
1174 #ifdef WITH_NODE_COMPRESSION
1175 static void *trie_comp_match(
fr_trie_t *trie,
uint8_t const *key,
int start_bit,
int end_bit,
bool exact)
1179 fr_trie_comp_t *
comp = (fr_trie_comp_t *) trie;
1183 for (i = 0; i <
comp->used; i++) {
1184 if (
comp->index[i] < chunk)
continue;
1186 if (
comp->index[i] == chunk) {
1205 #ifdef WITH_PATH_COMPRESSION
1208 #ifdef WITH_NODE_COMPRESSION
1209 [ FR_TRIE_COMP ] = trie_comp_match,
1230 if (!trie)
return NULL;
1235 if ((start_bit + trie->bits) > end_bit) {
1236 MPRINT2(
"%d + %d = %d > %d\n",
1237 start_bit, trie->bits, start_bit + trie->bits, end_bit);
1239 MPRINT2(
"no match for key too short for trie NODE-%d at %d\n", trie->number, __LINE__);
1270 if (!ft->
trie)
return NULL;
1294 if (!ft->
trie)
return NULL;
1315 MPRINT3(
"%.*sFailed to find user data %s from start %d end %d at %d\n", start_bit,
spaces,
data,
1316 start_bit, end_bit, lineno);
1320 if (answer !=
data) {
1323 MPRINT3(
"%.*sFound wrong user data %s != %s, from start %d end %d at %d\n", start_bit,
spaces,
1324 answer,
data, start_bit, end_bit, lineno);
1329 #define trie_check(_trie, _key, _start_bit, _end_bit, _data, _lineno)
1341 MPRINT3(
"user insert to start %d end %d with data %s\n", start_bit, end_bit, (
char *)
data);
1346 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1357 MPRINT3(
"%.*snode insert end %d with data %s\n",
1366 if ((start_bit + node->bits) > end_bit) {
1369 MPRINT3(
"%.*snode insert splitting %d at %d start %d end %d with data %s\n",
1371 node->bits, start_bit - end_bit,
1372 start_bit, end_bit, (
char *)
data);
1384 chunk =
get_chunk(key, start_bit, node->bits);
1390 if (!node->
trie[chunk]) {
1392 if (!node->
trie[chunk]) {
1394 if (trie_to_free)
trie_free(trie_to_free);
1404 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1406 MPRINT(
"Failed recursing at %d\n", __LINE__);
1407 if (trie_to_free)
trie_free(trie_to_free);
1414 MPRINT3(
"%.*snode insert returning at %d\n",
1415 start_bit,
spaces, __LINE__);
1417 if (trie_to_free)
trie_free(trie_to_free);
1423 #ifdef WITH_PATH_COMPRESSION
1435 MPRINT3(
"%.*spath insert start %d end %d with key %02x%02x data %s\n",
1436 start_bit,
spaces, start_bit, end_bit, key[0], key[1], (
char *)
data);
1444 if (start_bit + path->bits <= end_bit) {
1445 chunk =
get_chunk(key, start_bit, path->bits);
1451 if (chunk == path->
chunk) {
1452 MPRINT3(
"%.*spath chunk matches %04x bits of %d\n",
1453 start_bit,
spaces, chunk, path->bits);
1454 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1461 MPRINT3(
"%.*spath returning at %d\n", start_bit,
spaces, __LINE__);
1467 MPRINT3(
"%.*spath using %d\n", start_bit,
spaces, path->bits);
1474 bits = end_bit - start_bit;
1475 MPRINT3(
"%.*spath limiting %d to %d\n", start_bit,
spaces, path->bits, bits);
1483 start_bit2 = start_bit;
1484 if (start_bit2 > 7) {
1485 key2 += (start_bit2 >> 3);
1486 start_bit2 -= 8 * (start_bit2 >> 3);
1501 if (lcp == path->bits) {
1514 MPRINT3(
"%.*spath split depth %d bits %d at lcp %d with data %s\n",
1515 start_bit,
spaces, start_bit, path->bits, lcp, (
char *)
data);
1517 MPRINT3(
"%.*spath key %02x%02x input key %02x%02x, offset %d\n",
1519 path->
key[0],path->
key[1],
1538 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1554 MPRINT3(
"%.*spath returning at %d\n", start_bit,
spaces, __LINE__);
1569 #ifdef WITH_NODE_COMPRESSION
1571 if (bits > MAX_COMP_BITS) bits = MAX_COMP_BITS;
1573 MPRINT3(
"%.*sFanout to comp %d at depth %d data %s\n", start_bit,
spaces, bits, start_bit, (
char *)
data);
1574 node = (
fr_trie_t *) fr_trie_comp_alloc(ctx, bits);
1584 MPRINT3(
"%.*sFanout to node %d at depth %d data %s\n", start_bit,
spaces, bits, start_bit, (
char *)
data);
1587 if (!node)
return -1;
1593 chunk =
get_chunk(&path->
key[0], start_bit2, node->bits);
1595 if (node->bits == path->bits) {
1626 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1646 chunk =
get_chunk(key, start_bit, node->bits);
1656 MPRINT3(
"%.*spath returning at %d\n", start_bit,
spaces, __LINE__);
1668 #ifdef WITH_NODE_COMPRESSION
1669 static CC_HINT(
nonnull(2,3,6)) int trie_comp_insert(TALLOC_CTX *ctx,
fr_trie_t **trie_p,
uint8_t const *key,
int start_bit,
int end_bit,
void *
data)
1673 fr_trie_comp_t *
comp = (fr_trie_comp_t *) trie;
1677 MPRINT3(
"%.*scomp insert start %d end %d with key %02x%02x data %s\n",
1678 start_bit,
spaces, start_bit, end_bit, key[0], key[1], (
char *)
data);
1680 if ((end_bit - start_bit) <
comp->bits) {
1691 for (i = 0; i <
comp->used; i++) {
1692 if (
comp->index[i] < chunk)
continue;
1697 if (
comp->index[i] == chunk) {
1698 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1700 MPRINT3(
"%.*scomp failed recursing at %d", start_bit,
spaces, __LINE__);
1706 MPRINT3(
"%.*scomp returning at %d", start_bit,
spaces, __LINE__);
1723 if (
comp->used < MAX_COMP_EDGES) {
1724 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1727 MPRINT3(
"%.*scomp failed recursing at %d", start_bit,
spaces, __LINE__);
1753 MPRINT3(
"%.*scomp swapping to node bits %d at %d\n", start_bit,
spaces, bits, __LINE__);
1756 if (!node)
return -1;
1758 for (i = 0; i <
comp->used; i++) {
1763 node->
used += (node->
trie[chunk] == NULL);
1769 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1771 MPRINT3(
"%.*scomp failed recursing at %d", start_bit,
spaces, __LINE__);
1778 MPRINT3(
"%.*scomp returning at %d", start_bit,
spaces, __LINE__);
1790 #ifdef WITH_PATH_COMPRESSION
1793 #ifdef WITH_NODE_COMPRESSION
1794 [ FR_TRIE_COMP ] = trie_comp_insert,
1822 if (!*trie_p)
return -1;
1826 MPRINT3(
"%.*sIN recurse at %d\n", start_bit,
spaces, __LINE__);
1834 if (start_bit == end_bit) {
1843 if (!user)
return -1;
1855 MPRINT3(
"%.*srecurse at start %d end %d with data %s\n", start_bit,
spaces, start_bit, end_bit, (
char *)
data);
1902 MPRINT2(
"No match for data, inserting...\n");
1904 MPRINT3(
"%.*srecurse STARTS at %d with %.*s=%s\n", 0,
spaces, __LINE__,
1905 (
int) keylen, key, my_data);
1912 typedef void *(*trie_key_remove_t)(TALLOC_CTX *ctx,
fr_trie_t **trie_p,
uint8_t const *key,
int start_bit,
int end_bit);
1924 if (start_bit == end_bit) {
1927 *trie_p = user->
trie;
1943 chunk =
get_chunk(key, start_bit, node->bits);
1944 if (!node->
trie[chunk])
return NULL;
1947 if (!
data)
return NULL;
1952 if (node->
trie[chunk])
return data;
1975 #ifdef WITH_PATH_COMPRESSION
1983 chunk =
get_chunk(key, start_bit, path->bits);
1988 if (path->
chunk != chunk)
return NULL;
1991 if (!
data)
return NULL;
2007 #ifdef WITH_NODE_COMPRESSION
2008 static void *trie_comp_remove(TALLOC_CTX *ctx,
fr_trie_t **trie_p,
uint8_t const *key,
int start_bit,
int end_bit)
2013 fr_trie_comp_t *
comp = *(fr_trie_comp_t **) trie_p;
2021 for (i = 0; i <
comp->used; i++) {
2022 if (
comp->index[i] < chunk)
continue;
2024 if (
comp->index[i] == chunk) {
2033 if (
comp->index[i] > chunk)
return NULL;
2039 if (i >=
comp->used)
return NULL;
2044 if (!
data)
return NULL;
2049 if (
comp->trie[i]) {
2061 for (j = i; j <
comp->used - 1; j++) {
2062 comp->index[j] =
comp->index[j + 1];
2067 if (
comp->used >= 2) {
2093 if (!path)
return data;
2117 #ifdef WITH_PATH_COMPRESSION
2120 #ifdef WITH_NODE_COMPRESSION
2121 [ FR_TRIE_COMP ] = trie_comp_remove,
2132 if (!trie)
return NULL;
2138 if ((start_bit + trie->bits) > end_bit)
return NULL;
2162 if (!ft->
trie)
return NULL;
2194 if (!user->
trie)
return 0;
2205 for (i = 0; i < (1 << node->bits); i++) {
2206 if (!node->
trie[i])
continue;
2212 more || (used < node->
used)) < 0) {
2220 #ifdef WITH_PATH_COMPRESSION
2232 #ifdef WITH_NODE_COMPRESSION
2236 fr_trie_comp_t *
comp = (fr_trie_comp_t *) trie;
2239 for (i = 0; i <
comp->used; i++) {
2246 more || (used < comp->
used)) < 0) {
2258 #ifdef WITH_PATH_COMPRESSION
2261 #ifdef WITH_NODE_COMPRESSION
2262 [ FR_TRIE_COMP ] = trie_comp_walk,
2288 #ifdef WITH_TRIE_VERIFY
2291 typedef int (*trie_verify_t)(
fr_trie_t *trie);
2293 static int trie_user_verify(
fr_trie_t *trie)
2302 if (!user->
trie)
return 0;
2304 return trie_verify(user->
trie);
2307 static int trie_node_verify(
fr_trie_t *trie)
2318 if ((node->
used == 0) || (node->
used > (1 << node->bits))) {
2320 node->
used, node->bits);
2325 for (i = 0; i < (1 << node->bits); i++) {
2326 if (!node->
trie[i])
continue;
2328 if (trie_verify(node->
trie[i]) < 0)
return -1;
2342 #ifdef WITH_PATH_COMPRESSION
2343 static int trie_path_verify(
fr_trie_t *trie)
2347 if ((path->bits == 0) || (path->bits > 16)) {
2358 return trie_verify(path->
trie);
2362 #ifdef WITH_NODE_COMPRESSION
2363 static int trie_comp_verify(
fr_trie_t *trie)
2366 fr_trie_comp_t *
comp = (fr_trie_comp_t *) trie;
2368 if ((
comp->bits == 0) || (
comp->bits > MAX_COMP_BITS)) {
2375 for (i = 0; i <
comp->used; i++) {
2376 if (!
comp->trie[i]) {
2381 if ((i + 1) <
comp->used) {
2382 if (
comp->index[i] >=
comp->index[i + 1]) {
2384 i,
comp->index[i],
comp->index[i + 1]);
2389 if (trie_verify(
comp->trie[i]) < 0)
return -1;
2403 static trie_verify_t trie_verify_table[
FR_TRIE_MAX] = {
2406 #ifdef WITH_PATH_COMPRESSION
2409 #ifdef WITH_NODE_COMPRESSION
2410 [ FR_TRIE_COMP ] = trie_comp_verify,
2420 if (!trie)
return 0;
2424 return trie_verify_table[trie->type](trie);
2434 static void trie_dump_edge(FILE *fp,
fr_trie_t *trie)
2438 fprintf(fp,
"NODE-%d\n", trie->number);
2443 typedef void (*fr_trie_dump_t)(FILE *fp,
fr_trie_t *trie,
char const *key,
int keylen);
2445 static void trie_user_dump(FILE *fp,
fr_trie_t *trie,
char const *key,
int keylen)
2448 int bytes =
BYTES(keylen);
2450 fprintf(fp,
"{ NODE-%d\n", user->number);
2451 fprintf(fp,
"\ttype\tUSER\n");
2452 fprintf(fp,
"\tinput\t{%d}%.*s\n", keylen, bytes, key);
2454 fprintf(fp,
"\tdata\t\"%s\"\n", (
char const *) user->
data);
2456 fprintf(fp,
"}\n\n");
2460 fprintf(fp,
"\tnext\t");
2461 trie_dump_edge(fp, user->
trie);
2462 fprintf(fp,
"}\n\n");
2465 static void trie_node_dump(FILE *fp,
fr_trie_t *trie,
char const *key,
int keylen)
2469 int bytes =
BYTES(keylen);
2471 fprintf(fp,
"{ NODE-%d\n", node->number);
2472 fprintf(fp,
"\ttype\tNODE\n");
2473 fprintf(fp,
"\tinput\t{%d}%.*s\n", keylen, bytes, key);
2475 fprintf(fp,
"\tbits\t%d\n", node->bits);
2476 fprintf(fp,
"\tused\t%d\n", node->
used);
2478 for (i = 0; i < (1 << node->bits); i++) {
2479 if (!node->
trie[i])
continue;
2481 fprintf(fp,
"\t%02x\t", (
int) i);
2482 trie_dump_edge(fp, node->
trie[i]);
2484 fprintf(fp,
"}\n\n");
2487 #ifdef WITH_PATH_COMPRESSION
2488 static void trie_path_dump(FILE *fp,
fr_trie_t *trie,
char const *key,
int keylen)
2491 int bytes =
BYTES(keylen);
2493 fprintf(fp,
"{ NODE-%d\n", path->number);
2494 fprintf(fp,
"\ttype\tPATH\n");
2495 fprintf(fp,
"\tinput\t{%d}%.*s\n", keylen, bytes, key);
2497 fprintf(fp,
"\tbits\t%d\n", (
int) path->bits);
2498 fprintf(fp,
"\tpath\t");
2500 fprintf(fp,
"%02x %02x", path->
key[0], path->
key[1]);
2504 fprintf(fp,
"\tnext\t");
2505 trie_dump_edge(fp, path->
trie);
2507 fprintf(fp,
"}\n\n");
2511 #ifdef WITH_NODE_COMPRESSION
2512 static void trie_comp_dump(FILE *fp,
fr_trie_t *trie,
char const *key,
int keylen)
2514 fr_trie_comp_t *
comp = (fr_trie_comp_t *) trie;
2516 int bytes =
BYTES(keylen);
2518 fprintf(fp,
"{ NODE-%d\n",
comp->number);
2519 fprintf(fp,
"\ttype\tCOMP\n");
2520 fprintf(fp,
"\tinput\t{%d}%.*s\n", keylen, bytes, key);
2522 fprintf(fp,
"\tbits\t%d\n",
comp->bits);
2523 fprintf(fp,
"\tused\t%d\n",
comp->used);
2525 for (i = 0; i <
comp->used; i++) {
2526 fprintf(fp,
"\t%d = %02x\t", i,
comp->index[i]);
2527 trie_dump_edge(fp,
comp->trie[i]);
2529 fprintf(fp,
"}\n\n");
2534 static fr_trie_dump_t trie_dump_table[
FR_TRIE_MAX] = {
2537 #ifdef WITH_PATH_COMPRESSION
2540 #ifdef WITH_NODE_COMPRESSION
2541 [ FR_TRIE_COMP ] = trie_comp_dump,
2553 if (!trie)
return 0;
2557 trie_dump_table[trie->type](fp, trie, (
char const *) cb->
start, keylen);
2574 bytes =
BYTES(keylen);
2577 if ((keylen & 0x07) != 0) {
2578 fprintf(fp,
"{%d}%.*s\t%s\n", keylen, bytes, cb->
start, (
char const *) user->
data);
2580 fprintf(fp,
"%.*s\t%s\n", bytes, cb->
start, (
char const *) user->
data);
2616 .user_callback = callback,
2651 keylen =
sizeof(uctx->
buffer) * 8;
2653 if (!uctx->
get_key)
return false;
2655 if (uctx->
get_key(&key, &keylen,
data) < 0)
return false;
2676 keylen =
sizeof(uctx->
buffer) * 8;
2678 if (!uctx->
get_key)
return false;
2680 if (uctx->
get_key(&key, &keylen,
data) < 0)
return false;
2701 keylen =
sizeof(uctx->
buffer) * 8;
2703 if (!uctx->
get_key)
return false;
2705 if (uctx->
get_key(&key, &keylen,
data) < 0)
return false;
2734 keylen =
sizeof(uctx->
buffer) * 8;
2736 if (!uctx->
get_key)
return -1;
2738 if (uctx->
get_key(&key, &keylen,
data) < 0)
return -1;
2742 if (old) *old = found;
2745 if (old) *old = NULL;
2753 return found ? 1 : 0;
2772 keylen =
sizeof(uctx->
buffer) * 8;
2774 if (!uctx->
get_key)
return NULL;
2776 if (uctx->
get_key(&key, &keylen,
data) < 0)
return NULL;
2798 keylen =
sizeof(uctx->
buffer) * 8;
2800 if (!uctx->
get_key)
return false;
2802 if (uctx->
get_key(&key, &keylen,
data) < 0)
return false;
2805 if (!found)
return false;
2823 static bool print_lineno =
false;
2829 } trie_sprint_ctx_t;
2837 trie_sprint_ctx_t *ctx;
2843 len =
snprintf(ctx->buffer, ctx->buflen,
"{}");
2849 bytes =
BYTES(keylen);
2852 if (!user->
trie && !more) {
2853 len =
snprintf(ctx->buffer, ctx->buflen,
"%.*s=%s",
2854 bytes, cb->
start, (
char const *) user->
data);
2856 len =
snprintf(ctx->buffer, ctx->buflen,
"%.*s=%s,",
2857 bytes, cb->
start, (
char const *) user->
data);
2871 trie_sprint_ctx_t my_sprint;
2879 memset(
out, 0,
sizeof(
out));
2887 my_sprint.start =
out;
2888 my_sprint.buffer =
out;
2889 my_sprint.buflen =
sizeof(
out);
2898 my_cb.
ctx = &my_sprint;
2916 static int arg2key(
char *arg,
char **key,
int *length)
2923 *length =
BITSOF(strlen(arg));
2927 p = strchr(arg,
'}');
2929 MPRINT(
"Failed to find end '}' for {bits}\n");
2933 bits =
BITSOF(strlen(p + 1));
2935 MPRINT(
"No key found in in '%s'\n", arg);
2939 size = atoi(arg + 1);
2941 MPRINT(
"Length '%d' is longer than bits in key %s",
2956 static void *data_ctx = NULL;
2967 if (arg2key(argv[0], &key, &bits) < 0) {
2975 data = talloc_strdup(data_ctx, argv[1]);
3003 fprintf(stderr,
"Verify failed: trie is malformed\n");
3007 if (trie_verify(ft->
trie) < 0) {
3008 fprintf(stderr,
"Verify failed: %s\n",
fr_strerror());
3069 if (!ft->
trie)
return 0;
3090 if (strcmp(argv[0],
"true") == 0) {
3091 print_lineno =
true;
3093 print_lineno =
false;
3114 if (arg2key(argv[0], &key, &bits) < 0) {
3134 static int command_lookup(
fr_trie_t *ft,
UNUSED int argc,
char **argv,
char *
out,
size_t outlen)
3140 if (arg2key(argv[0], &key, &bits) < 0) {
3160 static int command_remove(
fr_trie_t *ft,
UNUSED int argc,
char **argv,
char *
out,
size_t outlen)
3166 if (arg2key(argv[0], &key, &bits) < 0) {
3172 MPRINT(
"Could not remove key %s\n", key);
3186 MPRINT(
"Still in trie after 'remove' for key %s, found data %s\n", key, (
char const *) answer);
3198 static int command_try_to_remove(
fr_trie_t *ft,
UNUSED int argc,
char **argv,
char *
out,
size_t outlen)
3204 if (arg2key(argv[0], &key, &bits) < 0) {
3224 MPRINT(
"Still in trie after 'remove' for key %s, found data %s\n", key, (
char const *) answer);
3241 trie_sprint_ctx_t my_sprint;
3247 my_sprint.start =
out;
3248 my_sprint.buffer =
out;
3249 my_sprint.buflen = outlen;
3258 my_cb.
ctx = &my_sprint;
3274 static int command_path(
fr_trie_t *ft,
int argc,
char **argv,
char *
out,
size_t outlen)
3279 data = talloc_strdup(ft, argv[1]);
3292 MPRINT(
"Could not look up key %s\n", argv[0]);
3296 if (answer !=
data) {
3297 MPRINT(
"Expected to find %s, got %s\n", argv[1], (
char const *) answer);
3308 MPRINT(
"Could not remove key %s\n", argv[0]);
3312 if (answer !=
data) {
3313 MPRINT(
"Expected to remove %s, got %s\n", argv[1], (
char const *) answer);
3326 static int command_lcp(
UNUSED fr_trie_t *ft,
int argc,
char **argv,
char *
out,
size_t outlen)
3329 int keylen1, keylen2;
3334 key1 = (
uint8_t const *) argv[0];
3335 keylen1 =
BITSOF(strlen(argv[0]));
3337 key2 = (
uint8_t const *) argv[1];
3338 keylen2 =
BITSOF(strlen(argv[1]));
3341 }
else if (argc == 5) {
3342 key1 = (
uint8_t const *) argv[0];
3343 keylen1 = atoi(argv[1]);
3344 if ((keylen1 < 0) || (keylen1 > (
int)
BITSOF(strlen(argv[0])))) {
3345 MPRINT(
"length of key1 %s is larger than string length %ld\n",
3346 argv[1],
BITSOF(strlen(argv[0])));
3350 key2 = (
uint8_t const *) argv[2];
3351 keylen2 = atoi(argv[3]);
3352 if ((keylen2 < 0) || (keylen2 > (
int)
BITSOF(strlen(argv[2])))) {
3353 MPRINT(
"length of key2 %s is larger than string length %ld\n",
3354 argv[3],
BITSOF(strlen(argv[2])));
3358 start_bit = atoi(argv[4]);
3359 if ((start_bit < 0) || (start_bit > 7)) {
3360 MPRINT(
"start_bit has invalid value %s\n", argv[4]);
3365 MPRINT(
"Invalid number of arguments\n");
3380 int start_bit, num_bits;
3383 start_bit = atoi(argv[1]);
3384 num_bits = atoi(argv[2]);
3395 typedef int (*fr_trie_function_t)(
fr_trie_t *ft,
int argc,
char **argv,
char *
out,
size_t outlen);
3402 fr_trie_function_t
function;
3406 } fr_trie_command_t;
3412 static fr_trie_command_t
commands[] = {
3413 {
"lcp", command_lcp, 2, 5,
true },
3414 {
"chunk", command_chunk, 3, 3,
true },
3415 {
"path", command_path, 2, 2,
true },
3416 {
"insert", command_insert, 2, 2,
false },
3418 {
"lookup", command_lookup, 1, 1,
true },
3419 {
"remove", command_remove, 1, 1,
true },
3420 {
"-remove", command_try_to_remove, 1, 1,
true },
3422 {
"dump", command_dump, 0, 0,
false },
3423 {
"keys", command_keys, 0, 0,
false },
3424 {
"verify", command_verify, 0, 0,
false },
3425 {
"lineno", command_lineno, 1, 1,
false },
3430 #define MAX_ARGC (16)
3431 int main(
int argc,
char **argv)
3438 char *my_argv[MAX_ARGC];
3443 fprintf(stderr,
"Please specify filename\n");
3447 fp = fopen(argv[1],
"r");
3449 fprintf(stderr,
"Failed opening %s: %s\n", argv[1],
fr_syserror(errno));
3456 talloc_enable_null_tracking();
3462 fprintf(stderr,
"Failed creating trie\n");
3475 for (p =
buffer; *p !=
'\0'; p++) {
3497 if (strcmp(my_argv[0],
commands[i].
name) != 0)
continue;
3504 fprintf(stderr,
"Unknown command '%s' at line %d\n",
3505 my_argv[0], lineno);
3516 fprintf(stderr,
"Invalid number of arguments to %s at line %d. Expected %d, got %d\n",
3517 my_argv[0], lineno,
commands[cmd].min_argc + 1, my_argc - 1);
3522 printf(
"%d ", lineno);
3526 MPRINT3(
"[%d] %s\n", lineno, my_argv[0]);
3527 if (
commands[cmd].
function(ft, my_argc - 1 -
commands[cmd].output, &my_argv[1], output,
sizeof(output)) < 0) {
3528 fprintf(stderr,
"Failed running %s at line %d\n",
3529 my_argv[0], lineno);
3533 if (!
commands[cmd].output)
continue;
3535 if (strcmp(output, my_argv[my_argc - 1]) != 0) {
3536 fprintf(stderr,
"Failed running %s at line %d: Expected '%s' got '%s'\n",
3537 my_argv[0], lineno, my_argv[my_argc - 1], output);
3547 talloc_report_full(NULL, stdout);
3548 talloc_disable_null_tracking();
static int const char char buffer[256]
#define UNCONST(_type, _ptr)
Remove const qualification from a pointer.
static int split(char **input, char **output, bool syntax_string)
#define fr_cond_assert(_x)
Calls panic_action ifndef NDEBUG, else logs error and evaluates to value of _x.
#define fr_exit_now(_x)
Exit without calling atexit() handlers, producing a log message in debug builds.
static char const * spaces
int main(int argc, char **argv)
int fr_dict_str_to_argv(char *str, char **argv, int max_argc)
static uint8_t depth(fr_minmax_heap_index_t i)
#define fr_skip_whitespace(_p)
Skip whitespace ('\t', '\n', '\v', '\f', '\r', ' ')
void(* fr_free_t)(void *)
static int8_t comp(void const *a, void const *b)
static void xor(char *out, char *in1, char *in2, int n)
PUBLIC int snprintf(char *string, size_t length, char *format, va_alist)
size_t strlcpy(char *dst, char const *src, size_t siz)
char const * fr_syserror(int num)
Guaranteed to be thread-safe version of strerror.
static TALLOC_CTX * talloc_init_const(char const *name)
Allocate a top level chunk with a constant name.
int(* fr_trie_key_walk_t)(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
fr_trie_t * fr_trie_alloc(TALLOC_CTX *ctx, fr_trie_key_t get_key, fr_free_t free_data)
Allocate a trie.
#define MPRINT(...)
Internal sanity checks for debugging.
static trie_key_match_t trie_match_table[FR_TRIE_MAX]
static void * trie_user_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
bool fr_trie_delete(fr_trie_t *ft, void const *data)
Remove node and free data (if a free function was specified)
#define trie_check(_trie, _key, _start_bit, _end_bit, _data, _lineno)
static trie_key_remove_t trie_remove_table[FR_TRIE_MAX]
bool fr_trie_insert(fr_trie_t *ft, void const *data)
Insert data into a trie.
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.
unsigned int fr_trie_num_elements(UNUSED fr_trie_t *ft)
Return how many nodes there are in a trie.
static fr_trie_key_walk_t trie_walk_table[FR_TRIE_MAX]
void * fr_trie_find(fr_trie_t *ft, void const *data)
Find an element in the trie, returning the data.
static fr_trie_node_t * trie_node_alloc(TALLOC_CTX *ctx, int bits)
static fr_trie_path_t * fr_trie_path_alloc(TALLOC_CTX *ctx, uint8_t const *key, int start_bit, int end_bit)
void *(* trie_key_match_t)(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
static void * trie_node_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
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.
static int trie_key_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
static fr_trie_t * trie_key_alloc(TALLOC_CTX *ctx, uint8_t const *key, int start_bit, int end_bit, void *data)
void * fr_trie_remove(fr_trie_t *ft, void const *data)
Remove an entry, without freeing the data.
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.
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.
static fr_trie_user_t * fr_trie_user_alloc(TALLOC_CTX *ctx, void const *data)
int fr_trie_walk(fr_trie_t *ft, void *ctx, fr_trie_walk_t callback)
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.
fr_trie_walk_t user_callback
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.
static uint8_t xor2lcp[256]
void *(* trie_key_remove_t)(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
static void * trie_path_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
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)
void * fr_trie_match(fr_trie_t *ft, void const *data)
Match an element exactly in the trie, returning the data.
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)
fr_trie_key_walk_t callback
#define trie_sprint(_trie, _key, _start_bit, _lineno)
static trie_key_insert_t trie_insert_table[FR_TRIE_MAX]
static int trie_node_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
static uint16_t get_chunk(uint8_t const *key, int start_bit, int num_bits)
Return a chunk of a key (in the low bits) for use in 2^N node de-indexing.
#define TRIE_TYPE_CHECK(_x, _r)
static void write_chunk(uint8_t *out, int start_bit, int num_bits, uint16_t chunk)
Write a chunk to an output buffer.
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.
static int trie_user_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
static fr_trie_node_t * trie_node_split(TALLOC_CTX *ctx, fr_trie_node_t *node, int bits)
Split a node at bits.
static int trie_add_edge(fr_trie_t *trie, uint16_t chunk, fr_trie_t *child)
Add an edge to a node.
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.
static fr_trie_path_t * trie_path_split(TALLOC_CTX *ctx, fr_trie_path_t *path, int start_bit, int lcp)
static void * trie_path_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
static void * trie_user_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
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.
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.
static int trie_path_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
static uint8_t start_bit_mask[8]
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)
static uint8_t used_bit_mask[8]
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)
static void * trie_node_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
static void trie_free(fr_trie_t *trie)
Free a fr_trie_t.
int(* fr_trie_key_t)(uint8_t **out, size_t *outlen, void const *data)
int(* fr_trie_walk_t)(uint8_t const *key, size_t keylen, void *data, void *uctx)
Walk over a trie.
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.
#define fr_strerror_printf(_fmt,...)
Log to thread local error buffer.
#define fr_strerror_const(_msg)
static size_t char ** out