1/* $NetBSD: warshall.c,v 1.11 2021/02/20 22:57:56 christos Exp $ */ 2 3/* Id: warshall.c,v 1.9 2020/09/22 20:17:00 tom Exp */ 4 5#include "defs.h" 6 7#include <sys/cdefs.h> 8__RCSID("$NetBSD: warshall.c,v 1.11 2021/02/20 22:57:56 christos Exp $"); 9 10static void 11transitive_closure(unsigned *R, int n) 12{ 13 int rowsize; 14 unsigned i; 15 unsigned *rowj; 16 unsigned *rp; 17 unsigned *rend; 18 unsigned *relend; 19 unsigned *cword; 20 unsigned *rowi; 21 22 rowsize = WORDSIZE(n); 23 relend = R + n * rowsize; 24 25 cword = R; 26 i = 0; 27 rowi = R; 28 while (rowi < relend) 29 { 30 unsigned *ccol = cword; 31 32 rowj = R; 33 34 while (rowj < relend) 35 { 36 if (*ccol & (1U << 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 61void 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 |= (1U << i); 79 if (++i >= BITS_PER_WORD) 80 { 81 i = 0; 82 rp++; 83 } 84 85 rp += rowsize; 86 } 87} 88