summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--color.c6
-rw-r--r--mtab.c4
-rw-r--r--parse.c4
-rw-r--r--trie.c51
-rw-r--r--trie.h24
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.
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-25 14:33:58 +0000