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 void RTC PARAMS((unsigned *, int));
  26
  27
  28 /* given n by n matrix of bits R, modify its contents
  29    to be the transive closure of what was given.  */
  30
  31 static void
  32 TC (unsigned *R, 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 (unsigned *R, int n)
  91 {
  92   register int rowsize;
  93   register unsigned mask;
  94   register unsigned *rp;
  95   register unsigned *relend;
  96
  97   TC(R, n);
  98
  99   rowsize = WORDSIZE(n) * sizeof(unsigned);
 100   relend = (unsigned *) ((char *) R + n*rowsize);
 101
 102   mask = 1;
 103   rp = R;
 104   while (rp < relend)
 105     {
 106       *rp |= mask;
 107
 108       mask <<= 1;
 109       if (mask == 0)
 110         {
 111           mask = 1;
 112           rp++;
 113         }
 114
 115       rp = (unsigned *) ((char *) rp + rowsize);
 116     }
 117 }