From ba2d4ac206ff1321ea953d3305d8bda048922983 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Tue, 28 Mar 2023 15:34:43 -0400
Subject: trie: Use list.h for the list of leaves

---
 src/trie.c   | 28 ++++------------------------
 src/trie.h   | 31 ++++++++++---------------------
 tests/trie.c |  2 --
 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);
-- 
cgit v1.2.3