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