diff options
Diffstat (limited to 'contrib/byacc/warshall.c')
-rw-r--r-- | contrib/byacc/warshall.c | 82 |
1 files changed, 82 insertions, 0 deletions
diff --git a/contrib/byacc/warshall.c b/contrib/byacc/warshall.c new file mode 100644 index 0000000..efb7cf4 --- /dev/null +++ b/contrib/byacc/warshall.c @@ -0,0 +1,82 @@ +/* $Id: warshall.c,v 1.7 2010/06/06 22:48:51 tom Exp $ */ + +#include "defs.h" + +static void +transitive_closure(unsigned *R, int n) +{ + int rowsize; + unsigned i; + unsigned *rowj; + unsigned *rp; + unsigned *rend; + unsigned *ccol; + unsigned *relend; + unsigned *cword; + unsigned *rowi; + + rowsize = WORDSIZE(n); + relend = R + n * rowsize; + + cword = R; + i = 0; + rowi = R; + while (rowi < relend) + { + ccol = cword; + rowj = R; + + while (rowj < relend) + { + if (*ccol & (unsigned)(1 << i)) + { + rp = rowi; + rend = rowj + rowsize; + while (rowj < rend) + *rowj++ |= *rp++; + } + else + { + rowj += rowsize; + } + + ccol += rowsize; + } + + if (++i >= BITS_PER_WORD) + { + i = 0; + cword++; + } + + rowi += rowsize; + } +} + +void +reflexive_transitive_closure(unsigned *R, int n) +{ + int rowsize; + unsigned i; + unsigned *rp; + unsigned *relend; + + transitive_closure(R, n); + + rowsize = WORDSIZE(n); + relend = R + n * rowsize; + + i = 0; + rp = R; + while (rp < relend) + { + *rp |= (unsigned)(1 << i); + if (++i >= BITS_PER_WORD) + { + i = 0; + rp++; + } + + rp += rowsize; + } +} |