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