18e022d3cSDag-Erling Smørgrav /* $Id: warshall.c,v 1.9 2020/09/22 20:17:00 tom Exp $ */ 298e903e7SBaptiste Daroussin 398e903e7SBaptiste Daroussin #include "defs.h" 498e903e7SBaptiste Daroussin 598e903e7SBaptiste Daroussin static void transitive_closure(unsigned * R,int n)698e903e7SBaptiste Daroussintransitive_closure(unsigned *R, int n) 798e903e7SBaptiste Daroussin { 898e903e7SBaptiste Daroussin int rowsize; 998e903e7SBaptiste Daroussin unsigned i; 1098e903e7SBaptiste Daroussin unsigned *rowj; 1198e903e7SBaptiste Daroussin unsigned *rp; 1298e903e7SBaptiste Daroussin unsigned *rend; 1398e903e7SBaptiste Daroussin unsigned *relend; 1498e903e7SBaptiste Daroussin unsigned *cword; 1598e903e7SBaptiste Daroussin unsigned *rowi; 1698e903e7SBaptiste Daroussin 1798e903e7SBaptiste Daroussin rowsize = WORDSIZE(n); 1898e903e7SBaptiste Daroussin relend = R + n * rowsize; 1998e903e7SBaptiste Daroussin 2098e903e7SBaptiste Daroussin cword = R; 2198e903e7SBaptiste Daroussin i = 0; 2298e903e7SBaptiste Daroussin rowi = R; 2398e903e7SBaptiste Daroussin while (rowi < relend) 2498e903e7SBaptiste Daroussin { 258e022d3cSDag-Erling Smørgrav unsigned *ccol = cword; 268e022d3cSDag-Erling Smørgrav 2798e903e7SBaptiste Daroussin rowj = R; 2898e903e7SBaptiste Daroussin 2998e903e7SBaptiste Daroussin while (rowj < relend) 3098e903e7SBaptiste Daroussin { 318e022d3cSDag-Erling Smørgrav if (*ccol & (1U << i)) 3298e903e7SBaptiste Daroussin { 3398e903e7SBaptiste Daroussin rp = rowi; 3498e903e7SBaptiste Daroussin rend = rowj + rowsize; 3598e903e7SBaptiste Daroussin while (rowj < rend) 3698e903e7SBaptiste Daroussin *rowj++ |= *rp++; 3798e903e7SBaptiste Daroussin } 3898e903e7SBaptiste Daroussin else 3998e903e7SBaptiste Daroussin { 4098e903e7SBaptiste Daroussin rowj += rowsize; 4198e903e7SBaptiste Daroussin } 4298e903e7SBaptiste Daroussin 4398e903e7SBaptiste Daroussin ccol += rowsize; 4498e903e7SBaptiste Daroussin } 4598e903e7SBaptiste Daroussin 4698e903e7SBaptiste Daroussin if (++i >= BITS_PER_WORD) 4798e903e7SBaptiste Daroussin { 4898e903e7SBaptiste Daroussin i = 0; 4998e903e7SBaptiste Daroussin cword++; 5098e903e7SBaptiste Daroussin } 5198e903e7SBaptiste Daroussin 5298e903e7SBaptiste Daroussin rowi += rowsize; 5398e903e7SBaptiste Daroussin } 5498e903e7SBaptiste Daroussin } 5598e903e7SBaptiste Daroussin 5698e903e7SBaptiste Daroussin void reflexive_transitive_closure(unsigned * R,int n)5798e903e7SBaptiste Daroussinreflexive_transitive_closure(unsigned *R, int n) 5898e903e7SBaptiste Daroussin { 5998e903e7SBaptiste Daroussin int rowsize; 6098e903e7SBaptiste Daroussin unsigned i; 6198e903e7SBaptiste Daroussin unsigned *rp; 6298e903e7SBaptiste Daroussin unsigned *relend; 6398e903e7SBaptiste Daroussin 6498e903e7SBaptiste Daroussin transitive_closure(R, n); 6598e903e7SBaptiste Daroussin 6698e903e7SBaptiste Daroussin rowsize = WORDSIZE(n); 6798e903e7SBaptiste Daroussin relend = R + n * rowsize; 6898e903e7SBaptiste Daroussin 6998e903e7SBaptiste Daroussin i = 0; 7098e903e7SBaptiste Daroussin rp = R; 7198e903e7SBaptiste Daroussin while (rp < relend) 7298e903e7SBaptiste Daroussin { 738e022d3cSDag-Erling Smørgrav *rp |= (1U << i); 7498e903e7SBaptiste Daroussin if (++i >= BITS_PER_WORD) 7598e903e7SBaptiste Daroussin { 7698e903e7SBaptiste Daroussin i = 0; 7798e903e7SBaptiste Daroussin rp++; 7898e903e7SBaptiste Daroussin } 7998e903e7SBaptiste Daroussin 8098e903e7SBaptiste Daroussin rp += rowsize; 8198e903e7SBaptiste Daroussin } 8298e903e7SBaptiste Daroussin } 83