1234949Sbapt/* $Id: warshall.c,v 1.7 2010/06/06 22:48:51 tom Exp $ */ 2234949Sbapt 3234949Sbapt#include "defs.h" 4234949Sbapt 5234949Sbaptstatic void 6234949Sbapttransitive_closure(unsigned *R, int n) 7234949Sbapt{ 8234949Sbapt int rowsize; 9234949Sbapt unsigned i; 10234949Sbapt unsigned *rowj; 11234949Sbapt unsigned *rp; 12234949Sbapt unsigned *rend; 13234949Sbapt unsigned *ccol; 14234949Sbapt unsigned *relend; 15234949Sbapt unsigned *cword; 16234949Sbapt unsigned *rowi; 17234949Sbapt 18234949Sbapt rowsize = WORDSIZE(n); 19234949Sbapt relend = R + n * rowsize; 20234949Sbapt 21234949Sbapt cword = R; 22234949Sbapt i = 0; 23234949Sbapt rowi = R; 24234949Sbapt while (rowi < relend) 25234949Sbapt { 26234949Sbapt ccol = cword; 27234949Sbapt rowj = R; 28234949Sbapt 29234949Sbapt while (rowj < relend) 30234949Sbapt { 31234949Sbapt if (*ccol & (unsigned)(1 << i)) 32234949Sbapt { 33234949Sbapt rp = rowi; 34234949Sbapt rend = rowj + rowsize; 35234949Sbapt while (rowj < rend) 36234949Sbapt *rowj++ |= *rp++; 37234949Sbapt } 38234949Sbapt else 39234949Sbapt { 40234949Sbapt rowj += rowsize; 41234949Sbapt } 42234949Sbapt 43234949Sbapt ccol += rowsize; 44234949Sbapt } 45234949Sbapt 46234949Sbapt if (++i >= BITS_PER_WORD) 47234949Sbapt { 48234949Sbapt i = 0; 49234949Sbapt cword++; 50234949Sbapt } 51234949Sbapt 52234949Sbapt rowi += rowsize; 53234949Sbapt } 54234949Sbapt} 55234949Sbapt 56234949Sbaptvoid 57234949Sbaptreflexive_transitive_closure(unsigned *R, int n) 58234949Sbapt{ 59234949Sbapt int rowsize; 60234949Sbapt unsigned i; 61234949Sbapt unsigned *rp; 62234949Sbapt unsigned *relend; 63234949Sbapt 64234949Sbapt transitive_closure(R, n); 65234949Sbapt 66234949Sbapt rowsize = WORDSIZE(n); 67234949Sbapt relend = R + n * rowsize; 68234949Sbapt 69234949Sbapt i = 0; 70234949Sbapt rp = R; 71234949Sbapt while (rp < relend) 72234949Sbapt { 73234949Sbapt *rp |= (unsigned)(1 << i); 74234949Sbapt if (++i >= BITS_PER_WORD) 75234949Sbapt { 76234949Sbapt i = 0; 77234949Sbapt rp++; 78234949Sbapt } 79234949Sbapt 80234949Sbapt rp += rowsize; 81234949Sbapt } 82234949Sbapt} 83