1 /* $NetBSD: warshall.c,v 1.7 2013/04/06 14:52:24 christos Exp $ */ 2 3 /* Id: warshall.c,v 1.7 2010/06/06 22:48:51 tom Exp */ 4 5 #include "defs.h" 6 7 #include <sys/cdefs.h> 8 __RCSID("$NetBSD: warshall.c,v 1.7 2013/04/06 14:52:24 christos Exp $"); 9 10 static void transitive_closure(unsigned * R,int n)11transitive_closure(unsigned *R, int n) 12 { 13 int rowsize; 14 unsigned i; 15 unsigned *rowj; 16 unsigned *rp; 17 unsigned *rend; 18 unsigned *ccol; 19 unsigned *relend; 20 unsigned *cword; 21 unsigned *rowi; 22 23 rowsize = WORDSIZE(n); 24 relend = R + n * rowsize; 25 26 cword = R; 27 i = 0; 28 rowi = R; 29 while (rowi < relend) 30 { 31 ccol = cword; 32 rowj = R; 33 34 while (rowj < relend) 35 { 36 if (*ccol & (unsigned)(1 << i)) 37 { 38 rp = rowi; 39 rend = rowj + rowsize; 40 while (rowj < rend) 41 *rowj++ |= *rp++; 42 } 43 else 44 { 45 rowj += rowsize; 46 } 47 48 ccol += rowsize; 49 } 50 51 if (++i >= BITS_PER_WORD) 52 { 53 i = 0; 54 cword++; 55 } 56 57 rowi += rowsize; 58 } 59 } 60 61 void reflexive_transitive_closure(unsigned * R,int n)62reflexive_transitive_closure(unsigned *R, int n) 63 { 64 int rowsize; 65 unsigned i; 66 unsigned *rp; 67 unsigned *relend; 68 69 transitive_closure(R, n); 70 71 rowsize = WORDSIZE(n); 72 relend = R + n * rowsize; 73 74 i = 0; 75 rp = R; 76 while (rp < relend) 77 { 78 *rp |= (unsigned)(1 << i); 79 if (++i >= BITS_PER_WORD) 80 { 81 i = 0; 82 rp++; 83 } 84 85 rp += rowsize; 86 } 87 } 88