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