src/trie.h

   1 // Copyright © Tavian Barnes <tavianator@tavianator.com>
   2 // SPDX-License-Identifier: 0BSD
   3
   4 #ifndef BFS_TRIE_H
   5 #define BFS_TRIE_H
   6
   7 #include "config.h"
   8 #include "alloc.h"
   9 #include "list.h"
  10 #include <stddef.h>
  11 #include <stdint.h>
  12
  13 /**
  14  * A leaf of a trie.
  15  */
  16 struct trie_leaf {
  17         /** Linked list of leaves, in insertion order. */
  18         struct trie_leaf *prev, *next;
  19         /** An arbitrary value associated with this leaf. */
  20         void *value;
  21         /** The length of the key in bytes. */
  22         size_t length;
  23         /** The key itself, stored inline. */
  24         char key[];
  25 };
  26
  27 /**
  28  * A trie that holds a set of fixed- or variable-length strings.
  29  */
  30 struct trie {
  31         /** Pointer to the root node/leaf. */
  32         uintptr_t root;
  33         /** Linked list of leaves. */
  34         struct trie_leaf *head, *tail;
  35         /** Node allocator. */
  36         struct varena nodes;
  37         /** Leaf allocator. */
  38         struct varena leaves;
  39 };
  40
  41 /**
  42  * Initialize an empty trie.
  43  */
  44 void trie_init(struct trie *trie);
  45
  46 /**
  47  * Find the leaf for a string key.
  48  *
  49  * @param trie
  50  *         The trie to search.
  51  * @param key
  52  *         The key to look up.
  53  * @return
  54  *         The found leaf, or NULL if the key is not present.
  55  */
  56 struct trie_leaf *trie_find_str(const struct trie *trie, const char *key);
  57
  58 /**
  59  * Find the leaf for a fixed-size key.
  60  *
  61  * @param trie
  62  *         The trie to search.
  63  * @param key
  64  *         The key to look up.
  65  * @param length
  66  *         The length of the key in bytes.
  67  * @return
  68  *         The found leaf, or NULL if the key is not present.
  69  */
  70 struct trie_leaf *trie_find_mem(const struct trie *trie, const void *key, size_t length);
  71
  72 /**
  73  * Find the shortest leaf that starts with a given key.
  74  *
  75  * @param trie
  76  *         The trie to search.
  77  * @param key
  78  *         The key to look up.
  79  * @return
  80  *         A leaf that starts with the given key, or NULL.
  81  */
  82 struct trie_leaf *trie_find_postfix(const struct trie *trie, const char *key);
  83
  84 /**
  85  * Find the leaf that is the longest prefix of the given key.
  86  *
  87  * @param trie
  88  *         The trie to search.
  89  * @param key
  90  *         The key to look up.
  91  * @return
  92  *         The longest prefix match for the given key, or NULL.
  93  */
  94 struct trie_leaf *trie_find_prefix(const struct trie *trie, const char *key);
  95
  96 /**
  97  * Insert a string key into the trie.
  98  *
  99  * @param trie
 100  *         The trie to modify.
 101  * @param key
 102  *         The key to insert.
 103  * @return
 104  *         The inserted leaf, or NULL on failure.
 105  */
 106 struct trie_leaf *trie_insert_str(struct trie *trie, const char *key);
 107
 108 /**
 109  * Insert a fixed-size key into the trie.
 110  *
 111  * @param trie
 112  *         The trie to modify.
 113  * @param key
 114  *         The key to insert.
 115  * @param length
 116  *         The length of the key in bytes.
 117  * @return
 118  *         The inserted leaf, or NULL on failure.
 119  */
 120 struct trie_leaf *trie_insert_mem(struct trie *trie, const void *key, size_t length);
 121
 122 /**
 123  * Remove a leaf from a trie.
 124  *
 125  * @param trie
 126  *         The trie to modify.
 127  * @param leaf
 128  *         The leaf to remove.
 129  */
 130 void trie_remove(struct trie *trie, struct trie_leaf *leaf);
 131
 132 /**
 133  * Remove all leaves from a trie.
 134  */
 135 void trie_clear(struct trie *trie);
 136
 137 /**
 138  * Destroy a trie and its contents.
 139  */
 140 void trie_destroy(struct trie *trie);
 141
 142 /**
 143  * Iterate over the leaves of a trie.
 144  */
 145 #define for_trie(leaf, trie) \
 146         for_list(struct trie_leaf, leaf, trie)
 147
 148 #endif // BFS_TRIE_H