fatbase

portable OpenBSD tools
git clone git://git.2f30.org/fatbase
Log | Files | Refs

warshall.c (2780B)

      1 /* $OpenBSD: warshall.c,v 1.11 2014/03/13 01:18:22 tedu Exp $	 */
      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.
     19  * 3. Neither the name of the University nor the names of its contributors
     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 
     36 #include "defs.h"
     37 
     38 void transitive_closure(unsigned int *, int);
     39 
     40 void
     41 transitive_closure(unsigned int *R, int n)
     42 {
     43 	int rowsize;
     44 	unsigned int i;
     45 	unsigned int *rowj, *rp, *rend, *ccol, *relend, *cword, *rowi;
     46 
     47 	rowsize = WORDSIZE(n);
     48 	relend = R + n * rowsize;
     49 
     50 	cword = R;
     51 	i = 0;
     52 	rowi = R;
     53 	while (rowi < relend) {
     54 		ccol = cword;
     55 		rowj = R;
     56 
     57 		while (rowj < relend) {
     58 			if (*ccol & (1 << i)) {
     59 				rp = rowi;
     60 				rend = rowj + rowsize;
     61 				while (rowj < rend)
     62 					*rowj++ |= *rp++;
     63 			} else {
     64 				rowj += rowsize;
     65 			}
     66 
     67 			ccol += rowsize;
     68 		}
     69 
     70 		if (++i >= BITS_PER_WORD) {
     71 			i = 0;
     72 			cword++;
     73 		}
     74 		rowi += rowsize;
     75 	}
     76 }
     77 
     78 void
     79 reflexive_transitive_closure(unsigned int *R, int n)
     80 {
     81 	int rowsize;
     82 	unsigned int i;
     83 	unsigned int *rp, *relend;
     84 
     85 	transitive_closure(R, n);
     86 
     87 	rowsize = WORDSIZE(n);
     88 	relend = R + n * rowsize;
     89 
     90 	i = 0;
     91 	rp = R;
     92 	while (rp < relend) {
     93 		*rp |= (1 << i);
     94 		if (++i >= BITS_PER_WORD) {
     95 			i = 0;
     96 			rp++;
     97 		}
     98 		rp += rowsize;
     99 	}
    100 }