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
|
/*% clang -Wall -o # %
*/
#include "lisc.h"
static void
rporec(int *rpo, int *cnt, Blk *bs, int b)
{
if (rpo[b] >= 0)
return;
if (bs[b].suc1 >= 0)
rporec(rpo, cnt, bs, bs[b].suc1);
if (bs[b].suc0 >= 0)
rporec(rpo, cnt, bs, bs[b].suc0);
rpo[b] = --*cnt;
}
int
dorpo(Blk *bs, int nb)
{
static int rpo[MaxBlks];
Blk t;
int cnt, i, j;
for (i=0; i<nb; i++)
rpo[i] = -1;
cnt = nb;
rporec(rpo, &cnt, bs, 0);
if (cnt) {
for (i=0; i<nb; i++)
rpo[i] -= cnt;
}
for (i=0; i<nb; i++) {
if (bs[i].suc0 >= 0)
bs[i].suc0 = rpo[bs[i].suc0];
if (bs[i].suc1 >= 0)
bs[i].suc1 = rpo[bs[i].suc1];
}
/*
A little messy, the idea is that we have an
array permutation inside the rpo array, now we
apply it to the bs array with a linear algorithm
using swaps.
*/
for (i=0; i<nb; i++)
while (rpo[i] >= 0 && rpo[i] != i) {
j = rpo[i];
rpo[i] = rpo[j];
rpo[j] = j;
t = bs[i];
bs[i] = bs[j];
bs[j] = t;
}
return nb - cnt;
}
#define LEN(a) sizeof a / sizeof a[0]
Blk rpocond[] = {
{ .suc0 = 2, .suc1 = 3 },
{ .suc0 = -1, .suc1 = -1 },
{ .suc0 = 1, .suc1 = -1 },
{ .suc0 = -1, .suc1 = 1 },
{ .suc0 = 12, .suc1 = -1 }, /* dead */
};
int
main()
{
Blk *bs;
int i, nb;
bs = rpocond;
nb = LEN(rpocond);
nb = dorpo(bs, nb);
for (i=0; i<nb; i++) {
printf("%02d -> [%02d, %02d]\n", i,
bs[i].suc0, bs[i].suc1);
}
return 0;
}
|
