Initial commitHEADmaster

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 -
diff --git a/test b/test
new file mode 100644
index 0000000..a1850cc
--- /dev/null
+++ b/test
@@ -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
+
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;
+}