external/bsd/byacc/dist/warshall.c

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