aboutsummaryrefslogtreecommitdiff
path: root/lib/src/svc_tsort.c
diff options
context:
space:
mode:
authorDavid Oberhollenzer <david.oberhollenzer@tele2.at>2018-03-25 12:14:06 +0200
committerDavid Oberhollenzer <david.oberhollenzer@tele2.at>2018-03-25 12:14:06 +0200
commita71c92b33dc69bc6cbc5eae161f82a5bca27a82f (patch)
tree917eaeb4b2460345e122a00cbc32c7398f438d39 /lib/src/svc_tsort.c
parenta108beaaf7b19198acbcc5435708d4ff0c8fb5df (diff)
Unify naming of service to shorthand svc
Signed-off-by: David Oberhollenzer <david.oberhollenzer@tele2.at>
Diffstat (limited to 'lib/src/svc_tsort.c')
-rw-r--r--lib/src/svc_tsort.c92
1 files changed, 92 insertions, 0 deletions
diff --git a/lib/src/svc_tsort.c b/lib/src/svc_tsort.c
new file mode 100644
index 0000000..50517f2
--- /dev/null
+++ b/lib/src/svc_tsort.c
@@ -0,0 +1,92 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * Copyright (C) 2018 - David Oberhollenzer
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <https://www.gnu.org/licenses/>.
+ */
+#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 *svc_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;
+}