Nim/tests/gc/bintrees.nim at devel · googol-lab/Nim

Repository navigation

# -*- nim -*-

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()