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

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