sparse.c

Go to the documentation of this file.

/*
 **  Bitmap library
 **
 **  Written by David Gerdes     12 November 1992
 **  US Army Construction Engineering Research Laboratories
 **
 **
 **  This library provides basic support for the creation and manipulation
 **  of two dimensional bitmap arrays.
 **
 **   BM_create (x, y)                  Create bitmap of specified dimensions
 **
 **   BM_destroy (map)                  Destroy bitmap and free memory
 **
 **   BM_set (map, x, y, val)           Set array position to val [TRUE/FALSE]
 **
 **   BM_get (map, x, y)                        Return value at array position
 */

#include <stdio.h>
#include <stdlib.h>
#include <grass/linkm.h>
#include <grass/bitmap.h>


#define BM_col_to_byte(x)  ((x) >> 3)  /* x / 8 */
#define BM_col_to_bit(x)   ((x) & 7)   /* x % 8 */

static int depth;


/*!
 * \brief
 *
 * Create a sparse bitmap of dimension 'x'/'y'
 *
 * Returns bitmap structure or NULL on error
 *
 *  \param x
 *  \param y
 *  \return struct BM 
 */

struct BM *BM_create_sparse(int x, int y)
{
    struct BM *map;
    int i;

    if (NULL == (map = (struct BM *)malloc(sizeof(struct BM))))
        return (NULL);
    map->bytes = (x + 7) / 8;

    if (NULL == (map->data = (unsigned char *)
                 malloc(sizeof(struct BMlink *) * y))) 
    {
        free(map);
        return (NULL);
    }

    map->rows = y;
    map->cols = x;
    map->sparse = 1;

    link_set_chunk_size(500);
    map->token = link_init(sizeof(struct BMlink));

    for (i = 0; i < map->rows; i++) {
        ((struct BMlink **)(map->data))[i] =
            (struct BMlink *)link_new(map->token);
        ((struct BMlink **)(map->data))[i]->count = x;
        ((struct BMlink **)(map->data))[i]->val = 0;
        ((struct BMlink **)(map->data))[i]->next = NULL;
    }


    depth++;

    return map;
}


/*!
 * \brief
 *
 * Destroy sparse bitmap and free all associated memory
 *
 * Returns 0
 *
 *  \param map
 *  \return int
 */

int BM_destroy_sparse(struct BM *map)
{
    int i;
    struct BMlink *p, *tmp;

    for (i = 0; i < map->rows; i++) {
        p = ((struct BMlink **)(map->data))[i];
        while (p != NULL) {
            tmp = p->next;
            link_dispose(map->token, (VOID_T *) p);
            p = tmp;
        }
    }

    if (--depth == 0)
        link_cleanup(map->token);

    free(map->data);
    free(map);

    return 0;
}


/*!
 * \brief
 *
 * Set sparse bitmap value to 'val' at location 'x'/'y'
 *
 * Returns 0
 *
 *  \param map
 *  \param x
 *  \param y
 *  \param val
 *  \return int
 */

int BM_set_sparse(struct BM *map, int x, int y, int val)
{
    struct BMlink *p, *p2, *prev;
    int cur_x = 0;
    int Tval;
    int dist_a, dist_b;

    val = !(!val);              /* set val == 1 or 0 */

    p = ((struct BMlink **)(map->data))[y];
    prev = NULL;
    while (p != NULL) {
        if (cur_x + p->count > x) {
            if (p->val == val)  /* no change */
                return 0;

            Tval = p->val;

            /* if x is on edge, then we probably want to merge it with 
             ** its neighbor for efficiency 
             */

            /* dist_a is how far x is from Left  edge of group */
            /* dist_b is how far x is from right edge of group */

            dist_a = x - cur_x;
            dist_b = (cur_x + p->count - 1) - x;

            /* if on both edges, then we should be able to  merge 3 into one */
            if (dist_b == 0 && p->next && p->next->val == val) {
                if (dist_a == 0 && x > 0) {
                    if (prev != NULL && prev->val == val) {
                        prev->count += p->next->count + 1;
                        prev->next = p->next->next;
                        link_dispose(map->token, (VOID_T *) p->next);
                        link_dispose(map->token, (VOID_T *) p);
                        return 0;
                    }
                }
            }

            /* handle right edge merge */
            if (dist_b == 0 && p->next && p->next->val == val) {
                p->count--;
                p->next->count++;
                if (p->count == 0) {
                    if (prev) {
                        prev->next = p->next;
                    }
                    else {
                        ((struct BMlink **)(map->data))[y] = p->next;
                    }
                    link_dispose(map->token, (VOID_T *) p);
                }
                return 0;
            }

            /* handle left edge merge */
            if (dist_a == 0 && x > 0) {

                if (prev != NULL && prev->val == val) {
                    prev->count++;
                    p->count--;
                    if (p->count == 0) {
                        prev->next = p->next;
                        link_dispose(map->token, (VOID_T *) p);
                    }
                    return 0;
                }
            }

            /* if not on edge, have to add link for each side */
            if (dist_a > 0) {
                p->count = dist_a;
                p->val = Tval;
                p2 = (struct BMlink *)link_new(map->token);
                p2->next = p->next;
                p->next = p2;
                p = p2;
            }
            p->count = 1;
            p->val = val;

            if (dist_b > 0) {
                p2 = (struct BMlink *)link_new(map->token);
                p2->count = dist_b;
                p2->val = Tval;

                p2->next = p->next;
                p->next = p2;
            }

            return 0;

        }
        cur_x += p->count;
        prev = p;
        p = p->next;
    }

    return 0;
}


