Annotation of src/usr.bin/yacc/warshall.c, Revision 1.5
1.5 ! mpech 1: /* $OpenBSD: warshall.c,v 1.4 2001/07/16 06:29:45 pvalchev Exp $ */
1.2 deraadt 2: /* $NetBSD: warshall.c,v 1.4 1996/03/19 03:21:51 jtc Exp $ */
3:
4: /*
5: * Copyright (c) 1989 The Regents of the University of California.
6: * All rights reserved.
7: *
8: * This code is derived from software contributed to Berkeley by
9: * Robert Paul Corbett.
10: *
11: * Redistribution and use in source and binary forms, with or without
12: * modification, are permitted provided that the following conditions
13: * are met:
14: * 1. Redistributions of source code must retain the above copyright
15: * notice, this list of conditions and the following disclaimer.
16: * 2. Redistributions in binary form must reproduce the above copyright
17: * notice, this list of conditions and the following disclaimer in the
18: * documentation and/or other materials provided with the distribution.
19: * 3. All advertising materials mentioning features or use of this software
20: * must display the following acknowledgement:
21: * This product includes software developed by the University of
22: * California, Berkeley and its contributors.
23: * 4. Neither the name of the University nor the names of its contributors
24: * may be used to endorse or promote products derived from this software
25: * without specific prior written permission.
26: *
27: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
28: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
31: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
33: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
34: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
36: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37: * SUCH DAMAGE.
38: */
39:
1.1 deraadt 40: #ifndef lint
1.2 deraadt 41: #if 0
42: static char sccsid[] = "@(#)warshall.c 5.4 (Berkeley) 5/24/93";
43: #else
1.5 ! mpech 44: static char rcsid[] = "$OpenBSD: warshall.c,v 1.4 2001/07/16 06:29:45 pvalchev Exp $";
1.2 deraadt 45: #endif
1.1 deraadt 46: #endif /* not lint */
47:
48: #include "defs.h"
49:
1.4 pvalchev 50: void transitive_closure __P((unsigned *, int));
51:
52: void
1.1 deraadt 53: transitive_closure(R, n)
54: unsigned *R;
55: int n;
56: {
1.5 ! mpech 57: int rowsize;
! 58: unsigned i;
! 59: unsigned *rowj;
! 60: unsigned *rp;
! 61: unsigned *rend;
! 62: unsigned *ccol;
! 63: unsigned *relend;
! 64: unsigned *cword;
! 65: unsigned *rowi;
1.1 deraadt 66:
67: rowsize = WORDSIZE(n);
68: relend = R + n*rowsize;
69:
70: cword = R;
71: i = 0;
72: rowi = R;
73: while (rowi < relend)
74: {
75: ccol = cword;
76: rowj = R;
77:
78: while (rowj < relend)
79: {
80: if (*ccol & (1 << i))
81: {
82: rp = rowi;
83: rend = rowj + rowsize;
84: while (rowj < rend)
85: *rowj++ |= *rp++;
86: }
87: else
88: {
89: rowj += rowsize;
90: }
91:
92: ccol += rowsize;
93: }
94:
95: if (++i >= BITS_PER_WORD)
96: {
97: i = 0;
98: cword++;
99: }
100:
101: rowi += rowsize;
102: }
103: }
104:
1.4 pvalchev 105: void
1.1 deraadt 106: reflexive_transitive_closure(R, n)
107: unsigned *R;
108: int n;
109: {
1.5 ! mpech 110: int rowsize;
! 111: unsigned i;
! 112: unsigned *rp;
! 113: unsigned *relend;
1.1 deraadt 114:
115: transitive_closure(R, n);
116:
117: rowsize = WORDSIZE(n);
118: relend = R + n*rowsize;
119:
120: i = 0;
121: rp = R;
122: while (rp < relend)
123: {
124: *rp |= (1 << i);
125: if (++i >= BITS_PER_WORD)
126: {
127: i = 0;
128: rp++;
129: }
130:
131: rp += rowsize;
132: }
133: }