5.005_03 compatible use of mkdir
[imager.git] / datatypes.c
CommitLineData
02d1d628
AMH
1#include <stdlib.h>
2#include <stdio.h>
35891892 3#include <string.h>
e310e5f9 4#include "imager.h"
02d1d628
AMH
5
6/*
7 2d bitmask with test and set operations
8*/
9
10struct i_bitmap*
11btm_new(int xsize,int ysize) {
12 int i;
f0960b14 13 int bytes;
02d1d628 14 struct i_bitmap *btm;
f0960b14
TC
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 */
02d1d628
AMH
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
29void
30btm_destroy(struct i_bitmap *btm) {
31 myfree(btm->data);
32 myfree(btm);
33}
34
35
36int
37btm_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
44void
45btm_set(struct i_bitmap *btm,int x,int y) {
46 int btno;
e25e59b1 47 if (x<0 || x>btm->xsize-1 || y<0 || y>btm->ysize-1) abort();
02d1d628
AMH
48 btno=btm->xsize*y+x;
49 btm->data[btno/8]|=1<<(btno%8);
50}
51
52
53
54
55
56/*
a73aeb5f 57 Bucketed linked list - stack type
02d1d628
AMH
58*/
59
60struct llink *
61llink_new(struct llink* p,int size) {
62 struct llink *l;
f0960b14 63 l = mymalloc(sizeof(struct llink)); /* checked 4jul05 tonyc */
a73aeb5f
AMH
64 l->n = NULL;
65 l->p = p;
66 l->fill = 0;
f0960b14 67 l->data = mymalloc(size); /* checked 4jul05 tonyc - depends on caller to llist_push */
02d1d628
AMH
68 return l;
69}
70
71/* free's the data pointer, itself, and sets the previous' next pointer to null */
72
73void
74llink_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
84int
85llist_llink_push(struct llist *lst, struct llink *lnk,void *data) {
86 int multip;
a73aeb5f 87 multip = lst->multip;
02d1d628
AMH
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
101struct llist *
102llist_new(int multip, int ssize) {
103 struct llist *l;
f0960b14 104 l = mymalloc(sizeof(struct llist)); /* checked 4jul05 tonyc */
a73aeb5f
AMH
105 l->h = NULL;
106 l->t = NULL;
107 l->multip = multip;
108 l->ssize = ssize;
109 l->count = 0;
02d1d628
AMH
110 return l;
111}
112
113void
114llist_push(struct llist *l,void *data) {
a73aeb5f
AMH
115 int ssize = l->ssize;
116 int multip = l->multip;
02d1d628 117
a73aeb5f
AMH
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 }
02d1d628
AMH
125 else { /* Check for overflow in current tail */
126 if (l->t->fill >= l->multip) {
a73aeb5f 127 struct llink* nt = llink_new(l->t, ssize*multip);
02d1d628
AMH
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); */
a73aeb5f 134 if (llist_llink_push(l,l->t,data)) {
b1e96952 135 i_fatal(3, "out of memory\n");
a73aeb5f 136 }
02d1d628
AMH
137}
138
139/* returns 0 if the list is empty */
140
141int
142llist_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--;
02d1d628
AMH
148 memcpy(data,(char*)(l->t->data)+l->ssize*l->t->fill,l->ssize);
149
150 if (!l->t->fill) { /* This link empty */
a73aeb5f
AMH
151 if (l->t->p == NULL) { /* and it's the only link */
152 llink_destroy(l->t);
153 l->h = l->t = NULL;
154 }
02d1d628
AMH
155 else {
156 l->t=l->t->p;
157 llink_destroy(l->t->n);
158 }
159 }
160 return 1;
161}
162
163void
164llist_dump(struct llist *l) {
165 int k,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 - %X\n",i,k);
174 i++;
175 }
176 lnk=lnk->n;
177 }
178}
179
180void
181llist_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
200struct octt *
201octt_new() {
202 int i;
203 struct octt *t;
204
f0960b14 205 t=(struct octt*)mymalloc(sizeof(struct octt)); /* checked 4jul05 tonyc */
02d1d628
AMH
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
215int
216octt_add(struct octt *ct,unsigned char r,unsigned char g,unsigned char b) {
217 struct octt *c;
218 int i,cm;
219 int ci,idx[8];
220 int rc;
221 rc=0;
222 c=ct;
223 /* printf("[r,g,b]=[%d,%d,%d]\n",r,g,b); */
224 ct->cnt++;
225 for(i=7;i>-1;i--) {
226 cm=1<<i;
227 ci=((!!(r&cm))<<2)+((!!(g&cm))<<1)+!!(b&cm);
228 /* printf("idx[%d]=%d\n",i,ci); */
229 if (c->t[ci] == NULL) { c->t[ci]=octt_new(); rc=1; }
230 c=c->t[ci];
231 c->cnt++;
232 idx[i]=ci;
233 }
234 return rc;
235}
236
237
238void
239octt_delete(struct octt *ct) {
240 int i;
241 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 */
242 myfree(ct);
243}
244
245
246void
247octt_dump(struct octt *ct) {
248 int i;
249 /* printf("node [0x%08X] -> (%d)\n",ct,ct->cnt); */
250 for(i=0;i<8;i++) if (ct->t[i] != NULL) printf("[ %d ] -> 0x%08X\n",i,(unsigned int)ct->t[i]);
251 for(i=0;i<8;i++) if (ct->t[i] != NULL) octt_dump(ct->t[i]);
252}
253
254/* note that all calls of octt_count are operating on the same overflow
255 variable so all calls will know at the same time if an overflow
256 has occured and stops there. */
257
258void
259octt_count(struct octt *ct,int *tot,int max,int *overflow) {
260 int i,c;
261 c=0;
262 if (!(*overflow)) return;
263 for(i=0;i<8;i++) if (ct->t[i]!=NULL) {
264 octt_count(ct->t[i],tot,max,overflow);
265 c++;
266 }
267 if (!c) (*tot)++;
268 if ( (*tot) > (*overflow) ) *overflow=0;
269}