/*!
 * \brief
 *
 * Returns sparse bitmap value at location 'x'/'y'
 *
 * Returns value or -1 on error
 *
 *  \param map
 *  \param x
 *  \param y
 *  \return int
 */

int BM_get_sparse(struct BM *map, int x, int y)
{
    struct BMlink *p;
    int cur_x = 0;

    p = ((struct BMlink **)(map->data))[y];
    while (p != NULL) {
        if (cur_x + p->count > x)
            return (p->val);
        cur_x += p->count;
        p = p->next;
    }

    return -1;
}


/*!
 * \brief
 *
 * Returns size of sparse bitmap in bytes
 *
 *  \param map
 *  \return int
 */

size_t BM_get_map_size_sparse(struct BM *map)
{
    int i;
    size_t size;
    struct BMlink *p;

    size = (size_t) map->rows * sizeof(struct BMlink *);
    for (i = 0; i < map->rows; i++) {
        p = ((struct BMlink **)(map->data))[i];
        while (p != NULL) {
            size += sizeof(struct BMlink);
            p = p->next;
        }
    }

    return size;
}


/*!
 * \brief
 *
 * Debugging code to dump out structure of links
 *
 * Returns 0
 *
 *  \param map
 *  \return int
 */

int BM_dump_map_sparse(struct BM *map)
{
    int i;
    struct BMlink *p;

    for (i = 0; i < map->rows; i++) {
        p = ((struct BMlink **)(map->data))[i];
        while (p != NULL) {
            fprintf(stdout, "(%2d %2d)  ", p->count, p->val);
            p = p->next;
        }
        fprintf(stdout, "\n");
    }

    return 0;
}


/*!
 * \brief
 *
 * Debugging code to dump out structure of links for single row
 *
 * Returns 0
 *
 *  \param map
 *  \param y
 *  \return int
 */

int BM_dump_map_row_sparse(struct BM *map, int y)
{
    int i;
    struct BMlink *p;

    i = y;
    {
        p = ((struct BMlink **)(map->data))[i];
        while (p != NULL) {
            fprintf(stdout, "(%2d %2d)  ", p->count, p->val);
            p = p->next;
        }
        fprintf(stdout, "\n");
    }

    return 0;
}


/*!
 * \brief
 *
 * Write sparse bitmap matrix out to disk file 'fp'.
 * NOTE: 'fp' must already be opened and later closed by user
 *
 * Returns 0 on success or -1 on error
 *
 *  \param fp
 *  \param map
 *  \return int
 */

int BM_file_write_sparse(FILE * fp, struct BM *map)
{
    char c;
    int i, y;
    struct BMlink *p;

    c = BM_MAGIC;
    fwrite(&c, sizeof(char), sizeof(char), fp);

    fwrite(BM_TEXT, BM_TEXT_LEN, sizeof(char), fp);

    c = BM_SPARSE;
    fwrite(&c, sizeof(char), sizeof(char), fp);

    fwrite(&(map->rows), sizeof(map->rows), sizeof(char), fp);

    fwrite(&(map->cols), sizeof(map->cols), sizeof(char), fp);

    for (y = 0; y < map->rows; y++) {
        /* first count number of links */
        p = ((struct BMlink **)(map->data))[y];
        int cnt = 0;
        while (p != NULL) {
            cnt++;
            p = p->next;
        }

        i = cnt;
        fwrite(&i, sizeof(i), sizeof(char), fp);


        /* then write them out */
        p = ((struct BMlink **)(map->data))[y];
        while (p != NULL) {
            i = p->count;
            fwrite(&i, sizeof(i), sizeof(char), fp);

            i = p->val;
            fwrite(&i, sizeof(i), sizeof(char), fp);

            p = p->next;
        }
    }
    fflush(fp);

    return 0;
}