commands/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 i;
   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     i = 0;
  22     rowi = R;
  23     while (rowi < relend)
  24     {
  25         ccol = cword;
  26         rowj = R;
  27
  28         while (rowj < relend)
  29         {
  30             if (*ccol & (1 << i))
  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         if (++i >= BITS_PER_WORD)
  46         {
  47             i = 0;
  48             cword++;
  49         }
  50
  51         rowi += rowsize;
  52     }
  53 }
  54
  55 reflexive_transitive_closure(R, n)
  56 unsigned *R;
  57 int n;
  58 {
  59     register int rowsize;
  60     register unsigned i;
  61     register unsigned *rp;
  62     register 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 |= (1 << i);
  74         if (++i >= BITS_PER_WORD)
  75         {
  76             i = 0;
  77             rp++;
  78         }
  79
  80         rp += rowsize;
  81     }
  82 }