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