GRASS Programmer's Manual
6.4.2(2012)
|
00001 /* 00002 ** Bitmap library 00003 ** 00004 ** Written by David Gerdes 12 November 1992 00005 ** US Army Construction Engineering Research Laboratories 00006 ** 00007 ** 00008 ** This library provides basic support for the creation and manipulation 00009 ** of two dimensional bitmap arrays. 00010 ** 00011 ** BM_create (x, y) Create bitmap of specified dimensions 00012 ** 00013 ** BM_destroy (map) Destroy bitmap and free memory 00014 ** 00015 ** BM_set (map, x, y, val) Set array position to val [TRUE/FALSE] 00016 ** 00017 ** BM_get (map, x, y) Return value at array position 00018 */ 00019 00020 #include <stdio.h> 00021 #include <stdlib.h> 00022 #include <grass/linkm.h> 00023 #include <grass/bitmap.h> 00024 00025 00026 #define BM_col_to_byte(x) ((x)/8) 00027 #define BM_col_to_bit(x) ((x)%8) 00028 00029 static int depth; 00030 00031 00044 struct BM *BM_create_sparse(int x, int y) 00045 { 00046 struct BM *map; 00047 int i; 00048 00049 if (NULL == (map = (struct BM *)malloc(sizeof(struct BM)))) 00050 return (NULL); 00051 map->bytes = (x + 7) / 8; 00052 00053 if (NULL == (map->data = (unsigned char *) 00054 malloc(sizeof(struct BMlink *) * y))) 00055 return (NULL); 00056 00057 map->rows = y; 00058 map->cols = x; 00059 map->sparse = 1; 00060 00061 link_set_chunk_size(500); 00062 map->token = link_init(sizeof(struct BMlink)); 00063 00064 for (i = 0; i < map->rows; i++) { 00065 ((struct BMlink **)(map->data))[i] = 00066 (struct BMlink *)link_new(map->token); 00067 ((struct BMlink **)(map->data))[i]->count = x; 00068 ((struct BMlink **)(map->data))[i]->val = 0; 00069 ((struct BMlink **)(map->data))[i]->next = NULL; 00070 } 00071 00072 00073 depth++; 00074 00075 return map; 00076 } 00077 00078 00090 int BM_destroy_sparse(struct BM *map) 00091 { 00092 int i; 00093 struct BMlink *p, *tmp; 00094 00095 for (i = 0; i < map->rows; i++) { 00096 p = ((struct BMlink **)(map->data))[i]; 00097 while (p != NULL) { 00098 tmp = p->next; 00099 link_dispose(map->token, (VOID_T *) p); 00100 p = tmp; 00101 } 00102 } 00103 00104 if (--depth == 0) 00105 link_cleanup(map->token); 00106 00107 free(map->data); 00108 free(map); 00109 00110 return 0; 00111 } 00112 00113 00128 int BM_set_sparse(struct BM *map, int x, int y, int val) 00129 { 00130 struct BMlink *p, *p2, *prev; 00131 int cur_x = 0; 00132 int Tcount, Tval; 00133 int dist_a, dist_b; 00134 00135 val = !(!val); /* set val == 1 or 0 */ 00136 00137 p = ((struct BMlink **)(map->data))[y]; 00138 prev = NULL; 00139 while (p != NULL) { 00140 if (cur_x + p->count > x) { 00141 if (p->val == val) /* no change */ 00142 return 0; 00143 00144 Tcount = p->count; /* save current state */ 00145 Tval = p->val; 00146 00147 /* if x is on edge, then we probably want to merge it with 00148 ** its neighbor for efficiency 00149 */ 00150 00151 /* dist_a is how far x is from Left edge of group */ 00152 /* dist_b is how far x is from right edge of group */ 00153 00154 dist_a = x - cur_x; 00155 dist_b = (cur_x + p->count - 1) - x; 00156 00157 /* if on both edges, then we should be able to merge 3 into one */ 00158 if (dist_b == 0 && p->next && p->next->val == val) { 00159 if (dist_a == 0 && x > 0) { 00160 if (prev != NULL && prev->val == val) { 00161 prev->count += p->next->count + 1; 00162 prev->next = p->next->next; 00163 link_dispose(map->token, (VOID_T *) p->next); 00164 link_dispose(map->token, (VOID_T *) p); 00165 return 0; 00166 } 00167 } 00168 } 00169 00170 /* handle right edge merge */ 00171 if (dist_b == 0 && p->next && p->next->val == val) { 00172 p->count--; 00173 p->next->count++; 00174 if (p->count == 0) { 00175 if (prev) { 00176 prev->next = p->next; 00177 } 00178 else { 00179 ((struct BMlink **)(map->data))[y] = p->next; 00180 } 00181 link_dispose(map->token, (VOID_T *) p); 00182 } 00183 return 0; 00184 } 00185 00186 /* handle left edge merge */ 00187 if (dist_a == 0 && x > 0) { 00188 00189 if (prev != NULL && prev->val == val) { 00190 prev->count++; 00191 p->count--; 00192 if (p->count == 0) { 00193 prev->next = p->next; 00194 link_dispose(map->token, (VOID_T *) p); 00195 } 00196 return 0; 00197 } 00198 } 00199 00200 /* if not on edge, have to add link for each side */ 00201 if (dist_a > 0) { 00202 p->count = dist_a; 00203 p->val = Tval; 00204 p2 = (struct BMlink *)link_new(map->token); 00205 p2->next = p->next; 00206 p->next = p2; 00207 p = p2; 00208 } 00209 p->count = 1; 00210 p->val = val; 00211 00212 if (dist_b > 0) { 00213 p2 = (struct BMlink *)link_new(map->token); 00214 p2->count = dist_b; 00215 p2->val = Tval; 00216 00217 p2->next = p->next; 00218 p->next = p2; 00219 } 00220 00221 return 0; 00222 00223 } 00224 cur_x += p->count; 00225 prev = p; 00226 p = p->next; 00227 } 00228 00229 return 0; 00230 } 00231 00232 00246 int BM_get_sparse(struct BM *map, int x, int y) 00247 { 00248 struct BMlink *p; 00249 int cur_x = 0; 00250 00251 p = ((struct BMlink **)(map->data))[y]; 00252 while (p != NULL) { 00253 if (cur_x + p->count > x) 00254 return (p->val); 00255 cur_x += p->count; 00256 p = p->next; 00257 } 00258 00259 return -1; 00260 } 00261 00262 00272 int BM_get_map_size_sparse(struct BM *map) 00273 { 00274 int i; 00275 int size; 00276 struct BMlink *p; 00277 00278 size = map->rows * sizeof(struct BMlink *); 00279 for (i = 0; i < map->rows; i++) { 00280 p = ((struct BMlink **)(map->data))[i]; 00281 while (p != NULL) { 00282 size += sizeof(struct BMlink); 00283 p = p->next; 00284 } 00285 } 00286 00287 return size; 00288 } 00289 00290 00302 int BM_dump_map_sparse(struct BM *map) 00303 { 00304 int i; 00305 struct BMlink *p; 00306 00307 for (i = 0; i < map->rows; i++) { 00308 p = ((struct BMlink **)(map->data))[i]; 00309 while (p != NULL) { 00310 fprintf(stdout, "(%2d %2d) ", p->count, p->val); 00311 p = p->next; 00312 } 00313 fprintf(stdout, "\n"); 00314 } 00315 00316 return 0; 00317 } 00318 00319 00332 int BM_dump_map_row_sparse(struct BM *map, int y) 00333 { 00334 int i; 00335 struct BMlink *p; 00336 00337 i = y; 00338 { 00339 p = ((struct BMlink **)(map->data))[i]; 00340 while (p != NULL) { 00341 fprintf(stdout, "(%2d %2d) ", p->count, p->val); 00342 p = p->next; 00343 } 00344 fprintf(stdout, "\n"); 00345 } 00346 00347 return 0; 00348 } 00349 00350 00364 int BM_file_write_sparse(FILE * fp, struct BM *map) 00365 { 00366 char c; 00367 int i, y; 00368 struct BMlink *p; 00369 int cnt; 00370 00371 c = BM_MAGIC; 00372 fwrite(&c, sizeof(char), sizeof(char), fp); 00373 00374 fwrite(BM_TEXT, BM_TEXT_LEN, sizeof(char), fp); 00375 00376 c = BM_SPARSE; 00377 fwrite(&c, sizeof(char), sizeof(char), fp); 00378 00379 fwrite(&(map->rows), sizeof(map->rows), sizeof(char), fp); 00380 00381 fwrite(&(map->cols), sizeof(map->cols), sizeof(char), fp); 00382 00383 for (y = 0; y < map->rows; y++) { 00384 /* first count number of links */ 00385 p = ((struct BMlink **)(map->data))[y]; 00386 cnt = 0; 00387 while (p != NULL) { 00388 cnt++; 00389 p = p->next; 00390 } 00391 00392 i = cnt; 00393 fwrite(&i, sizeof(i), sizeof(char), fp); 00394 00395 00396 /* then write them out */ 00397 p = ((struct BMlink **)(map->data))[y]; 00398 while (p != NULL) { 00399 i = p->count; 00400 fwrite(&i, sizeof(i), sizeof(char), fp); 00401 00402 i = p->val; 00403 fwrite(&i, sizeof(i), sizeof(char), fp); 00404 00405 p = p->next; 00406 } 00407 } 00408 fflush(fp); 00409 00410 return 0; 00411 }