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