summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--avltree.c8
-rw-r--r--avltree.h15
-rw-r--r--avltree_i.h21
-rw-r--r--rbtree.c7
-rw-r--r--rbtree.h13
-rw-r--r--rbtree_i.h19
-rw-r--r--rdxtree.c11
-rw-r--r--test/test_avltree.c4
-rw-r--r--test/test_rbtree.c4
9 files changed, 58 insertions, 44 deletions
diff --git a/avltree.c b/avltree.c
index 260288f..0b6ff9e 100644
--- a/avltree.c
+++ b/avltree.c
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2010-2015 Richard Braun.
+ * Copyright (c) 2010-2017 Richard Braun.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -29,6 +29,7 @@
#include <assert.h>
#include <stddef.h>
+#include <stdint.h>
#include "macros.h"
#include "avltree.h"
@@ -89,8 +90,7 @@ avltree_node_set_parent(struct avltree_node *node, struct avltree_node *parent)
{
assert(avltree_node_check_alignment(node));
assert(avltree_node_check_alignment(parent));
- node->parent = (unsigned long)parent
- | (node->parent & AVLTREE_BALANCE_MASK);
+ node->parent = (uintptr_t)parent | (node->parent & AVLTREE_BALANCE_MASK);
}
/*
@@ -251,7 +251,7 @@ avltree_insert_rebalance(struct avltree *tree, struct avltree_node *parent,
assert(avltree_node_check_alignment(parent));
assert(avltree_node_check_alignment(node));
- node->parent = (unsigned long)parent | AVLTREE_BALANCE_ZERO;
+ node->parent = (uintptr_t)parent | AVLTREE_BALANCE_ZERO;
node->children[AVLTREE_LEFT] = NULL;
node->children[AVLTREE_RIGHT] = NULL;
diff --git a/avltree.h b/avltree.h
index 211f0b7..028057d 100644
--- a/avltree.h
+++ b/avltree.h
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2010-2015 Richard Braun.
+ * Copyright (c) 2010-2017 Richard Braun.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -39,6 +39,7 @@
#include <assert.h>
#include <stddef.h>
+#include <stdint.h>
#include "macros.h"
@@ -59,6 +60,11 @@ struct avltree_node;
struct avltree;
/*
+ * Insertion point identifier.
+ */
+typedef uintptr_t avltree_slot_t;
+
+/*
* Static tree initializer.
*/
#define AVLTREE_INITIALIZER { NULL }
@@ -84,7 +90,7 @@ avltree_node_init(struct avltree_node *node)
{
assert(avltree_node_check_alignment(node));
- node->parent = (unsigned long)node | AVLTREE_BALANCE_ZERO;
+ node->parent = (uintptr_t)node | AVLTREE_BALANCE_ZERO;
node->children[AVLTREE_LEFT] = NULL;
node->children[AVLTREE_RIGHT] = NULL;
}
@@ -218,8 +224,7 @@ MACRO_END
* This macro essentially acts as avltree_lookup() but in addition to a node,
* it also returns a slot, which identifies an insertion point in the tree.
* If the returned node is NULL, the slot can be used by avltree_insert_slot()
- * to insert without the overhead of an additional lookup. The slot is a
- * simple unsigned long integer.
+ * to insert without the overhead of an additional lookup.
*
* The constraints that apply to the key parameter are the same as for
* avltree_lookup().
@@ -258,7 +263,7 @@ MACRO_END
* must denote a NULL node).
*/
static inline void
-avltree_insert_slot(struct avltree *tree, unsigned long slot,
+avltree_insert_slot(struct avltree *tree, avltree_slot_t slot,
struct avltree_node *node)
{
struct avltree_node *parent;
diff --git a/avltree_i.h b/avltree_i.h
index 131487f..ff4e0dc 100644
--- a/avltree_i.h
+++ b/avltree_i.h
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2010-2015 Richard Braun.
+ * Copyright (c) 2010-2017 Richard Braun.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -32,6 +32,7 @@
#include <assert.h>
#include <stddef.h>
+#include <stdint.h>
#include "macros.h"
@@ -55,7 +56,7 @@
* a balance of -1 from a raw value of 0.
*/
struct avltree_node {
- unsigned long parent;
+ uintptr_t parent;
struct avltree_node *children[2];
};
@@ -70,20 +71,20 @@ struct avltree {
* Masks applied on the parent member of a node to obtain either the
* balance or the parent address.
*/
-#define AVLTREE_BALANCE_MASK 0x3UL
+#define AVLTREE_BALANCE_MASK ((uintptr_t)0x3)
#define AVLTREE_PARENT_MASK (~AVLTREE_BALANCE_MASK)
/*
* Special raw balance values.
*/
-#define AVLTREE_BALANCE_ZERO 1UL
+#define AVLTREE_BALANCE_ZERO ((uintptr_t)1)
#define AVLTREE_BALANCE_INVALID AVLTREE_BALANCE_MASK
/*
* Masks applied on slots to obtain either the child index or the parent
* address.
*/
-#define AVLTREE_SLOT_INDEX_MASK 0x1UL
+#define AVLTREE_SLOT_INDEX_MASK ((uintptr_t)0x1)
#define AVLTREE_SLOT_PARENT_MASK (~AVLTREE_SLOT_INDEX_MASK)
/*
@@ -113,7 +114,7 @@ avltree_d2i(int diff)
static inline int
avltree_node_check_alignment(const struct avltree_node *node)
{
- return ((unsigned long)node & AVLTREE_BALANCE_MASK) == 0;
+ return ((uintptr_t)node & AVLTREE_BALANCE_MASK) == 0;
}
/*
@@ -128,19 +129,19 @@ avltree_node_parent(const struct avltree_node *node)
/*
* Translate an insertion point into a slot.
*/
-static inline unsigned long
+static inline avltree_slot_t
avltree_slot(struct avltree_node *parent, int index)
{
assert(avltree_node_check_alignment(parent));
assert(avltree_check_index(index));
- return (unsigned long)parent | index;
+ return (avltree_slot_t)parent | index;
}
/*
* Extract the parent address from a slot.
*/
static inline struct avltree_node *
-avltree_slot_parent(unsigned long slot)
+avltree_slot_parent(avltree_slot_t slot)
{
return (struct avltree_node *)(slot & AVLTREE_SLOT_PARENT_MASK);
}
@@ -149,7 +150,7 @@ avltree_slot_parent(unsigned long slot)
* Extract the index from a slot.
*/
static inline int
-avltree_slot_index(unsigned long slot)
+avltree_slot_index(avltree_slot_t slot)
{
return slot & AVLTREE_SLOT_INDEX_MASK;
}
diff --git a/rbtree.c b/rbtree.c
index 55960cf..ce3ed36 100644
--- a/rbtree.c
+++ b/rbtree.c
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2010-2015 Richard Braun.
+ * Copyright (c) 2010-2017 Richard Braun.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -29,6 +29,7 @@
#include <assert.h>
#include <stddef.h>
+#include <stdint.h>
#include "macros.h"
#include "rbtree.h"
@@ -92,7 +93,7 @@ rbtree_node_set_parent(struct rbtree_node *node, struct rbtree_node *parent)
assert(rbtree_node_check_alignment(node));
assert(rbtree_node_check_alignment(parent));
- node->parent = (unsigned long)parent | (node->parent & RBTREE_COLOR_MASK);
+ node->parent = (uintptr_t)parent | (node->parent & RBTREE_COLOR_MASK);
}
/*
@@ -192,7 +193,7 @@ rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent,
assert(rbtree_node_check_alignment(parent));
assert(rbtree_node_check_alignment(node));
- node->parent = (unsigned long)parent | RBTREE_COLOR_RED;
+ node->parent = (uintptr_t)parent | RBTREE_COLOR_RED;
node->children[RBTREE_LEFT] = NULL;
node->children[RBTREE_RIGHT] = NULL;
diff --git a/rbtree.h b/rbtree.h
index 20f7883..8fa3714 100644
--- a/rbtree.h
+++ b/rbtree.h
@@ -34,6 +34,7 @@
#include <assert.h>
#include <stddef.h>
+#include <stdint.h>
#include "macros.h"
@@ -54,6 +55,11 @@ struct rbtree_node;
struct rbtree;
/*
+ * Insertion point identifier.
+ */
+typedef uintptr_t rbtree_slot_t;
+
+/*
* Static tree initializer.
*/
#define RBTREE_INITIALIZER { NULL }
@@ -79,7 +85,7 @@ rbtree_node_init(struct rbtree_node *node)
{
assert(rbtree_node_check_alignment(node));
- node->parent = (unsigned long)node | RBTREE_COLOR_RED;
+ node->parent = (uintptr_t)node | RBTREE_COLOR_RED;
node->children[RBTREE_LEFT] = NULL;
node->children[RBTREE_RIGHT] = NULL;
}
@@ -217,8 +223,7 @@ MACRO_END
* This macro essentially acts as rbtree_lookup() but in addition to a node,
* it also returns a slot, which identifies an insertion point in the tree.
* If the returned node is NULL, the slot can be used by rbtree_insert_slot()
- * to insert without the overhead of an additional lookup. The slot is a
- * simple unsigned long integer.
+ * to insert without the overhead of an additional lookup.
*
* The constraints that apply to the key parameter are the same as for
* rbtree_lookup().
@@ -257,7 +262,7 @@ MACRO_END
* must denote a NULL node).
*/
static inline void
-rbtree_insert_slot(struct rbtree *tree, unsigned long slot,
+rbtree_insert_slot(struct rbtree *tree, rbtree_slot_t slot,
struct rbtree_node *node)
{
struct rbtree_node *parent;
diff --git a/rbtree_i.h b/rbtree_i.h
index 1445b0e..335f307 100644
--- a/rbtree_i.h
+++ b/rbtree_i.h
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2010-2015 Richard Braun.
+ * Copyright (c) 2010-2017 Richard Braun.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -32,6 +32,7 @@
#include <assert.h>
#include <stddef.h>
+#include <stdint.h>
#include "macros.h"
@@ -50,7 +51,7 @@
* special alignment constraints such as member packing.
*/
struct rbtree_node {
- unsigned long parent;
+ uintptr_t parent;
struct rbtree_node *children[2];
};
@@ -65,8 +66,8 @@ struct rbtree {
* Masks applied on the parent member of a node to obtain either the
* color or the parent address.
*/
-#define RBTREE_COLOR_MASK 0x1UL
-#define RBTREE_PARENT_MASK (~0x3UL)
+#define RBTREE_COLOR_MASK ((uintptr_t)0x1)
+#define RBTREE_PARENT_MASK (~(uintptr_t)0x3)
/*
* Node colors.
@@ -108,7 +109,7 @@ rbtree_d2i(int diff)
static inline int
rbtree_node_check_alignment(const struct rbtree_node *node)
{
- return ((unsigned long)node & (~RBTREE_PARENT_MASK)) == 0;
+ return ((uintptr_t)node & (~RBTREE_PARENT_MASK)) == 0;
}
/*
@@ -123,19 +124,19 @@ rbtree_node_parent(const struct rbtree_node *node)
/*
* Translate an insertion point into a slot.
*/
-static inline unsigned long
+static inline rbtree_slot_t
rbtree_slot(struct rbtree_node *parent, int index)
{
assert(rbtree_node_check_alignment(parent));
assert(rbtree_check_index(index));
- return (unsigned long)parent | index;
+ return (rbtree_slot_t)parent | index;
}
/*
* Extract the parent address from a slot.
*/
static inline struct rbtree_node *
-rbtree_slot_parent(unsigned long slot)
+rbtree_slot_parent(rbtree_slot_t slot)
{
return (struct rbtree_node *)(slot & RBTREE_SLOT_PARENT_MASK);
}
@@ -144,7 +145,7 @@ rbtree_slot_parent(unsigned long slot)
* Extract the index from a slot.
*/
static inline int
-rbtree_slot_index(unsigned long slot)
+rbtree_slot_index(rbtree_slot_t slot)
{
return slot & RBTREE_SLOT_INDEX_MASK;
}
diff --git a/rdxtree.c b/rdxtree.c
index da7b4c9..ca3e049 100644
--- a/rdxtree.c
+++ b/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
@@ -30,6 +30,7 @@
#include <assert.h>
#include <limits.h>
#include <stddef.h>
+#include <stdint.h>
#include <stdlib.h>
#include <string.h>
@@ -118,26 +119,26 @@ unsigned int rdxtree_nr_node_creations;
static inline void
rdxtree_assert_alignment(const void *ptr)
{
- assert(((unsigned long)ptr & ~RDXTREE_ENTRY_ADDR_MASK) == 0);
+ assert(((uintptr_t)ptr & ~RDXTREE_ENTRY_ADDR_MASK) == 0);
(void)ptr;
}
static inline void *
rdxtree_entry_addr(void *entry)
{
- return (void *)((unsigned long)entry & RDXTREE_ENTRY_ADDR_MASK);
+ return (void *)((uintptr_t)entry & RDXTREE_ENTRY_ADDR_MASK);
}
static inline int
rdxtree_entry_is_node(const void *entry)
{
- return ((unsigned long)entry & 1) != 0;
+ return ((uintptr_t)entry & 1) != 0;
}
static inline void *
rdxtree_node_to_entry(struct rdxtree_node *node)
{
- return (void *)((unsigned long)node | 1);
+ return (void *)((uintptr_t)node | 1);
}
static int
diff --git a/test/test_avltree.c b/test/test_avltree.c
index 3f11e57..39afe1f 100644
--- a/test/test_avltree.c
+++ b/test/test_avltree.c
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2010, 2011 Richard Braun.
+ * Copyright (c) 2010-2017 Richard Braun.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -104,7 +104,7 @@ main(int argc, char *argv[])
struct avltree tree;
struct avltree_node *node, *tmp;
struct obj *obj;
- unsigned long slot;
+ avltree_slot_t slot;
int i, id;
(void)argc;
diff --git a/test/test_rbtree.c b/test/test_rbtree.c
index db4b6ca..328e1f7 100644
--- a/test/test_rbtree.c
+++ b/test/test_rbtree.c
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2010, 2011 Richard Braun.
+ * Copyright (c) 2010-2017 Richard Braun.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -89,7 +89,7 @@ main(int argc, char *argv[])
struct rbtree tree;
struct rbtree_node *node, *tmp;
struct obj *obj;
- unsigned long slot;
+ rbtree_slot_t slot;
int i, id;
(void)argc;
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-20 02:40:06 +0000