rdxtree: use 64-bit keys

3 files changed, 27 insertions, 26 deletions

diff --git a/rdxtree.c b/rdxtree.c
index a6838db..30a81ad 100644
--- a/rdxtree.c
+++ b/rdxtree.c
@@ -296,17 +296,17 @@ rdxtree_node_bm_first(struct rdxtree_node *node)
     return rdxtree_ffs(node->alloc_bm) - 1;
 }
 
-static inline unsigned long
+static inline unsigned long long
 rdxtree_max_key(unsigned int height)
 {
-    unsigned int shift;
+    size_t shift;
 
     shift = RDXTREE_RADIX * height;
 
-    if (likely(shift < (sizeof(unsigned long) * CHAR_BIT)))
-        return (1 << shift) - 1;
+    if (likely(shift < (sizeof(unsigned long long) * CHAR_BIT)))
+        return (1ULL << shift) - 1;
     else
-        return ~0UL;
+        return ~0ULL;
 }
 
 static void
@@ -337,7 +337,7 @@ rdxtree_shrink(struct rdxtree *tree)
 }
 
 static int
-rdxtree_grow(struct rdxtree *tree, unsigned long key)
+rdxtree_grow(struct rdxtree *tree, unsigned long long key)
 {
     struct rdxtree_node *root, *node;
     unsigned int new_height;
@@ -424,8 +424,8 @@ rdxtree_insert_bm_clear(struct rdxtree_node *node, unsigned int index)
 }
 
 int
-rdxtree_insert_common(struct rdxtree *tree, unsigned long key, void *ptr,
-                      void ***slotp)
+rdxtree_insert_common(struct rdxtree *tree, unsigned long long key,
+                      void *ptr, void ***slotp)
 {
     struct rdxtree_node *node, *prev;
     unsigned int height, shift, index = index;
@@ -481,7 +481,7 @@ rdxtree_insert_common(struct rdxtree *tree, unsigned long key, void *ptr,
         }
 
         prev = node;
-        index = (key >> shift) & RDXTREE_RADIX_MASK;
+        index = (unsigned int)(key >> shift) & RDXTREE_RADIX_MASK;
         node = rdxtree_entry_addr(prev->entries[index]);
         shift -= RDXTREE_RADIX;
         height--;
@@ -501,10 +501,10 @@ rdxtree_insert_common(struct rdxtree *tree, unsigned long key, void *ptr,
 
 int
 rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr,
-                            unsigned long *keyp, void ***slotp)
+                            unsigned long long *keyp, void ***slotp)
 {
     struct rdxtree_node *node, *prev;
-    unsigned long key;
+    unsigned long long key;
     unsigned int height, shift, index = index;
     int error;
 
@@ -551,7 +551,7 @@ rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr,
         if (index == (unsigned int)-1)
             goto grow;
 
-        key |= ((unsigned long)index << shift);
+        key |= (unsigned long long)index << shift;
         node = rdxtree_entry_addr(node->entries[index]);
         shift -= RDXTREE_RADIX;
         height--;
@@ -592,7 +592,7 @@ rdxtree_remove_bm_set(struct rdxtree_node *node, unsigned int index)
 }
 
 void *
-rdxtree_remove(struct rdxtree *tree, unsigned long key)
+rdxtree_remove(struct rdxtree *tree, unsigned long long key)
 {
     struct rdxtree_node *node, *prev;
     unsigned int height, shift, index;
@@ -616,7 +616,7 @@ rdxtree_remove(struct rdxtree *tree, unsigned long key)
             return NULL;
 
         prev = node;
-        index = (key >> shift) & RDXTREE_RADIX_MASK;
+        index = (unsigned int)(key >> shift) & RDXTREE_RADIX_MASK;
         node = rdxtree_entry_addr(node->entries[index]);
         shift -= RDXTREE_RADIX;
         height--;
@@ -632,7 +632,8 @@ rdxtree_remove(struct rdxtree *tree, unsigned long key)
 }
 
 void *
