blob: c8f46ef1eb4ef75d71025eb6a314cdc304b24e37 (
plain) (
blame)
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
|
// a full binary tree of depth D. checksum is the node count, 8191.
// each node is two pointers. new() rounds that plus the 5-word header up
// to 8 words (a 4-word block cannot hold the header). free of the owned
// root recycles the tree onto the size-class lists.
// a plain new / own / free
// b the same, marked o3 (calls and new still leave the region)
// c one array, used as an arena of pairs. no allocator in the loop.
// the same shapes are tests/bench/trees.c.
const int D = 12;
const int WORDS = 16382; // two words for each of the 8191 nodes
struct node { node* left, right; };
int* heap;
int used;
node*.u make(int depth) {
node* n = new(node);
if (depth > 0) {
n.left = make(depth - 1);
n.right = make(depth - 1);
} else {
n.left = 0;
n.right = 0;
}
return u*n;
}
o3 node*.u make3(int depth) {
node* n = new(node);
if (depth > 0) {
n.left = make3(depth - 1);
n.right = make3(depth - 1);
} else {
n.left = 0;
n.right = 0;
}
return u*n;
}
int check(node* n) {
if (!n.left) return 1;
return 1 + check(n.left) + check(n.right);
}
o3 int check3(node* n) {
if (!n.left) return 1;
return 1 + check3(n.left) + check3(n.right);
}
// a node id is its word index plus one, so 0 can mean "no child"
o3 int build(int depth) {
int i = used;
used = used + 2;
if (depth > 0) {
heap[i] = build(depth - 1);
heap[i + 1] = build(depth - 1);
} else {
heap[i] = 0;
heap[i + 1] = 0;
}
return i + 1;
}
o3 int ck(int id) {
int i, l;
if (id == 0) return 0;
i = id - 1;
l = heap[i];
if (l == 0) return 1;
return 1 + ck(l) + ck(heap[i + 1]);
}
int main() {
int which = get_c(), reps = 0, ch = get_c(), r = 0;
while (ch >= '0' && ch <= '9') { reps = reps * 10 + ch - '0'; ch = get_c(); }
if (which == 'c') {
heap = new(int, WORDS);
while (reps > 0) { used = 0; r = ck(build(D)); reps--; }
put_n(r); put_c(10);
return 0;
}
while (reps > 0) {
if (which == 'b') {
node* root = make3(D);
r = check3(root);
free(d*root);
} else {
node* root = make(D);
r = check(root);
free(d*root);
}
reps--;
}
put_n(r); put_c(10);
return 0;
}
|
