GRASS Programmer's Manual  6.4.2(2012)
sparse.c
Go to the documentation of this file.
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 }
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines