GRASS GIS 7 Programmer's Manual  7.5.svn(2018)-r72846
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
sparse.c
Go to the documentation of this file.
1 /*
2  ** Bitmap library
3  **
4  ** Written by David Gerdes 12 November 1992
5  ** US Army Construction Engineering Research Laboratories
6  **
7  **
8  ** This library provides basic support for the creation and manipulation
9  ** of two dimensional bitmap arrays.
10  **
11  ** BM_create (x, y) Create bitmap of specified dimensions
12  **
13  ** BM_destroy (map) Destroy bitmap and free memory
14  **
15  ** BM_set (map, x, y, val) Set array position to val [TRUE/FALSE]
16  **
17  ** BM_get (map, x, y) Return value at array position
18  */
19 
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include <grass/linkm.h>
23 #include <grass/bitmap.h>
24 
25 
26 #define BM_col_to_byte(x) ((x) >> 3) /* x / 8 */
27 #define BM_col_to_bit(x) ((x) & 7) /* x % 8 */
28 
29 static int depth;
30 
31 
32 /*!
33  * \brief
34  *
35  * Create a sparse bitmap of dimension 'x'/'y'
36  *
37  * Returns bitmap structure or NULL on error
38  *
39  * \param x
40  * \param y
41  * \return struct BM
42  */
43 
44 struct BM *BM_create_sparse(int x, int y)
45 {
46  struct BM *map;
47  int i;
48 
49  if (NULL == (map = (struct BM *)malloc(sizeof(struct BM))))
50  return (NULL);
51  map->bytes = (x + 7) / 8;
52 
53  if (NULL == (map->data = (unsigned char *)
54  malloc(sizeof(struct BMlink *) * y)))
55  return (NULL);
56 
57  map->rows = y;
58  map->cols = x;
59  map->sparse = 1;
60 
62  map->token = link_init(sizeof(struct BMlink));
63 
64  for (i = 0; i < map->rows; i++) {
65  ((struct BMlink **)(map->data))[i] =
66  (struct BMlink *)link_new(map->token);
67  ((struct BMlink **)(map->data))[i]->count = x;
68  ((struct BMlink **)(map->data))[i]->val = 0;
69  ((struct BMlink **)(map->data))[i]->next = NULL;
70  }
71 
72 
73  depth++;
74 
75  return map;
76 }
77 
78 
79 /*!
80  * \brief
81  *
82  * Destroy sparse bitmap and free all associated memory
83  *
84  * Returns 0
85  *
86  * \param map
87  * \return int
88  */
89 
90 int BM_destroy_sparse(struct BM *map)
91 {
92  int i;
93  struct BMlink *p, *tmp;
94 
95  for (i = 0; i < map->rows; i++) {
96  p = ((struct BMlink **)(map->data))[i];
97  while (p != NULL) {
98  tmp = p->next;
99  link_dispose(map->token, (VOID_T *) p);
100  p = tmp;
101  }
102  }
103 
104  if (--depth == 0)
105  link_cleanup(map->token);
106 
107  free(map->data);
108  free(map);
109 
110  return 0;
111 }
112 
113 
114 /*!
115  * \brief
116  *
117  * Set sparse bitmap value to 'val' at location 'x'/'y'
118  *
119  * Returns 0
120  *
121  * \param map
122  * \param x
123  * \param y
124  * \param val
125  * \return int
126  */
127 
128 int BM_set_sparse(struct BM *map, int x, int y, int val)
129 {
130  struct BMlink *p, *p2, *prev;
131  int cur_x = 0;
132  int Tcount, Tval;
133  int dist_a, dist_b;
134 
135  val = !(!val); /* set val == 1 or 0 */
136 
137  p = ((struct BMlink **)(map->data))[y];
138  prev = NULL;
139  while (p != NULL) {
140  if (cur_x + p->count > x) {
141  if (p->val == val) /* no change */
142  return 0;
143 
144  Tcount = p->count; /* save current state */
145  Tval = p->val;
146 
147  /* if x is on edge, then we probably want to merge it with
148  ** its neighbor for efficiency
149  */
150 
151  /* dist_a is how far x is from Left edge of group */
152  /* dist_b is how far x is from right edge of group */
153 
154  dist_a = x - cur_x;
155  dist_b = (cur_x + p->count - 1) - x;
156 
157  /* if on both edges, then we should be able to merge 3 into one */
158  if (dist_b == 0 && p->next && p->next->val == val) {
159  if (dist_a == 0 && x > 0) {
160  if (prev != NULL && prev->val == val) {
161  prev->count += p->next->count + 1;
162  prev->next = p->next->next;
163  link_dispose(map->token, (VOID_T *) p->next);
164  link_dispose(map->token, (VOID_T *) p);
165  return 0;
166  }
167  }
168  }
169 
170  /* handle right edge merge */
171  if (dist_b == 0 && p->next && p->next->val == val) {
172  p->count--;
173  p->next->count++;
174  if (p->count == 0) {
175  if (prev) {
176  prev->next = p->next;
177  }
178  else {
179  ((struct BMlink **)(map->data))[y] = p->next;
180  }
181  link_dispose(map->token, (VOID_T *) p);
182  }
183  return 0;
184  }
185 
186  /* handle left edge merge */
187  if (dist_a == 0 && x > 0) {
188 
189  if (prev != NULL && prev->val == val) {
190  prev->count++;
191  p->count--;
192  if (p->count == 0) {
193  prev->next = p->next;
194  link_dispose(map->token, (VOID_T *) p);
195  }
196  return 0;
197  }
198  }
199 
200  /* if not on edge, have to add link for each side */
201  if (dist_a > 0) {
202  p->count = dist_a;
203  p->val = Tval;
204  p2 = (struct BMlink *)link_new(map->token);
205  p2->next = p->next;
206  p->next = p2;
207  p = p2;
208  }
209  p->count = 1;
210  p->val = val;
211 
212  if (dist_b > 0) {
213  p2 = (struct BMlink *)link_new(map->token);
214  p2->count = dist_b;
215  p2->val = Tval;
216 
217  p2->next = p->next;
218  p->next = p2;
219  }
220 
221  return 0;
222 
223  }
224  cur_x += p->count;
225  prev = p;
226  p = p->next;
227  }
228 
229  return 0;
230 }
231 
232 
233 /*!
234  * \brief
235  *
236  * Returns sparse bitmap value at location 'x'/'y'
237  *
238  * Returns value or -1 on error
239  *
240  * \param map
241  * \param x
242  * \param y
243  * \return int
244  */
245 
246 int BM_get_sparse(struct BM *map, int x, int y)
247 {
248  struct BMlink *p;
249  int cur_x = 0;
250 
251  p = ((struct BMlink **)(map->data))[y];
252  while (p != NULL) {
253  if (cur_x + p->count > x)
254  return (p->val);
255  cur_x += p->count;
256  p = p->next;
257  }
258 
259  return -1;
260 }
261 
262 
263 /*!
264  * \brief
265  *
266  * Returns size of sparse bitmap in bytes
267  *
268  * \param map
269  * \return int
270  */
271 
272 size_t BM_get_map_size_sparse(struct BM *map)
273 {
274  int i;
275  size_t size;
276  struct BMlink *p;
277 
278  size = (size_t) map->rows * sizeof(struct BMlink *);
279  for (i = 0; i < map->rows; i++) {
280  p = ((struct BMlink **)(map->data))[i];
281  while (p != NULL) {
282  size += sizeof(struct BMlink);
283  p = p->next;
284  }
285  }
286 
287  return size;
288 }
289 
290 
291 /*!
292  * \brief
293  *
294  * Debugging code to dump out structure of links
295  *
296  * Returns 0
297  *
298  * \param map
299  * \return int
300  */
301 
302 int BM_dump_map_sparse(struct BM *map)
303 {
304  int i;
305  struct BMlink *p;
306 
307  for (i = 0; i < map->rows; i++) {
308  p = ((struct BMlink **)(map->data))[i];
309  while (p != NULL) {
310  fprintf(stdout, "(%2d %2d) ", p->count, p->val);
311  p = p->next;
312  }
313  fprintf(stdout, "\n");
314  }
315 
316  return 0;
317 }
318 
319 
320 /*!
321  * \brief
322  *
323  * Debugging code to dump out structure of links for single row
324  *
325  * Returns 0
326  *
327  * \param map
328  * \param y
329  * \return int
330  */
331 
332 int BM_dump_map_row_sparse(struct BM *map, int y)
333 {
334  int i;
335  struct BMlink *p;
336 
337  i = y;
338  {
339  p = ((struct BMlink **)(map->data))[i];
340  while (p != NULL) {
341  fprintf(stdout, "(%2d %2d) ", p->count, p->val);
342  p = p->next;
343  }
344  fprintf(stdout, "\n");
345  }
346 
347  return 0;
348 }
349 
350 
351 /*!
352  * \brief
353  *
354  * Write sparse bitmap matrix out to disk file 'fp'.
355  * NOTE: 'fp' must already be opened and later closed by user
356  *
357  * Returns 0 on success or -1 on error
358  *
359  * \param fp
360  * \param map
361  * \return int
362  */
363 
364 int BM_file_write_sparse(FILE * fp, struct BM *map)
365 {
366  char c;
367  int i, y;
368  struct BMlink *p;
369  int cnt;
370 
371  c = BM_MAGIC;
372  fwrite(&c, sizeof(char), sizeof(char), fp);
373 
374  fwrite(BM_TEXT, BM_TEXT_LEN, sizeof(char), fp);
375 
376  c = BM_SPARSE;
377  fwrite(&c, sizeof(char), sizeof(char), fp);
378 
379  fwrite(&(map->rows), sizeof(map->rows), sizeof(char), fp);
380 
381  fwrite(&(map->cols), sizeof(map->cols), sizeof(char), fp);
382 
383  for (y = 0; y < map->rows; y++) {
384  /* first count number of links */
385  p = ((struct BMlink **)(map->data))[y];
386  cnt = 0;
387  while (p != NULL) {
388  cnt++;
389  p = p->next;
390  }
391 
392  i = cnt;
393  fwrite(&i, sizeof(i), sizeof(char), fp);
394 
395 
396  /* then write them out */
397  p = ((struct BMlink **)(map->data))[y];
398  while (p != NULL) {
399  i = p->count;
400  fwrite(&i, sizeof(i), sizeof(char), fp);
401 
402  i = p->val;
403  fwrite(&i, sizeof(i), sizeof(char), fp);
404 
405  p = p->next;
406  }
407  }
408  fflush(fp);
409 
410  return 0;
411 }
#define VOID_T
Definition: linkm.h:8
VOID_T * link_new(struct link_head *Head)
Definition: new.c:12
struct link_head * link_init(int size)
Definition: linkm/init.c:40
double cur_x
Definition: driver/init.c:32
int count
Definition: bitmap.h:17
int rows
Definition: bitmap.h:19
unsigned char * data
Definition: bitmap.h:22
void free(void *)
#define NULL
Definition: ccmath.h:32
#define x
int sparse
Definition: bitmap.h:23
void link_cleanup(struct link_head *Head)
Definition: linkm/init.c:64
void * malloc(YYSIZE_T)
#define BM_SPARSE
Definition: bitmap.h:11
#define BM_MAGIC
Definition: bitmap.h:4
struct BM * BM_create_sparse(int x, int y)
Create a sparse bitmap of dimension &#39;x&#39;/&#39;y&#39;.
Definition: sparse.c:44
void link_set_chunk_size(int size)
Definition: linkm/init.c:30
#define BM_TEXT_LEN
Definition: bitmap.h:7
size_t BM_get_map_size_sparse(struct BM *map)
Returns size of sparse bitmap in bytes.
Definition: sparse.c:272
int BM_dump_map_row_sparse(struct BM *map, int y)
Debugging code to dump out structure of links for single row.
Definition: sparse.c:332
int BM_file_write_sparse(FILE *fp, struct BM *map)
Write sparse bitmap matrix out to disk file &#39;fp&#39;. NOTE: &#39;fp&#39; must already be opened and later closed ...
Definition: sparse.c:364
void link_dispose(struct link_head *Head, VOID_T *ptr)
Definition: dispose.c:10
size_t bytes
Definition: bitmap.h:21
int cols
Definition: bitmap.h:20
int BM_get_sparse(struct BM *map, int x, int y)
Returns sparse bitmap value at location &#39;x&#39;/&#39;y&#39;.
Definition: sparse.c:246
int BM_destroy_sparse(struct BM *map)
Destroy sparse bitmap and free all associated memory.
Definition: sparse.c:90
struct link_head * token
Definition: bitmap.h:25
int BM_dump_map_sparse(struct BM *map)
Debugging code to dump out structure of links.
Definition: sparse.c:302
#define BM_TEXT
Definition: bitmap.h:6
int BM_set_sparse(struct BM *map, int x, int y, int val)
Set sparse bitmap value to &#39;val&#39; at location &#39;x&#39;/&#39;y&#39;.
Definition: sparse.c:128