From b8a09ae02ddb97e854d82112dd8fcb6947c3c54a Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Fri, 28 Oct 2022 20:59:23 -0400 Subject: trie: Make leaves into a linked list --- src/trie.h | 41 ++++++++++++++++++++++++----------------- 1 file changed, 24 insertions(+), 17 deletions(-) (limited to 'src/trie.h') diff --git a/src/trie.h b/src/trie.h index 2d29ac7..2ede6ea 100644 --- a/src/trie.h +++ b/src/trie.h @@ -1,6 +1,6 @@ /**************************************************************************** * bfs * - * Copyright (C) 2019 Tavian Barnes * + * Copyright (C) 2019-2022 Tavian Barnes * * * * Permission to use, copy, modify, and/or distribute this software for any * * purpose with or without fee is hereby granted. * @@ -17,20 +17,19 @@ #ifndef BFS_TRIE_H #define BFS_TRIE_H +#include #include #include -/** - * 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. */ @@ -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 -- cgit v1.2.3