Loading...
Searching...
No Matches
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;
}
NULL
#define NULL
Definition ccmath.h:32
link_dispose
void link_dispose(struct link_head *Head, VOID_T *ptr)
Definition dispose.c:10
cur_x
double cur_x
Definition driver/init.c:32
count
int count
link_cleanup
void link_cleanup(struct link_head *Head)
Definition linkm/init.c:67
link_set_chunk_size
void link_set_chunk_size(int size)
Definition linkm/init.c:32
link_init
struct link_head * link_init(int size)
Definition linkm/init.c:42
link_new
VOID_T * link_new(struct link_head *Head)
Definition new.c:12
VOID_T
#define VOID_T
Definition qtree.h:28
BM_create_sparse
struct BM * BM_create_sparse(int x, int y)
Create a sparse bitmap of dimension 'x'/'y'.
Definition sparse.c:41
BM_dump_map_row_sparse
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:316
BM_file_write_sparse
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:346
BM_get_sparse
int BM_get_sparse(struct BM *map, int x, int y)
Returns sparse bitmap value at location 'x'/'y'.
Definition sparse.c:236
BM_get_map_size_sparse
size_t BM_get_map_size_sparse(struct BM *map)
Returns size of sparse bitmap in bytes.
Definition sparse.c:260
BM_destroy_sparse
int BM_destroy_sparse(struct BM *map)
Destroy sparse bitmap and free all associated memory.
Definition sparse.c:86
BM_set_sparse
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:122
BM_dump_map_sparse
int BM_dump_map_sparse(struct BM *map)
Debugging code to dump out structure of links.
Definition sparse.c:288
x
#define x