blob: 4f304deb19d22ae3f98fdde90f837d6615e636d7 (
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
|
namespace;
include rt;
// a binary search tree where every node owns its children. there's no free
// anywhere: when the root's block ends, the whole tree goes with it.
struct node { int v; node* left, right; };
node*.u leaf(int v) { node* n = rt.new(node); n.v = v; return n; }
// n is borrowed; storing a new leaf into it makes n the leaf's owner
void insert(node*.m n, int v) {
if (v < n.v) { if (n.left) insert(n.left, v); else n.left = leaf(v); }
else { if (n.right) insert(n.right, v); else n.right = leaf(v); }
return;
}
void walk(node* n) { if (!n) return; walk(n.left); rt.put_n(n.v); rt.put_c(' '); walk(n.right); return; }
int height(node* n) { if (!n) return 0; int l = height(n.left), r = height(n.right); return 1 + (l > r ? l : r); }
void main() {
let before = rt.live_objects();
{
node* root = leaf(50);
int x = 7;
for (int i = 0; i < 30; i++) { x = (x * 37 + 11) % 100; insert(root, x); }
walk(root); rt.put_c(10);
rt.put_s("height "); rt.put_n(height(root)); rt.put_s(", live objects "); rt.put_n(rt.live_objects() - before); rt.put_c(10);
}
rt.put_s("after the block: "); rt.put_n(rt.live_objects() - before); rt.put_c(10);
return;
}
|
