contrib/byacc/warshall.c

   1 /* $Id: warshall.c,v 1.9 2020/09/22 20:17:00 tom Exp $ */
   2
   3 #include "defs.h"
   4
   5 static void
   6 transitive_closure(unsigned *R, int n)
   7 {
   8     int rowsize;
   9     unsigned i;
  10     unsigned *rowj;
  11     unsigned *rp;
  12     unsigned *rend;
  13     unsigned *relend;
  14     unsigned *cword;
  15     unsigned *rowi;
  16
  17     rowsize = WORDSIZE(n);
  18     relend = R + n * rowsize;
  19
  20     cword = R;
  21     i = 0;
  22     rowi = R;
  23     while (rowi < relend)
  24     {
  25         unsigned *ccol = cword;
  26
  27         rowj = R;
  28
  29         while (rowj < relend)
  30         {
  31             if (*ccol & (1U << i))
  32             {
  33                 rp = rowi;
  34                 rend = rowj + rowsize;
  35                 while (rowj < rend)
  36                     *rowj++ |= *rp++;
  37             }
  38             else
  39             {
  40                 rowj += rowsize;
  41             }
  42
  43             ccol += rowsize;
  44         }
  45
  46         if (++i >= BITS_PER_WORD)
  47         {
  48             i = 0;
  49             cword++;
  50         }
  51
  52         rowi += rowsize;
  53     }
  54 }
  55
  56 void
  57 reflexive_transitive_closure(unsigned *R, int n)
  58 {
  59     int rowsize;
  60     unsigned i;
  61     unsigned *rp;
  62     unsigned *relend;
  63
  64     transitive_closure(R, n);
  65
  66     rowsize = WORDSIZE(n);
  67     relend = R + n * rowsize;
  68
  69     i = 0;
  70     rp = R;
  71     while (rp < relend)
  72     {
  73         *rp |= (1U << i);
  74         if (++i >= BITS_PER_WORD)
  75         {
  76             i = 0;
  77             rp++;
  78         }
  79
  80         rp += rowsize;
  81     }
  82 }