1 /* $NetBSD: warshall.c,v 1.6 2011/09/10 21:29:04 christos Exp $ */ 2 /* Id: warshall.c,v 1.7 2010/06/06 22:48:51 tom Exp */ 3 4 #include "defs.h" 5 6 #include <sys/cdefs.h> 7 __RCSID("$NetBSD: warshall.c,v 1.6 2011/09/10 21:29:04 christos Exp $"); 8 9 static void 10 transitive_closure(unsigned *R, int n) 11 { 12 int rowsize; 13 unsigned i; 14 unsigned *rowj; 15 unsigned *rp; 16 unsigned *rend; 17 unsigned *ccol; 18 unsigned *relend; 19 unsigned *cword; 20 unsigned *rowi; 21 22 rowsize = WORDSIZE(n); 23 relend = R + n * rowsize; 24 25 cword = R; 26 i = 0; 27 rowi = R; 28 while (rowi < relend) 29 { 30 ccol = cword; 31 rowj = R; 32 33 while (rowj < relend) 34 { 35 if (*ccol & (unsigned)(1 << i)) 36 { 37 rp = rowi; 38 rend = rowj + rowsize; 39 while (rowj < rend) 40 *rowj++ |= *rp++; 41 } 42 else 43 { 44 rowj += rowsize; 45 } 46 47 ccol += rowsize; 48 } 49 50 if (++i >= BITS_PER_WORD) 51 { 52 i = 0; 53 cword++; 54 } 55 56 rowi += rowsize; 57 } 58 } 59 60 void 61 reflexive_transitive_closure(unsigned *R, int n) 62 { 63 int rowsize; 64 unsigned i; 65 unsigned *rp; 66 unsigned *relend; 67 68 transitive_closure(R, n); 69 70 rowsize = WORDSIZE(n); 71 relend = R + n * rowsize; 72 73 i = 0; 74 rp = R; 75 while (rp < relend) 76 { 77 *rp |= (unsigned)(1 << i); 78 if (++i >= BITS_PER_WORD) 79 { 80 i = 0; 81 rp++; 82 } 83 84 rp += rowsize; 85 } 86 } 87