Return to warshall.c CVS log

Up to [Research Unix] / researchv10dc / cmd / bison

Annotation of researchv10dc/cmd/bison/warshall.c, revision 1.1.1.1

1.1       root        1: /* Generate transitive closure of a matrix,
                      2:    Copyright (C) 1984 Bob Corbett and Free Software Foundation, Inc.
                      3: 
                      4: BISON is distributed in the hope that it will be useful, but WITHOUT ANY
                      5: WARRANTY.  No author or distributor accepts responsibility to anyone
                      6: for the consequences of using it or for whether it serves any
                      7: particular purpose or works at all, unless he says so in writing.
                      8: Refer to the BISON General Public License for full details.
                      9: 
                     10: Everyone is granted permission to copy, modify and redistribute BISON,
                     11: but only under the conditions described in the BISON General Public
                     12: License.  A copy of this license is supposed to have been given to you
                     13: along with BISON so you can know your rights and responsibilities.  It
                     14: should be in a file named COPYING.  Among other things, the copyright
                     15: notice and this notice must be preserved on all copies.
                     16: 
                     17:  In other words, you are welcome to use, share and improve this program.
                     18:  You are forbidden to forbid anyone else to use, share and improve
                     19:  what you give them.   Help stamp out software-hoarding!  */
                     20: 
                     21: #include <stdio.h>
                     22: #include "machine.h"
                     23: 
                     24: 
                     25: /* given n by n matrix of bits R, modify its contents
                     26:    to be the transive closure of what was given.  */
                     27: 
                     28: TC(R, n)
                     29: unsigned *R;
                     30: int n;
                     31: {
                     32:   register int rowsize;
                     33:   register unsigned mask;
                     34:   register unsigned *rowj;
                     35:   register unsigned *rp;
                     36:   register unsigned *rend;
                     37:   register unsigned *ccol;
                     38: 
                     39:   unsigned *relend;
                     40:   unsigned *cword;
                     41:   unsigned *rowi;
                     42: 
                     43:   rowsize = WORDSIZE(n) * sizeof(unsigned);
                     44:   relend = (unsigned *) ((char *) R + (n * rowsize));
                     45: 
                     46:   cword = R;
                     47:   mask = 1;
                     48:   rowi = R;
                     49:   while (rowi < relend)
                     50:     {
                     51:       ccol = cword;
                     52:       rowj = R;
                     53: 
                     54:       while (rowj < relend)
                     55:        {
                     56:          if (*ccol & mask)
                     57:            {
                     58:              rp = rowi;
                     59:              rend = (unsigned *) ((char *) rowj + rowsize);
                     60: 
                     61:              while (rowj < rend)
                     62:                *rowj++ |= *rp++;
                     63:            }
                     64:          else
                     65:            {
                     66:              rowj = (unsigned *) ((char *) rowj + rowsize);
                     67:            }
                     68: 
                     69:          ccol = (unsigned *) ((char *) ccol + rowsize);
                     70:        }
                     71: 
                     72:       mask <<= 1;
                     73:       if (mask == 0)
                     74:        {
                     75:          mask = 1;
                     76:          cword++;
                     77:        }
                     78: 
                     79:       rowi = (unsigned *) ((char *) rowi + rowsize);
                     80:     }
                     81: }
                     82: 
                     83: 
                     84: /* Reflexive Transitive Closure.  Same as TC
                     85:    and then set all the bits on the diagonal of R.  */
                     86: 
                     87: RTC(R, n)
                     88: unsigned *R;
                     89: int n;
                     90: {
                     91:   register int rowsize;
                     92:   register unsigned mask;
                     93:   register unsigned *rp;
                     94:   register unsigned *relend;
                     95: 
                     96:   TC(R, n);
                     97: 
                     98:   rowsize = WORDSIZE(n) * sizeof(unsigned);
                     99:   relend = (unsigned *) ((char *) R + n*rowsize);
                    100: 
                    101:   mask = 1;
                    102:   rp = R;
                    103:   while (rp < relend)
                    104:     {
                    105:       *rp |= mask;
                    106: 
                    107:       mask <<= 1;
                    108:       if (mask == 0)
                    109:        {
                    110:          mask = 1;
                    111:          rp++;
                    112:        }
                    113: 
                    114:       rp = (unsigned *) ((char *) rp + rowsize);
                    115:     }
                    116: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.