diff options
| author | Michael Anthony Knyszek <mknyszek@google.com> | 2019-01-04 20:17:15 +0000 |
|---|---|---|
| committer | Michael Knyszek <mknyszek@google.com> | 2019-01-10 18:15:48 +0000 |
| commit | 4b3f04c63b5b1a1bbc4dfd71c34341ea4e935115 (patch) | |
| tree | 5da95c95bcc936225cc3e90ca5be87cf920d593f /src/runtime/mheap.go | |
| parent | 44cf595a7efcd3d7048c745d1d1531696bcb5941 (diff) | |
| download | go1.12beta2.tar.xz | |
runtime: make mTreap iterator bidirectionalgo1.12beta2
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>
Diffstat (limited to 'src/runtime/mheap.go')
| -rw-r--r-- | src/runtime/mheap.go | 14 |
1 files changed, 8 insertions, 6 deletions
diff --git a/src/runtime/mheap.go b/src/runtime/mheap.go index 9d7d683cd1..f5b5ba99b8 100644 --- a/src/runtime/mheap.go +++ b/src/runtime/mheap.go @@ -1287,7 +1287,7 @@ func (h *mheap) scavengeLargest(nbytes uintptr) { // 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 @@ func (h *mheap) scavengeLargest(nbytes uintptr) { // 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) scavengeLargest(nbytes uintptr) { 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 } |