Return to warshall.c CVS log

Up to [local] / src / usr.bin / yacc

Annotation of src/usr.bin/yacc/warshall.c, Revision 1.7

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