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

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