datatypes.c

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