LCOV - code coverage report
Current view: top level - lib/generic - trie.c Hit Total Coverage
Test: Knot Resolver 3.2.1-POSIX coverage report Lines: 358 447 80.1 %
Date: 2019-03-12 03:31:59
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*  Copyright (C) 2016-2018 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
       2             : 
       3             :     This program is free software: you can redistribute it and/or modify
       4             :     it under the terms of the GNU General Public License as published by
       5             :     the Free Software Foundation, either version 3 of the License, or
       6             :     (at your option) any later version.
       7             : 
       8             :     This program is distributed in the hope that it will be useful,
       9             :     but WITHOUT ANY WARRANTY; without even the implied warranty of
      10             :     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      11             :     GNU General Public License for more details.
      12             : 
      13             :     You should have received a copy of the GNU General Public License
      14             :     along with this program.  If not, see <http://www.gnu.org/licenses/>.
      15             : 
      16             :     The code originated from https://github.com/fanf2/qp/blob/master/qp.c
      17             :     at revision 5f6d93753.
      18             :  */
      19             : 
      20             : #include <assert.h>
      21             : #include <stdlib.h>
      22             : #include <string.h>
      23             : 
      24             : #include "lib/generic/trie.h"
      25             : #include "lib/utils.h"
      26             : #include "contrib/ucw/lib.h"
      27             : 
      28             : #if defined(__i386) || defined(__x86_64) || defined(_M_IX86) \
      29             :         || (defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN) \
      30             :                 && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
      31             : 
      32             :         /*!
      33             :          * \brief Use a pointer alignment hack to save memory.
      34             :          *
      35             :          * When on, isbranch() relies on the fact that in leaf_t the first pointer
      36             :          * is aligned on multiple of 4 bytes and that the flags bitfield is
      37             :          * overlaid over the lowest two bits of that pointer.
      38             :          * Neither is really guaranteed by the C standards; the second part should
      39             :          * be OK with x86_64 ABI and most likely any other little-endian platform.
      40             :          * It would be possible to manipulate the right bits portably, but it would
      41             :          * complicate the code nontrivially. C++ doesn't even guarantee type-punning.
      42             :          * In debug mode we check this works OK when creating a new trie instance.
      43             :          */
      44             :         #define FLAGS_HACK 1
      45             : #else
      46             :         #define FLAGS_HACK 0
      47             : #endif
      48             : 
      49             : typedef unsigned char byte;
      50             : #ifndef uint
      51             : typedef unsigned int uint;
      52             : #define uint uint
      53             : #endif
      54             : typedef uint bitmap_t; /*! Bit-maps, using the range of 1<<0 to 1<<16 (inclusive). */
      55             : 
      56             : typedef struct {
      57             :         uint32_t len; // 32 bits are enough for key lengths; probably even 16 bits would be.
      58             :         char chars[];
      59             : } tkey_t;
      60             : 
      61             : /*! \brief Leaf of trie. */
      62             : typedef struct {
      63             :         #if !FLAGS_HACK
      64             :                 byte flags;
      65             :         #endif
      66             :         tkey_t *key; /*!< The pointer must be aligned to 4-byte multiples! */
      67             :         trie_val_t val;
      68             : } leaf_t;
      69             : 
      70             : /*! \brief A trie node is either leaf_t or branch_t. */
      71             : typedef union node node_t;
      72             : 
      73             : /*!
      74             :  * \brief Branch node of trie.
      75             :  *
      76             :  * - The flags distinguish whether the node is a leaf_t (0), or a branch
      77             :  *   testing the more-important nibble (1) or the less-important one (2).
      78             :  * - It stores the index of the byte that the node tests.  The combined
      79             :  *   value (index*4 + flags) increases in branch nodes as you go deeper
      80             :  *   into the trie.  All the keys below a branch are identical up to the
      81             :  *   nibble identified by the branch.  Indices have to be stored because
      82             :  *   we skip any branch nodes that would have a single child.
      83             :  *   (Consequently, the skipped parts of key have to be validated in a leaf.)
      84             :  * - The bitmap indicates which subtries are present.  The present child nodes
      85             :  *   are stored in the twigs array (with no holes between them).
      86             :  * - To simplify storing keys that are prefixes of each other, the end-of-string
      87             :  *   position is treated as another nibble value, ordered before all others.
      88             :  *   That affects the bitmap and twigs fields.
      89             :  *
      90             :  * \note The branch nodes are never allocated individually, but they are
      91             :  *   always part of either the root node or the twigs array of the parent.
      92             :  */
      93             : typedef struct {
      94             :         #if FLAGS_HACK
      95             :                 uint32_t flags  : 2,
      96             :                          bitmap : 17; /*!< The first bitmap bit is for end-of-string child. */
      97             :         #else
      98             :                 byte flags;
      99             :                 uint32_t bitmap;
     100             :         #endif
     101             :         uint32_t index;
     102             :         node_t *twigs;
     103             : } branch_t;
     104             : 
     105             : union node {
     106             :         leaf_t leaf;
     107             :         branch_t branch;
     108             : };
     109             : 
     110             : struct trie {
     111             :         node_t root; // undefined when weight == 0, see empty_root()
     112             :         size_t weight;
     113             :         knot_mm_t mm;
     114             : };
     115             : 
     116             : /*! \brief Make the root node empty (debug-only). */
     117       66293 : static inline void empty_root(node_t *root) {
     118             : #ifndef NDEBUG
     119       71721 :         *root = (node_t){ .branch = {
     120             :                 .flags = 3, // invalid value that fits
     121             :                 .bitmap = 0,
     122             :                 .index = -1,
     123             :                 .twigs = NULL
     124             :         } };
     125             : #endif
     126       66293 : }
     127             : 
     128             : /*! \brief Check that unportable code works OK (debug-only). */
     129       55903 : static void assert_portability(void) {
     130             : #if FLAGS_HACK
     131       55903 :         assert(((union node){ .leaf = {
     132             :                         .key = (tkey_t *)(((uint8_t *)NULL) + 1),
     133             :                         .val = NULL
     134             :                 } }).branch.flags == 1);
     135             : #endif
     136       55903 : }
     137             : 
     138             : /*! \brief Propagate error codes. */
     139             : #define ERR_RETURN(x) \
     140             :         do { \
     141             :                 int err_code_ = x; \
     142             :                 if (unlikely(err_code_ != KNOT_EOK)) \
     143             :                         return err_code_; \
     144             :         } while (false)
     145             : 
     146             : /*!
     147             :  * \brief Count the number of set bits.
     148             :  *
     149             :  * \TODO This implementation may be relatively slow on some HW.
     150             :  */
     151      435303 : static uint bitmap_weight(bitmap_t w)
     152             : {
     153      435303 :         assert((w & ~((1 << 17) - 1)) == 0); // using the least-important 17 bits
     154      447906 :         return __builtin_popcount(w);
     155             : }
     156             : 
     157             : /*! \brief Only keep the lowest bit in the bitmap (least significant -> twigs[0]). */
     158           0 : static bitmap_t bitmap_lowest_bit(bitmap_t w)
     159             : {
     160           0 :         assert((w & ~((1 << 17) - 1)) == 0); // using the least-important 17 bits
     161         202 :         return 1 << __builtin_ctz(w);
     162             : }
     163             : 
     164             : /*! \brief Test flags to determine type of this node. */
     165     2110964 : static bool isbranch(const node_t *t)
     166             : {
     167     2181318 :         uint f = t->branch.flags;
     168     2176929 :         assert(f <= 2);
     169     2110964 :         return f != 0;
     170             : }
     171             : 
     172             : /*! \brief Make a bitmask for testing a branch bitmap. */
     173      322624 : static bitmap_t nibbit(byte k, uint flags)
     174             : {
     175      329442 :         uint shift = (2 - flags) << 2;
     176      329442 :         uint nibble = (k >> shift) & 0xf;
     177      329442 :         return 1 << (nibble + 1/*because of prefix keys*/);
     178             : }
     179             : 
     180             : /*! \brief Extract a nibble from a key and turn it into a bitmask. */
     181      300276 : static bitmap_t twigbit(const node_t *t, const char *key, uint32_t len)
     182             : {
     183      300276 :         assert(isbranch(t));
     184      300276 :         uint i = t->branch.index;
     185             : 
     186      300276 :         if (i >= len)
     187           2 :                 return 1 << 0; // leaf position
     188             : 
     189      305973 :         return nibbit((byte)key[i], t->branch.flags);
     190             : }
     191             : 
     192             : /*! \brief Test if a branch node has a child indicated by a bitmask. */
     193      271108 : static bool hastwig(const node_t *t, bitmap_t bit)
     194             : {
     195      271108 :         assert(isbranch(t));
     196      271108 :         return t->branch.bitmap & bit;
     197             : }
     198             : 
     199             : /*! \brief Compute offset of an existing child in a branch node. */
     200      267048 : static uint twigoff(const node_t *t, bitmap_t b)
     201             : {
     202      267048 :         assert(isbranch(t));
     203      271431 :         return bitmap_weight(t->branch.bitmap & (b - 1));
     204             : }
     205             : 
     206             : /*! \brief Get pointer to a particular child of a branch node. */
     207      377803 : static node_t* twig(node_t *t, uint i)
     208             : {
     209      377803 :         assert(isbranch(t));
     210      377803 :         return &t->branch.twigs[i];
     211             : }
     212             : 
     213             : /*!
     214             :  * \brief For a branch nod, compute offset of a child and child count.
     215             :  *
     216             :  * Having this separate might be meaningful for performance optimization.
     217             :  */
     218             : #define TWIGOFFMAX(off, max, t, b) do {                 \
     219             :                 (off) = twigoff((t), (b));              \
     220             :                 (max) = bitmap_weight((t)->branch.bitmap);\
     221             :         } while(0)
     222             : 
     223             : /*! \brief Simple string comparator. */
     224       37995 : static int key_cmp(const char *k1, uint32_t k1_len, const char *k2, uint32_t k2_len)
     225             : {
     226       38107 :         int ret = memcmp(k1, k2, MIN(k1_len, k2_len));
     227       38107 :         if (ret != 0) {
     228        6451 :                 return ret;
     229             :         }
     230             : 
     231             :         /* Key string is equal, compare lengths. */
     232       31656 :         if (k1_len == k2_len) {
     233       31544 :                 return 0;
     234           0 :         } else if (k1_len < k2_len) {
     235           0 :                 return -1;
     236             :         } else {
     237           0 :                 return 1;
     238             :         }
     239             : }
     240             : 
     241       55903 : trie_t* trie_create(knot_mm_t *mm)
     242             : {
     243       55903 :         assert_portability();
     244       55903 :         trie_t *trie = mm_alloc(mm, sizeof(trie_t));
     245       55903 :         if (trie != NULL) {
     246       50620 :                 empty_root(&trie->root);
     247       55903 :                 trie->weight = 0;
     248       55903 :                 if (mm != NULL)
     249       40223 :                         trie->mm = *mm;
     250             :                 else
     251       15645 :                         mm_ctx_init(&trie->mm);
     252             :         }
     253       55903 :         return trie;
     254             : }
     255             : 
     256             : /*! \brief Free anything under the trie node, except for the passed pointer itself. */
     257        2479 : static void clear_trie(node_t *trie, knot_mm_t *mm)
     258             : {
     259        2479 :         if (!isbranch(trie)) {
     260        2282 :                 mm_free(mm, trie->leaf.key);
     261             :         } else {
     262          62 :                 branch_t *b = &trie->branch;
     263         197 :                 int len = bitmap_weight(b->bitmap);
     264        2490 :                 for (int i = 0; i < len; ++i)
     265        2293 :                         clear_trie(b->twigs + i, mm);
     266         197 :                 mm_free(mm, b->twigs);
     267             :         }
     268        2479 : }
     269             : 
     270       22819 : void trie_free(trie_t *tbl)
     271             : {
     272       22819 :         if (tbl == NULL)
     273           0 :                 return;
     274       22819 :         if (tbl->weight)
     275          18 :                 clear_trie(&tbl->root, &tbl->mm);
     276       22819 :         mm_free(&tbl->mm, tbl);
     277             : }
     278             : 
     279       30141 : void trie_clear(trie_t *tbl)
     280             : {
     281       30141 :         assert(tbl);
     282       30141 :         if (!tbl->weight)
     283       29898 :                 return;
     284         168 :         clear_trie(&tbl->root, &tbl->mm);
     285          29 :         empty_root(&tbl->root);
     286         168 :         tbl->weight = 0;
     287             : }
     288             : 
     289       65143 : size_t trie_weight(const trie_t *tbl)
     290             : {
     291       65143 :         assert(tbl);
     292       65143 :         return tbl->weight;
     293             : }
     294             : 
     295             : struct found {
     296             :         leaf_t *l;      /**< the found leaf (NULL if not found) */
     297             :         branch_t *p;    /**< the leaf's parent (if exists) */
     298             :         bitmap_t b;     /**< bit-mask with a single bit marking l under p */
     299             : };
     300             : /** Search trie for an item with the given key (equality only). */
     301       80787 : static struct found find_equal(trie_t *tbl, const char *key, uint32_t len)
     302             : {
     303       80787 :         assert(tbl);
     304       80658 :         struct found ret0;
     305       80787 :         memset(&ret0, 0, sizeof(ret0));
     306       80787 :         if (!tbl->weight)
     307       35864 :                 return ret0;
     308             :         /* Current node and parent while descending (returned values basically). */
     309       44923 :         node_t *t = &tbl->root;
     310       44809 :         branch_t *p = NULL;
     311       44809 :         bitmap_t b = 0;
     312      106659 :         while (isbranch(t)) {
     313       68438 :                 __builtin_prefetch(t->branch.twigs);
     314       68438 :                 b = twigbit(t, key, len);
     315       68438 :                 if (!hastwig(t, b))
     316        6816 :                         return ret0;
     317       61622 :                 p = &t->branch;
     318       61622 :                 t = twig(t, twigoff(t, b));
     319             :         }
     320       38115 :         if (key_cmp(key, len, t->leaf.key->chars, t->leaf.key->len) != 0)
     321        6451 :                 return ret0;
     322       31656 :         return (struct found) {
     323       31656 :                 .l = &t->leaf,
     324             :                 .p = p,
     325             :                 .b = b,
     326             :         };
     327             : }
     328             : /** Find item with the first key (lexicographical order). */
     329        2696 : static struct found find_first(trie_t *tbl)
     330             : {
     331        2696 :         assert(tbl);
     332        2696 :         if (!tbl->weight) {
     333           0 :                 struct found ret0;
     334           0 :                 memset(&ret0, 0, sizeof(ret0));
     335           0 :                 return ret0;
     336             :         }
     337             :         /* Current node and parent while descending (returned values basically). */
     338        2696 :         node_t *t = &tbl->root;
     339        2492 :         branch_t *p = NULL;
     340        3458 :         while (isbranch(t)) {
     341         558 :                 p = &t->branch;
     342         558 :                 t = &p->twigs[0];
     343             :         }
     344        2696 :         return (struct found) {
     345        2696 :                 .l = &t->leaf,
     346             :                 .p = p,
     347        2696 :                 .b = p ? bitmap_lowest_bit(p->bitmap) : 0,
     348             :         };
     349             : }
     350             : 
     351       33557 : trie_val_t* trie_get_try(trie_t *tbl, const char *key, uint32_t len)
     352             : {
     353       33557 :         struct found found = find_equal(tbl, key, len);
     354       33557 :         return found.l ? &found.l->val : NULL;
     355             : }
     356             : 
     357        2593 : trie_val_t* trie_get_first(trie_t *tbl, char **key, uint32_t *len)
     358             : {
     359        2593 :         struct found found = find_first(tbl);
     360        2593 :         if (!found.l)
     361           0 :                 return NULL;
     362        2593 :         if (key)
     363         102 :                 *key = found.l->key->chars;
     364        2593 :         if (len)
     365         102 :                 *len = found.l->key->len;
     366        2593 :         return &found.l->val;
     367             : }
     368             : 
     369             : /** Delete the found element (if any) and return value (unless NULL is passed) */
     370       47231 : static int del_found(trie_t *tbl, struct found found, trie_val_t *val)
     371             : {
     372       47231 :         if (!found.l)
     373       18287 :                 return KNOT_ENOENT;
     374       28941 :         mm_free(&tbl->mm, found.l->key);
     375       28941 :         if (val != NULL)
     376       28850 :                 *val = found.l->val; // we return trie_val_t directly when deleting
     377       28941 :         --tbl->weight;
     378       28941 :         branch_t * const p = found.p; // short-hand
     379       28941 :         if (unlikely(!p)) { // whole trie was a single leaf
     380       15650 :                 assert(tbl->weight == 0);
     381       15644 :                 empty_root(&tbl->root);
     382       15644 :                 return KNOT_EOK;
     383             :         }
     384             :         // remove leaf t as child of p; get child index via pointer arithmetic
     385       13291 :         int ci = ((union node *)found.l) - p->twigs,
     386       13291 :             cc = bitmap_weight(p->bitmap); // child count
     387       13291 :         assert(ci >= 0 && ci < cc);
     388             : 
     389       13291 :         if (cc == 2) { // collapse binary node p: move the other child to this node
     390        7582 :                 node_t *twigs = p->twigs;
     391        7582 :                 (*(union node *)p) = twigs[1 - ci]; // it might be a leaf or branch
     392        7582 :                 mm_free(&tbl->mm, twigs);
     393        7582 :                 return KNOT_EOK;
     394             :         }
     395        5709 :         memmove(p->twigs + ci, p->twigs + ci + 1, sizeof(node_t) * (cc - ci - 1));
     396        5709 :         p->bitmap &= ~found.b;
     397        5709 :         node_t *twigs = mm_realloc(&tbl->mm, p->twigs, sizeof(node_t) * (cc - 1),
     398             :                                    sizeof(node_t) * cc);
     399        5709 :         if (likely(twigs != NULL))
     400        5709 :                 p->twigs = twigs;
     401             :                 /* We can ignore mm_realloc failure, only beware that next time
     402             :                  * the prev_size passed to it wouldn't be correct; TODO? */
     403        5709 :         return KNOT_EOK;
     404             : }
     405             : 
     406       47230 : int trie_del(trie_t *tbl, const char *key, uint32_t len, trie_val_t *val)
     407             : {
     408       47230 :         struct found found = find_equal(tbl, key, len);
     409       47230 :         return del_found(tbl, found, val);
     410             : }
     411             : 
     412         103 : int trie_del_first(trie_t *tbl, char *key, uint32_t *len, trie_val_t *val)
     413             : {
     414         103 :         struct found found = find_first(tbl);
     415         103 :         if (!found.l)
     416           0 :                 return KNOT_ENOENT;
     417         103 :         if (key) {
     418         102 :                 if (!len)
     419           0 :                         return KNOT_EINVAL;
     420         102 :                 if (*len < found.l->key->len)
     421           0 :                         return kr_error(ENOSPC);
     422         102 :                 memcpy(key, found.l->key->chars, found.l->key->len);
     423             :         }
     424         103 :         if (len) { // makes sense even with key == NULL
     425         102 :                 *len = found.l->key->len;
     426             :         }
     427         103 :         return del_found(tbl, found, val);
     428             : }
     429             : 
     430             : /*!
     431             :  * \brief Stack of nodes, storing a path down a trie.
     432             :  *
     433             :  * The structure also serves directly as the public trie_it_t type,
     434             :  * in which case it always points to the current leaf, unless we've finished
     435             :  * (i.e. it->len == 0).
     436             :  */
     437             : typedef struct trie_it {
     438             :         node_t* *stack; /*!< The stack; malloc is used directly instead of mm. */
     439             :         uint32_t len;   /*!< Current length of the stack. */
     440             :         uint32_t alen;  /*!< Allocated/available length of the stack. */
     441             :         /*! \brief Initial storage for \a stack; it should fit in many use cases. */
     442             :         node_t* stack_init[60];
     443             : } nstack_t;
     444             : 
     445             : /*! \brief Create a node stack containing just the root (or empty). */
     446      143641 : static void ns_init(nstack_t *ns, trie_t *tbl)
     447             : {
     448      143641 :         assert(tbl);
     449      143641 :         ns->stack = ns->stack_init;
     450      143641 :         ns->alen = sizeof(ns->stack_init) / sizeof(ns->stack_init[0]);
     451      143641 :         if (tbl->weight) {
     452      129412 :                 ns->len = 1;
     453      129412 :                 ns->stack[0] = &tbl->root;
     454             :         } else {
     455       14229 :                 ns->len = 0;
     456             :         }
     457      143641 : }
     458             : 
     459             : /*! \brief Free inside of the stack, i.e. not the passed pointer itself. */
     460      143641 : static void ns_cleanup(nstack_t *ns)
     461             : {
     462      143641 :         assert(ns && ns->stack);
     463      143641 :         if (likely(ns->stack == ns->stack_init))
     464      138399 :                 return;
     465           0 :         free(ns->stack);
     466             :         #ifndef NDEBUG
     467           0 :                 ns->stack = NULL;
     468           0 :                 ns->alen = 0;
     469             :         #endif
     470             : }
     471             : 
     472             : /*! \brief Allocate more space for the stack. */
     473           0 : static int ns_longer_alloc(nstack_t *ns)
     474             : {
     475           0 :         ns->alen *= 2;
     476           0 :         size_t new_size = sizeof(nstack_t) + ns->alen * sizeof(node_t *);
     477             :         node_t **st;
     478           0 :         if (ns->stack == ns->stack_init) {
     479           0 :                 st = malloc(new_size);
     480           0 :                 if (st != NULL)
     481           0 :                         memcpy(st, ns->stack, ns->len * sizeof(node_t *));
     482             :         } else {
     483           0 :                 st = realloc(ns->stack, new_size);
     484             :         }
     485           0 :         if (st == NULL)
     486           0 :                 return KNOT_ENOMEM;
     487           0 :         ns->stack = st;
     488           0 :         return KNOT_EOK;
     489             : }
     490             : 
     491             : /*! \brief Ensure the node stack can be extended by one. */
     492      232357 : static inline int ns_longer(nstack_t *ns)
     493             : {
     494             :         // get a longer stack if needed
     495      241859 :         if (likely(ns->len < ns->alen))
     496      232357 :                 return KNOT_EOK;
     497           0 :         return ns_longer_alloc(ns); // hand-split the part suitable for inlining
     498             : }
     499             : 
     500             : /*!
     501             :  * \brief Find the "branching point" as if searching for a key.
     502             :  *
     503             :  *  The whole path to the point is kept on the passed stack;
     504             :  *  always at least the root will remain on the top of it.
     505             :  *  Beware: the precise semantics of this function is rather tricky.
     506             :  *  The top of the stack will contain: the corresponding leaf if exact match is found;
     507             :  *  or the immediate node below a branching-point-on-edge or the branching-point itself.
     508             :  *
     509             :  *  \param info   Set position of the point of first mismatch (in index and flags).
     510             :  *  \param first  Set the value of the first non-matching character (from trie),
     511             :  *                optionally; end-of-string character has value -256 (that's why it's int).
     512             :  *                Note: the character is converted to *unsigned* char (i.e. 0..255),
     513             :  *                as that's the ordering used in the trie.
     514             :  *
     515             :  *  \return KNOT_EOK or KNOT_ENOMEM.
     516             :  */
     517      113710 : static int ns_find_branch(nstack_t *ns, const char *key, uint32_t len,
     518             :                           branch_t *info, int *first)
     519             : {
     520      113710 :         assert(ns && ns->len && info);
     521             :         // First find some leaf with longest matching prefix.
     522      242162 :         while (isbranch(ns->stack[ns->len - 1])) {
     523      122546 :                 ERR_RETURN(ns_longer(ns));
     524      122546 :                 node_t *t = ns->stack[ns->len - 1];
     525      122546 :                 __builtin_prefetch(t->branch.twigs);
     526      122546 :                 bitmap_t b = twigbit(t, key, len);
     527             :                 // Even if our key is missing from this branch we need to
     528             :                 // keep iterating down to a leaf. It doesn't matter which
     529             :                 // twig we choose since the keys are all the same up to this
     530             :                 // index. Note that blindly using twigoff(t, b) can cause
     531             :                 // an out-of-bounds index if it equals twigmax(t).
     532      122546 :                 uint i = hastwig(t, b) ? twigoff(t, b) : 0;
     533      122546 :                 ns->stack[ns->len++] = twig(t, i);
     534             :         }
     535      113710 :         tkey_t *lkey = ns->stack[ns->len-1]->leaf.key;
     536             :         // Find index of the first char that differs.
     537      110532 :         uint32_t index = 0;
     538      647070 :         while (index < MIN(len,lkey->len)) {
     539      627058 :                 if (key[index] != lkey->chars[index])
     540       93805 :                         break;
     541             :                 else
     542      530286 :                         ++index;
     543             :         }
     544      113710 :         info->index = index;
     545      113710 :         if (first)
     546      113710 :                 *first = lkey->len > index ? (unsigned char)lkey->chars[index] : -256;
     547             :         // Find flags: which half-byte has matched.
     548             :         uint flags;
     549      113710 :         if (index == len && len == lkey->len) { // found equivalent key
     550       16938 :                 info->flags = flags = 0;
     551       16938 :                 goto success;
     552             :         }
     553       96772 :         if (likely(index < MIN(len,lkey->len))) {
     554       96772 :                 byte k2 = (byte)lkey->chars[index];
     555       96772 :                 byte k1 = (byte)key[index];
     556       96772 :                 flags = ((k1 ^ k2) & 0xf0) ? 1 : 2;
     557             :         } else { // one is prefix of another
     558           0 :                 flags = 1;
     559             :         }
     560       96772 :         info->flags = flags;
     561             :         // now go up the trie from the current leaf
     562             :         branch_t *t;
     563             :         do {
     564      176866 :                 if (unlikely(ns->len == 1))
     565       75047 :                         goto success; // only the root stays on the stack
     566       96332 :                 t = (branch_t*)ns->stack[ns->len - 2];
     567       96332 :                 if (t->index < index || (t->index == index && t->flags < flags))
     568       18758 :                         goto success;
     569       77471 :                 --ns->len;
     570             :         } while (true);
     571      110636 : success:
     572             :         #ifndef NDEBUG // invariants on successful return
     573      113710 :                 assert(ns->len);
     574      116784 :                 if (isbranch(ns->stack[ns->len - 1])) {
     575       70173 :                         t = &ns->stack[ns->len - 1]->branch;
     576       72843 :                         assert(t->index > index || (t->index == index && t->flags >= flags));
     577             :                 }
     578      113710 :                 if (ns->len > 1) {
     579       31190 :                         t = &ns->stack[ns->len - 2]->branch;
     580       31190 :                         assert(t->index < index || (t->index == index
     581             :                                && (t->flags < flags || (t->flags == 1 && flags == 0))));
     582             :                 }
     583             :         #endif
     584      110532 :         return KNOT_EOK;
     585             : }
     586             : 
     587             : /*!
     588             :  * \brief Advance the node stack to the last leaf in the subtree.
     589             :  *
     590             :  * \return KNOT_EOK or KNOT_ENOMEM.
     591             :  */
     592           1 : static int ns_last_leaf(nstack_t *ns)
     593             : {
     594           1 :         assert(ns);
     595           0 :         do {
     596           1 :                 ERR_RETURN(ns_longer(ns));
     597           1 :                 node_t *t = ns->stack[ns->len - 1];
     598           1 :                 if (!isbranch(t))
     599           0 :                         return KNOT_EOK;
     600           0 :                 int lasti = bitmap_weight(t->branch.bitmap) - 1;
     601           0 :                 assert(lasti >= 0);
     602           0 :                 ns->stack[ns->len++] = twig(t, lasti);
     603             :         } while (true);
     604             : }
     605             : 
     606             : /*!
     607             :  * \brief Advance the node stack to the first leaf in the subtree.
     608             :  *
     609             :  * \return KNOT_EOK or KNOT_ENOMEM.
     610             :  */
     611       95705 : static int ns_first_leaf(nstack_t *ns)
     612             : {
     613       95705 :         assert(ns && ns->len);
     614       23607 :         do {
     615      119312 :                 ERR_RETURN(ns_longer(ns));
     616      119312 :                 node_t *t = ns->stack[ns->len - 1];
     617      119312 :                 if (!isbranch(t))
     618       89790 :                         return KNOT_EOK;
     619       23607 :                 ns->stack[ns->len++] = twig(t, 0);
     620             :         } while (true);
     621             : }
     622             : 
     623             : /*!
     624             :  * \brief Advance the node stack to the leaf that is previous to the current node.
     625             :  *
     626             :  * \note Prefix leaf under the current node DOES count (if present; perhaps questionable).
     627             :  * \return KNOT_EOK on success, KNOT_ENOENT on not-found, or possibly KNOT_ENOMEM.
     628             :  */
     629           0 : static int ns_prev_leaf(nstack_t *ns)
     630             : {
     631           0 :         assert(ns && ns->len > 0);
     632             : 
     633           0 :         node_t *t = ns->stack[ns->len - 1];
     634           0 :         if (hastwig(t, 1 << 0)) { // the prefix leaf
     635           0 :                 t = twig(t, 0);
     636           0 :                 ERR_RETURN(ns_longer(ns));
     637           0 :                 ns->stack[ns->len++] = t;
     638           0 :                 return KNOT_EOK;
     639             :         }
     640             : 
     641           0 :         do {
     642           0 :                 if (ns->len < 2)
     643           0 :                         return KNOT_ENOENT; // root without empty key has no previous leaf
     644           0 :                 t = ns->stack[ns->len - 1];
     645           0 :                 node_t *p = ns->stack[ns->len - 2];
     646           0 :                 int pindex = t - p->branch.twigs; // index in parent via pointer arithmetic
     647           0 :                 assert(pindex >= 0 && pindex <= 16);
     648           0 :                 if (pindex > 0) { // t isn't the first child -> go down the previous one
     649           0 :                         ns->stack[ns->len - 1] = twig(p, pindex - 1);
     650           0 :                         return ns_last_leaf(ns);
     651             :                 }
     652             :                 // we've got to go up again
     653           0 :                 --ns->len;
     654             :         } while (true);
     655             : }
     656             : 
     657             : /*!
     658             :  * \brief Advance the node stack to the leaf that is successor to the current node.
     659             :  *
     660             :  * \note Prefix leaf or anything else under the current node DOES count.
     661             :  * \return KNOT_EOK on success, KNOT_ENOENT on not-found, or possibly KNOT_ENOMEM.
     662             :  */
     663       92465 : static int ns_next_leaf(nstack_t *ns)
     664             : {
     665       92465 :         assert(ns && ns->len > 0);
     666             : 
     667       92465 :         node_t *t = ns->stack[ns->len - 1];
     668       92465 :         if (isbranch(t))
     669           0 :                 return ns_first_leaf(ns);
     670       19368 :         do {
     671      111833 :                 if (ns->len < 2)
     672       11245 :                         return KNOT_ENOENT; // not found, as no more parent is available
     673       99371 :                 t = ns->stack[ns->len - 1];
     674       99371 :                 node_t *p = ns->stack[ns->len - 2];
     675       99371 :                 int pindex = t - p->branch.twigs; // index in parent via pointer arithmetic
     676       99371 :                 assert(pindex >= 0 && pindex <= 16);
     677       99371 :                 int pcount = bitmap_weight(p->branch.bitmap);
     678       99371 :                 if (pindex + 1 < pcount) { // t isn't the last child -> go down the next one
     679       80003 :                         ns->stack[ns->len - 1] = twig(p, pindex + 1);
     680       80003 :                         return ns_first_leaf(ns);
     681             :                 }
     682             :                 // we've got to go up again
     683       19368 :                 --ns->len;
     684             :         } while (true);
     685             : }
     686             : 
     687           1 : int trie_get_leq(trie_t *tbl, const char *key, uint32_t len, trie_val_t **val)
     688             : {
     689           1 :         assert(tbl && val);
     690           1 :         *val = NULL; // so on failure we can just return;
     691           1 :         if (tbl->weight == 0)
     692           0 :                 return KNOT_ENOENT;
     693             :         { // Intentionally un-indented; until end of function, to bound cleanup attr.
     694             :         // First find a key with longest-matching prefix
     695             :         __attribute__((cleanup(ns_cleanup)))
     696           1 :                 nstack_t ns_local;
     697           1 :         ns_init(&ns_local, tbl);
     698           0 :         nstack_t *ns = &ns_local;
     699           0 :         branch_t bp;
     700           0 :         int un_leaf; // first unmatched character in the leaf
     701           1 :         ERR_RETURN(ns_find_branch(ns, key, len, &bp, &un_leaf));
     702           1 :         int un_key = bp.index < len ? (unsigned char)key[bp.index] : -256;
     703           1 :         node_t *t = ns->stack[ns->len - 1];
     704           1 :         if (bp.flags == 0) { // found exact match
     705           0 :                 *val = &t->leaf.val;
     706           0 :                 return KNOT_EOK;
     707             :         }
     708             :         // Get t: the last node on matching path
     709           1 :         if (isbranch(t) && t->branch.index == bp.index && t->branch.flags == bp.flags) {
     710             :                 // t is OK
     711             :         } else {
     712             :                 // the top of the stack was the first unmatched node -> step up
     713           1 :                 if (ns->len == 1) {
     714             :                         // root was unmatched already
     715           1 :                         if (un_key < un_leaf)
     716           0 :                                 return KNOT_ENOENT;
     717           1 :                         ERR_RETURN(ns_last_leaf(ns));
     718           0 :                         goto success;
     719             :                 }
     720           0 :                 --ns->len;
     721           0 :                 t = ns->stack[ns->len - 1];
     722             :         }
     723             :         // Now we re-do the first "non-matching" step in the trie
     724             :         // but try the previous child if key was less (it may not exist)
     725           0 :         bitmap_t b = twigbit(t, key, len);
     726           0 :         int i = hastwig(t, b)
     727           0 :                 ? twigoff(t, b) - (un_key < un_leaf)
     728           0 :                 : twigoff(t, b) - 1 /*twigoff returns successor when !hastwig*/;
     729           0 :         if (i >= 0) {
     730           0 :                 ERR_RETURN(ns_longer(ns));
     731           0 :                 ns->stack[ns->len++] = twig(t, i);
     732           0 :                 ERR_RETURN(ns_last_leaf(ns));
     733             :         } else {
     734           0 :                 ERR_RETURN(ns_prev_leaf(ns));
     735             :         }
     736           0 : success:
     737           1 :         assert(!isbranch(ns->stack[ns->len - 1]));
     738           1 :         *val = &ns->stack[ns->len - 1]->leaf.val;
     739           1 :         return 1;
     740             :         }
     741             : }
     742             : 
     743             : /*! \brief Initialize a new leaf, copying the key, and returning failure code. */
     744      126470 : static int mk_leaf(node_t *leaf, const char *key, uint32_t len, knot_mm_t *mm)
     745             : {
     746      126470 :         tkey_t *k = mm_alloc(mm, sizeof(tkey_t) + len);
     747             :         #if FLAGS_HACK
     748      126470 :                 assert(((uintptr_t)k) % 4 == 0); // we need an aligned pointer
     749             :         #endif
     750      126470 :         if (unlikely(!k))
     751           0 :                 return KNOT_ENOMEM;
     752      126470 :         k->len = len;
     753      126470 :         memcpy(k->chars, key, len);
     754      126470 :         leaf->leaf = (leaf_t){
     755             :                 #if !FLAGS_HACK
     756             :                         .flags = 0,
     757             :                 #endif
     758             :                 .val = NULL,
     759             :                 .key = k
     760             :         };
     761      126470 :         return KNOT_EOK;
     762             : }
     763             : 
     764      143515 : trie_val_t* trie_get_ins(trie_t *tbl, const char *key, uint32_t len)
     765             : {
     766      143515 :         assert(tbl);
     767             :         // First leaf in an empty tbl?
     768      143515 :         if (unlikely(!tbl->weight)) {
     769       29806 :                 if (unlikely(mk_leaf(&tbl->root, key, len, &tbl->mm)))
     770           0 :                         return NULL;
     771       29806 :                 ++tbl->weight;
     772       29806 :                 return &tbl->root.leaf.val;
     773             :         }
     774             :         { // Intentionally un-indented; until end of function, to bound cleanup attr.
     775             :         // Find the branching-point
     776             :         __attribute__((cleanup(ns_cleanup)))
     777      224241 :                 nstack_t ns_local;
     778      113709 :         ns_init(&ns_local, tbl);
     779      110532 :         nstack_t *ns = &ns_local;
     780      110532 :         branch_t bp; // branch-point: index and flags signifying the longest common prefix
     781      110532 :         int k2; // the first unmatched character in the leaf
     782      113709 :         if (unlikely(ns_find_branch(ns, key, len, &bp, &k2)))
     783           0 :                 return NULL;
     784      113709 :         node_t *t = ns->stack[ns->len - 1];
     785      113709 :         if (bp.flags == 0) // the same key was already present
     786       16938 :                 return &t->leaf.val;
     787       93805 :         node_t leaf;
     788       96771 :         if (unlikely(mk_leaf(&leaf, key, len, &tbl->mm)))
     789           0 :                 return NULL;
     790             : 
     791       96771 :         if (isbranch(t) && bp.index == t->branch.index && bp.flags == t->branch.flags) {
     792             :                 // The node t needs a new leaf child.
     793       67603 :                 bitmap_t b1 = twigbit(t, key, len);
     794       67603 :                 assert(!hastwig(t, b1));
     795       67603 :                 uint s, m; TWIGOFFMAX(s, m, t, b1); // new child position and original child count
     796      135206 :                 node_t *twigs = mm_realloc(&tbl->mm, t->branch.twigs,
     797       67603 :                                 sizeof(node_t) * (m + 1), sizeof(node_t) * m);
     798       67603 :                 if (unlikely(!twigs))
     799           0 :                         goto err_leaf;
     800       67603 :                 memmove(twigs + s + 1, twigs + s, sizeof(node_t) * (m - s));
     801       67603 :                 twigs[s] = leaf;
     802       67603 :                 t->branch.twigs = twigs;
     803       67603 :                 t->branch.bitmap |= b1;
     804       67603 :                 ++tbl->weight;
     805       67603 :                 return &twigs[s].leaf.val;
     806             :         } else {
     807             :                 // We need to insert a new binary branch with leaf at *t.
     808             :                 // Note: it works the same for the case where we insert above root t.
     809             :                 #ifndef NDEBUG
     810       29168 :                         if (ns->len > 1) {
     811       12521 :                                 node_t *pt = ns->stack[ns->len - 2];
     812       12521 :                                 assert(hastwig(pt, twigbit(pt, key, len)));
     813             :                         }
     814             :                 #endif
     815       29168 :                 node_t *twigs = mm_alloc(&tbl->mm, sizeof(node_t) * 2);
     816       29168 :                 if (unlikely(!twigs))
     817           0 :                         goto err_leaf;
     818       29168 :                 node_t t2 = *t; // Save before overwriting t.
     819       29168 :                 t->branch.flags = bp.flags;
     820       29168 :                 t->branch.index = bp.index;
     821       29168 :                 t->branch.twigs = twigs;
     822       29168 :                 bitmap_t b1 = twigbit(t, key, len);
     823       29168 :                 bitmap_t b2 = unlikely(k2 == -256) ? (1 << 0) : nibbit(k2, bp.flags);
     824       29168 :                 t->branch.bitmap = b1 | b2;
     825       29168 :                 *twig(t, twigoff(t, b1)) = leaf;
     826       29168 :                 *twig(t, twigoff(t, b2)) = t2;
     827       29168 :                 ++tbl->weight;
     828       29168 :                 return &twig(t, twigoff(t, b1))->leaf.val;
     829             :         };
     830           0 : err_leaf:
     831           0 :         mm_free(&tbl->mm, leaf.leaf.key);
     832           0 :         return NULL;
     833             :         }
     834             : }
     835             : 
     836             : /*! \brief Apply a function to every trie_val_t*, in order; a recursive solution. */
     837        2879 : static int apply_trie(node_t *t, int (*f)(trie_val_t *, void *), void *d)
     838             : {
     839        2879 :         assert(t);
     840        2879 :         if (!isbranch(t))
     841        2483 :                 return f(&t->leaf.val, d);
     842         396 :         int child_count = bitmap_weight(t->branch.bitmap);
     843        2734 :         for (int i = 0; i < child_count; ++i)
     844        2521 :                 ERR_RETURN(apply_trie(twig(t, i), f, d));
     845          78 :         return KNOT_EOK;
     846             : }
     847             : 
     848        7644 : int trie_apply(trie_t *tbl, int (*f)(trie_val_t *, void *), void *d)
     849             : {
     850        7644 :         assert(tbl && f);
     851        7644 :         if (!tbl->weight)
     852        7142 :                 return KNOT_EOK;
     853         358 :         return apply_trie(&tbl->root, f, d);
     854             : }
     855             : 
     856             : /* These are all thin wrappers around static Tns* functions. */
     857       29931 : trie_it_t* trie_it_begin(trie_t *tbl)
     858             : {
     859       29931 :         assert(tbl);
     860       29931 :         trie_it_t *it = malloc(sizeof(nstack_t));
     861       29931 :         if (!it)
     862           0 :                 return NULL;
     863       29931 :         ns_init(it, tbl);
     864       29931 :         if (it->len == 0) // empty tbl
     865       13382 :                 return it;
     866       15702 :         if (ns_first_leaf(it)) {
     867           0 :                 ns_cleanup(it);
     868           0 :                 free(it);
     869           0 :                 return NULL;
     870             :         }
     871       14485 :         return it;
     872             : }
     873             : 
     874       92465 : void trie_it_next(trie_it_t *it)
     875             : {
     876       92465 :         assert(it && it->len);
     877       92465 :         if (ns_next_leaf(it) != KNOT_EOK)
     878       12462 :                 it->len = 0;
     879       92465 : }
     880             : 
     881      122396 : bool trie_it_finished(trie_it_t *it)
     882             : {
     883      122396 :         assert(it);
     884      122396 :         return it->len == 0;
     885             : }
     886             : 
     887       29931 : void trie_it_free(trie_it_t *it)
     888             : {
     889       29931 :         if (!it)
     890           0 :                 return;
     891       29931 :         ns_cleanup(it);
     892       29931 :         free(it);
     893             : }
     894             : 
     895       95704 : const char* trie_it_key(trie_it_t *it, size_t *len)
     896             : {
     897       95704 :         assert(it && it->len);
     898       95704 :         node_t *t = it->stack[it->len - 1];
     899       95704 :         assert(!isbranch(t));
     900       95704 :         tkey_t *key = t->leaf.key;
     901       95704 :         if (len)
     902        8676 :                 *len = key->len;
     903       95704 :         return key->chars;
     904             : }
     905             : 
     906       95705 : trie_val_t* trie_it_val(trie_it_t *it)
     907             : {
     908       95705 :         assert(it && it->len);
     909       95705 :         node_t *t = it->stack[it->len - 1];
     910       95705 :         assert(!isbranch(t));
     911       95705 :         return &t->leaf.val;
     912             : }

Generated by: LCOV version 1.13