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