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