/[zanavi_public1]/navit/navit/maptool/tile.c
ZANavi

Contents of /navit/navit/maptool/tile.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 8 - (show annotations) (download)
Fri Oct 28 21:39:42 2011 UTC (9 years, 1 month ago) by zoff99
File MIME type: text/plain
File size: 15385 byte(s)
import
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
21 #define _FILE_OFFSET_BITS 64
22 #define _LARGEFILE_SOURCE
23 #define _LARGEFILE64_SOURCE
24 #include <stdlib.h>
25 #include <glib.h>
26 #include <assert.h>
27 #include <string.h>
28 #include <signal.h>
29 #include <stdio.h>
30 #include <math.h>
31 #include <getopt.h>
32 #include <unistd.h>
33 #include <fcntl.h>
34 #include <sys/stat.h>
35 #include <zlib.h>
36 #include "file.h"
37 #include "item.h"
38 #include "map.h"
39 #include "zipfile.h"
40 #include "main.h"
41 #include "config.h"
42 #include "linguistics.h"
43 #include "plugin.h"
44
45 #include "maptool.h"
46
47 GList *aux_tile_list;
48 struct tile_head *tile_head_root;
49 GHashTable *strings_hash,*tile_hash,*tile_hash2;
50
51 static char* string_hash_lookup( const char* key )
52 {
53 char* key_ptr = NULL;
54
55 if ( strings_hash == NULL ) {
56 strings_hash = g_hash_table_new(g_str_hash, g_str_equal);
57 }
58
59 if ( ( key_ptr = g_hash_table_lookup(strings_hash, key )) == NULL ) {
60 key_ptr = g_strdup( key );
61 g_hash_table_insert(strings_hash, key_ptr, (gpointer)key_ptr );
62
63 }
64 return key_ptr;
65 }
66
67 static char** th_get_subtile( const struct tile_head* th, int idx )
68 {
69 char* subtile_ptr = NULL;
70 subtile_ptr = (char*)th + sizeof( struct tile_head ) + idx * sizeof( char *);
71 return (char**)subtile_ptr;
72 }
73
74 int
75 tile(struct rect *r, char *suffix, char *ret, int max, int overlap, struct rect *tr)
76 {
77 int x0,x2,x4;
78 int y0,y2,y4;
79 int xo,yo;
80 int i;
81 x0=world_bbox.l.x;
82 y0=world_bbox.l.y;
83 x4=world_bbox.h.x;
84 y4=world_bbox.h.y;
85 for (i = 0 ; i < max ; i++) {
86 x2=(x0+x4)/2;
87 y2=(y0+y4)/2;
88 xo=(x4-x0)*overlap/100;
89 yo=(y4-y0)*overlap/100;
90 if ( contains_bbox(x0,y0,x2+xo,y2+yo,r)) {
91 strcat(ret,"d");
92 x4=x2+xo;
93 y4=y2+yo;
94 } else if (contains_bbox(x2-xo,y0,x4,y2+yo,r)) {
95 strcat(ret,"c");
96 x0=x2-xo;
97 y4=y2+yo;
98 } else if (contains_bbox(x0,y2-yo,x2+xo,y4,r)) {
99 strcat(ret,"b");
100 x4=x2+xo;
101 y0=y2-yo;
102 } else if (contains_bbox(x2-xo,y2-yo,x4,y4,r)) {
103 strcat(ret,"a");
104 x0=x2-xo;
105 y0=y2-yo;
106 } else
107 break;
108 }
109 if (tr) {
110 tr->l.x=x0;
111 tr->l.y=y0;
112 tr->h.x=x4;
113 tr->h.y=y4;
114 }
115 if (suffix)
116 strcat(ret,suffix);
117 return i;
118 }
119
120 void
121 tile_bbox(char *tile, struct rect *r, int overlap)
122 {
123 struct coord c;
124 int xo,yo;
125 *r=world_bbox;
126 while (*tile) {
127 c.x=(r->l.x+r->h.x)/2;
128 c.y=(r->l.y+r->h.y)/2;
129 xo=(r->h.x-r->l.x)*overlap/100;
130 yo=(r->h.y-r->l.y)*overlap/100;
131 switch (*tile) {
132 case 'a':
133 r->l.x=c.x-xo;
134 r->l.y=c.y-yo;
135 break;
136 case 'b':
137 r->h.x=c.x+xo;
138 r->l.y=c.y-yo;
139 break;
140 case 'c':
141 r->l.x=c.x-xo;
142 r->h.y=c.y+yo;
143 break;
144 case 'd':
145 r->h.x=c.x+xo;
146 r->h.y=c.y+yo;
147 break;
148 }
149 tile++;
150 }
151 }
152
153 int
154 tile_len(char *tile)
155 {
156 int ret=0;
157 while (tile[0] >= 'a' && tile[0] <= 'd') {
158 tile++;
159 ret++;
160 }
161 return ret;
162 }
163
164 static void
165 tile_extend(char *tile, struct item_bin *ib, GList **tiles_list)
166 {
167 struct tile_head *th=NULL;
168 if (debug_tile(tile))
169 fprintf(stderr,"Tile:Writing %d bytes to '%s' (%p,%p) 0x%x "LONGLONG_FMT"\n", (ib->len+1)*4, tile, g_hash_table_lookup(tile_hash, tile), tile_hash2 ? g_hash_table_lookup(tile_hash2, tile) : NULL, ib->type, item_bin_get_id(ib));
170 if (tile_hash2)
171 th=g_hash_table_lookup(tile_hash2, tile);
172 if (!th)
173 th=g_hash_table_lookup(tile_hash, tile);
174 if (! th) {
175 th=malloc(sizeof(struct tile_head)+ sizeof( char* ) );
176 assert(th != NULL);
177 // strcpy(th->subtiles, tile);
178 th->num_subtiles=1;
179 th->total_size=0;
180 th->total_size_used=0;
181 th->zipnum=0;
182 th->zip_data=NULL;
183 th->name=string_hash_lookup(tile);
184 *th_get_subtile( th, 0 ) = th->name;
185
186 if (tile_hash2)
187 g_hash_table_insert(tile_hash2, string_hash_lookup( th->name ), th);
188 if (tiles_list)
189 *tiles_list=g_list_append(*tiles_list, string_hash_lookup( th->name ) );
190 processed_tiles++;
191 if (debug_tile(tile))
192 fprintf(stderr,"new '%s'\n", tile);
193 }
194 th->total_size+=ib->len*4+4;
195 if (debug_tile(tile))
196 fprintf(stderr,"New total size of %s(%p):%d\n", th->name, th, th->total_size);
197 g_hash_table_insert(tile_hash, string_hash_lookup( th->name ), th);
198 }
199
200 static int
201 tile_data_size(char *tile)
202 {
203 struct tile_head *th;
204 th=g_hash_table_lookup(tile_hash, tile);
205 if (! th)
206 return 0;
207 return th->total_size;
208 }
209
210 static int
211 merge_tile(char *base, char *sub)
212 {
213 struct tile_head *thb, *ths;
214 thb=g_hash_table_lookup(tile_hash, base);
215 ths=g_hash_table_lookup(tile_hash, sub);
216 if (! ths)
217 return 0;
218 if (debug_tile(base) || debug_tile(sub))
219 fprintf(stderr,"merging '%s'(%p) (%d) with '%s'(%p) (%d)\n", base, thb, thb ? thb->total_size : 0, sub, ths, ths->total_size);
220 if (! thb) {
221 thb=ths;
222 g_hash_table_remove(tile_hash, sub);
223 thb->name=string_hash_lookup(base);
224 g_hash_table_insert(tile_hash, string_hash_lookup( thb->name ), thb);
225
226 } else {
227 thb=realloc(thb, sizeof(struct tile_head)+( ths->num_subtiles+thb->num_subtiles ) * sizeof( char*) );
228 assert(thb != NULL);
229 memcpy( th_get_subtile( thb, thb->num_subtiles ), th_get_subtile( ths, 0 ), ths->num_subtiles * sizeof( char*) );
230 thb->num_subtiles+=ths->num_subtiles;
231 thb->total_size+=ths->total_size;
232 g_hash_table_insert(tile_hash, string_hash_lookup( thb->name ), thb);
233 g_hash_table_remove(tile_hash, sub);
234 g_free(ths);
235 }
236 return 1;
237 }
238
239 static gint
240 get_tiles_list_cmp(gconstpointer s1, gconstpointer s2)
241 {
242 return strcmp((char *)s1, (char *)s2);
243 }
244
245 static void
246 get_tiles_list_func(char *key, struct tile_head *th, GList **list)
247 {
248 *list=g_list_prepend(*list, key);
249 }
250
251 static GList *
252 get_tiles_list(void)
253 {
254 GList *ret=NULL;
255 g_hash_table_foreach(tile_hash, (GHFunc)get_tiles_list_func, &ret);
256 ret=g_list_sort(ret, get_tiles_list_cmp);
257 return ret;
258 }
259
260 #if 0
261 static void
262 write_tile(char *key, struct tile_head *th, gpointer dummy)
263 {
264 FILE *f;
265 char buffer[1024];
266 fprintf(stderr,"DEBUG: Writing %s\n", key);
267 strcpy(buffer,"tiles/");
268 strcat(buffer,key);
269 #if 0
270 strcat(buffer,".bin");
271 #endif
272 f=fopen(buffer, "wb+");
273 while (th) {
274 fwrite(th->data, th->size, 1, f);
275 th=th->next;
276 }
277 fclose(f);
278 }
279 #endif
280
281 static void
282 write_item(char *tile, struct item_bin *ib, FILE *reference)
283 {
284 struct tile_head *th;
285 int size;
286
287 th=g_hash_table_lookup(tile_hash2, tile);
288 if (debug_itembin(ib)) {
289 fprintf(stderr,"tile head %p\n",th);
290 }
291 if (! th)
292 th=g_hash_table_lookup(tile_hash, tile);
293 if (th) {
294 if (debug_itembin(ib)) {
295 fprintf(stderr,"Match %s %d %s\n",tile,th->process,th->name);
296 dump_itembin(ib);
297 }
298 if (th->process != 0 && th->process != 1) {
299 fprintf(stderr,"error with tile '%s' of length %d\n", tile, (int)strlen(tile));
300 abort();
301 }
302 if (! th->process) {
303 if (reference)
304 fseek(reference, 8, SEEK_CUR);
305 return;
306 }
307 if (debug_tile(tile))
308 fprintf(stderr,"Data:Writing %d bytes to '%s' (%p,%p) 0x%x\n", (ib->len+1)*4, tile, g_hash_table_lookup(tile_hash, tile), tile_hash2 ? g_hash_table_lookup(tile_hash2, tile) : NULL, ib->type);
309 size=(ib->len+1)*4;
310 if (th->total_size_used+size > th->total_size) {
311 fprintf(stderr,"Overflow in tile %s (used %d max %d item %d)\n", tile, th->total_size_used, th->total_size, size);
312 exit(1);
313 return;
314 }
315 if (reference) {
316 int offset=th->total_size_used/4;
317 fwrite(&th->zipnum, sizeof(th->zipnum), 1, reference);
318 fwrite(&offset, sizeof(th->total_size_used), 1, reference);
319 }
320 if (th->zip_data)
321 memcpy(th->zip_data+th->total_size_used, ib, size);
322 th->total_size_used+=size;
323 } else {
324 fprintf(stderr,"no tile hash found for %s\n", tile);
325 exit(1);
326 }
327 }
328
329 void
330 tile_write_item_to_tile(struct tile_info *info, struct item_bin *ib, FILE *reference, char *name)
331 {
332 if (info->write)
333 write_item(name, ib, reference);
334 else
335 tile_extend(name, ib, info->tiles_list);
336 }
337
338 void
339 tile_write_item_minmax(struct tile_info *info, struct item_bin *ib, FILE *reference, int min, int max)
340 {
341 struct rect r;
342 char buffer[1024];
343 bbox((struct coord *)(ib+1), ib->clen/2, &r);
344 buffer[0]='\0';
345 tile(&r, info->suffix, buffer, max, overlap, NULL);
346 tile_write_item_to_tile(info, ib, reference, buffer);
347 }
348
349 int
350 add_aux_tile(struct zip_info *zip_info, char *name, char *filename, int size)
351 {
352 struct aux_tile *at;
353 GList *l;
354 l=aux_tile_list;
355 while (l) {
356 at=l->data;
357 if (!strcmp(at->name, name)) {
358 fprintf(stderr,"exists %s vs %s\n",at->name, name);
359 return -1;
360 }
361 l=g_list_next(l);
362 }
363 at=g_new0(struct aux_tile, 1);
364 at->name=g_strdup(name);
365 at->filename=g_strdup(filename);
366 at->size=size;
367 aux_tile_list=g_list_append(aux_tile_list, at);
368 return zip_add_member(zip_info);
369 }
370
371 int
372 write_aux_tiles(struct zip_info *zip_info)
373 {
374 GList *l=aux_tile_list;
375 struct aux_tile *at;
376 char *buffer;
377 FILE *f;
378 int count=0;
379
380 while (l) {
381 at=l->data;
382 buffer=malloc(at->size);
383 assert(buffer != NULL);
384 f=fopen(at->filename,"rb");
385 assert(f != NULL);
386 fread(buffer, at->size, 1, f);
387 fclose(f);
388 write_zipmember(zip_info, at->name, zip_get_maxnamelen(zip_info), buffer, at->size);
389 free(buffer);
390 count++;
391 l=g_list_next(l);
392 zip_add_member(zip_info);
393 }
394 return count;
395 }
396
397 static int
398 add_tile_hash(struct tile_head *th)
399 {
400 int idx,len,maxnamelen=0;
401 char **data;
402
403 #if 0
404 g_hash_table_insert(tile_hash2, string_hash_lookup( th->name ), th);
405 #endif
406 for( idx = 0; idx < th->num_subtiles; idx++ ) {
407
408 data = th_get_subtile( th, idx );
409
410 if (debug_tile(((char *)data)) || debug_tile(th->name)) {
411 fprintf(stderr,"Parent for '%s' is '%s'\n", *data, th->name);
412 }
413
414 g_hash_table_insert(tile_hash2, *data, th);
415
416 len = strlen( *data );
417
418 if (len > maxnamelen) {
419 maxnamelen=len;
420 }
421 }
422 return maxnamelen;
423 }
424
425
426 int
427 create_tile_hash(void)
428 {
429 struct tile_head *th;
430 int len,maxnamelen=0;
431
432 tile_hash2=g_hash_table_new(g_str_hash, g_str_equal);
433 th=tile_head_root;
434 while (th) {
435 len=add_tile_hash(th);
436 if (len > maxnamelen)
437 maxnamelen=len;
438 th=th->next;
439 }
440 return maxnamelen;
441 }
442
443 static void
444 create_tile_hash_list(GList *list)
445 {
446 GList *next;
447 struct tile_head *th;
448
449 tile_hash2=g_hash_table_new(g_str_hash, g_str_equal);
450
451 next=g_list_first(list);
452 while (next) {
453 th=g_hash_table_lookup(tile_hash, next->data);
454 if (!th) {
455 fprintf(stderr,"No tile found for '%s'\n", (char *)(next->data));
456 }
457 add_tile_hash(th);
458 next=g_list_next(next);
459 }
460 }
461
462 void
463 write_tilesdir(struct tile_info *info, struct zip_info *zip_info, FILE *out)
464 {
465 int idx,len,maxlen;
466 GList *next,*tiles_list;
467 char **data;
468 struct tile_head *th,**last=NULL;
469
470 tiles_list=get_tiles_list();
471 info->tiles_list=&tiles_list;
472 if (phase == 3)
473 create_tile_hash_list(tiles_list);
474 next=g_list_first(tiles_list);
475 last=&tile_head_root;
476 maxlen=info->maxlen;
477 if (! maxlen) {
478 while (next) {
479 if (strlen(next->data) > maxlen)
480 maxlen=strlen(next->data);
481 next=g_list_next(next);
482 }
483 }
484 len=maxlen;
485 while (len >= 0) {
486 #if 0
487 fprintf(stderr,"PROGRESS: collecting tiles with len=%d\n", len);
488 #endif
489 next=g_list_first(tiles_list);
490 while (next) {
491 if (strlen(next->data) == len) {
492 th=g_hash_table_lookup(tile_hash, next->data);
493 if (phase == 3) {
494 *last=th;
495 last=&th->next;
496 th->next=NULL;
497 th->zipnum=zip_get_zipnum(zip_info);
498 fprintf(out,"%s:%d",(char *)next->data,th->total_size);
499
500 for ( idx = 0; idx< th->num_subtiles; idx++ ){
501 data= th_get_subtile( th, idx );
502 fprintf(out,":%s", *data);
503 }
504
505 fprintf(out,"\n");
506 }
507 if (th->name[strlen(info->suffix)])
508 index_submap_add(info, th);
509 zip_add_member(zip_info);
510 processed_tiles++;
511 }
512 next=g_list_next(next);
513 }
514 len--;
515 }
516 if (info->suffix[0] && info->write) {
517 struct item_bin *item_bin=init_item(type_submap);
518 item_bin_add_coord_rect(item_bin, &world_bbox);
519 item_bin_add_attr_range(item_bin, attr_order, 0, 255);
520 item_bin_add_attr_int(item_bin, attr_zipfile_ref, zip_get_zipnum(zip_info)-1);
521 item_bin_write(item_bin, zip_get_index(zip_info));
522 }
523 }
524
525 void
526 merge_tiles(struct tile_info *info)
527 {
528 struct tile_head *th;
529 char basetile[1024];
530 char subtile[1024];
531 GList *tiles_list_sorted,*last;
532 int i,i_min,len,size_all,size[5],size_min,work_done;
533 long long zip_size;
534
535 do {
536 tiles_list_sorted=get_tiles_list();
537 fprintf(stderr,"PROGRESS: sorting %d tiles\n", g_list_length(tiles_list_sorted));
538 tiles_list_sorted=g_list_sort(tiles_list_sorted, (GCompareFunc)strcmp);
539 fprintf(stderr,"PROGRESS: sorting %d tiles done\n", g_list_length(tiles_list_sorted));
540 last=g_list_last(tiles_list_sorted);
541 zip_size=0;
542 while (last) {
543 th=g_hash_table_lookup(tile_hash, last->data);
544 zip_size+=th->total_size;
545 last=g_list_previous(last);
546 }
547 last=g_list_last(tiles_list_sorted);
548 work_done=0;
549 while (last) {
550 processed_tiles++;
551 len=tile_len(last->data);
552 if (len >= 1) {
553 strcpy(basetile,last->data);
554 basetile[len-1]='\0';
555 strcat(basetile, info->suffix);
556 strcpy(subtile,last->data);
557 for (i = 0 ; i < 4 ; i++) {
558 subtile[len-1]='a'+i;
559 size[i]=tile_data_size(subtile);
560 }
561 size[4]=tile_data_size(basetile);
562 size_all=size[0]+size[1]+size[2]+size[3]+size[4];
563 if (size_all < 65536 && size_all > 0 && size_all != size[4]) {
564 for (i = 0 ; i < 4 ; i++) {
565 subtile[len-1]='a'+i;
566 work_done+=merge_tile(basetile, subtile);
567 }
568 } else {
569 for (;;) {
570 size_min=size_all;
571 i_min=-1;
572 for (i = 0 ; i < 4 ; i++) {
573 if (size[i] && size[i] < size_min) {
574 size_min=size[i];
575 i_min=i;
576 }
577 }
578 if (i_min == -1)
579 break;
580 if (size[4]+size_min >= 65536)
581 break;
582 subtile[len-1]='a'+i_min;
583 work_done+=merge_tile(basetile, subtile);
584 size[4]+=size[i_min];
585 size[i_min]=0;
586 }
587 }
588 }
589 last=g_list_previous(last);
590 }
591 g_list_free(tiles_list_sorted);
592 fprintf(stderr,"PROGRESS: merged %d tiles\n", work_done);
593 } while (work_done);
594 }
595
596 struct attr map_information_attrs[32];
597
598 void
599 index_init(struct zip_info *info, int version)
600 {
601 struct item_bin *item_bin;
602 int i;
603 map_information_attrs[0].type=attr_version;
604 map_information_attrs[0].u.num=version;
605 item_bin=init_item(type_map_information);
606 for (i = 0 ; i < 32 ; i++) {
607 if (!map_information_attrs[i].type)
608 break;
609 item_bin_add_attr(item_bin, &map_information_attrs[i]);
610 }
611 item_bin_write(item_bin, zip_get_index(info));
612 }
613
614 void
615 index_submap_add(struct tile_info *info, struct tile_head *th)
616 {
617 int tlen=tile_len(th->name);
618 int len=tlen;
619 char index_tile[len+1+strlen(info->suffix)];
620 struct rect r;
621 struct item_bin *item_bin;
622
623 strcpy(index_tile, th->name);
624 if (len > 6)
625 len=6;
626 else
627 len=0;
628 index_tile[len]=0;
629 strcat(index_tile, info->suffix);
630 tile_bbox(th->name, &r, overlap);
631
632 item_bin=init_item(type_submap);
633 item_bin_add_coord_rect(item_bin, &r);
634 item_bin_add_attr_range(item_bin, attr_order, (tlen > 4)?tlen-4 : 0, 255);
635 item_bin_add_attr_int(item_bin, attr_zipfile_ref, th->zipnum);
636 tile_write_item_to_tile(info, item_bin, NULL, index_tile);
637 }

   
Visit the ZANavi Wiki