Re: [PATCH 4/9] Add treap implementation

From: Jonathan Nieder <jrnieder@gmail.com>
To: Ramkumar Ramachandra <artagnon@gmail.com>
Cc: Git Mailing List <git@vger.kernel.org>,
	David Michael Barr <david.barr@cordelta.com>,
	Sverre Rabbelier <srabbelier@gmail.com>,
	Junio C Hamano <gitster@pobox.com>
Subject: Re: [PATCH 4/9] Add treap implementation
Date: Fri, 16 Jul 2010 13:26:19 -0500	[thread overview]
Message-ID: <20100716182619.GA15661@burratino> (raw)
In-Reply-To: <20100716102313.GC14374@burratino>

Jonathan Nieder wrote:

> Tweaked treap_search() to always return the node after a missing
> node, like it is documented to.

In this case, the documentation was wrong.

> For vcs-svn this doesn’t matter

Or rather, it does.  Sorry about that.

-- 8< --
Subject: vcs-svn: treap_search should return NULL for missing items

In a misguided attempt to make the code match the documentation,
commit 4692f8e7d (Add treap implementation, 2010-07-15) changed
the semantics of treap_search to return the /next/ node when a
node is missing.

That is great in some circumstances (and the new tests even rely on
it), but the rest of vcs-svn relies on treap_search to return
NULL in that case instead.  The documentation only suggested
otherwise because of a typo.

So fix it: now treap_search can do what it was always supposed
to (return NULL on failure) and Jason Evans’s treap_nsearch function
can be used to keep the test suite working.

Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
---
 test-treap.c    |    2 +-
 vcs-svn/trp.h   |   13 +++++++++++++
 vcs-svn/trp.txt |    9 +++++++--
 3 files changed, 21 insertions(+), 3 deletions(-)

diff --git a/test-treap.c b/test-treap.c
index eae7324..cdba511 100644
--- a/test-treap.c
+++ b/test-treap.c
@@ -52,7 +52,7 @@ int main(int argc, char *argv[])
 		next = node_offset(treap_next(&root, node_pointer(item)));
 
 		treap_remove(&root, node_pointer(item));
-		item = node_offset(treap_search(&root, tmp));
+		item = node_offset(treap_nsearch(&root, tmp));
 
 		if (item != next && (!~item || node_pointer(item)->n != tmp->n))
 			die("found %"PRIuMAX" in place of %"PRIuMAX"",
diff --git a/vcs-svn/trp.h b/vcs-svn/trp.h
index 49940cf..1f5f51f 100644
--- a/vcs-svn/trp.h
+++ b/vcs-svn/trp.h
@@ -138,6 +138,19 @@ a_attr a_type MAYBE_UNUSED *a_pre##search(struct trp_root *treap, a_type *key) \
 	uint32_t ret = treap->trp_root; \
 	while (~ret && (cmp = (a_cmp)(key, trpn_pointer(a_base,ret)))) { \
 		if (cmp < 0) { \
+			ret = trp_left_get(a_base, a_field, ret); \
+		} else { \
+			ret = trp_right_get(a_base, a_field, ret); \
+		} \
+	} \
+	return trpn_pointer(a_base, ret); \
+} \
+a_attr a_type MAYBE_UNUSED *a_pre##nsearch(struct trp_root *treap, a_type *key) \
+{ \
+	int cmp; \
+	uint32_t ret = treap->trp_root; \
+	while (~ret && (cmp = (a_cmp)(key, trpn_pointer(a_base,ret)))) { \
+		if (cmp < 0) { \
 			if (!~trp_left_get(a_base, a_field, ret)) \
 				break; \
 			ret = trp_left_get(a_base, a_field, ret); \
diff --git a/vcs-svn/trp.txt b/vcs-svn/trp.txt
index 9247eba..eb4c191 100644
--- a/vcs-svn/trp.txt
+++ b/vcs-svn/trp.txt
@@ -86,8 +86,13 @@ void foo_remove(struct trp_root *treap, node_type \*node)::
 node_type *foo_search(struct trp_root \*treap, node_type \*key)::
 
 	Search for a node that matches key.  If no match is found,
-	return what would be key's successor, were key in treap
-	(NULL if no successor).
+	result is NULL.
+
+node_type *foo_nsearch(struct trp_root \*treap, node_type \*key)::
+
+	Like `foo_search`, but if if the key is missing return what
+	would be key's successor, were key in treap (NULL if no
+	successor).
 
 node_type *foo_first(struct trp_root \*treap)::
 
-- 
1.7.2.rc2
