diff options
Diffstat (limited to 'src/cmd/compile/internal/ssa/redblack32.go')
| -rw-r--r-- | src/cmd/compile/internal/ssa/redblack32.go | 429 |
1 files changed, 429 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ssa/redblack32.go b/src/cmd/compile/internal/ssa/redblack32.go new file mode 100644 index 0000000..fc9cc71 --- /dev/null +++ b/src/cmd/compile/internal/ssa/redblack32.go @@ -0,0 +1,429 @@ +// Copyright 2016 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package ssa + +import "fmt" + +const ( + rankLeaf rbrank = 1 + rankZero rbrank = 0 +) + +type rbrank int8 + +// RBTint32 is a red-black tree with data stored at internal nodes, +// following Tarjan, Data Structures and Network Algorithms, +// pp 48-52, using explicit rank instead of red and black. +// Deletion is not yet implemented because it is not yet needed. +// Extra operations glb, lub, glbEq, lubEq are provided for +// use in sparse lookup algorithms. +type RBTint32 struct { + root *node32 + // An extra-clever implementation will have special cases + // for small sets, but we are not extra-clever today. +} + +func (t *RBTint32) String() string { + if t.root == nil { + return "[]" + } + return "[" + t.root.String() + "]" +} + +func (t *node32) String() string { + s := "" + if t.left != nil { + s = t.left.String() + " " + } + s = s + fmt.Sprintf("k=%d,d=%v", t.key, t.data) + if t.right != nil { + s = s + " " + t.right.String() + } + return s +} + +type node32 struct { + // Standard conventions hold for left = smaller, right = larger + left, right, parent *node32 + data interface{} + key int32 + rank rbrank // From Tarjan pp 48-49: + // If x is a node with a parent, then x.rank <= x.parent.rank <= x.rank+1. + // If x is a node with a grandparent, then x.rank < x.parent.parent.rank. + // If x is an "external [null] node", then x.rank = 0 && x.parent.rank = 1. + // Any node with one or more null children should have rank = 1. +} + +// makeNode returns a new leaf node with the given key and nil data. +func (t *RBTint32) makeNode(key int32) *node32 { + return &node32{key: key, rank: rankLeaf} +} + +// IsEmpty reports whether t is empty. +func (t *RBTint32) IsEmpty() bool { + return t.root == nil +} + +// IsSingle reports whether t is a singleton (leaf). +func (t *RBTint32) IsSingle() bool { + return t.root != nil && t.root.isLeaf() +} + +// VisitInOrder applies f to the key and data pairs in t, +// with keys ordered from smallest to largest. +func (t *RBTint32) VisitInOrder(f func(int32, interface{})) { + if t.root == nil { + return + } + t.root.visitInOrder(f) +} + +func (n *node32) Data() interface{} { + if n == nil { + return nil + } + return n.data +} + +func (n *node32) keyAndData() (k int32, d interface{}) { + if n == nil { + k = 0 + d = nil + } else { + k = n.key + d = n.data + } + return +} + +func (n *node32) Rank() rbrank { + if n == nil { + return 0 + } + return n.rank +} + +// Find returns the data associated with key in the tree, or +// nil if key is not in the tree. +func (t *RBTint32) Find(key int32) interface{} { + return t.root.find(key).Data() +} + +// Insert adds key to the tree and associates key with data. +// If key was already in the tree, it updates the associated data. +// Insert returns the previous data associated with key, +// or nil if key was not present. +// Insert panics if data is nil. +func (t *RBTint32) Insert(key int32, data interface{}) interface{} { + if data == nil { + panic("Cannot insert nil data into tree") + } + n := t.root + var newroot *node32 + if n == nil { + n = t.makeNode(key) + newroot = n + } else { + newroot, n = n.insert(key, t) + } + r := n.data + n.data = data + t.root = newroot + return r +} + +// Min returns the minimum element of t and its associated data. +// If t is empty, then (0, nil) is returned. +func (t *RBTint32) Min() (k int32, d interface{}) { + return t.root.min().keyAndData() +} + +// Max returns the maximum element of t and its associated data. +// If t is empty, then (0, nil) is returned. +func (t *RBTint32) Max() (k int32, d interface{}) { + return t.root.max().keyAndData() +} + +// Glb returns the greatest-lower-bound-exclusive of x and its associated +// data. If x has no glb in the tree, then (0, nil) is returned. +func (t *RBTint32) Glb(x int32) (k int32, d interface{}) { + return t.root.glb(x, false).keyAndData() +} + +// GlbEq returns the greatest-lower-bound-inclusive of x and its associated +// data. If x has no glbEQ in the tree, then (0, nil) is returned. +func (t *RBTint32) GlbEq(x int32) (k int32, d interface{}) { + return t.root.glb(x, true).keyAndData() +} + +// Lub returns the least-upper-bound-exclusive of x and its associated +// data. If x has no lub in the tree, then (0, nil) is returned. +func (t *RBTint32) Lub(x int32) (k int32, d interface{}) { + return t.root.lub(x, false).keyAndData() +} + +// LubEq returns the least-upper-bound-inclusive of x and its associated +// data. If x has no lubEq in the tree, then (0, nil) is returned. +func (t *RBTint32) LubEq(x int32) (k int32, d interface{}) { + return t.root.lub(x, true).keyAndData() +} + +func (t *node32) isLeaf() bool { + return t.left == nil && t.right == nil +} + +func (t *node32) visitInOrder(f func(int32, interface{})) { + if t.left != nil { + t.left.visitInOrder(f) + } + f(t.key, t.data) + if t.right != nil { + t.right.visitInOrder(f) + } +} + +func (t *node32) maxChildRank() rbrank { + if t.left == nil { + if t.right == nil { + return rankZero + } + return t.right.rank + } + if t.right == nil { + return t.left.rank + } + if t.right.rank > t.left.rank { + return t.right.rank + } + return t.left.rank +} + +func (t *node32) minChildRank() rbrank { + if t.left == nil || t.right == nil { + return rankZero + } + if t.right.rank < t.left.rank { + return t.right.rank + } + return t.left.rank +} + +func (t *node32) find(key int32) *node32 { + for t != nil { + if key < t.key { + t = t.left + } else if key > t.key { + t = t.right + } else { + return t + } + } + return nil +} + +func (t *node32) min() *node32 { + if t == nil { + return t + } + for t.left != nil { + t = t.left + } + return t +} + +func (t *node32) max() *node32 { + if t == nil { + return t + } + for t.right != nil { + t = t.right + } + return t +} + +func (t *node32) glb(key int32, allow_eq bool) *node32 { + var best *node32 + for t != nil { + if key <= t.key { + if key == t.key && allow_eq { + return t + } + // t is too big, glb is to left. + t = t.left + } else { + // t is a lower bound, record it and seek a better one. + best = t + t = t.right + } + } + return best +} + +func (t *node32) lub(key int32, allow_eq bool) *node32 { + var best *node32 + for t != nil { + if key >= t.key { + if key == t.key && allow_eq { + return t + } + // t is too small, lub is to right. + t = t.right + } else { + // t is a upper bound, record it and seek a better one. + best = t + t = t.left + } + } + return best +} + +func (t *node32) insert(x int32, w *RBTint32) (newroot, newnode *node32) { + // defaults + newroot = t + newnode = t + if x == t.key { + return + } + if x < t.key { + if t.left == nil { + n := w.makeNode(x) + n.parent = t + t.left = n + newnode = n + return + } + var new_l *node32 + new_l, newnode = t.left.insert(x, w) + t.left = new_l + new_l.parent = t + newrank := 1 + new_l.maxChildRank() + if newrank > t.rank { + if newrank > 1+t.right.Rank() { // rotations required + if new_l.left.Rank() < new_l.right.Rank() { + // double rotation + t.left = new_l.rightToRoot() + } + newroot = t.leftToRoot() + return + } else { + t.rank = newrank + } + } + } else { // x > t.key + if t.right == nil { + n := w.makeNode(x) + n.parent = t + t.right = n + newnode = n + return + } + var new_r *node32 + new_r, newnode = t.right.insert(x, w) + t.right = new_r + new_r.parent = t + newrank := 1 + new_r.maxChildRank() + if newrank > t.rank { + if newrank > 1+t.left.Rank() { // rotations required + if new_r.right.Rank() < new_r.left.Rank() { + // double rotation + t.right = new_r.leftToRoot() + } + newroot = t.rightToRoot() + return + } else { + t.rank = newrank + } + } + } + return +} + +func (t *node32) rightToRoot() *node32 { + // this + // left right + // rl rr + // + // becomes + // + // right + // this rr + // left rl + // + right := t.right + rl := right.left + right.parent = t.parent + right.left = t + t.parent = right + // parent's child ptr fixed in caller + t.right = rl + if rl != nil { + rl.parent = t + } + return right +} + +func (t *node32) leftToRoot() *node32 { + // this + // left right + // ll lr + // + // becomes + // + // left + // ll this + // lr right + // + left := t.left + lr := left.right + left.parent = t.parent + left.right = t + t.parent = left + // parent's child ptr fixed in caller + t.left = lr + if lr != nil { + lr.parent = t + } + return left +} + +// next returns the successor of t in a left-to-right +// walk of the tree in which t is embedded. +func (t *node32) next() *node32 { + // If there is a right child, it is to the right + r := t.right + if r != nil { + return r.min() + } + // if t is p.left, then p, else repeat. + p := t.parent + for p != nil { + if p.left == t { + return p + } + t = p + p = t.parent + } + return nil +} + +// prev returns the predecessor of t in a left-to-right +// walk of the tree in which t is embedded. +func (t *node32) prev() *node32 { + // If there is a left child, it is to the left + l := t.left + if l != nil { + return l.max() + } + // if t is p.right, then p, else repeat. + p := t.parent + for p != nil { + if p.right == t { + return p + } + t = p + p = t.parent + } + return nil +} |