Return to warshall.c CVS log

Up to [Apple XNU] / GNUtools / bison

Annotation of GNUtools/bison/warshall.c, revision 1.1.1.1

1.1       root        1: /* Generate transitive closure of a matrix,
                      2:    Copyright (C) 1984, 1989 Free Software Foundation, Inc.
                      3: 
                      4: This file is part of Bison, the GNU Compiler Compiler.
                      5: 
                      6: Bison is free software; you can redistribute it and/or modify
                      7: it under the terms of the GNU General Public License as published by
                      8: the Free Software Foundation; either version 2, or (at your option)
                      9: any later version.
                     10: 
                     11: Bison is distributed in the hope that it will be useful,
                     12: but WITHOUT ANY WARRANTY; without even the implied warranty of
                     13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
                     14: GNU General Public License for more details.
                     15: 
                     16: You should have received a copy of the GNU General Public License
                     17: along with Bison; see the file COPYING.  If not, write to
                     18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
                     19: 
                     20: 
                     21: #include <stdio.h>
                     22: #include "system.h"
                     23: #include "machine.h"
                     24: 
                     25: 
                     26: /* given n by n matrix of bits R, modify its contents
                     27:    to be the transive closure of what was given.  */
                     28: 
                     29: void
                     30: TC(R, n)
                     31: unsigned *R;
                     32: int n;
                     33: {
                     34:   register int rowsize;
                     35:   register unsigned mask;
                     36:   register unsigned *rowj;
                     37:   register unsigned *rp;
                     38:   register unsigned *rend;
                     39:   register unsigned *ccol;
                     40: 
                     41:   unsigned *relend;
                     42:   unsigned *cword;
                     43:   unsigned *rowi;
                     44: 
                     45:   rowsize = WORDSIZE(n) * sizeof(unsigned);
                     46:   relend = (unsigned *) ((char *) R + (n * rowsize));
                     47: 
                     48:   cword = R;
                     49:   mask = 1;
                     50:   rowi = R;
                     51:   while (rowi < relend)
                     52:     {
                     53:       ccol = cword;
                     54:       rowj = R;
                     55: 
                     56:       while (rowj < relend)
                     57:        {
                     58:          if (*ccol & mask)
                     59:            {
                     60:              rp = rowi;
                     61:              rend = (unsigned *) ((char *) rowj + rowsize);
                     62: 
                     63:              while (rowj < rend)
                     64:                *rowj++ |= *rp++;
                     65:            }
                     66:          else
                     67:            {
                     68:              rowj = (unsigned *) ((char *) rowj + rowsize);
                     69:            }
                     70: 
                     71:          ccol = (unsigned *) ((char *) ccol + rowsize);
                     72:        }
                     73: 
                     74:       mask <<= 1;
                     75:       if (mask == 0)
                     76:        {
                     77:          mask = 1;
                     78:          cword++;
                     79:        }
                     80: 
                     81:       rowi = (unsigned *) ((char *) rowi + rowsize);
                     82:     }
                     83: }
                     84: 
                     85: 
                     86: /* Reflexive Transitive Closure.  Same as TC
                     87:    and then set all the bits on the diagonal of R.  */
                     88: 
                     89: void
                     90: RTC(R, n)
                     91: unsigned *R;
                     92: int n;
                     93: {
                     94:   register int rowsize;
                     95:   register unsigned mask;
                     96:   register unsigned *rp;
                     97:   register unsigned *relend;
                     98: 
                     99:   TC(R, n);
                    100: 
                    101:   rowsize = WORDSIZE(n) * sizeof(unsigned);
                    102:   relend = (unsigned *) ((char *) R + n*rowsize);
                    103: 
                    104:   mask = 1;
                    105:   rp = R;
                    106:   while (rp < relend)
                    107:     {
                    108:       *rp |= mask;
                    109: 
                    110:       mask <<= 1;
                    111:       if (mask == 0)
                    112:        {
                    113:          mask = 1;
                    114:          rp++;
                    115:        }
                    116: 
                    117:       rp = (unsigned *) ((char *) rp + rowsize);
                    118:     }
                    119: }

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