Return to warshall.c CVS log

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

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

1.10    ! tedu        1: /* $OpenBSD: warshall.c,v 1.9 2009/10/27 23:59:50 deraadt Exp $         */
        !             2: /* $NetBSD: warshall.c,v 1.4 1996/03/19 03:21:51 jtc Exp $      */
1.2       deraadt     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.10    ! tedu       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;
        !            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:                ccol = cword;
        !            61:                rowj = R;
        !            62:
        !            63:                while (rowj < relend) {
        !            64:                        if (*ccol & (1 << i)) {
        !            65:                                rp = rowi;
        !            66:                                rend = rowj + rowsize;
        !            67:                                while (rowj < rend)
        !            68:                                        *rowj++ |= *rp++;
        !            69:                        } else {
        !            70:                                rowj += rowsize;
        !            71:                        }
        !            72:
        !            73:                        ccol += rowsize;
        !            74:                }
        !            75:
        !            76:                if (++i >= BITS_PER_WORD) {
        !            77:                        i = 0;
        !            78:                        cword++;
        !            79:                }
        !            80:                rowi += rowsize;
1.1       deraadt    81:        }
                     82: }
                     83:
1.4       pvalchev   84: void
1.8       pvalchev   85: reflexive_transitive_closure(unsigned int *R, int n)
1.1       deraadt    86: {
1.10    ! tedu       87:        int rowsize;
        !            88:        unsigned i;
        !            89:        unsigned *rp;
        !            90:        unsigned *relend;
        !            91:
        !            92:        transitive_closure(R, n);
        !            93:
        !            94:        rowsize = WORDSIZE(n);
        !            95:        relend = R + n * rowsize;
        !            96:
        !            97:        i = 0;
        !            98:        rp = R;
        !            99:        while (rp < relend) {
        !           100:                *rp |= (1 << i);
        !           101:                if (++i >= BITS_PER_WORD) {
        !           102:                        i = 0;
        !           103:                        rp++;
        !           104:                }
        !           105:                rp += rowsize;
1.1       deraadt   106:        }
                    107: }