From 4c48af0c8e817db40e2bca9dad977acd470d36e8 Mon Sep 17 00:00:00 2001
From: David Barr <david.barr@cordelta.com>
Date: Fri, 4 Jun 2010 10:46:25 +1000
Subject: [PATCH] Refactor trp.h to use offsets internally.

Using offsets rather than pointers on the stack will allow
allocations to occur while traversing the treap.
This will be very helpful when implementing immutable treaps.

Signed-off-by: David Barr <david.barr@cordelta.com>
---
 trp.h | 45 ++++++++++++++++++++++-----------------------
 1 file changed, 22 insertions(+), 23 deletions(-)

diff --git a/trp.h b/trp.h
index 632778c..53e7be5 100644
--- a/trp.h
+++ b/trp.h
@@ -30,25 +30,25 @@ struct trp_root {
 
 /* Left accessors. */
 #define trp_left_get(a_base, a_field, a_node) \
-	trpn_pointer(a_base, (a_node)->a_field.trpn_left)
+	(trpn_pointer(a_base, a_node)->a_field.trpn_left)
 #define trp_left_set(a_base, a_field, a_node, a_left) \
-	(a_node)->a_field.trpn_left = trpn_offset(a_base, a_left)
+	do { trp_left_get(a_base, a_field, a_node) = (a_left); } while(0)
 
 /* Right accessors. */
 #define trp_right_get(a_base, a_field, a_node) \
-	trpn_pointer(a_base, (a_node)->a_field.trpn_right)
+	(trpn_pointer(a_base, a_node)->a_field.trpn_right)
 #define trp_right_set(a_base, a_field, a_node, a_right) \
-	(a_node)->a_field.trpn_right = trpn_offset(a_base, a_right)
+	do { trp_right_get(a_base, a_field, a_node) = (a_right); } while(0)
 
 /* Priority accessors. */
 #define KNUTH_GOLDEN_RATIO_32BIT 2654435761u
 #define trp_prio_get(a_node) \
-	(KNUTH_GOLDEN_RATIO_32BIT*(uint32_t)(uintptr_t)(a_node))
+	(KNUTH_GOLDEN_RATIO_32BIT*(a_node))
 
 /* Node initializer. */
 #define trp_node_new(a_base, a_field, a_node) \
-	trp_left_set(a_base, a_field, (a_node), NULL); \
-	trp_right_set(a_base, a_field, (a_node), NULL)
+	trp_left_set(a_base, a_field, (a_node), ~0); \
+	trp_right_set(a_base, a_field, (a_node), ~0)
 
 /* Internal utility macros. */
 #define trpn_rotate_left(a_base, a_field, a_node, r_node) \
@@ -66,11 +66,10 @@ struct trp_root {
 #define trp_gen(a_attr, a_pre, a_type, a_field, a_base, a_cmp) \
 a_attr a_type *a_pre##psearch(struct trp_root *treap, a_type *key) \
 { \
-	a_type *ret; \
-	a_type *tnode = trpn_pointer(a_base, treap->trp_root); \
-	ret = NULL; \
-	while (tnode != NULL) { \
-		int cmp = (a_cmp)(key, tnode); \
+	uint32_t ret = ~0; \
+	uint32_t tnode = treap->trp_root; \
+	while (~tnode) { \
+		int cmp = (a_cmp)(key, trpn_pointer(a_base, tnode)); \
 		if (cmp < 0) \
 			tnode = trp_left_get(a_base, a_field, tnode); \
 		else if (cmp > 0) { \
@@ -81,17 +80,18 @@ a_attr a_type *a_pre##psearch(struct trp_root *treap, a_type *key) \
 			break; \
 		} \
 	} \
-	return (ret); \
+	return trpn_pointer(a_base, ret); \
 } \
-a_attr a_type *a_pre##insert_recurse(a_type *cur_node, a_type *ins_node) \
+a_attr uint32_t a_pre##insert_recurse(uint32_t cur_node, uint32_t ins_node) \
 { \
-	if (cur_node == NULL) \
+	if (cur_node == ~0) \
 		return (ins_node); \
 	else { \
-		a_type *ret; \
-		int cmp = a_cmp(ins_node, cur_node); \
+		uint32_t ret; \
+		int cmp = (a_cmp)(trpn_pointer(a_base, ins_node), \
+					trpn_pointer(a_base, cur_node)); \
 		if (cmp < 0) { \
-			a_type *left = a_pre##insert_recurse( \
+			uint32_t left = a_pre##insert_recurse( \
 				trp_left_get(a_base, a_field, cur_node), ins_node); \
 			trp_left_set(a_base, a_field, cur_node, left); \
 			if (trp_prio_get(left) < trp_prio_get(cur_node)) \
@@ -99,7 +99,7 @@ a_attr a_type *a_pre##insert_recurse(a_type *cur_node, a_type *ins_node) \
 			else \
 				ret = cur_node; \
 		} else { \
-			a_type *right = a_pre##insert_recurse( \
+			uint32_t right = a_pre##insert_recurse( \
 				trp_right_get(a_base, a_field, cur_node), ins_node); \
 			trp_right_set(a_base, a_field, cur_node, right); \
 			if (trp_prio_get(right) < trp_prio_get(cur_node)) \
@@ -112,10 +112,9 @@ a_attr a_type *a_pre##insert_recurse(a_type *cur_node, a_type *ins_node) \
 } \
 a_attr void a_pre##insert(struct trp_root *treap, a_type *node) \
 { \
-	trp_node_new(a_base, a_field, node); \
-	treap->trp_root = trpn_offset(a_base, a_pre##insert_recurse( \
-					      trpn_pointer(a_base, treap->trp_root), \
-					      node)); \
+	uint32_t offset = trpn_offset(a_base, node); \
+	trp_node_new(a_base, a_field, offset); \
+	treap->trp_root = a_pre##insert_recurse( treap->trp_root, offset); \
 }
 
 #endif
-- 
2.11.4.GIT