diff options
| -rw-r--r-- | tests/gc/bintrees.nim | 54 |
1 files changed, 54 insertions, 0 deletions
diff --git a/tests/gc/bintrees.nim b/tests/gc/bintrees.nim new file mode 100644 index 000000000..3f8acee1e --- /dev/null +++ b/tests/gc/bintrees.nim @@ -0,0 +1,54 @@ +# -*- nimrod -*- + +import os, strutils + +type + PNode = ref TNode + TNode {.final, acyclic.} = object + left, right: PNode + item: int + +proc checkTree(node: PNode): int = + result = node.item + if node.left != nil: + inc result, checkTree(node.left) - checkTree(node.right) + +proc makeTreeAux(item, depth: int): PNode = + new(result) + result.item = item + if depth > 0: + result.left = makeTreeAux(2 * item - 1, depth - 1) + result.right = makeTreeAux(2 * item, depth - 1) + +proc makeTree(item, depth: int): PNode = + #GC_disable() + result = makeTreeAux(item, depth) + #GC_enable() + +proc main = + var n = parseInt(paramStr(1)) + const minDepth = 4 + var maxDepth = if minDepth+2 > n: minDepth+2 else: n + + var stretchDepth = maxDepth + 1 + + echo("stretch tree of depth ", stretchDepth, "\t check: ", checkTree( + makeTree(0, stretchDepth))) + + var longLivedTree = makeTree(0, maxDepth) + + var iterations = 1 shl maxDepth + for depth in countup (minDepth, stretchDepth-1, 2): + var check = 0 + for i in 1..iterations: + check += checkTree(makeTree(i, depth)) + checkTree(makeTree(-i, depth)) + + echo(iterations*2, "\t trees of depth ", depth, "\t check: ", check) + iterations = iterations div 4 + + echo("long lived tree of depth ", maxDepth, "\t check: ", + longLivedTree.checkTree) + echo GC_getstatistics() + +main() + |