Return to warshall.c CVS log

Up to [CSRG BSD Unix] / 43BSDReno / pgrm / yacc

Annotation of 43BSDReno/pgrm/yacc/warshall.c, revision 1.1.1.1

1.1       root        1: /*
                      2:  * Copyright (c) 1989 The Regents of the University of California.
                      3:  * All rights reserved.
                      4:  *
                      5:  * This code is derived from software contributed to Berkeley by
                      6:  * Robert Paul Corbett.
                      7:  *
                      8:  * Redistribution and use in source and binary forms are permitted provided
                      9:  * that: (1) source distributions retain this entire copyright notice and
                     10:  * comment, and (2) distributions including binaries display the following
                     11:  * acknowledgement:  ``This product includes software developed by the
                     12:  * University of California, Berkeley and its contributors'' in the
                     13:  * documentation or other materials provided with the distribution and in
                     14:  * all advertising materials mentioning features or use of this software.
                     15:  * Neither the name of the University nor the names of its contributors may
                     16:  * be used to endorse or promote products derived from this software without
                     17:  * specific prior written permission.
                     18:  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
                     19:  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
                     20:  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
                     21:  */
                     22: 
                     23: #ifndef lint
                     24: static char sccsid[] = "@(#)warshall.c 5.3 (Berkeley) 6/1/90";
                     25: #endif /* not lint */
                     26: 
                     27: #include "defs.h"
                     28: 
                     29: transitive_closure(R, n)
                     30: unsigned *R;
                     31: int n;
                     32: {
                     33:     register int rowsize;
                     34:     register unsigned mask;
                     35:     register unsigned *rowj;
                     36:     register unsigned *rp;
                     37:     register unsigned *rend;
                     38:     register unsigned *ccol;
                     39:     register unsigned *relend;
                     40:     register unsigned *cword;
                     41:     register unsigned *rowi;
                     42: 
                     43:     rowsize = WORDSIZE(n);
                     44:     relend = R + n*rowsize;
                     45: 
                     46:     cword = R;
                     47:     mask = 1;
                     48:     rowi = R;
                     49:     while (rowi < relend)
                     50:     {
                     51:        ccol = cword;
                     52:        rowj = R;
                     53: 
                     54:        while (rowj < relend)
                     55:        {
                     56:            if (*ccol & mask)
                     57:            {
                     58:                rp = rowi;
                     59:                rend = rowj + rowsize;
                     60:                while (rowj < rend)
                     61:                    *rowj++ |= *rp++;
                     62:            }
                     63:            else
                     64:            {
                     65:                rowj += rowsize;
                     66:            }
                     67: 
                     68:            ccol += rowsize;
                     69:        }
                     70: 
                     71:        mask <<= 1;
                     72:        if (mask == 0)
                     73:        {
                     74:            mask = 1;
                     75:            cword++;
                     76:        }
                     77: 
                     78:        rowi += rowsize;
                     79:     }
                     80: }
                     81: 
                     82: reflexive_transitive_closure(R, n)
                     83: unsigned *R;
                     84: int n;
                     85: {
                     86:     register int rowsize;
                     87:     register unsigned mask;
                     88:     register unsigned *rp;
                     89:     register unsigned *relend;
                     90: 
                     91:     transitive_closure(R, n);
                     92: 
                     93:     rowsize = WORDSIZE(n);
                     94:     relend = R + n*rowsize;
                     95: 
                     96:     mask = 1;
                     97:     rp = R;
                     98:     while (rp < relend)
                     99:     {
                    100:        *rp |= mask;
                    101:        mask <<= 1;
                    102:        if (mask == 0)
                    103:        {
                    104:            mask = 1;
                    105:            rp++;
                    106:        }
                    107: 
                    108:        rp += rowsize;
                    109:     }
                    110: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.