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@xxxxxxxxx>
---
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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html