From 4b31caa9cdaef67c70bc7fb43963ba68b7bf5bb1 Mon Sep 17 00:00:00 2001
From: Laurent Bercot <ska-skaware@skarnet.org>
Date: Thu, 4 Jun 2015 20:48:10 +0000
Subject:  Initial commit

---
 src/libs6rc/s6rc_graph_closure.c | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)
 create mode 100644 src/libs6rc/s6rc_graph_closure.c

(limited to 'src/libs6rc/s6rc_graph_closure.c')

diff --git a/src/libs6rc/s6rc_graph_closure.c b/src/libs6rc/s6rc_graph_closure.c
new file mode 100644
index 0000000..0ec2def
--- /dev/null
+++ b/src/libs6rc/s6rc_graph_closure.c
@@ -0,0 +1,39 @@
+/* ISC license. */
+
+#include <skalibs/bitarray.h>
+#include <s6-rc/s6rc-db.h>
+#include <s6-rc/s6rc-utils.h>
+
+typedef struct recinfo_s recinfo_t, *recinfo_t_ref ;
+struct recinfo_s
+{
+  s6rc_db_t const *db ;
+  unsigned int n ;
+  unsigned char *bits ;
+  unsigned char *mark ;
+  unsigned char mask ;
+  unsigned char h : 1 ;
+} ;
+
+static void s6rc_graph_closure_rec (recinfo_t *recinfo, unsigned int i)
+{
+  if (!bitarray_peek(recinfo->mark, i))
+  {
+    unsigned int j = recinfo->db->services[i].ndeps[recinfo->h] ;
+    bitarray_set(recinfo->mark, i) ;
+    while (j--) s6rc_graph_closure_rec(recinfo, recinfo->db->deps[recinfo->h * recinfo->db->ndeps + recinfo->db->services[i].deps[recinfo->h] + j]) ;
+    recinfo->bits[i] |= recinfo->mask ;
+  }
+}
+
+void s6rc_graph_closure (s6rc_db_t const *db, unsigned char *bits, unsigned int bitno, int h)
+{
+  unsigned int n = db->nshort + db->nlong ;
+  unsigned int m = bitarray_div8(n) ;
+  unsigned char mark[m] ;
+  recinfo_t info = { .db = db, .n = n, .bits = bits, .mark = mark, .mask = 1 << (bitno & 7), .h = !!h } ;
+  register unsigned int i = n ;
+  byte_zero(mark, m) ;
+  while (i--)
+    if (bits[i] & info.mask) s6rc_graph_closure_rec(&info, i) ;
+}
-- 
cgit v1.2.3