From 03860d2a744368b3514087943f2694485e56224d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Karlo=20Mili=C4=8Devi=C4=87?= Date: Thu, 29 May 2025 20:12:47 +0200 Subject: Initial commit --- topo.c | 249 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 249 insertions(+) create mode 100644 topo.c (limited to 'topo.c') 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 + +#include +#include +#include + +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; +} -- cgit v1.2.3