summaryrefslogtreecommitdiffabout
path: root/src/depmap.c
Side-by-side diff
Diffstat (limited to 'src/depmap.c') (more/less context) (ignore whitespace changes)
-rw-r--r--src/depmap.c118
1 files changed, 118 insertions, 0 deletions
diff --git a/src/depmap.c b/src/depmap.c
new file mode 100644
index 0000000..340d41f
--- a/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);
+}
+

Return to:

Send suggestions and report system problems to the System administrator.