Return to warshall.c CVS log

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

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

1.1     ! deraadt     1: #ifndef lint
        !             2: static char rcsid[] = "$Id: warshall.c,v 1.3 1993/08/02 17:56:52 mycroft Exp $";
        !             3: #endif /* not lint */
        !             4:
        !             5: #include "defs.h"
        !             6:
        !             7: transitive_closure(R, n)
        !             8: unsigned *R;
        !             9: int n;
        !            10: {
        !            11:     register int rowsize;
        !            12:     register unsigned i;
        !            13:     register unsigned *rowj;
        !            14:     register unsigned *rp;
        !            15:     register unsigned *rend;
        !            16:     register unsigned *ccol;
        !            17:     register unsigned *relend;
        !            18:     register unsigned *cword;
        !            19:     register unsigned *rowi;
        !            20:
        !            21:     rowsize = WORDSIZE(n);
        !            22:     relend = R + n*rowsize;
        !            23:
        !            24:     cword = R;
        !            25:     i = 0;
        !            26:     rowi = R;
        !            27:     while (rowi < relend)
        !            28:     {
        !            29:        ccol = cword;
        !            30:        rowj = R;
        !            31:
        !            32:        while (rowj < relend)
        !            33:        {
        !            34:            if (*ccol & (1 << i))
        !            35:            {
        !            36:                rp = rowi;
        !            37:                rend = rowj + rowsize;
        !            38:                while (rowj < rend)
        !            39:                    *rowj++ |= *rp++;
        !            40:            }
        !            41:            else
        !            42:            {
        !            43:                rowj += rowsize;
        !            44:            }
        !            45:
        !            46:            ccol += rowsize;
        !            47:        }
        !            48:
        !            49:        if (++i >= BITS_PER_WORD)
        !            50:        {
        !            51:            i = 0;
        !            52:            cword++;
        !            53:        }
        !            54:
        !            55:        rowi += rowsize;
        !            56:     }
        !            57: }
        !            58:
        !            59: reflexive_transitive_closure(R, n)
        !            60: unsigned *R;
        !            61: int n;
        !            62: {
        !            63:     register int rowsize;
        !            64:     register unsigned i;
        !            65:     register unsigned *rp;
        !            66:     register 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: }