- renamed io.h to imio.h to prevent problems building under cygwin.
[imager.git] / datatypes.c
1 #include "imio.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   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 }