diff options
Diffstat (limited to 'src/trie.h')
| -rw-r--r-- | src/trie.h | 41 |
1 files changed, 24 insertions, 17 deletions
@@ -1,6 +1,6 @@ /**************************************************************************** * bfs * - * Copyright (C) 2019 Tavian Barnes <tavianator@tavianator.com> * + * Copyright (C) 2019-2022 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. * @@ -17,21 +17,20 @@ #ifndef BFS_TRIE_H #define BFS_TRIE_H +#include <stdbool.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 { /** + * Linked list of leaves, in insertion order. + */ + struct trie_leaf *prev, *next; + + /** * An arbitrary value associated with this leaf. */ void *value; @@ -48,19 +47,19 @@ struct trie_leaf { }; /** - * Initialize an empty trie. + * A trie that holds a set of fixed- or variable-length strings. */ -void trie_init(struct trie *trie); +struct trie { + /** Pointer to the root node/leaf. */ + uintptr_t root; + /** Linked list of leaves. */ + struct trie_leaf *head, *tail; +}; /** - * Get the first (lexicographically earliest) leaf in the trie. - * - * @param trie - * The trie to search. - * @return - * The first leaf, or NULL if the trie is empty. + * Initialize an empty trie. */ -struct trie_leaf *trie_first_leaf(const struct trie *trie); +void trie_init(struct trie *trie); /** * Find the leaf for a string key. @@ -153,4 +152,12 @@ void trie_remove(struct trie *trie, struct trie_leaf *leaf); */ void trie_destroy(struct trie *trie); +/** + * Iterate over the leaves of a trie. + */ +#define TRIE_FOR_EACH(trie, leaf) \ + for (struct trie_leaf *leaf = (trie)->head, *_next; \ + leaf && (_next = leaf->next, true); \ + leaf = _next) + #endif // BFS_TRIE_H |