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