diff options
Diffstat (limited to '')
-rw-r--r-- | dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/binary-tree-freelist.go | 132 |
1 files changed, 132 insertions, 0 deletions
diff --git a/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/binary-tree-freelist.go b/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/binary-tree-freelist.go new file mode 100644 index 0000000..e4c3e8a --- /dev/null +++ b/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/binary-tree-freelist.go @@ -0,0 +1,132 @@ +//go:build ignore +// +build ignore + +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + * based on C program by Kevin Carson + */ + +package main + +import ( + "flag" + "fmt" +) + +var n = flag.Int("n", 15, "depth") + +type Node struct { + item int + left, right *Node +} + +type Arena struct { + head *Node +} + +var arena Arena + +func (n *Node) free() { + if n.left != nil { + n.left.free() + } + if n.right != nil { + n.right.free() + } + n.left = arena.head + arena.head = n +} + +func (a *Arena) New(item int, left, right *Node) *Node { + if a.head == nil { + nodes := make([]Node, 3<<uint(*n)) + for i := 0; i < len(nodes)-1; i++ { + nodes[i].left = &nodes[i+1] + } + a.head = &nodes[0] + } + n := a.head + a.head = a.head.left + n.item = item + n.left = left + n.right = right + return n +} + +func bottomUpTree(item, depth int) *Node { + if depth <= 0 { + return arena.New(item, nil, nil) + } + return arena.New(item, bottomUpTree(2*item-1, depth-1), bottomUpTree(2*item, depth-1)) +} + +func (n *Node) itemCheck() int { + if n.left == nil { + return n.item + } + return n.item + n.left.itemCheck() - n.right.itemCheck() +} + +const minDepth = 4 + +func main() { + flag.Parse() + + maxDepth := *n + if minDepth+2 > *n { + maxDepth = minDepth + 2 + } + stretchDepth := maxDepth + 1 + + check := bottomUpTree(0, stretchDepth).itemCheck() + fmt.Printf("stretch tree of depth %d\t check: %d\n", stretchDepth, check) + + longLivedTree := bottomUpTree(0, maxDepth) + + for depth := minDepth; depth <= maxDepth; depth += 2 { + iterations := 1 << uint(maxDepth-depth+minDepth) + check = 0 + + for i := 1; i <= iterations; i++ { + t := bottomUpTree(i, depth) + check += t.itemCheck() + t.free() + t = bottomUpTree(-i, depth) + check += t.itemCheck() + t.free() + } + fmt.Printf("%d\t trees of depth %d\t check: %d\n", iterations*2, depth, check) + } + fmt.Printf("long lived tree of depth %d\t check: %d\n", maxDepth, longLivedTree.itemCheck()) +} |