aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--bitmapped_patricia_tree.c59
-rw-r--r--bitmapped_patricia_tree.h5
-rw-r--r--bpt_test.c11
3 files changed, 59 insertions, 16 deletions
diff --git a/bitmapped_patricia_tree.c b/bitmapped_patricia_tree.c
index 42985c5..0351a60 100644
--- a/bitmapped_patricia_tree.c
+++ b/bitmapped_patricia_tree.c
@@ -84,6 +84,26 @@ struct bpt_node {
};
+// Forward declarations.
+void init_bpt_leaf(bpt_t leaf, bpt_key_t key, void *value);
+bpt_t bpt_make_leaf(bpt_key_t key, void *value);
+
+
+// Boilerplate definitions.
+void bpt_retain0(bpt_t bpt, void *user_data) {
+ bpt_retain(bpt);
+}
+
+void bpt_seal0(bpt_t bpt, void *user_data) {
+ bpt_seal(bpt);
+}
+
+void bpt_release0(bpt_t bpt, void *user_data) {
+ bpt_release(bpt);
+}
+
+
+// Implementation.
void init_bpt_leaf(bpt_t a_leaf, bpt_key_t key, void *value) {
bpt_leaf_t leaf = (bpt_leaf_t)a_leaf;
leaf->bpt.tag = BPT_LEAF;
@@ -128,16 +148,16 @@ static inline uint_fast8_t bpt_offset_of_key(bpt_key_t key, unsigned int branchi
static bpt_key_t bpt_prefix_of_key(bpt_key_t key, unsigned int branching_chunk);
static inline unsigned int bpt_branching_chunk(bpt_t bpt);
static unsigned int bpt_find_diverging_chunk(bpt_key_t key1, bpt_key_t key2);
-static void bpt_for_children(bpt_t bpt, void (*thunk)(bpt_t));
+static void bpt_for_children(bpt_t bpt, void (*thunk)(bpt_t, void*), void *user_data);
-static void bpt_for_children(bpt_t bpt, void (*thunk)(bpt_t)) {
+static void bpt_for_children(bpt_t bpt, void (*thunk)(bpt_t, void*), void *user_data) {
if (bpt && bpt->tag == BPT_INNER_NODE) {
bpt_node_t b = (bpt_node_t)bpt;
bpt_t *iter = b->children;
bpt_t *children_end = b->children + bpt_popcount(b->bitmask);
while (iter < children_end) {
- thunk(*iter);
+ thunk(*iter, user_data);
iter++;
}
}
@@ -249,7 +269,7 @@ bpt_t bpt_assoc(bpt_t bpt, bpt_key_t key, void *value) {
memcpy(new_node->children, b->children, size_of_child_array);
new_node->children[child_index] = new_child;
// Retain the children copied into the new node.
- bpt_for_children((bpt_t)new_node, bpt_retain);
+ bpt_for_children((bpt_t)new_node, bpt_retain0, NULL);
bpt_release(new_child);
return (bpt_t)new_node;
}
@@ -276,7 +296,7 @@ bpt_t bpt_assoc(bpt_t bpt, bpt_key_t key, void *value) {
new_node->children = new_children;
new_node->bitmask = b->bitmask | (1 << child_number);
// Retain the children copied into the new node.
- bpt_for_children(bpt, bpt_retain);
+ bpt_for_children(bpt, bpt_retain0, NULL);
return (bpt_t)new_node;
}
}
@@ -349,7 +369,7 @@ bpt_t bpt_dissoc(bpt_t bpt, bpt_key_t key) {
new_node->children = new_children;
new_node->bitmask = bitmask;
// Retain the children copied into the new node.
- bpt_for_children((bpt_t)new_node, bpt_retain);
+ bpt_for_children((bpt_t)new_node, bpt_retain0, NULL);
bpt_release(new_child);
return (bpt_t)new_node;
}
@@ -367,7 +387,7 @@ void bpt_seal(bpt_t bpt) {
if (bpt->mutable) {
bpt->mutable = false;
if (bpt->tag == BPT_INNER_NODE) {
- bpt_for_children(bpt, bpt_seal);
+ bpt_for_children(bpt, bpt_seal0, NULL);
}
}
}
@@ -459,7 +479,7 @@ void bpt_dealloc(bpt_t bpt) {
free(b);
} else {
bpt_node_t b = (bpt_node_t)bpt;
- bpt_for_children(bpt, bpt_release);
+ bpt_for_children(bpt, bpt_release0, NULL);
free(b->children);
free(b);
}
@@ -477,3 +497,26 @@ void bpt_set_dealloc_hook(bpt_t bpt, bpt_key_t key, void (*hook)(bpt_key_t, void
bpt_leaf_set_dealloc_hook(bpt_get_leaf(bpt, key), hook);
}
#endif
+
+
+
+/* Utilities */
+struct bpt_for_mappings_closure_data {
+ void (*thunk)(bpt_key_t, void*, void*);
+ void *user_data;
+};
+static void bpt_for_mappings_iter(bpt_t bpt, void *closure_data_) {
+ struct bpt_for_mappings_closure_data *closure_data = closure_data_;
+ if (bpt->tag == BPT_LEAF) {
+ bpt_leaf_t leaf = (bpt_leaf_t)bpt;
+ closure_data->thunk(bpt->prefix, leaf->value, closure_data->user_data);
+ } else {
+ bpt_for_children(bpt, bpt_for_mappings_iter, closure_data);
+ }
+}
+void bpt_for_mappings(bpt_t bpt, void (*thunk)(bpt_key_t, void*, void*), void *user_data) {
+ struct bpt_for_mappings_closure_data closure_data =
+ { .user_data = user_data, .thunk = thunk };
+
+ bpt_for_mappings_iter(bpt, &closure_data);
+}
diff --git a/bitmapped_patricia_tree.h b/bitmapped_patricia_tree.h
index f1d65c3..4807256 100644
--- a/bitmapped_patricia_tree.h
+++ b/bitmapped_patricia_tree.h
@@ -48,18 +48,19 @@ enum bpt_tag {
struct bpt;
typedef struct bpt *bpt_t;
+// Base functionality.
void *bpt_get(bpt_t bpt, bpt_key_t key);
bool bpt_has_key(bpt_t bpt, bpt_key_t key);
void **bpt_get_pointer(bpt_t bpt, bpt_key_t key);
bpt_t bpt_assoc(bpt_t bpt, bpt_key_t key, void *item);
bpt_t bpt_dissoc(bpt_t bpt, bpt_key_t key);
-void init_bpt_leaf(bpt_t leaf, bpt_key_t key, void *value);
-bpt_t bpt_make_leaf(bpt_key_t key, void *value);
void bpt_retain(bpt_t bpt);
void bpt_release(bpt_t bpt);
void bpt_dealloc(bpt_t bpt);
void bpt_seal(bpt_t bpt);
+// Utilities
+void bpt_for_mappings(bpt_t bpt, void (*thunk)(bpt_key_t, void*, void*), void *user_data);
#ifdef BPT_ENABLE_DEALLOC_HOOKS
void bpt_set_dealloc_hook(bpt_t bpt, bpt_key_t key, void (*hook)(bpt_key_t key, void* value));
#endif
diff --git a/bpt_test.c b/bpt_test.c
index 9f57152..225baa0 100644
--- a/bpt_test.c
+++ b/bpt_test.c
@@ -6,13 +6,12 @@ void print_deallocation(bpt_key_t key, void *value) {
printf("Deallocated: %s\n", value);
}
+void print_mapping(bpt_key_t key, void *value, void *user_data) {
+ printf(" %d -> %s\n", key, value);
+}
+
void print_tree(bpt_t b) {
- int i;
- for (i = 0; i < 10; i++) {
- if (bpt_has_key(b, i)) {
- printf(" %d -> %s\n", i, bpt_get(b, i));
- }
- }
+ bpt_for_mappings(b, print_mapping, NULL);
}
bpt_t bpt_assoc_and_release(bpt_t bpt, bpt_key_t key, void *value) {