diff options
author | Richard Braun <rbraun@sceen.net> | 2017-01-26 00:41:07 +0100 |
---|---|---|
committer | Richard Braun <rbraun@sceen.net> | 2017-01-26 00:41:07 +0100 |
commit | 900d78f86a2a6684a956f95163898814eb54d9ea (patch) | |
tree | 445937ac20493639c10b5d01f0b7d6080d1eb7af | |
parent | bd875458fcb4aa5516996ffb128b601a89bd25af (diff) |
rdxtree: make key allocation optional
-rw-r--r-- | rdxtree.c | 93 | ||||
-rw-r--r-- | rdxtree.h | 12 | ||||
-rw-r--r-- | rdxtree_i.h | 5 | ||||
-rw-r--r-- | test/test_rdxtree.c | 82 |
4 files changed, 111 insertions, 81 deletions
@@ -27,6 +27,8 @@ * http://git.sceen.net/rbraun/librbraun.git/ */ +#include <stdbool.h> + #include <assert.h> #include <limits.h> #include <stddef.h> @@ -104,9 +106,9 @@ typedef unsigned long long rdxtree_bm_t; */ struct rdxtree_node { struct rdxtree_node *parent; - unsigned int index; - unsigned int height; - unsigned int nr_entries; + unsigned short index; + unsigned short height; + unsigned short nr_entries; rdxtree_bm_t alloc_bm; void *entries[RDXTREE_RADIX_SIZE]; }; @@ -142,7 +144,7 @@ rdxtree_node_to_entry(struct rdxtree_node *node) } static int -rdxtree_node_create(struct rdxtree_node **nodep, unsigned int height) +rdxtree_node_create(struct rdxtree_node **nodep, unsigned short height) { struct rdxtree_node *node; @@ -187,7 +189,7 @@ rdxtree_node_schedule_destruction(struct rdxtree_node *node) static inline void rdxtree_node_link(struct rdxtree_node *node, struct rdxtree_node *parent, - unsigned int index) + unsigned short index) { node->parent = parent; node->index = index; @@ -213,7 +215,7 @@ rdxtree_node_empty(struct rdxtree_node *node) } static inline void -rdxtree_node_insert(struct rdxtree_node *node, unsigned int index, +rdxtree_node_insert(struct rdxtree_node *node, unsigned short index, void *entry) { assert(index < ARRAY_SIZE(node->entries)); @@ -224,14 +226,14 @@ rdxtree_node_insert(struct rdxtree_node *node, unsigned int index, } static inline void -rdxtree_node_insert_node(struct rdxtree_node *node, unsigned int index, +rdxtree_node_insert_node(struct rdxtree_node *node, unsigned short index, struct rdxtree_node *child) { rdxtree_node_insert(node, index, rdxtree_node_to_entry(child)); } static inline void -rdxtree_node_remove(struct rdxtree_node *node, unsigned int index) +rdxtree_node_remove(struct rdxtree_node *node, unsigned short index) { assert(index < ARRAY_SIZE(node->entries)); assert(node->entries[index] != NULL); @@ -241,9 +243,9 @@ rdxtree_node_remove(struct rdxtree_node *node, unsigned int index) } static inline void * -rdxtree_node_find(struct rdxtree_node *node, unsigned int *indexp) +rdxtree_node_find(struct rdxtree_node *node, unsigned short *indexp) { - unsigned int index; + unsigned short index; void *ptr; index = *indexp; @@ -263,19 +265,19 @@ rdxtree_node_find(struct rdxtree_node *node, unsigned int *indexp) } static inline void -rdxtree_node_bm_set(struct rdxtree_node *node, unsigned int index) +rdxtree_node_bm_set(struct rdxtree_node *node, unsigned short index) { node->alloc_bm |= (rdxtree_bm_t)1 << index; } static inline void -rdxtree_node_bm_clear(struct rdxtree_node *node, unsigned int index) +rdxtree_node_bm_clear(struct rdxtree_node *node, unsigned short index) { node->alloc_bm &= ~((rdxtree_bm_t)1 << index); } static inline int -rdxtree_node_bm_is_set(struct rdxtree_node *node, unsigned int index) +rdxtree_node_bm_is_set(struct rdxtree_node *node, unsigned short index) { return (node->alloc_bm & ((rdxtree_bm_t)1 << index)); } @@ -286,14 +288,14 @@ rdxtree_node_bm_empty(struct rdxtree_node *node) return (node->alloc_bm == RDXTREE_BM_EMPTY); } -static inline unsigned int +static inline unsigned short rdxtree_node_bm_first(struct rdxtree_node *node) { return rdxtree_ffs(node->alloc_bm) - 1; } static inline rdxtree_key_t -rdxtree_max_key(unsigned int height) +rdxtree_max_key(unsigned short height) { size_t shift; @@ -306,6 +308,12 @@ rdxtree_max_key(unsigned int height) } } +static inline bool +rdxtree_key_alloc_enabled(const struct rdxtree *tree) +{ + return (tree->flags & RDXTREE_KEY_ALLOC); +} + static void rdxtree_shrink(struct rdxtree *tree) { @@ -340,7 +348,7 @@ static int rdxtree_grow(struct rdxtree *tree, rdxtree_key_t key) { struct rdxtree_node *root, *node; - unsigned int new_height; + unsigned short new_height; int error; new_height = tree->height + 1; @@ -365,11 +373,14 @@ rdxtree_grow(struct rdxtree *tree, rdxtree_key_t key) } if (tree->height == 0) { - rdxtree_node_bm_clear(node, 0); + if (rdxtree_key_alloc_enabled(tree)) { + rdxtree_node_bm_clear(node, 0); + } } else { rdxtree_node_link(root, node, 0); - if (rdxtree_node_bm_empty(root)) { + if (rdxtree_key_alloc_enabled(tree) + && rdxtree_node_bm_empty(root)) { rdxtree_node_bm_clear(node, 0); } } @@ -413,7 +424,7 @@ rdxtree_cleanup(struct rdxtree *tree, struct rdxtree_node *node) } static void -rdxtree_insert_bm_clear(struct rdxtree_node *node, unsigned int index) +rdxtree_insert_bm_clear(struct rdxtree_node *node, unsigned short index) { for (;;) { rdxtree_node_bm_clear(node, index); @@ -432,8 +443,8 @@ rdxtree_insert_common(struct rdxtree *tree, rdxtree_key_t key, void *ptr, void ***slotp) { struct rdxtree_node *node, *prev; - unsigned int height, shift; - unsigned int index = 0; /* GCC */ + unsigned short height, shift; + unsigned short index = 0; /* GCC */ int error; assert(ptr != NULL); @@ -490,7 +501,7 @@ rdxtree_insert_common(struct rdxtree *tree, rdxtree_key_t key, } prev = node; - index = (unsigned int)(key >> shift) & RDXTREE_RADIX_MASK; + index = (unsigned short)(key >> shift) & RDXTREE_RADIX_MASK; node = rdxtree_entry_addr(prev->entries[index]); shift -= RDXTREE_RADIX; height--; @@ -501,7 +512,10 @@ rdxtree_insert_common(struct rdxtree *tree, rdxtree_key_t key, } rdxtree_node_insert(prev, index, ptr); - rdxtree_insert_bm_clear(prev, index); + + if (rdxtree_key_alloc_enabled(tree)) { + rdxtree_insert_bm_clear(prev, index); + } if (slotp != NULL) { *slotp = &prev->entries[index]; @@ -515,11 +529,12 @@ rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr, rdxtree_key_t *keyp, void ***slotp) { struct rdxtree_node *node, *prev; - unsigned int height, shift; - unsigned int index = 0; /* GCC */ + unsigned short height, shift; + unsigned short index = 0; /* GCC */ rdxtree_key_t key; int error; + assert(rdxtree_key_alloc_enabled(tree)); assert(ptr != NULL); rdxtree_assert_alignment(ptr); @@ -561,7 +576,7 @@ rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr, prev = node; index = rdxtree_node_bm_first(node); - if (index == (unsigned int)-1) { + if (index == (unsigned short)-1) { goto grow; } @@ -594,7 +609,7 @@ out: } static void -rdxtree_remove_bm_set(struct rdxtree_node *node, unsigned int index) +rdxtree_remove_bm_set(struct rdxtree_node *node, unsigned short index) { do { rdxtree_node_bm_set(node, index); @@ -612,7 +627,7 @@ void * rdxtree_remove(struct rdxtree *tree, rdxtree_key_t key) { struct rdxtree_node *node, *prev; - unsigned int height, shift, index; + unsigned short height, shift, index; height = tree->height; @@ -635,7 +650,7 @@ rdxtree_remove(struct rdxtree *tree, rdxtree_key_t key) } prev = node; - index = (unsigned int)(key >> shift) & RDXTREE_RADIX_MASK; + index = (unsigned short)(key >> shift) & RDXTREE_RADIX_MASK; node = rdxtree_entry_addr(node->entries[index]); shift -= RDXTREE_RADIX; height--; @@ -645,8 +660,11 @@ rdxtree_remove(struct rdxtree *tree, rdxtree_key_t key) return NULL; } + if (rdxtree_key_alloc_enabled(tree)) { + rdxtree_remove_bm_set(prev, index); + } + rdxtree_node_remove(prev, index); - rdxtree_remove_bm_set(prev, index); rdxtree_cleanup(tree, prev); return node; } @@ -656,7 +674,7 @@ rdxtree_lookup_common(const struct rdxtree *tree, rdxtree_key_t key, int get_slot) { struct rdxtree_node *node, *prev; - unsigned int height, shift, index; + unsigned short height, shift, index; void *entry; entry = llsync_read_ptr(tree->root); @@ -689,7 +707,7 @@ rdxtree_lookup_common(const struct rdxtree *tree, rdxtree_key_t key, } prev = node; - index = (unsigned int)(key >> shift) & RDXTREE_RADIX_MASK; + index = (unsigned short)(key >> shift) & RDXTREE_RADIX_MASK; entry = llsync_read_ptr(node->entries[index]); node = rdxtree_entry_addr(entry); shift -= RDXTREE_RADIX; @@ -722,7 +740,7 @@ static void * rdxtree_walk_next(struct rdxtree *tree, struct rdxtree_iter *iter) { struct rdxtree_node *root, *node, *prev; - unsigned int height, shift, index, orig_index; + unsigned short height, shift, index, orig_index; rdxtree_key_t key; void *entry; @@ -792,7 +810,7 @@ restart: void * rdxtree_walk(struct rdxtree *tree, struct rdxtree_iter *iter) { - unsigned int index, orig_index; + unsigned short index, orig_index; void *ptr; if (iter->node == NULL) { @@ -840,10 +858,13 @@ rdxtree_remove_all(struct rdxtree *tree) parent = node->parent; if (parent == NULL) { - rdxtree_init(tree); + rdxtree_init(tree, tree->flags); } else { + if (rdxtree_key_alloc_enabled(tree)) { + rdxtree_remove_bm_set(parent, node->index); + } + rdxtree_node_remove(parent, node->index); - rdxtree_remove_bm_set(parent, node->index); rdxtree_cleanup(tree, parent); node->parent = NULL; } @@ -1,5 +1,5 @@ /* - * Copyright (c) 2011-2015 Richard Braun. + * Copyright (c) 2011-2017 Richard Braun. * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -52,6 +52,11 @@ typedef uint64_t rdxtree_key_t; #endif /* RDXTREE_KEY_32 */ /* + * Radix tree initialization flags. + */ +#define RDXTREE_KEY_ALLOC 0x1 /* Enable key allocation */ + +/* * Radix tree. */ struct rdxtree; @@ -72,9 +77,12 @@ struct rdxtree_iter; * Initialize a tree. */ static inline void -rdxtree_init(struct rdxtree *tree) +rdxtree_init(struct rdxtree *tree, unsigned short flags) { + assert((flags & ~RDXTREE_KEY_ALLOC) == 0); + tree->height = 0; + tree->flags = flags; tree->root = NULL; } diff --git a/rdxtree_i.h b/rdxtree_i.h index d9a59bf..ca5e8ea 100644 --- a/rdxtree_i.h +++ b/rdxtree_i.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2011-2015 Richard Braun. + * Copyright (c) 2011-2017 Richard Braun. * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -34,7 +34,8 @@ * Radix tree. */ struct rdxtree { - unsigned int height; + unsigned short height; + unsigned short flags; void *root; }; diff --git a/test/test_rdxtree.c b/test/test_rdxtree.c index 9ed21ac..b95d11f 100644 --- a/test/test_rdxtree.c +++ b/test/test_rdxtree.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2011-2015 Richard Braun. + * Copyright (c) 2011-2017 Richard Braun. * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -169,7 +169,7 @@ test_1(void) TITLE("insert 0"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(0); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -186,7 +186,7 @@ test_2(void) TITLE("insert 1"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(1); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -203,7 +203,7 @@ test_3(void) TITLE("insert 0 and 1"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(0); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -223,7 +223,7 @@ test_4(void) TITLE("insert 1 and 0"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(1); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -243,7 +243,7 @@ test_5(void) TITLE("insert 0 and 4096"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(0); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -263,7 +263,7 @@ test_5_1(void) TITLE("insert 0, 256 and 4096"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(0); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -287,7 +287,7 @@ test_5_2(void) TITLE("insert [0..78], remove 77"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); for (i = 0; i <= 78; i++) { obj = obj_create(i); @@ -311,7 +311,7 @@ test_6(void) TITLE("insert 4096 and 0"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(4096); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -332,7 +332,7 @@ test_7(void) TITLE("insert and remove 0"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(0); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -352,7 +352,7 @@ test_8(void) TITLE("insert and remove 4096"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(4096); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -372,7 +372,7 @@ test_9(void) TITLE("insert 0 and 4096 and remove in reverse order"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj1 = obj_create(0); error = rdxtree_insert(&tree, obj1->id, obj1); check(!error); @@ -398,7 +398,7 @@ test_10(void) TITLE("insert 0 and 4096 and remove in same order"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj1 = obj_create(0); error = rdxtree_insert(&tree, obj1->id, obj1); check(!error); @@ -424,7 +424,7 @@ test_11(void) TITLE("insert [0..4096] and remove in reverse order"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); for (i = 0; i <= 4096; i++) { obj = obj_create(i); @@ -450,7 +450,7 @@ test_12(void) TITLE("insert [0..4096] and remove in same order"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); for (i = 0; i <= 4096; i++) { obj = obj_create(i); @@ -476,7 +476,7 @@ test_13(void) TITLE("allocate"); - rdxtree_init(&tree); + rdxtree_init(&tree, RDXTREE_KEY_ALLOC); obj = obj_create(0); error = rdxtree_insert_alloc(&tree, obj, &obj->id); check(!error); @@ -498,7 +498,7 @@ test_14(void) TITLE("insert 0, allocate"); - rdxtree_init(&tree); + rdxtree_init(&tree, RDXTREE_KEY_ALLOC); obj = obj_create(0); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -523,7 +523,7 @@ test_15(void) TITLE("insert [0..4095], remove 0, allocate"); - rdxtree_init(&tree); + rdxtree_init(&tree, RDXTREE_KEY_ALLOC); for (i = 0; i < 4096; i++) { obj = obj_create(i); @@ -549,7 +549,7 @@ test_16(void) TITLE("insert [0..4095], remove 1, allocate"); - rdxtree_init(&tree); + rdxtree_init(&tree, RDXTREE_KEY_ALLOC); for (i = 0; i < 4096; i++) { obj = obj_create(i); @@ -575,7 +575,7 @@ test_17(void) TITLE("insert [0..63] and [128..191], allocate x65"); - rdxtree_init(&tree); + rdxtree_init(&tree, RDXTREE_KEY_ALLOC); for (i = 0; i < 64; i++) { obj = obj_create(i); @@ -613,7 +613,7 @@ test_18(void) TITLE("insert [0..4095], allocate"); - rdxtree_init(&tree); + rdxtree_init(&tree, RDXTREE_KEY_ALLOC); for (i = 0; i < 4096; i++) { obj = obj_create(i); @@ -638,7 +638,7 @@ test_19(void) TITLE("insert 0, replace"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj1 = obj_create(0); error = rdxtree_insert(&tree, 0, obj1); check(!error); @@ -664,7 +664,7 @@ test_20(void) TITLE("insert 4096, replace"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj1 = obj_create(4096); error = rdxtree_insert(&tree, 4096, obj1); check(!error); @@ -689,7 +689,7 @@ test_21(void) TITLE("insert 0, insert again"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(0); error = rdxtree_insert(&tree, 0, obj); check(!error); @@ -707,7 +707,7 @@ test_22(void) TITLE("insert 123, insert again"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(123); error = rdxtree_insert(&tree, 123, obj); check(!error); @@ -726,7 +726,7 @@ test_23(void) TITLE("insert_slot 0, check slot"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(0); error = rdxtree_insert_slot(&tree, obj->id, obj, &slot); check(!error); @@ -744,7 +744,7 @@ test_24(void) TITLE("insert_slot 321, check slot"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(321); error = rdxtree_insert_slot(&tree, obj->id, obj, &slot); check(!error); @@ -763,7 +763,7 @@ test_25(void) TITLE("insert_alloc_slot x3"); - rdxtree_init(&tree); + rdxtree_init(&tree, RDXTREE_KEY_ALLOC); for (i = 0; i < 3; i++) { obj = obj_create(0); @@ -786,7 +786,7 @@ test_26(void) TITLE("insert [0..62], remove 63"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); for (i = 0; i < 62; i++) { obj = obj_create(i); @@ -810,7 +810,7 @@ test_27(void) TITLE("insert [0..63], remove 64"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); for (i = 0; i < 64; i++) { obj = obj_create(i); @@ -833,7 +833,7 @@ test_28(void) TITLE("insert 60000, remove 1"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(60000); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -850,7 +850,7 @@ test_29(void) TITLE("empty tree, lookup 0"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = rdxtree_lookup(&tree, 0); check(obj == NULL); } @@ -863,7 +863,7 @@ test_30(void) TITLE("empty tree, lookup 10"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = rdxtree_lookup(&tree, 10); check(obj == NULL); } @@ -877,7 +877,7 @@ test_31(void) TITLE("insert 60000, lookup 1"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(60000); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -895,7 +895,7 @@ test_32(void) TITLE("insert 60001, lookup 60000"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(60001); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -919,7 +919,7 @@ test_33(void) rdxtree_fail_node_creation_threshold = 1; rdxtree_nr_node_creations = 0; - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(1); error = rdxtree_insert(&tree, obj->id, obj); check(error == ERR_NOMEM); @@ -939,7 +939,7 @@ test_34(void) rdxtree_fail_node_creation_threshold = 2; rdxtree_nr_node_creations = 0; - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(64); error = rdxtree_insert(&tree, obj->id, obj); check(error == ERR_NOMEM); @@ -959,7 +959,7 @@ test_35(void) rdxtree_fail_node_creation_threshold = 2; rdxtree_nr_node_creations = 0; - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(0); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -983,7 +983,7 @@ test_36(void) rdxtree_fail_node_creation_threshold = 2; rdxtree_nr_node_creations = 0; - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(1); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -1006,7 +1006,7 @@ test_37(void) TITLE("insert and remove 4294967296"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(4294967296); error = rdxtree_insert(&tree, obj->id, obj); check(!error); @@ -1026,7 +1026,7 @@ test_38(void) TITLE("insert 1, 3 and max_key"); - rdxtree_init(&tree); + rdxtree_init(&tree, 0); obj = obj_create(1); error = rdxtree_insert(&tree, obj->id, obj); check(!error); |