diff options
| -rw-r--r-- | src/trie.c | 8 | ||||
| -rw-r--r-- | src/trie.h | 6 | ||||
| -rw-r--r-- | tests/trie.c | 7 |
3 files changed, 4 insertions, 17 deletions
@@ -87,7 +87,6 @@ #include "bfs.h" #include "bit.h" #include "diag.h" -#include "list.h" #include <stdint.h> #include <string.h> @@ -165,7 +164,6 @@ static uintptr_t trie_encode_leaf(const struct trie_leaf *leaf) { void trie_init(struct trie *trie) { trie->root = 0; - LIST_INIT(trie); VARENA_INIT(&trie->nodes, struct trie_node, children); VARENA_INIT(&trie->leaves, struct trie_leaf, key); } @@ -339,9 +337,6 @@ static struct trie_leaf *trie_leaf_alloc(struct trie *trie, const void *key, siz return NULL; } - LIST_ITEM_INIT(leaf); - LIST_APPEND(trie, leaf); - leaf->value = NULL; leaf->length = length; memcpy(leaf->key, key, length); @@ -351,7 +346,6 @@ 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) { - LIST_REMOVE(trie, leaf); varena_free(&trie->leaves, leaf); } @@ -736,8 +730,6 @@ void trie_remove(struct trie *trie, struct trie_leaf *leaf) { void trie_clear(struct trie *trie) { trie->root = 0; - LIST_INIT(trie); - varena_clear(&trie->leaves); varena_clear(&trie->nodes); } @@ -14,8 +14,6 @@ * 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. */ @@ -30,8 +28,6 @@ struct trie_leaf { 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. */ @@ -143,6 +139,6 @@ 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) + for_varena (struct trie_leaf, leaf, &(trie)->leaves) #endif // BFS_TRIE_H diff --git a/tests/trie.c b/tests/trie.c index 6e6024a..d69f37e 100644 --- a/tests/trie.c +++ b/tests/trie.c @@ -71,15 +71,14 @@ void check_trie(void) { bfs_verify(leaf); bfs_check(strcmp(keys[i], leaf->key) == 0); bfs_check(leaf->length == strlen(keys[i]) + 1); + leaf->value = (void *)keys[i]; } { size_t i = 0; for_trie (leaf, &trie) { - bfs_check(leaf == trie_find_str(&trie, keys[i])); - bfs_check(leaf == trie_insert_str(&trie, keys[i])); - bfs_check(!leaf->prev || leaf->prev->next == leaf); - bfs_check(!leaf->next || leaf->next->prev == leaf); + bfs_check(strcmp(leaf->value, leaf->key) == 0); + leaf->value = NULL; ++i; } bfs_check(i == nkeys); |