1 /**************************************************************************/
2 /*                                                                        */
3 /*                                 OCaml                                  */
4 /*                                                                        */
5 /*             Xavier Leroy, projet Cristal, INRIA Rocquencourt           */
6 /*                                                                        */
7 /*   Copyright 1996 Institut National de Recherche en Informatique et     */
8 /*     en Automatique.                                                    */
9 /*                                                                        */
10 /*   All rights reserved.  This file is distributed under the terms of    */
11 /*   the GNU Lesser General Public License version 2.1, with the          */
12 /*   special exception on linking described in the file LICENSE.          */
13 /*                                                                        */
14 /**************************************************************************/
15 
16 /* Based on public-domain code from Berkeley Yacc */
17 
18 #include "defs.h"
19 
transitive_closure(unsigned int * R,int n)20 void transitive_closure(unsigned int *R, int n)
21 {
22     register int rowsize;
23     register unsigned mask;
24     register unsigned *rowj;
25     register unsigned *rp;
26     register unsigned *rend;
27     register unsigned *ccol;
28     register unsigned *relend;
29     register unsigned *cword;
30     register unsigned *rowi;
31 
32     rowsize = WORDSIZE(n);
33     relend = R + n*rowsize;
34 
35     cword = R;
36     mask = 1;
37     rowi = R;
38     while (rowi < relend)
39     {
40         ccol = cword;
41         rowj = R;
42 
43         while (rowj < relend)
44         {
45             if (*ccol & mask)
46             {
47                 rp = rowi;
48                 rend = rowj + rowsize;
49                 while (rowj < rend)
50                     *rowj++ |= *rp++;
51             }
52             else
53             {
54                 rowj += rowsize;
55             }
56 
57             ccol += rowsize;
58         }
59 
60         mask <<= 1;
61         if (mask == 0)
62         {
63             mask = 1;
64             cword++;
65         }
66 
67         rowi += rowsize;
68     }
69 }
70 
reflexive_transitive_closure(unsigned int * R,int n)71 void reflexive_transitive_closure(unsigned int *R, int n)
72 {
73     register int rowsize;
74     register unsigned mask;
75     register unsigned *rp;
76     register unsigned *relend;
77 
78     transitive_closure(R, n);
79 
80     rowsize = WORDSIZE(n);
81     relend = R + n*rowsize;
82 
83     mask = 1;
84     rp = R;
85     while (rp < relend)
86     {
87         *rp |= mask;
88         mask <<= 1;
89         if (mask == 0)
90         {
91             mask = 1;
92             rp++;
93         }
94 
95         rp += rowsize;
96     }
97 }
98