/* 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 */