diff options
| -rw-r--r-- | CMakeLists.txt | 2 | ||||
| -rw-r--r-- | contrib/lc-btrie/CMakeLists.txt | 8 | ||||
| -rw-r--r-- | contrib/lc-btrie/btrie.c | 2622 | ||||
| -rw-r--r-- | contrib/lc-btrie/btrie.h | 83 | ||||
| -rw-r--r-- | test/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | test/rspamd_radix_test.c | 112 |
6 files changed, 2804 insertions, 24 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index ae950659d..33dcf5cbf 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -471,6 +471,7 @@ INCLUDE_DIRECTORIES("${CMAKE_SOURCE_DIR}/src" "${CMAKE_SOURCE_DIR}/contrib/snowball/include" "${CMAKE_SOURCE_DIR}/contrib/librdns" "${CMAKE_SOURCE_DIR}/contrib/aho-corasick" + "${CMAKE_SOURCE_DIR}/contrib/lc-btrie" "${CMAKE_BINARY_DIR}/src" #Stored in the binary dir "${CMAKE_BINARY_DIR}/src/libcryptobox") @@ -1064,6 +1065,7 @@ ENDIF(GLIB_COMPAT) ADD_SUBDIRECTORY(contrib/xxhash) ADD_SUBDIRECTORY(contrib/cdb) ADD_SUBDIRECTORY(contrib/http-parser) +ADD_SUBDIRECTORY(contrib/lc-btrie) ADD_SUBDIRECTORY(contrib/libottery) IF(ENABLE_SNOWBALL MATCHES "ON") ADD_SUBDIRECTORY(contrib/snowball) diff --git a/contrib/lc-btrie/CMakeLists.txt b/contrib/lc-btrie/CMakeLists.txt new file mode 100644 index 000000000..7ae9ce063 --- /dev/null +++ b/contrib/lc-btrie/CMakeLists.txt @@ -0,0 +1,8 @@ +SET(LCTRIESRC btrie.c) +ADD_LIBRARY(lcbtrie STATIC ${LCTRIESRC}) + +SET(LCTRIE_CFLAGS "-DBUILD_RSPAMD") +if ("${CMAKE_C_COMPILER_ID}" STREQUAL "Clang" OR "${CMAKE_C_COMPILER_ID}" STREQUAL "GNU") + SET(LCTRIE_CFLAGS "${LCTRIE_CFLAGS} -O3") +endif () +set_target_properties(lcbtrie PROPERTIES COMPILE_FLAGS "${LCTRIE_CFLAGS}")
\ No newline at end of file diff --git a/contrib/lc-btrie/btrie.c b/contrib/lc-btrie/btrie.c new file mode 100644 index 000000000..899b05061 --- /dev/null +++ b/contrib/lc-btrie/btrie.c @@ -0,0 +1,2622 @@ +/* Level-Compressed Tree Bitmap (LC-TBM) Trie implementation + * + * Contributed by Geoffrey T. Dairiki <dairiki@dairiki.org> + * + * This file is released under a "Three-clause BSD License". + * + * Copyright (c) 2013, Geoffrey T. Dairiki + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * * Neither the name of Geoffrey T. Dairiki nor the names of other + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GEOFFREY + * T. DAIRIKI BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE + * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + */ + +/***************************************************************** + * + * This code implements a routing table conceptually based on a binary + * trie structure. Internally, the trie is represented by two types + * of compound nodes: "multibit nodes", which contain the top few + * levels of an entire binary subtree; and "level compression" (LC) + * nodes which represent a (potentially long) chain of out-degree one + * (single child) binary nodes (possibly ending at a terminal node). + * + * The multibit nodes are represented using a "Tree Bitmap" structure + * (more on this below), which is very efficient --- both in terms of + * memory usage and lookup speed --- at representing densely branching + * parts of the trie. The LC nodes can efficiently represent long + * non-branching chains of binary trie nodes. Using both node types + * together results in efficient representation of both the sparse and + * dense parts of a binary trie. + * + * Graphically, here's the rough idea: + * + * ........ + * .LC o . + * . / . LC nodes can + * . o . <= represent long chains + * . \ . of (non-branching) binary + * . o . trie nodes + * . / . + * . o . + * ......../..... + * .TBM o . + * . / \ . TBM nodes can represent + * . o * . <= several levels of densely + * . / \ . branching binary trie nodes + * . o o . + * ......./.....\....... + * .TBM o .. o LC. + * . / \ .. \ . + * . o o .. o . + * . / / \ .. \ . + * . * o *.. o . + * ...../....... / . + * . o LC. . o . + * . \ . .....\...... + * . * . . o TBM. + * ........ . / \ . + * . o o . + * . / \ \ . + * .* * *. + * ........... + * + * Terminology + * ----------- + * + * node + * Usually, in the comments below, "node" will be used to refer to + * a compound node: either a multibit (TBM) node or an LC node. + * + * "internal node" or "prefix" + * The terms "prefix" or "internal node" are used to refer to + * a node in the binary trie which is internal to a multibit (TBM) + * node. + * + * ---------------------------------------------------------------- + * + * Internal Representation of the Nodes + * ==================================== + * + * Multibit (TBM) Nodes + * ~~~~~~~~~~~~~~~~~~~~ + * + * The multibit nodes are represented using a "Tree Bitmap" (TBM) + * structure as described by Eatherton, Dittia and Varghese[1]. See + * the paper referenced below for basic details. + * + * A multibit node, represents several levels of a binary trie. + * For example, here is a multibit node of stride 2 (which represent + * two levels of a binary trie. + * + * +------- | ------+ + * | multi o | + * | bit / \ | + * | node / \ | + * | o * | + * +--- / \ - / \ --+ + * O + * + * Note that, for a multibit node of stride S, there are 2^S - 1 internal + * nodes, each of which may have data (or not) associated with them, and + * 2^S "external paths" leading to other (possibly compound nodes). + * (In the diagram above, one of three internal node (the one denoted by "*") + * has data, and one of four extending paths leads to an external node + * (denoted by the 'O').) + * + * The TBM structure can represent these bitmaps in a very memory-efficient + * manner. + * + * Each TBM node consists of two bitmaps --- the "internal bitmap" and the + * "extending paths bitmap" --- and a pointer which points to an array + * which contains both the extending path ("child") nodes and any + * internal prefix data for the TBM node. + * + * +--------+--------+ + * TBM | ext bm | int bm | + * Node +--------+--------+ + * | pointer |----+ + * +-----------------+ | + * | + * | + * +-----------------+ | + * | extending path | | + * | node[N-1] | | + * +-----------------+ | + * / ... / | + * / ... / | + * +-----------------+ | + * | extending path | | + * | node[0] | | + * +-----------------+<---+ + * | int. data[M-1] | + * +-----------------+ + * / ... / + * +-----------------+ + * | int. data[0] | + * +-----------------+ + * + * The extending paths bitmap (or "ext bitmap") has one bit for each + * possible "extending path" from the bottom of the multibit node. To + * check if a particular extending path is present, one checks to see if + * the corresponding bit is set in the ext bitmap. The index into the + * array of children for that path can be found by counting the number + * of set bits to the left of that bit. + * + * Similary, the internal bitmap has one bit for each binary node + * which is internal to the multibit node. To determine whether there + * is data stored for an internal prefix, one checks the corresponding + * bit in the internal bitmap. As for extending paths, the index into + * the array of internal data is found by counting the number of set + * bits to the left of that bit. + * + * To save space in the node structure, the node data array is stored + * contiguously with the node extending path array. The single + * ("children") pointer in the TBM structure points to the beginning + * of the array of extending path nodes and to (one past) the end of + * the the internal data array. + * + * The multibit stride is chosen so that the entire TBM node structure fits + * in the space of two pointers. On 32 bit machines this means the stride + * is four (each of the two bitmaps is 16 bits); on 32 bit machines the + * stride is five. + * + * Note that there are only 2^stride - 1 internal prefixes in a TBM + * node. That means there is one unused bit in the internal bitmap. + * We require that that bit must always be clear for a TBM node. (If + * set, it indicates that the structure represents, instead, an LC + * node. See below.) + * + * ---------------------------------------------------------------- + * + * Level Compression (LC) Nodes + * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + * + * LC nodes are used to represent a chain of out-degree-one (single + * child) prefixes in the binary trie. The are represented by a bit + * string (the "relative prefix") along with its length and a pointer + * to the extending path (the next node past the LC node.) + * + * + * Non-Terminal LC Node: + * + * +------------------+-------+ + * | relative prefix |1|0|len| + * +------------------+-------+ + * | ptr.child |--+ + * +--------------------------+ | + * | + * | + * +--------------------------+ | + * | Next node - | | + * | either LC or TBM | | + * | | | + * +--------------------------+<-+ + * + * The Relative Prefix + * ------------------- + * + * The maximum relative prefix per LC node is selected so that (again) + * the entire node structure fits in the space of two pointers. On 32 bit + * machines, the maximum relative prefix is 24 bits; on 62 bit machines + * the limit is 56 bits. + * + * In the LC node structure, the relative prefix is stored as an array + * of bytes. To avoid some bit-shifting during tree searches, these + * bytes are byte-aligned with the global prefix. In other words, in + * general there are (pos % 8) "pad" bits at the beginning of the + * relative prefix --- where pos "starting bit" (or depth in the + * binary tree) of the LC node --- which really belong to the parent + * node(s) of the LC node. For efficiency (so that we don't have to + * mask them out when matching) we require that these pad bits be + * correct --- they must match the path which leads to the LC node. + * + * The relative prefix length stored in the LC node structure does not + * count the pad bits. + * + * Terminal Node Compression + * ------------------------- + * + * For memory efficiency, we also support "terminal LC" nodes. When + * the extension path from an LC node consists a single terminal node, + * we store that terminal nodes data directly in the parent LC node. + * + * Instead of this: + * + * +------------------+-------+ + * | relative prefix |1|0|len| + * +------------------+-------+ + * | ptr.child |--+ + * +--------------------------+ | + * | + * +--------------------------+ | + * | Terminal Node (TBM node, | | + * | empty except for the | | + * +--| root internal node.) | | + * | +--------------------------+<-+ + * | + * +->+--------------------------+ + * | terminal node data | + * +--------------------------+ + * + * We can do this: + * + * +------------------+-------+ + * | relative prefix |1|1|len| + * +------------------+-------+ + * | terminal node data | + * +--------------------------+ + * + * Terminal LC nodes are differentiated from non-terminal LC nodes + * by the setting of the is_terminal flag. + * + * Node Structure Packing Details + * ------------------------------ + * + * The LC and TBM node structures are carefully packed so that the + * "is_lc" flag (which indicates that a node is an LC node) + * corresponds to the one unused bit in the internal bitmap of the TBM + * node structure (which we require to be zero for TBM nodes). + * + * ---------------------------------------------------------------- + * + * References + * ========== + * + * [1] Will Eatherton, George Varghese, and Zubin Dittia. 2004. Tree + * bitmap: hardware/software IP lookups with incremental + * updates. SIGCOMM Comput. Commun. Rev. 34, 2 (April 2004), + * 97-122. DOI=10.1145/997150.997160 + * http://doi.acm.org/10.1145/997150.997160 + * http://comnet.kaist.ac.kr/yhlee/CN_2008_Spring/readings/Eath-04-tree_bitmap.pdf + * + ****************************************************************/ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <setjmp.h> +#if defined(TEST) && defined(NDEBUG) +# warning undefining NDEBUG for TEST build +# undef NDEBUG +#endif +#include <assert.h> + +#include "btrie.h" +#include "libutil/mem_pool.h" + +#if __SIZEOF_POINTER__ == 4 +# define TBM_STRIDE 4 +#elif __SIZEOF_POINTER__ == 8 +# define TBM_STRIDE 5 +#else +# error "Unsupported word size" +#endif + +#ifndef NO_STDINT_H +# if TBM_STRIDE == 4 +typedef uint16_t tbm_bitmap_t; +# else +typedef uint32_t tbm_bitmap_t; +# endif +#else /* NO_STDINT_H */ +# if TBM_STRIDE == 4 +# if SIZEOF_SHORT == 2 +typedef short unsigned tbm_bitmap_t; +# else +# error "can not determine type for 16 bit unsigned int" +# endif +# else /* TBM_STRIDE == 5 */ +# if SIZEOF_INT == 4 +typedef unsigned tbm_bitmap_t; +# elif SIZEOF_LONG == 4 +typedef long unsigned tbm_bitmap_t; +# else +# error "can not determine type for 32 bit unsigned int" +# endif +# endif +#endif + +#define TBM_FANOUT (1U << TBM_STRIDE) +#define LC_BYTES_PER_NODE (__SIZEOF_POINTER__ - 1) + +typedef union node_u node_t; + +/* The tbm_node and lc_node structs must be packed so that the the + * high bit (LC_FLAGS_IS_LC) of lc_flags in the the lc_node struct + * coincides with bit zero (the most significant bit) of tbm_node's + * int_bm. (This bit is how we differentiate between the two node + * types. It is always clear for a tbm_node and always set for an + * lc_node.) + */ + +struct tbm_node +{ +#ifdef WORDS_BIGENDIAN + tbm_bitmap_t int_bm; /* the internal bitmap */ + tbm_bitmap_t ext_bm; /* extending path ("external") bitmap */ +#else + tbm_bitmap_t ext_bm; /* extending path ("external") bitmap */ + tbm_bitmap_t int_bm; /* the internal bitmap */ +#endif + union + { + node_t *children; /* pointer to array of children */ + const void **data_end; /* one past end of internal prefix data array */ + } ptr; +}; + +struct lc_node +{ + /* lc_flags contains the LC prefix length and a couple of bit flags + * (apparently char-sized bit fields are a gcc extension) + */ +# define LC_FLAGS_IS_LC 0x80 +# define LC_FLAGS_IS_TERMINAL 0x40 +# define LC_FLAGS_LEN_MASK 0x3f +#ifdef WORDS_BIGENDIAN + btrie_oct_t lc_flags; + btrie_oct_t prefix[LC_BYTES_PER_NODE]; +#else + btrie_oct_t prefix[LC_BYTES_PER_NODE]; + btrie_oct_t lc_flags; +#endif + union + { + node_t *child; /* pointer to child (if !is_terminal) */ + const void *data; /* the prefix data (if is_terminal) */ + } ptr; +}; + +union node_u +{ + struct tbm_node tbm_node; + struct lc_node lc_node; +}; + +struct free_hunk +{ + struct free_hunk *next; +}; + +#define MAX_CHILD_ARRAY_LEN (TBM_FANOUT + TBM_FANOUT / 2) + +struct btrie +{ + node_t root; + + rspamd_mempool_t *mp; + struct free_hunk *free_list[MAX_CHILD_ARRAY_LEN]; + jmp_buf exception; + /* mem mgmt stats */ + size_t alloc_total; /* total bytes allocated from mempool */ + size_t alloc_data; /* bytes allocated for TBM node int. prefix data */ + size_t alloc_waste; /* bytes wasted by rounding of data array size */ +#ifdef BTRIE_DEBUG_ALLOC + size_t alloc_hist[MAX_CHILD_ARRAY_LEN * 2]; /* histogram of alloc sizes */ +#endif + + /* trie stats */ + size_t n_entries; /* number of entries */ + size_t n_tbm_nodes; /* total number of TBM nodes in tree */ + size_t n_lc_nodes; /* total number of LC nodes in tree */ +}; + +/**************************************************************** + * + * Memory management + * + * We will need to frequently resize child/data arrays. The current + * mempool implementation does not support resizing/freeing, so here + * we roll our own. + */ + +static inline void _free_hunk(struct btrie *btrie, void *buf, unsigned n_nodes) +{ + struct free_hunk *hunk = buf; + + hunk->next = btrie->free_list[n_nodes - 1]; + btrie->free_list[n_nodes - 1] = hunk; +} + +static inline void * +_get_hunk(struct btrie *btrie, unsigned n_nodes) +{ + struct free_hunk *hunk = btrie->free_list[n_nodes - 1]; + + if (hunk != NULL) + btrie->free_list[n_nodes - 1] = hunk->next; + return hunk; +} + +/* Get pointer to uninitialized child/data array. + * + * Allocates memory for an array of NDATA (void *)s followed by an + * array of NCHILDREN (node_t)s. The returned pointer points to to + * beginning of the children array (i.e. it points to (one past) the + * end of the data array.) + */ +static node_t * +alloc_nodes(struct btrie *btrie, unsigned nchildren, unsigned ndata) +{ + size_t n_nodes = nchildren + (ndata + 1) / 2; + node_t *hunk; + + assert(n_nodes > 0 && n_nodes <= MAX_CHILD_ARRAY_LEN); + + hunk = _get_hunk (btrie, n_nodes); + if (hunk == NULL) { + /* Do not have free hunk of exactly the requested size, look for a + * larger hunk. (The funny order in which we scan the buckets is + * heuristically selected in an attempt to minimize unnecessary + * creation of small fragments) + */ + size_t n, skip = n_nodes > 4 ? 4 : n_nodes; + for (n = n_nodes + skip; n <= MAX_CHILD_ARRAY_LEN; n++) { + if ((hunk = _get_hunk (btrie, n)) != NULL) { + _free_hunk (btrie, hunk + n_nodes, n - n_nodes); + goto DONE; + } + } + for (n = n_nodes + 1; n < n_nodes + skip && n <= MAX_CHILD_ARRAY_LEN; + n++) { + if ((hunk = _get_hunk (btrie, n)) != NULL) { + _free_hunk (btrie, hunk + n_nodes, n - n_nodes); + goto DONE; + } + } + + /* failed to find free hunk, allocate a fresh one */ + hunk = rspamd_mempool_alloc (btrie->mp, n_nodes * sizeof(node_t)); + if (hunk == NULL) + longjmp (btrie->exception, BTRIE_ALLOC_FAILED); + btrie->alloc_total += n_nodes * sizeof(node_t); + } + + DONE: btrie->alloc_data += ndata * sizeof(void *); + btrie->alloc_waste += (ndata % 2) * sizeof(void *); +#ifdef BTRIE_DEBUG_ALLOC + btrie->alloc_hist[2 * nchildren + ndata]++; +#endif + + /* adjust pointer to allow room for data array before child array */ + return hunk + (ndata + 1) / 2; +} + +/* Free memory allocated by alloc_nodes */ +static void free_nodes(struct btrie *btrie, node_t *buf, unsigned nchildren, + unsigned ndata) +{ + size_t n_nodes = nchildren + (ndata + 1) / 2; + + assert(n_nodes > 0 && n_nodes <= MAX_CHILD_ARRAY_LEN); + + _free_hunk (btrie, buf - (ndata + 1) / 2, n_nodes); + + btrie->alloc_data -= ndata * sizeof(void *); + btrie->alloc_waste -= (ndata % 2) * sizeof(void *); +#ifdef BTRIE_DEBUG_ALLOC + btrie->alloc_hist[2 * nchildren + ndata]--; +#endif +} + +/* Debugging/development only: */ +#ifdef BTRIE_DEBUG_ALLOC +static void +dump_alloc_hist(const struct btrie *btrie) +{ + unsigned bin; + size_t total_alloc = 0; + size_t total_free = 0; + size_t total_bytes = 0; + size_t total_waste = 0; + size_t total_free_bytes = 0; + + puts("hunk alloc free alloc wasted free"); + puts("size hunks hunks bytes bytes bytes"); + puts("==== ====== ====== ======== ======== ========"); + + for (bin = 1; bin < 2 * MAX_CHILD_ARRAY_LEN; bin++) { + size_t n_alloc = btrie->alloc_hist[bin]; + size_t bytes = n_alloc * bin * sizeof(void *); + size_t waste_bytes = (bin % 2) * n_alloc * sizeof(void *); + size_t n_free = 0, free_bytes; + if (bin % 2 == 0) { + const struct free_hunk *hunk; + for (hunk = btrie->free_list[bin / 2 - 1]; hunk; hunk = hunk->next) + n_free++; + } + free_bytes = n_free * bin * sizeof(void *); + + printf("%3zu: %6zu %6zu %8zu %8zu %8zu\n", bin * sizeof(void *), + n_alloc, n_free, bytes, waste_bytes, free_bytes); + + total_alloc += n_alloc; + total_free += n_free; + total_bytes += bytes; + total_waste += waste_bytes; + total_free_bytes += free_bytes; + } + puts("---- ------ ------ -------- -------- --------"); + printf("SUM: %6zu %6zu %8zu %8zu %8zu\n", + total_alloc, total_free, total_bytes, total_waste, total_free_bytes); +} +#endif + +/**************************************************************** + * + * Bit twiddling + * + */ + +static inline tbm_bitmap_t bit(unsigned b) +{ + return 1U << ((1 << TBM_STRIDE) - 1 - b); +} + +/* count the number of set bits in bitmap + * + * algorithm from + * http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel + */ +static inline unsigned count_bits(tbm_bitmap_t v) +{ + /* Count set bits in parallel. */ + /* v = (v & 0x5555...) + ((v >> 1) & 0x5555...); */ + v -= (v >> 1) & (tbm_bitmap_t) ~0UL / 3; + /* v = (v & 0x3333...) + ((v >> 2) & 0x3333...); */ + v = (v & (tbm_bitmap_t) ~0UL / 5) + ((v >> 2) & (tbm_bitmap_t) ~0UL / 5); + /* v = (v & 0x0f0f...) + ((v >> 4) & 0x0f0f...); */ + v = (v + (v >> 4)) & (tbm_bitmap_t) ~0UL / 17; + /* v = v % 255; */ +#if TBM_STRIDE == 4 + /* tbm_bitmap_t is uint16_t, avoid the multiply */ + return (v + (v >> 8)) & 0x0ff; +#else + return (v * (tbm_bitmap_t) (~0UL / 255)) >> ((sizeof(tbm_bitmap_t) - 1) * 8); +#endif +} + +static inline unsigned count_bits_before(tbm_bitmap_t bm, int b) +{ + return b ? count_bits (bm >> ((1 << TBM_STRIDE) - b)) : 0; +} + +static inline unsigned count_bits_from(tbm_bitmap_t bm, int b) +{ + return count_bits (bm << b); +} + +/* extracts a few bits from bitstring, returning them as an integer */ +static inline btrie_oct_t extract_bits(const btrie_oct_t *prefix, unsigned pos, + unsigned nbits) +{ + if (nbits == 0) + return 0; + else { + unsigned v = (prefix[pos / 8] << 8) + prefix[pos / 8 + 1]; + return (v >> (16 - nbits - pos % 8)) & ((1U << nbits) - 1); + } +} + +static inline unsigned extract_bit(const btrie_oct_t *prefix, int pos) +{ + return (prefix[pos / 8] >> (7 - pos % 8)) & 0x01; +} + +/* get mask for high n bits of a byte */ +static inline btrie_oct_t high_bits(unsigned n) +{ + return (btrie_oct_t) -(1U << (8 - n)); +} + +/* determine whether two prefixes are equal */ +static inline int prefixes_equal(const btrie_oct_t *pfx1, + const btrie_oct_t *pfx2, unsigned len) +{ + return (memcmp (pfx1, pfx2, len / 8) == 0 + && ((pfx1[len / 8] ^ pfx2[len / 8]) & high_bits (len % 8)) == 0); +} + +/* determine length of longest common subprefix */ +static inline unsigned common_prefix(const btrie_oct_t *pfx1, + const btrie_oct_t *pfx2, unsigned len) +{ + /* algorithm adapted from + * http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup + */ + static btrie_oct_t leading_zeros[] = + { 8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, + 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, }; + unsigned nb; + + for (nb = 0; nb < len / 8; nb++) { + unsigned diff = *pfx1++ ^ *pfx2++; + if (diff != 0) + return 8 * nb + leading_zeros[diff]; + } + if (len % 8) { + unsigned n = leading_zeros[*pfx1 ^ *pfx2]; + if (n < len % 8) + return 8 * nb + n; + } + return len; +} + +/**************************************************************** + */ + +static inline int is_empty_node(const node_t *node) +{ + return node->tbm_node.ext_bm == 0 && node->tbm_node.int_bm == 0; +} + +static inline int is_lc_node(const node_t *node) +{ + return (node->lc_node.lc_flags & LC_FLAGS_IS_LC) != 0; +} + +static inline int is_tbm_node(const node_t *node) +{ + return !is_lc_node (node); +} + +/* is node a TBM node with internal data? */ +static inline int has_data(const node_t *node) +{ + return is_tbm_node (node) && node->tbm_node.int_bm != 0; +} + +static inline unsigned base_index(unsigned pfx, unsigned plen) +{ + assert(plen < TBM_STRIDE); + assert(pfx < (1U << plen)); + return pfx | (1U << plen); +} + +/* initialize node to an empty TBM node */ +static inline void init_empty_node(struct btrie *btrie, node_t *node) +{ + memset(node, 0, sizeof(*node)); + btrie->n_tbm_nodes++; +} + +/* get pointer to TBM internal prefix data */ +static inline const void ** +tbm_data_p(const struct tbm_node *node, unsigned pfx, unsigned plen) +{ + unsigned bi = base_index (pfx, plen); + + if ((node->int_bm & bit (bi)) == 0) + return NULL; /* no data */ + else { + return &node->ptr.data_end[-(int) count_bits_from (node->int_bm, bi)]; + } +} + +/* add an element to the internal data array */ +static void tbm_insert_data(struct btrie *btrie, struct tbm_node *node, + unsigned pfx, unsigned plen, const void *data) +{ + /* XXX: don't realloc if already big enough? */ + unsigned bi = base_index (pfx, plen); + unsigned nchildren = count_bits (node->ext_bm); + int ndata = count_bits (node->int_bm); + unsigned di = count_bits_before (node->int_bm, bi); + node_t *old_children = node->ptr.children; + const void **old_data_beg = node->ptr.data_end - ndata; + const void **data_beg; + + assert((node->int_bm & bit (bi)) == 0); + + node->ptr.children = alloc_nodes (btrie, nchildren, ndata + 1); + data_beg = node->ptr.data_end - (ndata + 1); + data_beg[di] = data; + node->int_bm |= bit (bi); + + if (nchildren != 0 || ndata != 0) { + memcpy(data_beg, old_data_beg, di * sizeof(data_beg[0])); + memcpy(&data_beg[di + 1], &old_data_beg[di], + (ndata - di) * sizeof(data_beg[0]) + + nchildren * sizeof(node_t)); + free_nodes (btrie, old_children, nchildren, ndata); + } +} + +/* determine whether TBM has internal prefix data for pfx/plen or ancestors */ +static inline int has_internal_data(const struct tbm_node *node, unsigned pfx, + unsigned plen) +{ +# define BIT(n) (1U << ((1 << TBM_STRIDE) - 1 - (n))) +# define B0() BIT(1) /* the bit for 0/0 */ +# define B1(n) (BIT((n) + 2) | B0()) /* the bits for n/1 and its ancestors */ +# define B2(n) (BIT((n) + 4) | B1(n >> 1)) /* the bits for n/2 and ancestors */ +# define B3(n) (BIT((n) + 8) | B2(n >> 1)) /* the bits for n/3 and ancestors */ +# define B4(n) (BIT((n) + 16) | B3(n >> 1)) /* the bits for n/4 and ancestors */ + + static tbm_bitmap_t ancestors[] = + { 0, B0(), B1(0), B1(1), B2(0), B2(1), B2(2), B2(3), B3(0), B3(1), B3(2), + B3(3), B3(4), B3(5), B3(6), B3(7), +# if TBM_STRIDE == 5 + B4(0), B4(1), B4(2), B4(3), B4(4), B4(5), B4(6), B4(7), B4(8), B4( + 9), B4(10), B4(11), B4(12), B4(13), B4(14), B4(15), +# elif TBM_STRIDE != 4 +# error "unsupported TBM_STRIDE" +# endif + }; +# undef B4 +# undef B3 +# undef B2 +# undef B1 +# undef B0 +# undef BIT + + return (node->int_bm & ancestors[base_index (pfx, plen)]) != 0; +} + +/* get pointer to TBM extending path */ +static inline node_t * +tbm_ext_path(const struct tbm_node *node, unsigned pfx) +{ + if ((node->ext_bm & bit (pfx)) == 0) + return NULL; + else + return &node->ptr.children[count_bits_before (node->ext_bm, pfx)]; +} + +/* resize TBM node child array to make space for new child node */ +static node_t * +tbm_insert_ext_path(struct btrie *btrie, struct tbm_node *node, unsigned pfx) +{ + unsigned nchildren = count_bits (node->ext_bm); + unsigned ci = count_bits_before (node->ext_bm, pfx); + int ndata = count_bits (node->int_bm); + node_t *old_children = node->ptr.children; + const void **old_data_beg = node->ptr.data_end - ndata; + + assert((node->ext_bm & bit (pfx)) == 0); + + node->ptr.children = alloc_nodes (btrie, nchildren + 1, ndata); + init_empty_node (btrie, &node->ptr.children[ci]); + node->ext_bm |= bit (pfx); + + if (nchildren != 0 || ndata != 0) { + const void **data_beg = node->ptr.data_end - ndata; + memcpy(data_beg, old_data_beg, + ndata * sizeof(data_beg[0]) + ci * sizeof(node_t)); + memcpy(&node->ptr.children[ci + 1], &old_children[ci], + (nchildren - ci) * sizeof(old_children[0])); + free_nodes (btrie, old_children, nchildren, ndata); + } + + return &node->ptr.children[ci]; +} + +static inline int lc_is_terminal(const struct lc_node *node) +{ + return (node->lc_flags & LC_FLAGS_IS_TERMINAL) != 0; +} + +static inline unsigned lc_len(const struct lc_node *node) +{ + return node->lc_flags & LC_FLAGS_LEN_MASK; +} + +static inline void lc_init_flags(struct lc_node *node, int is_terminal, + unsigned len) +{ + assert((len & ~LC_FLAGS_LEN_MASK) == 0); + node->lc_flags = LC_FLAGS_IS_LC | len; + if (is_terminal) + node->lc_flags |= LC_FLAGS_IS_TERMINAL; +} + +static inline void lc_add_to_len(struct lc_node *node, int increment) +{ + unsigned new_len = lc_len (node) + increment; + assert((new_len & ~LC_FLAGS_LEN_MASK) == 0); + node->lc_flags = (node->lc_flags & ~LC_FLAGS_LEN_MASK) | new_len; +} + +static inline unsigned lc_shift(unsigned pos) +{ + return pos / 8; +} + +static inline unsigned lc_base(unsigned pos) +{ + return 8 * lc_shift (pos); +} + +static inline unsigned lc_bits(const struct lc_node *node, unsigned pos) +{ + return pos % 8 + lc_len (node); +} + +static inline unsigned lc_bytes(const struct lc_node *node, unsigned pos) +{ + return (lc_bits (node, pos) + 7) / 8; +} + +static inline unsigned lc_leading_bits(const struct lc_node *node, unsigned pos, + unsigned nbits) +{ + return extract_bits (node->prefix, pos % 8, nbits); +} + +/* Initialize a new terminal LC node + * + * If prefix is too long to fit in a single LC node, then a chain + * of LC nodes will be created. + */ +static void init_terminal_node(struct btrie *btrie, node_t *dst, unsigned pos, + const btrie_oct_t *prefix, unsigned len, const void *data) +{ + struct lc_node *node = &dst->lc_node; + unsigned nbytes = (len + 7) / 8; + + while (nbytes - lc_shift (pos) > LC_BYTES_PER_NODE) { + memcpy(node->prefix, prefix + lc_shift (pos), LC_BYTES_PER_NODE); + lc_init_flags (node, 0, 8 * LC_BYTES_PER_NODE - pos % 8); + node->ptr.child = alloc_nodes (btrie, 1, 0); + pos += lc_len (node); + node = &node->ptr.child->lc_node; + btrie->n_lc_nodes++; + } + + memcpy(node->prefix, prefix + lc_shift (pos), nbytes - lc_shift (pos)); + lc_init_flags (node, 1, len - pos); + node->ptr.data = data; + btrie->n_lc_nodes++; +} + +/* merge chains of multiple LC nodes into a single LC node, if possible. + * + * also ensure that the leading nodes in the LC chain have maximum length. + */ +static void coalesce_lc_node(struct btrie *btrie, struct lc_node *node, + unsigned pos) +{ + while (!lc_is_terminal (node) && lc_bits (node, pos) < 8 * LC_BYTES_PER_NODE + && is_lc_node (node->ptr.child)) { + struct lc_node *child = &node->ptr.child->lc_node; + unsigned spare_bits = 8 * LC_BYTES_PER_NODE - lc_bits (node, pos); + unsigned end = pos + lc_len (node); + unsigned shift = lc_shift (end) - lc_shift (pos); + if (lc_len (child) <= spare_bits) { + /* node plus child will fit in single node - merge */ + memcpy(node->prefix + shift, child->prefix, lc_bytes (child, end)); + lc_init_flags (node, lc_is_terminal (child), + lc_len (node) + lc_len (child)); + node->ptr = child->ptr; + free_nodes (btrie, (node_t *) child, 1, 0); + btrie->n_lc_nodes--; + } + else { + /* can't merge, but can take some of childs bits */ + unsigned cshift = lc_shift (end + spare_bits) - lc_shift (end); + + memcpy(node->prefix + shift, child->prefix, + LC_BYTES_PER_NODE - shift); + lc_add_to_len (node, spare_bits); + if (cshift) + memmove(child->prefix, child->prefix + cshift, + lc_bytes (child, end) - cshift); + assert(lc_len (child) > spare_bits); + lc_add_to_len (child, -spare_bits); + + pos += lc_len (node); + node = child; + } + } +} + +static void init_tbm_node(struct btrie *btrie, node_t *node, unsigned pos, + const btrie_oct_t pbyte, const void **root_data_p, node_t *left, + node_t *right); + +/* given an LC node at orig_pos, create a new (shorter) node at pos */ +static void shorten_lc_node(struct btrie *btrie, node_t *dst, unsigned pos, + struct lc_node *src, unsigned orig_pos) +{ + assert(orig_pos < pos); + assert(lc_len (src) >= pos - orig_pos); + assert(dst != (node_t * )src); + + if (lc_len (src) == pos - orig_pos && !lc_is_terminal (src)) { + /* just steal the child */ + node_t *child = src->ptr.child; + *dst = *child; + free_nodes (btrie, child, 1, 0); + btrie->n_lc_nodes--; + } + else { + struct lc_node *node = &dst->lc_node; + unsigned shift = lc_shift (pos) - lc_shift (orig_pos); + if (shift) { + memmove(node->prefix, src->prefix + shift, + lc_bytes (src, orig_pos) - shift); + node->lc_flags = src->lc_flags; + node->ptr = src->ptr; + } + else { + *node = *src; + } + lc_add_to_len (node, -(pos - orig_pos)); + coalesce_lc_node (btrie, node, pos); + } +} + +/* convert LC node to non-terminal LC node of length len *in place* + * + * on entry, node must have length at least len + */ +static void split_lc_node(struct btrie *btrie, struct lc_node *node, + unsigned pos, unsigned len) +{ + node_t *child = alloc_nodes (btrie, 1, 0); + + assert(lc_len (node) >= len); + shorten_lc_node (btrie, child, pos + len, node, pos); + + lc_init_flags (node, 0, len); + node->ptr.child = child; + btrie->n_lc_nodes++; +} + +/* convert non-terminal LC node of length one to a TBM node *in place* */ +static void convert_lc_node_1(struct btrie *btrie, struct lc_node *node, + unsigned pos) +{ + btrie_oct_t pbyte = node->prefix[0]; + node_t *child = node->ptr.child; + node_t *left, *right; + + assert(lc_len (node) == 1); + assert(!lc_is_terminal (node)); + + if (extract_bit (node->prefix, pos % 8)) + left = NULL, right = child; + else + left = child, right = NULL; + init_tbm_node (btrie, (node_t *) node, pos, pbyte, NULL, left, right); + free_nodes (btrie, child, 1, 0); + btrie->n_lc_nodes--; +} + +/* convert an LC node to TBM node *in place* */ +static void convert_lc_node(struct btrie *btrie, struct lc_node *node, + unsigned pos) +{ + unsigned len = lc_len (node); + + if (len >= TBM_STRIDE) { + unsigned pfx = lc_leading_bits (node, pos, TBM_STRIDE); + struct tbm_node *result = (struct tbm_node *) node; + + /* split to LC of len TBM_STRIDE followed by child (extending path) */ + split_lc_node (btrie, node, pos, TBM_STRIDE); + /* then convert leading LC node to TBM node */ + result->int_bm = 0; + result->ext_bm = bit (pfx); + btrie->n_lc_nodes--; + btrie->n_tbm_nodes++; + } + else if (lc_is_terminal (node)) { + /* convert short terminal LC to TBM (with internal data) */ + unsigned pfx = lc_leading_bits (node, pos, len); + const void *data = node->ptr.data; + node_t *result = (node_t *) node; + + init_empty_node (btrie, result); + tbm_insert_data (btrie, &result->tbm_node, pfx, len, data); + + btrie->n_lc_nodes--; + } + else { + assert(len > 0); + for (; len > 1; len--) { + split_lc_node (btrie, node, pos, len - 1); + convert_lc_node_1 (btrie, &node->ptr.child->lc_node, pos + len - 1); + } + convert_lc_node_1 (btrie, node, pos); + } +} + +static void insert_lc_node(struct btrie *btrie, node_t *dst, unsigned pos, + btrie_oct_t pbyte, unsigned last_bit, node_t *tail) +{ + struct lc_node *node = &dst->lc_node; + btrie_oct_t mask = 1 << (7 - (pos % 8)); + btrie_oct_t bit = last_bit ? mask : 0; + + if (mask != 0x01 && is_lc_node (tail)) { + /* optimization: LC tail has room for the extra bit (without shifting) */ + assert((tail->lc_node.prefix[0] & mask) == bit); + *node = tail->lc_node; + lc_add_to_len (node, 1); + return; + } + + /* add new leading LC node of len 1 */ + node->prefix[0] = pbyte | bit; + lc_init_flags (node, 0, 1); + node->ptr.child = alloc_nodes (btrie, 1, 0); + node->ptr.child[0] = *tail; + btrie->n_lc_nodes++; + + if (is_lc_node (tail)) + coalesce_lc_node (btrie, node, pos); +} + +/* given: + * pbyte: the bits in the prefix between lc_base(pos) and pos + * pfx: the next TBM_STRIDE bits in the prefix starting at pos + * returns: + * the bits in the prefix between lc_base(pos + plen) and pos + plen + */ +static inline btrie_oct_t next_pbyte(btrie_oct_t pbyte, unsigned pos, + unsigned pfx) +{ + unsigned end = pos + TBM_STRIDE; + + if (end % 8 != 0) { + btrie_oct_t nbyte = (btrie_oct_t) pfx << (8 - end % 8); + if (end % 8 > TBM_STRIDE) + nbyte |= pbyte & high_bits (pos % 8); + return nbyte; + } + return 0; +} + +/* construct a new TBM node, given the data and children of the + * root prefix of the new node. + */ +static void init_tbm_node(struct btrie *btrie, node_t *dst, unsigned pos, + const btrie_oct_t pbyte, const void **root_data_p, node_t *left, + node_t *right) +{ + struct tbm_node *node = &dst->tbm_node; + unsigned nchildren = 0; + unsigned ndata = 0; + node_t children[TBM_FANOUT]; + const void *data[TBM_FANOUT - 1]; + tbm_bitmap_t ext_bm = 0; + tbm_bitmap_t int_bm = 0; + unsigned i, d, pfx_base; + + if (left && is_lc_node (left) && lc_len (&left->lc_node) < TBM_STRIDE) + convert_lc_node (btrie, &left->lc_node, pos + 1); + if (right && is_lc_node (right) && lc_len (&right->lc_node) < TBM_STRIDE) + convert_lc_node (btrie, &right->lc_node, pos + 1); + + /* set internal data for root prefix */ + if (root_data_p) { + data[ndata++] = *root_data_p; + int_bm |= bit (base_index (0, 0)); + } + /* copy internal data from children */ + for (d = 0; d < TBM_STRIDE - 1; d++) { + if (left && has_data (left)) { + for (i = 0; i < 1U << d; i++) { + const void **data_p = tbm_data_p (&left->tbm_node, i, d); + if (data_p) { + data[ndata++] = *data_p; + int_bm |= bit (base_index (i, d + 1)); + } + } + } + if (right && has_data (right)) { + for (i = 0; i < 1U << d; i++) { + const void **data_p = tbm_data_p (&right->tbm_node, i, d); + if (data_p) { + data[ndata++] = *data_p; + int_bm |= bit (base_index (i + (1 << d), d + 1)); + } + } + } + } + + /* copy extending paths */ + for (pfx_base = 0; pfx_base < TBM_FANOUT; pfx_base += TBM_FANOUT / 2) { + node_t *child = pfx_base ? right : left; + if (child == NULL) { + continue; + } + else if (is_lc_node (child)) { + unsigned pfx = pfx_base + lc_leading_bits (&child->lc_node, pos + 1, + TBM_STRIDE - 1); + /* child is LC node, just shorten it by TBM_STRIDE - 1 */ + shorten_lc_node (btrie, &children[nchildren++], pos + TBM_STRIDE, + &child->lc_node, pos + 1); + ext_bm |= bit (pfx); + } + else if (!is_empty_node (child)) { + /* convert deepest internal prefixes of child to extending paths + * of the new node + */ + for (i = 0; i < TBM_FANOUT / 2; i++) { + const void **data_p = tbm_data_p (&child->tbm_node, i, + TBM_STRIDE - 1); + node_t *left_ext = tbm_ext_path (&child->tbm_node, 2 * i); + node_t *right_ext = tbm_ext_path (&child->tbm_node, 2 * i + 1); + if (data_p || left_ext || right_ext) { + node_t *ext_path = &children[nchildren++]; + unsigned pfx = pfx_base + i; + btrie_oct_t npbyte = next_pbyte (pbyte, pos, pfx); + + ext_bm |= bit (pfx); + if (left_ext == NULL && right_ext == NULL) { + /* only have data - set ext_path to zero-length terminal LC node */ + lc_init_flags (&ext_path->lc_node, 1, 0); + ext_path->lc_node.prefix[0] = npbyte; + ext_path->lc_node.ptr.data = *data_p; + btrie->n_lc_nodes++; + } + else if (data_p || (left_ext && right_ext)) { + /* have at least two of data, left_ext, right_ext + * ext_path must be a full TBM node */ + init_tbm_node (btrie, ext_path, pos + TBM_STRIDE, + npbyte, data_p, left_ext, right_ext); + } + else if (left_ext) { + /* have only left_ext, insert length-one LC node */ + insert_lc_node (btrie, ext_path, pos + TBM_STRIDE, + npbyte, 0, left_ext); + } + else { + /* have only right_ext, insert length-one LC node */ + insert_lc_node (btrie, ext_path, pos + TBM_STRIDE, + npbyte, 1, right_ext); + } + } + } + btrie->n_tbm_nodes--; + free_nodes (btrie, child->tbm_node.ptr.children, + count_bits (child->tbm_node.ext_bm), + count_bits (child->tbm_node.int_bm)); + } + } + + assert(count_bits (int_bm) == ndata); + assert(count_bits (ext_bm) == nchildren); + + node->ptr.children = alloc_nodes (btrie, nchildren, ndata); + memcpy(node->ptr.data_end - (int )ndata, data, ndata * sizeof(data[0])); + memcpy(node->ptr.children, children, nchildren * sizeof(children[0])); + node->ext_bm = ext_bm; + node->int_bm = int_bm; + btrie->n_tbm_nodes++; +} + +static enum btrie_result add_to_trie(struct btrie *btrie, node_t *node, + unsigned pos, const btrie_oct_t *prefix, unsigned len, const void *data) +{ + for (;;) { + if (is_lc_node (node)) { + struct lc_node *lc_node = &node->lc_node; + unsigned end = pos + lc_len (lc_node); + unsigned cbits = common_prefix (prefix + lc_shift (pos), + lc_node->prefix, (len < end ? len : end) - lc_base (pos)); + unsigned clen = lc_base (pos) + cbits; /* position of first mismatch */ + + if (clen == end && !lc_is_terminal (lc_node)) { + /* matched entire prefix of LC node, proceed to child */ + assert(lc_len (lc_node) > 0); + node = lc_node->ptr.child; + pos = end; + } + else if (clen == end && len == end && lc_is_terminal (lc_node)) { + /* exact match for terminal node - already have data for prefix */ + return BTRIE_DUPLICATE_PREFIX; + } + else { + assert(clen < end || (lc_is_terminal (lc_node) && len > end)); + /* Need to insert new TBM node at clen */ + if (clen > pos) { + split_lc_node (btrie, lc_node, pos, clen - pos); + node = lc_node->ptr.child; + assert(is_lc_node (node)); + pos = clen; + } + convert_lc_node (btrie, &node->lc_node, pos); + } + } + else if (is_empty_node (node)) { + /* at empty TBM node - just replace with terminal LC node */ + init_terminal_node (btrie, node, pos, prefix, len, data); + btrie->n_entries++; + btrie->n_tbm_nodes--; + return BTRIE_OKAY; + } + else { + struct tbm_node *tbm_node = &node->tbm_node; + unsigned end = pos + TBM_STRIDE; + + if (len < end) { + unsigned plen = len - pos; + unsigned pfx = extract_bits (prefix, pos, plen); + + if (tbm_data_p (tbm_node, pfx, plen) != NULL) + return BTRIE_DUPLICATE_PREFIX; /* prefix already has data */ + else { + tbm_insert_data (btrie, tbm_node, pfx, plen, data); + btrie->n_entries++; + return BTRIE_OKAY; + } + } + else { + unsigned pfx = extract_bits (prefix, pos, TBM_STRIDE); + + /* follow extending path */ + node = tbm_ext_path (tbm_node, pfx); + if (node == NULL) + node = tbm_insert_ext_path (btrie, tbm_node, pfx); + pos = end; + } + } + } +} + +static const void * +search_trie(const node_t *node, unsigned pos, const btrie_oct_t *prefix, + unsigned len) +{ + /* remember last TBM node seen with internal data */ + const struct tbm_node *int_node = 0; + unsigned int_pfx = 0, int_plen = 0; + + while (node) { + if (is_lc_node (node)) { + const struct lc_node *lc_node = &node->lc_node; + unsigned end = pos + lc_len (lc_node); + if (len < end) + break; + if (!prefixes_equal (prefix + lc_shift (pos), lc_node->prefix, + end - lc_base (pos))) + break; + + if (lc_is_terminal (lc_node)) + return lc_node->ptr.data; /* found terminal node */ + + pos = end; + node = lc_node->ptr.child; + } + else { + const struct tbm_node *tbm_node = &node->tbm_node; + unsigned end = pos + TBM_STRIDE; + if (len < end) { + unsigned plen = len - pos; + unsigned pfx = extract_bits (prefix, pos, plen); + if (has_internal_data (tbm_node, pfx, plen)) { + int_node = tbm_node; + int_pfx = pfx; + int_plen = plen; + } + break; + } + else { + unsigned pfx = extract_bits (prefix, pos, TBM_STRIDE); + if (has_internal_data (tbm_node, pfx >> 1, TBM_STRIDE - 1)) { + int_node = tbm_node; + int_pfx = pfx >> 1; + int_plen = TBM_STRIDE - 1; + } + pos = end; + node = tbm_ext_path (tbm_node, pfx); + } + } + } + + if (int_node) { + const void **data_p = tbm_data_p (int_node, int_pfx, int_plen); + while (data_p == NULL) { + assert(int_plen > 0); + int_pfx >>= 1; + int_plen--; + data_p = tbm_data_p (int_node, int_pfx, int_plen); + } + return *data_p; + } + + return NULL; +} + +struct btrie * +btrie_init(rspamd_mempool_t *mp) +{ + struct btrie *btrie; + + if (!(btrie = rspamd_mempool_alloc (mp, sizeof(*btrie)))) + return NULL; + memset(btrie, 0, sizeof(*btrie)); + btrie->mp = mp; + btrie->alloc_total = sizeof(*btrie); + + /* count the empty root node */ + btrie->n_tbm_nodes = 1; + + return btrie; +} + +enum btrie_result btrie_add_prefix(struct btrie *btrie, + const btrie_oct_t *prefix, unsigned len, const void *data) +{ + enum btrie_result rv; + if ((rv = setjmp (btrie->exception)) != 0) + return rv; /* out of memory */ + + return add_to_trie (btrie, &btrie->root, 0, prefix, len, data); +} + +const void * +btrie_lookup(const struct btrie *btrie, const btrie_oct_t *prefix, unsigned len) +{ + return search_trie (&btrie->root, 0, prefix, len); +} + +/**************************************************************** + * + * btrie_stats() - statistics reporting + */ + +#ifdef BTRIE_EXTENDED_STATS + +/* Define BTRIE_EXTENDED_STATS to get extra statistics (including + * trie depth). This statistics require a traversal of the entire trie + * to compute, and so are disabled by default. + */ + +struct stats { + size_t max_depth; + size_t total_depth; +#ifndef NDEBUG + size_t n_lc_nodes; + size_t n_tbm_nodes; + size_t n_entries; + size_t alloc_data; + size_t alloc_waste; +#endif +}; + +static void +node_stats(const node_t *node, size_t depth, struct stats *stats) +{ + if (depth > stats->max_depth) + stats->max_depth = depth; + stats->total_depth += depth; + + if (is_lc_node(node)) { +#ifndef NDEBUG + stats->n_lc_nodes++; +#endif + if (!lc_is_terminal(&node->lc_node)) + node_stats(node->lc_node.ptr.child, depth + 1, stats); +#ifndef NDEBUG + else + stats->n_entries++; +#endif + } + else { + unsigned i; + unsigned nchildren = count_bits(node->tbm_node.ext_bm); +#ifndef NDEBUG + unsigned ndata = count_bits(node->tbm_node.int_bm); + + stats->n_tbm_nodes++; + stats->n_entries += ndata; + stats->alloc_data += ndata * sizeof(void *); + stats->alloc_waste += (ndata % 2) * sizeof(void *); +#endif + for (i = 0; i < nchildren; i++) + node_stats(&node->tbm_node.ptr.children[i], depth + 1, stats); + } +} +#endif /* BTRIE_EXTENDED_STATS */ + +#ifndef NDEBUG +static size_t count_free(const struct btrie *btrie) +{ + size_t total = 0; + unsigned sz; + for (sz = 1; sz <= MAX_CHILD_ARRAY_LEN; sz++) { + const struct free_hunk *free = btrie->free_list[sz - 1]; + size_t n; + for (n = 0; free; n++) + free = free->next; + total += sz * n; + } + return total * sizeof(node_t); +} +#endif /* not NDEBUG */ + +const char * +btrie_stats(const struct btrie *btrie) +{ + static char buf[128]; + size_t n_nodes = btrie->n_lc_nodes + btrie->n_tbm_nodes; + size_t alloc_free = (btrie->alloc_total + sizeof(node_t) /* do not double-count the root node */ + - n_nodes * sizeof(node_t) - btrie->alloc_data - btrie->alloc_waste + - sizeof(*btrie)); +#ifdef BTRIE_EXTENDED_STATS + struct stats stats; + double average_depth; + + memset(&stats, 0, sizeof(stats)); + node_stats(&btrie->root, 0, &stats); + average_depth = (double)stats.total_depth / n_nodes; + +#ifndef NDEBUG + /* check the node counts */ + assert(stats.n_lc_nodes == btrie->n_lc_nodes); + assert(stats.n_tbm_nodes == btrie->n_tbm_nodes); + assert(stats.n_entries == btrie->n_entries); + assert(stats.alloc_data == btrie->alloc_data); + assert(stats.alloc_waste == btrie->alloc_waste); +#endif /* not NDEBUG */ +#endif /* BTRIE_EXTENDED_STATS */ + +#ifndef NDEBUG + /* check that we haven't lost any memory */ + assert(alloc_free == count_free (btrie)); +#endif + +#ifdef BTRIE_DEBUG_ALLOC + dump_alloc_hist(btrie); +#endif + + +#ifdef BTRIE_EXTENDED_STATS + snprintf(buf, sizeof(buf), + "ents=%lu tbm=%lu lc=%lu mem=%.0fk free=%lu waste=%lu" + " depth=%.1f/%lu" + ,(long unsigned)btrie->n_entries, (long unsigned)btrie->n_tbm_nodes, + (long unsigned)btrie->n_lc_nodes, (double)btrie->alloc_total / 1024, + (long unsigned)alloc_free, (long unsigned)btrie->alloc_waste + , average_depth, (long unsigned)stats.max_depth); +#else + snprintf(buf, sizeof(buf), + "ents=%lu tbm=%lu lc=%lu mem=%.0fk free=%lu waste=%lu" + ,(long unsigned)btrie->n_entries, (long unsigned)btrie->n_tbm_nodes, + (long unsigned)btrie->n_lc_nodes, (double)btrie->alloc_total / 1024, + (long unsigned)alloc_free, (long unsigned)btrie->alloc_waste + ); +#endif + buf[sizeof(buf) - 1] = '\0'; + return buf; +} + +/****************************************************************/ + +#ifndef NO_MASTER_DUMP + +struct walk_context +{ + btrie_walk_cb_t *callback; + void *user_data; + + btrie_oct_t prefix[(BTRIE_MAX_PREFIX + 7) / 8]; +}; + +static void +walk_node(const node_t *node, unsigned pos, struct walk_context *ctx); + +static void walk_tbm_node(const struct tbm_node *node, unsigned pos, + unsigned pfx, unsigned plen, struct walk_context *ctx) +{ + btrie_oct_t *prefix = ctx->prefix; + int pbyte = pos / 8; + btrie_oct_t pbit = 0x80 >> (pos % 8); + const void **data_p = tbm_data_p (node, pfx, plen); + + if (pos >= BTRIE_MAX_PREFIX) { + /* This can/should not happen, but don't overwrite buffers if it does. */ + return; + } + + if (data_p) + ctx->callback (prefix, pos, *data_p, 0, ctx->user_data); + + /* walk children */ + if (plen < TBM_STRIDE - 1) { + /* children are internal prefixes in same node */ + walk_tbm_node (node, pos + 1, pfx << 1, plen + 1, ctx); + prefix[pbyte] |= pbit; + walk_tbm_node (node, pos + 1, (pfx << 1) + 1, plen + 1, ctx); + prefix[pbyte] &= ~pbit; + } + else { + /* children are extending paths */ + const node_t *ext_path; + if ((ext_path = tbm_ext_path (node, pfx << 1)) != NULL) + walk_node (ext_path, pos + 1, ctx); + if ((ext_path = tbm_ext_path (node, (pfx << 1) + 1)) != NULL) { + prefix[pbyte] |= pbit; + walk_node (ext_path, pos + 1, ctx); + prefix[pbyte] &= ~pbit; + } + } + + if (data_p) + ctx->callback (prefix, pos, *data_p, 1, ctx->user_data); +} + +static void walk_lc_node(const struct lc_node *node, unsigned pos, + struct walk_context *ctx) +{ + btrie_oct_t *prefix = ctx->prefix; + unsigned end = pos + lc_len (node); + btrie_oct_t save_prefix = prefix[lc_shift (pos)]; + + if (end > BTRIE_MAX_PREFIX) { + /* This can/should not happen, but don't overwrite buffers if it does. */ + return; + } + + /* construct full prefix to node */ + memcpy(&prefix[lc_shift (pos)], node->prefix, lc_bytes (node, pos)); + if (end % 8) + prefix[end / 8] &= high_bits (end % 8); + + if (lc_is_terminal (node)) { + ctx->callback (prefix, end, node->ptr.data, 0, ctx->user_data); + ctx->callback (prefix, end, node->ptr.data, 1, ctx->user_data); + } + else + walk_node (node->ptr.child, end, ctx); + + prefix[lc_shift (pos)] = save_prefix; /* restore parents prefix */ + if (lc_bytes (node, pos) > 1) + memset(&prefix[lc_shift (pos) + 1], 0, lc_bytes (node, pos) - 1); +} + +static void walk_node(const node_t *node, unsigned pos, + struct walk_context *ctx) +{ + if (is_lc_node (node)) + walk_lc_node (&node->lc_node, pos, ctx); + else + walk_tbm_node (&node->tbm_node, pos, 0, 0, ctx); +} + +/* walk trie in lexicographical order + * + * calls callback twice (once preorder, once postorder) at each prefix + */ +void btrie_walk(const struct btrie *btrie, btrie_walk_cb_t *callback, + void *user_data) +{ + struct walk_context ctx; + + memset(&ctx, 0, sizeof(ctx)); + ctx.callback = callback; + ctx.user_data = user_data; + + walk_node (&btrie->root, 0, &ctx); +} + +#endif /* not NO_MASTER_DUMP */ + + +#ifdef TEST +/***************************************************************** + * + * Unit tests + * + */ +#include <stdio.h> + +#ifndef UNUSED +# define UNUSED __attribute__((unused)) +#endif + +/* bogus replacements mp_alloc for running self-tests */ +void * +mp_alloc(UNUSED struct mempool *mp, unsigned sz, UNUSED int align) +{ + return malloc(sz); +} + +#if 0 +# define PASS(name) puts("OK " name) +#else +# define PASS(name) fputs(".", stdout); fflush(stdout) +#endif + +const char * pgm_name = "???"; + +static void +test_struct_node_packing() +{ + node_t node; + + assert(sizeof(struct tbm_node) == 2 * sizeof(void *)); + assert(sizeof(struct lc_node) == 2 * sizeof(void *)); + assert(sizeof(node_t) == 2 * sizeof(void *)); + + /* The lc_node bit must be an alias for bit zero of int_bm, since + * that is the only unused bit in the TBM node structure. + */ + memset(&node, 0, sizeof(node)); + assert(node.tbm_node.int_bm == 0); + lc_init_flags(&node.lc_node, 0, 0); + assert(node.tbm_node.int_bm == bit(0)); + + PASS("test_struct_node_packing"); +} + +static void +test_bit() +{ + tbm_bitmap_t ones = ~(tbm_bitmap_t)0; + tbm_bitmap_t high_bit = ones ^ (ones >> 1); + + assert(bit(0) == high_bit); + assert(bit(1) == high_bit >> 1); + assert(bit(8 * sizeof(tbm_bitmap_t) - 1) == 1); + PASS("test_bit"); +} + +static void +test_count_bits() +{ + unsigned max_bits = sizeof(tbm_bitmap_t) * 8; + tbm_bitmap_t ones = ~(tbm_bitmap_t)0; + + assert(count_bits(0) == 0); + assert(count_bits(1) == 1); + assert(count_bits(2) == 1); + assert(count_bits(3) == 2); + assert(count_bits(ones) == max_bits); + assert(count_bits(~1) == max_bits - 1); + + /* count_bits(0x5555....) */ + assert(count_bits(ones / 3) == max_bits / 2); + /* count_bits(0x3333...) */ + assert(count_bits(ones / 5) == max_bits / 2); + /* count_bits(0x0f0f...) */ + assert(count_bits(ones / 17) == max_bits / 2); + /* count_bits(0x1010...) */ + assert(count_bits(ones / 255) == max_bits / 8); + + PASS("test_count_bits"); +} + +static void +test_count_bits_before() +{ + unsigned max_bits = sizeof(tbm_bitmap_t) * 8; + tbm_bitmap_t ones = ~(tbm_bitmap_t)0; + unsigned i; + + for (i = 0; i < max_bits; i++) { + assert(count_bits_before(0, i) == 0); + assert(count_bits_before(ones, i) == i); + } + + PASS("test_count_bits_before"); +} + +static void +test_count_bits_from() +{ + unsigned max_bits = sizeof(tbm_bitmap_t) * 8; + tbm_bitmap_t ones = ~(tbm_bitmap_t)0; + unsigned i; + + for (i = 0; i < max_bits; i++) { + assert(count_bits_from(0, i) == 0); + assert(count_bits_from(ones, i) == max_bits - i); + } + + PASS("test_count_bits_from"); +} + +static void +test_extract_bits() +{ + static btrie_oct_t prefix[] = {0xff, 0x55, 0xaa, 0x00}; + unsigned i; + + for (i = 0; i < 32; i++) + assert(extract_bits(prefix, i, 0) == 0); + + for (i = 0; i < 8; i++) + assert(extract_bits(prefix, i, 1) == 1); + for (i = 8; i < 16; i++) + assert(extract_bits(prefix, i, 1) == i % 2); + for (i = 16; i < 24; i++) + assert(extract_bits(prefix, i, 1) == (i + 1) % 2); + for (i = 24; i < 32; i++) + assert(extract_bits(prefix, i, 1) == 0); + + assert(extract_bits(prefix, 2, 6) == 0x3f); + assert(extract_bits(prefix, 3, 6) == 0x3e); + assert(extract_bits(prefix, 4, 6) == 0x3d); + assert(extract_bits(prefix, 5, 6) == 0x3a); + assert(extract_bits(prefix, 6, 6) == 0x35); + assert(extract_bits(prefix, 7, 6) == 0x2a); + assert(extract_bits(prefix, 8, 6) == 0x15); + + PASS("test_extract_bits"); +} + +static void +test_high_bits() +{ + assert(high_bits(0) == 0x00); + assert(high_bits(1) == 0x80); + assert(high_bits(2) == 0xc0); + assert(high_bits(3) == 0xe0); + assert(high_bits(4) == 0xf0); + assert(high_bits(5) == 0xf8); + assert(high_bits(6) == 0xfc); + assert(high_bits(7) == 0xfe); + assert(high_bits(8) == 0xff); + PASS("test_high_bits"); +} + +static void +test_prefixes_equal() +{ + btrie_oct_t prefix1[LC_BYTES_PER_NODE]; + btrie_oct_t prefix2[LC_BYTES_PER_NODE]; + unsigned i; + memset(prefix1, 0xaa, LC_BYTES_PER_NODE); + memset(prefix2, 0xaa, LC_BYTES_PER_NODE); + + for (i = 0; i < 8 * LC_BYTES_PER_NODE; i++) { + assert(prefixes_equal(prefix1, prefix2, i)); + prefix1[i / 8] ^= 1 << (7 - i % 8); + assert(!prefixes_equal(prefix1, prefix2, 8 * LC_BYTES_PER_NODE)); + assert(prefixes_equal(prefix1, prefix2, i)); + if (i + 1 < 8 * LC_BYTES_PER_NODE) + assert(!prefixes_equal(prefix1, prefix2, i + 1)); + prefix1[i / 8] ^= 1 << (7 - i % 8); + } + PASS("test_prefixes_equal"); +} + +static void +test_common_prefix() +{ + btrie_oct_t prefix1[LC_BYTES_PER_NODE]; + btrie_oct_t prefix2[LC_BYTES_PER_NODE]; + unsigned i; + memset(prefix1, 0x55, LC_BYTES_PER_NODE); + memset(prefix2, 0x55, LC_BYTES_PER_NODE); + + for (i = 0; i < 8 * LC_BYTES_PER_NODE; i++) { + assert(common_prefix(prefix1, prefix2, i) == i); + prefix1[i / 8] ^= 1 << (7 - i % 8); + assert(common_prefix(prefix1, prefix2, 8 * LC_BYTES_PER_NODE) == i); + if (i + 1 < 8 * LC_BYTES_PER_NODE) + assert(common_prefix(prefix1, prefix2, i+1) == i); + prefix1[i / 8] ^= 1 << (7 - i % 8); + } + PASS("test_common_prefix"); +} + +static void +test_base_index() +{ + assert(base_index(0,0) == 1); + assert(base_index(0,1) == 2); + assert(base_index(1,1) == 3); + assert(base_index(0,2) == 4); + assert(base_index(1,2) == 5); + assert(base_index(2,2) == 6); + assert(base_index(3,2) == 7); + PASS("test_base_index"); +} + +static void +test_has_internal_data() +{ + struct tbm_node node; + unsigned plen, pfx, bi; + for (plen = 0; plen < TBM_STRIDE; plen++) { + for (pfx = 0; pfx < 1U << plen; pfx++) { + tbm_bitmap_t ancestor_mask = 0; + for (bi = base_index(pfx, plen); bi; bi >>= 1) { + node.int_bm = bit(bi); + ancestor_mask |= bit(bi); + assert(has_internal_data(&node, pfx, plen)); + } + node.int_bm = ~ancestor_mask; + assert(!has_internal_data(&node, pfx, plen)); + } + } + PASS("test_has_internal_data"); +} + +/****************************************************************/ +static const btrie_oct_t numbered_bytes[] = { + 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, + 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, + 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, + 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, + 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, + 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, + 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, + 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, +}; + +static void +check_non_terminal_lc_node(struct lc_node *node, unsigned len) +{ + assert(is_lc_node((node_t *)node)); + assert(!lc_is_terminal(node)); + assert(lc_len(node) == len); +} + +static void +check_terminal_lc_node(struct lc_node *node, unsigned len, const void *data) +{ + assert(is_lc_node((node_t *)node)); + assert(lc_is_terminal(node)); + assert(lc_len(node) == len); + assert(node->ptr.data == data); +} + +static void +test_init_terminal_node() +{ + struct btrie *btrie = btrie_init(NULL); + const void *data = (void *)0xdeadbeef; + node_t node; + struct lc_node *head = &node.lc_node; + + init_terminal_node(btrie, &node, 0, + numbered_bytes, 8 * LC_BYTES_PER_NODE, data); + check_terminal_lc_node(head, 8 * LC_BYTES_PER_NODE, data); + assert(memcmp(head->prefix, numbered_bytes, LC_BYTES_PER_NODE) == 0); + + init_terminal_node(btrie, &node, 7, + numbered_bytes, 8 * LC_BYTES_PER_NODE, data); + check_terminal_lc_node(head, 8 * LC_BYTES_PER_NODE - 7, data); + assert(memcmp(head->prefix, numbered_bytes, LC_BYTES_PER_NODE) == 0); + + init_terminal_node(btrie, &node, 0, + numbered_bytes, 2 * 8 * LC_BYTES_PER_NODE, data); + check_non_terminal_lc_node(head, 8 * LC_BYTES_PER_NODE); + assert(memcmp(head->prefix, numbered_bytes, LC_BYTES_PER_NODE) == 0); + { + struct lc_node *child = &head->ptr.child->lc_node; + check_terminal_lc_node(child, 8 * LC_BYTES_PER_NODE, data); + assert(memcmp(child->prefix, &numbered_bytes[LC_BYTES_PER_NODE], + LC_BYTES_PER_NODE) == 0); + } + + init_terminal_node(btrie, &node, 15, + numbered_bytes, 8 * LC_BYTES_PER_NODE + 15, data); + check_non_terminal_lc_node(head, 8 * LC_BYTES_PER_NODE - 7); + assert(memcmp(head->prefix, &numbered_bytes[1], LC_BYTES_PER_NODE) == 0); + { + struct lc_node *child = &head->ptr.child->lc_node; + check_terminal_lc_node(child, 7, data); + assert(child->prefix[0] == numbered_bytes[LC_BYTES_PER_NODE + 1]); + } + + PASS("test_init_terminal_node"); +} + +static void +test_coalesce_lc_node() +{ + struct btrie *btrie = btrie_init(NULL); + const void *data = (void *)0xdeadbeef; + node_t node; + struct lc_node *head = &node.lc_node; + + /* test merging */ + init_terminal_node(btrie, &node, 0, + numbered_bytes, 8 * (LC_BYTES_PER_NODE + 1), data); + check_non_terminal_lc_node(head, LC_BYTES_PER_NODE * 8); + lc_add_to_len(head, -8); + coalesce_lc_node(btrie, head, 8); + check_terminal_lc_node(head, LC_BYTES_PER_NODE * 8, data); + assert(head->prefix[LC_BYTES_PER_NODE - 1] + == numbered_bytes[LC_BYTES_PER_NODE]); + + /* test bit stealing */ + init_terminal_node(btrie, &node, 0, + numbered_bytes, 8 * (2 * LC_BYTES_PER_NODE), data); + check_non_terminal_lc_node(head, LC_BYTES_PER_NODE * 8); + lc_add_to_len(head, -15); + coalesce_lc_node(btrie, head, 15); + check_non_terminal_lc_node(head, LC_BYTES_PER_NODE * 8 - 7); + assert(memcmp(head->prefix, numbered_bytes, LC_BYTES_PER_NODE - 1) == 0); + assert(head->prefix[LC_BYTES_PER_NODE - 1] + == numbered_bytes[LC_BYTES_PER_NODE]); + { + struct lc_node *child = &head->ptr.child->lc_node; + check_terminal_lc_node(child, 8 * (LC_BYTES_PER_NODE - 1), data); + assert(memcmp(child->prefix, &numbered_bytes[LC_BYTES_PER_NODE + 1], + LC_BYTES_PER_NODE - 1) == 0); + } + + PASS("test_coalesce_lc_node"); +} + +static void +test_shorten_lc_node() +{ + struct btrie *btrie = btrie_init(NULL); + const void *data = (void *)0xdeadbeef; + node_t node, shorter; + + /* test shorten without shift */ + init_terminal_node(btrie, &node, 0, + numbered_bytes, 8 * LC_BYTES_PER_NODE, data); + memset(shorter.lc_node.prefix, 0xff, LC_BYTES_PER_NODE); + shorten_lc_node(btrie, &shorter, 7, &node.lc_node, 0); + check_terminal_lc_node(&shorter.lc_node, LC_BYTES_PER_NODE * 8 - 7, data); + assert(memcmp(shorter.lc_node.prefix, numbered_bytes, LC_BYTES_PER_NODE) + == 0); + + /* test shorten with shift */ + init_terminal_node(btrie, &node, 7, + numbered_bytes, 8 * LC_BYTES_PER_NODE, data); + memset(shorter.lc_node.prefix, 0xff, LC_BYTES_PER_NODE); + shorten_lc_node(btrie, &shorter, 9, &node.lc_node, 7); + check_terminal_lc_node(&shorter.lc_node, LC_BYTES_PER_NODE * 8 - 9, data); + assert(memcmp(shorter.lc_node.prefix, &numbered_bytes[1], + LC_BYTES_PER_NODE - 1) == 0); + + { + /* test child stealing */ + struct lc_node head; + node_t tail, shorter; + + lc_init_flags(&head, 0, 7); + head.ptr.child = &tail; + init_empty_node(btrie, &tail); + + shorten_lc_node(btrie, &shorter, 7, &head, 0); + assert(is_empty_node(&shorter)); + } + + PASS("test_shorten_lc_node"); +} + +static void +test_split_lc_node() +{ + struct btrie *btrie = btrie_init(NULL); + const void *data = (void *)0xdeadbeef; + struct lc_node node; + + init_terminal_node(btrie, (node_t *)&node, 1, numbered_bytes, 25, data); + split_lc_node(btrie, &node, 1, 8); + check_non_terminal_lc_node(&node, 8); + check_terminal_lc_node(&node.ptr.child->lc_node, 16, data); + + /* test conversion of terminal to non-terminal */ + init_terminal_node(btrie, (node_t *)&node, 7, numbered_bytes, 10, data); + split_lc_node(btrie, &node, 7, 3); + check_non_terminal_lc_node(&node, 3); + check_terminal_lc_node(&node.ptr.child->lc_node, 0, data); + + PASS("test_split_lc_node"); +} + +static void +test_convert_lc_node_1() +{ + struct btrie *btrie = btrie_init(NULL); + const void *data = (void *)0xdeadbeef; + struct lc_node head; + + /* test tail is left */ + lc_init_flags(&head, 0, 1); + head.prefix[0] = 0; + head.ptr.child = alloc_nodes(btrie, 1, 0); + init_terminal_node(btrie, head.ptr.child, 1, numbered_bytes, 1, data); + convert_lc_node_1(btrie, &head, 0); + { + node_t *result = (node_t *)&head; + assert(is_tbm_node(result)); + assert(result->tbm_node.ext_bm == 0); + assert(result->tbm_node.int_bm == bit(base_index(0, 1))); + assert(*tbm_data_p(&result->tbm_node, 0, 1) == data); + } + + /* test tail is right */ + lc_init_flags(&head, 0, 1); + head.prefix[0] = 1; + head.ptr.child = alloc_nodes(btrie, 1, 0); + init_terminal_node(btrie, head.ptr.child, 8, numbered_bytes, 10, data); + convert_lc_node_1(btrie, &head, 7); + { + node_t *result = (node_t *)&head; + assert(is_tbm_node(result)); + assert(result->tbm_node.ext_bm == 0); + assert(result->tbm_node.int_bm == bit(base_index(4, 3))); + assert(*tbm_data_p(&result->tbm_node, 4, 3) == data); + } + + PASS("test_convert_lc_node_1"); +} + +static void +test_convert_lc_node() +{ + struct btrie *btrie = btrie_init(NULL); + const void *data = (void *)0xdeadbeef; + node_t node; + + /* if (len >= TBM_STRIDE) */ + init_terminal_node(btrie, &node, 7, numbered_bytes, TBM_STRIDE + 7, data); + convert_lc_node(btrie, &node.lc_node, 7); + assert(is_tbm_node(&node)); + assert(node.tbm_node.ext_bm == bit(0)); + assert(node.tbm_node.int_bm == 0); + check_terminal_lc_node(&tbm_ext_path(&node.tbm_node, 0)->lc_node, 0, data); + + /* if (lc_is_terminal(node)) */ + init_terminal_node(btrie, &node, 0, numbered_bytes, 0, data); + convert_lc_node(btrie, &node.lc_node, 0); + assert(is_tbm_node(&node)); + assert(node.tbm_node.ext_bm == 0); + assert(node.tbm_node.int_bm == bit(base_index(0, 0))); + assert(*tbm_data_p(&node.tbm_node, 0, 0) == data); + + /* else */ + lc_init_flags(&node.lc_node, 0, TBM_STRIDE - 1); + node.lc_node.prefix[0] = 0; + node.lc_node.ptr.child = alloc_nodes(btrie, 1, 0); + init_empty_node(btrie, node.lc_node.ptr.child); + tbm_insert_data(btrie, &node.lc_node.ptr.child->tbm_node, 0, 0, data); + + convert_lc_node(btrie, &node.lc_node, 0); + assert(is_tbm_node(&node)); + assert(node.tbm_node.ext_bm == 0); + assert(node.tbm_node.int_bm == bit(base_index(0, TBM_STRIDE - 1))); + assert(*tbm_data_p(&node.tbm_node, 0, TBM_STRIDE - 1) == data); + + PASS("test_convert_lc_node"); +} + +static void +test_insert_lc_node() +{ + struct btrie *btrie = btrie_init(NULL); + const void *data = (void *)0xdeadbeef; + node_t node, tail; + + /* test optimized case, last_bit == 0 */ + init_terminal_node(btrie, &tail, 9, numbered_bytes, 17, data); + insert_lc_node(btrie, &node, 8, 0, 0, &tail); + check_terminal_lc_node(&node.lc_node, 9, data); + assert(memcmp(node.lc_node.prefix, &numbered_bytes[1], 2) == 0); + + /* test optimized case, last_bit == 1 */ + init_terminal_node(btrie, &tail, 7, &numbered_bytes[0x12], 15, data); + insert_lc_node(btrie, &node, 6, 0x10, 1, &tail); + check_terminal_lc_node(&node.lc_node, 9, data); + assert(node.lc_node.prefix[0] == 0x12); + assert(node.lc_node.prefix[1] == 0x13); + + /* test with shift */ + init_terminal_node(btrie, &tail, 0, numbered_bytes, 8, data); + insert_lc_node(btrie, &node, 7, 0x40, 1, &tail); + check_terminal_lc_node(&node.lc_node, 9, data); + assert(node.lc_node.prefix[0] == 0x41); + assert(node.lc_node.prefix[1] == numbered_bytes[0]); + + /* test with TBM node */ + init_empty_node(btrie, &tail); + insert_lc_node(btrie, &node, 6, 0x40, 0, &tail); + check_non_terminal_lc_node(&node.lc_node, 1); + assert(is_tbm_node(node.lc_node.ptr.child)); + + PASS("test_insert_lc_node"); +} + +static void +test_next_pbyte() +{ + assert(next_pbyte(0xff, 0, 1) == 0x80 >> (TBM_STRIDE - 1)); + assert(next_pbyte(0xff, 1, 1) == (0x80 | (0x80 >> TBM_STRIDE))); + assert(next_pbyte(0xff, 2, 1) == (0xc0 | (0x80 >> (TBM_STRIDE + 1)))); + assert(next_pbyte(0xff, 8 - TBM_STRIDE, 1) == 0); + assert(next_pbyte(0xff, 9 - TBM_STRIDE, 1) == 0x80); + + PASS("test_next_pbyte"); +} + +static void +test_init_tbm_node() +{ + struct btrie *btrie = btrie_init(NULL); + const void *data = (void *)0xdeadbeef; + unsigned lr; + node_t node; + + /* test root data */ + init_tbm_node(btrie, &node, 0, 0, &data, NULL, NULL); + assert(is_tbm_node(&node)); + assert(node.tbm_node.ext_bm == 0); + assert(node.tbm_node.int_bm == bit(base_index(0, 0))); + assert(*tbm_data_p(&node.tbm_node, 0, 0) == data); + + for (lr = 0; lr < 2; lr++) { + node_t child; + node_t *left = lr ? NULL : &child; + node_t *right = lr ? &child : NULL; + unsigned base = lr ? (1U << (TBM_STRIDE - 1)) : 0; + unsigned pfx; + + /* test with long LC node child */ + init_terminal_node(btrie, &child, 1, numbered_bytes, TBM_STRIDE + 1, data); + init_tbm_node(btrie, &node, 0, 0, NULL, left, right); + assert(is_tbm_node(&node)); + assert(node.tbm_node.ext_bm == bit(base)); + assert(node.tbm_node.int_bm == 0); + check_terminal_lc_node(&tbm_ext_path(&node.tbm_node, base)->lc_node, + 1, data); + + /* test with short LC node children */ + init_terminal_node(btrie, &child, 1, numbered_bytes, TBM_STRIDE - 1, data); + init_tbm_node(btrie, &node, 0, 0, NULL, left, right); + assert(is_tbm_node(&node)); + assert(node.tbm_node.ext_bm == 0); + assert(node.tbm_node.int_bm == bit(base_index(base >> 1, TBM_STRIDE-1))); + assert(*tbm_data_p(&node.tbm_node, base >> 1, TBM_STRIDE-1) == data); + + /* construct TBM node with all eight combinations of having data, + * left_ext and/or right_ext in its extending paths */ + init_empty_node(btrie, &child); + for (pfx = 0; pfx < 8; pfx++) { + if (pfx & 1) + tbm_insert_data(btrie, &child.tbm_node, pfx, TBM_STRIDE - 1, data); + if (pfx & 2) { + btrie_oct_t prefix0 = 0; + init_terminal_node(btrie, + tbm_insert_ext_path(btrie, &child.tbm_node, 2*pfx), + TBM_STRIDE + 1, + &prefix0, TBM_STRIDE + 2, data); + } + if (pfx & 4) { + btrie_oct_t prefix0 = 0x80 >> TBM_STRIDE; + init_terminal_node(btrie, + tbm_insert_ext_path(btrie, &child.tbm_node, 2*pfx+1), + TBM_STRIDE + 1, + &prefix0, TBM_STRIDE + 3, data); + } + } + init_tbm_node(btrie, &node, 0, 0, NULL, left, right); + for (pfx = 0; pfx < 8; pfx++) { + unsigned base = lr ? (1U << (TBM_STRIDE - 1)) : 0; + node_t *ext_path = tbm_ext_path(&node.tbm_node, base + pfx); + if (pfx == 0) + assert(ext_path == NULL); + else if (pfx == 1) + check_terminal_lc_node(&ext_path->lc_node, 0, data); + else if (pfx == 2) { + check_terminal_lc_node(&ext_path->lc_node, 2, data); + assert(ext_path->lc_node.prefix[0] == 0); + } + else if (pfx == 4) { + check_terminal_lc_node(&ext_path->lc_node, 3, data); + assert(ext_path->lc_node.prefix[0] == (0x80 >> TBM_STRIDE)); + } + else { + tbm_bitmap_t int_bm = 0; + assert(is_tbm_node(ext_path)); + if (pfx & 1) { + int_bm |= bit(base_index(0, 0)); + assert(*tbm_data_p(&ext_path->tbm_node, 0, 0) == data); + } + if (pfx & 2) { + int_bm |= bit(base_index(0, 2)); + assert(*tbm_data_p(&ext_path->tbm_node, 0, 2) == data); + } + if (pfx & 4) { + int_bm |= bit(base_index(4, 3)); + assert(*tbm_data_p(&ext_path->tbm_node, 4, 3) == data); + } + assert(ext_path->tbm_node.int_bm == int_bm); + } + } + } + + PASS("test_init_tbm_node"); +} + +static void +test_add_to_trie() +{ + struct btrie *btrie = btrie_init(NULL); + const void *data = (void *)0xdeadbeef; + enum btrie_result result; + unsigned pfx, plen; + node_t root; + + /* test initial insertion */ + init_empty_node(btrie, &root); + result = add_to_trie(btrie, &root, 0, + numbered_bytes, 8 * 2 * LC_BYTES_PER_NODE, data); + assert(result == BTRIE_OKAY); + check_non_terminal_lc_node(&root.lc_node, 8 * LC_BYTES_PER_NODE); + check_terminal_lc_node(&root.lc_node.ptr.child->lc_node, + 8 * LC_BYTES_PER_NODE, data); + + /* test can follow LC node to tail, and then detect duplicate prefix */ + result = add_to_trie(btrie, &root, 0, + numbered_bytes, 8 * 2 * LC_BYTES_PER_NODE, data); + assert(result == BTRIE_DUPLICATE_PREFIX); + + /* test can insert new TBM node within existing LC node */ + result = add_to_trie(btrie, &root, 0, + &numbered_bytes[1], 16, data); + assert(result == BTRIE_OKAY); + check_non_terminal_lc_node(&root.lc_node, 7); + assert(is_tbm_node(root.lc_node.ptr.child)); + + /* test can convert terminal LC node to TBM node */ + init_terminal_node(btrie, &root, 0, numbered_bytes, 12, data); + result = add_to_trie(btrie, &root, 0, numbered_bytes, 24, data); + assert(result == BTRIE_OKAY); + check_non_terminal_lc_node(&root.lc_node, 12); + assert(is_tbm_node(root.lc_node.ptr.child)); + + /* test can insert internal prefix data in TBM node */ + for (plen = 0; plen < TBM_STRIDE; plen++) { + for (pfx = 0; pfx < (1U << plen); pfx++) { + btrie_oct_t prefix0 = plen ? pfx << (8 - plen) : 0; + init_empty_node(btrie, &root); + init_terminal_node(btrie, tbm_insert_ext_path(btrie, &root.tbm_node, 0), + TBM_STRIDE, + numbered_bytes, 8, data); + result = add_to_trie(btrie, &root, 0, &prefix0, plen, data); + assert(result == BTRIE_OKAY); + assert(is_tbm_node(&root)); + assert(root.tbm_node.ext_bm == bit(0)); + assert(root.tbm_node.int_bm == bit(base_index(pfx, plen))); + assert(*tbm_data_p(&root.tbm_node, pfx, plen) == data); + + result = add_to_trie(btrie, &root, 0, &prefix0, plen, data); + assert(result == BTRIE_DUPLICATE_PREFIX); + } + } + + /* test can add extending paths to TBM node */ + for (pfx = 0; pfx < (1U << TBM_STRIDE); pfx++) { + btrie_oct_t prefix0 = pfx << (8 - TBM_STRIDE); + init_empty_node(btrie, &root); + tbm_insert_data(btrie, &root.tbm_node, 0, 0, data); + result = add_to_trie(btrie, &root, 0, &prefix0, 8, data); + assert(result == BTRIE_OKAY); + assert(is_tbm_node(&root)); + assert(root.tbm_node.ext_bm == bit(pfx)); + assert(root.tbm_node.int_bm == bit(base_index(0, 0))); + check_terminal_lc_node(&tbm_ext_path(&root.tbm_node, pfx)->lc_node, + 8 - TBM_STRIDE, data); + + result = add_to_trie(btrie, &root, 0, &prefix0, 8, data); + assert(result == BTRIE_DUPLICATE_PREFIX); + } + + /* test can follow extending path */ + init_empty_node(btrie, &root); + init_terminal_node(btrie, + tbm_insert_ext_path(btrie, &root.tbm_node, 0), TBM_STRIDE, + numbered_bytes, 8, data); + result = add_to_trie(btrie, &root, 0, numbered_bytes, 7, data); + assert(result == BTRIE_OKAY); + assert(root.tbm_node.ext_bm == bit(0)); + assert(root.tbm_node.int_bm == 0); + check_non_terminal_lc_node(&root.tbm_node.ptr.children[0].lc_node, + 7 - TBM_STRIDE); + + PASS("test_add_to_trie"); +} + +static void +test_search_trie() +{ + struct btrie *btrie = btrie_init(NULL); + const void *data01 = (void *)0xdead0001; + const void *data11 = (void *)0xdead0101; + const void *data = (void *)0xdeadbeef; + unsigned plen, pfx; + node_t root; + + /* test can follow chain of LC nodes to an exact match */ + init_empty_node(btrie, &root); + add_to_trie(btrie, &root, 0, + numbered_bytes, 8 * 2 * LC_BYTES_PER_NODE, data); + + assert(search_trie(&root, 0, numbered_bytes, 8 * 2 * LC_BYTES_PER_NODE) + == data); + assert(search_trie(&root, 0, numbered_bytes, 8 * 2 * LC_BYTES_PER_NODE + 1) + == data); + assert(search_trie(&root, 0, numbered_bytes, 8 * 2 * LC_BYTES_PER_NODE - 1) + == NULL); + assert(search_trie(&root, 0, &numbered_bytes[1], 8 * 2 * LC_BYTES_PER_NODE) + == NULL); + + /* test can follow extending path to an exact match */ + for (pfx = 0; pfx < (1U << TBM_STRIDE); pfx++) { + btrie_oct_t prefix0 = pfx << (8 - TBM_STRIDE); + init_empty_node(btrie, &root); + tbm_insert_data(btrie, &root.tbm_node, 0, 1, data01); + tbm_insert_data(btrie, &root.tbm_node, 1, 1, data11); + add_to_trie(btrie, &root, 0, &prefix0, 8, data); + assert(search_trie(&root, 0, &prefix0, 8) == data); + /* test that last matching TBM internal prefix gets picked up */ + if (prefix0 & 0x80) + assert(search_trie(&root, 0, &prefix0, 7) == data11); + else + assert(search_trie(&root, 0, &prefix0, 7) == data01); + prefix0 ^= 1 << (8 - TBM_STRIDE); + if (prefix0 & 0x80) + assert(search_trie(&root, 0, &prefix0, 8) == data11); + else + assert(search_trie(&root, 0, &prefix0, 8) == data01); + } + + /* test finding of TBM internal prefixes */ + init_empty_node(btrie, &root); + tbm_insert_data(btrie, &root.tbm_node, 0, 1, data01); + tbm_insert_data(btrie, &root.tbm_node, 1, 1, data11); + + assert(search_trie(&root, 0, numbered_bytes, 0) == NULL); + for (plen = 1; plen < TBM_STRIDE; plen++) { + for (pfx = 0; pfx < (1U << TBM_STRIDE); pfx++) { + btrie_oct_t prefix0 = pfx << (8 - plen); + if (prefix0 & 0x80) + assert(search_trie(&root, 0, &prefix0, plen) == data11); + else + assert(search_trie(&root, 0, &prefix0, plen) == data01); + } + } + + PASS("test_search_trie"); +} + +static int +unit_tests() +{ + test_struct_node_packing(); + test_bit(); + test_count_bits(); + test_count_bits_before(); + test_count_bits_from(); + test_extract_bits(); + test_high_bits(); + test_prefixes_equal(); + test_common_prefix(); + test_base_index(); + test_has_internal_data(); + + test_init_terminal_node(); + test_coalesce_lc_node(); + test_shorten_lc_node(); + test_split_lc_node(); + test_convert_lc_node_1(); + test_convert_lc_node(); + test_insert_lc_node(); + test_next_pbyte(); + test_init_tbm_node(); + test_add_to_trie(); + test_search_trie(); + + puts("\nOK"); + return 0; +} + +/***************************************************************** + * + * btrie_dump: print out the trie structure (for testing) + * + */ +#define INDENT_FILL "....:....|....:....|....:....|....:....|" + +static void dump_node(const node_t *node, unsigned pos, btrie_oct_t *prefix, + int indent); + +static void +dump_prefix(btrie_oct_t *prefix, unsigned len, int indent, const char *tail) +{ + unsigned i; + + printf("%*.*s0x", indent, indent, INDENT_FILL); + for (i = 0; i < len / 8; i++) + printf("%02x", prefix[i]); + if (len % 8) + printf("%02x", prefix[len / 8] & high_bits(len % 8)); + printf("/%u%s", len, tail); +} + +/* the opposite of extract_bits, sets a short string of bits from integer */ +static void +insert_bits(btrie_oct_t *prefix, unsigned pos, btrie_oct_t pfx, unsigned nbits) +{ + if (nbits != 0) { + unsigned v = (prefix[pos / 8] << 8) + prefix[pos / 8 + 1]; + unsigned mask = (1U << nbits) - 1; + unsigned shift = 16 - (pos % 8) - nbits; + v = (v & ~(mask << shift)) | (pfx << shift); + prefix[pos / 8] = v >> 8; + prefix[pos / 8 + 1] = (btrie_oct_t)v; + } +} + +static void +dump_tbm_node(const struct tbm_node *node, unsigned pos, + btrie_oct_t *prefix, int indent) +{ + unsigned pfx = 0, plen = 0; + + dump_prefix(prefix, pos, indent, " [tbm]\n"); + + for (;;) { + if (plen < TBM_STRIDE) { + const void **data_p = tbm_data_p(node, pfx, plen); + if (data_p) { + insert_bits(prefix, pos, pfx, plen); + dump_prefix(prefix, pos + plen, indent, ""); + printf(" [%u/%u] (%s)\n", pfx, plen, (const char *)*data_p); + } + plen++; + pfx <<= 1; + } + else { + const node_t *ext_path = tbm_ext_path(node, pfx); + if (ext_path) { + insert_bits(prefix, pos, pfx, TBM_STRIDE); + dump_node(ext_path, pos + TBM_STRIDE, prefix, indent + 1); + } + while (pfx & 1) { + if (--plen == 0) + return; + pfx >>= 1; + } + pfx++; + } + } +} + +static void +dump_lc_node(const struct lc_node *node, unsigned pos, + btrie_oct_t *prefix, int indent) +{ + unsigned end = pos + lc_len(node); + btrie_oct_t save_prefix = prefix[lc_shift(pos)]; + + memcpy(&prefix[lc_shift(pos)], node->prefix, lc_bytes(node, pos)); + + if (lc_is_terminal(node)) { + dump_prefix(prefix, end, indent, ""); + printf(" (%s)\n", (const char *)node->ptr.data); + } + else { + dump_prefix(prefix, end, indent, "\n"); + dump_node(node->ptr.child, end, prefix, indent + 1); + } + + prefix[lc_shift(pos)] = save_prefix; + if (lc_bytes(node, pos) > 1) + memset(&prefix[lc_shift(pos) + 1], 0, lc_bytes(node, pos) - 1); +} + +static void +dump_node(const node_t *node, unsigned pos, btrie_oct_t *prefix, int indent) +{ + if (is_lc_node(node)) + dump_lc_node(&node->lc_node, pos, prefix, indent); + else + dump_tbm_node(&node->tbm_node, pos, prefix, indent); +} + +static void +btrie_dump(struct btrie *btrie) +{ + btrie_oct_t prefix[(BTRIE_MAX_PREFIX + 7) / 8]; + + memset(prefix, 0, sizeof(prefix)); + dump_node(&btrie->root, 0, prefix, 0); + puts(btrie_stats(btrie)); +} + +/**************************************************************** + * + * test program - just enough to construct a trie and preform a lookup + * + */ + +#include <arpa/inet.h> + +static int +parse_prefix(const char *arg, btrie_oct_t prefix[16], unsigned *len) +{ + char addrbuf[128]; + return sscanf(arg, "%127[0-9a-fA-F:]/%u", addrbuf, len) == 2 + && inet_pton(AF_INET6, addrbuf, prefix) == 1; +} + +static int +test_btrie(int argc, char *argv[]) +{ + struct btrie *btrie = btrie_init(NULL); + int i; + btrie_oct_t prefix[16]; + unsigned len; + + for (i = 1; i < argc-1; i++) { + if (!parse_prefix(argv[i], prefix, &len)) { + fprintf(stderr, "Can not parse arg '%s'\n", argv[i]); + return 1; + } + btrie_add_prefix(btrie, prefix, len, argv[i]); + } + + btrie_dump(btrie); + + if (argc > 1) { + const void *data; + + if (!parse_prefix(argv[argc-1], prefix, &len)) { + fprintf(stderr, "Can not parse arg '%s'\n", argv[argc-1]); + return 1; + } + data = btrie_lookup(btrie, prefix, 128); + printf("lookup(%s) => %s\n", argv[argc-1], (const char *)data); + } + + return 0; +} + +int +main(int argc, char *argv[]) +{ + if ((pgm_name = strrchr(argv[0], '/')) != NULL) + pgm_name++; + else + pgm_name = argv[0]; + + if (argc > 1) + return test_btrie(argc, argv); + else + return unit_tests(); +} + +#endif /* TEST */ diff --git a/contrib/lc-btrie/btrie.h b/contrib/lc-btrie/btrie.h new file mode 100644 index 000000000..2cc662961 --- /dev/null +++ b/contrib/lc-btrie/btrie.h @@ -0,0 +1,83 @@ +/* Level-Compressed Tree Bitmap (LC-TBM) Trie implementation + * + * Contributed by Geoffrey T. Dairiki <dairiki@dairiki.org> + * + * This file is released under a "Three-clause BSD License". + * + * Copyright (c) 2013, Geoffrey T. Dairiki + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * * Neither the name of Geoffrey T. Dairiki nor the names of other + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GEOFFREY + * T. DAIRIKI BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE + * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + */ +#ifndef _BTRIE_H_INCLUDED +#define _BTRIE_H_INCLUDED + +#include "config.h" + +#include <stdint.h> +typedef uint8_t btrie_oct_t; + +/* maximum length of bit string btrie_walk() can handle + * + * note: this limit is necessitated by the use of fixed length buffers + * in btrie_walk() --- btrie_add_prefix() and btrie_lookup() impose no + * limit on the length of bitstrings + */ +#define BTRIE_MAX_PREFIX 128 + +struct btrie; +struct memory_pool_s; + +struct btrie * btrie_init(struct memory_pool_s *mp); + +enum btrie_result +{ + BTRIE_OKAY = 0, + BTRIE_ALLOC_FAILED = -1, + BTRIE_DUPLICATE_PREFIX = 1 +}; + +enum btrie_result btrie_add_prefix(struct btrie *btrie, + const btrie_oct_t *prefix, unsigned len, const void *data); + +const void *btrie_lookup(const struct btrie *btrie, const btrie_oct_t *pfx, + unsigned len); + +const char *btrie_stats(const struct btrie *btrie); + +#ifndef NO_MASTER_DUMP +typedef void btrie_walk_cb_t(const btrie_oct_t *prefix, unsigned len, + const void *data, int post, void *user_data); + +void btrie_walk(const struct btrie *btrie, btrie_walk_cb_t *callback, + void *user_data); +#endif /* not NO_MASTER_DUMP */ + +#endif /* _BTRIE_H_INCLUDED */ diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt index f21e604f7..fccdef5e8 100644 --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt @@ -23,6 +23,7 @@ ELSE(NOT CMAKE_SYSTEM_NAME STREQUAL "Darwin") TARGET_LINK_LIBRARIES(rspamd-test "-Wl,-force_load ${CMAKE_BINARY_DIR}/src/librspamd-server.a") ENDIF(NOT CMAKE_SYSTEM_NAME STREQUAL "Darwin") TARGET_LINK_LIBRARIES(rspamd-test rspamd-cdb) +TARGET_LINK_LIBRARIES(rspamd-test lcbtrie) TARGET_LINK_LIBRARIES(rspamd-test rspamd-http-parser) TARGET_LINK_LIBRARIES(rspamd-test ${RSPAMD_REQUIRED_LIBRARIES}) IF (ENABLE_SNOWBALL MATCHES "ON") diff --git a/test/rspamd_radix_test.c b/test/rspamd_radix_test.c index 367fbfd35..9bf421cdb 100644 --- a/test/rspamd_radix_test.c +++ b/test/rspamd_radix_test.c @@ -17,6 +17,7 @@ #include "rspamd.h" #include "radix.h" #include "ottery.h" +#include "btrie.h" const gsize max_elts = 50 * 1024; const gint lookup_cycles = 1 * 1024; @@ -74,7 +75,7 @@ struct _tv { }; static void -rspamd_radix_text_vec (void) +rspamd_radix_test_vec (void) { radix_compressed_t *tree = radix_create_compressed (); struct _tv *t = &test_vec[0]; @@ -124,7 +125,7 @@ rspamd_radix_text_vec (void) while (t->ip != NULL) { val = radix_find_compressed (tree, t->addr, t->len); g_assert (val == ++i); - //g_assert (val != RADIX_NO_VALUE); + /* g_assert (val != RADIX_NO_VALUE); */ if (t->nip != NULL) { val = radix_find_compressed (tree, t->naddr, t->len); g_assert (val != i); @@ -135,12 +136,78 @@ rspamd_radix_text_vec (void) radix_destroy_compressed (tree); } +static void +rspamd_btrie_test_vec (void) +{ + rspamd_mempool_t *pool; + struct btrie *tree; + struct _tv *t = &test_vec[0]; + struct in_addr ina; + struct in6_addr in6a; + gsize i; + gpointer val; + + pool = rspamd_mempool_new (rspamd_mempool_suggest_size (), "btrie"); + tree = btrie_init (pool); + + while (t->ip != NULL) { + t->addr = g_malloc (sizeof (in6a)); + t->naddr = g_malloc (sizeof (in6a)); + if (inet_pton (AF_INET, t->ip, &ina) == 1) { + memcpy (t->addr, &ina, sizeof (ina)); + t->len = sizeof (ina); + } + else if (inet_pton (AF_INET6, t->ip, &in6a) == 1) { + memcpy (t->addr, &in6a, sizeof (in6a)); + t->len = sizeof (in6a); + } + else { + g_assert (0); + } + if (t->nip) { + if (inet_pton (AF_INET, t->nip, &ina) == 1) { + memcpy (t->naddr, &ina, sizeof (ina)); + } + else if (inet_pton (AF_INET6, t->nip, &in6a) == 1) { + memcpy (t->naddr, &in6a, sizeof (in6a)); + } + else { + g_assert (0); + } + } + + t->mask = strtoul (t->m, NULL, 10); + t ++; + } + t = &test_vec[0]; + + i = 0; + while (t->ip != NULL) { + g_assert (btrie_add_prefix (tree, t->addr, t->mask, + GSIZE_TO_POINTER (++i)) == BTRIE_OKAY); + t ++; + } + + i = 0; + t = &test_vec[0]; + while (t->ip != NULL) { + val = btrie_lookup (tree, t->addr, t->len * NBBY); + i ++; + + g_assert (GPOINTER_TO_SIZE (val) == i); + if (t->nip != NULL) { + val = btrie_lookup (tree, t->naddr, t->len * NBBY); + g_assert (GPOINTER_TO_SIZE (val) != i); + } + t ++; + } +} + void rspamd_radix_test_func (void) { -#if 0 - radix_tree_t *tree = radix_tree_create (); -#endif + struct btrie *btrie; + rspamd_mempool_t *pool; radix_compressed_t *comp_tree = radix_create_compressed (); struct { guint32 addr; @@ -155,7 +222,8 @@ rspamd_radix_test_func (void) double diff; /* Test suite for the compressed trie */ - rspamd_radix_text_vec (); + rspamd_radix_test_vec (); + rspamd_btrie_test_vec (); nelts = max_elts; /* First of all we generate many elements and push them to the array */ @@ -167,12 +235,15 @@ rspamd_radix_test_func (void) ottery_rand_bytes (addrs[i].addr6, sizeof(addrs[i].addr6)); addrs[i].mask6 = ottery_rand_range(128); } -#if 0 - msg_info ("old radix performance (%z elts)", nelts); + + pool = rspamd_mempool_new (65536, "btrie"); + btrie = btrie_init (pool); + msg_info ("btrie performance (%z elts)", nelts); + ts1 = rspamd_get_ticks (); for (i = 0; i < nelts; i ++) { - guint32 mask = G_MAXUINT32 << (32 - addrs[i].mask); - radix32tree_insert (tree, addrs[i].addr, mask, 1); + btrie_add_prefix (btrie, addrs[i].addr6, + addrs[i].mask6, GSIZE_TO_POINTER (i)); } ts2 = rspamd_get_ticks (); diff = (ts2 - ts1) * 1000.0; @@ -182,25 +253,18 @@ rspamd_radix_test_func (void) ts1 = rspamd_get_ticks (); for (lc = 0; lc < lookup_cycles; lc ++) { for (i = 0; i < nelts; i ++) { - g_assert (radix32tree_find (tree, addrs[i].addr) != RADIX_NO_VALUE); + if (btrie_lookup (btrie, addrs[i].addr6, sizeof (addrs[i].addr6)) + == NULL) { + all_good = FALSE; + } } } + g_assert (all_good); ts2 = rspamd_get_ticks (); diff = (ts2 - ts1) * 1000.0; - msg_info ("Checked %z elements in %.6f ms", nelts, diff); - - ts1 = rspamd_get_ticks (); - for (i = 0; i < nelts; i ++) { - radix32tree_delete (tree, addrs[i].addr, addrs[i].mask); - } - ts2 = rspamd_get_ticks (); - diff = (ts2 - ts1) * 1000.; - - msg_info ("Deleted %z elements in %.6f ms", nelts, diff); + msg_info ("Checked %z elements in %.6f ms", nelts * lookup_cycles, diff); - radix_tree_free (tree); -#endif msg_info ("new radix performance (%z elts)", nelts); ts1 = rspamd_get_ticks (); for (i = 0; i < nelts; i ++) { @@ -238,7 +302,7 @@ rspamd_radix_test_func (void) ts2 = rspamd_get_ticks (); diff = (ts2 - ts1) * 1000.0; - msg_info ("Checked %z elements in %.6f ms", nelts, diff); + msg_info ("Checked %z elements in %.6f ms", nelts * lookup_cycles, diff); radix_destroy_compressed (comp_tree); g_free (addrs); |