From 4eeae2264cf32e67a0aac46293752251328e2745 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Sat, 20 Apr 2019 12:05:43 -0400
Subject: trie: Make trie_remove() take a leaf instead of a key

---
 trie.c | 51 ++++++++++++++++-----------------------------------
 1 file changed, 16 insertions(+), 35 deletions(-)

(limited to 'trie.c')

diff --git a/trie.c b/trie.c
index c95dbfa..b9adc8c 100644
--- a/trie.c
+++ b/trie.c
@@ -614,55 +614,38 @@ static int trie_collapse_node(uintptr_t *parent, struct trie_node *parent_node,
 	return 0;
 }
 
-bool trie_remove_str(struct trie *trie, const char *key) {
-	return trie_remove_mem(trie, key, strlen(key) + 1);
-}
-
-bool trie_remove_mem(struct trie *trie, const void *key, size_t length) {
+void trie_remove(struct trie *trie, struct trie_leaf *leaf) {
 	uintptr_t *child = &trie->root;
-	if (!*child) {
-		return false;
-	}
-
 	uintptr_t *parent = NULL;
 	unsigned int child_bit = 0, child_index = 0;
 	size_t offset = 0;
 	while (!trie_is_leaf(*child)) {
 		struct trie_node *node = trie_decode_node(*child);
 		offset += node->offset;
-		if ((offset >> 1) >= length) {
-			return false;
-		}
+		assert((offset >> 1) < leaf->length);
 
-		unsigned char nibble = trie_key_nibble(key, offset);
+		unsigned char nibble = trie_key_nibble(leaf->key, offset);
 		unsigned int bit = 1U << nibble;
 		unsigned int bitmap = node->bitmap;
-		if (bitmap & bit) {
-			unsigned int index = trie_popcount(bitmap & (bit - 1));
-
-			// Advance the parent pointer, unless this node had only
-			// one child
-			if (bitmap & (bitmap - 1)) {
-				parent = child;
-				child_bit = bit;
-				child_index = index;
-			}
-
-			child = node->children + index;
-		} else {
-			return false;
+		assert(bitmap & bit);
+		unsigned int index = trie_popcount(bitmap & (bit - 1));
+
+		// Advance the parent pointer, unless this node had only one child
+		if (bitmap & (bitmap - 1)) {
+			parent = child;
+			child_bit = bit;
+			child_index = index;
 		}
-	}
 
-	const struct trie_leaf *leaf = trie_decode_leaf(*child);
-	if (leaf->length != length || memcmp(leaf->key, key, length) != 0) {
-		return false;
+		child = node->children + index;
 	}
 
+	assert(trie_decode_leaf(*child) == leaf);
+
 	if (!parent) {
 		trie_free_singletons(trie->root);
 		trie->root = 0;
-		return true;
+		return;
 	}
 
 	struct trie_node *node = trie_decode_node(*parent);
@@ -673,7 +656,7 @@ bool trie_remove_mem(struct trie *trie, const void *key, size_t length) {
 	unsigned int parent_size = trie_popcount(node->bitmap);
 	assert(parent_size > 0);
 	if (parent_size == 1 && trie_collapse_node(parent, node, child_index) == 0) {
-		return true;
+		return;
 	}
 
 	if (child_index < parent_size) {
@@ -686,8 +669,6 @@ bool trie_remove_mem(struct trie *trie, const void *key, size_t length) {
 			*parent = trie_encode_node(node);
 		}
 	}
-
-	return true;
 }
 
 /** Free an encoded pointer to a node. */
-- 
cgit v1.2.3