1 files changed, 55 insertions, 0 deletions
diff --git a/src/serverlib/s6rc_db_check_depcycles.c b/src/serverlib/s6rc_db_check_depcycles.c
new file mode 100644
index 0000000..5f8339e
--- /dev/null
+++ b/src/serverlib/s6rc_db_check_depcycles.c
@@ -0,0 +1,55 @@
+/* ISC license. */
+
+#include <string.h>
+#include <stdint.h>
+#include <skalibs/bitarray.h>
+#include <s6-rc/s6rc-db.h>
+
+typedef struct recinfo_s recinfo_t, *recinfo_t_ref ;
+struct recinfo_s
+{
+  s6rc_db_t const *db ;
+  uint32_t n ;
+  unsigned char *gray ;
+  unsigned char *black ;
+  unsigned char h : 1 ;
+} ;
+
+static uint32_t s6rc_db_checknocycle_rec (recinfo_t *recinfo, uint32_t i)
+{
+  if (!bitarray_peek(recinfo->black, i))
+  {
+    uint32_t j = recinfo->db->services[i].ndeps[recinfo->h] ;
+    if (bitarray_peek(recinfo->gray, i)) return i ;
+    bitarray_set(recinfo->gray, i) ;
+    while (j--)
+    {
+      uint32_t r = s6rc_db_checknocycle_rec(recinfo, recinfo->db->deps[recinfo->h * recinfo->db->ndeps + recinfo->db->services[i].deps[recinfo->h] + j]) ;
+      if (r < recinfo->n) return r ;
+    }
+    bitarray_set(recinfo->black, i) ;
+  }
+  return recinfo->n ;
+}
+
+int s6rc_db_check_depcycles (s6rc_db_t const *db, int h, diuint32 *problem)
+{
+  uint32_t n = db->nshort + db->nlong ;
+  uint32_t i = n ;
+  unsigned char gray[bitarray_div8(n)] ;
+  unsigned char black[bitarray_div8(n)] ;
+  recinfo_t info = { .db = db, .n = n, .gray = gray, .black = black, .h = !!h } ;
+  memset(gray, 0, bitarray_div8(n)) ;
+  memset(black, 0, bitarray_div8(n)) ;
+  while (i--)
+  {
+    uint32_t r = s6rc_db_checknocycle_rec(&info, i) ;
+    if (r < n)
+    {
+      problem->left = i ;
+      problem->right = r ;
+      return 1 ;
+    }
+  }
+  return 0 ;
+}