23RCSID(
"$Id: c8fe1cef472fddb6b5bb3e4e5f08f9765c22cd43 $")
25#include <freeradius-devel/util/dict.h>
26#include <freeradius-devel/util/syserror.h>
27#include <freeradius-devel/util/trie.h>
72#if !defined(NO_PATH_COMPRESSION) && !defined(WITH_PATH_COMPRESSION)
73#define WITH_PATH_COMPRESSION
78#ifdef WITH_NODE_COMPRESSION
79#ifndef WITH_PATH_COMPRESSION
80#define WITH_PATH_COMPRESSION
84#define MAX_COMP_BITS (8)
88#define MAX_COMP_EDGES (4)
93#define MAX_KEY_BYTES (256)
94#define MAX_KEY_BITS (MAX_KEY_BYTES * 8)
97#define MAX_NODE_BITS (4)
110#define WITH_TRIE_VERIFY (1)
111# define MPRINT(...) fprintf(stderr, ## __VA_ARGS__)
121#define trie_sprint(_trie, _key, _start_bit, _lineno)
124#ifdef WITH_TRIE_VERIFY
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)
135#define BITSOF(_x) ((_x) * 8)
136#define BYTEOF(_x) ((_x) >> 3)
137#define BYTES(_x) (((_x) + 0x07) >> 3)
150 0xff, 0x7f, 0x3f, 0x1f,
151 0x0f, 0x07, 0x03, 0x01
155 0x80, 0xc0, 0xe0, 0xf0,
156 0xf8, 0xfc, 0xfe, 0xff,
163static char const *
spaces =
" ";
167#if defined(WITH_PATH_COMPRESSION) || defined(TESTING)
230 if (!keylen1 || !keylen2)
return 0;
234 if (end_bit > keylen2) end_bit = keylen2;
235 end_bit += start_bit;
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);
242 while (end_bit > 0) {
270 if ((start_bit & 0x07) != 0) {
273 num_bits -= start_bit;
274 end_bit -= start_bit;
320static void hex_dump(FILE *fp,
char const *
msg,
uint8_t const *key,
int start_bit,
int end_bit)
324 fprintf(fp,
"%s\ts=%zd e=%zd\t\t",
msg, start_bit, end_bit);
326 for (i = 0; i <
BYTES(end_bit); i++) {
327 fprintf(fp,
"%02x ", key[i]);
356 chunk = key[0] >> (7 - start_bit);
364 if (start_bit == 0) {
365 if (num_bits < 7)
return key[0] >> (8 - num_bits);
366 if (num_bits == 8)
return key[0];
368 chunk = (key[0] << 8) | key[1];
369 if (num_bits < 16) chunk >>= (16 - num_bits);
382 if (
BYTEOF(start_bit + num_bits - 1) != 0) {
394 end_bit = (start_bit + num_bits) & 0x07;
395 if (end_bit != 0) chunk >>= 8 - end_bit;
424 out[0] &= ~((1 << (7 - start_bit)) - 1);
425 out[0] |= chunk << (7 - start_bit);
439 if ((start_bit + num_bits) < 16) chunk <<= (16 - (start_bit + num_bits));
446 out[0] |= chunk >> 8;
448 if ((start_bit + num_bits) > 8) {
449 out[1] = chunk & 0xff;
456#ifdef WITH_PATH_COMPRESSION
459#ifdef WITH_NODE_COMPRESSION
465#define FR_TRIE_MAX (FR_TRIE_NODE + 1)
468static int trie_number = 0;
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); \
479#define TRIE_HEADER uint8_t type; uint8_t bits
480#define TRIE_TYPE_CHECK(_x, _r)
503#ifdef WITH_PATH_COMPRESSION
514#ifdef WITH_NODE_COMPRESSION
532 if ((bits <= 0) || (bits > 8)) {
545 talloc_set_name_const(node,
"fr_trie_node_t");
550 node->number = trie_number++;
577 for (i = 0; i < (1 << node->bits); i++) {
578 if (!node->
trie[i])
continue;
587#ifdef WITH_PATH_COMPRESSION
597#ifdef WITH_NODE_COMPRESSION
598 if (trie->type == FR_TRIE_COMP) {
599 fr_trie_comp_t *
comp = (fr_trie_comp_t *) trie;
602 for (i = 0; i <
comp->used; i++) {
626 user->number = trie_number++;
632#ifdef WITH_PATH_COMPRESSION
637 if (end_bit <= start_bit) {
646 key += (start_bit >> 3);
647 end_bit -= 8 * (start_bit >> 3);
648 start_bit -= 8 * (start_bit >> 3);
651 if ((end_bit - start_bit) > 16) {
672 path->bits = end_bit - start_bit;
681 fprintf(stderr,
"PATH ALLOC key %02x%02x start %d end %d bits %d == chunk %04x key %02x%02x\n",
683 start_bit, end_bit, path->bits,
688 path->number = trie_number++;
695#ifdef WITH_NODE_COMPRESSION
696static fr_trie_comp_t *fr_trie_comp_alloc(TALLOC_CTX *ctx,
int bits)
698 fr_trie_comp_t *
comp;
703 if ((bits <= 2) || (bits > MAX_COMP_BITS)) {
708 comp = talloc_zero(ctx, fr_trie_comp_t);
714 comp->type = FR_TRIE_COMP;
719 comp->number = trie_number++;
750 if (!user)
return NULL;
775 int i, remaining_bits;
781 if ((bits == 0) || (bits >= node->bits) || (node->bits == 1)) {
787 if (!
split)
return NULL;
789 remaining_bits = node->bits - bits;
795 for (i = 0; i < (1 << bits); i++) {
805 for (j = 0; j < (1 << remaining_bits); j++) {
806 if (!node->trie[(i << remaining_bits) + j])
continue;
808 child->
trie[j] = node->
trie[(i << remaining_bits) + j];
809 node->
trie[(i << remaining_bits) + j] = NULL;
829#ifdef WITH_PATH_COMPRESSION
837 if ((lcp <= 0) || (lcp > path->bits) || (start_bit < 0)) {
842 MPRINT3(
"%.*sSPLIT start %d\n", start_bit,
spaces, start_bit);
846 if (!
split)
return NULL;
848 child =
fr_trie_path_alloc(ctx, &path->key[0], start_bit + lcp, start_bit + path->bits);
849 if (!child)
return NULL;
875 MPRINT3(
"%.*ssplit %02x%02x start %d split %d -> %02x%02x %02x%02x\n",
877 path->key[0], path->key[1],
878 start_bit,
split->bits,
880 child->
key[0], child->
key[1]);
893 if (start_bit > end_bit) {
901 next_bit = start_bit + 16 - (start_bit & 0x07);
903 if (next_bit >= end_bit) {
905 if (!path)
return NULL;
913 if (!path)
return NULL;
930 if (start_bit == end_bit) {
934 bits = end_bit - start_bit;
941 if (!node)
return NULL;
943 chunk =
get_chunk(key, start_bit, node->bits);
945 if (!node->
trie[chunk]) {
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)
964 fr_trie_comp_t *
split;
970 if ((bits == 0) || (bits >=
comp->bits)) {
975 split = fr_trie_comp_alloc(ctx, bits);
976 if (!
split)
return NULL;
978 if (start_bit > 7) start_bit &= 0x07;
989 for (i = 0; i <
comp->used; i++) {
995 before = i >> (
comp->bits - bits);
996 after = i & ((1 << bits) - 1);
1004 for (j = 0; j <
split->used; j++) {
1005 if (before ==
split->index[j]) {
1011 if (
split->index[where]) {
1018 if (!path)
goto fail;
1028 for (i = 0; i <
split->used; i++) {
1039#ifdef WITH_PATH_COMPRESSION
1049#ifdef WITH_NODE_COMPRESSION
1050 if (trie->type == FR_TRIE_COMP) {
1051 fr_trie_comp_t *
comp = (fr_trie_comp_t *) trie;
1054 if (chunk >= (1 <<
comp->bits))
return -1;
1056 if (
comp->used >= MAX_COMP_EDGES)
return -1;
1059 for (i = 0; i <
comp->used; i++) {
1060 if (
comp->index[i] < chunk)
continue;
1062 if (
comp->index[edge] == chunk)
return -1;
1068 if (edge == MAX_COMP_EDGES)
return -1;
1074 for (i = edge; i <
comp->used; i++) {
1075 comp->index[i + 1] =
comp->index[i];
1079 comp->index[edge] = chunk;
1092 if (chunk >= (1 << node->bits))
return -1;
1094 if (node->
trie[chunk] != NULL)
return -1;
1097 node->
trie[chunk] = child;
1105typedef void *(*trie_key_match_t)(
fr_trie_t *trie,
uint8_t const *key,
int start_bit,
int end_bit,
bool exact);
1118 if (start_bit == end_bit)
return user->
data;
1134 MPRINT2(
"no exact match at %d\n", __LINE__);
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__);
1155 return trie_key_match(node->
trie[chunk], key, start_bit + node->bits, end_bit, exact);
1158#ifdef WITH_PATH_COMPRESSION
1164 chunk =
get_chunk(key, start_bit, path->bits);
1165 if (chunk != path->
chunk)
return NULL;
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)
1176 fr_trie_comp_t *
comp = (fr_trie_comp_t *) trie;
1180 for (i = 0; i <
comp->used; i++) {
1181 if (
comp->index[i] < chunk)
continue;
1183 if (
comp->index[i] == chunk) {
1202#ifdef WITH_PATH_COMPRESSION
1205#ifdef WITH_NODE_COMPRESSION
1206 [ FR_TRIE_COMP ] = trie_comp_match,
1227 if (!trie)
return NULL;
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);
1236 MPRINT2(
"no match for key too short for trie NODE-%d at %d\n", trie->number, __LINE__);
1267 if (!ft->
trie)
return NULL;
1291 if (!ft->
trie)
return NULL;
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);
1317 if (answer !=
data) {
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);
1326#define trie_check(_trie, _key, _start_bit, _end_bit, _data, _lineno)
1338 MPRINT3(
"user insert to start %d end %d with data %s\n", start_bit, end_bit, (
char *)
data);
1343 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1354 MPRINT3(
"%.*snode insert end %d with data %s\n",
1363 if ((start_bit + node->bits) > end_bit) {
1366 MPRINT3(
"%.*snode insert splitting %d at %d start %d end %d with data %s\n",
1368 node->bits, start_bit - end_bit,
1369 start_bit, end_bit, (
char *)
data);
1381 chunk =
get_chunk(key, start_bit, node->bits);
1387 if (!node->
trie[chunk]) {
1389 if (!node->
trie[chunk]) {
1391 if (trie_to_free)
trie_free(trie_to_free);
1401 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1403 MPRINT(
"Failed recursing at %d\n", __LINE__);
1404 if (trie_to_free)
trie_free(trie_to_free);
1411 MPRINT3(
"%.*snode insert returning at %d\n",
1412 start_bit,
spaces, __LINE__);
1414 if (trie_to_free)
trie_free(trie_to_free);
1420#ifdef WITH_PATH_COMPRESSION
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);
1441 if (start_bit + path->bits <= end_bit) {
1442 chunk =
get_chunk(key, start_bit, path->bits);
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__);
1458 MPRINT3(
"%.*spath returning at %d\n", start_bit,
spaces, __LINE__);
1464 MPRINT3(
"%.*spath using %d\n", start_bit,
spaces, path->bits);
1471 bits = end_bit - start_bit;
1472 MPRINT3(
"%.*spath limiting %d to %d\n", start_bit,
spaces, path->bits, bits);
1480 start_bit2 = start_bit;
1481 if (start_bit2 > 7) {
1482 key2 += (start_bit2 >> 3);
1483 start_bit2 -= 8 * (start_bit2 >> 3);
1498 if (lcp == path->bits) {
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);
1514 MPRINT3(
"%.*spath key %02x%02x input key %02x%02x, offset %d\n",
1516 path->
key[0],path->
key[1],
1535 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1551 MPRINT3(
"%.*spath returning at %d\n", start_bit,
spaces, __LINE__);
1566#ifdef WITH_NODE_COMPRESSION
1568 if (bits > MAX_COMP_BITS) bits = MAX_COMP_BITS;
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);
1581 MPRINT3(
"%.*sFanout to node %d at depth %d data %s\n", start_bit,
spaces, bits, start_bit, (
char *)
data);
1584 if (!node)
return -1;
1590 chunk =
get_chunk(&path->
key[0], start_bit2, node->bits);
1592 if (node->bits == path->bits) {
1623 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1643 chunk =
get_chunk(key, start_bit, node->bits);
1653 MPRINT3(
"%.*spath returning at %d\n", start_bit,
spaces, __LINE__);
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)
1670 fr_trie_comp_t *
comp = (fr_trie_comp_t *) trie;
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);
1677 if ((end_bit - start_bit) <
comp->bits) {
1688 for (i = 0; i <
comp->used; i++) {
1689 if (
comp->index[i] < chunk)
continue;
1694 if (
comp->index[i] == chunk) {
1695 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1697 MPRINT3(
"%.*scomp failed recursing at %d", start_bit,
spaces, __LINE__);
1703 MPRINT3(
"%.*scomp returning at %d", start_bit,
spaces, __LINE__);
1720 if (
comp->used < MAX_COMP_EDGES) {
1721 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1724 MPRINT3(
"%.*scomp failed recursing at %d", start_bit,
spaces, __LINE__);
1750 MPRINT3(
"%.*scomp swapping to node bits %d at %d\n", start_bit,
spaces, bits, __LINE__);
1753 if (!node)
return -1;
1755 for (i = 0; i <
comp->used; i++) {
1760 node->
used += (node->
trie[chunk] == NULL);
1766 MPRINT3(
"%.*srecurse at %d\n", start_bit,
spaces, __LINE__);
1768 MPRINT3(
"%.*scomp failed recursing at %d", start_bit,
spaces, __LINE__);
1775 MPRINT3(
"%.*scomp returning at %d", start_bit,
spaces, __LINE__);
1787#ifdef WITH_PATH_COMPRESSION
1790#ifdef WITH_NODE_COMPRESSION
1791 [ FR_TRIE_COMP ] = trie_comp_insert,
1819 if (!*trie_p)
return -1;
1823 MPRINT3(
"%.*sIN recurse at %d\n", start_bit,
spaces, __LINE__);
1831 if (start_bit == end_bit) {
1840 if (!user)
return -1;
1852 MPRINT3(
"%.*srecurse at start %d end %d with data %s\n", start_bit,
spaces, start_bit, end_bit, (
char *)
data);
1899 MPRINT2(
"No match for data, inserting...\n");
1901 MPRINT3(
"%.*srecurse STARTS at %d with %.*s=%s\n", 0,
spaces, __LINE__,
1902 (
int) keylen, key, my_data);
1909typedef void *(*trie_key_remove_t)(TALLOC_CTX *ctx,
fr_trie_t **trie_p,
uint8_t const *key,
int start_bit,
int end_bit);
1921 if (start_bit == end_bit) {
1924 *trie_p = user->
trie;
1940 chunk =
get_chunk(key, start_bit, node->bits);
1941 if (!node->
trie[chunk])
return NULL;
1944 if (!
data)
return NULL;
1949 if (node->
trie[chunk])
return data;
1972#ifdef WITH_PATH_COMPRESSION
1980 chunk =
get_chunk(key, start_bit, path->bits);
1985 if (path->
chunk != chunk)
return NULL;
1988 if (!
data)
return NULL;
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)
2010 fr_trie_comp_t *
comp = *(fr_trie_comp_t **) trie_p;
2018 for (i = 0; i <
comp->used; i++) {
2019 if (
comp->index[i] < chunk)
continue;
2021 if (
comp->index[i] == chunk) {
2030 if (
comp->index[i] > chunk)
return NULL;
2036 if (i >=
comp->used)
return NULL;
2041 if (!
data)
return NULL;
2046 if (
comp->trie[i]) {
2058 for (j = i; j <
comp->used - 1; j++) {
2059 comp->index[j] =
comp->index[j + 1];
2064 if (
comp->used >= 2) {
2090 if (!path)
return data;
2114#ifdef WITH_PATH_COMPRESSION
2117#ifdef WITH_NODE_COMPRESSION
2118 [ FR_TRIE_COMP ] = trie_comp_remove,
2129 if (!trie)
return NULL;
2135 if ((start_bit + trie->bits) > end_bit)
return NULL;
2159 if (!ft->
trie)
return NULL;
2191 if (!user->
trie)
return 0;
2202 for (i = 0; i < (1 << node->bits); i++) {
2203 if (!node->
trie[i])
continue;
2209 more || (used < node->
used)) < 0) {
2217#ifdef WITH_PATH_COMPRESSION
2229#ifdef WITH_NODE_COMPRESSION
2233 fr_trie_comp_t *
comp = (fr_trie_comp_t *) trie;
2236 for (i = 0; i <
comp->used; i++) {
2243 more || (used < comp->
used)) < 0) {
2255#ifdef WITH_PATH_COMPRESSION
2258#ifdef WITH_NODE_COMPRESSION
2259 [ FR_TRIE_COMP ] = trie_comp_walk,
2285#ifdef WITH_TRIE_VERIFY
2288typedef int (*trie_verify_t)(
fr_trie_t *trie);
2290static int trie_user_verify(
fr_trie_t *trie)
2299 if (!user->
trie)
return 0;
2301 return trie_verify(user->
trie);
2304static int trie_node_verify(
fr_trie_t *trie)
2315 if ((node->
used == 0) || (node->
used > (1 << node->bits))) {
2317 node->
used, node->bits);
2322 for (i = 0; i < (1 << node->bits); i++) {
2323 if (!node->
trie[i])
continue;
2325 if (trie_verify(node->
trie[i]) < 0)
return -1;
2339#ifdef WITH_PATH_COMPRESSION
2340static int trie_path_verify(
fr_trie_t *trie)
2344 if ((path->bits == 0) || (path->bits > 16)) {
2355 return trie_verify(path->
trie);
2359#ifdef WITH_NODE_COMPRESSION
2360static int trie_comp_verify(
fr_trie_t *trie)
2363 fr_trie_comp_t *
comp = (fr_trie_comp_t *) trie;
2365 if ((
comp->bits == 0) || (
comp->bits > MAX_COMP_BITS)) {
2372 for (i = 0; i <
comp->used; i++) {
2373 if (!
comp->trie[i]) {
2378 if ((i + 1) <
comp->used) {
2379 if (
comp->index[i] >=
comp->index[i + 1]) {
2381 i,
comp->index[i],
comp->index[i + 1]);
2386 if (trie_verify(
comp->trie[i]) < 0)
return -1;
2400static trie_verify_t trie_verify_table[
FR_TRIE_MAX] = {
2403#ifdef WITH_PATH_COMPRESSION
2406#ifdef WITH_NODE_COMPRESSION
2407 [ FR_TRIE_COMP ] = trie_comp_verify,
2417 if (!trie)
return 0;
2421 return trie_verify_table[trie->type](trie);
2431static void trie_dump_edge(FILE *fp,
fr_trie_t *trie)
2435 fprintf(fp,
"NODE-%d\n", trie->number);
2440typedef void (*fr_trie_dump_t)(FILE *fp,
fr_trie_t *trie,
char const *key,
int keylen);
2442static void trie_user_dump(FILE *fp,
fr_trie_t *trie,
char const *key,
int keylen)
2445 int bytes =
BYTES(keylen);
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);
2451 fprintf(fp,
"\tdata\t\"%s\"\n", (
char const *) user->
data);
2453 fprintf(fp,
"}\n\n");
2457 fprintf(fp,
"\tnext\t");
2458 trie_dump_edge(fp, user->
trie);
2459 fprintf(fp,
"}\n\n");
2462static void trie_node_dump(FILE *fp,
fr_trie_t *trie,
char const *key,
int keylen)
2466 int bytes =
BYTES(keylen);
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);
2472 fprintf(fp,
"\tbits\t%d\n", node->bits);
2473 fprintf(fp,
"\tused\t%d\n", node->
used);
2475 for (i = 0; i < (1 << node->bits); i++) {
2476 if (!node->
trie[i])
continue;
2478 fprintf(fp,
"\t%02x\t", (
int) i);
2479 trie_dump_edge(fp, node->
trie[i]);
2481 fprintf(fp,
"}\n\n");
2484#ifdef WITH_PATH_COMPRESSION
2485static void trie_path_dump(FILE *fp,
fr_trie_t *trie,
char const *key,
int keylen)
2488 int bytes =
BYTES(keylen);
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);
2494 fprintf(fp,
"\tbits\t%d\n", (
int) path->bits);
2495 fprintf(fp,
"\tpath\t");
2497 fprintf(fp,
"%02x %02x", path->
key[0], path->
key[1]);
2501 fprintf(fp,
"\tnext\t");
2502 trie_dump_edge(fp, path->
trie);
2504 fprintf(fp,
"}\n\n");
2508#ifdef WITH_NODE_COMPRESSION
2509static void trie_comp_dump(FILE *fp,
fr_trie_t *trie,
char const *key,
int keylen)
2511 fr_trie_comp_t *
comp = (fr_trie_comp_t *) trie;
2513 int bytes =
BYTES(keylen);
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);
2519 fprintf(fp,
"\tbits\t%d\n",
comp->bits);
2520 fprintf(fp,
"\tused\t%d\n",
comp->used);
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]);
2526 fprintf(fp,
"}\n\n");
2531static fr_trie_dump_t trie_dump_table[
FR_TRIE_MAX] = {
2534#ifdef WITH_PATH_COMPRESSION
2537#ifdef WITH_NODE_COMPRESSION
2538 [ FR_TRIE_COMP ] = trie_comp_dump,
2550 if (!trie)
return 0;
2554 trie_dump_table[trie->type](fp, trie, (
char const *) cb->
start, keylen);
2571 bytes =
BYTES(keylen);
2574 if ((keylen & 0x07) != 0) {
2575 fprintf(fp,
"{%d}%.*s\t%s\n", keylen, bytes, cb->
start, (
char const *) user->
data);
2577 fprintf(fp,
"%.*s\t%s\n", bytes, cb->
start, (
char const *) user->
data);
2613 .user_callback = callback,
2649 keylen =
sizeof(uctx->
buffer) * 8;
2651 if (!uctx->
get_key)
return false;
2653 if (uctx->
get_key(&key, &keylen,
data) < 0)
return false;
2675 keylen =
sizeof(uctx->
buffer) * 8;
2677 if (!uctx->
get_key)
return false;
2679 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;
2735 keylen =
sizeof(uctx->
buffer) * 8;
2737 if (!uctx->
get_key)
return -1;
2739 if (uctx->
get_key(&key, &keylen,
data) < 0)
return -1;
2743 if (old) *old = found;
2746 if (old) *old = NULL;
2754 return found ? 1 : 0;
2774 keylen =
sizeof(uctx->
buffer) * 8;
2776 if (!uctx->
get_key)
return NULL;
2778 if (uctx->
get_key(&key, &keylen,
data) < 0)
return NULL;
2801 keylen =
sizeof(uctx->
buffer) * 8;
2803 if (!uctx->
get_key)
return false;
2805 if (uctx->
get_key(&key, &keylen,
data) < 0)
return false;
2808 if (!found)
return false;
2827static bool print_lineno =
false;
2841 trie_sprint_ctx_t *ctx;
2847 len =
snprintf(ctx->buffer, ctx->buflen,
"{}");
2853 bytes =
BYTES(keylen);
2856 if (!user->
trie && !more) {
2857 len =
snprintf(ctx->buffer, ctx->buflen,
"%.*s=%s",
2858 bytes, cb->
start, (
char const *) user->
data);
2860 len =
snprintf(ctx->buffer, ctx->buflen,
"%.*s=%s,",
2861 bytes, cb->
start, (
char const *) user->
data);
2875 trie_sprint_ctx_t my_sprint;
2883 memset(
out, 0,
sizeof(
out));
2891 my_sprint.start =
out;
2892 my_sprint.buffer =
out;
2893 my_sprint.buflen =
sizeof(
out);
2902 my_cb.
ctx = &my_sprint;
2920static int arg2key(
char *arg,
char **key,
int *length)
2927 *length =
BITSOF(strlen(arg));
2931 p = strchr(arg,
'}');
2933 MPRINT(
"Failed to find end '}' for {bits}\n");
2937 bits =
BITSOF(strlen(p + 1));
2939 MPRINT(
"No key found in in '%s'\n", arg);
2943 size = atoi(arg + 1);
2945 MPRINT(
"Length '%d' is longer than bits in key %s",
2960static void *data_ctx = NULL;
2971 if (arg2key(argv[0], &key, &bits) < 0) {
2979 data = talloc_strdup(data_ctx, argv[1]);
3007 fprintf(stderr,
"Verify failed: trie is malformed\n");
3011 if (trie_verify(ft->
trie) < 0) {
3012 fprintf(stderr,
"Verify failed: %s\n",
fr_strerror());
3073 if (!ft->
trie)
return 0;
3094 if (strcmp(argv[0],
"true") == 0) {
3095 print_lineno =
true;
3097 print_lineno =
false;
3118 if (arg2key(argv[0], &key, &bits) < 0) {
3138static int command_lookup(
fr_trie_t *ft,
UNUSED int argc,
char **argv,
char *
out,
size_t outlen)
3144 if (arg2key(argv[0], &key, &bits) < 0) {
3164static int command_remove(
fr_trie_t *ft,
UNUSED int argc,
char **argv,
char *
out,
size_t outlen)
3170 if (arg2key(argv[0], &key, &bits) < 0) {
3176 MPRINT(
"Could not remove key %s\n", key);
3190 MPRINT(
"Still in trie after 'remove' for key %s, found data %s\n", key, (
char const *) answer);
3202static int command_try_to_remove(
fr_trie_t *ft,
UNUSED int argc,
char **argv,
char *
out,
size_t outlen)
3208 if (arg2key(argv[0], &key, &bits) < 0) {
3228 MPRINT(
"Still in trie after 'remove' for key %s, found data %s\n", key, (
char const *) answer);
3245 trie_sprint_ctx_t my_sprint;
3252 my_sprint.buffer =
out;
3253 my_sprint.buflen = outlen;
3262 my_cb.
ctx = &my_sprint;
3278static int command_path(
fr_trie_t *ft,
int argc,
char **argv,
char *
out,
size_t outlen)
3283 data = talloc_strdup(ft, argv[1]);
3296 MPRINT(
"Could not look up key %s\n", argv[0]);
3300 if (answer !=
data) {
3301 MPRINT(
"Expected to find %s, got %s\n", argv[1], (
char const *) answer);
3312 MPRINT(
"Could not remove key %s\n", argv[0]);
3316 if (answer !=
data) {
3317 MPRINT(
"Expected to remove %s, got %s\n", argv[1], (
char const *) answer);
3330static int command_lcp(
UNUSED fr_trie_t *ft,
int argc,
char **argv,
char *
out,
size_t outlen)
3333 int keylen1, keylen2;
3338 key1 = (
uint8_t const *) argv[0];
3339 keylen1 =
BITSOF(strlen(argv[0]));
3341 key2 = (
uint8_t const *) argv[1];
3342 keylen2 =
BITSOF(strlen(argv[1]));
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])));
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])));
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]);
3369 MPRINT(
"Invalid number of arguments\n");
3384 int start_bit, num_bits;
3387 start_bit = atoi(argv[1]);
3388 num_bits = atoi(argv[2]);
3399typedef int (*fr_trie_function_t)(
fr_trie_t *ft,
int argc,
char **argv,
char *
out,
size_t outlen);
3406 fr_trie_function_t function;
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 },
3422 {
"lookup", command_lookup, 1, 1,
true },
3423 {
"remove", command_remove, 1, 1,
true },
3424 {
"-remove", command_try_to_remove, 1, 1,
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 },
3434#define MAX_ARGC (16)
3435int main(
int argc,
char **argv)
3442 char *my_argv[MAX_ARGC];
3447 fprintf(stderr,
"Please specify filename\n");
3451 fp = fopen(argv[1],
"r");
3453 fprintf(stderr,
"Failed opening %s: %s\n", argv[1],
fr_syserror(errno));
3460 talloc_enable_null_tracking();
3466 fprintf(stderr,
"Failed creating trie\n");
3479 for (p =
buffer; *p !=
'\0'; p++) {
3501 if (strcmp(my_argv[0],
commands[i].
name) != 0)
continue;
3508 fprintf(stderr,
"Unknown command '%s' at line %d\n",
3509 my_argv[0], lineno);
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);
3526 printf(
"%d ", lineno);
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);
3537 if (!
commands[cmd].output)
continue;
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);
3551 talloc_report_full(NULL, stdout);
3552 talloc_disable_null_tracking();
static int const char char buffer[256]
#define UNCONST(_type, _ptr)
Remove const qualification from a pointer.
#define CC_NO_UBSAN(_sanitize)
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.
fr_table_elem_name_t name
static TALLOC_CTX * talloc_init_const(char const *name)
Allocate a top level chunk with a constant name.
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.
int(* fr_trie_key_walk_t)(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
#define MPRINT(...)
Internal sanity checks for debugging.
fr_trie_t * fr_trie_alloc(TALLOC_CTX *ctx, fr_trie_key_t get_key, fr_free_t free_data)
Allocate a trie.
static trie_key_match_t trie_match_table[FR_TRIE_MAX]
static fr_trie_user_t * fr_trie_user_alloc(TALLOC_CTX *ctx, void const *data)
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 void * trie_node_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
void * fr_trie_remove(fr_trie_t *ft, void const *data)
Remove an entry, without freeing the data.
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]
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 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.
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.
static void * trie_path_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
static fr_trie_path_t * fr_trie_path_alloc(TALLOC_CTX *ctx, uint8_t const *key, int start_bit, int end_bit)
int fr_trie_walk(fr_trie_t *ft, void *ctx, fr_trie_walk_t callback)
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.
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]
static void * trie_user_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
static fr_trie_path_t * trie_path_split(TALLOC_CTX *ctx, fr_trie_path_t *path, int start_bit, int lcp)
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)
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 void * trie_path_remove(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
static void * trie_user_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
static trie_key_insert_t trie_insert_table[FR_TRIE_MAX]
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_node_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
void * fr_trie_match(fr_trie_t *ft, void const *data)
Match an element exactly in the trie, returning the data.
#define TRIE_TYPE_CHECK(_x, _r)
static fr_trie_t * trie_key_alloc(TALLOC_CTX *ctx, uint8_t const *key, int start_bit, int end_bit, void *data)
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)
void * fr_trie_find(fr_trie_t *ft, void const *data)
Find an element in the trie, returning the data.
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.
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_node_t * trie_node_alloc(TALLOC_CTX *ctx, int bits)
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 *(* trie_key_match_t)(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
static void * trie_node_match(fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)
static int trie_path_walk(fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)
void *(* trie_key_remove_t)(TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)
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_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