- start of external Imager API access:
[imager.git] / datatypes.c
1 #include "imio.h"
2 #include "imdatatypes.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 }