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, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 4. Neither the name of the University nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 */ 32 33#if 0 34#ifndef lint 35static char sccsid[] = "@(#)warshall.c 5.4 (Berkeley) 5/24/93"; 36#endif 37#endif 38 39#include <sys/cdefs.h> 40__FBSDID("$FreeBSD$"); 41 42#include "defs.h" 43 44static void transitive_closure(unsigned *, int); 45 46static void 47transitive_closure(unsigned *R, int n) 48{ 49 int rowsize; 50 unsigned i; 51 unsigned *rowj; 52 unsigned *rp; 53 unsigned *rend; 54 unsigned *ccol; 55 unsigned *relend; 56 unsigned *cword; 57 unsigned *rowi; 58 59 rowsize = WORDSIZE(n); 60 relend = R + n*rowsize; 61 62 cword = R; 63 i = 0; 64 rowi = R; 65 while (rowi < relend) 66 { 67 ccol = cword; 68 rowj = R; 69 70 while (rowj < relend) 71 { 72 if (*ccol & (1 << i)) 73 { 74 rp = rowi; 75 rend = rowj + rowsize; 76 while (rowj < rend) 77 *rowj++ |= *rp++; 78 } 79 else 80 { 81 rowj += rowsize; 82 } 83 84 ccol += rowsize; 85 } 86 87 if (++i >= BITS_PER_WORD) 88 { 89 i = 0; 90 cword++; 91 } 92 93 rowi += rowsize; 94 } 95} 96 97void 98reflexive_transitive_closure(unsigned *R, int n) 99{ 100 int rowsize; 101 unsigned i; 102 unsigned *rp; 103 unsigned *relend; 104 105 transitive_closure(R, n); 106 107 rowsize = WORDSIZE(n); 108 relend = R + n*rowsize; 109 110 i = 0; 111 rp = R; 112 while (rp < relend) 113 { 114 *rp |= (1 << i); 115 if (++i >= BITS_PER_WORD) 116 { 117 i = 0; 118 rp++; 119 } 120 121 rp += rowsize; 122 } 123} 124