treap: make treap_insert return inserted node

Suppose I try the following:

	struct int_node *node = node_pointer(node_alloc(1));
	node->n = 5;
	treap_insert(&root, node);
	printf("%d\n", node->n);

Usually the result will be 5.  But since treap_insert draws memory
from the node pool, if the caller is unlucky then (1) the node pool
will be full and (2) realloc will be forced to move the node pool to
find room, so the node address becomes invalid and the result of
dereferencing it is undefined.

So we ought to use offsets in preference to pointers for references
that would remain valid after a call to treap_insert.  Tweak the
signature to hint at a certain special case: since the inserted node
can change address (though not offset), as a convenience teach
treap_insert to return its new address.

So the motivational example could be fixed by adding "node =".

	struct int_node *node = node_pointer(node_alloc(1));
	node->n = 5;
	node = treap_insert(&root, node);
	printf("%d\n", node->n);

Based on a true story.

Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 2 insertions, 1 deletions

diff --git a/vcs-svn/trp.h b/vcs-svn/trp.h
index ee35c688a0..c32b9184e9 100644
--- a/vcs-svn/trp.h
+++ b/vcs-svn/trp.h
@@ -188,11 +188,12 @@ a_attr uint32_t MAYBE_UNUSED a_pre##insert_recurse(uint32_t cur_node, uint32_t i
 		return ret; \
 	} \
 } \
-a_attr void MAYBE_UNUSED a_pre##insert(struct trp_root *treap, a_type *node) \
+a_attr a_type *MAYBE_UNUSED a_pre##insert(struct trp_root *treap, a_type *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); \
+	return trpn_pointer(a_base, offset); \
 } \
 a_attr uint32_t MAYBE_UNUSED a_pre##remove_recurse(uint32_t cur_node, uint32_t rem_node) \
 { \