- start of external Imager API access:
[imager.git] / datatypes.c
CommitLineData
7ac6a2e9 1#include "imio.h"
92bda632 2#include "imdatatypes.h"
02d1d628
AMH
3#include <stdlib.h>
4#include <stdio.h>
35891892 5#include <string.h>
02d1d628
AMH
6
7
8/*
9 2d bitmask with test and set operations
10*/
11
12struct i_bitmap*
13btm_new(int xsize,int ysize) {
14 int i;
f0960b14 15 int bytes;
02d1d628 16 struct i_bitmap *btm;
f0960b14
TC
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 */
02d1d628
AMH
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
31void
32btm_destroy(struct i_bitmap *btm) {
33 myfree(btm->data);
34 myfree(btm);
35}
36
37
38int
39btm_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
46void
47btm_set(struct i_bitmap *btm,int x,int y) {
48 int btno;
e25e59b1 49 if (x<0 || x>btm->xsize-1 || y<0 || y>btm->ysize-1) abort();
02d1d628
AMH
50 btno=btm->xsize*y+x;
51 btm->data[btno/8]|=1<<(btno%8);
52}
53
54
55
56
57
58/*
a73aeb5f 59 Bucketed linked list - stack type
02d1d628
AMH
60*/
61
62struct llink *
63llink_new(struct llink* p,int size) {
64 struct llink *l;
f0960b14 65 l = mymalloc(sizeof(struct llink)); /* checked 4jul05 tonyc */
a73aeb5f
AMH
66 l->n = NULL;
67 l->p = p;
68 l->fill = 0;
f0960b14 69 l->data = mymalloc(size); /* checked 4jul05 tonyc - depends on caller to llist_push */
02d1d628
AMH
70 return l;
71}
72
73/* free's the data pointer, itself, and sets the previous' next pointer to null */
74
75void
76llink_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
86int
87llist_llink_push(struct llist *lst, struct llink *lnk,void *data) {
88 int multip;
a73aeb5f 89 multip = lst->multip;
02d1d628
AMH
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
103struct llist *
104llist_new(int multip, int ssize) {
105 struct llist *l;
f0960b14 106 l = mymalloc(sizeof(struct llist)); /* checked 4jul05 tonyc */
a73aeb5f
AMH
107 l->h = NULL;
108 l->t = NULL;
109 l->multip = multip;
110 l->ssize = ssize;
111 l->count = 0;
02d1d628
AMH
112 return l;
113}
114
115void
116llist_push(struct llist *l,void *data) {
a73aeb5f
AMH
117 int ssize = l->ssize;
118 int multip = l->multip;
02d1d628 119
a73aeb5f
AMH
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 }
02d1d628
AMH
127 else { /* Check for overflow in current tail */
128 if (l->t->fill >= l->multip) {
a73aeb5f 129 struct llink* nt = llink_new(l->t, ssize*multip);
02d1d628
AMH
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); */
a73aeb5f
AMH
136 if (llist_llink_push(l,l->t,data)) {
137 m_fatal(3, "out of memory\n");
138 }
02d1d628
AMH
139}
140
141/* returns 0 if the list is empty */
142
143int
144llist_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--;
02d1d628
AMH
150 memcpy(data,(char*)(l->t->data)+l->ssize*l->t->fill,l->ssize);
151
152 if (!l->t->fill) { /* This link empty */
a73aeb5f
AMH
153 if (l->t->p == NULL) { /* and it's the only link */
154 llink_destroy(l->t);
155 l->h = l->t = NULL;
156 }
02d1d628
AMH
157 else {
158 l->t=l->t->p;
159 llink_destroy(l->t->n);
160 }
161 }
162 return 1;
163}
164
165void
166llist_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
182void
183llist_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
202struct octt *
203octt_new() {
204 int i;
205 struct octt *t;
206
f0960b14 207 t=(struct octt*)mymalloc(sizeof(struct octt)); /* checked 4jul05 tonyc */
02d1d628
AMH
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
217int
218octt_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
240void
241octt_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
248void
249octt_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
260void
261octt_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}