src/warshall.c

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