datatypes.c

   1 #include "imio.h"
   2 #include "datatypes.h"
   3 #include <stdlib.h>
   4 #include <stdio.h>
   5 #include <string.h>
   6
   7
   8 /*
   9   2d bitmask with test and set operations
  10 */
  11
  12 struct i_bitmap*
  13 btm_new(int xsize,int ysize) {
  14   int i;
  15   int bytes;
  16   struct i_bitmap *btm;
  17   btm=(struct i_bitmap*)mymalloc(sizeof(struct i_bitmap)); /* checked 4jul05 tonyc */
  18   bytes = (xsize*ysize+8)/8;
  19   if (bytes * 8 / ysize < xsize-1) { /* this is kind of rough */
  20     fprintf(stderr, "Integer overflow allocating bitmap %d x %d", xsize, ysize);
  21     exit(3);
  22   }
  23   btm->data=(char*)mymalloc(bytes); /* checked 4jul05 tonyc */
  24   btm->xsize=xsize;
  25   btm->ysize=ysize;
  26   for(i=0;i<(xsize*ysize+8)/8;i++) btm->data[i]=0; /* Is this always needed */
  27   return btm;
  28 }
  29
  30
  31 void
  32 btm_destroy(struct i_bitmap *btm) {
  33   myfree(btm->data);
  34   myfree(btm);
  35 }
  36
  37
  38 int
  39 btm_test(struct i_bitmap *btm,int x,int y) {
  40   int btno;
  41   if (x<0 || x>btm->xsize-1 || y<0 || y>btm->ysize-1) return 0;
  42   btno=btm->xsize*y+x;
  43   return (1<<(btno%8))&(btm->data[btno/8]);
  44 }
  45
  46 void
  47 btm_set(struct i_bitmap *btm,int x,int y) {
  48   int btno;
  49   if (x<0 || x>btm->xsize-1 || y<0 || y>btm->ysize-1) abort();
  50   btno=btm->xsize*y+x;
  51   btm->data[btno/8]|=1<<(btno%8);
  52 }
  53
  54
  55
  56
  57
  58 /*
  59   Bucketed linked list - stack type
  60 */
  61
  62 struct llink *
  63 llink_new(struct llink* p,int size) {
  64   struct llink *l;
  65   l       = mymalloc(sizeof(struct llink)); /* checked 4jul05 tonyc */
  66   l->n    = NULL;
  67   l->p    = p;
  68   l->fill = 0;
  69   l->data = mymalloc(size); /* checked 4jul05 tonyc - depends on caller to llist_push */
  70   return l;
  71 }
  72
  73 /* free's the data pointer, itself, and sets the previous' next pointer to null */
  74
  75 void
  76 llink_destroy(struct llink* l) {
  77   if (l->p != NULL) { l->p->n=NULL; }
  78   myfree(l->data);
  79   myfree(l);
  80 }
  81
  82
  83 /* if it returns true there wasn't room for the
  84    item on the link */
  85
  86 int
  87 llist_llink_push(struct llist *lst, struct llink *lnk,void *data) {
  88   int multip;
  89   multip = lst->multip;
  90
  91   /*   fprintf(stderr,"llist_llink_push: data=0x%08X -> 0x%08X\n",data,*(int*)data);
  92        fprintf(stderr,"ssize = %d, multip = %d, fill = %d\n",lst->ssize,lst->multip,lnk->fill); */
  93   if (lnk->fill == lst->multip) return 1;
  94   /*   memcpy((char*)(lnk->data)+lnk->fill*lst->ssize,data,lst->ssize); */
  95   memcpy((char*)(lnk->data)+lnk->fill*lst->ssize,data,lst->ssize);
  96
  97   /*   printf("data=%X res=%X\n",*(int*)data,*(int*)(lnk->data));*/
  98   lnk->fill++;
  99   lst->count++;
 100   return 0;
 101 }
 102
 103 struct llist *
 104 llist_new(int multip, int ssize) {
 105   struct llist *l;
 106   l         = mymalloc(sizeof(struct llist)); /* checked 4jul05 tonyc */
 107   l->h      = NULL;
 108   l->t      = NULL;
 109   l->multip = multip;
 110   l->ssize  = ssize;
 111   l->count  = 0;
 112   return l;
 113 }
 114
 115 void
 116 llist_push(struct llist *l,void *data) {
 117   int ssize  = l->ssize;
 118   int multip = l->multip;
 119
 120   /*  fprintf(stderr,"llist_push: data=0x%08X\n",data);
 121       fprintf(stderr,"Chain size: %d\n", l->count); */
 122
 123   if (l->t == NULL) {
 124     l->t = l->h = llink_new(NULL,ssize*multip);  /* Tail is empty - list is empty */
 125     /* fprintf(stderr,"Chain empty - extended\n"); */
 126   }
 127   else { /* Check for overflow in current tail */
 128     if (l->t->fill >= l->multip) {
 129       struct llink* nt = llink_new(l->t, ssize*multip);
 130       l->t->n=nt;
 131       l->t=nt;
 132       /* fprintf(stderr,"Chain extended\n"); */
 133     }
 134   }
 135   /*   fprintf(stderr,"0x%08X\n",l->t); */
 136   if (llist_llink_push(l,l->t,data)) {
 137     m_fatal(3, "out of memory\n");
 138   }
 139 }
 140
 141 /* returns 0 if the list is empty */
 142
 143 int
 144 llist_pop(struct llist *l,void *data) {
 145   /*   int ssize=l->ssize;
 146        int multip=l->multip;*/
 147   if (l->t == NULL) return 0;
 148   l->t->fill--;
 149   l->count--;
 150   memcpy(data,(char*)(l->t->data)+l->ssize*l->t->fill,l->ssize);
 151
 152   if (!l->t->fill) {                            /* This link empty */
 153     if (l->t->p == NULL) {                      /* and it's the only link */
 154       llink_destroy(l->t);
 155       l->h = l->t = NULL;
 156     }
 157     else {
 158       l->t=l->t->p;
 159       llink_destroy(l->t->n);
 160     }
 161   }
 162   return 1;
 163 }
 164
 165 void
 166 llist_dump(struct llist *l) {
 167   int k,j;
 168   int i=0;
 169   struct llink *lnk;
 170   lnk=l->h;
 171   while(lnk != NULL) {
 172     for(j=0;j<lnk->fill;j++) {
 173       /*       memcpy(&k,(char*)(lnk->data)+l->ssize*j,sizeof(void*));*/
 174       memcpy(&k,(char*)(lnk->data)+l->ssize*j,sizeof(void*));
 175       printf("%d - %X\n",i,k);
 176       i++;
 177     }
 178     lnk=lnk->n;
 179   }
 180 }
 181
 182 void
 183 llist_destroy(struct llist *l) {
 184   struct llink *t,*lnk = l->h;
 185   while( lnk != NULL ) {
 186     t=lnk;
 187     lnk=lnk->n;
 188     myfree(t);
 189   }
 190   myfree(l);
 191 }
 192
 193
 194
 195
 196
 197
 198 /*
 199   Oct-tree implementation
 200 */
 201
 202 struct octt *
 203 octt_new() {
 204   int i;
 205   struct octt *t;
 206
 207   t=(struct octt*)mymalloc(sizeof(struct octt)); /* checked 4jul05 tonyc */
 208   for(i=0;i<8;i++) t->t[i]=NULL;
 209   t->cnt=0;
 210   return t;
 211 }
 212
 213
 214 /* returns 1 if the colors wasn't in the octtree already */
 215
 216
 217 int
 218 octt_add(struct octt *ct,unsigned char r,unsigned char g,unsigned char b) {
 219   struct octt *c;
 220   int i,cm;
 221   int ci,idx[8];
 222   int rc;
 223   rc=0;
 224   c=ct;
 225   /*  printf("[r,g,b]=[%d,%d,%d]\n",r,g,b); */
 226   ct->cnt++;
 227   for(i=7;i>-1;i--) {
 228     cm=1<<i;
 229     ci=((!!(r&cm))<<2)+((!!(g&cm))<<1)+!!(b&cm);
 230     /* printf("idx[%d]=%d\n",i,ci); */
 231     if (c->t[ci] == NULL) { c->t[ci]=octt_new(); rc=1; }
 232     c=c->t[ci];
 233     c->cnt++;
 234     idx[i]=ci;
 235   }
 236   return rc;
 237 }
 238
 239
 240 void
 241 octt_delete(struct octt *ct) {
 242   int i;
 243   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 */
 244   myfree(ct);
 245 }
 246
 247
 248 void
 249 octt_dump(struct octt *ct) {
 250         int i;
 251         /*      printf("node [0x%08X] -> (%d)\n",ct,ct->cnt); */
 252         for(i=0;i<8;i++) if (ct->t[i] != NULL) printf("[ %d ] -> 0x%08X\n",i,(unsigned int)ct->t[i]);
 253         for(i=0;i<8;i++) if (ct->t[i] != NULL) octt_dump(ct->t[i]);
 254 }
 255
 256 /* note that all calls of octt_count are operating on the same overflow
 257    variable so all calls will know at the same time if an overflow
 258    has occured and stops there. */
 259
 260 void
 261 octt_count(struct octt *ct,int *tot,int max,int *overflow) {
 262   int i,c;
 263   c=0;
 264   if (!(*overflow)) return;
 265   for(i=0;i<8;i++) if (ct->t[i]!=NULL) {
 266     octt_count(ct->t[i],tot,max,overflow);
 267     c++;
 268   }
 269   if (!c) (*tot)++;
 270   if ( (*tot) > (*overflow) ) *overflow=0;
 271 }