1/*	$NetBSD: warshall.c,v 1.11 2021/02/20 22:57:56 christos Exp $	*/
2
3/* Id: warshall.c,v 1.9 2020/09/22 20:17:00 tom Exp  */
4
5#include "defs.h"
6
7#include <sys/cdefs.h>
8__RCSID("$NetBSD: warshall.c,v 1.11 2021/02/20 22:57:56 christos Exp $");
9
10static void
11transitive_closure(unsigned *R, int n)
12{
13    int rowsize;
14    unsigned i;
15    unsigned *rowj;
16    unsigned *rp;
17    unsigned *rend;
18    unsigned *relend;
19    unsigned *cword;
20    unsigned *rowi;
21
22    rowsize = WORDSIZE(n);
23    relend = R + n * rowsize;
24
25    cword = R;
26    i = 0;
27    rowi = R;
28    while (rowi < relend)
29    {
30	unsigned *ccol = cword;
31
32	rowj = R;
33
34	while (rowj < relend)
35	{
36	    if (*ccol & (1U << i))
37	    {
38		rp = rowi;
39		rend = rowj + rowsize;
40		while (rowj < rend)
41		    *rowj++ |= *rp++;
42	    }
43	    else
44	    {
45		rowj += rowsize;
46	    }
47
48	    ccol += rowsize;
49	}
50
51	if (++i >= BITS_PER_WORD)
52	{
53	    i = 0;
54	    cword++;
55	}
56
57	rowi += rowsize;
58    }
59}
60
61void
62reflexive_transitive_closure(unsigned *R, int n)
63{
64    int rowsize;
65    unsigned i;
66    unsigned *rp;
67    unsigned *relend;
68
69    transitive_closure(R, n);
70
71    rowsize = WORDSIZE(n);
72    relend = R + n * rowsize;
73
74    i = 0;
75    rp = R;
76    while (rp < relend)
77    {
78	*rp |= (1U << i);
79	if (++i >= BITS_PER_WORD)
80	{
81	    i = 0;
82	    rp++;
83	}
84
85	rp += rowsize;
86    }
87}
88