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, Inc., 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21
  22 #include "system.h"
  23
  24 void RTC PARAMS((unsigned *, int));
  25
  26
  27 /* given n by n matrix of bits R, modify its contents
  28    to be the transive closure of what was given.  */
  29
  30 static void
  31 TC (unsigned *R, int n)
  32 {
  33   register int rowsize;
  34   register unsigned mask;
  35   register unsigned *rowj;
  36   register unsigned *rp;
  37   register unsigned *rend;
  38   register unsigned *ccol;
  39
  40   unsigned *relend;
  41   unsigned *cword;
  42   unsigned *rowi;
  43
  44   rowsize = WORDSIZE(n) * sizeof(unsigned);
  45   relend = (unsigned *) ((char *) R + (n * rowsize));
  46
  47   cword = R;
  48   mask = 1;
  49   rowi = R;
  50   while (rowi < relend)
  51     {
  52       ccol = cword;
  53       rowj = R;
  54
  55       while (rowj < relend)
  56         {
  57           if (*ccol & mask)
  58             {
  59               rp = rowi;
  60               rend = (unsigned *) ((char *) rowj + rowsize);
  61
  62               while (rowj < rend)
  63                 *rowj++ |= *rp++;
  64             }
  65           else
  66             {
  67               rowj = (unsigned *) ((char *) rowj + rowsize);
  68             }
  69
  70           ccol = (unsigned *) ((char *) ccol + rowsize);
  71         }
  72
  73       mask <<= 1;
  74       if (mask == 0)
  75         {
  76           mask = 1;
  77           cword++;
  78         }
  79
  80       rowi = (unsigned *) ((char *) rowi + rowsize);
  81     }
  82 }
  83
  84
  85 /* Reflexive Transitive Closure.  Same as TC
  86    and then set all the bits on the diagonal of R.  */
  87
  88 void
  89 RTC (unsigned *R, 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 }