diff options
Diffstat (limited to 'src/trie.h')
-rw-r--r-- | src/trie.h | 147 |
1 files changed, 147 insertions, 0 deletions
diff --git a/src/trie.h b/src/trie.h new file mode 100644 index 0000000..4288d76 --- /dev/null +++ b/src/trie.h @@ -0,0 +1,147 @@ +// Copyright © Tavian Barnes <tavianator@tavianator.com> +// SPDX-License-Identifier: 0BSD + +#ifndef BFS_TRIE_H +#define BFS_TRIE_H + +#include "alloc.h" +#include "list.h" +#include <stddef.h> +#include <stdint.h> + +/** + * A leaf of a trie. + */ +struct trie_leaf { + /** Linked list of leaves, in insertion order. */ + struct trie_leaf *prev, *next; + /** An arbitrary value associated with this leaf. */ + void *value; + /** The length of the key in bytes. */ + size_t length; + /** The key itself, stored inline. */ + char key[]; +}; + +/** + * A trie that holds a set of fixed- or variable-length strings. + */ +struct trie { + /** Pointer to the root node/leaf. */ + uintptr_t root; + /** Linked list of leaves. */ + struct trie_leaf *head, *tail; + /** Node allocator. */ + struct varena nodes; + /** Leaf allocator. */ + struct varena leaves; +}; + +/** + * Initialize an empty trie. + */ +void trie_init(struct trie *trie); + +/** + * Find the leaf for a string key. + * + * @param trie + * The trie to search. + * @param key + * The key to look up. + * @return + * The found leaf, or NULL if the key is not present. + */ +struct trie_leaf *trie_find_str(const struct trie *trie, const char *key); + +/** + * Find the leaf for a fixed-size key. + * + * @param trie + * The trie to search. + * @param key + * The key to look up. + * @param length + * The length of the key in bytes. + * @return + * The found leaf, or NULL if the key is not present. + */ +struct trie_leaf *trie_find_mem(const struct trie *trie, const void *key, size_t length); + +/** + * Find the shortest leaf that starts with a given key. + * + * @param trie + * The trie to search. + * @param key + * The key to look up. + * @return + * A leaf that starts with the given key, or NULL. + */ +struct trie_leaf *trie_find_postfix(const struct trie *trie, const char *key); + +/** + * Find the leaf that is the longest prefix of the given key. + * + * @param trie + * The trie to search. + * @param key + * The key to look up. + * @return + * The longest prefix match for the given key, or NULL. + */ +struct trie_leaf *trie_find_prefix(const struct trie *trie, const char *key); + +/** + * Insert a string key into the trie. + * + * @param trie + * The trie to modify. + * @param key + * The key to insert. + * @return + * The inserted leaf, or NULL on failure. + */ +struct trie_leaf *trie_insert_str(struct trie *trie, const char *key); + +/** + * Insert a fixed-size key into the trie. + * + * @param trie + * The trie to modify. + * @param key + * The key to insert. + * @param length + * The length of the key in bytes. + * @return + * The inserted leaf, or NULL on failure. + */ +struct trie_leaf *trie_insert_mem(struct trie *trie, const void *key, size_t length); + +/** + * Remove a leaf from a trie. + * + * @param trie + * The trie to modify. + * @param leaf + * The leaf to remove. + */ +void trie_remove(struct trie *trie, struct trie_leaf *leaf); + +/** + * Remove all leaves from a trie. + */ +void trie_clear(struct trie *trie); + +/** + * Destroy a trie and its contents. + */ +void trie_destroy(struct trie *trie); + +/** + * Iterate over the leaves of a trie. + */ +#define for_trie(leaf, trie) \ + for_list (struct trie_leaf, leaf, trie) + +#endif // BFS_TRIE_H |