Return to warshall.c CVS log

Up to [Apple XNU] / GNUtools / bison

Annotation of GNUtools/bison/warshall.c, revision 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.