From fae1b41e9d6f18b719a99e91a4219896d9c19677 Mon Sep 17 00:00:00 2001
From: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date: Thu, 11 Jun 2015 08:49:34 -0400
Subject: some new C

---
 lisc/lo.c | 82 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 82 insertions(+)
 create mode 100644 lisc/lo.c

(limited to 'lisc/lo.c')

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;
+}
-- 
cgit 1.4.1