- the segments parameter supplied to the fountain filter and the
[imager.git] / datatypes.c
CommitLineData
7ac6a2e9 1#include "imio.h"
02d1d628
AMH
2#include "datatypes.h"
3#include <stdlib.h>
4#include <stdio.h>
5
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;
15 struct i_bitmap *btm;
16 btm=(struct i_bitmap*)mymalloc(sizeof(struct i_bitmap));
17 btm->data=(char*)mymalloc((xsize*ysize+8)/8);
18 btm->xsize=xsize;
19 btm->ysize=ysize;
20 for(i=0;i<(xsize*ysize+8)/8;i++) btm->data[i]=0; /* Is this always needed */
21 return btm;
22}
23
24
25void
26btm_destroy(struct i_bitmap *btm) {
27 myfree(btm->data);
28 myfree(btm);
29}
30
31
32int
33btm_test(struct i_bitmap *btm,int x,int y) {
34 int btno;
35 if (x<0 || x>btm->xsize-1 || y<0 || y>btm->ysize-1) return 0;
36 btno=btm->xsize*y+x;
37 return (1<<(btno%8))&(btm->data[btno/8]);
38}
39
40void
41btm_set(struct i_bitmap *btm,int x,int y) {
42 int btno;
e25e59b1 43 if (x<0 || x>btm->xsize-1 || y<0 || y>btm->ysize-1) abort();
02d1d628
AMH
44 btno=btm->xsize*y+x;
45 btm->data[btno/8]|=1<<(btno%8);
46}
47
48
49
50
51
52/*
a73aeb5f 53 Bucketed linked list - stack type
02d1d628
AMH
54*/
55
56struct llink *
57llink_new(struct llink* p,int size) {
58 struct llink *l;
a73aeb5f
AMH
59 l = mymalloc(sizeof(struct llink));
60 l->n = NULL;
61 l->p = p;
62 l->fill = 0;
63 l->data = mymalloc(size);
02d1d628
AMH
64 return l;
65}
66
67/* free's the data pointer, itself, and sets the previous' next pointer to null */
68
69void
70llink_destroy(struct llink* l) {
71 if (l->p != NULL) { l->p->n=NULL; }
72 myfree(l->data);
73 myfree(l);
74}
75
76
77/* if it returns true there wasn't room for the
78 item on the link */
79
80int
81llist_llink_push(struct llist *lst, struct llink *lnk,void *data) {
82 int multip;
a73aeb5f 83 multip = lst->multip;
02d1d628
AMH
84
85 /* fprintf(stderr,"llist_llink_push: data=0x%08X -> 0x%08X\n",data,*(int*)data);
86 fprintf(stderr,"ssize = %d, multip = %d, fill = %d\n",lst->ssize,lst->multip,lnk->fill); */
87 if (lnk->fill == lst->multip) return 1;
88 /* memcpy((char*)(lnk->data)+lnk->fill*lst->ssize,data,lst->ssize); */
89 memcpy((char*)(lnk->data)+lnk->fill*lst->ssize,data,lst->ssize);
90
91 /* printf("data=%X res=%X\n",*(int*)data,*(int*)(lnk->data));*/
92 lnk->fill++;
93 lst->count++;
94 return 0;
95}
96
97struct llist *
98llist_new(int multip, int ssize) {
99 struct llist *l;
a73aeb5f
AMH
100 l = mymalloc(sizeof(struct llist));
101 l->h = NULL;
102 l->t = NULL;
103 l->multip = multip;
104 l->ssize = ssize;
105 l->count = 0;
02d1d628
AMH
106 return l;
107}
108
109void
110llist_push(struct llist *l,void *data) {
a73aeb5f
AMH
111 int ssize = l->ssize;
112 int multip = l->multip;
02d1d628 113
a73aeb5f
AMH
114 /* fprintf(stderr,"llist_push: data=0x%08X\n",data);
115 fprintf(stderr,"Chain size: %d\n", l->count); */
116
117 if (l->t == NULL) {
118 l->t = l->h = llink_new(NULL,ssize*multip); /* Tail is empty - list is empty */
119 /* fprintf(stderr,"Chain empty - extended\n"); */
120 }
02d1d628
AMH
121 else { /* Check for overflow in current tail */
122 if (l->t->fill >= l->multip) {
a73aeb5f 123 struct llink* nt = llink_new(l->t, ssize*multip);
02d1d628
AMH
124 l->t->n=nt;
125 l->t=nt;
126 /* fprintf(stderr,"Chain extended\n"); */
127 }
128 }
129 /* fprintf(stderr,"0x%08X\n",l->t); */
a73aeb5f
AMH
130 if (llist_llink_push(l,l->t,data)) {
131 m_fatal(3, "out of memory\n");
132 }
02d1d628
AMH
133}
134
135/* returns 0 if the list is empty */
136
137int
138llist_pop(struct llist *l,void *data) {
139 /* int ssize=l->ssize;
140 int multip=l->multip;*/
141 if (l->t == NULL) return 0;
142 l->t->fill--;
143 l->count--;
02d1d628
AMH
144 memcpy(data,(char*)(l->t->data)+l->ssize*l->t->fill,l->ssize);
145
146 if (!l->t->fill) { /* This link empty */
a73aeb5f
AMH
147 if (l->t->p == NULL) { /* and it's the only link */
148 llink_destroy(l->t);
149 l->h = l->t = NULL;
150 }
02d1d628
AMH
151 else {
152 l->t=l->t->p;
153 llink_destroy(l->t->n);
154 }
155 }
156 return 1;
157}
158
159void
160llist_dump(struct llist *l) {
161 int k,j;
162 int i=0;
163 struct llink *lnk;
164 lnk=l->h;
165 while(lnk != NULL) {
166 for(j=0;j<lnk->fill;j++) {
167 /* memcpy(&k,(char*)(lnk->data)+l->ssize*j,sizeof(void*));*/
168 memcpy(&k,(char*)(lnk->data)+l->ssize*j,sizeof(void*));
169 printf("%d - %X\n",i,k);
170 i++;
171 }
172 lnk=lnk->n;
173 }
174}
175
176void
177llist_destroy(struct llist *l) {
178 struct llink *t,*lnk = l->h;
179 while( lnk != NULL ) {
180 t=lnk;
181 lnk=lnk->n;
182 myfree(t);
183 }
184 myfree(l);
185}
186
187
188
189
190
191
192/*
193 Oct-tree implementation
194*/
195
196struct octt *
197octt_new() {
198 int i;
199 struct octt *t;
200
201 t=(struct octt*)mymalloc(sizeof(struct octt));
202 for(i=0;i<8;i++) t->t[i]=NULL;
203 t->cnt=0;
204 return t;
205}
206
207
208/* returns 1 if the colors wasn't in the octtree already */
209
210
211int
212octt_add(struct octt *ct,unsigned char r,unsigned char g,unsigned char b) {
213 struct octt *c;
214 int i,cm;
215 int ci,idx[8];
216 int rc;
217 rc=0;
218 c=ct;
219 /* printf("[r,g,b]=[%d,%d,%d]\n",r,g,b); */
220 ct->cnt++;
221 for(i=7;i>-1;i--) {
222 cm=1<<i;
223 ci=((!!(r&cm))<<2)+((!!(g&cm))<<1)+!!(b&cm);
224 /* printf("idx[%d]=%d\n",i,ci); */
225 if (c->t[ci] == NULL) { c->t[ci]=octt_new(); rc=1; }
226 c=c->t[ci];
227 c->cnt++;
228 idx[i]=ci;
229 }
230 return rc;
231}
232
233
234void
235octt_delete(struct octt *ct) {
236 int i;
237 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 */
238 myfree(ct);
239}
240
241
242void
243octt_dump(struct octt *ct) {
244 int i;
245 /* printf("node [0x%08X] -> (%d)\n",ct,ct->cnt); */
246 for(i=0;i<8;i++) if (ct->t[i] != NULL) printf("[ %d ] -> 0x%08X\n",i,(unsigned int)ct->t[i]);
247 for(i=0;i<8;i++) if (ct->t[i] != NULL) octt_dump(ct->t[i]);
248}
249
250/* note that all calls of octt_count are operating on the same overflow
251 variable so all calls will know at the same time if an overflow
252 has occured and stops there. */
253
254void
255octt_count(struct octt *ct,int *tot,int max,int *overflow) {
256 int i,c;
257 c=0;
258 if (!(*overflow)) return;
259 for(i=0;i<8;i++) if (ct->t[i]!=NULL) {
260 octt_count(ct->t[i],tot,max,overflow);
261 c++;
262 }
263 if (!c) (*tot)++;
264 if ( (*tot) > (*overflow) ) *overflow=0;
265}