summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--rdxtree.c22
-rw-r--r--rdxtree.h30
-rw-r--r--rdxtree_i.h6
-rw-r--r--test/test_rdxtree.c32
4 files changed, 54 insertions, 36 deletions
diff --git a/rdxtree.c b/rdxtree.c
index de32006..7d94e82 100644
--- a/rdxtree.c
+++ b/rdxtree.c
@@ -279,17 +279,17 @@ rdxtree_node_bm_first(struct rdxtree_node *node)
return rdxtree_ffs(node->alloc_bm) - 1;
}
-static inline unsigned long long
+static inline rdxtree_key_t
rdxtree_max_key(unsigned int height)
{
size_t shift;
shift = RDXTREE_RADIX * height;
- if (likely(shift < (sizeof(unsigned long long) * CHAR_BIT)))
- return (1ULL << shift) - 1;
+ if (likely(shift < (sizeof(rdxtree_key_t) * CHAR_BIT)))
+ return ((rdxtree_key_t)1 << shift) - 1;
else
- return ~0ULL;
+ return ~((rdxtree_key_t)0);
}
static void
@@ -320,7 +320,7 @@ rdxtree_shrink(struct rdxtree *tree)
}
static int
-rdxtree_grow(struct rdxtree *tree, unsigned long long key)
+rdxtree_grow(struct rdxtree *tree, rdxtree_key_t key)
{
struct rdxtree_node *root, *node;
unsigned int new_height;
@@ -407,7 +407,7 @@ rdxtree_insert_bm_clear(struct rdxtree_node *node, unsigned int index)
}
int
-rdxtree_insert_common(struct rdxtree *tree, unsigned long long key,
+rdxtree_insert_common(struct rdxtree *tree, rdxtree_key_t key,
void *ptr, void ***slotp)
{
struct rdxtree_node *node, *prev;
@@ -484,11 +484,11 @@ rdxtree_insert_common(struct rdxtree *tree, unsigned long long key,
int
rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr,
- unsigned long long *keyp, void ***slotp)
+ rdxtree_key_t *keyp, void ***slotp)
{
struct rdxtree_node *node, *prev;
- unsigned long long key;
unsigned int height, shift, index = index;
+ rdxtree_key_t key;
int error;
assert(ptr != NULL);
@@ -534,7 +534,7 @@ rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr,
if (index == (unsigned int)-1)
goto grow;
- key |= (unsigned long long)index << shift;
+ key |= (rdxtree_key_t)index << shift;
node = rdxtree_entry_addr(node->entries[index]);
shift -= RDXTREE_RADIX;
height--;
@@ -575,7 +575,7 @@ rdxtree_remove_bm_set(struct rdxtree_node *node, unsigned int index)
}
void *
-rdxtree_remove(struct rdxtree *tree, unsigned long long key)
+rdxtree_remove(struct rdxtree *tree, rdxtree_key_t key)
{
struct rdxtree_node *node, *prev;
unsigned int height, shift, index;
@@ -615,7 +615,7 @@ rdxtree_remove(struct rdxtree *tree, unsigned long long key)
}
void *
-rdxtree_lookup_common(const struct rdxtree *tree, unsigned long long key,
+rdxtree_lookup_common(const struct rdxtree *tree, rdxtree_key_t key,
int get_slot)
{
struct rdxtree_node *node, *prev;
diff --git a/rdxtree.h b/rdxtree.h
index cb2356a..2449937 100644
--- a/rdxtree.h
+++ b/rdxtree.h
@@ -33,6 +33,20 @@
#define _RDXTREE_H
#include <stddef.h>
+#include <stdint.h>
+
+/*
+ * This macro selects between 32 or 64-bits (the default) keys.
+ */
+#if 0
+#define RDXTREE_KEY_32
+#endif
+
+#ifdef RDXTREE_KEY_32
+typedef uint32_t rdxtree_key_t;
+#else /* RDXTREE_KEY_32 */
+typedef uint64_t rdxtree_key_t;
+#endif /* RDXTREE_KEY_32 */
/*
* Radix tree.
@@ -67,7 +81,7 @@ rdxtree_init(struct rdxtree *tree)
* The ptr parameter must not be NULL.
*/
static inline int
-rdxtree_insert(struct rdxtree *tree, unsigned long long key, void *ptr)
+rdxtree_insert(struct rdxtree *tree, rdxtree_key_t key, void *ptr)
{
return rdxtree_insert_common(tree, key, ptr, NULL);
}
@@ -80,8 +94,8 @@ rdxtree_insert(struct rdxtree *tree, unsigned long long key, void *ptr)
* parameter.
*/
static inline int
-rdxtree_insert_slot(struct rdxtree *tree, unsigned long long key, void *ptr,
- void ***slotp)
+rdxtree_insert_slot(struct rdxtree *tree, rdxtree_key_t key,
+ void *ptr, void ***slotp)
{
return rdxtree_insert_common(tree, key, ptr, slotp);
}
@@ -93,7 +107,7 @@ rdxtree_insert_slot(struct rdxtree *tree, unsigned long long key, void *ptr,
* stored at the address pointed to by the keyp parameter.
*/
static inline int
-rdxtree_insert_alloc(struct rdxtree *tree, void *ptr, unsigned long long *keyp)
+rdxtree_insert_alloc(struct rdxtree *tree, void *ptr, rdxtree_key_t *keyp)
{
return rdxtree_insert_alloc_common(tree, ptr, keyp, NULL);
}
@@ -109,7 +123,7 @@ rdxtree_insert_alloc(struct rdxtree *tree, void *ptr, unsigned long long *keyp)
*/
static inline int
rdxtree_insert_alloc_slot(struct rdxtree *tree, void *ptr,
- unsigned long long *keyp, void ***slotp)
+ rdxtree_key_t *keyp, void ***slotp)
{
return rdxtree_insert_alloc_common(tree, ptr, keyp, slotp);
}
@@ -119,7 +133,7 @@ rdxtree_insert_alloc_slot(struct rdxtree *tree, void *ptr,
*
* The matching pointer is returned if successful, NULL otherwise.
*/
-void * rdxtree_remove(struct rdxtree *tree, unsigned long long key);
+void * rdxtree_remove(struct rdxtree *tree, rdxtree_key_t key);
/*
* Look up a pointer in a tree.
@@ -127,7 +141,7 @@ void * rdxtree_remove(struct rdxtree *tree, unsigned long long key);
* The matching pointer is returned if successful, NULL otherwise.
*/
static inline void *
-rdxtree_lookup(const struct rdxtree *tree, unsigned long long key)
+rdxtree_lookup(const struct rdxtree *tree, rdxtree_key_t key)
{
return rdxtree_lookup_common(tree, key, 0);
}
@@ -144,7 +158,7 @@ rdxtree_lookup(const struct rdxtree *tree, unsigned long long key)
* See rdxtree_replace_slot().
*/
static inline void **
-rdxtree_lookup_slot(const struct rdxtree *tree, unsigned long long key)
+rdxtree_lookup_slot(const struct rdxtree *tree, rdxtree_key_t key)
{
return rdxtree_lookup_common(tree, key, 1);
}
diff --git a/rdxtree_i.h b/rdxtree_i.h
index 4ba27d8..d32c4d6 100644
--- a/rdxtree_i.h
+++ b/rdxtree_i.h
@@ -44,13 +44,13 @@ rdxtree_iter_init(struct rdxtree_iter *iter)
iter->slot = NULL;
}
-int rdxtree_insert_common(struct rdxtree *tree, unsigned long long key,
+int rdxtree_insert_common(struct rdxtree *tree, rdxtree_key_t key,
void *ptr, void ***slotp);
int rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr,
- unsigned long long *keyp, void ***slotp);
+ rdxtree_key_t *keyp, void ***slotp);
-void * rdxtree_lookup_common(const struct rdxtree *tree, unsigned long long key,
+void * rdxtree_lookup_common(const struct rdxtree *tree, rdxtree_key_t key,
int get_slot);
/*
diff --git a/test/test_rdxtree.c b/test/test_rdxtree.c
index de4965b..b971628 100644
--- a/test/test_rdxtree.c
+++ b/test/test_rdxtree.c
@@ -42,14 +42,14 @@
#endif /* RDXTREE_RADIX < 6 */
struct obj {
- unsigned long long id;
+ rdxtree_key_t id;
};
static void print_subtree(struct rdxtree_node *node, int height, size_t index,
size_t level);
static struct obj *
-obj_create(unsigned long long id)
+obj_create(rdxtree_key_t id)
{
struct obj *obj;
@@ -79,7 +79,7 @@ print_value(void *ptr, size_t index, size_t level)
for (i = level; i > 0; i--)
putchar(' ');
- printf("%zu:%llu\n", index, obj->id);
+ printf("%zu:%llu\n", index, (unsigned long long)obj->id);
}
static void
@@ -361,7 +361,7 @@ test_11(void)
{
struct rdxtree tree;
struct obj *obj;
- unsigned long long i;
+ rdxtree_key_t i;
int error;
TITLE("insert [0..4096] and remove in reverse order");
@@ -387,7 +387,7 @@ test_12(void)
{
struct rdxtree tree;
struct obj *obj;
- unsigned long long i;
+ rdxtree_key_t i;
int error;
TITLE("insert [0..4096] and remove in same order");
@@ -413,7 +413,7 @@ test_13(void)
{
struct rdxtree tree;
struct obj *obj;
- unsigned long long i;
+ rdxtree_key_t i;
int error;
TITLE("allocate");
@@ -435,7 +435,7 @@ test_14(void)
{
struct rdxtree tree;
struct obj *obj;
- unsigned long long i;
+ rdxtree_key_t i;
int error;
TITLE("insert 0, allocate");
@@ -460,7 +460,7 @@ test_15(void)
{
struct rdxtree tree;
struct obj *obj;
- unsigned long long i;
+ rdxtree_key_t i;
int error;
TITLE("insert [0..4095], remove 0, allocate");
@@ -486,7 +486,7 @@ test_16(void)
{
struct rdxtree tree;
struct obj *obj;
- unsigned long long i;
+ rdxtree_key_t i;
int error;
TITLE("insert [0..4095], remove 1, allocate");
@@ -512,7 +512,7 @@ test_17(void)
{
struct rdxtree tree;
struct obj *obj;
- unsigned long long i;
+ rdxtree_key_t i;
int error;
TITLE("insert [0..63] and [128..191], allocate x65");
@@ -550,7 +550,7 @@ test_18(void)
{
struct rdxtree tree;
struct obj *obj;
- unsigned long long i;
+ rdxtree_key_t i;
int error;
TITLE("insert [0..4095], allocate");
@@ -700,7 +700,7 @@ test_25(void)
struct rdxtree tree;
struct obj *obj;
void **slot;
- unsigned long long i;
+ rdxtree_key_t i;
int error;
TITLE("insert_alloc_slot x3");
@@ -723,7 +723,7 @@ test_26(void)
{
struct rdxtree tree;
struct obj *obj;
- unsigned long long i;
+ rdxtree_key_t i;
int error;
TITLE("insert [0..62], remove 63");
@@ -747,7 +747,7 @@ test_27(void)
{
struct rdxtree tree;
struct obj *obj;
- unsigned long long i;
+ rdxtree_key_t i;
int error;
TITLE("insert [0..63], remove 64");
@@ -937,6 +937,7 @@ test_36(void)
destroy_tree(&tree);
}
+#ifndef RDXTREE_KEY_32
static void
test_37(void)
{
@@ -956,6 +957,7 @@ test_37(void)
obj_destroy(obj);
print_tree(&tree);
}
+#endif /* RDXTREE_KEY_32 */
int
main(int argc, char *argv[])
@@ -999,6 +1001,8 @@ main(int argc, char *argv[])
test_34();
test_35();
test_36();
+#ifndef RDXTREE_KEY_32
test_37();
+#endif /* RDXTREE_KEY_32 */
return 0;
}
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-30 22:31:02 +0000