home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / online / source / c / compilers / Bison.sit.hqx / Bison / Source / warshall.c < prev    next >
Text File  |  1992-08-21  |  3KB  |  131 lines
  1. /***********************************************************
  2.  *
  3.  * Macintosh/MPW version of GNU Bison 1.18
  4.  * Please read the README_MPW file for more information
  5.  *
  6.  ***********************************************************/
  7.  
  8. /* Generate transitive closure of a matrix,
  9.    Copyright (C) 1984, 1989 Free Software Foundation, Inc.
  10.  
  11. This file is part of Bison, the GNU Compiler Compiler.
  12.  
  13. Bison is free software; you can redistribute it and/or modify
  14. it under the terms of the GNU General Public License as published by
  15. the Free Software Foundation; either version 2, or (at your option)
  16. any later version.
  17.  
  18. Bison is distributed in the hope that it will be useful,
  19. but WITHOUT ANY WARRANTY; without even the implied warranty of
  20. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21. GNU General Public License for more details.
  22.  
  23. You should have received a copy of the GNU General Public License
  24. along with Bison; see the file COPYING.  If not, write to
  25. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  26.  
  27.  
  28. #include <stdio.h>
  29. #include "system.h"
  30. #include "machine.h"
  31.  
  32. #ifdef macintosh
  33. #pragma segment bison
  34. #endif
  35.  
  36.  
  37. /* given n by n matrix of bits R, modify its contents
  38.    to be the transive closure of what was given.  */
  39.  
  40. void
  41. TC(R, n)
  42. unsigned *R;
  43. int n;
  44. {
  45.   register int rowsize;
  46.   register unsigned mask;
  47.   register unsigned *rowj;
  48.   register unsigned *rp;
  49.   register unsigned *rend;
  50.   register unsigned *ccol;
  51.  
  52.   unsigned *relend;
  53.   unsigned *cword;
  54.   unsigned *rowi;
  55.  
  56.   rowsize = WORDSIZE(n) * sizeof(unsigned);
  57.   relend = (unsigned *) ((char *) R + (n * rowsize));
  58.  
  59.   cword = R;
  60.   mask = 1;
  61.   rowi = R;
  62.   while (rowi < relend)
  63.     {
  64.       ccol = cword;
  65.       rowj = R;
  66.  
  67.       while (rowj < relend)
  68.     {
  69.       if (*ccol & mask)
  70.         {
  71.           rp = rowi;
  72.           rend = (unsigned *) ((char *) rowj + rowsize);
  73.  
  74.           while (rowj < rend)
  75.         *rowj++ |= *rp++;
  76.         }
  77.       else
  78.         {
  79.           rowj = (unsigned *) ((char *) rowj + rowsize);
  80.         }
  81.  
  82.       ccol = (unsigned *) ((char *) ccol + rowsize);
  83.     }
  84.  
  85.       mask <<= 1;
  86.       if (mask == 0)
  87.     {
  88.       mask = 1;
  89.       cword++;
  90.     }
  91.  
  92.       rowi = (unsigned *) ((char *) rowi + rowsize);
  93.     }
  94. }
  95.  
  96.  
  97. /* Reflexive Transitive Closure.  Same as TC
  98.    and then set all the bits on the diagonal of R.  */
  99.  
  100. void
  101. RTC(R, n)
  102. unsigned *R;
  103. int n;
  104. {
  105.   register int rowsize;
  106.   register unsigned mask;
  107.   register unsigned *rp;
  108.   register unsigned *relend;
  109.  
  110.   TC(R, n);
  111.  
  112.   rowsize = WORDSIZE(n) * sizeof(unsigned);
  113.   relend = (unsigned *) ((char *) R + n*rowsize);
  114.  
  115.   mask = 1;
  116.   rp = R;
  117.   while (rp < relend)
  118.     {
  119.       *rp |= mask;
  120.  
  121.       mask <<= 1;
  122.       if (mask == 0)
  123.     {
  124.       mask = 1;
  125.       rp++;
  126.     }
  127.  
  128.       rp = (unsigned *) ((char *) rp + rowsize);
  129.     }
  130. }
  131.