diff options
author | Quentin Carbonneaux <quentin.carbonneaux@yale.edu> | 2015-06-11 08:49:34 -0400 |
---|---|---|
committer | Quentin Carbonneaux <quentin.carbonneaux@yale.edu> | 2015-09-15 23:01:27 -0400 |
commit | fae1b41e9d6f18b719a99e91a4219896d9c19677 (patch) | |
tree | cedea0ecf4b67213cfdb5477cdd2494057266fe6 /lisc/lo.c | |
parent | fd55a09b7f7454d7232c4645b349b27090ad02c4 (diff) | |
download | roux-fae1b41e9d6f18b719a99e91a4219896d9c19677.tar.gz |
some new C
Diffstat (limited to 'lisc/lo.c')
-rw-r--r-- | lisc/lo.c | 82 |
1 files changed, 82 insertions, 0 deletions
diff --git a/lisc/lo.c b/lisc/lo.c new file mode 100644 index 0000000..931385e --- /dev/null +++ b/lisc/lo.c @@ -0,0 +1,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; +} |