From 4b3f04c63b5b1a1bbc4dfd71c34341ea4e935115 Mon Sep 17 00:00:00 2001
From: Michael Anthony Knyszek <mknyszek@google.com>
Date: Fri, 4 Jan 2019 20:17:15 +0000
Subject: runtime: make mTreap iterator bidirectional

This change makes mTreap's iterator type, treapIter, bidirectional
instead of unidirectional. This change helps support moving the find
operation on a treap to return an iterator instead of a treapNode, in
order to hide the details of the treap when accessing elements.

For #28479.

Change-Id: I5dbea4fd4fb9bede6e81bfd089f2368886f98943
Reviewed-on: https://go-review.googlesource.com/c/156918
Reviewed-by: Austin Clements <austin@google.com>
Run-TryBot: Austin Clements <austin@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
---
 src/runtime/mgclarge.go | 54 +++++++++++++++++++++++--------------------------
 1 file changed, 25 insertions(+), 29 deletions(-)

(limited to 'src/runtime/mgclarge.go')

diff --git a/src/runtime/mgclarge.go b/src/runtime/mgclarge.go
index 2a04d4a793..7b01a11780 100644
--- a/src/runtime/mgclarge.go
+++ b/src/runtime/mgclarge.go
@@ -153,15 +153,14 @@ func checkTreapNode(t *treapNode) {
 	}
 }
 
-// treapIter is a unidirectional iterator type which may be used to iterate over a
+// treapIter is a bidirectional iterator type which may be used to iterate over a
 // an mTreap in-order forwards (increasing order) or backwards (decreasing order).
 // Its purpose is to hide details about the treap from users when trying to iterate
 // over it.
 //
-// To create iterators over the treap, call iter or rev on an mTreap.
+// To create iterators over the treap, call start or end on an mTreap.
 type treapIter struct {
-	t   *treapNode
-	inc bool // if true, iterate in increasing order, otherwise decreasing order.
+	t *treapNode
 }
 
 // span returns the span at the current position in the treap.
@@ -179,42 +178,41 @@ func (i *treapIter) valid() bool {
 // next moves the iterator forward by one. Once the iterator
 // ceases to be valid, calling next will panic.
 func (i treapIter) next() treapIter {
-	if i.inc {
-		i.t = i.t.succ()
-	} else {
-		i.t = i.t.pred()
-	}
+	i.t = i.t.succ()
 	return i
 }
 
-// iter returns an iterator which may be used to iterate over the treap
-// in increasing order of span size ("forwards").
-func (root *mTreap) iter() treapIter {
-	i := treapIter{inc: true}
+// prev moves the iterator backwards by one. Once the iterator
+// ceases to be valid, calling prev will panic.
+func (i treapIter) prev() treapIter {
+	i.t = i.t.pred()
+	return i
+}
+
+// start returns an iterator which points to the start of the treap (the
+// left-most node in the treap).
+func (root *mTreap) start() treapIter {
 	t := root.treap
 	if t == nil {
-		return i
+		return treapIter{}
 	}
 	for t.left != nil {
 		t = t.left
 	}
-	i.t = t
-	return i
+	return treapIter{t: t}
 }
 
-// rev returns an iterator which may be used to iterate over the treap
-// in decreasing order of span size ("reverse").
-func (root *mTreap) rev() treapIter {
-	i := treapIter{inc: false}
+// end returns an iterator which points to the end of the treap (the
+// right-most node in the treap).
+func (root *mTreap) end() treapIter {
 	t := root.treap
 	if t == nil {
-		return i
+		return treapIter{}
 	}
 	for t.right != nil {
 		t = t.right
 	}
-	i.t = t
-	return i
+	return treapIter{t: t}
 }
 
 // insert adds span to the large span treap.
@@ -342,13 +340,11 @@ func (root *mTreap) removeSpan(span *mspan) {
 }
 
 // erase removes the element referred to by the current position of the
-// iterator and returns i.next(). This operation consumes the given
-// iterator, so it should no longer be used and iteration should continue
-// from the returned iterator.
-func (root *mTreap) erase(i treapIter) treapIter {
-	n := i.next()
+// iterator. This operation consumes the given iterator, so it should no
+// longer be used. It is up to the caller to get the next or previous
+// iterator before calling erase, if need be.
+func (root *mTreap) erase(i treapIter) {
 	root.removeNode(i.t)
-	return n
 }
 
 // rotateLeft rotates the tree rooted at node x.
-- 
cgit v1.3-6-g1900