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