From ba3bcbb86ea0177349bcd021559347248d6ab10a Mon Sep 17 00:00:00 2001 From: Laurent Bercot Date: Mon, 30 Nov 2020 13:08:04 +0000 Subject: Stash temporary changes. Does not build; is not intended to. --- src/serverlib/s6rc_db_check_depcycles.c | 55 +++++++++++++++++++++++++++++++++ 1 file changed, 55 insertions(+) create mode 100644 src/serverlib/s6rc_db_check_depcycles.c (limited to 'src/serverlib/s6rc_db_check_depcycles.c') 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 +#include +#include +#include + +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 ; +} -- cgit v1.3.1