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