update datatypes.c with IMAGER_NO_CONTEXT
[imager.git] / datatypes.c
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <string.h>
4 #define IMAGER_NO_CONTEXT
5 #include "imager.h"
6
7 /*
8   2d bitmask with test and set operations
9 */
10
11 struct i_bitmap*
12 btm_new(i_img_dim xsize,i_img_dim ysize) {
13   size_t bytes;
14   struct i_bitmap *btm;
15   btm=(struct i_bitmap*)mymalloc(sizeof(struct i_bitmap)); /* checked 4jul05 tonyc */
16   bytes = (xsize*ysize+8)/8;
17   if (bytes * 8 / ysize < xsize-1) { /* this is kind of rough */
18     fprintf(stderr, "Integer overflow allocating bitmap (" i_DFp ")",
19             i_DFcp(xsize, ysize));
20     exit(3);
21   }
22   btm->data=(char*)mymalloc(bytes); /* checked 4jul05 tonyc */
23   btm->xsize=xsize;
24   btm->ysize=ysize;
25   memset(btm->data, 0, bytes);
26   return btm;
27 }
28
29
30 void
31 btm_destroy(struct i_bitmap *btm) {
32   myfree(btm->data);
33   myfree(btm);
34 }
35
36
37 int
38 btm_test(struct i_bitmap *btm,i_img_dim x,i_img_dim y) {
39   i_img_dim btno;
40   if (x<0 || x>btm->xsize-1 || y<0 || y>btm->ysize-1) return 0;
41   btno=btm->xsize*y+x;
42   return (1<<(btno%8))&(btm->data[btno/8]);
43 }
44
45 void
46 btm_set(struct i_bitmap *btm,i_img_dim x,i_img_dim y) {
47   i_img_dim btno;
48   if (x<0 || x>btm->xsize-1 || y<0 || y>btm->ysize-1) abort();
49   btno=btm->xsize*y+x;
50   btm->data[btno/8]|=1<<(btno%8);
51 }
52
53
54
55
56
57 /*
58   Bucketed linked list - stack type 
59 */
60
61 static struct llink *
62 llink_new(struct llink* p,size_t size);
63 static int
64 llist_llink_push(struct llist *lst, struct llink *lnk,const void *data);
65 static void
66 llink_destroy(struct llink* l);
67
68 /*
69 =item llist_new()
70 =synopsis struct llist *l = llist_new(100, sizeof(foo);
71
72 Create a new stack structure.  Implemented as a linked list of pools.
73
74 Parameters:
75
76 =over
77
78 =item *
79
80 multip - number of entries in each pool
81
82 =item *
83
84 ssize - size of the objects being pushed/popped
85
86 =back
87
88 =cut
89 */
90
91 struct llist *
92 llist_new(int multip, size_t ssize) {
93   struct llist *l;
94   l         = mymalloc(sizeof(struct llist)); /* checked 4jul05 tonyc */
95   l->h      = NULL;
96   l->t      = NULL;
97   l->multip = multip;
98   l->ssize  = ssize;
99   l->count  = 0;
100   return l;
101 }
102
103 /*
104 =item llist_push()
105 =synopsis llist_push(l, &foo);
106
107 Push an item on the stack.
108
109 =cut
110 */
111
112 void
113 llist_push(struct llist *l,const void *data) {
114   size_t ssize  = l->ssize;
115   int multip = l->multip;
116   
117   /*  fprintf(stderr,"llist_push: data=0x%08X\n",data);
118       fprintf(stderr,"Chain size: %d\n", l->count); */
119     
120   if (l->t == NULL) {
121     l->t = l->h = llink_new(NULL,ssize*multip);  /* Tail is empty - list is empty */
122     /* fprintf(stderr,"Chain empty - extended\n"); */
123   }
124   else { /* Check for overflow in current tail */
125     if (l->t->fill >= l->multip) {
126       struct llink* nt = llink_new(l->t, ssize*multip);
127       l->t->n=nt;
128       l->t=nt;
129       /* fprintf(stderr,"Chain extended\n"); */
130     }
131   }
132   /*   fprintf(stderr,"0x%08X\n",l->t); */
133   if (llist_llink_push(l,l->t,data)) { 
134     i_fatal(3, "out of memory\n");
135   }
136 }
137
138 /* 
139 =item llist_pop()
140
141 Pop an item off the list, storing it at C<data> which must have enough room for an object of the size supplied to llist_new().
142
143 returns 0 if the list is empty
144
145 =cut
146 */
147
148 int
149 llist_pop(struct llist *l,void *data) {
150   /*   int ssize=l->ssize; 
151        int multip=l->multip;*/
152   if (l->t == NULL) return 0;
153   l->t->fill--;
154   l->count--;
155   memcpy(data,(char*)(l->t->data)+l->ssize*l->t->fill,l->ssize);
156   
157   if (!l->t->fill) {                            /* This link empty */
158     if (l->t->p == NULL) {                      /* and it's the only link */
159       llink_destroy(l->t);
160       l->h = l->t = NULL;
161     }
162     else {
163       l->t=l->t->p;
164       llink_destroy(l->t->n);
165     }
166   }
167   return 1;
168 }
169
170 void
171 llist_dump(struct llist *l) {
172   int j;
173   int i=0;
174   struct llink *lnk; 
175   lnk=l->h;
176   while(lnk != NULL) {
177     for(j=0;j<lnk->fill;j++) {
178       /*       memcpy(&k,(char*)(lnk->data)+l->ssize*j,sizeof(void*));*/
179       /*memcpy(&k,(char*)(lnk->data)+l->ssize*j,sizeof(void*));*/
180       printf("%d - %p\n",i,*(void **)((char *)(lnk->data)+l->ssize*j));
181       i++;
182     }
183     lnk=lnk->n;
184   }
185 }
186
187 /*
188 =item llist_destroy()
189
190 Destroy a linked-list based stack.
191
192 =cut
193 */
194
195 void
196 llist_destroy(struct llist *l) {
197   struct llink *t,*lnk = l->h;
198   while( lnk != NULL ) {
199     t=lnk;
200     lnk=lnk->n;
201     myfree(t);
202   }
203   myfree(l);
204 }
205
206 /* Links */
207
208 static struct llink *
209 llink_new(struct llink* p,size_t size) {
210   struct llink *l;
211   l       = mymalloc(sizeof(struct llink)); /* checked 4jul05 tonyc */
212   l->n    = NULL;
213   l->p    = p;
214   l->fill = 0;
215   l->data = mymalloc(size); /* checked 4jul05 tonyc - depends on caller to llist_push */
216   return l;
217 }
218
219 /* free's the data pointer, itself, and sets the previous' next pointer to null */
220
221 static void
222 llink_destroy(struct llink* l) {
223   if (l->p != NULL) { l->p->n=NULL; }
224   myfree(l->data);
225   myfree(l);
226 }
227
228
229 /* if it returns true there wasn't room for the
230    item on the link */
231
232 static int
233 llist_llink_push(struct llist *lst, struct llink *lnk, const void *data) {
234   int multip;
235   multip = lst->multip;
236
237   /*   fprintf(stderr,"llist_llink_push: data=0x%08X -> 0x%08X\n",data,*(int*)data);
238        fprintf(stderr,"ssize = %d, multip = %d, fill = %d\n",lst->ssize,lst->multip,lnk->fill); */
239   if (lnk->fill == lst->multip) return 1;
240   /*   memcpy((char*)(lnk->data)+lnk->fill*lst->ssize,data,lst->ssize); */
241   memcpy((char*)(lnk->data)+lnk->fill*lst->ssize,data,lst->ssize);
242   
243   /*   printf("data=%X res=%X\n",*(int*)data,*(int*)(lnk->data));*/
244   lnk->fill++;
245   lst->count++;
246   return 0;
247 }
248
249 /*
250   Oct-tree implementation 
251 */
252
253 struct octt *
254 octt_new() {
255   int i;
256   struct octt *t;
257   
258   t=(struct octt*)mymalloc(sizeof(struct octt)); /* checked 4jul05 tonyc */
259   for(i=0;i<8;i++) t->t[i]=NULL;
260   t->cnt=0;
261   return t;
262 }
263
264
265 /* returns 1 if the colors wasn't in the octtree already */
266
267
268 int
269 octt_add(struct octt *ct,unsigned char r,unsigned char g,unsigned char b) {
270   struct octt *c;
271   int i,cm;
272   int ci;
273   int rc;
274   rc=0;
275   c=ct;
276   /*  printf("[r,g,b]=[%d,%d,%d]\n",r,g,b); */
277   for(i=7;i>-1;i--) {
278     cm=1<<i;
279     ci=((!!(r&cm))<<2)+((!!(g&cm))<<1)+!!(b&cm); 
280     /* printf("idx[%d]=%d\n",i,ci); */
281     if (c->t[ci] == NULL) { 
282       c->t[ci]=octt_new(); 
283       rc=1; 
284     }
285     c=c->t[ci];
286   }
287   c->cnt++;  /* New. The only thing really needed (I think) */
288   return rc;
289 }
290
291
292 void
293 octt_delete(struct octt *ct) {
294   int i;
295   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 */
296   myfree(ct);
297 }
298
299
300 void
301 octt_dump(struct octt *ct) {
302         int i;
303         /*      printf("node [0x%08X] -> (%d)\n",ct,ct->cnt); */
304         for(i=0;i<8;i++)
305           if (ct->t[i] != NULL) 
306             printf("[ %d ] -> %p\n", i, (void *)ct->t[i]);      
307         for(i=0;i<8;i++) 
308           if (ct->t[i] != NULL) 
309             octt_dump(ct->t[i]);
310 }
311
312 /* note that all calls of octt_count are operating on the same overflow 
313    variable so all calls will know at the same time if an overflow
314    has occured and stops there. */
315
316 void
317 octt_count(struct octt *ct,int *tot,int max,int *overflow) {
318   int i,c;
319   c=0;
320   if (!(*overflow)) return;
321   for(i=0;i<8;i++) if (ct->t[i]!=NULL) { 
322     octt_count(ct->t[i],tot,max,overflow);
323     c++;
324   }
325   if (!c) (*tot)++;
326   if ( (*tot) > (*overflow) ) *overflow=0;
327 }
328
329 /* This whole function is new */
330 /* walk through the tree and for each colour, store its seen count in the
331    space pointed by *col_usage_it_adr */
332 void
333 octt_histo(struct octt *ct, unsigned int **col_usage_it_adr) {
334     int i,c;
335     c = 0;
336     for(i = 0; i < 8; i++) 
337         if (ct->t[i] != NULL) { 
338             octt_histo(ct->t[i], col_usage_it_adr);
339             c++;
340         }
341     if (!c) {
342         *(*col_usage_it_adr)++ = ct->cnt;
343     }
344 }
345
346
347 i_img_dim
348 i_abs(i_img_dim x) {
349   return x < 0 ? -x : x;
350 }