diff options
Diffstat (limited to 'src/trie.h')
| -rw-r--r-- | src/trie.h | 164 |
1 files changed, 106 insertions, 58 deletions
@@ -1,50 +1,41 @@ -/**************************************************************************** - * bfs * - * Copyright (C) 2019 Tavian Barnes <tavianator@tavianator.com> * - * * - * Permission to use, copy, modify, and/or distribute this software for any * - * purpose with or without fee is hereby granted. * - * * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. * - ****************************************************************************/ +// 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 trie that holds a set of fixed- or variable-length strings. - */ -struct trie { - uintptr_t root; -}; - -/** * A leaf of a trie. */ struct trie_leaf { - /** - * An arbitrary value associated with this 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. - */ + /** The length of the key in bytes. */ size_t length; + /** The key itself, stored inline. */ + char key[] _counted_by(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; }; /** @@ -53,47 +44,63 @@ struct trie_leaf { void trie_init(struct trie *trie); /** - * Get the first (lexicographically earliest) leaf in the trie. + * Find the leaf for a string key. * - * @param trie + * @trie * The trie to search. + * @key + * The key to look up. * @return - * The first leaf, or NULL if the trie is empty. + * The found leaf, or NULL if the key is not present. */ -struct trie_leaf *trie_first_leaf(const struct trie *trie); +struct trie_leaf *trie_find_str(const struct trie *trie, const char *key); /** - * Find the leaf for a string key. + * Find the leaf for a fixed-size key. * - * @param trie + * @trie * The trie to search. - * @param key + * @key * The key to look up. + * @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_str(const struct trie *trie, const char *key); +struct trie_leaf *trie_find_mem(const struct trie *trie, const void *key, size_t length); /** - * Find the leaf for a fixed-size key. + * Get the value associated with a string key. * - * @param trie + * @trie * The trie to search. - * @param key + * @key * The key to look up. - * @param length + * @return + * The found value, or NULL if the key is not present. + */ +void *trie_get_str(const struct trie *trie, const char *key); + +/** + * Get the value associated with a fixed-size key. + * + * @trie + * The trie to search. + * @key + * The key to look up. + * @length * The length of the key in bytes. * @return - * The found leaf, or NULL if the key is not present. + * The found value, or NULL if the key is not present. */ -struct trie_leaf *trie_find_mem(const struct trie *trie, const void *key, size_t length); +void *trie_get_mem(const struct trie *trie, const void *key, size_t length); /** * Find the shortest leaf that starts with a given key. * - * @param trie + * @trie * The trie to search. - * @param key + * @key * The key to look up. * @return * A leaf that starts with the given key, or NULL. @@ -103,9 +110,9 @@ 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 + * @trie * The trie to search. - * @param key + * @key * The key to look up. * @return * The longest prefix match for the given key, or NULL. @@ -115,9 +122,9 @@ struct trie_leaf *trie_find_prefix(const struct trie *trie, const char *key); /** * Insert a string key into the trie. * - * @param trie + * @trie * The trie to modify. - * @param key + * @key * The key to insert. * @return * The inserted leaf, or NULL on failure. @@ -127,11 +134,11 @@ struct trie_leaf *trie_insert_str(struct trie *trie, const char *key); /** * Insert a fixed-size key into the trie. * - * @param trie + * @trie * The trie to modify. - * @param key + * @key * The key to insert. - * @param length + * @length * The length of the key in bytes. * @return * The inserted leaf, or NULL on failure. @@ -139,18 +146,59 @@ struct trie_leaf *trie_insert_str(struct trie *trie, const char *key); struct trie_leaf *trie_insert_mem(struct trie *trie, const void *key, size_t length); /** + * Set the value for a string key. + * + * @trie + * The trie to modify. + * @key + * The key to insert. + * @value + * The value to set. + * @return + * 0 on success, -1 on error. + */ +int trie_set_str(struct trie *trie, const char *key, const void *value); + +/** + * Set the value for a fixed-size key. + * + * @trie + * The trie to modify. + * @key + * The key to insert. + * @length + * The length of the key in bytes. + * @value + * The value to set. + * @return + * 0 on success, -1 on error. + */ +int trie_set_mem(struct trie *trie, const void *key, size_t length, const void *value); + +/** * Remove a leaf from a trie. * - * @param trie + * @trie * The trie to modify. - * @param leaf + * @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 |