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.4 (Berkeley) 05/24/93"; 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 i; 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 i = 0; 36 rowi = R; 37 while (rowi < relend) 38 { 39 ccol = cword; 40 rowj = R; 41 42 while (rowj < relend) 43 { 44 if (*ccol & (1 << i)) 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 if (++i >= BITS_PER_WORD) 60 { 61 i = 0; 62 cword++; 63 } 64 65 rowi += rowsize; 66 } 67 } 68 69 reflexive_transitive_closure(R, n) 70 unsigned *R; 71 int n; 72 { 73 register int rowsize; 74 register unsigned i; 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 i = 0; 84 rp = R; 85 while (rp < relend) 86 { 87 *rp |= (1 << i); 88 if (++i >= BITS_PER_WORD) 89 { 90 i = 0; 91 rp++; 92 } 93 94 rp += rowsize; 95 } 96 } 97