xref: /dragonfly/contrib/byacc/warshall.c (revision f8731e3afcc99aceff0baa3c56b6d51e6ca4cf19) 
1 /* $Id: warshall.c,v 1.9 2020/09/22 20:17:00 tom Exp $ */
2 
3 #include "defs.h"
4 
5 static void
transitive_closure(unsigned * R,int n)6 transitive_closure(unsigned *R, int n)
7 {
8     int rowsize;
9     unsigned i;
10     unsigned *rowj;
11     unsigned *rp;
12     unsigned *rend;
13     unsigned *relend;
14     unsigned *cword;
15     unsigned *rowi;
16 
17     rowsize = WORDSIZE(n);
18     relend = R + n * rowsize;
19 
20     cword = R;
21     i = 0;
22     rowi = R;
23     while (rowi < relend)
24     {
25           unsigned *ccol = cword;
26 
27           rowj = R;
28 
29           while (rowj < relend)
30           {
31               if (*ccol & (1U << 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 
56 void
reflexive_transitive_closure(unsigned * R,int n)57 reflexive_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 |= (1U << i);
74           if (++i >= BITS_PER_WORD)
75           {
76               i = 0;
77               rp++;
78           }
79 
80           rp += rowsize;
81     }
82 }
83