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 <stdio.h>
  23 #include "system.h"
  24 #include "machine.h"
  25
  26 void RTC PARAMS((unsigned *, int));
  27
  28
  29 /* given n by n matrix of bits R, modify its contents
  30    to be the transive closure of what was given.  */
  31
  32 static void
  33 TC (unsigned *R, int n)
  34 {
  35   register int rowsize;
  36   register unsigned mask;
  37   register unsigned *rowj;
  38   register unsigned *rp;
  39   register unsigned *rend;
  40   register unsigned *ccol;
  41
  42   unsigned *relend;
  43   unsigned *cword;
  44   unsigned *rowi;
  45
  46   rowsize = WORDSIZE(n) * sizeof(unsigned);
  47   relend = (unsigned *) ((char *) R + (n * rowsize));
  48
  49   cword = R;
  50   mask = 1;
  51   rowi = R;
  52   while (rowi < relend)
  53     {
  54       ccol = cword;
  55       rowj = R;
  56
  57       while (rowj < relend)
  58         {
  59           if (*ccol & mask)
  60             {
  61               rp = rowi;
  62               rend = (unsigned *) ((char *) rowj + rowsize);
  63
  64               while (rowj < rend)
  65                 *rowj++ |= *rp++;
  66             }
  67           else
  68             {
  69               rowj = (unsigned *) ((char *) rowj + rowsize);
  70             }
  71
  72           ccol = (unsigned *) ((char *) ccol + rowsize);
  73         }
  74
  75       mask <<= 1;
  76       if (mask == 0)
  77         {
  78           mask = 1;
  79           cword++;
  80         }
  81
  82       rowi = (unsigned *) ((char *) rowi + rowsize);
  83     }
  84 }
  85
  86
  87 /* Reflexive Transitive Closure.  Same as TC
  88    and then set all the bits on the diagonal of R.  */
  89
  90 void
  91 RTC (unsigned *R, int n)
  92 {
  93   register int rowsize;
  94   register unsigned mask;
  95   register unsigned *rp;
  96   register unsigned *relend;
  97
  98   TC(R, n);
  99
 100   rowsize = WORDSIZE(n) * sizeof(unsigned);
 101   relend = (unsigned *) ((char *) R + n*rowsize);
 102
 103   mask = 1;
 104   rp = R;
 105   while (rp < relend)
 106     {
 107       *rp |= mask;
 108
 109       mask <<= 1;
 110       if (mask == 0)
 111         {
 112           mask = 1;
 113           rp++;
 114         }
 115
 116       rp = (unsigned *) ((char *) rp + rowsize);
 117     }
 118 }