From 239341f3b6b5c921c2352ce8267d74948476d8fa Mon Sep 17 00:00:00 2001 From: Michael Anthony Knyszek Date: Thu, 25 Oct 2018 18:18:53 +0000 Subject: [PATCH] runtime: add successor method to treap This change adds a method for computing a treap node's successor to the treap, which will simplify the implementation of algorithms used for heap growth scavenging. For #14045. Change-Id: If2af3f2707dbcbef5fb6e42cb2712061f9da5129 Reviewed-on: https://go-review.googlesource.com/c/144718 Run-TryBot: Michael Knyszek TryBot-Result: Gobot Gobot Reviewed-by: Austin Clements --- src/runtime/mgclarge.go | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) diff --git a/src/runtime/mgclarge.go b/src/runtime/mgclarge.go index 7bc56259ae..ec4f7ead71 100644 --- a/src/runtime/mgclarge.go +++ b/src/runtime/mgclarge.go @@ -78,6 +78,27 @@ func (t *treapNode) pred() *treapNode { return t.parent } +func (t *treapNode) succ() *treapNode { + if t.right != nil { + // If it has a right child, its successor will be + // its left-most right (grand)child. + t = t.right + for t.left != nil { + t = t.left + } + return t + } + // See pred. + for t.parent != nil && t.parent.left != t { + if t.parent.right != t { + println("runtime: predecessor t=", t, "t.spanKey=", t.spanKey) + throw("node is not its parent's child") + } + t = t.parent + } + return t.parent +} + // isSpanInTreap is handy for debugging. One should hold the heap lock, usually // mheap_.lock(). func (t *treapNode) isSpanInTreap(s *mspan) bool { -- 2.50.0