diff options
Diffstat (limited to 'src/depmap.c')
-rw-r--r-- | src/depmap.c | 118 |
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); +} + |