summaryrefslogtreecommitdiffstats
path: root/src/trie.c
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2022-10-28 20:59:23 -0400
committerTavian Barnes <tavianator@tavianator.com>2022-10-29 11:24:19 -0400
commitb8a09ae02ddb97e854d82112dd8fcb6947c3c54a (patch)
treeff257d993a4fb295a19204c5a0968e750025e44e /src/trie.c
parentdd13a1deee5bda50e76046baa7290b4e0991feea (diff)
downloadbfs-b8a09ae02ddb97e854d82112dd8fcb6947c3c54a.tar.xz
trie: Make leaves into a linked list
Diffstat (limited to 'src/trie.c')
-rw-r--r--src/trie.c69
1 files changed, 49 insertions, 20 deletions
diff --git a/src/trie.c b/src/trie.c
index b38ff68..bde1e39 100644
--- a/src/trie.c
+++ b/src/trie.c
@@ -172,6 +172,8 @@ 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;
}
/** Check if a number is a power of two. */
@@ -242,10 +244,6 @@ static struct trie_leaf *trie_representative(const struct trie *trie, const void
return trie_decode_leaf(ptr);
}
-struct trie_leaf *trie_first_leaf(const struct trie *trie) {
- return trie_representative(trie, NULL, 0);
-}
-
struct trie_leaf *trie_find_str(const struct trie *trie, const char *key) {
return trie_find_mem(trie, key, strlen(key) + 1);
}
@@ -342,16 +340,47 @@ struct trie_leaf *trie_find_prefix(const struct trie *trie, const char *key) {
}
/** Create a new leaf, holding a copy of the given key. */
-static struct trie_leaf *new_trie_leaf(const void *key, size_t length) {
+static struct trie_leaf *trie_leaf_alloc(struct trie *trie, const void *key, size_t length) {
struct trie_leaf *leaf = malloc(BFS_FLEX_SIZEOF(struct trie_leaf, key, length));
- if (leaf) {
- leaf->value = NULL;
- leaf->length = length;
- memcpy(leaf->key, key, length);
+ if (!leaf) {
+ return NULL;
+ }
+
+ leaf->prev = trie->tail;
+ leaf->next = NULL;
+
+ if (leaf->prev) {
+ leaf->prev->next = leaf;
+ } else {
+ trie->head = leaf;
}
+
+ trie->tail = leaf;
+
+ leaf->value = NULL;
+ leaf->length = length;
+ memcpy(leaf->key, key, length);
+
return leaf;
}
+/** 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;
+ }
+
+ free(leaf);
+}
+
/** Compute the size of a trie node with a certain number of children. */
static size_t trie_node_size(unsigned int size) {
// Empty nodes aren't supported
@@ -410,7 +439,7 @@ static size_t trie_key_mismatch(const void *key1, const void *key2, size_t lengt
* | Z
* +--->...
*/
-static struct trie_leaf *trie_node_insert(uintptr_t *ptr, const void *key, size_t length, size_t offset) {
+static struct trie_leaf *trie_node_insert(struct trie *trie, uintptr_t *ptr, const void *key, size_t length, size_t offset) {
struct trie_node *node = trie_decode_node(*ptr);
unsigned int size = trie_popcount(node->bitmap);
@@ -423,7 +452,7 @@ static struct trie_leaf *trie_node_insert(uintptr_t *ptr, const void *key, size_
*ptr = trie_encode_node(node);
}
- struct trie_leaf *leaf = new_trie_leaf(key, length);
+ struct trie_leaf *leaf = trie_leaf_alloc(trie, key, length);
if (!leaf) {
return NULL;
}
@@ -507,7 +536,7 @@ static uintptr_t *trie_jump(uintptr_t *ptr, const char *key, size_t *offset) {
* | Y
* +--->key
*/
-static struct trie_leaf *trie_split(uintptr_t *ptr, const void *key, size_t length, struct trie_leaf *rep, size_t offset, size_t mismatch) {
+static struct trie_leaf *trie_split(struct trie *trie, uintptr_t *ptr, const void *key, size_t length, struct trie_leaf *rep, size_t offset, size_t mismatch) {
unsigned char key_nibble = trie_key_nibble(key, mismatch);
unsigned char rep_nibble = trie_key_nibble(rep->key, mismatch);
assert(key_nibble != rep_nibble);
@@ -517,7 +546,7 @@ static struct trie_leaf *trie_split(uintptr_t *ptr, const void *key, size_t leng
return NULL;
}
- struct trie_leaf *leaf = new_trie_leaf(key, length);
+ struct trie_leaf *leaf = trie_leaf_alloc(trie, key, length);
if (!leaf) {
free(node);
return NULL;
@@ -546,7 +575,7 @@ 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) {
struct trie_leaf *rep = trie_representative(trie, key, length);
if (!rep) {
- struct trie_leaf *leaf = new_trie_leaf(key, length);
+ struct trie_leaf *leaf = trie_leaf_alloc(trie, key, length);
if (leaf) {
trie->root = trie_encode_leaf(leaf);
}
@@ -576,7 +605,7 @@ struct trie_leaf *trie_insert_mem(struct trie *trie, const void *key, size_t len
ptr = &node->children[index];
} else {
assert(offset == mismatch);
- return trie_node_insert(ptr, key, length, offset);
+ return trie_node_insert(trie, ptr, key, length, offset);
}
}
@@ -587,11 +616,11 @@ struct trie_leaf *trie_insert_mem(struct trie *trie, const void *key, size_t len
}
}
- return trie_split(ptr, key, length, rep, offset, mismatch);
+ return trie_split(trie, ptr, key, length, rep, offset, mismatch);
}
/** Free a chain of singleton nodes. */
-static void trie_free_singletons(uintptr_t ptr) {
+static void trie_free_singletons(struct trie *trie, uintptr_t ptr) {
while (!trie_is_leaf(ptr)) {
struct trie_node *node = trie_decode_node(ptr);
@@ -602,7 +631,7 @@ static void trie_free_singletons(uintptr_t ptr) {
free(node);
}
- free(trie_decode_leaf(ptr));
+ trie_leaf_free(trie, trie_decode_leaf(ptr));
}
/**
@@ -667,14 +696,14 @@ void trie_remove(struct trie *trie, struct trie_leaf *leaf) {
assert(trie_decode_leaf(*child) == leaf);
if (!parent) {
- trie_free_singletons(trie->root);
+ trie_free_singletons(trie, trie->root);
trie->root = 0;
return;
}
struct trie_node *node = trie_decode_node(*parent);
child = node->children + child_index;
- trie_free_singletons(*child);
+ trie_free_singletons(trie, *child);
node->bitmap ^= child_bit;
unsigned int parent_size = trie_popcount(node->bitmap);