GRASS Programmer's Manual  6.5.svn(2014)-r66266
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator 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)/8)
27 #define BM_col_to_bit(x) ((x)%8)
28 
29 static int depth;
30 
31 
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 
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 
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 
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 
272 int BM_get_map_size_sparse(struct BM *map)
273 {
274  int i;
275  int size;
276  struct BMlink *p;
277 
278  size = 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 
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 
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 
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: qtree.h:17
struct link_head * link_init(int size)
Definition: linkm/init.c:40
struct link_head * link_new(struct link_head *Head)
Definition: new.c:12
int count
int y
Definition: plot.c:34
void link_cleanup(struct link_head *Head)
Definition: linkm/init.c:64
tuple size
value.Bind(wx.EVT_TEXT, self.OnVolumeIsosurfMap)
Definition: tools.py:2334
void * malloc(YYSIZE_T)
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
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
int cur_x
Definition: driver/init.c:37
return NULL
Definition: dbfopen.c:1394
int BM_get_map_size_sparse(struct BM *map)
Returns size of sparse bitmap in bytes.
Definition: sparse.c:272
void free(void *)
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
int BM_dump_map_sparse(struct BM *map)
Debugging code to dump out structure of links.
Definition: sparse.c:302
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