diff options
author | marha <marha@users.sourceforge.net> | 2010-11-19 15:19:19 +0000 |
---|---|---|
committer | marha <marha@users.sourceforge.net> | 2010-11-19 15:19:19 +0000 |
commit | d12ad2fa1165573df95c857ce59f582f964b7cee (patch) | |
tree | 8d5546283940c928290a23c50748b3f5c431ef06 /tools/bison++/warshall.cc | |
parent | bd5413c3a7e500fa8c8ccd68a33d2fcc4c172e28 (diff) | |
parent | 12f606ce06ef926f366a03079c5e3107c23f18af (diff) | |
download | vcxsrv-d12ad2fa1165573df95c857ce59f582f964b7cee.tar.gz vcxsrv-d12ad2fa1165573df95c857ce59f582f964b7cee.tar.bz2 vcxsrv-d12ad2fa1165573df95c857ce59f582f964b7cee.zip |
svn merge ^/branches/released .
Diffstat (limited to 'tools/bison++/warshall.cc')
-rw-r--r-- | tools/bison++/warshall.cc | 115 |
1 files changed, 115 insertions, 0 deletions
diff --git a/tools/bison++/warshall.cc b/tools/bison++/warshall.cc new file mode 100644 index 000000000..576a3a4e9 --- /dev/null +++ b/tools/bison++/warshall.cc @@ -0,0 +1,115 @@ +/* Generate transitive closure of a matrix, + Copyright (C) 1984, 1989 Free Software Foundation, Inc. + +This file is part of Bison, the GNU Compiler Compiler. + +Bison is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +Bison is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with Bison; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + + +#include <stdio.h> +#include "system.h" +#include "machine.h" + + +/* given n by n matrix of bits R, modify its contents + to be the transive closure of what was given. */ + +void +TC(unsigned* R, int n) +{ + register int rowsize; + register unsigned mask; + register unsigned *rowj; + register unsigned *rp; + register unsigned *rend; + register unsigned *ccol; + + unsigned *relend; + unsigned *cword; + unsigned *rowi; + + rowsize = WORDSIZE(n) * sizeof(unsigned); + relend = (unsigned *) ((char *) R + (n * rowsize)); + + cword = R; + mask = 1; + rowi = R; + while (rowi < relend) + { + ccol = cword; + rowj = R; + + while (rowj < relend) + { + if (*ccol & mask) + { + rp = rowi; + rend = (unsigned *) ((char *) rowj + rowsize); + + while (rowj < rend) + *rowj++ |= *rp++; + } + else + { + rowj = (unsigned *) ((char *) rowj + rowsize); + } + + ccol = (unsigned *) ((char *) ccol + rowsize); + } + + mask <<= 1; + if (mask == 0) + { + mask = 1; + cword++; + } + + rowi = (unsigned *) ((char *) rowi + rowsize); + } +} + + +/* Reflexive Transitive Closure. Same as TC + and then set all the bits on the diagonal of R. */ + +void +RTC(unsigned* R, int n) +{ + register int rowsize; + register unsigned mask; + register unsigned *rp; + register unsigned *relend; + + TC(R, n); + + rowsize = WORDSIZE(n) * sizeof(unsigned); + relend = (unsigned *) ((char *) R + n*rowsize); + + mask = 1; + rp = R; + while (rp < relend) + { + *rp |= mask; + + mask <<= 1; + if (mask == 0) + { + mask = 1; + rp++; + } + + rp = (unsigned *) ((char *) rp + rowsize); + } +} |