GRASS GIS 8 Programmer's Manual 8.4.1(2025)-45ca3179ab
Loading...
Searching...
No Matches
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
28static 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
42struct 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
88int 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
125int 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
240int 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
265size_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
294int 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
323int 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
354int 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 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:67
void link_set_chunk_size(int size)
Definition linkm/init.c:32
struct link_head * link_init(int size)
Definition linkm/init.c:42
VOID_T * link_new(struct link_head *Head)
Definition new.c:12
#define VOID_T
Definition qtree.h:28
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
#define x