1 files changed, 118 insertions, 0 deletions

diff --git a/src/depmap.c b/src/depmap.c
new file mode 100644
index 0000000..340d41f
--- /dev/null
+++ b/src/depmap.c
@@ -0,0 +1,118 @@
+/* This file is part of GNU cflow.
+   Copyright (C) 2008, 2009 Sergey Poznyakoff
+
+   GNU cflow is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3, or (at your option)
+   any later version.
+
+   GNU cflow is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with GNU cflow.  If not, see <http://www.gnu.org/licenses/>. */
+
+#include <cflow.h>
+
+#ifndef CHAR_BIT
+# define CHAR_BIT 8
+#endif
+#define BITS_PER_WORD   (sizeof(unsigned)*CHAR_BIT)
+
+#define WORDSIZE(n)     (((n) + BITS_PER_WORD - 1) / BITS_PER_WORD)
+#define SETBIT(x, i)    ((x)[(i)/BITS_PER_WORD] |= (1<<((i) % BITS_PER_WORD)))
+#define RESETBIT(x, i)  ((x)[(i)/BITS_PER_WORD] &= ~(1<<((i) % BITS_PER_WORD)))
+#define BITISSET(x, i)  (((x)[(i)/BITS_PER_WORD] & (1<<((i) % BITS_PER_WORD))) != 0)
+
+static void
+transitive_closure(unsigned *R, int n)
+{
+     register size_t rowsize;
+     register unsigned mask;
+     register unsigned *rowj;
+     register unsigned *rp;
+     register unsigned *rend;
+     register unsigned *ccol;
+     
+     unsigned *relend;
+     unsigned *cword;
+     unsigned *rowi;
+     
+     rowsize = WORDSIZE (n) * sizeof (unsigned);
+     relend = (unsigned *) ((char *) R + (n * rowsize));
+     
+     cword = R;
+     mask = 1;
+     rowi = R;
+     while (rowi < relend) {
+          ccol = cword;
+          rowj = R;
+                
+          while (rowj < relend) {
+               if (*ccol & mask) {
+                    rp = rowi;
+                    rend = (unsigned *) ((char *) rowj + rowsize);
+                                
+                    while (rowj < rend)
+                         *rowj++ |= *rp++;
+               } else {
+                    rowj = (unsigned *) ((char *) rowj + rowsize);
+               }
+          
+               ccol = (unsigned *) ((char *) ccol + rowsize);
+          }
+                
+          mask <<= 1;
+          if (mask == 0) {
+               mask = 1;
+               cword++;
+          }
+          rowi = (unsigned *) ((char *) rowi + rowsize);
+     }
+}
+
+struct cflow_depmap {
+     size_t nrows;
+     size_t rowlen;
+     unsigned r[1];
+};
+  
+cflow_depmap_t
+depmap_alloc(size_t count)
+{
+     size_t size = (count + BITS_PER_WORD - 1) / BITS_PER_WORD;
+     cflow_depmap_t dmap = xzalloc(sizeof(*dmap) - 1 
+                                   + count * size * sizeof(unsigned));
+     dmap->nrows  = count;
+     dmap->rowlen = size;
+     return dmap;
+}
+
+static unsigned *
+depmap_rowptr(cflow_depmap_t dmap, size_t row)
+{
+     return dmap->r + dmap->rowlen * row;
+}
+
+void
+depmap_set(cflow_depmap_t dmap, size_t row, size_t col)
+{
+     unsigned *rptr = depmap_rowptr(dmap, row);
+     SETBIT(rptr, col);
+}
+
+int
+depmap_isset(cflow_depmap_t dmap, size_t row, size_t col)
+{
+     unsigned *rptr = depmap_rowptr(dmap, row);
+     return BITISSET(rptr, col);
+}
+
+void
+depmap_tc(cflow_depmap_t dmap)
+{
+     transitive_closure(dmap->r, dmap->nrows);
+}
+