Commit | Line | Data |
---|---|---|
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 | ||
12 | struct i_bitmap* | |
13 | btm_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 | ||
25 | void | |
26 | btm_destroy(struct i_bitmap *btm) { | |
27 | myfree(btm->data); | |
28 | myfree(btm); | |
29 | } | |
30 | ||
31 | ||
32 | int | |
33 | btm_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 | ||
40 | void | |
41 | btm_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 | ||
55 | struct llink * | |
56 | llink_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 | ||
68 | void | |
69 | llink_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 | ||
79 | int | |
80 | llist_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 | ||
96 | struct llist * | |
97 | llist_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 | ||
107 | void | |
108 | llist_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 | ||
129 | int | |
130 | llist_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 | ||
149 | void | |
150 | llist_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 | ||
166 | void | |
167 | llist_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 | ||
186 | struct octt * | |
187 | octt_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 | ||
201 | int | |
202 | octt_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 | ||
224 | void | |
225 | octt_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 | ||
232 | void | |
233 | octt_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 | ||
244 | void | |
245 | octt_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 | } |