summaryrefslogtreecommitdiffstats
path: root/src/trie.h
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2022-10-28 20:59:23 -0400
committerTavian Barnes <tavianator@tavianator.com>2022-10-29 11:24:19 -0400
commitb8a09ae02ddb97e854d82112dd8fcb6947c3c54a (patch)
treeff257d993a4fb295a19204c5a0968e750025e44e /src/trie.h
parentdd13a1deee5bda50e76046baa7290b4e0991feea (diff)
downloadbfs-b8a09ae02ddb97e854d82112dd8fcb6947c3c54a.tar.xz
trie: Make leaves into a linked list
Diffstat (limited to 'src/trie.h')
-rw-r--r--src/trie.h41
1 files changed, 24 insertions, 17 deletions
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 <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