1234949Sbapt/* $Id: warshall.c,v 1.7 2010/06/06 22:48:51 tom Exp $ */
2234949Sbapt
3234949Sbapt#include "defs.h"
4234949Sbapt
5234949Sbaptstatic void
6234949Sbapttransitive_closure(unsigned *R, int n)
7234949Sbapt{
8234949Sbapt    int rowsize;
9234949Sbapt    unsigned i;
10234949Sbapt    unsigned *rowj;
11234949Sbapt    unsigned *rp;
12234949Sbapt    unsigned *rend;
13234949Sbapt    unsigned *ccol;
14234949Sbapt    unsigned *relend;
15234949Sbapt    unsigned *cword;
16234949Sbapt    unsigned *rowi;
17234949Sbapt
18234949Sbapt    rowsize = WORDSIZE(n);
19234949Sbapt    relend = R + n * rowsize;
20234949Sbapt
21234949Sbapt    cword = R;
22234949Sbapt    i = 0;
23234949Sbapt    rowi = R;
24234949Sbapt    while (rowi < relend)
25234949Sbapt    {
26234949Sbapt	ccol = cword;
27234949Sbapt	rowj = R;
28234949Sbapt
29234949Sbapt	while (rowj < relend)
30234949Sbapt	{
31234949Sbapt	    if (*ccol & (unsigned)(1 << i))
32234949Sbapt	    {
33234949Sbapt		rp = rowi;
34234949Sbapt		rend = rowj + rowsize;
35234949Sbapt		while (rowj < rend)
36234949Sbapt		    *rowj++ |= *rp++;
37234949Sbapt	    }
38234949Sbapt	    else
39234949Sbapt	    {
40234949Sbapt		rowj += rowsize;
41234949Sbapt	    }
42234949Sbapt
43234949Sbapt	    ccol += rowsize;
44234949Sbapt	}
45234949Sbapt
46234949Sbapt	if (++i >= BITS_PER_WORD)
47234949Sbapt	{
48234949Sbapt	    i = 0;
49234949Sbapt	    cword++;
50234949Sbapt	}
51234949Sbapt
52234949Sbapt	rowi += rowsize;
53234949Sbapt    }
54234949Sbapt}
55234949Sbapt
56234949Sbaptvoid
57234949Sbaptreflexive_transitive_closure(unsigned *R, int n)
58234949Sbapt{
59234949Sbapt    int rowsize;
60234949Sbapt    unsigned i;
61234949Sbapt    unsigned *rp;
62234949Sbapt    unsigned *relend;
63234949Sbapt
64234949Sbapt    transitive_closure(R, n);
65234949Sbapt
66234949Sbapt    rowsize = WORDSIZE(n);
67234949Sbapt    relend = R + n * rowsize;
68234949Sbapt
69234949Sbapt    i = 0;
70234949Sbapt    rp = R;
71234949Sbapt    while (rp < relend)
72234949Sbapt    {
73234949Sbapt	*rp |= (unsigned)(1 << i);
74234949Sbapt	if (++i >= BITS_PER_WORD)
75234949Sbapt	{
76234949Sbapt	    i = 0;
77234949Sbapt	    rp++;
78234949Sbapt	}
79234949Sbapt
80234949Sbapt	rp += rowsize;
81234949Sbapt    }
82234949Sbapt}
83