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