diff options
Diffstat (limited to 'src/depmap.c')
-rw-r--r-- | src/depmap.c | 170 |
1 files changed, 170 insertions, 0 deletions
diff --git a/src/depmap.c b/src/depmap.c new file mode 100644 index 0000000..76b492f --- /dev/null +++ b/src/depmap.c @@ -0,0 +1,170 @@ +/* This file is part of Mailfromd. + Copyright (C) 2008 Sergey Poznyakoff + + This program 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 of the License, or (at your + option) any later version. + + This program 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 this program. If not, see <http://www.gnu.org/licenses/>. */ + +#include "pies.h" + +#ifndef CHAR_BIT +# define CHAR_BIT 8 +#endif +#define BITS_PER_WORD (sizeof(unsigned)*CHAR_BIT) +#define MAXTABLE 32767 + +#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) + +void +TC (unsigned *R, int n) +{ + register int 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 pies_depmap +{ + unsigned nrows; + unsigned rowlen; + unsigned r[1]; +}; + +pies_depmap_t +depmap_alloc (unsigned count) +{ + size_t size = (count + BITS_PER_WORD - 1) / BITS_PER_WORD; + pies_depmap_t dmap = xzalloc (sizeof (*dmap) - 1 + + count * size * sizeof (unsigned)); + dmap->nrows = count; + dmap->rowlen = size; + return dmap; +} + +pies_depmap_t +depmap_copy (pies_depmap_t dpm) +{ + pies_depmap_t copy = depmap_alloc (dpm->nrows); + memcpy (copy->r, dpm->r, dpm->nrows * dpm->rowlen * sizeof (unsigned)); + return copy; +} + +static unsigned * +depmap_rowptr (pies_depmap_t dmap, unsigned row) +{ + return dmap->r + dmap->rowlen * row; +} + +void +depmap_set (pies_depmap_t dmap, unsigned row, unsigned col) +{ + unsigned *rptr = depmap_rowptr (dmap, row); + SETBIT (rptr, col); +} + +int +depmap_isset (pies_depmap_t dmap, unsigned row, unsigned col) +{ + unsigned *rptr = depmap_rowptr (dmap, row); + return BITISSET (rptr, col); +} + +void +depmap_tc (pies_depmap_t dmap) +{ + TC (dmap->r, dmap->nrows); +} + +struct pies_depmap_pos +{ + enum pies_depmap_direction dir; + unsigned coord[2]; +}; + +unsigned +depmap_next (pies_depmap_t dmap, pies_depmap_pos_t pos) +{ + for (pos->coord[pos->dir]++; pos->coord[pos->dir] < dmap->nrows; + pos->coord[pos->dir]++) + if (depmap_isset (dmap, pos->coord[0], pos->coord[1])) + break; + + return pos->coord[pos->dir] == dmap->nrows ? + (unsigned) -1 : pos->coord[pos->dir]; +} + +unsigned +depmap_first (pies_depmap_t dmap, enum pies_depmap_direction dir, + unsigned coord, pies_depmap_pos_t *ppos) +{ + pies_depmap_pos_t pos = xmalloc (sizeof *pos); + *ppos = pos; + pos->dir = dir; + pos->coord[!pos->dir] = coord; + pos->coord[pos->dir] = -1; + return depmap_next (dmap, pos); +} + +/* + Local Variables: + c-file-style: "gnu" + End: +*/ +/* EOF */ |