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_test.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"
	"testing"
)

type sstring string

func (s sstring) String() string {
	return string(s)
}

// wellFormed ensures that a red-black tree meets
// all of its invariants and returns a string identifying
// the first problem encountered. If there is no problem
// then the returned string is empty. The size is also
// returned to allow comparison of calculated tree size
// with expected.
func (t *RBTint32) wellFormed() (s string, i int) {
	if t.root == nil {
		s = ""
		i = 0
		return
	}
	return t.root.wellFormedSubtree(nil, -0x80000000, 0x7fffffff)
}

// wellFormedSubtree ensures that a red-black subtree meets
// all of its invariants and returns a string identifying
// the first problem encountered. If there is no problem
// then the returned string is empty. The size is also
// returned to allow comparison of calculated tree size
// with expected.
func (t *node32) wellFormedSubtree(parent *node32, min, max int32) (s string, i int) {
	i = -1 // initialize to a failing value
	s = "" // s is the reason for failure; empty means okay.

if t.parent != parent {
		s = "t.parent != parent"
		return
	}

if min >= t.key {
		s = "min >= t.key"
		return
	}

if max <= t.key {
		s = "max <= t.key"
		return
	}

l := t.left
	r := t.right
	if l == nil && r == nil {
		if t.rank != rankLeaf {
			s = "leaf rank wrong"
			return
		}
	}
	if l != nil {
		if t.rank < l.rank {
			s = "t.rank < l.rank"
		} else if t.rank > 1+l.rank {
			s = "t.rank > 1+l.rank"
		} else if t.rank <= l.maxChildRank() {
			s = "t.rank <= l.maxChildRank()"
		} else if t.key <= l.key {
			s = "t.key <= l.key"
		}
		if s != "" {
			return
		}
	} else {
		if t.rank != 1 {
			s = "t w/ left nil has rank != 1"
			return
		}
	}
	if r != nil {
		if t.rank < r.rank {
			s = "t.rank < r.rank"
		} else if t.rank > 1+r.rank {
			s = "t.rank > 1+r.rank"
		} else if t.rank <= r.maxChildRank() {
			s = "t.rank <= r.maxChildRank()"
		} else if t.key >= r.key {
			s = "t.key >= r.key"
		}
		if s != "" {
			return
		}
	} else {
		if t.rank != 1 {
			s = "t w/ right nil has rank != 1"
			return
		}
	}
	ii := 1
	if l != nil {
		res, il := l.wellFormedSubtree(t, min, t.key)
		if res != "" {
			s = "L." + res
			return
		}
		ii += il
	}
	if r != nil {
		res, ir := r.wellFormedSubtree(t, t.key, max)
		if res != "" {
			s = "R." + res
			return
		}
		ii += ir
	}
	i = ii
	return
}

func (t *RBTint32) DebugString() string {
	if t.root == nil {
		return ""
	}
	return t.root.DebugString()
}

// DebugString prints the tree with nested information
// to allow an eyeball check on the tree balance.
func (t *node32) DebugString() string {
	s := ""
	if t.left != nil {
		s += "["
		s += t.left.DebugString()
		s += "]"
	}
	s += fmt.Sprintf("%v=%v:%d", t.key, t.data, t.rank)
	if t.right != nil {
		s += "["
		s += t.right.DebugString()
		s += "]"
	}
	return s
}

func allRBT32Ops(te *testing.T, x []int32) {
	t := &RBTint32{}
	for i, d := range x {
		x[i] = d + d // Double everything for glb/lub testing
	}

// fmt.Printf("Inserting double of %v", x)
	k := 0
	min := int32(0x7fffffff)
	max := int32(-0x80000000)
	for _, d := range x {
		if d < min {
			min = d
		}

if d > max {
			max = d
		}

t.Insert(d, sstring(fmt.Sprintf("%v", d)))
		k++
		s, i := t.wellFormed()
		if i != k {
			te.Errorf("Wrong tree size %v, expected %v for %v", i, k, t.DebugString())
		}
		if s != "" {
			te.Errorf("Tree consistency problem at %v", s)
			return
		}
	}

oops := false

for _, d := range x {
		s := fmt.Sprintf("%v", d)
		f := t.Find(d)

// data
		if s != fmt.Sprintf("%v", f) {
			te.Errorf("s(%v) != f(%v)", s, f)
			oops = true
		}
	}

if !oops {
		for _, d := range x {
			s := fmt.Sprintf("%v", d)

kg, g := t.Glb(d + 1)
			kge, ge := t.GlbEq(d)
			kl, l := t.Lub(d - 1)
			kle, le := t.LubEq(d)

// keys
			if d != kg {
				te.Errorf("d(%v) != kg(%v)", d, kg)
			}
			if d != kl {
				te.Errorf("d(%v) != kl(%v)", d, kl)
			}
			if d != kge {
				te.Errorf("d(%v) != kge(%v)", d, kge)
			}
			if d != kle {
				te.Errorf("d(%v) != kle(%v)", d, kle)
			}
			// data
			if s != fmt.Sprintf("%v", g) {
				te.Errorf("s(%v) != g(%v)", s, g)
			}
			if s != fmt.Sprintf("%v", l) {
				te.Errorf("s(%v) != l(%v)", s, l)
			}
			if s != fmt.Sprintf("%v", ge) {
				te.Errorf("s(%v) != ge(%v)", s, ge)
			}
			if s != fmt.Sprintf("%v", le) {
				te.Errorf("s(%v) != le(%v)", s, le)
			}
		}

for _, d := range x {
			s := fmt.Sprintf("%v", d)
			kge, ge := t.GlbEq(d + 1)
			kle, le := t.LubEq(d - 1)
			if d != kge {
				te.Errorf("d(%v) != kge(%v)", d, kge)
			}
			if d != kle {
				te.Errorf("d(%v) != kle(%v)", d, kle)
			}
			if s != fmt.Sprintf("%v", ge) {
				te.Errorf("s(%v) != ge(%v)", s, ge)
			}
			if s != fmt.Sprintf("%v", le) {
				te.Errorf("s(%v) != le(%v)", s, le)
			}
		}

kg, g := t.Glb(min)
		kge, ge := t.GlbEq(min - 1)
		kl, l := t.Lub(max)
		kle, le := t.LubEq(max + 1)
		fmin := t.Find(min - 1)
		fmax := t.Find(min + 11)

if kg != 0 || kge != 0 || kl != 0 || kle != 0 {
			te.Errorf("Got non-zero-key for missing query")
		}

if g != nil || ge != nil || l != nil || le != nil || fmin != nil || fmax != nil {
			te.Errorf("Got non-error-data for missing query")
		}

}
}

func TestAllRBTreeOps(t *testing.T) {
	allRBT32Ops(t, []int32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25})
	allRBT32Ops(t, []int32{22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 3, 2, 1, 25, 24, 23, 12, 11, 10, 9, 8, 7, 6, 5, 4})
	allRBT32Ops(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
	allRBT32Ops(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
	allRBT32Ops(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
	allRBT32Ops(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
}

${this.title}

Code Editor : redblack32_test.go