usr.bin/yacc/warshall.c

   1 /*      $NetBSD: warshall.c,v 1.7 2003/08/07 11:17:55 agc Exp $ */
   2
   3 /*
   4  * Copyright (c) 1989 The Regents of the University of California.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Robert Paul Corbett.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 #include <sys/cdefs.h>
  36 #if defined(__RCSID) && !defined(lint)
  37 #if 0
  38 static char sccsid[] = "@(#)warshall.c  5.4 (Berkeley) 5/24/93";
  39 #else
  40 __RCSID("$NetBSD: warshall.c,v 1.7 2003/08/07 11:17:55 agc Exp $");
  41 #endif
  42 #endif /* not lint */
  43
  44 #include "defs.h"
  45
  46 static void transitive_closure(unsigned *, int);
  47
  48 static void
  49 transitive_closure(unsigned *R, int n)
  50 {
  51     int rowsize;
  52     unsigned i;
  53     unsigned *rowj;
  54     unsigned *rp;
  55     unsigned *rend;
  56     unsigned *ccol;
  57     unsigned *relend;
  58     unsigned *cword;
  59     unsigned *rowi;
  60
  61     rowsize = WORDSIZE(n);
  62     relend = R + n*rowsize;
  63
  64     cword = R;
  65     i = 0;
  66     rowi = R;
  67     while (rowi < relend)
  68     {
  69         ccol = cword;
  70         rowj = R;
  71
  72         while (rowj < relend)
  73         {
  74             if (*ccol & (1 << i))
  75             {
  76                 rp = rowi;
  77                 rend = rowj + rowsize;
  78                 while (rowj < rend)
  79                     *rowj++ |= *rp++;
  80             }
  81             else
  82             {
  83                 rowj += rowsize;
  84             }
  85
  86             ccol += rowsize;
  87         }
  88
  89         if (++i >= BITS_PER_WORD)
  90         {
  91             i = 0;
  92             cword++;
  93         }
  94
  95         rowi += rowsize;
  96     }
  97 }
  98
  99 void
 100 reflexive_transitive_closure(unsigned *R, int n)
 101 {
 102     int rowsize;
 103     unsigned i;
 104     unsigned *rp;
 105     unsigned *relend;
 106
 107     transitive_closure(R, n);
 108
 109     rowsize = WORDSIZE(n);
 110     relend = R + n*rowsize;
 111
 112     i = 0;
 113     rp = R;
 114     while (rp < relend)
 115     {
 116         *rp |= (1 << i);
 117         if (++i >= BITS_PER_WORD)
 118         {
 119             i = 0;
 120             rp++;
 121         }
 122
 123         rp += rowsize;
 124     }
 125 }