From: Adam Joseph <adam@westernsemico.com>
To: supervision@list.skarnet.org
Cc: Adam Joseph <adam@westernsemico.com>
Subject: [PATCH] libs6rc/s6rc_graph_closure.c: add comments explaining behavior
Date: Mon, 25 Sep 2023 17:41:57 -0700 [thread overview]
Message-ID: <20230926004157.23807-1-adam@westernsemico.com> (raw)
While reviewing the algorithm implemented by s6-rc-update I found it
difficult to determine the meaning of some of the arguments to the
functions in libs6rc/s6rc_graph_closure.c. This commit adds
comments to that file documenting those arguments and functions
where their behavior was not immediately obvious to me.
Signed-off-by: Adam Joseph <adam@westernsemico.com>
---
src/libs6rc/s6rc_graph_closure.c | 13 +++++++++++++
1 file changed, 13 insertions(+)
diff --git a/src/libs6rc/s6rc_graph_closure.c b/src/libs6rc/s6rc_graph_closure.c
index 7c3a8f9..50af30b 100644
--- a/src/libs6rc/s6rc_graph_closure.c
+++ b/src/libs6rc/s6rc_graph_closure.c
@@ -11,11 +11,19 @@ struct recinfo_s
s6rc_db_t const *db ;
unsigned int n ;
unsigned char *bits ;
+ /* bitarray in which the i^th bit is set iff the closure routine
+ has already visited the i^th graph node */
unsigned char *mark ;
unsigned char mask ;
unsigned char h : 1 ;
} ;
+/*
+ If the i^th graph node has *any* bit of `recinfo->mask` set then
+ this function will be called on each of the i^th node's
+ dependencies. This function will then set *every* `mask` bit on
+ that node and call itself recursively on that node.
+*/
static void s6rc_graph_closure_rec (recinfo_t *recinfo, unsigned int i)
{
if (!bitarray_peek(recinfo->mark, i))
@@ -27,6 +35,11 @@ static void s6rc_graph_closure_rec (recinfo_t *recinfo, unsigned int i)
}
}
+/*
+ `h` indicates whether you want a forward or reverse search.
+ - If `h==0` then we close over everything that the marked node *depends upon*
+ - If `h==1` then we close over everything that *depends upon* the marked node
+*/
void s6rc_graph_closure (s6rc_db_t const *db, unsigned char *bits, unsigned int bitno, int h)
{
unsigned int n = db->nshort + db->nlong ;
--
2.41.0
reply other threads:[~2023-09-26 0:42 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20230926004157.23807-1-adam@westernsemico.com \
--to=adam@westernsemico.com \
--cc=supervision@list.skarnet.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).