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(int xsize,int ysize) {
  12   int i;
  13   int 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 %d x %d", xsize, ysize);
  19     exit(3);
  20   }
  21   btm->data=(char*)mymalloc(bytes); /* checked 4jul05 tonyc */
  22   btm->xsize=xsize;
  23   btm->ysize=ysize;
  24   for(i=0;i<(xsize*ysize+8)/8;i++) btm->data[i]=0; /* Is this always needed */
  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,int x,int y) {
  38   int 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,int x,int y) {
  46   int 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 struct llink *
  61 llink_new(struct llink* p,int size) {
  62   struct llink *l;
  63   l       = mymalloc(sizeof(struct llink)); /* checked 4jul05 tonyc */
  64   l->n    = NULL;
  65   l->p    = p;
  66   l->fill = 0;
  67   l->data = mymalloc(size); /* checked 4jul05 tonyc - depends on caller to llist_push */
  68   return l;
  69 }
  70
  71 /* free's the data pointer, itself, and sets the previous' next pointer to null */
  72
  73 void
  74 llink_destroy(struct llink* l) {
  75   if (l->p != NULL) { l->p->n=NULL; }
  76   myfree(l->data);
  77   myfree(l);
  78 }
  79
  80
  81 /* if it returns true there wasn't room for the
  82    item on the link */
  83
  84 int
  85 llist_llink_push(struct llist *lst, struct llink *lnk,void *data) {
  86   int multip;
  87   multip = lst->multip;
  88
  89   /*   fprintf(stderr,"llist_llink_push: data=0x%08X -> 0x%08X\n",data,*(int*)data);
  90        fprintf(stderr,"ssize = %d, multip = %d, fill = %d\n",lst->ssize,lst->multip,lnk->fill); */
  91   if (lnk->fill == lst->multip) return 1;
  92   /*   memcpy((char*)(lnk->data)+lnk->fill*lst->ssize,data,lst->ssize); */
  93   memcpy((char*)(lnk->data)+lnk->fill*lst->ssize,data,lst->ssize);
  94
  95   /*   printf("data=%X res=%X\n",*(int*)data,*(int*)(lnk->data));*/
  96   lnk->fill++;
  97   lst->count++;
  98   return 0;
  99 }
 100
 101 struct llist *
 102 llist_new(int multip, int ssize) {
 103   struct llist *l;
 104   l         = mymalloc(sizeof(struct llist)); /* checked 4jul05 tonyc */
 105   l->h      = NULL;
 106   l->t      = NULL;
 107   l->multip = multip;
 108   l->ssize  = ssize;
 109   l->count  = 0;
 110   return l;
 111 }
 112
 113 void
 114 llist_push(struct llist *l,void *data) {
 115   int ssize  = l->ssize;
 116   int multip = l->multip;
 117
 118   /*  fprintf(stderr,"llist_push: data=0x%08X\n",data);
 119       fprintf(stderr,"Chain size: %d\n", l->count); */
 120
 121   if (l->t == NULL) {
 122     l->t = l->h = llink_new(NULL,ssize*multip);  /* Tail is empty - list is empty */
 123     /* fprintf(stderr,"Chain empty - extended\n"); */
 124   }
 125   else { /* Check for overflow in current tail */
 126     if (l->t->fill >= l->multip) {
 127       struct llink* nt = llink_new(l->t, ssize*multip);
 128       l->t->n=nt;
 129       l->t=nt;
 130       /* fprintf(stderr,"Chain extended\n"); */
 131     }
 132   }
 133   /*   fprintf(stderr,"0x%08X\n",l->t); */
 134   if (llist_llink_push(l,l->t,data)) {
 135     i_fatal(3, "out of memory\n");
 136   }
 137 }
 138
 139 /* returns 0 if the list is empty */
 140
 141 int
 142 llist_pop(struct llist *l,void *data) {
 143   /*   int ssize=l->ssize;
 144        int multip=l->multip;*/
 145   if (l->t == NULL) return 0;
 146   l->t->fill--;
 147   l->count--;
 148   memcpy(data,(char*)(l->t->data)+l->ssize*l->t->fill,l->ssize);
 149
 150   if (!l->t->fill) {                            /* This link empty */
 151     if (l->t->p == NULL) {                      /* and it's the only link */
 152       llink_destroy(l->t);
 153       l->h = l->t = NULL;
 154     }
 155     else {
 156       l->t=l->t->p;
 157       llink_destroy(l->t->n);
 158     }
 159   }
 160   return 1;
 161 }
 162
 163 void
 164 llist_dump(struct llist *l) {
 165   int j;
 166   int i=0;
 167   struct llink *lnk;
 168   lnk=l->h;
 169   while(lnk != NULL) {
 170     for(j=0;j<lnk->fill;j++) {
 171       /*       memcpy(&k,(char*)(lnk->data)+l->ssize*j,sizeof(void*));*/
 172       /*memcpy(&k,(char*)(lnk->data)+l->ssize*j,sizeof(void*));*/
 173       printf("%d - %p\n",i,*(void **)((char *)(lnk->data)+l->ssize*j));
 174       i++;
 175     }
 176     lnk=lnk->n;
 177   }
 178 }
 179
 180 void
 181 llist_destroy(struct llist *l) {
 182   struct llink *t,*lnk = l->h;
 183   while( lnk != NULL ) {
 184     t=lnk;
 185     lnk=lnk->n;
 186     myfree(t);
 187   }
 188   myfree(l);
 189 }
 190
 191
 192
 193
 194
 195
 196 /*
 197   Oct-tree implementation
 198 */
 199
 200 struct octt *
 201 octt_new() {
 202   int i;
 203   struct octt *t;
 204
 205   t=(struct octt*)mymalloc(sizeof(struct octt)); /* checked 4jul05 tonyc */
 206   for(i=0;i<8;i++) t->t[i]=NULL;
 207   t->cnt=0;
 208   return t;
 209 }
 210
 211
 212 /* returns 1 if the colors wasn't in the octtree already */
 213
 214
 215 int
 216 octt_add(struct octt *ct,unsigned char r,unsigned char g,unsigned char b) {
 217   struct octt *c;
 218   int i,cm;
 219   int ci;
 220   int rc;
 221   rc=0;
 222   c=ct;
 223   /*  printf("[r,g,b]=[%d,%d,%d]\n",r,g,b); */
 224   for(i=7;i>-1;i--) {
 225     cm=1<<i;
 226     ci=((!!(r&cm))<<2)+((!!(g&cm))<<1)+!!(b&cm);
 227     /* printf("idx[%d]=%d\n",i,ci); */
 228     if (c->t[ci] == NULL) {
 229       c->t[ci]=octt_new();
 230       rc=1;
 231     }
 232     c=c->t[ci];
 233   }
 234   c->cnt++;  /* New. The only thing really needed (I think) */
 235   return rc;
 236 }
 237
 238
 239 void
 240 octt_delete(struct octt *ct) {
 241   int i;
 242   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 */
 243   myfree(ct);
 244 }
 245
 246
 247 void
 248 octt_dump(struct octt *ct) {
 249         int i;
 250         /*      printf("node [0x%08X] -> (%d)\n",ct,ct->cnt); */
 251         for(i=0;i<8;i++)
 252           if (ct->t[i] != NULL)
 253             printf("[ %d ] -> %p\n", i, (void *)ct->t[i]);
 254         for(i=0;i<8;i++)
 255           if (ct->t[i] != NULL)
 256             octt_dump(ct->t[i]);
 257 }
 258
 259 /* note that all calls of octt_count are operating on the same overflow
 260    variable so all calls will know at the same time if an overflow
 261    has occured and stops there. */
 262
 263 void
 264 octt_count(struct octt *ct,int *tot,int max,int *overflow) {
 265   int i,c;
 266   c=0;
 267   if (!(*overflow)) return;
 268   for(i=0;i<8;i++) if (ct->t[i]!=NULL) {
 269     octt_count(ct->t[i],tot,max,overflow);
 270     c++;
 271   }
 272   if (!c) (*tot)++;
 273   if ( (*tot) > (*overflow) ) *overflow=0;
 274 }
 275
 276 /* This whole function is new */
 277 /* walk through the tree and for each colour, store its seen count in the
 278    space pointed by *col_usage_it_adr */
 279 void
 280 octt_histo(struct octt *ct, unsigned int **col_usage_it_adr) {
 281     int i,c;
 282     c = 0;
 283     for(i = 0; i < 8; i++)
 284         if (ct->t[i] != NULL) {
 285             octt_histo(ct->t[i], col_usage_it_adr);
 286             c++;
 287         }
 288     if (!c) {
 289         *(*col_usage_it_adr)++ = ct->cnt;
 290     }
 291 }
 292
 293