avoid a dangerous cast (in an unused function)
[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(int xsize,int ysize) {
12   int i;
13   int 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 %d x %d", xsize, ysize);
19     exit(3);
20   }
21   btm->data=(char*)mymalloc(bytes); /* checked 4jul05 tonyc */
22   btm->xsize=xsize;
23   btm->ysize=ysize;
24   for(i=0;i<(xsize*ysize+8)/8;i++) btm->data[i]=0; /* Is this always needed */
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,int x,int y) {
38   int 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,int x,int y) {
46   int 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 struct llink *
61 llink_new(struct llink* p,int size) {
62   struct llink *l;
63   l       = mymalloc(sizeof(struct llink)); /* checked 4jul05 tonyc */
64   l->n    = NULL;
65   l->p    = p;
66   l->fill = 0;
67   l->data = mymalloc(size); /* checked 4jul05 tonyc - depends on caller to llist_push */
68   return l;
69 }
70
71 /* free's the data pointer, itself, and sets the previous' next pointer to null */
72
73 void
74 llink_destroy(struct llink* l) {
75   if (l->p != NULL) { l->p->n=NULL; }
76   myfree(l->data);
77   myfree(l);
78 }
79
80
81 /* if it returns true there wasn't room for the
82    item on the link */
83
84 int
85 llist_llink_push(struct llist *lst, struct llink *lnk,void *data) {
86   int multip;
87   multip = lst->multip;
88
89   /*   fprintf(stderr,"llist_llink_push: data=0x%08X -> 0x%08X\n",data,*(int*)data);
90        fprintf(stderr,"ssize = %d, multip = %d, fill = %d\n",lst->ssize,lst->multip,lnk->fill); */
91   if (lnk->fill == lst->multip) return 1;
92   /*   memcpy((char*)(lnk->data)+lnk->fill*lst->ssize,data,lst->ssize); */
93   memcpy((char*)(lnk->data)+lnk->fill*lst->ssize,data,lst->ssize);
94   
95   /*   printf("data=%X res=%X\n",*(int*)data,*(int*)(lnk->data));*/
96   lnk->fill++;
97   lst->count++;
98   return 0;
99 }
100
101 struct llist *
102 llist_new(int multip, int ssize) {
103   struct llist *l;
104   l         = mymalloc(sizeof(struct llist)); /* checked 4jul05 tonyc */
105   l->h      = NULL;
106   l->t      = NULL;
107   l->multip = multip;
108   l->ssize  = ssize;
109   l->count  = 0;
110   return l;
111 }
112
113 void
114 llist_push(struct llist *l,void *data) {
115   int ssize  = l->ssize;
116   int multip = l->multip;
117   
118   /*  fprintf(stderr,"llist_push: data=0x%08X\n",data);
119       fprintf(stderr,"Chain size: %d\n", l->count); */
120     
121   if (l->t == NULL) {
122     l->t = l->h = llink_new(NULL,ssize*multip);  /* Tail is empty - list is empty */
123     /* fprintf(stderr,"Chain empty - extended\n"); */
124   }
125   else { /* Check for overflow in current tail */
126     if (l->t->fill >= l->multip) {
127       struct llink* nt = llink_new(l->t, ssize*multip);
128       l->t->n=nt;
129       l->t=nt;
130       /* fprintf(stderr,"Chain extended\n"); */
131     }
132   }
133   /*   fprintf(stderr,"0x%08X\n",l->t); */
134   if (llist_llink_push(l,l->t,data)) { 
135     i_fatal(3, "out of memory\n");
136   }
137 }
138
139 /* returns 0 if the list is empty */
140
141 int
142 llist_pop(struct llist *l,void *data) {
143   /*   int ssize=l->ssize; 
144        int multip=l->multip;*/
145   if (l->t == NULL) return 0;
146   l->t->fill--;
147   l->count--;
148   memcpy(data,(char*)(l->t->data)+l->ssize*l->t->fill,l->ssize);
149   
150   if (!l->t->fill) {                            /* This link empty */
151     if (l->t->p == NULL) {                      /* and it's the only link */
152       llink_destroy(l->t);
153       l->h = l->t = NULL;
154     }
155     else {
156       l->t=l->t->p;
157       llink_destroy(l->t->n);
158     }
159   }
160   return 1;
161 }
162
163 void
164 llist_dump(struct llist *l) {
165   int j;
166   int i=0;
167   struct llink *lnk; 
168   lnk=l->h;
169   while(lnk != NULL) {
170     for(j=0;j<lnk->fill;j++) {
171       /*       memcpy(&k,(char*)(lnk->data)+l->ssize*j,sizeof(void*));*/
172       /*memcpy(&k,(char*)(lnk->data)+l->ssize*j,sizeof(void*));*/
173       printf("%d - %p\n",i,*(void **)((lnk->data)+l->ssize*j));
174       i++;
175     }
176     lnk=lnk->n;
177   }
178 }
179
180 void
181 llist_destroy(struct llist *l) {
182   struct llink *t,*lnk = l->h;
183   while( lnk != NULL ) {
184     t=lnk;
185     lnk=lnk->n;
186     myfree(t);
187   }
188   myfree(l);
189 }
190
191
192
193
194
195
196 /*
197   Oct-tree implementation 
198 */
199
200 struct octt *
201 octt_new() {
202   int i;
203   struct octt *t;
204   
205   t=(struct octt*)mymalloc(sizeof(struct octt)); /* checked 4jul05 tonyc */
206   for(i=0;i<8;i++) t->t[i]=NULL;
207   t->cnt=0;
208   return t;
209 }
210
211
212 /* returns 1 if the colors wasn't in the octtree already */
213
214
215 int
216 octt_add(struct octt *ct,unsigned char r,unsigned char g,unsigned char b) {
217   struct octt *c;
218   int i,cm;
219   int ci;
220   int rc;
221   rc=0;
222   c=ct;
223   /*  printf("[r,g,b]=[%d,%d,%d]\n",r,g,b); */
224   for(i=7;i>-1;i--) {
225     cm=1<<i;
226     ci=((!!(r&cm))<<2)+((!!(g&cm))<<1)+!!(b&cm); 
227     /* printf("idx[%d]=%d\n",i,ci); */
228     if (c->t[ci] == NULL) { 
229       c->t[ci]=octt_new(); 
230       rc=1; 
231     }
232     c=c->t[ci];
233   }
234   c->cnt++;  /* New. The only thing really needed (I think) */
235   return rc;
236 }
237
238
239 void
240 octt_delete(struct octt *ct) {
241   int i;
242   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 */
243   myfree(ct);
244 }
245
246
247 void
248 octt_dump(struct octt *ct) {
249         int i;
250         /*      printf("node [0x%08X] -> (%d)\n",ct,ct->cnt); */
251         for(i=0;i<8;i++)
252           if (ct->t[i] != NULL) 
253             printf("[ %d ] -> %p\n", i, (void *)ct->t[i]);      
254         for(i=0;i<8;i++) 
255           if (ct->t[i] != NULL) 
256             octt_dump(ct->t[i]);
257 }
258
259 /* note that all calls of octt_count are operating on the same overflow 
260    variable so all calls will know at the same time if an overflow
261    has occured and stops there. */
262
263 void
264 octt_count(struct octt *ct,int *tot,int max,int *overflow) {
265   int i,c;
266   c=0;
267   if (!(*overflow)) return;
268   for(i=0;i<8;i++) if (ct->t[i]!=NULL) { 
269     octt_count(ct->t[i],tot,max,overflow);
270     c++;
271   }
272   if (!c) (*tot)++;
273   if ( (*tot) > (*overflow) ) *overflow=0;
274 }
275
276 /* This whole function is new */
277 /* walk through the tree and for each colour, store its seen count in the
278    space pointed by *col_usage_it_adr */
279 void
280 octt_histo(struct octt *ct, unsigned int **col_usage_it_adr) {
281     int i,c;
282     c = 0;
283     for(i = 0; i < 8; i++) 
284         if (ct->t[i] != NULL) { 
285             octt_histo(ct->t[i], col_usage_it_adr);
286             c++;
287         }
288     if (!c) {
289         *(*col_usage_it_adr)++ = ct->cnt;
290     }
291 }
292
293