trie: Make trie_remove() take a leaf instead of a key

5 files changed, 27 insertions, 62 deletions

diff --git a/color.c b/color.c
index c6e58cd..17d59e6 100644
--- a/color.c
+++ b/color.c
@@ -160,7 +160,7 @@ static int set_ext_color(struct colors *colors, char *key, const char *value) {
 	struct trie_leaf *match;
 	while ((match = trie_find_postfix(&colors->ext_colors, key))) {
 		dstrfree(match->value);
-		trie_remove_mem(&colors->ext_colors, match->key, match->length);
+		trie_remove(&colors->ext_colors, match);
 	}
 
 	struct trie_leaf *leaf = trie_insert_str(&colors->ext_colors, key);
@@ -473,14 +473,14 @@ void free_colors(struct colors *colors) {
 		struct trie_leaf *leaf;
 		while ((leaf = trie_first_leaf(&colors->ext_colors))) {
 			dstrfree(leaf->value);
-			trie_remove_mem(&colors->ext_colors, leaf->key, leaf->length);
+			trie_remove(&colors->ext_colors, leaf);
 		}
 		trie_destroy(&colors->ext_colors);
 
 		while ((leaf = trie_first_leaf(&colors->names))) {
 			char **field = leaf->value;
 			dstrfree(*field);
-			trie_remove_mem(&colors->names, leaf->key, leaf->length);
+			trie_remove(&colors->names, leaf);
 		}
 		trie_destroy(&colors->names);
 
diff --git a/mtab.c b/mtab.c
index ed80030..63c04ac 100644
--- a/mtab.c
+++ b/mtab.c
@@ -77,7 +77,7 @@ static int bfs_mtab_add(struct bfs_mtab *mtab, const char *path, dev_t dev, cons
 	if (leaf->value) {
 		return 0;
 	} else {
-		trie_remove_mem(&mtab->types, leaf->key, leaf->length);
+		trie_remove(&mtab->types, leaf);
 		return -1;
 	}
 }
@@ -220,7 +220,7 @@ void free_bfs_mtab(struct bfs_mtab *mtab) {
 		struct trie_leaf *leaf;
 		while ((leaf = trie_first_leaf(&mtab->types))) {
 			free(leaf->value);
-			trie_remove_mem(&mtab->types, leaf->key, leaf->length);
+			trie_remove(&mtab->types, leaf);
 		}
 		trie_destroy(&mtab->types);
 
diff --git a/parse.c b/parse.c
index f60a963..e2a3dbf 100644
--- a/parse.c
+++ b/parse.c
@@ -274,7 +274,7 @@ int free_cmdline(struct cmdline *cmdline) {
 			}
 
 			free(ofile);
-			trie_remove_mem(&cmdline->open_files, leaf->key, leaf->length);
+			trie_remove(&cmdline->open_files, leaf);
 		}
 		trie_destroy(&cmdline->open_files);
 
@@ -438,7 +438,7 @@ static int expr_open(struct parser_state *state, struct expr *expr, const char *
 	struct open_file *ofile = malloc(sizeof(*ofile));
 	if (!ofile) {
 		perror("malloc()");
-		trie_remove_mem(&cmdline->open_files, leaf->key, leaf->length);
+		trie_remove(&cmdline->open_files, leaf);
 		goto out_close;
 	}
 
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. */
diff --git a/trie.h b/trie.h
index ae554e7..7b073f1 100644
--- a/trie.h
+++ b/trie.h
@@ -140,30 +140,14 @@ struct trie_leaf *trie_insert_str(struct trie *trie, const char *key);
 struct trie_leaf *trie_insert_mem(struct trie *trie, const void *key, size_t length);
 
 /**
- * Remove a string key from a trie.
+ * Remove a leaf from a trie.
  *
  * @param trie
  *         The trie to modify.
- * @param key
- *         The key to remove.
- * @return
- *         Whether the key was found.
- */
-bool trie_remove_str(struct trie *trie, const char *key);
-
-/**
- * Remove a fixed-size key from a trie.
- *
- * @param trie
- *         The trie to modify.
- * @param key
- *         The key to remove.
- * @param size
- *         The size of the key in bytes.
- * @return
- *         Whether the key was found.
+ * @param leaf
+ *         The leaf to remove.
  */
-bool trie_remove_mem(struct trie *trie, const void *key, size_t size);
+void trie_remove(struct trie *trie, struct trie_leaf *leaf);
 
 /**
  * Destroy a trie and its contents.