diff options
| -rw-r--r-- | .clang-format | 92 | ||||
| -rw-r--r-- | COPYRIGHT | 20 | ||||
| -rw-r--r-- | README.org | 26 | ||||
| -rwxr-xr-x | build.sh | 2 | ||||
| -rwxr-xr-x | graph.sh | 6 | ||||
| -rw-r--r-- | test | 15 | ||||
| -rw-r--r-- | topo.c | 249 |
7 files changed, 410 insertions, 0 deletions
diff --git a/.clang-format b/.clang-format new file mode 100644 index 0000000..99ffd27 --- /dev/null +++ b/.clang-format @@ -0,0 +1,92 @@ +--- +BasedOnStyle: Mozilla +AccessModifierOffset: '0' + +AlignAfterOpenBracket: Align +AlignArrayOfStructures: Left +AlignConsecutiveBitFields: AcrossEmptyLines +AlignConsecutiveMacros: true +AlignConsecutiveAssignments: true +AlignConsecutiveDeclarations: true +AlignEscapedNewlines: Left +AlignOperands: true +AlignTrailingComments: true + +AllowAllArgumentsOnNextLine: false +AllowAllConstructorInitializersOnNextLine: false +AllowAllParametersOfDeclarationOnNextLine: false + +AllowShortBlocksOnASingleLine: Always +AllowShortCaseLabelsOnASingleLine: true +AllowShortEnumsOnASingleLine: true +AllowShortFunctionsOnASingleLine: All +AllowShortIfStatementsOnASingleLine: Always +AllowShortLambdasOnASingleLine: All +AllowShortLoopsOnASingleLine: true + +AlwaysBreakAfterDefinitionReturnType: All +AlwaysBreakAfterReturnType: AllDefinitions +AlwaysBreakTemplateDeclarations: Yes + +BinPackArguments: false +BinPackParameters: false + +BitFieldColonSpacing: Both + +BraceWrapping: + AfterCaseLabel: true + AfterClass: true + AfterControlStatement: true + AfterEnum: true + AfterExternBlock: true + AfterFunction: true + AfterNamespace: true + AfterStruct: true + AfterUnion: true + BeforeCatch: false + BeforeElse: false + BeforeLambdaBody: true + BeforeWhile: false + IndentBraces: false + SplitEmptyFunction: false + SplitEmptyNamespace: false + +BreakBeforeBinaryOperators: None +BreakBeforeBraces: Custom +BreakBeforeTernaryOperators: true +BreakStringLiterals: false + +ColumnLimit: 112 +CompactNamespaces: false +IncludeBlocks: Preserve +IndentPPDirectives: AfterHash +IndentWidth: 4 +KeepEmptyLinesAtTheStartOfBlocks: false +Language: Cpp +MaxEmptyLinesToKeep: 1 +NamespaceIndentation: All +PointerAlignment: Right +QualifierAlignment: Right +ReflowComments: false + +SortIncludes: Never +SortUsingDeclarations: true + +SpaceAfterCStyleCast: false +SpaceAfterLogicalNot: false +SpaceAfterTemplateKeyword: false +SpaceBeforeAssignmentOperators: true +SpaceBeforeCtorInitializerColon: true +SpaceBeforeInheritanceColon: true +SpaceBeforeParens: Never +SpaceBeforeRangeBasedForLoopColon: true +SpaceInEmptyParentheses: false +SpacesInAngles: false +SpacesInCStyleCastParentheses: false +SpacesInContainerLiterals: false +SpacesInParentheses: false +SpacesInSquareBrackets: false + +TabWidth: 4 +UseTab: ForIndentation +... diff --git a/COPYRIGHT b/COPYRIGHT new file mode 100644 index 0000000..f9a31ff --- /dev/null +++ b/COPYRIGHT @@ -0,0 +1,20 @@ +Copyright (c) 2025 Karlo Milicevic + +Redistribution and use in source and binary forms, with or without modification, +are permitted provided that the following conditions are met: +1. Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. +2. Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + +THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS +OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT +SHALL AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR +BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING +IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY +OF SUCH DAMAGE. diff --git a/README.org b/README.org new file mode 100644 index 0000000..af2c917 --- /dev/null +++ b/README.org @@ -0,0 +1,26 @@ +* topo +A tiny unix-like utility for resolving arbitrary graph dependencies. +It takes no arguments and has no flags. +It also provides a tiny shell script that visualizes graphs. + +* Interaction +| STDIN | input graph | +| STDOUT | result | +| STDERR | errors | + +** Input +*** Form 1 +These are lines that look like two names separated by a space. +Let's say these two names were =a= and =b=. +This means =a= is being blocked (or depending on) =b=. +=b= would first have to be resolved for =a= to be able to run. + +*** Form 2 +These are lines that look like a single name with no space. +Let's say the line was =a=. +This means =a= is complete, allowing other nodes which depend on it to be run if they have no other dependencies unresolved. + +*** Form 3 +These are empty lines. +After receiving this query it outputs on the STDOUT nodes which can be resolved. +Output is a single line containing names of nodes followed by a space. diff --git a/build.sh b/build.sh new file mode 100755 index 0000000..88c2e8c --- /dev/null +++ b/build.sh @@ -0,0 +1,2 @@ +#!/bin/sh +clang -std=c23 -O3 -Wall -Wextra topo.c -o topo diff --git a/graph.sh b/graph.sh new file mode 100755 index 0000000..da8f49c --- /dev/null +++ b/graph.sh @@ -0,0 +1,6 @@ +#!/bin/sh +( + echo "digraph {" + grep ' ' | sed 's/\(.*\) \(.*\)/\t\2->\1;/' + echo "}" +) | dot -Tpng | feh - @@ -0,0 +1,15 @@ +a b +a c +a d +b p +c p +d p +c d +s x +d f +f p +f s +p + +d + @@ -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; +} |