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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
#!./parrot -R cgp
# Copyright (C) 2005-2009, Parrot Foundation.
# $Id$
#
# binarytrees.pir N (N = 16 for shootout)
# by Joshua Isom, modified by Leopold Toetsch
# modified by karl : default value of N=10 to match shootout output
.sub itemcheck
.param pmc node
$I0 = exists node[0]
unless $I0 goto final
.local pmc tmp
tmp = node[0]
unless_null tmp, else
$I0 = node[2]
.return($I0)
else:
# tmp = node[0]
$I0 = itemcheck(tmp)
tmp = node[1]
$I1 = itemcheck(tmp)
$I0 -= $I1
$I1 = node[2]
$I0 += $I1
final:
.return($I0)
.end
.sub bottomuptree
.param int item
.param int dep
.local pmc left, right, tree
.local int item2
unless dep > 0 goto else
item2 = item * 2
$I0 = item2 - 1
dec dep
left = bottomuptree($I0, dep)
right = bottomuptree(item2, dep)
goto endif
else:
null left
null right
endif:
tree = new 'FixedPMCArray'
tree = 3
tree[0] = left
tree[1] = right
tree[2] = item
.return(tree)
.end
.sub main :main
.param pmc argv
.local int argc
.local int N, dep, mindepth, maxdepth, stretchdepth
.local pmc stretchtree, longlivedtree, tmptree
argc = elements argv
N = 10
if argc == 1 goto default
$S0 = argv[1]
N = $S0
default:
mindepth = 4
unless N < 6 goto else
maxdepth = mindepth + 2
goto endif
else:
maxdepth = N
endif:
stretchdepth = maxdepth + 1
$I0 = 0
stretchtree = bottomuptree($I0, stretchdepth)
$I0 = itemcheck(stretchtree)
print "stretch tree of depth "
print stretchdepth
print "\t check: "
print $I0
print "\n"
null stretchtree
$I0 = 0
longlivedtree = bottomuptree($I0, maxdepth)
dep = mindepth
beginfor_1:
.local int i, iterations, check
$N0 = maxdepth - dep
$N0 += mindepth
$N1 = 2
$N2 = pow $N1, $N0
iterations = $N2
check = 0
i = 1
beginfor_2:
noop
tmptree = bottomuptree(i, dep)
$I0 = itemcheck(tmptree)
check += $I0
$I0 = 0 - i
tmptree = bottomuptree($I0, dep)
$I0 = itemcheck(tmptree)
check += $I0
inc i
if i <= iterations goto beginfor_2
$I0 = iterations * 2
print $I0
print "\t trees of depth "
print dep
print "\t check: "
print check
print "\n"
dep += 2
if dep <= maxdepth goto beginfor_1
$I0 = itemcheck(longlivedtree)
print "long lived tree of depth "
print maxdepth
print "\t check: "
print $I0
print "\n"
.end
# Local Variables:
# mode: pir
# fill-column: 100
# End:
# vim: expandtab shiftwidth=4 ft=pir:
|
