From 4b3f04c63b5b1a1bbc4dfd71c34341ea4e935115 Mon Sep 17 00:00:00 2001 From: Michael Anthony Knyszek 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 Run-TryBot: Austin Clements TryBot-Result: Gobot Gobot --- src/runtime/mheap.go | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) (limited to 'src/runtime/mheap.go') 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 } -- cgit v1.3-6-g1900