GRASS GIS 8 Programmer's Manual 8.2.1RC1(2022)-exported
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
29static 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
44struct 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
93int 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
131int 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
248int 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
274size_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
304int 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
334int 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
366int 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 NULL
Definition: ccmath.h:32
void link_dispose(struct link_head *Head, VOID_T *ptr)
Definition: dispose.c:10
double cur_x
Definition: driver/init.c:32
int count
void link_cleanup(struct link_head *Head)
Definition: linkm/init.c:64
void link_set_chunk_size(int size)
Definition: linkm/init.c:30
struct link_head * link_init(int size)
Definition: linkm/init.c:40
VOID_T * link_new(struct link_head *Head)
Definition: new.c:12
#define VOID_T
Definition: qtree.h:29
struct BM * BM_create_sparse(int x, int y)
Create a sparse bitmap of dimension 'x'/'y'.
Definition: sparse.c:44
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
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:366
int BM_get_sparse(struct BM *map, int x, int y)
Returns sparse bitmap value at location 'x'/'y'.
Definition: sparse.c:248
size_t BM_get_map_size_sparse(struct BM *map)
Returns size of sparse bitmap in bytes.
Definition: sparse.c:274
int BM_destroy_sparse(struct BM *map)
Destroy sparse bitmap and free all associated memory.
Definition: sparse.c:93
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:131
int BM_dump_map_sparse(struct BM *map)
Debugging code to dump out structure of links.
Definition: sparse.c:304
#define x