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