aboutsummaryrefslogtreecommitdiff
path: root/pies/depmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'pies/depmap.c')
-rw-r--r--pies/depmap.c170
1 files changed, 170 insertions, 0 deletions
diff --git a/pies/depmap.c b/pies/depmap.c
new file mode 100644
index 0000000..76b492f
--- /dev/null
+++ b/pies/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 */

Return to:

Send suggestions and report system problems to the System administrator.