From 5dd4d1f820a8e6a6407fac08cb41f1dec6a9f079 Mon Sep 17 00:00:00 2001 From: Michael Anthony Knyszek Date: Thu, 25 Oct 2018 18:11:54 +0000 Subject: [PATCH] runtime: add predecessor method to treap This change adds a method for computing a treap node's predecessor to the treap, which will simplify the implementation of algorithms used for heap growth scavenging. For #14045. Change-Id: Id203e4bd246db3504f2f0c5163ec36f4579167df Reviewed-on: https://go-review.googlesource.com/c/144717 Run-TryBot: Michael Knyszek TryBot-Result: Gobot Gobot Reviewed-by: Austin Clements --- src/runtime/mgclarge.go | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) diff --git a/src/runtime/mgclarge.go b/src/runtime/mgclarge.go index 11a977d6ba..7bc56259ae 100644 --- a/src/runtime/mgclarge.go +++ b/src/runtime/mgclarge.go @@ -46,6 +46,38 @@ type treapNode struct { priority uint32 // random number used by treap algorithm to keep tree probabilistically balanced } +func (t *treapNode) pred() *treapNode { + if t.left != nil { + // If it has a left child, its predecessor will be + // its right most left (grand)child. + t = t.left + for t.right != nil { + t = t.right + } + return t + } + // If it has no left child, its predecessor will be + // the first grandparent who's right child is its + // ancestor. + // + // We compute this by walking up the treap until the + // current node's parent is its parent's right child. + // + // If we find at any point walking up the treap + // that the current node doesn't have a parent, + // we've hit the root. This means that t is already + // the left-most node in the treap and therefore + // has no predecessor. + for t.parent != nil && t.parent.right != t { + if t.parent.left != 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