From 4eeae2264cf32e67a0aac46293752251328e2745 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sat, 20 Apr 2019 12:05:43 -0400 Subject: trie: Make trie_remove() take a leaf instead of a key --- color.c | 6 +++--- mtab.c | 4 ++-- parse.c | 4 ++-- trie.c | 51 ++++++++++++++++----------------------------------- trie.h | 24 ++++-------------------- 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. -- cgit v1.2.3