-rdxtree_lookup_common(struct rdxtree *tree, unsigned long key, int get_slot)
+rdxtree_lookup_common(struct rdxtree *tree, unsigned long long key,
+                      int get_slot)
 {
     struct rdxtree_node *node, *prev;
     unsigned int height, shift, index;
@@ -665,7 +666,7 @@ rdxtree_lookup_common(struct rdxtree *tree, unsigned long key, int get_slot)
             return NULL;
 
         prev = node;
-        index = (key >> shift) & RDXTREE_RADIX_MASK;
+        index = (unsigned int)(key >> shift) & RDXTREE_RADIX_MASK;
         entry = llsync_read_ptr(node->entries[index]);
         node = rdxtree_entry_addr(entry);
         shift -= RDXTREE_RADIX;
diff --git a/rdxtree.h b/rdxtree.h
index ec32929..1c6e056 100644
--- a/rdxtree.h
+++ b/rdxtree.h
@@ -84,7 +84,7 @@ rdxtree_init(struct rdxtree *tree)
  * The ptr parameter must not be NULL.
  */
 static inline int
-rdxtree_insert(struct rdxtree *tree, unsigned long key, void *ptr)
+rdxtree_insert(struct rdxtree *tree, unsigned long long key, void *ptr)
 {
     return rdxtree_insert_common(tree, key, ptr, NULL);
 }
@@ -97,7 +97,7 @@ rdxtree_insert(struct rdxtree *tree, unsigned long key, void *ptr)
  * parameter.
  */
 static inline int
-rdxtree_insert_slot(struct rdxtree *tree, unsigned long key, void *ptr,
+rdxtree_insert_slot(struct rdxtree *tree, unsigned long long key, void *ptr,
                     void ***slotp)
 {
     return rdxtree_insert_common(tree, key, ptr, slotp);
@@ -110,7 +110,7 @@ rdxtree_insert_slot(struct rdxtree *tree, unsigned 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 *keyp)
+rdxtree_insert_alloc(struct rdxtree *tree, void *ptr, unsigned long long *keyp)
 {
     return rdxtree_insert_alloc_common(tree, ptr, keyp, NULL);
 }
@@ -126,7 +126,7 @@ rdxtree_insert_alloc(struct rdxtree *tree, void *ptr, unsigned long *keyp)
  */
 static inline int
 rdxtree_insert_alloc_slot(struct rdxtree *tree, void *ptr,
-                          unsigned long *keyp, void ***slotp)
+                          unsigned long long *keyp, void ***slotp)
 {
     return rdxtree_insert_alloc_common(tree, ptr, keyp, slotp);
 }
@@ -136,7 +136,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 key);
+void * rdxtree_remove(struct rdxtree *tree, unsigned long long key);
 
 /*
  * Look up a pointer in a tree.
@@ -144,7 +144,7 @@ void * rdxtree_remove(struct rdxtree *tree, unsigned long key);
  * The matching pointer is returned if successful, NULL otherwise.
  */
 static inline void *
-rdxtree_lookup(struct rdxtree *tree, unsigned long key)
+rdxtree_lookup(struct rdxtree *tree, unsigned long long key)
 {
     return rdxtree_lookup_common(tree, key, 0);
 }
@@ -161,7 +161,7 @@ rdxtree_lookup(struct rdxtree *tree, unsigned long key)
  * See rdxtree_replace_slot().
  */
 static inline void **
-rdxtree_lookup_slot(struct rdxtree *tree, unsigned long key)
+rdxtree_lookup_slot(struct rdxtree *tree, unsigned long long key)
 {
     return rdxtree_lookup_common(tree, key, 1);
 }
diff --git a/rdxtree_i.h b/rdxtree_i.h
index 1bd171c..a6dd85e 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 key,
+int rdxtree_insert_common(struct rdxtree *tree, unsigned long long key,
                           void *ptr, void ***slotp);
 
 int rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr,
-                                unsigned long *keyp, void ***slotp);
+                                unsigned long long *keyp, void ***slotp);
 
-void * rdxtree_lookup_common(struct rdxtree *tree, unsigned long key,
+void * rdxtree_lookup_common(struct rdxtree *tree, unsigned long long key,
                              int get_slot);
 
 /*