summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/trie.c28
-rw-r--r--src/trie.h31
-rw-r--r--tests/trie.c2
3 files changed, 14 insertions, 47 deletions
diff --git a/src/trie.c b/src/trie.c
index 77c43cc..7b00f4b 100644
--- a/src/trie.c
+++ b/src/trie.c
@@ -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);
}
diff --git a/src/trie.h b/src/trie.h
index 03ee64d..6e1e875 100644
--- a/src/trie.h
+++ b/src/trie.h
@@ -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);