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
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
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