diff options
Diffstat (limited to 'src/runtime/mgclarge.go')
-rw-r--r-- | src/runtime/mgclarge.go | 54 |
1 files changed, 25 insertions, 29 deletions
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. |