datatypes.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include "imager.h"
   5
   6 /*
   7   2d bitmask with test and set operations
   8 */
   9
  10 struct i_bitmap*
  11 btm_new(i_img_dim xsize,i_img_dim ysize) {
  12   i_img_dim i;
  13   size_t bytes;
  14   struct i_bitmap *btm;
  15   btm=(struct i_bitmap*)mymalloc(sizeof(struct i_bitmap)); /* checked 4jul05 tonyc */
  16   bytes = (xsize*ysize+8)/8;
  17   if (bytes * 8 / ysize < xsize-1) { /* this is kind of rough */
  18     fprintf(stderr, "Integer overflow allocating bitmap (" i_DFp ")",
  19             i_DFcp(xsize, ysize));
  20     exit(3);
  21   }
  22   btm->data=(char*)mymalloc(bytes); /* checked 4jul05 tonyc */
  23   btm->xsize=xsize;
  24   btm->ysize=ysize;
  25   for(i=0;i<(xsize*ysize+8)/8;i++) btm->data[i]=0; /* Is this always needed */
  26   return btm;
  27 }
  28
  29
  30 void
  31 btm_destroy(struct i_bitmap *btm) {
  32   myfree(btm->data);
  33   myfree(btm);
  34 }
  35
  36
  37 int
  38 btm_test(struct i_bitmap *btm,i_img_dim x,i_img_dim y) {
  39   i_img_dim btno;
  40   if (x<0 || x>btm->xsize-1 || y<0 || y>btm->ysize-1) return 0;
  41   btno=btm->xsize*y+x;
  42   return (1<<(btno%8))&(btm->data[btno/8]);
  43 }
  44
  45 void
  46 btm_set(struct i_bitmap *btm,i_img_dim x,i_img_dim y) {
  47   i_img_dim btno;
  48   if (x<0 || x>btm->xsize-1 || y<0 || y>btm->ysize-1) abort();
  49   btno=btm->xsize*y+x;
  50   btm->data[btno/8]|=1<<(btno%8);
  51 }
  52
  53
  54
  55
  56
  57 /*
  58   Bucketed linked list - stack type
  59 */
  60
  61 static struct llink *
  62 llink_new(struct llink* p,size_t size);
  63 static int
  64 llist_llink_push(struct llist *lst, struct llink *lnk,const void *data);
  65 static void
  66 llink_destroy(struct llink* l);
  67
  68 /*
  69 =item llist_new()
  70 =synopsis struct llist *l = llist_new(100, sizeof(foo);
  71
  72 Create a new stack structure.  Implemented as a linked list of pools.
  73
  74 Parameters:
  75
  76 =over
  77
  78 =item *
  79
  80 multip - number of entries in each pool
  81
  82 =item *
  83
  84 ssize - size of the objects being pushed/popped
  85
  86 =back
  87
  88 =cut
  89 */
  90
  91 struct llist *
  92 llist_new(int multip, size_t ssize) {
  93   struct llist *l;
  94   l         = mymalloc(sizeof(struct llist)); /* checked 4jul05 tonyc */
  95   l->h      = NULL;
  96   l->t      = NULL;
  97   l->multip = multip;
  98   l->ssize  = ssize;
  99   l->count  = 0;
 100   return l;
 101 }
 102
 103 /*
 104 =item llist_push()
 105 =synopsis llist_push(l, &foo);
 106
 107 Push an item on the stack.
 108
 109 =cut
 110 */
 111
 112 void
 113 llist_push(struct llist *l,const void *data) {
 114   size_t ssize  = l->ssize;
 115   int multip = l->multip;
 116
 117   /*  fprintf(stderr,"llist_push: data=0x%08X\n",data);
 118       fprintf(stderr,"Chain size: %d\n", l->count); */
 119
 120   if (l->t == NULL) {
 121     l->t = l->h = llink_new(NULL,ssize*multip);  /* Tail is empty - list is empty */
 122     /* fprintf(stderr,"Chain empty - extended\n"); */
 123   }
 124   else { /* Check for overflow in current tail */
 125     if (l->t->fill >= l->multip) {
 126       struct llink* nt = llink_new(l->t, ssize*multip);
 127       l->t->n=nt;
 128       l->t=nt;
 129       /* fprintf(stderr,"Chain extended\n"); */
 130     }
 131   }
 132   /*   fprintf(stderr,"0x%08X\n",l->t); */
 133   if (llist_llink_push(l,l->t,data)) {
 134     i_fatal(3, "out of memory\n");
 135   }
 136 }
 137
 138 /*
 139 =item llist_pop()
 140
 141 Pop an item off the list, storing it at C<data> which must have enough room for an object of the size supplied to llist_new().
 142
 143 returns 0 if the list is empty
 144
 145 =cut
 146 */
 147
 148 int
 149 llist_pop(struct llist *l,void *data) {
 150   /*   int ssize=l->ssize;
 151        int multip=l->multip;*/
 152   if (l->t == NULL) return 0;
 153   l->t->fill--;
 154   l->count--;
 155   memcpy(data,(char*)(l->t->data)+l->ssize*l->t->fill,l->ssize);
 156
 157   if (!l->t->fill) {                            /* This link empty */
 158     if (l->t->p == NULL) {                      /* and it's the only link */
 159       llink_destroy(l->t);
 160       l->h = l->t = NULL;
 161     }
 162     else {
 163       l->t=l->t->p;
 164       llink_destroy(l->t->n);
 165     }
 166   }
 167   return 1;
 168 }
 169
 170 void
 171 llist_dump(struct llist *l) {
 172   int j;
 173   int i=0;
 174   struct llink *lnk;
 175   lnk=l->h;
 176   while(lnk != NULL) {
 177     for(j=0;j<lnk->fill;j++) {
 178       /*       memcpy(&k,(char*)(lnk->data)+l->ssize*j,sizeof(void*));*/
 179       /*memcpy(&k,(char*)(lnk->data)+l->ssize*j,sizeof(void*));*/
 180       printf("%d - %p\n",i,*(void **)((char *)(lnk->data)+l->ssize*j));
 181       i++;
 182     }
 183     lnk=lnk->n;
 184   }
 185 }
 186
 187 /*
 188 =item llist_destroy()
 189
 190 Destroy a linked-list based stack.
 191
 192 =cut
 193 */
 194
 195 void
 196 llist_destroy(struct llist *l) {
 197   struct llink *t,*lnk = l->h;
 198   while( lnk != NULL ) {
 199     t=lnk;
 200     lnk=lnk->n;
 201     myfree(t);
 202   }
 203   myfree(l);
 204 }
 205
 206 /* Links */
 207
 208 static struct llink *
 209 llink_new(struct llink* p,size_t size) {
 210   struct llink *l;
 211   l       = mymalloc(sizeof(struct llink)); /* checked 4jul05 tonyc */
 212   l->n    = NULL;
 213   l->p    = p;
 214   l->fill = 0;
 215   l->data = mymalloc(size); /* checked 4jul05 tonyc - depends on caller to llist_push */
 216   return l;
 217 }
 218
 219 /* free's the data pointer, itself, and sets the previous' next pointer to null */
 220
 221 static void
 222 llink_destroy(struct llink* l) {
 223   if (l->p != NULL) { l->p->n=NULL; }
 224   myfree(l->data);
 225   myfree(l);
 226 }
 227
 228
 229 /* if it returns true there wasn't room for the
 230    item on the link */
 231
 232 static int
 233 llist_llink_push(struct llist *lst, struct llink *lnk, const void *data) {
 234   int multip;
 235   multip = lst->multip;
 236
 237   /*   fprintf(stderr,"llist_llink_push: data=0x%08X -> 0x%08X\n",data,*(int*)data);
 238        fprintf(stderr,"ssize = %d, multip = %d, fill = %d\n",lst->ssize,lst->multip,lnk->fill); */
 239   if (lnk->fill == lst->multip) return 1;
 240   /*   memcpy((char*)(lnk->data)+lnk->fill*lst->ssize,data,lst->ssize); */
 241   memcpy((char*)(lnk->data)+lnk->fill*lst->ssize,data,lst->ssize);
 242
 243   /*   printf("data=%X res=%X\n",*(int*)data,*(int*)(lnk->data));*/
 244   lnk->fill++;
 245   lst->count++;
 246   return 0;
 247 }
 248
 249 /*
 250   Oct-tree implementation
 251 */
 252
 253 struct octt *
 254 octt_new() {
 255   int i;
 256   struct octt *t;
 257
 258   t=(struct octt*)mymalloc(sizeof(struct octt)); /* checked 4jul05 tonyc */
 259   for(i=0;i<8;i++) t->t[i]=NULL;
 260   t->cnt=0;
 261   return t;
 262 }
 263
 264
 265 /* returns 1 if the colors wasn't in the octtree already */
 266
 267
 268 int
 269 octt_add(struct octt *ct,unsigned char r,unsigned char g,unsigned char b) {
 270   struct octt *c;
 271   int i,cm;
 272   int ci;
 273   int rc;
 274   rc=0;
 275   c=ct;
 276   /*  printf("[r,g,b]=[%d,%d,%d]\n",r,g,b); */
 277   for(i=7;i>-1;i--) {
 278     cm=1<<i;
 279     ci=((!!(r&cm))<<2)+((!!(g&cm))<<1)+!!(b&cm);
 280     /* printf("idx[%d]=%d\n",i,ci); */
 281     if (c->t[ci] == NULL) {
 282       c->t[ci]=octt_new();
 283       rc=1;
 284     }
 285     c=c->t[ci];
 286   }
 287   c->cnt++;  /* New. The only thing really needed (I think) */
 288   return rc;
 289 }
 290
 291
 292 void
 293 octt_delete(struct octt *ct) {
 294   int i;
 295   for(i=0;i<8;i++) if (ct->t[i] != NULL) octt_delete(ct->t[i]);  /* do not free instance here because it will free itself */
 296   myfree(ct);
 297 }
 298
 299
 300 void
 301 octt_dump(struct octt *ct) {
 302         int i;
 303         /*      printf("node [0x%08X] -> (%d)\n",ct,ct->cnt); */
 304         for(i=0;i<8;i++)
 305           if (ct->t[i] != NULL)
 306             printf("[ %d ] -> %p\n", i, (void *)ct->t[i]);
 307         for(i=0;i<8;i++)
 308           if (ct->t[i] != NULL)
 309             octt_dump(ct->t[i]);
 310 }
 311
 312 /* note that all calls of octt_count are operating on the same overflow
 313    variable so all calls will know at the same time if an overflow
 314    has occured and stops there. */
 315
 316 void
 317 octt_count(struct octt *ct,int *tot,int max,int *overflow) {
 318   int i,c;
 319   c=0;
 320   if (!(*overflow)) return;
 321   for(i=0;i<8;i++) if (ct->t[i]!=NULL) {
 322     octt_count(ct->t[i],tot,max,overflow);
 323     c++;
 324   }
 325   if (!c) (*tot)++;
 326   if ( (*tot) > (*overflow) ) *overflow=0;
 327 }
 328
 329 /* This whole function is new */
 330 /* walk through the tree and for each colour, store its seen count in the
 331    space pointed by *col_usage_it_adr */
 332 void
 333 octt_histo(struct octt *ct, unsigned int **col_usage_it_adr) {
 334     int i,c;
 335     c = 0;
 336     for(i = 0; i < 8; i++)
 337         if (ct->t[i] != NULL) {
 338             octt_histo(ct->t[i], col_usage_it_adr);
 339             c++;
 340         }
 341     if (!c) {
 342         *(*col_usage_it_adr)++ = ct->cnt;
 343     }
 344 }
 345
 346
 347 i_img_dim
 348 i_abs(i_img_dim x) {
 349   return x < 0 ? -x : x;
 350 }