/[zanavi_public1]/navit/navit/map/mg/block.c
ZANavi

Contents of /navit/navit/map/mg/block.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2 - (show annotations) (download)
Fri Oct 28 21:19:04 2011 UTC (12 years, 5 months ago) by zoff99
File MIME type: text/plain
File size: 8350 byte(s)
import files
1 /**
2 * Navit, a modular navigation system.
3 * Copyright (C) 2005-2008 Navit Team
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * version 2 as published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the
16 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 */
19
20 #include <stdio.h>
21 #include <string.h>
22 #include "debug.h"
23 #include "mg.h"
24
25
26 int block_lin_count,block_idx_count,block_active_count,block_mem,block_active_mem;
27
28 struct block_index_item {
29 /*unsigned int blocknum;
30 unsigned int blocks;*/
31 unsigned char p[8];
32 };
33 static inline unsigned int block_index_item_get_blocknum(struct block_index_item * blk) { unsigned char *p = blk->p; return get_u32(&p); }
34 static inline unsigned int block_index_item_get_blocks(struct block_index_item * blk) { unsigned char *p = blk->p+4; return get_u32(&p); }
35
36 struct block_index {
37 /* unsigned int blocks;
38 unsigned int size;
39 unsigned int next;
40 struct block_index_item list[0];*/
41 unsigned char p[12];
42 };
43 static inline unsigned int block_index_get_blocks(struct block_index * blk) { unsigned char *p = blk->p; return get_u32(&p); }
44 static inline unsigned int block_index_get_size(struct block_index * blk) { unsigned char *p = blk->p+4; return get_u32(&p); }
45 static inline unsigned int block_index_get_next(struct block_index * blk) { unsigned char *p = blk->p+8; return get_u32(&p); }
46 static inline struct block_index_item * block_index_get_list(struct block_index * blk) { return (struct block_index_item *)(blk->p+12); }
47
48 static struct block *
49 block_get(unsigned char **p)
50 {
51 struct block *ret=(struct block *)(*p);
52 *p += sizeof(*ret);
53 return ret;
54 }
55
56
57 static struct block *
58 block_get_byid(struct file *file, int id, unsigned char **p_ret)
59 {
60 struct block_index *blk_idx;
61 int blk_num,max;
62
63
64 blk_idx=(struct block_index *)(file->begin+0x1000);
65 max=(block_index_get_size(blk_idx)-sizeof(struct block_index))/sizeof(struct block_index_item);
66 block_mem+=24;
67 while (id >= max) {
68 blk_idx=(struct block_index *)(file->begin+block_index_get_next(blk_idx)*512);
69 id-=max;
70 }
71 blk_num=block_index_item_get_blocknum(&block_index_get_list(blk_idx)[id]);
72
73 *p_ret=file->begin+blk_num*512;
74 return block_get(p_ret);
75 }
76
77 int
78 block_get_byindex(struct file *file, int idx, struct block_priv *blk)
79 {
80 dbg(1,"idx=%d\n", idx);
81 blk->b=block_get_byid(file, idx, &blk->p);
82 blk->block_start=(unsigned char *)(blk->b);
83 blk->p_start=blk->p;
84 blk->end=blk->block_start+block_get_size(blk->b);
85
86 return 1;
87 }
88
89 static void
90 block_setup_tags(struct map_rect_priv *mr)
91 {
92 int len;
93 unsigned char *p,*t;
94 char *str;
95
96 mr->b.binarytree=0;
97
98 p=mr->file->begin+0x0c;
99 while (*p) {
100 str=get_string(&p);
101 len=get_u32_unal(&p);
102 t=p;
103 /* printf("String '%s' len %d\n", str, len); */
104 if (! strcmp(str,"FirstBatBlock")) {
105 /* printf("%ld\n", get_u32_unal(&t)); */
106 } else if (! strcmp(str,"MaxBlockSize")) {
107 /* printf("%ld\n", get_u32_unal(&t)); */
108 } else if (! strcmp(str,"FREE_BLOCK_LIST")) {
109 /* printf("%ld\n", get_u32_unal(&t)); */
110 } else if (! strcmp(str,"TotalRect")) {
111 mr->b.b_rect.lu.x=get_u32_unal(&t);
112 mr->b.b_rect.lu.y=get_u32_unal(&t);
113 mr->b.b_rect.rl.x=get_u32_unal(&t);
114 mr->b.b_rect.rl.y=get_u32_unal(&t);
115 /* printf("0x%x,0x%x-0x%x,0x%x\n", mr->b.b_rect.lu.x, mr->b.b_rect.lu.y, mr->b.b_rect.rl.x, mr->b.b_rect.rl.y); */
116 } else if (! strcmp(str,"Version")) {
117 /* printf("0x%lx\n", get_u32_unal(&t)); */
118 } else if (! strcmp(str,"Categories")) {
119 /* printf("0x%x\n", get_u16(&t)); */
120 } else if (! strcmp(str,"binaryTree")) {
121 mr->b.binarytree=get_u32_unal(&t);
122 /* printf("%d\n", mr->b.binarytree); */
123 } else if (! strcmp(str,"CategorySets")) {
124 /* printf("0x%x\n", get_u16(&t)); */
125 } else if (! strcmp(str,"Kommentar")) {
126 /* printf("%s\n", get_string(&t)); */
127 }
128 p+=len;
129 }
130 }
131
132 #if 0
133 static void
134 block_rect_print(struct coord_rect *r)
135 {
136 printf ("0x%x,0x%x-0x%x,0x%x (0x%x,0x%x)", r->lu.x, r->lu.y, r->rl.x, r->rl.y, r->lu.x/2+r->rl.x/2,r->lu.y/2+r->rl.y/2);
137 }
138 #endif
139
140 static void
141 block_rect_same(struct coord_rect *r1, struct coord_rect *r2)
142 {
143 dbg_assert(r1->lu.x==r2->lu.x);
144 dbg_assert(r1->lu.y==r2->lu.y);
145 dbg_assert(r1->rl.x==r2->rl.x);
146 dbg_assert(r1->rl.y==r2->rl.y);
147 }
148
149 int
150 block_init(struct map_rect_priv *mr)
151 {
152 mr->b.block_num=-1;
153 mr->b.bt.b=NULL;
154 mr->b.bt.next=0;
155 block_setup_tags(mr);
156 if (mr->b.binarytree) {
157 mr->b.bt.next=mr->b.binarytree;
158 mr->b.bt.p=NULL;
159 mr->b.bt.block_count=0;
160 }
161 if (mr->cur_sel && !coord_rect_overlap(&mr->cur_sel->u.c_rect, &mr->b.b_rect))
162 return 0;
163 return block_next(mr);
164 }
165
166
167 int
168 block_next_lin(struct map_rect_priv *mr)
169 {
170 struct coord_rect r;
171 for (;;) {
172 block_lin_count++;
173 block_mem+=sizeof(struct block *);
174 mr->b.block_num++;
175 if (! mr->b.block_num)
176 mr->b.p=mr->file->begin+0x2000;
177 else
178 mr->b.p=mr->b.block_start+block_get_blocks(mr->b.b)*512;
179 if (mr->b.p >= mr->file->end) {
180 dbg(1,"end of blocks %p vs %p\n", mr->b.p, mr->file->end);
181 return 0;
182 }
183 mr->b.block_start=mr->b.p;
184 mr->b.b=block_get(&mr->b.p);
185 mr->b.p_start=mr->b.p;
186 mr->b.end=mr->b.block_start+block_get_size(mr->b.b);
187 if (block_get_count(mr->b.b) == -1) {
188 dbg(1,"empty blocks\n");
189 return 0;
190 }
191 block_get_r(mr->b.b, &r);
192 if (!mr->cur_sel || coord_rect_overlap(&mr->cur_sel->u.c_rect, &r)) {
193 block_active_count++;
194 block_active_mem+=block_get_blocks(mr->b.b)*512-sizeof(struct block *);
195 dbg(1,"block ok\n");
196 return 1;
197 }
198 dbg(2,"block not in cur_sel\n");
199 }
200 }
201
202 int
203 block_next(struct map_rect_priv *mr)
204 {
205 int blk_num,coord,r_h,r_w;
206 struct block_bt_priv *bt=&mr->b.bt;
207 struct coord_rect r;
208
209 if (!mr->b.binarytree || ! mr->cur_sel)
210 return block_next_lin(mr);
211 for (;;) {
212 if (! bt->p) {
213 dbg(1,"block 0x%x\n", bt->next);
214 if (bt->next == -1)
215 return 0;
216 bt->b=block_get_byid(mr->file, bt->next, &bt->p);
217 bt->end=(unsigned char *)mr->b.bt.b+block_get_size(mr->b.bt.b);
218 bt->next=block_get_next(bt->b);
219 bt->order=0;
220 dbg(1,"size 0x%x next 0x%x\n", block_get_size(bt->b), block_get_next(bt->b));
221 if (! mr->b.bt.block_count) {
222 #if 0
223 if (debug) {
224 printf("idx rect ");
225 block_rect_print(&mr->b.bt.b->r);
226 }
227 #endif
228 block_get_r(bt->b, &bt->r);
229 bt->r_curr=bt->r;
230 coord=get_u32(&mr->b.bt.p);
231 } else {
232 bt->p=(unsigned char *)bt->b+0xc;
233 }
234 bt->block_count++;
235 }
236 while (mr->b.bt.p < mr->b.bt.end) {
237 block_idx_count++;
238 blk_num=get_u32(&mr->b.bt.p);
239 coord=get_u32(&mr->b.bt.p);
240 block_mem+=8;
241 dbg(1,"%p vs %p coord 0x%x ", mr->b.bt.end, mr->b.bt.p, coord);
242 dbg(1,"block 0x%x", blk_num);
243
244 r_w=bt->r_curr.rl.x-bt->r_curr.lu.x;
245 r_h=bt->r_curr.lu.y-bt->r_curr.rl.y;
246 #if 0
247 if (debug) {
248 printf(" rect1 ");
249 block_rect_print(&bt->r_curr);
250 printf(" %dx%d", r_w, r_h);
251 }
252 #endif
253 mr->b.b=NULL;
254 if (blk_num != -1) {
255 block_mem+=8;
256 if (coord_rect_overlap(&mr->cur_sel->u.c_rect, &bt->r_curr)) {
257 mr->b.b=block_get_byid(mr->file, blk_num, &mr->b.p);
258 mr->b.block_num=blk_num;
259 dbg_assert(mr->b.b != NULL);
260 mr->b.block_start=(unsigned char *)(mr->b.b);
261 mr->b.p_start=mr->b.p;
262 mr->b.end=mr->b.block_start+block_get_size(mr->b.b);
263 block_get_r(mr->b.b, &r);
264 block_rect_same(&r, &bt->r_curr);
265 }
266 }
267 if (coord != -1) {
268 bt->stack[bt->stackp]=bt->r_curr;
269 if (r_w > r_h) {
270 bt->r_curr.rl.x=coord;
271 bt->stack[bt->stackp].lu.x=coord+1;
272 } else {
273 bt->r_curr.lu.y=coord;
274 bt->stack[bt->stackp].rl.y=coord+1;
275 }
276 bt->stackp++;
277 dbg_assert(bt->stackp < BT_STACK_SIZE);
278 } else {
279 if (bt->stackp) {
280 bt->stackp--;
281 bt->r_curr=bt->stack[bt->stackp];
282 } else {
283 bt->r_curr=bt->r;
284 bt->order++;
285 if (bt->order > 100)
286 return 0;
287 }
288 }
289 if (mr->b.b) {
290 block_active_count++;
291 block_active_mem+=block_get_blocks(mr->b.b)*512;
292 return 1;
293 }
294 }
295 bt->p=NULL;
296 }
297 return 0;
298 }

   
Visit the ZANavi Wiki