Initial commitHEADmaster

1 files changed, 249 insertions, 0 deletions

diff --git a/topo.c b/topo.c
new file mode 100644
index 0000000..0cc37aa
--- /dev/null
+++ b/topo.c
@@ -0,0 +1,249 @@
+#define _DEFAULT_SOURCE
+#define _POSIX_C_SOURCE 200809L
+
+#include <sys/queue.h>
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+struct node
+{
+	LIST_ENTRY(node) List;
+	char         *Name;
+	size_t        FromCount;
+	size_t        ToCount;
+	struct node **From;
+	struct node **To;
+};
+
+enum state
+{
+	state_not_ready,
+	state_ready,
+	state_done,
+};
+
+LIST_HEAD(node_list, node);
+
+static struct node_list Nodes;
+static struct node_list NodesReady;
+static struct node_list NodesDone;
+
+static bool
+Depends(struct node *A, struct node *B)
+{
+	for(size_t i = 0; i < A->FromCount; ++i)
+		if(B == A->From[i]) return true;
+	return false;
+}
+
+static struct node *
+New(char *Name)
+{
+	struct node *N = calloc(1, sizeof(struct node));
+	N->Name        = Name;
+	LIST_INSERT_HEAD(&NodesReady, N, List);
+	return N;
+}
+
+static void
+Free(struct node *Node)
+{
+	free(Node->Name);
+	if(Node->From != NULL) free(Node->From);
+	if(Node->To != NULL) free(Node->To);
+	LIST_REMOVE(Node, List);
+	free(Node);
+}
+
+static struct node *
+Find(struct node_list *L, char *A)
+{
+	for(struct node *I = L->lh_first; I != NULL; I = I->List.le_next)
+	{
+		if(strcmp(I->Name, A) == 0)
+		{
+			free(A);
+			return I;
+		}
+	}
+	return NULL;
+}
+
+static struct node *
+FindWithState(char *Name, enum state *State)
+{
+	struct node *Node;
+	*State = state_done;
+	Node   = Find(&NodesDone, Name);
+	if(Node != NULL) return Node;
+	*State = state_ready;
+	Node   = Find(&NodesReady, Name);
+	if(Node != NULL) return Node;
+	*State = state_not_ready;
+	Node   = Find(&Nodes, Name);
+	if(Node != NULL) return Node;
+	*State = state_ready;
+	return New(Name);
+}
+
+static void
+DependencyRemove(struct node *A, struct node *B)
+{
+	size_t i;
+	for(i = 0; i < B->ToCount; ++i)
+		if(B->To[i] == A) break;
+	memmove(B->To + i, B->To + i + 1, (B->ToCount - i - 1) * sizeof(struct node *));
+	if(--B->ToCount == 0)
+	{
+		free(B->To);
+		B->To = NULL;
+	}
+	for(i = 0; i < A->FromCount; ++i)
+		if(A->From[i] == B) break;
+	memmove(A->From + i, A->From + i + 1, (A->FromCount - i - 1) * sizeof(struct node *));
+	if(--A->FromCount == 0)
+	{
+		free(A->From);
+		A->From = NULL;
+		LIST_REMOVE(A, List);
+		LIST_INSERT_HEAD(&NodesReady, A, List);
+	}
+}
+
+static void
+Complete(char *Name)
+{
+	enum state   State;
+	struct node *Node = FindWithState(Name, &State);
+	switch(State)
+	{
+		case state_not_ready:
+		case state_ready:
+		{
+			// TODO: Cleanup from the end should be faster because we would have half as many memmoves
+			while(Node->FromCount > 0) DependencyRemove(Node, Node->From[0]);
+			while(Node->ToCount > 0) DependencyRemove(Node->To[0], Node);
+			LIST_REMOVE(Node, List);
+			LIST_INSERT_HEAD(&NodesDone, Node, List);
+			break;
+		}
+		case state_done: break;
+	}
+}
+
+static void
+DependencyAdd(char *NameA, char *NameB)
+{
+	enum state   StateA;
+	enum state   StateB;
+	struct node *A = FindWithState(NameA, &StateA);
+	struct node *B = FindWithState(NameB, &StateB);
+	switch(StateB)
+	{
+		case state_not_ready:
+		case state_ready:
+		{
+			switch(StateA)
+			{
+				case state_ready:
+				{
+					LIST_REMOVE(A, List);
+					LIST_INSERT_HEAD(&Nodes, A, List);
+					goto common;
+				}
+				case state_not_ready:
+				{
+					if(Depends(A, B)) return;
+					goto common;
+				}
+				common:
+				{
+					A->From = (struct node **)reallocarray(A->From, A->FromCount + 1, sizeof(struct node *));
+					A->From[A->FromCount++] = B;
+					B->To = (struct node **)reallocarray(B->To, B->ToCount + 1, sizeof(struct node *));
+					B->To[B->ToCount++] = A;
+					break;
+				}
+				case state_done: break;
+			}
+			break;
+		}
+		case state_done: break;
+	}
+}
+
+int
+main(void)
+{
+	LIST_INIT(&Nodes);
+	LIST_INIT(&NodesReady);
+	LIST_INIT(&NodesDone);
+	char  *Line = NULL;
+	size_t Size = 0;
+	while(true)
+	{
+		ssize_t Count = getline(&Line, &Size, stdin);
+		if(Count <= 0) break;
+		if(Count > 0 && Line[Count - 1] == '\n') --Count;
+		if(Count == 0)
+		{
+			for(struct node *At = NodesReady.lh_first; At != NULL; At = At->List.le_next)
+				printf("%s ", At->Name);
+			printf("\n");
+			continue;
+		}
+		ssize_t Space   = -1;
+		bool    Invalid = false;
+		for(ssize_t i = 0; i < Count; ++i)
+		{
+			if(Line[i] == ' ')
+			{
+				if(Space != -1)
+				{
+					Invalid = true;
+					break;
+				}
+				Space = i;
+			}
+		}
+		if(Invalid)
+		{
+			fprintf(stderr, "failed to parse '%.*s'\n", (int)Count, Line);
+			continue;
+		}
+		if(Space == -1)
+		{
+			Complete(strndup(Line, (size_t)Count));
+		} else
+		{
+			char *A = strndup(Line, (size_t)Space);
+			char *B = strndup(Line + Space + 1, (size_t)(Count - (Space + 1)));
+			DependencyAdd(A, B);
+		}
+	}
+	if(Line != NULL)
+	{
+		free(Line);
+		Line = NULL;
+		Size = 0;
+	}
+	struct node *Next;
+	for(struct node *At = Nodes.lh_first; At != NULL; At = Next)
+	{
+		Next = At->List.le_next;
+		Free(At);
+	}
+	for(struct node *At = NodesReady.lh_first; At != NULL; At = Next)
+	{
+		Next = At->List.le_next;
+		Free(At);
+	}
+	for(struct node *At = NodesDone.lh_first; At != NULL; At = Next)
+	{
+		Next = At->List.le_next;
+		Free(At);
+	}
+	return 0;
+}