Gecko [ 167.86.127.34 ]

Name	Size	Permission
gen	[ DIR ]	drwxr-xr-x
testdata	[ DIR ]	drwxr-xr-x
README.md	7.76 KB	-rw-r--r--
TODO	950 B	-rw-r--r--
biasedsparsemap.go	2.71 KB	-rw-r--r--
block.go	8.64 KB	-rw-r--r--
branchelim.go	11.41 KB	-rw-r--r--
branchelim_test.go	5.21 KB	-rw-r--r--
cache.go	2.46 KB	-rw-r--r--
check.go	13.9 KB	-rw-r--r--
checkbce.go	956 B	-rw-r--r--
compile.go	16.22 KB	-rw-r--r--
config.go	11.39 KB	-rw-r--r--
copyelim.go	1.82 KB	-rw-r--r--
copyelim_test.go	1.29 KB	-rw-r--r--
critical.go	3.15 KB	-rw-r--r--
cse.go	10.62 KB	-rw-r--r--
cse_test.go	4.21 KB	-rw-r--r--
deadcode.go	9.73 KB	-rw-r--r--
deadcode_test.go	3.49 KB	-rw-r--r--
deadstore.go	8.98 KB	-rw-r--r--
deadstore_test.go	4.09 KB	-rw-r--r--
debug.go	33.92 KB	-rw-r--r--
debug_test.go	28.68 KB	-rw-r--r--
decompose.go	10.91 KB	-rw-r--r--
dom.go	7.98 KB	-rw-r--r--
dom_test.go	13.34 KB	-rw-r--r--
export_test.go	5.68 KB	-rw-r--r--
flagalloc.go	5.49 KB	-rw-r--r--
func.go	22.17 KB	-rw-r--r--
func_test.go	12.85 KB	-rw-r--r--
fuse.go	5.7 KB	-rw-r--r--
fuse_test.go	5.04 KB	-rw-r--r--
html.go	29.04 KB	-rw-r--r--
id.go	576 B	-rw-r--r--
layout.go	3.56 KB	-rw-r--r--
lca.go	3.71 KB	-rw-r--r--
lca_test.go	1.65 KB	-rw-r--r--
likelyadjust.go	15.23 KB	-rw-r--r--
location.go	2.8 KB	-rw-r--r--
loopbce.go	9.85 KB	-rw-r--r--
loopreschedchecks.go	15.36 KB	-rw-r--r--
looprotate.go	2.24 KB	-rw-r--r--
lower.go	1.24 KB	-rw-r--r--
magic.go	13.42 KB	-rw-r--r--
magic_test.go	9.1 KB	-rw-r--r--
nilcheck.go	11.11 KB	-rw-r--r--
nilcheck_test.go	12.07 KB	-rw-r--r--
numberlines.go	8.44 KB	-rw-r--r--
op.go	8.74 KB	-rw-r--r--
opGen.go	839.32 KB	-rw-r--r--
opt.go	290 B	-rw-r--r--
passbm_test.go	3.14 KB	-rw-r--r--
phielim.go	1.47 KB	-rw-r--r--
phiopt.go	3.96 KB	-rw-r--r--
poset.go	37.23 KB	-rw-r--r--
poset_test.go	18.14 KB	-rw-r--r--
print.go	2.98 KB	-rw-r--r--
prove.go	36.68 KB	-rw-r--r--
redblack32.go	8.9 KB	-rw-r--r--
redblack32_test.go	5.96 KB	-rw-r--r--
regalloc.go	76.36 KB	-rw-r--r--
regalloc_test.go	6.41 KB	-rw-r--r--
rewrite.go	33.06 KB	-rw-r--r--
rewrite386.go	514.14 KB	-rw-r--r--
rewrite386splitload.go	3.7 KB	-rw-r--r--
rewriteAMD64.go	1.31 MB	-rw-r--r--
rewriteAMD64splitload.go	4.95 KB	-rw-r--r--
rewriteARM.go	538.26 KB	-rw-r--r--
rewriteARM64.go	837.68 KB	-rw-r--r--
rewriteMIPS.go	203.31 KB	-rw-r--r--
rewriteMIPS64.go	227.84 KB	-rw-r--r--
rewritePPC64.go	661.88 KB	-rw-r--r--
rewriteRISCV64.go	123.11 KB	-rw-r--r--
rewriteS390X.go	904.36 KB	-rw-r--r--
rewriteWasm.go	136.86 KB	-rw-r--r--
rewrite_test.go	3.01 KB	-rw-r--r--
rewritedec.go	10.56 KB	-rw-r--r--
rewritedec64.go	64.01 KB	-rw-r--r--
rewritedecArgs.go	6.6 KB	-rw-r--r--
rewritegeneric.go	1.09 MB	-rw-r--r--
schedule.go	13.99 KB	-rw-r--r--
schedule_test.go	2.91 KB	-rw-r--r--
shift_test.go	4.05 KB	-rw-r--r--
shortcircuit.go	3.97 KB	-rw-r--r--
shortcircuit_test.go	1.31 KB	-rw-r--r--
sizeof_test.go	855 B	-rw-r--r--
softfloat.go	1.94 KB	-rw-r--r--
sparsemap.go	1.98 KB	-rw-r--r--
sparseset.go	1.54 KB	-rw-r--r--
sparsetree.go	7.88 KB	-rw-r--r--
sparsetreemap.go	7.67 KB	-rw-r--r--
stackalloc.go	10.95 KB	-rw-r--r--
stackframe.go	290 B	-rw-r--r--
stmtlines_test.go	2.75 KB	-rw-r--r--
tighten.go	4.21 KB	-rw-r--r--
trim.go	4.24 KB	-rw-r--r--
value.go	10.71 KB	-rw-r--r--
writebarrier.go	17.92 KB	-rw-r--r--
writebarrier_test.go	1.75 KB	-rw-r--r--
xposmap.go	3.29 KB	-rw-r--r--
zcse.go	2.12 KB	-rw-r--r--
zeroextension_test.go	1.66 KB	-rw-r--r--

Code Editor : redblack32.go

// 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
}

${this.title}

Code Editor : redblack32.go