aboutsummaryrefslogtreecommitdiff
path: root/src/depmap.c
blob: 04e2584664411217a095dd2e6da72f3c2f947e8a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
/* This file is part of GNU Pies.
   Copyright (C) 2008, 2009, 2010 Sergey Poznyakoff

   GNU Pies 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 Pies 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 Pies.  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 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
{
  size_t nrows;
  size_t rowlen;
  unsigned r[1];
};
  
pies_depmap_t
depmap_alloc (size_t 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, size_t row)
{
  return dmap->r + dmap->rowlen * row;
}

void
depmap_set (pies_depmap_t dmap, size_t row, size_t col)
{
  unsigned *rptr = depmap_rowptr (dmap, row);
  SETBIT (rptr, col);
}

int
depmap_isset (pies_depmap_t dmap, size_t row, size_t 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;
  size_t coord[2];
};

size_t
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 ?
             (size_t) -1 : pos->coord[pos->dir];
}

size_t
depmap_first (pies_depmap_t dmap, enum pies_depmap_direction dir,
	      size_t 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);
}

Return to:

Send suggestions and report system problems to the System administrator.