Return to warshall.c CVS log

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

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

1.9     ! deraadt     1: /*     $OpenBSD: warshall.c,v 1.8 2003/06/19 16:34:53 pvalchev 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:  */
1.1       deraadt    35:
                     36: #include "defs.h"
                     37:
1.8       pvalchev   38: void transitive_closure(unsigned int *, int);
1.4       pvalchev   39:
                     40: void
1.8       pvalchev   41: transitive_closure(unsigned int *R, int n)
1.1       deraadt    42: {
1.5       mpech      43:     int rowsize;
                     44:     unsigned i;
                     45:     unsigned *rowj;
                     46:     unsigned *rp;
                     47:     unsigned *rend;
                     48:     unsigned *ccol;
                     49:     unsigned *relend;
                     50:     unsigned *cword;
                     51:     unsigned *rowi;
1.1       deraadt    52:
                     53:     rowsize = WORDSIZE(n);
                     54:     relend = R + n*rowsize;
                     55:
                     56:     cword = R;
                     57:     i = 0;
                     58:     rowi = R;
                     59:     while (rowi < relend)
                     60:     {
                     61:        ccol = cword;
                     62:        rowj = R;
                     63:
                     64:        while (rowj < relend)
                     65:        {
                     66:            if (*ccol & (1 << i))
                     67:            {
                     68:                rp = rowi;
                     69:                rend = rowj + rowsize;
                     70:                while (rowj < rend)
                     71:                    *rowj++ |= *rp++;
                     72:            }
                     73:            else
                     74:            {
                     75:                rowj += rowsize;
                     76:            }
                     77:
                     78:            ccol += rowsize;
                     79:        }
                     80:
                     81:        if (++i >= BITS_PER_WORD)
                     82:        {
                     83:            i = 0;
                     84:            cword++;
                     85:        }
                     86:
                     87:        rowi += rowsize;
                     88:     }
                     89: }
                     90:
1.4       pvalchev   91: void
1.8       pvalchev   92: reflexive_transitive_closure(unsigned int *R, int n)
1.1       deraadt    93: {
1.5       mpech      94:     int rowsize;
                     95:     unsigned i;
                     96:     unsigned *rp;
                     97:     unsigned *relend;
1.1       deraadt    98:
                     99:     transitive_closure(R, n);
                    100:
                    101:     rowsize = WORDSIZE(n);
                    102:     relend = R + n*rowsize;
                    103:
                    104:     i = 0;
                    105:     rp = R;
                    106:     while (rp < relend)
                    107:     {
                    108:        *rp |= (1 << i);
                    109:        if (++i >= BITS_PER_WORD)
                    110:        {
                    111:            i = 0;
                    112:            rp++;
                    113:        }
                    114:
                    115:        rp += rowsize;
                    116:     }
                    117: }