summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2023-06-19 16:58:45 -0400
committerTavian Barnes <tavianator@tavianator.com>2023-06-20 14:26:09 -0400
commit4b177a01a7f4e83f67af2200ec69505b75a3c399 (patch)
tree576028dbd29a0eae452ecd6b7de929de211a6d64
parent1649d37f7c88f8a5930fdd4c1ff1b59212da90ee (diff)
downloadbfs-4b177a01a7f4e83f67af2200ec69505b75a3c399.tar.xz
trie: Arena-allocate nodes and leaves
-rw-r--r--src/trie.c65
-rw-r--r--src/trie.h5
2 files changed, 36 insertions, 34 deletions
diff --git a/src/trie.c b/src/trie.c
index 19423cf..992d42b 100644
--- a/src/trie.c
+++ b/src/trie.c
@@ -166,6 +166,8 @@ static uintptr_t trie_encode_node(const struct trie_node *node) {
void trie_init(struct trie *trie) {
trie->root = 0;
LIST_INIT(trie);
+ VARENA_INIT(&trie->nodes, struct trie_node, children);
+ VARENA_INIT(&trie->leaves, struct trie_leaf, key);
}
/** Extract the nibble at a certain offset from a byte sequence. */
@@ -318,7 +320,7 @@ 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 *trie_leaf_alloc(struct trie *trie, const void *key, size_t length) {
- struct trie_leaf *leaf = ALLOC_FLEX(struct trie_leaf, key, length);
+ struct trie_leaf *leaf = varena_alloc(&trie->leaves, length);
if (!leaf) {
return NULL;
}
@@ -335,15 +337,26 @@ static struct trie_leaf *trie_leaf_alloc(struct trie *trie, const void *key, siz
/** Free a leaf. */
static void trie_leaf_free(struct trie *trie, struct trie_leaf *leaf) {
LIST_REMOVE(trie, leaf);
- free(leaf);
+ varena_free(&trie->leaves, leaf, leaf->length);
}
-/** Compute the size of a trie node with a certain number of children. */
-static size_t trie_node_size(unsigned int size) {
- // Node size must be a power of two
+/** Create a new node. */
+static struct trie_node *trie_node_alloc(struct trie *trie, size_t size) {
bfs_assert(has_single_bit(size));
+ return varena_alloc(&trie->nodes, size);
+}
+
+/** Reallocate a trie node. */
+static struct trie_node *trie_node_realloc(struct trie *trie, struct trie_node *node, size_t old_size, size_t new_size) {
+ bfs_assert(has_single_bit(old_size));
+ bfs_assert(has_single_bit(new_size));
+ return varena_realloc(&trie->nodes, node, old_size, new_size);
+}
- return sizeof_flex(struct trie_node, children, size);
+/** Free a node. */
+static void trie_node_free(struct trie *trie, struct trie_node *node, size_t size) {
+ bfs_assert(size == (size_t)count_ones(node->bitmap));
+ varena_free(&trie->nodes, node, size);
}
#if ENDIAN_NATIVE == ENDIAN_LITTLE
@@ -422,7 +435,7 @@ static struct trie_leaf *trie_node_insert(struct trie *trie, uintptr_t *ptr, str
// Double the capacity every power of two
if (has_single_bit(size)) {
- node = realloc(node, trie_node_size(2 * size));
+ node = trie_node_realloc(trie, node, size, 2 * size);
if (!node) {
trie_leaf_free(trie, leaf);
return NULL;
@@ -469,12 +482,12 @@ static struct trie_leaf *trie_node_insert(struct trie *trie, uintptr_t *ptr, str
* | Y
* +--->key
*/
-static uintptr_t *trie_jump(uintptr_t *ptr, const char *key, size_t *offset) {
+static uintptr_t *trie_jump(struct trie *trie, uintptr_t *ptr, const char *key, size_t *offset) {
// We only ever need to jump to leaf nodes, since internal nodes are
// guaranteed to be within OFFSET_MAX anyway
bfs_assert(trie_is_leaf(*ptr));
- struct trie_node *node = malloc(trie_node_size(1));
+ struct trie_node *node = trie_node_alloc(trie, 1);
if (!node) {
return NULL;
}
@@ -512,7 +525,7 @@ static struct trie_leaf *trie_split(struct trie *trie, uintptr_t *ptr, struct tr
unsigned char rep_nibble = trie_key_nibble(rep->key, mismatch);
bfs_assert(key_nibble != rep_nibble);
- struct trie_node *node = malloc(trie_node_size(2));
+ struct trie_node *node = trie_node_alloc(trie, 2);
if (!node) {
trie_leaf_free(trie, leaf);
return NULL;
@@ -578,7 +591,7 @@ static struct trie_leaf *trie_insert_mem_impl(struct trie *trie, const void *key
}
while (mismatch - offset > OFFSET_MAX) {
- ptr = trie_jump(ptr, key, &offset);
+ ptr = trie_jump(trie, ptr, key, &offset);
if (!ptr) {
trie_leaf_free(trie, leaf);
return NULL;
@@ -601,7 +614,7 @@ static void trie_free_singletons(struct trie *trie, uintptr_t ptr) {
bfs_assert(has_single_bit(node->bitmap));
ptr = node->children[0];
- free(node);
+ trie_node_free(trie, node, 1);
}
trie_leaf_free(trie, trie_decode_leaf(ptr));
@@ -624,7 +637,7 @@ static void trie_free_singletons(struct trie *trie, uintptr_t ptr) {
* v
* other
*/
-static int trie_collapse_node(uintptr_t *parent, struct trie_node *parent_node, unsigned int child_index) {
+static int trie_collapse_node(struct trie *trie, uintptr_t *parent, struct trie_node *parent_node, unsigned int child_index) {
uintptr_t other = parent_node->children[child_index ^ 1];
if (!trie_is_leaf(other)) {
struct trie_node *other_node = trie_decode_node(other);
@@ -636,7 +649,7 @@ static int trie_collapse_node(uintptr_t *parent, struct trie_node *parent_node,
}
*parent = other;
- free(parent_node);
+ trie_node_free(trie, parent_node, 1);
return 0;
}
@@ -682,7 +695,7 @@ static void trie_remove_impl(struct trie *trie, struct trie_leaf *leaf) {
node->bitmap ^= child_bit;
unsigned int parent_size = count_ones(node->bitmap);
bfs_assert(parent_size > 0);
- if (parent_size == 1 && trie_collapse_node(parent, node, child_index) == 0) {
+ if (parent_size == 1 && trie_collapse_node(trie, parent, node, child_index) == 0) {
return;
}
@@ -691,7 +704,7 @@ static void trie_remove_impl(struct trie *trie, struct trie_leaf *leaf) {
}
if (has_single_bit(parent_size)) {
- node = realloc(node, trie_node_size(parent_size));
+ node = trie_node_realloc(trie, node, 2 * parent_size, parent_size);
if (node) {
*parent = trie_encode_node(node);
}
@@ -702,23 +715,7 @@ void trie_remove(struct trie *trie, struct trie_leaf *leaf) {
trie_remove_impl(trie, leaf);
}
-/** Free an encoded pointer to a node. */
-TARGET_CLONES_POPCNT
-static void free_trie_ptr(uintptr_t ptr) {
- if (trie_is_leaf(ptr)) {
- free(trie_decode_leaf(ptr));
- } else {
- struct trie_node *node = trie_decode_node(ptr);
- size_t size = count_ones(node->bitmap);
- for (size_t i = 0; i < size; ++i) {
- free_trie_ptr(node->children[i]);
- }
- free(node);
- }
-}
-
void trie_destroy(struct trie *trie) {
- if (trie->root) {
- free_trie_ptr(trie->root);
- }
+ varena_destroy(&trie->leaves);
+ varena_destroy(&trie->nodes);
}
diff --git a/src/trie.h b/src/trie.h
index 6bd211e..6921f62 100644
--- a/src/trie.h
+++ b/src/trie.h
@@ -5,6 +5,7 @@
#define BFS_TRIE_H
#include "config.h"
+#include "alloc.h"
#include <stddef.h>
#include <stdint.h>
@@ -30,6 +31,10 @@ struct trie {
uintptr_t root;
/** Linked list of leaves. */
struct trie_leaf *head, *tail;
+ /** Node allocator. */
+ struct varena nodes;
+ /** Leaf allocator. */
+ struct varena leaves;
};
/**