src/warshall.c

   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 }