util/byacc/warshall.c

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