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