From 4b31caa9cdaef67c70bc7fb43963ba68b7bf5bb1 Mon Sep 17 00:00:00 2001 From: Laurent Bercot Date: Thu, 4 Jun 2015 20:48:10 +0000 Subject: Initial commit --- src/libs6rc/s6rc_db_check_depcycles.c | 50 +++++++++++++++++++++++++++++++++++ 1 file changed, 50 insertions(+) create mode 100644 src/libs6rc/s6rc_db_check_depcycles.c (limited to 'src/libs6rc/s6rc_db_check_depcycles.c') diff --git a/src/libs6rc/s6rc_db_check_depcycles.c b/src/libs6rc/s6rc_db_check_depcycles.c new file mode 100644 index 0000000..13dcf7b --- /dev/null +++ b/src/libs6rc/s6rc_db_check_depcycles.c @@ -0,0 +1,50 @@ +/* ISC license. */ + +#include +#include +#include +#include + +typedef struct recinfo_s recinfo_t, *recinfo_t_ref ; +struct recinfo_s +{ + s6rc_db_t const *db ; + unsigned int n ; + unsigned char *gray ; + unsigned char *black ; + unsigned char h : 1 ; +} ; + +static unsigned int s6rc_db_checknocycle_rec (recinfo_t *recinfo, unsigned int i) +{ + if (!bitarray_peek(recinfo->black, i)) + { + unsigned int j = recinfo->db->services[i].ndeps[recinfo->h] ; + if (bitarray_peek(recinfo->gray, i)) return i ; + bitarray_set(recinfo->gray, i) ; + while (j--) + { + register unsigned int 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 ; +} + +unsigned int s6rc_db_check_depcycles (s6rc_db_t const *db, int h, unsigned int *problem) +{ + unsigned int n = db->nshort + db->nlong ; + 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 } ; + unsigned int i = n ; + byte_zero(gray, bitarray_div8(n)) ; + byte_zero(black, bitarray_div8(n)) ; + while (i--) + { + register unsigned int r = s6rc_db_checknocycle_rec(&info, i) ; + if (r < n) return (*problem = r, i) ; + } + return n ; +} -- cgit v1.3.1