external/bsd/byacc/dist/warshall.c

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