/[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 - (hide 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 zoff99 2 /**
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