l4/pkg/ocaml/ocaml/contrib/yacc/warshall.c

   1 /***********************************************************************/
   2 /*                                                                     */
   3 /*                           Objective Caml                            */
   4 /*                                                                     */
   5 /*            Xavier Leroy, projet Cristal, INRIA Rocquencourt         */
   6 /*                                                                     */
   7 /*  Copyright 1996 Institut National de Recherche en Informatique et   */
   8 /*  en Automatique.  All rights reserved.  This file is distributed    */
   9 /*  under the terms of the Q Public License version 1.0.               */
  10 /*                                                                     */
  11 /***********************************************************************/
  12
  13 /* Based on public-domain code from Berkeley Yacc */
  14
  15 /* $Id: warshall.c 3573 2001-07-12 12:54:24Z doligez $ */
  16
  17 #include "defs.h"
  18
  19 void transitive_closure(unsigned int *R, int n)
  20 {
  21     register int rowsize;
  22     register unsigned mask;
  23     register unsigned *rowj;
  24     register unsigned *rp;
  25     register unsigned *rend;
  26     register unsigned *ccol;
  27     register unsigned *relend;
  28     register unsigned *cword;
  29     register unsigned *rowi;
  30
  31     rowsize = WORDSIZE(n);
  32     relend = R + n*rowsize;
  33
  34     cword = R;
  35     mask = 1;
  36     rowi = R;
  37     while (rowi < relend)
  38     {
  39         ccol = cword;
  40         rowj = R;
  41
  42         while (rowj < relend)
  43         {
  44             if (*ccol & mask)
  45             {
  46                 rp = rowi;
  47                 rend = rowj + rowsize;
  48                 while (rowj < rend)
  49                     *rowj++ |= *rp++;
  50             }
  51             else
  52             {
  53                 rowj += rowsize;
  54             }
  55
  56             ccol += rowsize;
  57         }
  58
  59         mask <<= 1;
  60         if (mask == 0)
  61         {
  62             mask = 1;
  63             cword++;
  64         }
  65
  66         rowi += rowsize;
  67     }
  68 }
  69
  70 void reflexive_transitive_closure(unsigned int *R, int n)
  71 {
  72     register int rowsize;
  73     register unsigned mask;
  74     register unsigned *rp;
  75     register unsigned *relend;
  76
  77     transitive_closure(R, n);
  78
  79     rowsize = WORDSIZE(n);
  80     relend = R + n*rowsize;
  81
  82     mask = 1;
  83     rp = R;
  84     while (rp < relend)
  85     {
  86         *rp |= mask;
  87         mask <<= 1;
  88         if (mask == 0)
  89         {
  90             mask = 1;
  91             rp++;
  92         }
  93
  94         rp += rowsize;
  95     }
  96 }