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>
diff --git a/src/runtime/export_test.go b/src/runtime/export_test.go
index de66b07..9eaf92d 100644
--- a/src/runtime/export_test.go
+++ b/src/runtime/export_test.go
@@ -337,7 +337,7 @@
slow.BySize[i].Frees = bySize[i].Frees
}
- for i := mheap_.scav.iter(); i.valid(); i = i.next() {
+ for i := mheap_.scav.start(); i.valid(); i = i.next() {
slow.HeapReleased += uint64(i.span().released())
}
diff --git a/src/runtime/mgclarge.go b/src/runtime/mgclarge.go
index 2a04d4a..7b01a11 100644
--- a/src/runtime/mgclarge.go
+++ b/src/runtime/mgclarge.go
@@ -153,15 +153,14 @@
}
}
-// 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 @@
// 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 @@
}
// 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.
diff --git a/src/runtime/mheap.go b/src/runtime/mheap.go
index 9d7d683..f5b5ba9 100644
--- a/src/runtime/mheap.go
+++ b/src/runtime/mheap.go
@@ -1287,7 +1287,7 @@
// Iterate over the treap backwards (from largest to smallest) scavenging spans
// until we've reached our quota of nbytes.
released := uintptr(0)
- for t := h.free.rev(); released < nbytes && t.valid(); {
+ for t := h.free.end(); released < nbytes && t.valid(); {
s := t.span()
r := s.scavenge()
if r == 0 {
@@ -1302,7 +1302,9 @@
// those which have it unset are only in the `free` treap.
return
}
- t = h.free.erase(t)
+ n := t.prev()
+ h.free.erase(t)
+ t = n
h.scav.insert(s)
released += r
}
@@ -1314,18 +1316,18 @@
func (h *mheap) scavengeAll(now, limit uint64) uintptr {
// Iterate over the treap scavenging spans if unused for at least limit time.
released := uintptr(0)
- for t := h.free.iter(); t.valid(); {
+ for t := h.free.start(); t.valid(); {
s := t.span()
+ n := t.next()
if (now - uint64(s.unusedsince)) > limit {
r := s.scavenge()
if r != 0 {
- t = h.free.erase(t)
+ h.free.erase(t)
h.scav.insert(s)
released += r
- continue
}
}
- t = t.next()
+ t = n
}
return released
}
