From 9a88f7da453eadc72d8f333700dbd80777feecd1 Mon Sep 17 00:00:00 2001
From: David Oberhollenzer <david.oberhollenzer@tele2.at>
Date: Sun, 25 Feb 2018 14:33:19 +0100
Subject: Initial commit

Signed-off-by: David Oberhollenzer <david.oberhollenzer@tele2.at>
---
 lib/src/srv_tsort.c | 75 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 75 insertions(+)
 create mode 100644 lib/src/srv_tsort.c

(limited to 'lib/src/srv_tsort.c')

diff --git a/lib/src/srv_tsort.c b/lib/src/srv_tsort.c
new file mode 100644
index 0000000..e2549b1
--- /dev/null
+++ b/lib/src/srv_tsort.c
@@ -0,0 +1,75 @@
+#include <stdbool.h>
+#include <stddef.h>
+#include <string.h>
+#include <errno.h>
+
+#include "service.h"
+
+static bool has_dependencies(service_t *list, service_t *svc)
+{
+	size_t i;
+
+	while (list != NULL) {
+		for (i = 0; i < svc->num_after; ++i) {
+			if (!strcmp(svc->after[i], list->name))
+				return true;
+		}
+
+		for (i = 0; i < list->num_before; ++i) {
+			if (!strcmp(list->before[i], svc->name))
+				return true;
+		}
+
+		list = list->next;
+	}
+
+	return false;
+}
+
+service_t *srv_tsort(service_t *list)
+{
+	service_t *nl = NULL, *end = NULL;
+	service_t *svc, *prev;
+
+	while (list != NULL) {
+		/* remove first service without dependencies */
+		prev = NULL;
+		svc = list;
+
+		while (svc != NULL) {
+			if (has_dependencies(list, svc)) {
+				prev = svc;
+				svc = svc->next;
+			} else {
+				if (prev != NULL) {
+					prev->next = svc->next;
+				} else {
+					list = svc->next;
+				}
+				svc->next = NULL;
+				break;
+			}
+		}
+
+		/* cycle! */
+		if (svc == NULL) {
+			if (end == NULL) {
+				nl = list;
+			} else {
+				end->next = list;
+			}
+			errno = ELOOP;
+			break;
+		}
+
+		/* append to new list */
+		if (end == NULL) {
+			nl = end = svc;
+		} else {
+			end->next = svc;
+			end = svc;
+		}
+	}
+
+	return nl;
+}
-- 
cgit v1.2.3