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

   1 /***************************************
   2  $Header: /home/amb/routino/src/RCS/nodesx.c,v 1.56 2010/04/28 17:27:02 amb Exp $
   3
   4  Extented Node 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 <stdlib.h>
  27 #include <stdio.h>
  28 #include <string.h>
  29 #include <sys/stat.h>
  30
  31 #include "types.h"
  32 #include "functions.h"
  33 #include "nodesx.h"
  34 #include "segmentsx.h"
  35 #include "waysx.h"
  36 #include "segments.h"
  37 #include "nodes.h"
  38
  39
  40 /* Variables */
  41
  42 /*+ The command line '--slim' option. +*/
  43 extern int option_slim;
  44
  45 /*+ The command line '--tmpdir' option or its default value. +*/
  46 extern char *option_tmpdirname;
  47
  48 /*+ A temporary file-local variable for use by the sort functions. +*/
  49 static NodesX *sortnodesx;
  50
  51 /* Functions */
  52
  53 static int sort_by_id(NodeX *a,NodeX *b);
  54 static int index_by_id(NodeX *nodex,index_t index);
  55
  56 static int sort_by_lat_long(NodeX *a,NodeX *b);
  57 static int index_by_lat_long(NodeX *nodex,index_t index);
  58
  59
  60 /*++++++++++++++++++++++++++++++++++++++
  61   Allocate a new node list (create a new file or open an existing one).
  62
  63   NodesX *NewNodeList Returns the node list.
  64
  65   int append Set to 1 if the file is to be opened for appending (now or later).
  66   ++++++++++++++++++++++++++++++++++++++*/
  67
  68 NodesX *NewNodeList(int append)
  69 {
  70  NodesX *nodesx;
  71
  72  nodesx=(NodesX*)calloc(1,sizeof(NodesX));
  73
  74  assert(nodesx); /* Check calloc() worked */
  75
  76  nodesx->filename=(char*)malloc(strlen(option_tmpdirname)+32);
  77
  78  if(append)
  79     sprintf(nodesx->filename,"%s/nodes.input.tmp",option_tmpdirname);
  80  else
  81     sprintf(nodesx->filename,"%s/nodes.%p.tmp",option_tmpdirname,nodesx);
  82
  83  if(append)
  84    {
  85     off_t size;
  86
  87     nodesx->fd=AppendFile(nodesx->filename);
  88
  89     size=SizeFile(nodesx->filename);
  90
  91     nodesx->xnumber=size/sizeof(NodeX);
  92    }
  93  else
  94     nodesx->fd=OpenFile(nodesx->filename);
  95
  96  return(nodesx);
  97 }
  98
  99
 100 /*++++++++++++++++++++++++++++++++++++++
 101   Free a node list.
 102
 103   NodesX *nodesx The list to be freed.
 104
 105   int keep Set to 1 if the file is to be kept.
 106   ++++++++++++++++++++++++++++++++++++++*/
 107
 108 void FreeNodeList(NodesX *nodesx,int keep)
 109 {
 110  if(!keep)
 111     DeleteFile(nodesx->filename);
 112
 113  free(nodesx->filename);
 114
 115  if(nodesx->idata)
 116     free(nodesx->idata);
 117
 118  if(nodesx->ndata)
 119     free(nodesx->ndata);
 120
 121  if(nodesx->super)
 122     free(nodesx->super);
 123
 124  if(nodesx->offsets)
 125     free(nodesx->offsets);
 126
 127  free(nodesx);
 128 }
 129
 130
 131 /*++++++++++++++++++++++++++++++++++++++
 132   Append a node to a newly created node list (unsorted).
 133
 134   NodesX* nodesx The set of nodes to process.
 135
 136   node_t id The node identification.
 137
 138   double latitude The latitude of the node.
 139
 140   double longitude The longitude of the node.
 141   ++++++++++++++++++++++++++++++++++++++*/
 142
 143 void AppendNode(NodesX* nodesx,node_t id,double latitude,double longitude)
 144 {
 145  NodeX nodex;
 146
 147  assert(!nodesx->idata);        /* Must not have idata filled in => unsorted */
 148
 149  nodex.id=id;
 150  nodex.latitude =radians_to_latlong(latitude);
 151  nodex.longitude=radians_to_latlong(longitude);
 152
 153  WriteFile(nodesx->fd,&nodex,sizeof(NodeX));
 154
 155  nodesx->xnumber++;
 156 }
 157
 158
 159 /*++++++++++++++++++++++++++++++++++++++
 160   Sort the node list (i.e. create the sortable indexes).
 161
 162   NodesX* nodesx The set of nodes to process.
 163   ++++++++++++++++++++++++++++++++++++++*/
 164
 165 void SortNodeList(NodesX* nodesx)
 166 {
 167  int fd;
 168
 169  /* Check the start conditions */
 170
 171  assert(!nodesx->idata);        /* Must not have idata filled in => unsorted */
 172
 173  /* Print the start message */
 174
 175  printf("Sorting Nodes");
 176  fflush(stdout);
 177
 178  /* Close the files and re-open them (finished appending) */
 179
 180  CloseFile(nodesx->fd);
 181  nodesx->fd=ReOpenFile(nodesx->filename);
 182
 183  DeleteFile(nodesx->filename);
 184
 185  fd=OpenFile(nodesx->filename);
 186
 187  /* Allocate the array of indexes */
 188
 189  nodesx->idata=(node_t*)malloc(nodesx->xnumber*sizeof(node_t));
 190
 191  assert(nodesx->idata); /* Check malloc() worked */
 192
 193  /* Sort by node indexes */
 194
 195  sortnodesx=nodesx;
 196
 197  filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int (*)(const void*,const void*))sort_by_id,(int (*)(void*,index_t))index_by_id);
 198
 199  /* Close the files and re-open them */
 200
 201  CloseFile(nodesx->fd);
 202  CloseFile(fd);
 203
 204  nodesx->fd=ReOpenFile(nodesx->filename);
 205
 206  /* Print the final message */
 207
 208  printf("\rSorted Nodes: Nodes=%d Duplicates=%d\n",nodesx->xnumber,nodesx->xnumber-nodesx->number);
 209  fflush(stdout);
 210 }
 211
 212
 213 /*++++++++++++++++++++++++++++++++++++++
 214   Sort the nodes into id order.
 215
 216   int sort_by_id Returns the comparison of the id fields.
 217
 218   NodeX *a The first extended node.
 219
 220   NodeX *b The second extended node.
 221   ++++++++++++++++++++++++++++++++++++++*/
 222
 223 static int sort_by_id(NodeX *a,NodeX *b)
 224 {
 225  node_t a_id=a->id;
 226  node_t b_id=b->id;
 227
 228  if(a_id<b_id)
 229     return(-1);
 230  else if(a_id>b_id)
 231     return(1);
 232  else
 233     return(0);
 234 }
 235
 236
 237 /*++++++++++++++++++++++++++++++++++++++
 238   Index the nodes after sorting.
 239
 240   int index_by_id Return 1 if the value is to be kept, otherwise zero.
 241
 242   NodeX *nodex The extended node.
 243
 244   index_t index The index of this node in the total.
 245   ++++++++++++++++++++++++++++++++++++++*/
 246
 247 static int index_by_id(NodeX *nodex,index_t index)
 248 {
 249  if(index==0 || sortnodesx->idata[index-1]!=nodex->id)
 250    {
 251     sortnodesx->idata[index]=nodex->id;
 252
 253     sortnodesx->number++;
 254
 255     return(1);
 256    }
 257
 258  return(0);
 259 }
 260
 261
 262 /*++++++++++++++++++++++++++++++++++++++
 263   Sort the node list geographically.
 264
 265   NodesX* nodesx The set of nodes to process.
 266   ++++++++++++++++++++++++++++++++++++++*/
 267
 268 void SortNodeListGeographically(NodesX* nodesx)
 269 {
 270  int fd;
 271
 272  /* Print the start message */
 273
 274  printf("Sorting Nodes Geographically");
 275  fflush(stdout);
 276
 277  /* Allocate the memory for the geographical offsets array */
 278
 279  nodesx->offsets=(index_t*)malloc((nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
 280
 281  nodesx->latlonbin=0;
 282
 283  /* Close the files and re-open them */
 284
 285  CloseFile(nodesx->fd);
 286  nodesx->fd=ReOpenFile(nodesx->filename);
 287
 288  DeleteFile(nodesx->filename);
 289
 290  fd=OpenFile(nodesx->filename);
 291
 292  /* Sort geographically */
 293
 294  sortnodesx=nodesx;
 295
 296  filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int (*)(const void*,const void*))sort_by_lat_long,(int (*)(void*,index_t))index_by_lat_long);
 297
 298  /* Close the files and re-open them */
 299
 300  CloseFile(nodesx->fd);
 301  CloseFile(fd);
 302
 303  nodesx->fd=ReOpenFile(nodesx->filename);
 304
 305  /* Finish off the indexing */
 306
 307  for(;nodesx->latlonbin<=(nodesx->latbins*nodesx->lonbins);nodesx->latlonbin++)
 308     nodesx->offsets[nodesx->latlonbin]=nodesx->number;
 309
 310  /* Print the final message */
 311
 312  printf("\rSorted Nodes Geographically \n");
 313  fflush(stdout);
 314 }
 315
 316
 317 /*++++++++++++++++++++++++++++++++++++++
 318   Sort the nodes into latitude and longitude order.
 319
 320   int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
 321
 322   NodeX *a The first extended node.
 323
 324   NodeX *b The second extended node.
 325   ++++++++++++++++++++++++++++++++++++++*/
 326
 327 static int sort_by_lat_long(NodeX *a,NodeX *b)
 328 {
 329  ll_bin_t a_lon=latlong_to_bin(a->longitude);
 330  ll_bin_t b_lon=latlong_to_bin(b->longitude);
 331
 332  if(a_lon<b_lon)
 333     return(-1);
 334  else if(a_lon>b_lon)
 335     return(1);
 336  else
 337    {
 338     ll_bin_t a_lat=latlong_to_bin(a->latitude);
 339     ll_bin_t b_lat=latlong_to_bin(b->latitude);
 340
 341     if(a_lat<b_lat)
 342        return(-1);
 343     else if(a_lat>b_lat)
 344        return(1);
 345     else
 346       {
 347 #ifdef REGRESSION_TESTING
 348        // Need this for regression testing because heapsort() is not order
 349        // preserving like qsort() is (or was when tested).
 350
 351        index_t a_id=a->id;
 352        index_t b_id=b->id;
 353
 354        if(a_id<b_id)
 355           return(-1);
 356        else if(a_id>b_id)
 357           return(1);
 358        else
 359 #endif
 360           return(0);
 361       }
 362    }
 363 }
 364
 365
 366 /*++++++++++++++++++++++++++++++++++++++
 367   Index the nodes after sorting.
 368
 369   int index_by_lat_long Return 1 if the value is to be kept, otherwise zero.
 370
 371   NodeX *nodex The extended node.
 372
 373   index_t index The index of this node in the total.
 374   ++++++++++++++++++++++++++++++++++++++*/
 375
 376 static int index_by_lat_long(NodeX *nodex,index_t index)
 377 {
 378  /* Work out the offsets */
 379
 380  ll_bin_t latbin=latlong_to_bin(nodex->latitude )-sortnodesx->latzero;
 381  ll_bin_t lonbin=latlong_to_bin(nodex->longitude)-sortnodesx->lonzero;
 382  int llbin=lonbin*sortnodesx->latbins+latbin;
 383
 384  for(;sortnodesx->latlonbin<=llbin;sortnodesx->latlonbin++)
 385     sortnodesx->offsets[sortnodesx->latlonbin]=index;
 386
 387  return(1);
 388 }
 389
 390
 391 /*++++++++++++++++++++++++++++++++++++++
 392   Find a particular node index.
 393
 394   index_t IndexNodeX Returns the index of the extended node with the specified id.
 395
 396   NodesX* nodesx The set of nodes to process.
 397
 398   node_t id The node id to look for.
 399   ++++++++++++++++++++++++++++++++++++++*/
 400
 401 index_t IndexNodeX(NodesX* nodesx,node_t id)
 402 {
 403  int start=0;
 404  int end=nodesx->number-1;
 405  int mid;
 406
 407  assert(nodesx->idata);         /* Must have idata filled in => sorted by id */
 408
 409  /* Binary search - search key exact match only is required.
 410   *
 411   *  # <- start  |  Check mid and move start or end if it doesn't match
 412   *  #           |
 413   *  #           |  Since an exact match is wanted we can set end=mid-1
 414   *  # <- mid    |  or start=mid+1 because we know that mid doesn't match.
 415   *  #           |
 416   *  #           |  Eventually either end=start or end=start+1 and one of
 417   *  # <- end    |  start or end is the wanted one.
 418   */
 419
 420  if(end<start)                        /* There are no nodes */
 421     return(NO_NODE);
 422  else if(id<nodesx->idata[start])     /* Check key is not before start */
 423     return(NO_NODE);
 424  else if(id>nodesx->idata[end])       /* Check key is not after end */
 425     return(NO_NODE);
 426  else
 427    {
 428     do
 429       {
 430        mid=(start+end)/2;             /* Choose mid point */
 431
 432        if(nodesx->idata[mid]<id)      /* Mid point is too low */
 433           start=mid+1;
 434        else if(nodesx->idata[mid]>id) /* Mid point is too high */
 435           end=mid-1;
 436        else                           /* Mid point is correct */
 437           return(mid);
 438       }
 439     while((end-start)>1);
 440
 441     if(nodesx->idata[start]==id)      /* Start is correct */
 442        return(start);
 443
 444     if(nodesx->idata[end]==id)        /* End is correct */
 445        return(end);
 446    }
 447
 448  return(NO_NODE);
 449 }
 450
 451
 452 /*++++++++++++++++++++++++++++++++++++++
 453   Lookup a particular node.
 454
 455   NodeX *LookupNodeX Returns a pointer to the extended node with the specified id.
 456
 457   NodesX* nodesx The set of nodes to process.
 458
 459   index_t index The node index to look for.
 460
 461   int position The position in the cache to use.
 462   ++++++++++++++++++++++++++++++++++++++*/
 463
 464 NodeX *LookupNodeX(NodesX* nodesx,index_t index,int position)
 465 {
 466  assert(index!=NO_NODE);     /* Must be a valid node */
 467
 468  if(option_slim)
 469    {
 470     SeekFile(nodesx->fd,index*sizeof(NodeX));
 471
 472     ReadFile(nodesx->fd,&nodesx->cached[position-1],sizeof(NodeX));
 473
 474     return(&nodesx->cached[position-1]);
 475    }
 476  else
 477    {
 478     return(&nodesx->xdata[index]);
 479    }
 480 }
 481
 482
 483 /*++++++++++++++++++++++++++++++++++++++
 484   Remove any nodes that are not part of a highway.
 485
 486   NodesX *nodesx The complete node list.
 487
 488   SegmentsX *segmentsx The list of segments.
 489   ++++++++++++++++++++++++++++++++++++++*/
 490
 491 void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
 492 {
 493  NodeX nodex;
 494  int total=0,highway=0,nothighway=0;
 495  ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
 496  latlong_t lat_min,lat_max,lon_min,lon_max;
 497  int fd;
 498
 499  /* Check the start conditions */
 500
 501  assert(nodesx->idata);         /* Must have idata filled in => data sorted */
 502
 503  /* Print the start message */
 504
 505  printf("Checking: Nodes=0");
 506  fflush(stdout);
 507
 508  /* While we are here we can work out the range of data */
 509
 510  lat_min=radians_to_latlong( 2);
 511  lat_max=radians_to_latlong(-2);
 512  lon_min=radians_to_latlong( 4);
 513  lon_max=radians_to_latlong(-4);
 514
 515  /* Modify the on-disk image */
 516
 517  DeleteFile(nodesx->filename);
 518
 519  fd=OpenFile(nodesx->filename);
 520  SeekFile(nodesx->fd,0);
 521
 522  while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX)))
 523    {
 524     if(IndexFirstSegmentX(segmentsx,nodex.id)==NO_SEGMENT)
 525        nothighway++;
 526     else
 527       {
 528        nodex.id=highway;
 529
 530        WriteFile(fd,&nodex,sizeof(NodeX));
 531
 532        nodesx->idata[highway]=nodesx->idata[total];
 533        highway++;
 534
 535        if(nodex.latitude<lat_min)
 536           lat_min=nodex.latitude;
 537        if(nodex.latitude>lat_max)
 538           lat_max=nodex.latitude;
 539        if(nodex.longitude<lon_min)
 540           lon_min=nodex.longitude;
 541        if(nodex.longitude>lon_max)
 542           lon_max=nodex.longitude;
 543       }
 544
 545     total++;
 546
 547     if(!(total%10000))
 548       {
 549        printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",total,highway,nothighway);
 550        fflush(stdout);
 551       }
 552    }
 553
 554  /* Close the files and re-open them */
 555
 556  CloseFile(nodesx->fd);
 557  CloseFile(fd);
 558
 559  nodesx->fd=ReOpenFile(nodesx->filename);
 560
 561  nodesx->number=highway;
 562
 563  /* Work out the number of bins */
 564
 565  lat_min_bin=latlong_to_bin(lat_min);
 566  lon_min_bin=latlong_to_bin(lon_min);
 567  lat_max_bin=latlong_to_bin(lat_max);
 568  lon_max_bin=latlong_to_bin(lon_max);
 569
 570  nodesx->latzero=lat_min_bin;
 571  nodesx->lonzero=lon_min_bin;
 572
 573  nodesx->latbins=(lat_max_bin-lat_min_bin)+1;
 574  nodesx->lonbins=(lon_max_bin-lon_min_bin)+1;
 575
 576  /* Allocate and clear the super-node markers */
 577
 578  nodesx->super=(uint8_t*)calloc(nodesx->number,sizeof(uint8_t));
 579
 580  assert(nodesx->super); /* Check calloc() worked */
 581
 582  /* Print the final message */
 583
 584  printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d  \n",total,highway,nothighway);
 585  fflush(stdout);
 586 }
 587
 588
 589 /*++++++++++++++++++++++++++++++++++++++
 590   Create the real node data.
 591
 592   NodesX *nodesx The set of nodes to use.
 593
 594   int iteration The final super-node iteration.
 595   ++++++++++++++++++++++++++++++++++++++*/
 596
 597 void CreateRealNodes(NodesX *nodesx,int iteration)
 598 {
 599  index_t i;
 600
 601  /* Check the start conditions */
 602
 603  assert(!nodesx->ndata);        /* Must not have ndata filled in => no real nodes */
 604
 605  /* Print the start message */
 606
 607  printf("Creating Real Nodes: Nodes=0");
 608  fflush(stdout);
 609
 610  /* Map into memory */
 611
 612  if(!option_slim)
 613     nodesx->xdata=MapFile(nodesx->filename);
 614
 615  /* Allocate the memory */
 616
 617  nodesx->ndata=(Node*)malloc(nodesx->number*sizeof(Node));
 618
 619  assert(nodesx->ndata); /* Check malloc() worked */
 620
 621  /* Loop through and allocate. */
 622
 623  for(i=0;i<nodesx->number;i++)
 624    {
 625     NodeX *nodex=LookupNodeX(nodesx,i,1);
 626
 627     nodesx->ndata[nodex->id].latoffset=latlong_to_off(nodex->latitude);
 628     nodesx->ndata[nodex->id].lonoffset=latlong_to_off(nodex->longitude);
 629     nodesx->ndata[nodex->id].firstseg=SEGMENT(NO_SEGMENT);
 630
 631     if(nodesx->super[nodex->id]==iteration)
 632        nodesx->ndata[nodex->id].firstseg|=NODE_SUPER;
 633
 634     if(!((i+1)%10000))
 635       {
 636        printf("\rCreating Real Nodes: Nodes=%d",i+1);
 637        fflush(stdout);
 638       }
 639    }
 640
 641  /* Free the unneeded memory */
 642
 643  free(nodesx->super);
 644  nodesx->super=NULL;
 645
 646  /* Unmap from memory */
 647
 648  if(!option_slim)
 649     nodesx->xdata=UnmapFile(nodesx->filename);
 650
 651  /* Print the final message */
 652
 653  printf("\rCreating Real Nodes: Nodes=%d \n",nodesx->number);
 654  fflush(stdout);
 655 }
 656
 657
 658 /*++++++++++++++++++++++++++++++++++++++
 659   Assign the segment indexes to the nodes.
 660
 661   NodesX *nodesx The list of nodes to process.
 662
 663   SegmentsX* segmentsx The set of segments to use.
 664   ++++++++++++++++++++++++++++++++++++++*/
 665
 666 void IndexNodes(NodesX *nodesx,SegmentsX *segmentsx)
 667 {
 668  index_t i;
 669
 670  /* Check the start conditions */
 671
 672  assert(nodesx->ndata);         /* Must have ndata filled in => real nodes exist */
 673  assert(segmentsx->sdata);      /* Must have sdata filled in => real segments exist */
 674
 675  /* Print the start message */
 676
 677  printf("Indexing Segments: Segments=0");
 678  fflush(stdout);
 679
 680  /* Map into memory */
 681
 682  if(!option_slim)
 683    {
 684     nodesx->xdata=MapFile(nodesx->filename);
 685     segmentsx->xdata=MapFile(segmentsx->filename);
 686    }
 687
 688  /* Index the nodes */
 689
 690  for(i=0;i<segmentsx->number;i++)
 691    {
 692     SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);
 693     node_t id1=segmentx->node1;
 694     node_t id2=segmentx->node2;
 695     Node *node1=&nodesx->ndata[id1];
 696     Node *node2=&nodesx->ndata[id2];
 697
 698     /* Check node1 */
 699
 700     if(SEGMENT(node1->firstseg)==SEGMENT(NO_SEGMENT))
 701       {
 702        node1->firstseg^=SEGMENT(NO_SEGMENT);
 703        node1->firstseg|=i;
 704       }
 705     else
 706       {
 707        index_t index=SEGMENT(node1->firstseg);
 708
 709        do
 710          {
 711           segmentx=LookupSegmentX(segmentsx,index,1);
 712
 713           if(segmentx->node1==id1)
 714             {
 715              index++;
 716
 717              if(index>=segmentsx->number)
 718                 break;
 719
 720              segmentx=LookupSegmentX(segmentsx,index,1);
 721
 722              if(segmentx->node1!=id1)
 723                 break;
 724             }
 725           else
 726             {
 727              if(segmentsx->sdata[index].next2==NO_NODE)
 728                {
 729                 segmentsx->sdata[index].next2=i;
 730                 break;
 731                }
 732              else
 733                 index=segmentsx->sdata[index].next2;
 734             }
 735          }
 736        while(1);
 737       }
 738
 739     /* Check node2 */
 740
 741     if(SEGMENT(node2->firstseg)==SEGMENT(NO_SEGMENT))
 742       {
 743        node2->firstseg^=SEGMENT(NO_SEGMENT);
 744        node2->firstseg|=i;
 745       }
 746     else
 747       {
 748        index_t index=SEGMENT(node2->firstseg);
 749
 750        do
 751          {
 752           segmentx=LookupSegmentX(segmentsx,index,1);
 753
 754           if(segmentx->node1==id2)
 755             {
 756              index++;
 757
 758              if(index>=segmentsx->number)
 759                 break;
 760
 761              segmentx=LookupSegmentX(segmentsx,index,1);
 762
 763              if(segmentx->node1!=id2)
 764                 break;
 765             }
 766           else
 767             {
 768              if(segmentsx->sdata[index].next2==NO_NODE)
 769                {
 770                 segmentsx->sdata[index].next2=i;
 771                 break;
 772                }
 773              else
 774                 index=segmentsx->sdata[index].next2;
 775             }
 776          }
 777        while(1);
 778       }
 779
 780     if(!((i+1)%10000))
 781       {
 782        printf("\rIndexing Segments: Segments=%d",i+1);
 783        fflush(stdout);
 784       }
 785    }
 786
 787  /* Unmap from memory */
 788
 789  if(!option_slim)
 790    {
 791     nodesx->xdata=UnmapFile(nodesx->filename);
 792     segmentsx->xdata=UnmapFile(segmentsx->filename);
 793    }
 794
 795  /* Print the final message */
 796
 797  printf("\rIndexed Segments: Segments=%d \n",segmentsx->number);
 798  fflush(stdout);
 799 }
 800
 801
 802 /*++++++++++++++++++++++++++++++++++++++
 803   Save the node list to a file.
 804
 805   NodesX* nodesx The set of nodes to save.
 806
 807   const char *filename The name of the file to save.
 808   ++++++++++++++++++++++++++++++++++++++*/
 809
 810 void SaveNodeList(NodesX* nodesx,const char *filename)
 811 {
 812  index_t i;
 813  int fd;
 814  Nodes *nodes;
 815  int super_number=0;
 816
 817  /* Check the start conditions */
 818
 819  assert(nodesx->ndata);         /* Must have ndata filled in => real nodes exist */
 820
 821  /* Print the start message */
 822
 823  printf("Writing Nodes: Nodes=0");
 824  fflush(stdout);
 825
 826  /* Map into memory */
 827
 828  if(!option_slim)
 829     nodesx->xdata=MapFile(nodesx->filename);
 830
 831  /* Count the number of super-nodes */
 832
 833  for(i=0;i<nodesx->number;i++)
 834     if(nodesx->ndata[i].firstseg&NODE_SUPER)
 835        super_number++;
 836
 837  /* Fill in a Nodes structure with the offset of the real data in the file after
 838     the Node structure itself. */
 839
 840  nodes=calloc(1,sizeof(Nodes));
 841
 842  assert(nodes); /* Check calloc() worked */
 843
 844  nodes->number=nodesx->number;
 845  nodes->snumber=super_number;
 846
 847  nodes->latbins=nodesx->latbins;
 848  nodes->lonbins=nodesx->lonbins;
 849
 850  nodes->latzero=nodesx->latzero;
 851  nodes->lonzero=nodesx->lonzero;
 852
 853  nodes->data=NULL;
 854  nodes->offsets=NULL;
 855  nodes->nodes=NULL;
 856
 857  /* Write out the Nodes structure and then the real data. */
 858
 859  fd=OpenFile(filename);
 860
 861  WriteFile(fd,nodes,sizeof(Nodes));
 862
 863  WriteFile(fd,nodesx->offsets,(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));
 864
 865  for(i=0;i<nodes->number;i++)
 866    {
 867     NodeX *nodex=LookupNodeX(nodesx,i,1);
 868     Node *node=&nodesx->ndata[nodex->id];
 869
 870     WriteFile(fd,node,sizeof(Node));
 871
 872     if(!((i+1)%10000))
 873       {
 874        printf("\rWriting Nodes: Nodes=%d",i+1);
 875        fflush(stdout);
 876       }
 877    }
 878
 879  CloseFile(fd);
 880
 881  /* Unmap from memory */
 882
 883  if(!option_slim)
 884     nodesx->xdata=UnmapFile(nodesx->filename);
 885
 886  /* Print the final message */
 887
 888  printf("\rWrote Nodes: Nodes=%d  \n",nodes->number);
 889  fflush(stdout);
 890
 891  /* Free the fake Nodes */
 892
 893  free(nodes);
 894 }