1 /* 2 * Copyright (c) 1989 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Robert Paul Corbett. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #ifndef lint 12 static char sccsid[] = "@(#)warshall.c 5.3 (Berkeley) 06/01/90"; 13 #endif /* not lint */ 14 15 #include "defs.h" 16 17 transitive_closure(R, n) 18 unsigned *R; 19 int n; 20 { 21 register int rowsize; 22 register unsigned mask; 23 register unsigned *rowj; 24 register unsigned *rp; 25 register unsigned *rend; 26 register unsigned *ccol; 27 register unsigned *relend; 28 register unsigned *cword; 29 register unsigned *rowi; 30 31 rowsize = WORDSIZE(n); 32 relend = R + n*rowsize; 33 34 cword = R; 35 mask = 1; 36 rowi = R; 37 while (rowi < relend) 38 { 39 ccol = cword; 40 rowj = R; 41 42 while (rowj < relend) 43 { 44 if (*ccol & mask) 45 { 46 rp = rowi; 47 rend = rowj + rowsize; 48 while (rowj < rend) 49 *rowj++ |= *rp++; 50 } 51 else 52 { 53 rowj += rowsize; 54 } 55 56 ccol += rowsize; 57 } 58 59 mask <<= 1; 60 if (mask == 0) 61 { 62 mask = 1; 63 cword++; 64 } 65 66 rowi += rowsize; 67 } 68 } 69 70 reflexive_transitive_closure(R, n) 71 unsigned *R; 72 int n; 73 { 74 register int rowsize; 75 register unsigned mask; 76 register unsigned *rp; 77 register unsigned *relend; 78 79 transitive_closure(R, n); 80 81 rowsize = WORDSIZE(n); 82 relend = R + n*rowsize; 83 84 mask = 1; 85 rp = R; 86 while (rp < relend) 87 { 88 *rp |= mask; 89 mask <<= 1; 90 if (mask == 0) 91 { 92 mask = 1; 93 rp++; 94 } 95 96 rp += rowsize; 97 } 98 } 99