navit/navit/maptool/ch.c

   1 #include <math.h>
   2 #include <stdlib.h>
   3 #include "maptool.h"
   4 #include "coord.h"
   5 #include "file.h"
   6 #include "debug.h"
   7
   8 struct ch_edge {
   9         int flags;
  10         int weight;
  11         struct item_id target,middle;
  12 };
  13
  14 struct node {
  15         int first_edge;
  16         int dummy;
  17 } *nodes;
  18 int node_count;
  19
  20 struct edge {
  21         unsigned target:26;
  22         unsigned scedge1:6;
  23         unsigned weight:28;
  24         unsigned type:2;
  25         unsigned flags:2;
  26         unsigned int edge_count;
  27         unsigned scedge2:6;
  28         unsigned scmiddle:26;
  29 } *edges;
  30
  31 int edge_count;
  32
  33 struct newnode {
  34         int newnode;
  35 } *newnodes;
  36
  37 int newnode_count;
  38
  39 GHashTable *newnode_hash;
  40
  41 struct edge_hash_item {
  42         int first,last;
  43 };
  44
  45
  46 GHashTable *edge_hash;
  47
  48 struct file *sgr,*ddsg_node_index;
  49
  50 struct coord *node_index;
  51
  52 GHashTable *sgr_nodes_hash;
  53
  54 static int ch_levels=14;
  55
  56 static int
  57 road_speed(enum item_type type)
  58 {
  59         switch (type) {
  60         case type_street_0:
  61         case type_street_1_city:
  62         case type_living_street:
  63         case type_street_service:
  64         case type_track_gravelled:
  65         case type_track_unpaved:
  66                 return 10;
  67         case type_street_2_city:
  68         case type_track_paved:
  69                 return 30;
  70         case type_street_3_city:
  71                 return 40;
  72         case type_street_4_city:
  73                 return 50;
  74         case type_highway_city:
  75                 return 80;
  76         case type_street_1_land:
  77                 return 60;
  78         case type_street_2_land:
  79                 return 65;
  80         case type_street_3_land:
  81                 return 70;
  82         case type_street_4_land:
  83                 return 80;
  84         case type_street_n_lanes:
  85                 return 120;
  86         case type_highway_land:
  87                 return 120;
  88         case type_ramp:
  89                 return 40;
  90         case type_roundabout:
  91                 return 10;
  92         case type_ferry:
  93                 return 40;
  94         default:
  95                 return 0;
  96         }
  97 }
  98
  99 static void
 100 coord_slice_free(void *data)
 101 {
 102         g_slice_free(struct coord, data);
 103 }
 104
 105
 106 static GHashTable *
 107 coord_hash_new(void)
 108 {
 109         return g_hash_table_new_full(coord_hash, coord_equal, coord_slice_free, NULL);
 110 }
 111
 112 static void
 113 item_id_slice_free(void *data)
 114 {
 115         g_slice_free(struct item_id, data);
 116 }
 117
 118 #define sq(x) ((double)(x)*(x))
 119
 120 static void
 121 add_node_to_hash(FILE *idx, GHashTable *hash, struct coord *c, int *nodes)
 122 {
 123         if (! g_hash_table_lookup(hash, c)) {
 124                 struct coord *ct=g_slice_new(struct coord);
 125                 *ct=*c;
 126                 fwrite(c, sizeof(*c), 1, idx);
 127                 (*nodes)++;
 128                 g_hash_table_insert(hash, ct, (void *)(*nodes));
 129         }
 130
 131 }
 132
 133 static void
 134 edge_hash_slice_free(void *data)
 135 {
 136         g_slice_free(struct edge_hash_item, data);
 137 }
 138
 139 static guint
 140 edge_hash_hash(gconstpointer key)
 141 {
 142         const struct edge_hash_item *itm=key;
 143         return itm->first*2654435761UL+itm->last;
 144 }
 145
 146 static gboolean
 147 edge_hash_equal(gconstpointer a, gconstpointer b)
 148 {
 149         const struct edge_hash_item *itm_a=a;
 150         const struct edge_hash_item *itm_b=b;
 151         return (itm_a->first == itm_b->first && itm_a->last == itm_b->last);
 152 }
 153
 154
 155
 156 static void
 157 ch_generate_ddsg(FILE *in, FILE *ref, FILE *idx, FILE *ddsg)
 158 {
 159         GHashTable *hash=coord_hash_new();
 160         struct item_bin *ib;
 161         int nodes=0,edges=0;
 162
 163         while ((ib=read_item(in))) {
 164                 int ccount=ib->clen/2;
 165                 struct coord *c=(struct coord *)(ib+1);
 166                 if (road_speed(ib->type)) {
 167                         add_node_to_hash(idx, hash, &c[0], &nodes);
 168                         add_node_to_hash(idx, hash, &c[ccount-1], &nodes);
 169                         edges++;
 170                 }
 171         }
 172         edge_hash=g_hash_table_new_full(edge_hash_hash, edge_hash_equal, edge_hash_slice_free, item_id_slice_free);
 173         fseek(in, 0, SEEK_SET);
 174         fprintf(ddsg,"d\n");
 175         fprintf(ddsg,"%d %d\n", nodes, edges);
 176         while ((ib=read_item(in))) {
 177                 int i,ccount=ib->clen/2;
 178                 struct coord *c=(struct coord *)(ib+1);
 179                 int n1,n2,speed=road_speed(ib->type);
 180                 struct item_id road_id;
 181                 double l;
 182                 fread(&road_id, sizeof(road_id), 1, ref);
 183                 if (speed) {
 184                         struct edge_hash_item *hi=g_slice_new(struct edge_hash_item);
 185                         struct item_id *id=g_slice_new(struct item_id);
 186                         *id=road_id;
 187                         dbg_assert((n1=GPOINTER_TO_INT(g_hash_table_lookup(hash, &c[0]))) != 0);
 188                         dbg_assert((n2=GPOINTER_TO_INT(g_hash_table_lookup(hash, &c[ccount-1]))) != 0);
 189                         l=0;
 190                         for (i = 0 ; i < ccount-1 ; i++) {
 191                                 l+=sqrt(sq(c[i+1].x-c[i].x)+sq(c[i+1].y-c[i].y));
 192                         }
 193                         fprintf(ddsg,"%d %d %d 0\n", n1-1, n2-1, (int)(l*36/speed));
 194                         hi->first=n1-1;
 195                         hi->last=n2-1;
 196                         g_hash_table_insert(edge_hash, hi, id);
 197                 }
 198         }
 199         g_hash_table_destroy(hash);
 200 }
 201
 202 static void
 203 ch_generate_sgr(char *suffix)
 204 {
 205 #ifndef HAVE_API_WIN32_CE
 206         char command[1024];
 207         sprintf(command,"./contraction-hierarchies-20080621/main -s -p -f ddsg_%s.tmp -o hcn_%s.tmp -l hcn_log_%s.tmp -x 190 -y 1 -e 600 -p 1000 -k 1,3.3,2,10,3,10,5",suffix,suffix,suffix);
 208         printf("%s\n",command);
 209         system(command);
 210         sprintf(command,"./contraction-hierarchies-20080621/main -c -f ddsg_%s.tmp -h hcn_%s.tmp -k 1,3.3,2,10,3,10,5 -C ch_%s.tmp -O 1 -z sgr_%s.tmp",suffix,suffix,suffix,suffix);
 211         printf("%s\n",command);
 212         system(command);
 213 #endif
 214 }
 215
 216 static void
 217 ch_process_node(FILE *out, int node, int resolve)
 218 {
 219         int first_edge_id=nodes[node].first_edge;
 220         int last_edge_id=nodes[node+1].first_edge;
 221         int edge_id;
 222         struct ch_edge ch_edge;
 223         struct item_bin *item_bin;
 224         memset(&ch_edge, 0, sizeof(ch_edge));
 225         struct edge_hash_item fwd,rev;
 226         item_bin=init_item(type_ch_node);
 227         int oldnode=GPOINTER_TO_INT(g_hash_table_lookup(newnode_hash, GINT_TO_POINTER(node)));
 228 #if 0
 229         dbg(0,"0x%x,0x%x\n",node_index[oldnode].x,node_index[oldnode].y);
 230 #endif
 231         item_bin_add_coord(item_bin, &node_index[oldnode], 1);
 232         fwd.first=oldnode;
 233         rev.last=oldnode;
 234         for (edge_id = first_edge_id ; edge_id < last_edge_id ; edge_id++) {
 235                 if (resolve)  {
 236                         struct edge *edge=&edges[edge_id];
 237                         int oldnode=GPOINTER_TO_INT(g_hash_table_lookup(newnode_hash, GINT_TO_POINTER((int)edge->target)));
 238                         struct item_id *id;
 239                         ch_edge.weight=edge->weight;
 240                         fwd.last=oldnode;
 241                         rev.first=oldnode;
 242                         ch_edge.flags=edge->flags & 3;
 243                         if (edge->scmiddle == 67108863) {
 244                                 id=g_hash_table_lookup(edge_hash, &fwd);
 245                                 if (!id) {
 246                                         ch_edge.flags|=8;
 247                                         id=g_hash_table_lookup(edge_hash, &rev);
 248                                 }
 249                                 if (id == NULL) {
 250                                         fprintf(stderr,"Shortcut %d Weight %d\n",edge->scmiddle,edge->weight);
 251                                         fprintf(stderr,"Neither %d-%d nor %d-%d exists\n",fwd.first,fwd.last,rev.first,rev.last);
 252                                         exit(1);
 253                                 } else {
 254                                         ch_edge.middle=*id;
 255 #if 0
 256                                         dbg(0,"middle street id for is "ITEM_ID_FMT"\n",ITEM_ID_ARGS(*id));
 257 #endif
 258                                 }
 259                         } else {
 260                                 ch_edge.flags|=4;
 261                                 id=g_hash_table_lookup(sgr_nodes_hash, GINT_TO_POINTER((int)edge->scmiddle));
 262                                 dbg_assert(id != NULL);
 263                                 ch_edge.middle=*id;
 264 #if 0
 265                                 dbg(0,"middle node id for is "ITEM_ID_FMT"\n",ITEM_ID_ARGS(*id));
 266 #endif
 267                         }
 268                         id=g_hash_table_lookup(sgr_nodes_hash, GINT_TO_POINTER((int)edge->target));
 269 #if 0
 270                         dbg(0,"id for %d is "ITEM_ID_FMT"\n",edge->target,ITEM_ID_ARGS(*id));
 271 #endif
 272                         if (id == NULL) {
 273                                 fprintf(stderr,"Failed to look up target %d\n",edge->target);
 274                         } else {
 275                                 ch_edge.target=*id;
 276                         }
 277                 }
 278                 item_bin_add_attr_data(item_bin,attr_ch_edge,&ch_edge,sizeof(ch_edge));
 279         }
 280         item_bin_write(item_bin, out);
 281 }
 282
 283 static void
 284 ch_process_nodes(FILE *out, int pos, int count, int resolve)
 285 {
 286         int i;
 287         printf("count %d sum=%d newnode_count=%d\n",count,pos,newnode_count);
 288         for (i = 0 ; i < count ; i++)
 289                 ch_process_node(out, pos+i, resolve);
 290 }
 291
 292
 293 static void
 294 ch_process(FILE **files, int depth, int resolve)
 295 {
 296         int count=newnode_count;
 297         int pos=0;
 298
 299         while (depth > 0 && pos < newnode_count) {
 300                 count=(count+1)/2;
 301                 ch_process_nodes(files[depth], pos, count, resolve);
 302                 pos+=count;
 303                 depth--;
 304         }
 305         ch_process_nodes(files[depth], pos, newnode_count-pos, resolve);
 306 }
 307
 308 static void
 309 ch_setup(char *suffix)
 310 {
 311         int i;
 312         if (!sgr) {
 313                 int *data,size,offset=0;
 314                 char *filename=tempfile_name(suffix,"sgr");
 315                 printf("filename=%s\n",filename);
 316                 sgr=file_create(filename,0);
 317                 g_free(filename);
 318                 dbg_assert(sgr != NULL);
 319                 file_mmap(sgr);
 320
 321                 size=sizeof(int);
 322                 data=(int *)file_data_read(sgr, offset, size);
 323                 node_count=*data;
 324                 offset+=size;
 325
 326                 size=node_count*sizeof(struct node);
 327                 nodes=(struct node *)file_data_read(sgr, offset, size);
 328                 offset+=size;
 329
 330                 size=sizeof(int);
 331                 data=(int *)file_data_read(sgr, offset, size);
 332                 edge_count=*data;
 333                 offset+=size;
 334
 335                 size=edge_count*sizeof(struct edge);
 336                 edges=(struct edge *)file_data_read(sgr, offset, size);
 337                 offset+=size;
 338
 339                 size=sizeof(int);
 340                 data=(int *)file_data_read(sgr, offset, size);
 341                 newnode_count=*data;
 342                 offset+=size;
 343
 344                 size=edge_count*sizeof(struct newnode);
 345                 newnodes=(struct newnode *)file_data_read(sgr, offset, size);
 346                 offset+=size;
 347
 348                 newnode_hash=g_hash_table_new(NULL, NULL);
 349
 350                 for (i = 0 ; i < newnode_count ; i++) {
 351                         g_hash_table_insert(newnode_hash, GINT_TO_POINTER(newnodes[i].newnode), GINT_TO_POINTER(i));
 352                 }
 353         }
 354         if (!ddsg_node_index) {
 355                 char *filename=tempfile_name(suffix,"ddsg_coords");
 356                 ddsg_node_index=file_create(filename,0);
 357                 g_free(filename);
 358                 dbg_assert(ddsg_node_index != NULL);
 359                 file_mmap(ddsg_node_index);
 360                 node_index=(struct coord *)file_data_read(ddsg_node_index, 0, file_size(ddsg_node_index));
 361         }
 362 }
 363
 364 static void
 365 ch_create_tempfiles(char *suffix, FILE **files, int count, int mode)
 366 {
 367         char name[256];
 368         int i;
 369
 370         for (i = 0 ; i <= count ; i++) {
 371                 sprintf(name,"graph_%d",i);
 372                 files[i]=tempfile(suffix, name, mode);
 373         }
 374 }
 375
 376 static void
 377 ch_close_tempfiles(FILE **files, int count)
 378 {
 379         int i;
 380
 381         for (i = 0 ; i <= count ; i++) {
 382                 fclose(files[i]);
 383         }
 384 }
 385
 386 static void
 387 ch_remove_tempfiles(char *suffix, int count)
 388 {
 389         char name[256];
 390         int i;
 391
 392         for (i = 0 ; i <= count ; i++) {
 393                 sprintf(name,"graph_%d",i);
 394                 tempfile_unlink(suffix, name);
 395         }
 396 }
 397
 398 static void
 399 ch_copy_to_tiles(char *suffix, int count, struct tile_info *info, FILE *ref)
 400 {
 401         char name[256];
 402         int i;
 403         FILE *f;
 404         struct item_bin *item_bin;
 405
 406         for (i = count ; i >= 0 ; i--) {
 407                 sprintf(name,"graph_%d",i);
 408                 f=tempfile(suffix, name, 0);
 409                 while ((item_bin = read_item(f))) {
 410                         tile_write_item_minmax(info, item_bin, ref, i, i);
 411                 }
 412                 fclose(f);
 413         }
 414 }
 415
 416 void
 417 ch_generate_tiles(char *map_suffix, char *suffix, FILE *tilesdir_out, struct zip_info *zip_info)
 418 {
 419         struct tile_info info;
 420         FILE *in,*ref,*ddsg_coords,*ddsg;
 421         info.write=0;
 422         info.maxlen=0;
 423         info.suffix=suffix;
 424         info.tiles_list=NULL;
 425         info.tilesdir_out=tilesdir_out;
 426         FILE *graphfiles[ch_levels+1];
 427
 428         ch_create_tempfiles(suffix, graphfiles, ch_levels, 1);
 429         in=tempfile(map_suffix,"ways_split",0);
 430         ref=tempfile(map_suffix,"ways_split_ref",0);
 431         ddsg_coords=tempfile(suffix,"ddsg_coords",1);
 432         ddsg=tempfile(suffix,"ddsg",1);
 433         ch_generate_ddsg(in, ref, ddsg_coords, ddsg);
 434         fclose(in);
 435         fclose(ref);
 436         fclose(ddsg_coords);
 437         fclose(ddsg);
 438         ch_generate_sgr(suffix);
 439         ch_setup(suffix);
 440         ch_process(graphfiles, ch_levels, 0);
 441         ch_close_tempfiles(graphfiles, ch_levels);
 442
 443         tile_hash=g_hash_table_new(g_str_hash, g_str_equal);
 444         ch_copy_to_tiles(suffix, ch_levels, &info, NULL);
 445         merge_tiles(&info);
 446
 447         write_tilesdir(&info, zip_info, tilesdir_out);
 448 }
 449
 450 void
 451 ch_assemble_map(char *map_suffix, char *suffix, struct zip_info *zip_info)
 452 {
 453         struct tile_info info;
 454         struct tile_head *th;
 455         FILE *graphfiles[ch_levels+1];
 456
 457         info.write=1;
 458         info.maxlen=zip_info->maxnamelen;
 459         info.suffix=suffix;
 460         info.tiles_list=NULL;
 461         info.tilesdir_out=NULL;
 462         FILE *ref=tempfile(suffix,"sgr_ref",1);
 463         struct item_id id;
 464         int nodeid=0;
 465
 466         create_tile_hash();
 467
 468         th=tile_head_root;
 469         while (th) {
 470                 th->zip_data=NULL;
 471                 th->process=1;
 472                 th=th->next;
 473         }
 474
 475         ch_setup(suffix);
 476         ch_copy_to_tiles(suffix, ch_levels, &info, ref);
 477         fclose(ref);
 478         ref=tempfile(suffix,"sgr_ref",0);
 479         sgr_nodes_hash=g_hash_table_new_full(NULL, NULL, NULL, item_id_slice_free);
 480         while (fread(&id, sizeof(id), 1, ref)) {
 481                 struct item_id *id2=g_slice_new(struct item_id);
 482                 *id2=id;
 483 #if 0
 484                 dbg(0,"%d is "ITEM_ID_FMT"\n",nodeid,ITEM_ID_ARGS(*id2));
 485 #endif
 486                 g_hash_table_insert(sgr_nodes_hash, GINT_TO_POINTER(nodeid), id2);
 487                 nodeid++;
 488         }
 489         th=tile_head_root;
 490         while (th) {
 491                 th->zip_data=malloc(th->total_size);
 492                 th->total_size_used=0;
 493                 th=th->next;
 494         }
 495         ch_create_tempfiles(suffix, graphfiles, ch_levels, 1);
 496         ch_process(graphfiles, ch_levels, 1);
 497         ch_close_tempfiles(graphfiles, ch_levels);
 498
 499         g_hash_table_destroy(newnode_hash);
 500         g_hash_table_destroy(edge_hash);
 501         g_hash_table_destroy(sgr_nodes_hash);
 502
 503         ch_copy_to_tiles(suffix, ch_levels, &info, NULL);
 504         write_tilesdir(&info, zip_info, NULL);
 505
 506         th=tile_head_root;
 507         while (th) {
 508                 if (th->name[0]) {
 509                         if (th->total_size != th->total_size_used) {
 510                                 fprintf(stderr,"Size error '%s': %d vs %d\n", th->name, th->total_size, th->total_size_used);
 511                                 exit(1);
 512                         }
 513                         write_zipmember(zip_info, th->name, zip_info->maxnamelen, th->zip_data, th->total_size);
 514                 } else {
 515                         fwrite(th->zip_data, th->total_size, 1, zip_info->index);
 516                 }
 517                 g_free(th->zip_data);
 518                 th=th->next;
 519         }
 520 }