diff options
| -rw-r--r-- | src/trie.c | 28 | ||||
| -rw-r--r-- | src/trie.h | 31 | ||||
| -rw-r--r-- | tests/trie.c | 2 |
3 files changed, 14 insertions, 47 deletions
@@ -163,8 +163,7 @@ static uintptr_t trie_encode_node(const struct trie_node *node) { void trie_init(struct trie *trie) { trie->root = 0; - trie->head = NULL; - trie->tail = NULL; + list_init(&trie->leaves); } /** Check if a number is a power of two. */ @@ -341,16 +340,8 @@ static struct trie_leaf *trie_leaf_alloc(struct trie *trie, const void *key, siz return NULL; } - leaf->prev = trie->tail; - leaf->next = NULL; - - if (leaf->prev) { - leaf->prev->next = leaf; - } else { - trie->head = leaf; - } - - trie->tail = leaf; + link_init(&leaf->link); + list_append(&trie->leaves, &leaf->link); leaf->value = NULL; leaf->length = length; @@ -361,18 +352,7 @@ static struct trie_leaf *trie_leaf_alloc(struct trie *trie, const void *key, siz /** Free a leaf. */ static void trie_leaf_free(struct trie *trie, struct trie_leaf *leaf) { - if (leaf->prev) { - leaf->prev->next = leaf->next; - } else { - trie->head = leaf->next; - } - - if (leaf->next) { - leaf->next->prev = leaf->prev; - } else { - trie->tail = leaf->prev; - } - + list_remove(&trie->leaves, &leaf->link); free(leaf); } @@ -4,6 +4,8 @@ #ifndef BFS_TRIE_H #define BFS_TRIE_H +#include "config.h" +#include "list.h" #include <stdbool.h> #include <stddef.h> #include <stdint.h> @@ -12,24 +14,13 @@ * 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. - */ + /** Linked list of leaves, in insertion order. */ + struct link link; + /** 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. - */ + /** The key itself, stored inline. */ char key[]; }; @@ -40,7 +31,7 @@ struct trie { /** Pointer to the root node/leaf. */ uintptr_t root; /** Linked list of leaves. */ - struct trie_leaf *head, *tail; + struct list leaves; }; /** @@ -142,9 +133,7 @@ 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) +#define TRIE_FOR_EACH(trie, leaf) \ + LIST_FOR_EACH(&(trie)->leaves, struct trie_leaf, leaf) #endif // BFS_TRIE_H diff --git a/tests/trie.c b/tests/trie.c index c2af18a..65660a9 100644 --- a/tests/trie.c +++ b/tests/trie.c @@ -74,8 +74,6 @@ int main(void) { size_t i = 0; TRIE_FOR_EACH(&trie, leaf) { assert(leaf == trie_find_str(&trie, keys[i])); - assert(!leaf->prev || leaf->prev->next == leaf); - assert(!leaf->next || leaf->next->prev == leaf); ++i; } assert(i == nkeys); |