git.maemo.org Git - routino/blob - src/segmentsx.c

   1 /***************************************
   2  $Header: /home/amb/routino/src/RCS/segmentsx.c,v 1.68 2010/10/09 14:14:42 amb Exp $
   3
   4  Extended Segment data type functions.
   5
   6  Part of the Routino routing software.
   7  ******************/ /******************
   8  This file Copyright 2008-2010 Andrew M. Bishop
   9
  10  This program is free software: you can redistribute it and/or modify
  11  it under the terms of the GNU Affero General Public License as published by
  12  the Free Software Foundation, either version 3 of the License, or
  13  (at your option) any later version.
  14
  15  This program is distributed in the hope that it will be useful,
  16  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  GNU Affero General Public License for more details.
  19
  20  You should have received a copy of the GNU Affero General Public License
  21  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  22  ***************************************/
  23
  24
  25 #include <assert.h>
  26 #include <math.h>
  27 #include <stdlib.h>
  28 #include <stdio.h>
  29 #include <string.h>
  30 #include <sys/stat.h>
  31
  32 #include "types.h"
  33 #include "nodes.h"
  34 #include "segments.h"
  35 #include "ways.h"
  36
  37 #include "nodesx.h"
  38 #include "segmentsx.h"
  39 #include "waysx.h"
  40
  41 #include "types.h"
  42
  43 #include "files.h"
  44 #include "functions.h"
  45
  46
  47 /* Variables */
  48
  49 /*+ The command line '--tmpdir' option or its default value. +*/
  50 extern char *option_tmpdirname;
  51
  52 /* Local Functions */
  53
  54 static int sort_by_id(SegmentX *a,SegmentX *b);
  55
  56 static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2);
  57
  58
  59 /*++++++++++++++++++++++++++++++++++++++
  60   Allocate a new segment list (create a new file or open an existing one).
  61
  62   SegmentsX *NewSegmentList Returns the segment list.
  63
  64   int append Set to 1 if the file is to be opened for appending (now or later).
  65   ++++++++++++++++++++++++++++++++++++++*/
  66
  67 SegmentsX *NewSegmentList(int append)
  68 {
  69  SegmentsX *segmentsx;
  70
  71  segmentsx=(SegmentsX*)calloc(1,sizeof(SegmentsX));
  72
  73  assert(segmentsx); /* Check calloc() worked */
  74
  75  segmentsx->filename=(char*)malloc(strlen(option_tmpdirname)+32);
  76
  77  if(append)
  78     sprintf(segmentsx->filename,"%s/segmentsx.input.tmp",option_tmpdirname);
  79  else
  80     sprintf(segmentsx->filename,"%s/segmentsx.%p.tmp",option_tmpdirname,segmentsx);
  81
  82 #if SLIM
  83  segmentsx->sfilename=(char*)malloc(strlen(option_tmpdirname)+32);
  84
  85  sprintf(segmentsx->sfilename,"%s/segments.%p.tmp",option_tmpdirname,segmentsx);
  86 #endif
  87
  88  if(append)
  89    {
  90     off_t size;
  91
  92     segmentsx->fd=OpenFileAppend(segmentsx->filename);
  93
  94     size=SizeFile(segmentsx->filename);
  95
  96     segmentsx->xnumber=size/sizeof(SegmentX);
  97    }
  98  else
  99     segmentsx->fd=OpenFileNew(segmentsx->filename);
 100
 101  return(segmentsx);
 102 }
 103
 104
 105 /*++++++++++++++++++++++++++++++++++++++
 106   Free a segment list.
 107
 108   SegmentsX *segmentsx The list to be freed.
 109
 110   int keep Set to 1 if the file is to be kept.
 111   ++++++++++++++++++++++++++++++++++++++*/
 112
 113 void FreeSegmentList(SegmentsX *segmentsx,int keep)
 114 {
 115  if(!keep)
 116     DeleteFile(segmentsx->filename);
 117
 118  free(segmentsx->filename);
 119
 120  if(segmentsx->idata)
 121     free(segmentsx->idata);
 122
 123  if(segmentsx->firstnode)
 124     free(segmentsx->firstnode);
 125
 126 #if !SLIM
 127  if(segmentsx->sdata)
 128     free(segmentsx->sdata);
 129 #endif
 130
 131 #if SLIM
 132  DeleteFile(segmentsx->sfilename);
 133
 134  free(segmentsx->sfilename);
 135 #endif
 136
 137  free(segmentsx);
 138 }
 139
 140
 141 /*++++++++++++++++++++++++++++++++++++++
 142   Append a single segment to an unsorted segment list.
 143
 144   SegmentsX* segmentsx The set of segments to process.
 145
 146   way_t way The way that the segment belongs to.
 147
 148   node_t node1 The first node in the segment.
 149
 150   node_t node2 The second node in the segment.
 151
 152   distance_t distance The distance between the nodes (or just the flags).
 153   ++++++++++++++++++++++++++++++++++++++*/
 154
 155 void AppendSegment(SegmentsX* segmentsx,way_t way,node_t node1,node_t node2,distance_t distance)
 156 {
 157  SegmentX segmentx;
 158
 159  segmentx.node1=node1;
 160  segmentx.node2=node2;
 161  segmentx.way=way;
 162  segmentx.distance=distance;
 163
 164  WriteFile(segmentsx->fd,&segmentx,sizeof(SegmentX));
 165
 166  segmentsx->xnumber++;
 167
 168  assert(segmentsx->xnumber<SEGMENT_FAKE); /* SEGMENT_FAKE marks the high-water mark for real segments. */
 169 }
 170
 171
 172 /*++++++++++++++++++++++++++++++++++++++
 173   Sort the segment list.
 174
 175   SegmentsX* segmentsx The set of segments to process.
 176   ++++++++++++++++++++++++++++++++++++++*/
 177
 178 void SortSegmentList(SegmentsX* segmentsx)
 179 {
 180  int fd;
 181
 182  if(segmentsx->xnumber==0)
 183     return;
 184
 185  /* Print the start message */
 186
 187  printf("Sorting Segments");
 188  fflush(stdout);
 189
 190  /* Close the files and re-open them (finished appending) */
 191
 192  CloseFile(segmentsx->fd);
 193  segmentsx->fd=ReOpenFile(segmentsx->filename);
 194
 195  DeleteFile(segmentsx->filename);
 196
 197  fd=OpenFileNew(segmentsx->filename);
 198
 199  /* Sort by node indexes */
 200
 201  filesort_fixed(segmentsx->fd,fd,sizeof(SegmentX),(int (*)(const void*,const void*))sort_by_id,NULL);
 202
 203  segmentsx->number=segmentsx->xnumber;
 204
 205  /* Close the files and re-open them */
 206
 207  CloseFile(segmentsx->fd);
 208  CloseFile(fd);
 209
 210  segmentsx->fd=ReOpenFile(segmentsx->filename);
 211
 212  /* Print the final message */
 213
 214  printf("\rSorted Segments: Segments=%d\n",segmentsx->xnumber);
 215  fflush(stdout);
 216 }
 217
 218
 219 /*++++++++++++++++++++++++++++++++++++++
 220   Sort the segments into id order (node1 then node2).
 221
 222   int sort_by_id Returns the comparison of the node fields.
 223
 224   SegmentX *a The first segment.
 225
 226   SegmentX *b The second segment.
 227   ++++++++++++++++++++++++++++++++++++++*/
 228
 229 static int sort_by_id(SegmentX *a,SegmentX *b)
 230 {
 231  node_t a_id1=a->node1;
 232  node_t b_id1=b->node1;
 233
 234  if(a_id1<b_id1)
 235     return(-1);
 236  else if(a_id1>b_id1)
 237     return(1);
 238  else /* if(a_id1==b_id1) */
 239    {
 240     node_t a_id2=a->node2;
 241     node_t b_id2=b->node2;
 242
 243     if(a_id2<b_id2)
 244        return(-1);
 245     else if(a_id2>b_id2)
 246        return(1);
 247     else
 248       {
 249        distance_t a_distance=a->distance;
 250        distance_t b_distance=b->distance;
 251
 252        if(a_distance<b_distance)
 253           return(-1);
 254        else if(a_distance>b_distance)
 255           return(1);
 256        else
 257           return(0);
 258       }
 259    }
 260 }
 261
 262
 263 /*++++++++++++++++++++++++++++++++++++++
 264   Find the first segment index with a particular starting node.
 265
 266   index_t IndexFirstSegmentX Returns a pointer to the index of the first extended segment with the specified id.
 267
 268   SegmentsX* segmentsx The set of segments to process.
 269
 270   node_t node The node to look for.
 271   ++++++++++++++++++++++++++++++++++++++*/
 272
 273 index_t IndexFirstSegmentX(SegmentsX* segmentsx,node_t node)
 274 {
 275  int start=0;
 276  int end=segmentsx->number-1;
 277  int mid;
 278  int found;
 279
 280  /* Check if the first node index exists */
 281
 282  if(segmentsx->firstnode)
 283    {
 284     index_t index=segmentsx->firstnode[node];
 285
 286     if(segmentsx->firstnode[node+1]==index)
 287        return(NO_SEGMENT);
 288
 289     return(index);
 290    }
 291
 292  /* Binary search - search key exact match only is required.
 293   *
 294   *  # <- start  |  Check mid and move start or end if it doesn't match
 295   *  #           |
 296   *  #           |  Since an exact match is wanted we can set end=mid-1
 297   *  # <- mid    |  or start=mid+1 because we know that mid doesn't match.
 298   *  #           |
 299   *  #           |  Eventually either end=start or end=start+1 and one of
 300   *  # <- end    |  start or end is the wanted one.
 301   */
 302
 303  if(end<start)                         /* There are no nodes */
 304     return(NO_SEGMENT);
 305  else if(node<segmentsx->idata[start]) /* Check key is not before start */
 306     return(NO_SEGMENT);
 307  else if(node>segmentsx->idata[end])   /* Check key is not after end */
 308     return(NO_SEGMENT);
 309  else
 310    {
 311     do
 312       {
 313        mid=(start+end)/2;                  /* Choose mid point */
 314
 315        if(segmentsx->idata[mid]<node)      /* Mid point is too low */
 316           start=mid;
 317        else if(segmentsx->idata[mid]>node) /* Mid point is too high */
 318           end=mid;
 319        else                                /* Mid point is correct */
 320          {found=mid; goto found;}
 321       }
 322     while((end-start)>1);
 323
 324     if(segmentsx->idata[start]==node)      /* Start is correct */
 325       {found=start; goto found;}
 326
 327     if(segmentsx->idata[end]==node)        /* End is correct */
 328       {found=end; goto found;}
 329    }
 330
 331  return(NO_SEGMENT);
 332
 333  found:
 334
 335  while(found>0 && segmentsx->idata[found-1]==node)
 336     found--;
 337
 338  return(found);
 339 }
 340
 341
 342 /*++++++++++++++++++++++++++++++++++++++
 343   Find the next segment index with a particular starting node.
 344
 345   index_t IndexNextSegmentX Returns the index of the next segment with the same id.
 346
 347   SegmentsX* segmentsx The set of segments to process.
 348
 349   index_t segindex The current segment index.
 350
 351   index_t nodeindex The node index.
 352   ++++++++++++++++++++++++++++++++++++++*/
 353
 354 index_t IndexNextSegmentX(SegmentsX* segmentsx,index_t segindex,index_t nodeindex)
 355 {
 356  if(++segindex==segmentsx->firstnode[nodeindex+1])
 357     return(NO_SEGMENT);
 358  else
 359     return(segindex);
 360 }
 361
 362
 363 /*++++++++++++++++++++++++++++++++++++++
 364   Remove bad segments (duplicated, zero length or missing nodes).
 365
 366   NodesX *nodesx The nodes to check.
 367
 368   SegmentsX *segmentsx The segments to modify.
 369   ++++++++++++++++++++++++++++++++++++++*/
 370
 371 void RemoveBadSegments(NodesX *nodesx,SegmentsX *segmentsx)
 372 {
 373  int duplicate=0,loop=0,missing=0,good=0,total=0;
 374  SegmentX segmentx;
 375  int fd;
 376  node_t prevnode1=NO_NODE,prevnode2=NO_NODE;
 377
 378  /* Print the start message */
 379
 380  printf("Checking: Segments=0 Duplicate=0 Loop=0 Missing-Node=0");
 381  fflush(stdout);
 382
 383  /* Allocate the array of indexes */
 384
 385  segmentsx->idata=(node_t*)malloc(segmentsx->xnumber*sizeof(node_t));
 386
 387  assert(segmentsx->idata); /* Check malloc() worked */
 388
 389  /* Modify the on-disk image */
 390
 391  DeleteFile(segmentsx->filename);
 392
 393  fd=OpenFileNew(segmentsx->filename);
 394  SeekFile(segmentsx->fd,0);
 395
 396  while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX)))
 397    {
 398     if(prevnode1==segmentx.node1 && prevnode2==segmentx.node2)
 399        duplicate++;
 400     else if(segmentx.node1==segmentx.node2)
 401        loop++;
 402     else if(IndexNodeX(nodesx,segmentx.node1)==NO_NODE ||
 403             IndexNodeX(nodesx,segmentx.node2)==NO_NODE)
 404        missing++;
 405     else
 406       {
 407        WriteFile(fd,&segmentx,sizeof(SegmentX));
 408
 409        segmentsx->idata[good]=segmentx.node1;
 410        good++;
 411
 412        prevnode1=segmentx.node1;
 413        prevnode2=segmentx.node2;
 414       }
 415
 416     total++;
 417
 418     if(!(total%10000))
 419       {
 420        printf("\rChecking: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d",total,duplicate,loop,missing);
 421        fflush(stdout);
 422       }
 423    }
 424
 425  /* Close the files and re-open them */
 426
 427  CloseFile(segmentsx->fd);
 428  CloseFile(fd);
 429
 430  segmentsx->fd=ReOpenFile(segmentsx->filename);
 431
 432  segmentsx->number=good;
 433
 434  /* Print the final message */
 435
 436  printf("\rChecked: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d  \n",total,duplicate,loop,missing);
 437  fflush(stdout);
 438 }
 439
 440
 441 /*++++++++++++++++++++++++++++++++++++++
 442   Measure the segments and replace node/way ids with indexes.
 443
 444   SegmentsX* segmentsx The set of segments to process.
 445
 446   NodesX *nodesx The list of nodes to use.
 447
 448   WaysX *waysx The list of ways to use.
 449   ++++++++++++++++++++++++++++++++++++++*/
 450
 451 void UpdateSegments(SegmentsX* segmentsx,NodesX *nodesx,WaysX *waysx)
 452 {
 453  index_t index=0;
 454  int i,fd;
 455  SegmentX segmentx;
 456
 457  /* Print the start message */
 458
 459  printf("Measuring Segments: Segments=0");
 460  fflush(stdout);
 461
 462  /* Map into memory */
 463
 464 #if !SLIM
 465  nodesx->xdata=MapFile(nodesx->filename);
 466 #endif
 467
 468  /* Free the now-unneeded index */
 469
 470  free(segmentsx->idata);
 471  segmentsx->idata=NULL;
 472
 473  /* Allocate the array of indexes */
 474
 475  segmentsx->firstnode=(index_t*)malloc((nodesx->number+1)*sizeof(index_t));
 476
 477  assert(segmentsx->firstnode); /* Check malloc() worked */
 478
 479  for(i=0;i<nodesx->number;i++)
 480     segmentsx->firstnode[i]=NO_SEGMENT;
 481
 482  segmentsx->firstnode[nodesx->number]=segmentsx->number;
 483
 484  /* Modify the on-disk image */
 485
 486  DeleteFile(segmentsx->filename);
 487
 488  fd=OpenFileNew(segmentsx->filename);
 489  SeekFile(segmentsx->fd,0);
 490
 491  while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX)))
 492    {
 493     index_t node1=IndexNodeX(nodesx,segmentx.node1);
 494     index_t node2=IndexNodeX(nodesx,segmentx.node2);
 495     index_t way  =IndexWayX (waysx ,segmentx.way);
 496
 497     NodeX *nodex1=LookupNodeX(nodesx,node1,1);
 498     NodeX *nodex2=LookupNodeX(nodesx,node2,2);
 499
 500     /* Replace the node and way ids with their indexes */
 501
 502     segmentx.node1=node1;
 503     segmentx.node2=node2;
 504     segmentx.way  =way;
 505
 506     /* Set the distance but preserve the ONEWAY_* flags */
 507
 508     segmentx.distance|=DISTANCE(DistanceX(nodex1,nodex2));
 509
 510     /* Set the first segment index in the nodes */
 511
 512     if(index<segmentsx->firstnode[node1])
 513        segmentsx->firstnode[node1]=index;
 514
 515     /* Write the modified segment */
 516
 517     WriteFile(fd,&segmentx,sizeof(SegmentX));
 518
 519     index++;
 520
 521     if(!(index%10000))
 522       {
 523        printf("\rMeasuring Segments: Segments=%d",index);
 524        fflush(stdout);
 525       }
 526    }
 527
 528  /* Close the files and re-open them */
 529
 530  CloseFile(segmentsx->fd);
 531  CloseFile(fd);
 532
 533  segmentsx->fd=ReOpenFile(segmentsx->filename);
 534
 535  /* Free the other now-unneeded indexes */
 536
 537  free(nodesx->idata);
 538  nodesx->idata=NULL;
 539
 540  free(waysx->idata);
 541  waysx->idata=NULL;
 542
 543  /* Unmap from memory */
 544
 545 #if !SLIM
 546  nodesx->xdata=UnmapFile(nodesx->filename);
 547 #endif
 548
 549  /* Print the final message */
 550
 551  printf("\rMeasured Segments: Segments=%d \n",segmentsx->number);
 552  fflush(stdout);
 553 }
 554
 555
 556 /*++++++++++++++++++++++++++++++++++++++
 557   Make the segments all point the same way (node1<node2).
 558
 559   SegmentsX* segmentsx The set of segments to process.
 560   ++++++++++++++++++++++++++++++++++++++*/
 561
 562 void RotateSegments(SegmentsX* segmentsx)
 563 {
 564  int index=0,rotated=0;
 565  int fd;
 566  SegmentX segmentx;
 567
 568  /* Print the start message */
 569
 570  printf("Rotating Segments: Segments=0 Rotated=0");
 571  fflush(stdout);
 572
 573  /* Close the files and re-open them (finished appending) */
 574
 575  CloseFile(segmentsx->fd);
 576  segmentsx->fd=ReOpenFile(segmentsx->filename);
 577
 578  DeleteFile(segmentsx->filename);
 579
 580  fd=OpenFileNew(segmentsx->filename);
 581
 582  /* Modify the file contents */
 583
 584  while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX)))
 585    {
 586     if(segmentx.node1>segmentx.node2)
 587       {
 588        node_t temp;
 589
 590        temp=segmentx.node1;
 591        segmentx.node1=segmentx.node2;
 592        segmentx.node2=temp;
 593
 594        if(segmentx.distance&(ONEWAY_2TO1|ONEWAY_1TO2))
 595           segmentx.distance^=ONEWAY_2TO1|ONEWAY_1TO2;
 596
 597        rotated++;
 598       }
 599
 600     WriteFile(fd,&segmentx,sizeof(SegmentX));
 601
 602     index++;
 603
 604     if(!(index%10000))
 605       {
 606        printf("\rRotating Segments: Segments=%d Rotated=%d",index,rotated);
 607        fflush(stdout);
 608       }
 609    }
 610
 611  /* Close the files and re-open them */
 612
 613  CloseFile(segmentsx->fd);
 614  CloseFile(fd);
 615
 616  segmentsx->fd=ReOpenFile(segmentsx->filename);
 617
 618  /* Print the final message */
 619
 620  printf("\rRotated Segments: Segments=%d Rotated=%d \n",index,rotated);
 621  fflush(stdout);
 622 }
 623
 624
 625 /*++++++++++++++++++++++++++++++++++++++
 626   Remove the duplicate segments.
 627
 628   SegmentsX* segmentsx The set of segments to process.
 629
 630   NodesX *nodesx The list of nodes to use.
 631
 632   WaysX *waysx The list of ways to use.
 633   ++++++++++++++++++++++++++++++++++++++*/
 634
 635 void DeduplicateSegments(SegmentsX* segmentsx,NodesX *nodesx,WaysX *waysx)
 636 {
 637  int duplicate=0,good=0;
 638  index_t firstindex=0,index=0;
 639  int i,fd;
 640  SegmentX prevsegmentx[16],segmentx;
 641
 642  /* Print the start message */
 643
 644  printf("Deduplicating Segments: Segments=0 Duplicate=0");
 645  fflush(stdout);
 646
 647  /* Map into memory */
 648
 649 #if !SLIM
 650  waysx->xdata=MapFile(waysx->filename);
 651 #endif
 652
 653  /* Allocate the array of indexes */
 654
 655  segmentsx->firstnode=(index_t*)malloc((nodesx->number+1)*sizeof(index_t));
 656
 657  assert(segmentsx->firstnode); /* Check malloc() worked */
 658
 659  for(i=0;i<nodesx->number;i++)
 660     segmentsx->firstnode[i]=NO_SEGMENT;
 661
 662  segmentsx->firstnode[nodesx->number]=segmentsx->number;
 663
 664  /* Modify the on-disk image */
 665
 666  DeleteFile(segmentsx->filename);
 667
 668  fd=OpenFileNew(segmentsx->filename);
 669  SeekFile(segmentsx->fd,0);
 670
 671  while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX)))
 672    {
 673     int isduplicate=0;
 674
 675     if(index && segmentx.node1==prevsegmentx[0].node1 &&
 676                 segmentx.node2==prevsegmentx[0].node2)
 677       {
 678        index_t previndex=firstindex;
 679
 680        while(previndex<index)
 681          {
 682           int offset=previndex-firstindex;
 683
 684           if(DISTFLAG(segmentx.distance)==DISTFLAG(prevsegmentx[offset].distance))
 685             {
 686              WayX *wayx1=LookupWayX(waysx,prevsegmentx[offset].way,1);
 687              WayX *wayx2=LookupWayX(waysx,    segmentx        .way,2);
 688
 689              if(!WaysCompare(&wayx1->way,&wayx2->way))
 690                {
 691                 isduplicate=1;
 692                 duplicate++;
 693                 break;
 694                }
 695             }
 696
 697           previndex++;
 698          }
 699
 700        assert((index-firstindex)<(sizeof(prevsegmentx)/sizeof(prevsegmentx[0])));
 701
 702        prevsegmentx[index-firstindex]=segmentx;
 703       }
 704     else
 705       {
 706        firstindex=index;
 707        prevsegmentx[0]=segmentx;
 708       }
 709
 710     if(!isduplicate)
 711       {
 712        WriteFile(fd,&segmentx,sizeof(SegmentX));
 713
 714        if(good<segmentsx->firstnode[segmentx.node1])
 715           segmentsx->firstnode[segmentx.node1]=good;
 716
 717        good++;
 718       }
 719
 720     index++;
 721
 722     if(!(index%10000))
 723       {
 724        printf("\rDeduplicating Segments: Segments=%d Duplicate=%d",index,duplicate);
 725        fflush(stdout);
 726       }
 727    }
 728
 729  /* Close the files and re-open them */
 730
 731  CloseFile(segmentsx->fd);
 732  CloseFile(fd);
 733
 734  segmentsx->fd=ReOpenFile(segmentsx->filename);
 735
 736  segmentsx->number=good;
 737
 738  /* Fix-up the firstnode index for the missing nodes */
 739
 740  for(i=nodesx->number-1;i>=0;i--)
 741     if(segmentsx->firstnode[i]==NO_SEGMENT)
 742        segmentsx->firstnode[i]=segmentsx->firstnode[i+1];
 743
 744  /* Unmap from memory */
 745
 746 #if !SLIM
 747  waysx->xdata=UnmapFile(waysx->filename);
 748 #endif
 749
 750  /* Print the final message */
 751
 752  printf("\rDeduplicated Segments: Segments=%d Duplicate=%d Unique=%d\n",index,duplicate,index-duplicate);
 753  fflush(stdout);
 754 }
 755
 756
 757 /*++++++++++++++++++++++++++++++++++++++
 758   Create the real segments data.
 759
 760   SegmentsX* segmentsx The set of segments to use.
 761
 762   WaysX* waysx The set of ways to use.
 763   ++++++++++++++++++++++++++++++++++++++*/
 764
 765 void CreateRealSegments(SegmentsX *segmentsx,WaysX *waysx)
 766 {
 767  index_t i;
 768
 769  if(segmentsx->number==0 || waysx->number==0)
 770     return;
 771
 772  /* Print the start message */
 773
 774  printf("Creating Real Segments: Segments=0");
 775  fflush(stdout);
 776
 777  /* Map into memory */
 778
 779 #if !SLIM
 780  segmentsx->xdata=MapFile(segmentsx->filename);
 781  waysx->xdata=MapFile(waysx->filename);
 782 #endif
 783
 784  /* Free the unneeded memory */
 785
 786  free(segmentsx->firstnode);
 787  segmentsx->firstnode=NULL;
 788
 789  /* Allocate the memory (or open the file) */
 790
 791 #if !SLIM
 792  segmentsx->sdata=(Segment*)malloc(segmentsx->number*sizeof(Segment));
 793
 794  assert(segmentsx->sdata); /* Check malloc() worked */
 795 #else
 796  segmentsx->sfd=OpenFileNew(segmentsx->sfilename);
 797 #endif
 798
 799  /* Loop through and fill */
 800
 801  for(i=0;i<segmentsx->number;i++)
 802    {
 803     SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);
 804     Segment  *segment =LookupSegmentXSegment(segmentsx,i,1);
 805     WayX     *wayx=LookupWayX(waysx,segmentx->way,1);
 806
 807     segment->node1=0;
 808     segment->node2=0;
 809     segment->next2=NO_NODE;
 810     segment->way=wayx->prop;
 811     segment->distance=segmentx->distance;
 812
 813 #if SLIM
 814     PutBackSegmentXSegment(segmentsx,i,1);
 815 #endif
 816
 817     if(!((i+1)%10000))
 818       {
 819        printf("\rCreating Real Segments: Segments=%d",i+1);
 820        fflush(stdout);
 821       }
 822    }
 823
 824  /* Unmap from memory */
 825
 826 #if !SLIM
 827  segmentsx->xdata=UnmapFile(segmentsx->filename);
 828  waysx->xdata=UnmapFile(waysx->filename);
 829 #endif
 830
 831  /* Print the final message */
 832
 833  printf("\rCreating Real Segments: Segments=%d \n",segmentsx->number);
 834  fflush(stdout);
 835 }
 836
 837
 838 /*++++++++++++++++++++++++++++++++++++++
 839   Assign the nodes indexes to the segments.
 840
 841   SegmentsX* segmentsx The set of segments to process.
 842
 843   NodesX *nodesx The list of nodes to use.
 844   ++++++++++++++++++++++++++++++++++++++*/
 845
 846 void IndexSegments(SegmentsX* segmentsx,NodesX *nodesx)
 847 {
 848  index_t i;
 849
 850  if(nodesx->number==0 || segmentsx->number==0)
 851     return;
 852
 853  /* Print the start message */
 854
 855  printf("Indexing Nodes: Nodes=0");
 856  fflush(stdout);
 857
 858  /* Map into memory */
 859
 860 #if !SLIM
 861  nodesx->xdata=MapFile(nodesx->filename);
 862  segmentsx->xdata=MapFile(segmentsx->filename);
 863 #endif
 864
 865  /* Index the segments */
 866
 867  for(i=0;i<nodesx->number;i++)
 868    {
 869     NodeX  *nodex=LookupNodeX(nodesx,i,1);
 870     Node   *node =LookupNodeXNode(nodesx,nodex->id,1);
 871     index_t index=node->firstseg;
 872
 873     do
 874       {
 875        SegmentX *segmentx=LookupSegmentX(segmentsx,index,1);
 876        Segment  *segment =LookupSegmentXSegment(segmentsx,index,1);
 877
 878        if(segmentx->node1==nodex->id)
 879          {
 880           segment->node1=i;
 881
 882 #if SLIM
 883           PutBackSegmentXSegment(segmentsx,index,1);
 884 #endif
 885
 886           index++;
 887
 888           if(index>=segmentsx->number)
 889              break;
 890
 891           segmentx=LookupSegmentX(segmentsx,index,1);
 892
 893           if(segmentx->node1!=nodex->id)
 894              break;
 895          }
 896        else
 897          {
 898           segment->node2=i;
 899
 900 #if SLIM
 901           PutBackSegmentXSegment(segmentsx,index,1);
 902 #endif
 903
 904           if(segment->next2==NO_NODE)
 905              break;
 906           else
 907              index=segment->next2;
 908          }
 909       }
 910     while(1);
 911
 912     if(!((i+1)%10000))
 913       {
 914        printf("\rIndexing Nodes: Nodes=%d",i+1);
 915        fflush(stdout);
 916       }
 917    }
 918
 919  /* Unmap from memory */
 920
 921 #if !SLIM
 922  nodesx->xdata=UnmapFile(nodesx->filename);
 923  segmentsx->xdata=UnmapFile(segmentsx->filename);
 924 #endif
 925
 926  /* Print the final message */
 927
 928  printf("\rIndexed Nodes: Nodes=%d \n",nodesx->number);
 929  fflush(stdout);
 930 }
 931
 932
 933 /*++++++++++++++++++++++++++++++++++++++
 934   Save the segment list to a file.
 935
 936   SegmentsX* segmentsx The set of segments to save.
 937
 938   const char *filename The name of the file to save.
 939   ++++++++++++++++++++++++++++++++++++++*/
 940
 941 void SaveSegmentList(SegmentsX* segmentsx,const char *filename)
 942 {
 943  index_t i;
 944  int fd;
 945  SegmentsFile segmentsfile={0};
 946  int super_number=0,normal_number=0;
 947
 948  /* Print the start message */
 949
 950  printf("Writing Segments: Segments=0");
 951  fflush(stdout);
 952
 953  /* Write out the segments data */
 954
 955  fd=OpenFileNew(filename);
 956
 957  SeekFile(fd,sizeof(SegmentsFile));
 958
 959  for(i=0;i<segmentsx->number;i++)
 960    {
 961     Segment *segment=LookupSegmentXSegment(segmentsx,i,1);
 962
 963     if(IsSuperSegment(segment))
 964        super_number++;
 965     if(IsNormalSegment(segment))
 966        normal_number++;
 967
 968     WriteFile(fd,segment,sizeof(Segment));
 969
 970     if(!((i+1)%10000))
 971       {
 972        printf("\rWriting Segments: Segments=%d",i+1);
 973        fflush(stdout);
 974       }
 975    }
 976
 977  /* Write out the header structure */
 978
 979  segmentsfile.number=segmentsx->number;
 980  segmentsfile.snumber=super_number;
 981  segmentsfile.nnumber=normal_number;
 982
 983  SeekFile(fd,0);
 984  WriteFile(fd,&segmentsfile,sizeof(SegmentsFile));
 985
 986  CloseFile(fd);
 987
 988  /* Print the final message */
 989
 990  printf("\rWrote Segments: Segments=%d  \n",segmentsx->number);
 991  fflush(stdout);
 992 }
 993
 994
 995 /*++++++++++++++++++++++++++++++++++++++
 996   Calculate the distance between two nodes.
 997
 998   distance_t DistanceX Returns the distance between the extended nodes.
 999
1000   NodeX *nodex1 The starting node.
1001
1002   NodeX *nodex2 The end node.
1003   ++++++++++++++++++++++++++++++++++++++*/
1004
1005 static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2)
1006 {
1007  double dlon = latlong_to_radians(nodex1->longitude) - latlong_to_radians(nodex2->longitude);
1008  double dlat = latlong_to_radians(nodex1->latitude)  - latlong_to_radians(nodex2->latitude);
1009  double lat1 = latlong_to_radians(nodex1->latitude);
1010  double lat2 = latlong_to_radians(nodex2->latitude);
1011
1012  double a1,a2,a,sa,c,d;
1013
1014  if(dlon==0 && dlat==0)
1015    return 0;
1016
1017  a1 = sin (dlat / 2);
1018  a2 = sin (dlon / 2);
1019  a = (a1 * a1) + cos (lat1) * cos (lat2) * a2 * a2;
1020  sa = sqrt (a);
1021  if (sa <= 1.0)
1022    {c = 2 * asin (sa);}
1023  else
1024    {c = 2 * asin (1.0);}
1025  d = 6378.137 * c;
1026
1027  return km_to_distance(d);
1028 }