trie: Make leaves into a linked list

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