diff options
author | Joe Thornber <ejt@redhat.com> | 2018-05-29 13:25:59 +0100 |
---|---|---|
committer | Joe Thornber <ejt@redhat.com> | 2018-05-29 13:25:59 +0100 |
commit | c2a8bbed3bc8c5c4f505a7cecc4db0b94e7243bc (patch) | |
tree | 56f99b070d75b1922d9e08d136d4cb0fdf38237a | |
parent | 9b41efae826257ecfd9400d6a9d17d7e98e822dc (diff) | |
download | lvm2-c2a8bbed3bc8c5c4f505a7cecc4db0b94e7243bc.tar.gz |
radix-tree: radix_tree_remove_prefix()
-rw-r--r-- | base/data-struct/radix-tree.c | 33 | ||||
-rw-r--r-- | base/data-struct/radix-tree.h | 4 | ||||
-rw-r--r-- | test/unit/radix_tree_t.c | 22 |
3 files changed, 51 insertions, 8 deletions
diff --git a/base/data-struct/radix-tree.c b/base/data-struct/radix-tree.c index 26748e306..5688decb6 100644 --- a/base/data-struct/radix-tree.c +++ b/base/data-struct/radix-tree.c @@ -101,9 +101,10 @@ static inline void _dtr(struct radix_tree *rt, union radix_value v) rt->dtr(rt->dtr_context, v); } -static void _free_node(struct radix_tree *rt, struct value v) +// Returns the number of values removed +static unsigned _free_node(struct radix_tree *rt, struct value v) { - unsigned i; + unsigned i, nr = 0; struct value_chain *vc; struct prefix_chain *pc; struct node4 *n4; @@ -117,49 +118,52 @@ static void _free_node(struct radix_tree *rt, struct value v) case VALUE: _dtr(rt, v.value); + nr = 1; break; case VALUE_CHAIN: vc = v.value.ptr; _dtr(rt, vc->value); - _free_node(rt, vc->child); + nr = 1 + _free_node(rt, vc->child); free(vc); break; case PREFIX_CHAIN: pc = v.value.ptr; - _free_node(rt, pc->child); + nr = _free_node(rt, pc->child); free(pc); break; case NODE4: n4 = (struct node4 *) v.value.ptr; for (i = 0; i < n4->nr_entries; i++) - _free_node(rt, n4->values[i]); + nr += _free_node(rt, n4->values[i]); free(n4); break; case NODE16: n16 = (struct node16 *) v.value.ptr; for (i = 0; i < n16->nr_entries; i++) - _free_node(rt, n16->values[i]); + nr += _free_node(rt, n16->values[i]); free(n16); break; case NODE48: n48 = (struct node48 *) v.value.ptr; for (i = 0; i < n48->nr_entries; i++) - _free_node(rt, n48->values[i]); + nr += _free_node(rt, n48->values[i]); free(n48); break; case NODE256: n256 = (struct node256 *) v.value.ptr; for (i = 0; i < 256; i++) - _free_node(rt, n256->values[i]); + nr += _free_node(rt, n256->values[i]); free(n256); break; } + + return nr; } void radix_tree_destroy(struct radix_tree *rt) @@ -728,6 +732,19 @@ bool radix_tree_remove(struct radix_tree *rt, uint8_t *key_begin, uint8_t *key_e return false; } +unsigned radix_tree_remove_prefix(struct radix_tree *rt, uint8_t *kb, uint8_t *ke) +{ + unsigned count = 0; + struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke); + if (lr.kb == ke) { + count = _free_node(rt, *lr.v); + lr.v->type = UNSET; + } + + rt->nr_entries -= count; + return count; +} + bool radix_tree_lookup(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, union radix_value *result) { diff --git a/base/data-struct/radix-tree.h b/base/data-struct/radix-tree.h index 8560b3495..ad8a952a5 100644 --- a/base/data-struct/radix-tree.h +++ b/base/data-struct/radix-tree.h @@ -34,6 +34,10 @@ void radix_tree_destroy(struct radix_tree *rt); unsigned radix_tree_size(struct radix_tree *rt); bool radix_tree_insert(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, union radix_value v); bool radix_tree_remove(struct radix_tree *rt, uint8_t *kb, uint8_t *ke); + +// Returns the number of values removed +unsigned radix_tree_remove_prefix(struct radix_tree *rt, uint8_t *prefix_b, uint8_t *prefix_e); + bool radix_tree_lookup(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, union radix_value *result); diff --git a/test/unit/radix_tree_t.c b/test/unit/radix_tree_t.c index d2b0adc87..eb3577340 100644 --- a/test/unit/radix_tree_t.c +++ b/test/unit/radix_tree_t.c @@ -267,6 +267,27 @@ static void test_remove_prefix_keys_reversed(void *fixture) T_ASSERT(!radix_tree_lookup(rt, k, k + i, &v)); } +static void test_remove_prefix(void *fixture) +{ + struct radix_tree *rt = fixture; + unsigned i, count = 0; + uint8_t k[4]; + union radix_value v; + + // populate some random 32bit keys + for (i = 0; i < 100000; i++) { + _gen_key(k, k + sizeof(k)); + if (k[0] == 21) + count++; + v.n = i; + T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); + } + + // remove keys in a sub range + k[0] = 21; + T_ASSERT_EQUAL(radix_tree_remove_prefix(rt, k, k + 1), count); +} + //---------------------------------------------------------------- #define T(path, desc, fn) register_test(ts, "/base/data-struct/radix-tree/" path, desc, fn) @@ -291,6 +312,7 @@ void radix_tree_tests(struct dm_list *all_tests) T("remove-one-byte-keys", "remove many one byte keys", test_remove_one_byte_keys); T("remove-prefix-keys", "remove a set of keys that have common prefixes", test_remove_prefix_keys); T("remove-prefix-keys-reversed", "remove a set of keys that have common prefixes (reversed)", test_remove_prefix_keys_reversed); + T("remove-prefix", "remove a subrange", test_remove_prefix); dm_list_add(all_tests, &ts->list); } |