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>

diff --git a/test-treap.c b/test-treap.c
index cdba5111e19cd850f262108a330ce5d4ce63a166..ab8c951c6eb39f54a9885dd15c173f974d7357d5 100644 (file)
--- a/test-treap.c
+++ b/test-treap.c
@@ -38,9 +38,14 @@ int main(int argc, char *argv[])
                usage("test-treap < ints");
 
        while (strbuf_getline(&sb, stdin, '\n') != EOF) {
                usage("test-treap < ints");
 
        while (strbuf_getline(&sb, stdin, '\n') != EOF) {

-               item = node_alloc(1);
-               strtonode(node_pointer(item), sb.buf);
-               treap_insert(&root, node_pointer(item));
+               struct int_node *node = node_pointer(node_alloc(1));
+
+               item = node_offset(node);
+               strtonode(node, sb.buf);
+               node = treap_insert(&root, node_pointer(item));
+               if (node_offset(node) != item)
+                       die("inserted %"PRIu32" in place of %"PRIu32"",
+                               node_offset(node), item);

        }
 
        item = node_offset(treap_first(&root));
        }
 
        item = node_offset(treap_first(&root));

diff --git a/vcs-svn/trp.h b/vcs-svn/trp.h
index ee35c688a0008ac210cdd28a82191c5a7cb7987e..c32b9184e9b8420e4d4e2904806bd2f14814132b 100644 (file)
--- 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; \
        } \
 } \
                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); \
 { \
        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) \
 { \
 } \
 a_attr uint32_t MAYBE_UNUSED a_pre##remove_recurse(uint32_t cur_node, uint32_t rem_node) \
 { \

diff --git a/vcs-svn/trp.txt b/vcs-svn/trp.txt
index eb4c191875f4580d18c1db1913cfe99f658a5f83..5ca6b42edb289c5f5714ae2f0a09710d40dd14f3 100644 (file)
--- a/vcs-svn/trp.txt
+++ b/vcs-svn/trp.txt
@@ -21,7 +21,9 @@ The caller:
 
 . Allocates a `struct trp_root` variable and sets it to {~0}.
 
 
 . Allocates a `struct trp_root` variable and sets it to {~0}.
 

-. Adds new nodes to the set using `foo_insert`.
+. Adds new nodes to the set using `foo_insert`.  Any pointers
+  to existing nodes cannot be relied upon any more, so the caller
+  might retrieve them anew with `foo_pointer`.

 
 . Can find a specific item in the set using `foo_search`.
 
 
 . Can find a specific item in the set using `foo_search`.
 


@@ -73,10 +75,14 @@ int (*cmp)(node_type \*a, node_type \*b)
 and returning a value less than, equal to, or greater than zero
 according to the result of comparison.
 
 and returning a value less than, equal to, or greater than zero
 according to the result of comparison.
 

-void foo_insert(struct trp_root *treap, node_type \*node)::
+node_type {asterisk}foo_insert(struct trp_root *treap, node_type \*node)::

 
        Insert node into treap.  If inserted multiple times,
        a node will appear in the treap multiple times.
 
        Insert node into treap.  If inserted multiple times,
        a node will appear in the treap multiple times.

++
+The return value is the address of the node within the treap,
+which might differ from `node` if `pool_alloc` had to call
+`realloc` to expand the pool.

 
 void foo_remove(struct trp_root *treap, node_type \*node)::
 
 
 void foo_remove(struct trp_root *treap, node_type \*node)::