trunk/src/nodesx.c

/***************************************
 Extented Node data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2012 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ***************************************/


#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/stat.h>

#include "types.h"
#include "nodes.h"
#include "segments.h"

#include "nodesx.h"
#include "segmentsx.h"
#include "waysx.h"

#include "types.h"

#include "files.h"
#include "logging.h"
#include "sorting.h"


/* Variables */

/*+ The command line '--tmpdir' option or its default value. +*/
extern char *option_tmpdirname;

/*+ A temporary file-local variable for use by the sort functions. +*/
static NodesX *sortnodesx;

/* Functions */

static int sort_by_id(NodeX *a,NodeX *b);
static int deduplicate_and_index_by_id(NodeX *nodex,index_t index);

static int sort_by_lat_long(NodeX *a,NodeX *b);
static int delete_pruned_and_index_by_lat_long(NodeX *nodex,index_t index);


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new node list (create a new file or open an existing one).

  NodesX *NewNodeList Returns a pointer to the node list.

  int append Set to 1 if the file is to be opened for appending (now or later).
  ++++++++++++++++++++++++++++++++++++++*/

NodesX *NewNodeList(int append)
{
 NodesX *nodesx;

 nodesx=(NodesX*)calloc(1,sizeof(NodesX));

 assert(nodesx); /* Check calloc() worked */

 nodesx->filename=(char*)malloc(strlen(option_tmpdirname)+32);

 if(append)
    sprintf(nodesx->filename,"%s/nodesx.input.tmp",option_tmpdirname);
 else
    sprintf(nodesx->filename,"%s/nodesx.%p.tmp",option_tmpdirname,(void*)nodesx);

 if(append)
   {
    off_t size;

    nodesx->fd=OpenFileAppend(nodesx->filename);

    size=SizeFile(nodesx->filename);

    nodesx->number=size/sizeof(NodeX);
   }
 else
    nodesx->fd=OpenFileNew(nodesx->filename);

 return(nodesx);
}


/*++++++++++++++++++++++++++++++++++++++
  Free a node list.

  NodesX *nodesx The set of nodes to be freed.

  int keep Set to 1 if the file is to be kept (for appending later).
  ++++++++++++++++++++++++++++++++++++++*/

void FreeNodeList(NodesX *nodesx,int keep)
{
 if(!keep)
    DeleteFile(nodesx->filename);

 free(nodesx->filename);

 if(nodesx->idata)
    free(nodesx->idata);

 if(nodesx->gdata)
    free(nodesx->gdata);

 if(nodesx->super)
    free(nodesx->super);

 free(nodesx);
}


/*++++++++++++++++++++++++++++++++++++++
  Append a single node to an unsorted node list.

  NodesX *nodesx The set of nodes to modify.

  node_t id The node identifier from the original OSM data.

  double latitude The latitude of the node.

  double longitude The longitude of the node.

  transports_t allow The allowed traffic types through the node.

  uint16_t flags The flags to set for this node.
  ++++++++++++++++++++++++++++++++++++++*/

void AppendNode(NodesX *nodesx,node_t id,double latitude,double longitude,transports_t allow,uint16_t flags)
{
 NodeX nodex;

 nodex.id=id;
 nodex.latitude =radians_to_latlong(latitude);
 nodex.longitude=radians_to_latlong(longitude);
 nodex.allow=allow;
 nodex.flags=flags;

 WriteFile(nodesx->fd,&nodex,sizeof(NodeX));

 nodesx->number++;

 assert(nodesx->number<NODE_FAKE); /* NODE_FAKE marks the high-water mark for real nodes. */
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the node list.

  NodesX *nodesx The set of nodes to modify.
  ++++++++++++++++++++++++++++++++++++++*/

void SortNodeList(NodesX *nodesx)
{
 int fd;
 index_t xnumber;

 /* Print the start message */

 printf_first("Sorting Nodes");

 /* Close the file (finished appending) */

 nodesx->fd=CloseFile(nodesx->fd);

 /* Re-open the file read-only and a new file writeable */

 nodesx->fd=ReOpenFile(nodesx->filename);

 DeleteFile(nodesx->filename);

 fd=OpenFileNew(nodesx->filename);

 /* Allocate the array of indexes */

 nodesx->idata=(node_t*)malloc(nodesx->number*sizeof(node_t));

 assert(nodesx->idata); /* Check malloc() worked */

 /* Sort by node indexes */

 xnumber=nodesx->number;
 nodesx->number=0;

 sortnodesx=nodesx;

 nodesx->number=filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int (*)(const void*,const void*))sort_by_id,(int (*)(void*,index_t))deduplicate_and_index_by_id);

 /* Close the files */

 nodesx->fd=CloseFile(nodesx->fd);
 CloseFile(fd);

 /* Print the final message */

 printf_last("Sorted Nodes: Nodes=%"Pindex_t" Duplicates=%"Pindex_t,xnumber,xnumber-nodesx->number);
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the nodes into id order.

  int sort_by_id Returns the comparison of the id fields.

  NodeX *a The first extended node.

  NodeX *b The second extended node.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_id(NodeX *a,NodeX *b)
{
 node_t a_id=a->id;
 node_t b_id=b->id;

 if(a_id<b_id)
    return(-1);
 else if(a_id>b_id)
    return(1);
 else
    return(0);
}


/*++++++++++++++++++++++++++++++++++++++
  Create the index of identifiers and discard duplicate nodes.

  int deduplicate_and_index_by_id Return 1 if the value is to be kept, otherwise 0.

  NodeX *nodex The extended node.

  index_t index The index of this node in the total.
  ++++++++++++++++++++++++++++++++++++++*/

static int deduplicate_and_index_by_id(NodeX *nodex,index_t index)
{
 if(index==0 || sortnodesx->idata[index-1]!=nodex->id)
   {
    sortnodesx->idata[index]=nodex->id;

    return(1);
   }
 else
   {
    logerror("Node %"Pnode_t" is duplicated\n",nodex->id);

    return(0);
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the node list geographically.

  NodesX *nodesx The set of nodes to modify.
  ++++++++++++++++++++++++++++++++++++++*/

void SortNodeListGeographically(NodesX *nodesx)
{
 int fd;
 index_t kept;

 /* Print the start message */

 printf_first("Sorting Nodes Geographically (Deleting Pruned)");

 /* Allocate the memory for the geographical index array */

 nodesx->gdata=(index_t*)malloc(nodesx->number*sizeof(index_t));

 assert(nodesx->gdata); /* Check malloc() worked */

 /* Re-open the file read-only and a new file writeable */

 nodesx->fd=ReOpenFile(nodesx->filename);

 DeleteFile(nodesx->filename);

 fd=OpenFileNew(nodesx->filename);

 /* Sort geographically */

 sortnodesx=nodesx;

 kept=filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int (*)(const void*,const void*))sort_by_lat_long,(int (*)(void*,index_t))delete_pruned_and_index_by_lat_long);

 /* Close the files */

 nodesx->fd=CloseFile(nodesx->fd);
 CloseFile(fd);

 /* Print the final message */

 printf_last("Sorted Nodes Geographically: Nodes=%"Pindex_t" Deleted=%"Pindex_t,kept,nodesx->number-kept);
 nodesx->number=kept;
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the nodes into latitude and longitude order (first by longitude bin
  number, then by latitude bin number and then by exact longitude and then by
  exact latitude).

  int sort_by_lat_long Returns the comparison of the latitude and longitude fields.

  NodeX *a The first extended node.

  NodeX *b The second extended node.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_lat_long(NodeX *a,NodeX *b)
{
 int a_pruned=IsPrunedNodeX(a);
 int b_pruned=IsPrunedNodeX(b);

 if(a_pruned && b_pruned)
    return(0);
 else if(a_pruned)
    return(1);
 else if(b_pruned)
    return(-1);
 else
   {
    ll_bin_t a_lon=latlong_to_bin(a->longitude);
    ll_bin_t b_lon=latlong_to_bin(b->longitude);

    if(a_lon<b_lon)
       return(-1);
    else if(a_lon>b_lon)
       return(1);
    else
      {
       ll_bin_t a_lat=latlong_to_bin(a->latitude);
       ll_bin_t b_lat=latlong_to_bin(b->latitude);

       if(a_lat<b_lat)
          return(-1);
       else if(a_lat>b_lat)
          return(1);
       else
         {
          if(a->longitude<b->longitude)
             return(-1);
          else if(a->longitude>b->longitude)
             return(1);
          else
            {
             if(a->latitude<b->latitude)
                return(-1);
             else if(a->latitude>b->latitude)
                return(1);
            }

          return(0);
         }
      }
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Delete the pruned nodes and create the index between the sorted and unsorted nodes.

  int delete_pruned_and_index_by_lat_long Return 1 if the value is to be kept, otherwise 0.

  NodeX *nodex The extended node.

  index_t index The index of this node in the total.
  ++++++++++++++++++++++++++++++++++++++*/

static int delete_pruned_and_index_by_lat_long(NodeX *nodex,index_t index)
{
 if(IsPrunedNodeX(nodex))
    return(0);

 /* Create the index from the previous sort to the current one */

 sortnodesx->gdata[nodex->id]=index;

 return(1);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a particular node index.

  index_t IndexNodeX Returns the index of the extended node with the specified id.

  NodesX *nodesx The set of nodes to use.

  node_t id The node id to look for.
  ++++++++++++++++++++++++++++++++++++++*/

index_t IndexNodeX(NodesX *nodesx,node_t id)
{
 index_t start=0;
 index_t end=nodesx->number-1;
 index_t mid;

 /* Binary search - search key exact match only is required.
  *
  *  # <- start  |  Check mid and move start or end if it doesn't match
  *  #           |
  *  #           |  Since an exact match is wanted we can set end=mid-1
  *  # <- mid    |  or start=mid+1 because we know that mid doesn't match.
  *  #           |
  *  #           |  Eventually either end=start or end=start+1 and one of
  *  # <- end    |  start or end is the wanted one.
  */

 if(end<start)                        /* There are no nodes */
    return(NO_NODE);
 else if(id<nodesx->idata[start])     /* Check key is not before start */
    return(NO_NODE);
 else if(id>nodesx->idata[end])       /* Check key is not after end */
    return(NO_NODE);
 else
   {
    do
      {
       mid=(start+end)/2;             /* Choose mid point */

       if(nodesx->idata[mid]<id)      /* Mid point is too low */
          start=mid+1;
       else if(nodesx->idata[mid]>id) /* Mid point is too high */
          end=mid?(mid-1):mid;
       else                           /* Mid point is correct */
          return(mid);
      }
    while((end-start)>1);

    if(nodesx->idata[start]==id)      /* Start is correct */
       return(start);

    if(nodesx->idata[end]==id)        /* End is correct */
       return(end);
   }

 return(NO_NODE);
}


/*++++++++++++++++++++++++++++++++++++++
  Remove any nodes that are not part of a highway.

  NodesX *nodesx The set of nodes to modify.

  SegmentsX *segmentsx The set of segments to use.
  ++++++++++++++++++++++++++++++++++++++*/

void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
{
 NodeX nodex;
 index_t total=0,highway=0,nothighway=0;
 ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
 latlong_t lat_min,lat_max,lon_min,lon_max;
 int fd;

 /* Print the start message */

 printf_first("Checking Nodes: Nodes=0");

 /* While we are here we can work out the range of data */

 lat_min=radians_to_latlong( 2);
 lat_max=radians_to_latlong(-2);
 lon_min=radians_to_latlong( 4);
 lon_max=radians_to_latlong(-4);

 /* Re-open the file read-only and a new file writeable */

 nodesx->fd=ReOpenFile(nodesx->filename);

 DeleteFile(nodesx->filename);

 fd=OpenFileNew(nodesx->filename);

 /* Modify the on-disk image */

 while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX)))
   {
    if(!IsBitSet(segmentsx->usednode,total))
       nothighway++;
    else
      {
       nodex.id=highway;

       WriteFile(fd,&nodex,sizeof(NodeX));

       nodesx->idata[highway]=nodesx->idata[total];
       highway++;

       if(nodex.latitude<lat_min)
          lat_min=nodex.latitude;
       if(nodex.latitude>lat_max)
          lat_max=nodex.latitude;
       if(nodex.longitude<lon_min)
          lon_min=nodex.longitude;
       if(nodex.longitude>lon_max)
          lon_max=nodex.longitude;
      }

    total++;

    if(!(total%10000))
       printf_middle("Checking Nodes: Nodes=%"Pindex_t" Highway=%"Pindex_t" not-Highway=%"Pindex_t,total,highway,nothighway);
   }

 nodesx->number=highway;

 /* Close the files */

 nodesx->fd=CloseFile(nodesx->fd);
 CloseFile(fd);

 /* Work out the number of bins */

 lat_min_bin=latlong_to_bin(lat_min);
 lon_min_bin=latlong_to_bin(lon_min);
 lat_max_bin=latlong_to_bin(lat_max);
 lon_max_bin=latlong_to_bin(lon_max);

 nodesx->latzero=lat_min_bin;
 nodesx->lonzero=lon_min_bin;

 nodesx->latbins=(lat_max_bin-lat_min_bin)+1;
 nodesx->lonbins=(lon_max_bin-lon_min_bin)+1;

 /* Free the now-unneeded index */

 free(segmentsx->usednode);
 segmentsx->usednode=NULL;

 /* Print the final message */

 printf_last("Checked Nodes: Nodes=%"Pindex_t" Highway=%"Pindex_t" not-Highway=%"Pindex_t,total,highway,nothighway);
}


/*++++++++++++++++++++++++++++++++++++++
  Insert the super-node flag and the first segment indexes after geographical sorting.

  NodesX *nodesx The set of nodes to modify.

  SegmentsX *segmentsx The set of segments to use.
  ++++++++++++++++++++++++++++++++++++++*/

void UpdateNodes(NodesX *nodesx,SegmentsX *segmentsx)
{
 index_t i;
 int fd;

 /* Print the start message */

 printf_first("Updating Super Nodes: Nodes=0");

 /* Re-open the file read-only and a new file writeable */

 nodesx->fd=ReOpenFile(nodesx->filename);

 DeleteFile(nodesx->filename);

 fd=OpenFileNew(nodesx->filename);

 /* Modify the on-disk image */

 for(i=0;i<nodesx->number;i++)
   {
    NodeX nodex;

    ReadFile(nodesx->fd,&nodex,sizeof(NodeX));

    if(IsBitSet(nodesx->super,nodex.id))
       nodex.flags|=NODE_SUPER;

    nodex.id=segmentsx->firstnode[nodesx->gdata[nodex.id]];

    WriteFile(fd,&nodex,sizeof(NodeX));

    if(!((i+1)%10000))
       printf_middle("Updating Super Nodes: Nodes=%"Pindex_t,i+1);
   }

 /* Close the files */

 nodesx->fd=CloseFile(nodesx->fd);
 CloseFile(fd);

 /* Free the memory */

 free(nodesx->super);
 nodesx->super=NULL;

 /* Print the final message */

 printf_last("Updated Super Nodes: Nodes=%"Pindex_t,nodesx->number);
}


/*++++++++++++++++++++++++++++++++++++++
  Save the final node list database to a file.

  NodesX *nodesx The set of nodes to save.

  const char *filename The name of the file to save.
  ++++++++++++++++++++++++++++++++++++++*/

void SaveNodeList(NodesX *nodesx,const char *filename)
{
 index_t i;
 int fd;
 NodesFile nodesfile={0};
 index_t super_number=0;
 ll_bin2_t latlonbin=0,maxlatlonbins;
 index_t *offsets;

 /* Print the start message */

 printf_first("Writing Nodes: Nodes=0");

 /* Allocate the memory for the geographical offsets array */

 offsets=(index_t*)malloc((nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));

 assert(offsets); /* Check malloc() worked */

 latlonbin=0;

 /* Re-open the file */

 nodesx->fd=ReOpenFile(nodesx->filename);

 /* Write out the nodes data */

 fd=OpenFileNew(filename);

 SeekFile(fd,sizeof(NodesFile)+(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));

 for(i=0;i<nodesx->number;i++)
   {
    NodeX nodex;
    Node node={0};
    ll_bin_t latbin,lonbin;
    ll_bin2_t llbin;

    ReadFile(nodesx->fd,&nodex,sizeof(NodeX));

    /* Create the Node */

    node.latoffset=latlong_to_off(nodex.latitude);
    node.lonoffset=latlong_to_off(nodex.longitude);
    node.firstseg=nodex.id;
    node.allow=nodex.allow;
    node.flags=nodex.flags;

    if(node.flags&NODE_SUPER)
       super_number++;

    /* Work out the offsets */

    latbin=latlong_to_bin(nodex.latitude )-nodesx->latzero;
    lonbin=latlong_to_bin(nodex.longitude)-nodesx->lonzero;
    llbin=lonbin*nodesx->latbins+latbin;

    for(;latlonbin<=llbin;latlonbin++)
       offsets[latlonbin]=i;

    /* Write the data */

    WriteFile(fd,&node,sizeof(Node));

    if(!((i+1)%10000))
       printf_middle("Writing Nodes: Nodes=%"Pindex_t,i+1);
   }

 /* Close the file */

 nodesx->fd=CloseFile(nodesx->fd);

 /* Finish off the offset indexing and write them out */

 maxlatlonbins=nodesx->latbins*nodesx->lonbins;

 for(;latlonbin<=maxlatlonbins;latlonbin++)
    offsets[latlonbin]=nodesx->number;

 SeekFile(fd,sizeof(NodesFile));
 WriteFile(fd,offsets,(nodesx->latbins*nodesx->lonbins+1)*sizeof(index_t));

 free(offsets);

 /* Write out the header structure */

 nodesfile.number=nodesx->number;
 nodesfile.snumber=super_number;

 nodesfile.latbins=nodesx->latbins;
 nodesfile.lonbins=nodesx->lonbins;

 nodesfile.latzero=nodesx->latzero;
 nodesfile.lonzero=nodesx->lonzero;

 SeekFile(fd,0);
 WriteFile(fd,&nodesfile,sizeof(NodesFile));

 CloseFile(fd);

 /* Print the final message */

 printf_last("Wrote Nodes: Nodes=%"Pindex_t,nodesx->number);
}
1	amb	110	/***************************************
2			Extented Node data type functions.
3	amb	151
4			Part of the Routino routing software.
5	amb	110	****************/ /****************
6	amb	947	This file Copyright 2008-2012 Andrew M. Bishop
7	amb	110
8	amb	151	This program is free software: you can redistribute it and/or modify
9			it under the terms of the GNU Affero General Public License as published by
10			the Free Software Foundation, either version 3 of the License, or
11			(at your option) any later version.
12
13			This program is distributed in the hope that it will be useful,
14			but WITHOUT ANY WARRANTY; without even the implied warranty of
15			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16			GNU Affero General Public License for more details.
17
18			You should have received a copy of the GNU Affero General Public License
19			along with this program. If not, see <http://www.gnu.org/licenses/>.
20	amb	110	***************************************/
21
22
23			#include <assert.h>
24			#include <stdlib.h>
25			#include <stdio.h>
26	amb	249	#include <string.h>
27	amb	326	#include <sys/stat.h>
28	amb	110
29			#include "types.h"
30	amb	449	#include "nodes.h"
31			#include "segments.h"
32
33	amb	110	#include "nodesx.h"
34			#include "segmentsx.h"
35	amb	204	#include "waysx.h"
36	amb	110
37	amb	466	#include "types.h"
38
39	amb	449	#include "files.h"
40	amb	519	#include "logging.h"
41	amb	532	#include "sorting.h"
42	amb	110
43	amb	449
44	amb	252	/* Variables */
45	amb	110
46	amb	289	/+ The command line '--tmpdir' option or its default value. +/
47	amb	284	extern char *option_tmpdirname;
48	amb	110
49	amb	284	/+ A temporary file-local variable for use by the sort functions. +/
50			static NodesX *sortnodesx;
51
52	amb	110	/* Functions */
53
54	amb	271	static int sort_by_id(NodeX a,NodeX b);
55	amb	680	static int deduplicate_and_index_by_id(NodeX *nodex,index_t index);
56	amb	271
57	amb	281	static int sort_by_lat_long(NodeX a,NodeX b);
58	amb	949	static int delete_pruned_and_index_by_lat_long(NodeX *nodex,index_t index);
59	amb	110
60
61			/*++++++++++++++++++++++++++++++++++++++
62	amb	326	Allocate a new node list (create a new file or open an existing one).
63	amb	110
64	amb	680	NodesX *NewNodeList Returns a pointer to the node list.
65	amb	326
66			int append Set to 1 if the file is to be opened for appending (now or later).
67	amb	110	++++++++++++++++++++++++++++++++++++++*/
68
69	amb	326	NodesX *NewNodeList(int append)
70	amb	110	{
71			NodesX *nodesx;
72
73	amb	213	nodesx=(NodesX*)calloc(1,sizeof(NodesX));
74	amb	110
75	amb	243	assert(nodesx); /* Check calloc() worked */
76
77	amb	284	nodesx->filename=(char*)malloc(strlen(option_tmpdirname)+32);
78	amb	216
79	amb	326	if(append)
80	amb	447	sprintf(nodesx->filename,"%s/nodesx.input.tmp",option_tmpdirname);
81	amb	326	else
82	amb	788	sprintf(nodesx->filename,"%s/nodesx.%p.tmp",option_tmpdirname,(void*)nodesx);
83	amb	249
84	amb	326	if(append)
85			{
86	amb	331	off_t size;
87	amb	326
88	amb	502	nodesx->fd=OpenFileAppend(nodesx->filename);
89	amb	326
90	amb	331	size=SizeFile(nodesx->filename);
91	amb	326
92	amb	650	nodesx->number=size/sizeof(NodeX);
93	amb	326	}
94			else
95	amb	502	nodesx->fd=OpenFileNew(nodesx->filename);
96	amb	326
97	amb	110	return(nodesx);
98			}
99
100
101			/*++++++++++++++++++++++++++++++++++++++
102	amb	226	Free a node list.
103
104	amb	681	NodesX *nodesx The set of nodes to be freed.
105	amb	326
106	amb	680	int keep Set to 1 if the file is to be kept (for appending later).
107	amb	226	++++++++++++++++++++++++++++++++++++++*/
108
109	amb	326	void FreeNodeList(NodesX *nodesx,int keep)
110	amb	226	{
111	amb	326	if(!keep)
112			DeleteFile(nodesx->filename);
113
114	amb	283	free(nodesx->filename);
115	amb	226
116			if(nodesx->idata)
117			free(nodesx->idata);
118
119	amb	552	if(nodesx->gdata)
120			free(nodesx->gdata);
121	amb	226
122	amb	283	if(nodesx->super)
123			free(nodesx->super);
124
125	amb	226	free(nodesx);
126			}
127
128
129			/*++++++++++++++++++++++++++++++++++++++
130	amb	493	Append a single node to an unsorted node list.
131	amb	243
132	amb	681	NodesX *nodesx The set of nodes to modify.
133	amb	243
134	amb	680	node_t id The node identifier from the original OSM data.
135	amb	110
136	amb	252	double latitude The latitude of the node.
137	amb	110
138	amb	252	double longitude The longitude of the node.
139	amb	469
140	amb	529	transports_t allow The allowed traffic types through the node.
141	amb	537
142	amb	538	uint16_t flags The flags to set for this node.
143	amb	252	++++++++++++++++++++++++++++++++++++++*/
144	amb	110
145	amb	681	void AppendNode(NodesX *nodesx,node_t id,double latitude,double longitude,transports_t allow,uint16_t flags)
146	amb	252	{
147			NodeX nodex;
148	amb	249
149	amb	252	nodex.id=id;
150			nodex.latitude =radians_to_latlong(latitude);
151			nodex.longitude=radians_to_latlong(longitude);
152	amb	469	nodex.allow=allow;
153	amb	538	nodex.flags=flags;
154	amb	252
155			WriteFile(nodesx->fd,&nodex,sizeof(NodeX));
156
157	amb	650	nodesx->number++;
158	amb	466
159	amb	650	assert(nodesx->number<NODE_FAKE); /* NODE_FAKE marks the high-water mark for real nodes. */
160	amb	110	}
161
162
163			/*++++++++++++++++++++++++++++++++++++++
164	amb	680	Sort the node list.
165	amb	110
166	amb	681	NodesX *nodesx The set of nodes to modify.
167	amb	110	++++++++++++++++++++++++++++++++++++++*/
168
169	amb	681	void SortNodeList(NodesX *nodesx)
170	amb	110	{
171	amb	263	int fd;
172	amb	650	index_t xnumber;
173	amb	110
174	amb	263	/* Print the start message */
175
176	amb	519	printf_first("Sorting Nodes");
177	amb	132
178	amb	555	/* Close the file (finished appending) */
179	amb	260
180	amb	612	nodesx->fd=CloseFile(nodesx->fd);
181	amb	555
182			/* Re-open the file read-only and a new file writeable */
183
184	amb	260	nodesx->fd=ReOpenFile(nodesx->filename);
185
186	amb	271	DeleteFile(nodesx->filename);
187
188	amb	502	fd=OpenFileNew(nodesx->filename);
189	amb	271
190	amb	252	/* Allocate the array of indexes */
191	amb	249
192	amb	650	nodesx->idata=(node_t)malloc(nodesx->numbersizeof(node_t));
193	amb	249
194	amb	252	assert(nodesx->idata); /* Check malloc() worked */
195	amb	249
196	amb	271	/* Sort by node indexes */
197	amb	249
198	amb	650	xnumber=nodesx->number;
199			nodesx->number=0;
200
201	amb	271	sortnodesx=nodesx;
202	amb	110
203	amb	948	nodesx->number=filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int ()(const void,const void))sort_by_id,(int ()(void*,index_t))deduplicate_and_index_by_id);
204	amb	252
205	amb	555	/* Close the files */
206	amb	260
207	amb	612	nodesx->fd=CloseFile(nodesx->fd);
208	amb	257	CloseFile(fd);
209	amb	252
210	amb	263	/* Print the final message */
211
212	amb	790	printf_last("Sorted Nodes: Nodes=%"Pindex_t" Duplicates=%"Pindex_t,xnumber,xnumber-nodesx->number);
213	amb	110	}
214
215
216			/*++++++++++++++++++++++++++++++++++++++
217			Sort the nodes into id order.
218
219			int sort_by_id Returns the comparison of the id fields.
220
221	amb	271	NodeX *a The first extended node.
222	amb	110
223	amb	271	NodeX *b The second extended node.
224	amb	110	++++++++++++++++++++++++++++++++++++++*/
225
226	amb	271	static int sort_by_id(NodeX a,NodeX b)
227	amb	110	{
228	amb	271	node_t a_id=a->id;
229			node_t b_id=b->id;
230	amb	252
231			if(a_id<b_id)
232			return(-1);
233			else if(a_id>b_id)
234	amb	249	return(1);
235	amb	110	else
236	amb	252	return(0);
237	amb	110	}
238
239
240	amb	271	/*++++++++++++++++++++++++++++++++++++++
241	amb	680	Create the index of identifiers and discard duplicate nodes.
242	amb	252
243	amb	680	int deduplicate_and_index_by_id Return 1 if the value is to be kept, otherwise 0.
244	amb	273
245	amb	271	NodeX *nodex The extended node.
246	amb	252
247	amb	271	index_t index The index of this node in the total.
248			++++++++++++++++++++++++++++++++++++++*/
249
250	amb	680	static int deduplicate_and_index_by_id(NodeX *nodex,index_t index)
251	amb	271	{
252	amb	273	if(index==0 \|\| sortnodesx->idata[index-1]!=nodex->id)
253			{
254			sortnodesx->idata[index]=nodex->id;
255	amb	271
256	amb	273	return(1);
257			}
258	amb	812	else
259			{
260			logerror("Node %"Pnode_t" is duplicated\n",nodex->id);
261	amb	273
262	amb	812	return(0);
263			}
264	amb	271	}
265
266
267	amb	110	/*++++++++++++++++++++++++++++++++++++++
268	amb	212	Sort the node list geographically.
269
270	amb	681	NodesX *nodesx The set of nodes to modify.
271	amb	212	++++++++++++++++++++++++++++++++++++++*/
272
273	amb	681	void SortNodeListGeographically(NodesX *nodesx)
274	amb	212	{
275	amb	281	int fd;
276	amb	949	index_t kept;
277	amb	212
278	amb	263	/* Print the start message */
279
280	amb	949	printf_first("Sorting Nodes Geographically (Deleting Pruned)");
281	amb	212
282	amb	552	/* Allocate the memory for the geographical index array */
283
284			nodesx->gdata=(index_t)malloc(nodesx->numbersizeof(index_t));
285
286			assert(nodesx->gdata); /* Check malloc() worked */
287
288	amb	555	/* Re-open the file read-only and a new file writeable */
289	amb	212
290	amb	281	nodesx->fd=ReOpenFile(nodesx->filename);
291	amb	243
292	amb	281	DeleteFile(nodesx->filename);
293	amb	212
294	amb	502	fd=OpenFileNew(nodesx->filename);
295	amb	212
296	amb	281	/* Sort geographically */
297	amb	252
298	amb	281	sortnodesx=nodesx;
299	amb	257
300	amb	949	kept=filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int ()(const void,const void))sort_by_lat_long,(int ()(void*,index_t))delete_pruned_and_index_by_lat_long);
301	amb	257
302	amb	555	/* Close the files */
303	amb	257
304	amb	612	nodesx->fd=CloseFile(nodesx->fd);
305	amb	281	CloseFile(fd);
306	amb	257
307	amb	263	/* Print the final message */
308	amb	257
309	amb	949	printf_last("Sorted Nodes Geographically: Nodes=%"Pindex_t" Deleted=%"Pindex_t,kept,nodesx->number-kept);
310			nodesx->number=kept;
311	amb	212	}
312
313
314			/*++++++++++++++++++++++++++++++++++++++
315	amb	680	Sort the nodes into latitude and longitude order (first by longitude bin
316			number, then by latitude bin number and then by exact longitude and then by
317			exact latitude).
318	amb	110
319			int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
320
321	amb	281	NodeX *a The first extended node.
322	amb	110
323	amb	281	NodeX *b The second extended node.
324	amb	110	++++++++++++++++++++++++++++++++++++++*/
325
326	amb	281	static int sort_by_lat_long(NodeX a,NodeX b)
327	amb	110	{
328	amb	949	int a_pruned=IsPrunedNodeX(a);
329			int b_pruned=IsPrunedNodeX(b);
330	amb	110
331	amb	949	if(a_pruned && b_pruned)
332			return(0);
333			else if(a_pruned)
334			return(1);
335			else if(b_pruned)
336	amb	110	return(-1);
337			else
338			{
339	amb	949	ll_bin_t a_lon=latlong_to_bin(a->longitude);
340			ll_bin_t b_lon=latlong_to_bin(b->longitude);
341	amb	110
342	amb	949	if(a_lon<b_lon)
343	amb	110	return(-1);
344	amb	949	else if(a_lon>b_lon)
345	amb	110	return(1);
346			else
347	amb	281	{
348	amb	949	ll_bin_t a_lat=latlong_to_bin(a->latitude);
349			ll_bin_t b_lat=latlong_to_bin(b->latitude);
350
351			if(a_lat<b_lat)
352	amb	281	return(-1);
353	amb	949	else if(a_lat>b_lat)
354	amb	281	return(1);
355			else
356	amb	664	{
357	amb	949	if(a->longitude<b->longitude)
358	amb	664	return(-1);
359	amb	949	else if(a->longitude>b->longitude)
360	amb	664	return(1);
361	amb	949	else
362			{
363			if(a->latitude<b->latitude)
364			return(-1);
365			else if(a->latitude>b->latitude)
366			return(1);
367			}
368
369			return(0);
370	amb	664	}
371	amb	281	}
372	amb	110	}
373			}
374
375
376			/*++++++++++++++++++++++++++++++++++++++
377	amb	949	Delete the pruned nodes and create the index between the sorted and unsorted nodes.
378	amb	281
379	amb	949	int delete_pruned_and_index_by_lat_long Return 1 if the value is to be kept, otherwise 0.
380	amb	281
381			NodeX *nodex The extended node.
382
383			index_t index The index of this node in the total.
384			++++++++++++++++++++++++++++++++++++++*/
385
386	amb	949	static int delete_pruned_and_index_by_lat_long(NodeX *nodex,index_t index)
387	amb	281	{
388	amb	949	if(IsPrunedNodeX(nodex))
389			return(0);
390
391	amb	552	/* Create the index from the previous sort to the current one */
392
393			sortnodesx->gdata[nodex->id]=index;
394
395	amb	281	return(1);
396			}
397
398
399			/*++++++++++++++++++++++++++++++++++++++
400	amb	285	Find a particular node index.
401
402			index_t IndexNodeX Returns the index of the extended node with the specified id.
403
404	amb	681	NodesX *nodesx The set of nodes to use.
405	amb	285
406			node_t id The node id to look for.
407			++++++++++++++++++++++++++++++++++++++*/
408
409	amb	681	index_t IndexNodeX(NodesX *nodesx,node_t id)
410	amb	285	{
411	amb	780	index_t start=0;
412			index_t end=nodesx->number-1;
413			index_t mid;
414	amb	285
415			/* Binary search - search key exact match only is required.
416			*
417			* # <- start \| Check mid and move start or end if it doesn't match
418			* # \|
419			* # \| Since an exact match is wanted we can set end=mid-1
420			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
421			* # \|
422			* # \| Eventually either end=start or end=start+1 and one of
423			* # <- end \| start or end is the wanted one.
424			*/
425
426			if(end<start) /* There are no nodes */
427			return(NO_NODE);
428			else if(id<nodesx->idata[start]) /* Check key is not before start */
429			return(NO_NODE);
430			else if(id>nodesx->idata[end]) /* Check key is not after end */
431			return(NO_NODE);
432			else
433			{
434			do
435			{
436			mid=(start+end)/2; /* Choose mid point */
437
438			if(nodesx->idata[mid]<id) /* Mid point is too low */
439			start=mid+1;
440			else if(nodesx->idata[mid]>id) /* Mid point is too high */
441	amb	843	end=mid?(mid-1):mid;
442	amb	285	else /* Mid point is correct */
443			return(mid);
444			}
445			while((end-start)>1);
446
447			if(nodesx->idata[start]==id) /* Start is correct */
448			return(start);
449
450			if(nodesx->idata[end]==id) /* End is correct */
451			return(end);
452			}
453
454			return(NO_NODE);
455			}
456
457
458			/*++++++++++++++++++++++++++++++++++++++
459	amb	110	Remove any nodes that are not part of a highway.
460
461	amb	681	NodesX *nodesx The set of nodes to modify.
462	amb	110
463	amb	680	SegmentsX *segmentsx The set of segments to use.
464	amb	110	++++++++++++++++++++++++++++++++++++++*/
465
466			void RemoveNonHighwayNodes(NodesX nodesx,SegmentsX segmentsx)
467			{
468	amb	263	NodeX nodex;
469	amb	780	index_t total=0,highway=0,nothighway=0;
470	amb	281	ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
471			latlong_t lat_min,lat_max,lon_min,lon_max;
472	amb	263	int fd;
473	amb	110
474	amb	263	/* Print the start message */
475
476	amb	627	printf_first("Checking Nodes: Nodes=0");
477	amb	227
478	amb	281	/* While we are here we can work out the range of data */
479
480			lat_min=radians_to_latlong( 2);
481			lat_max=radians_to_latlong(-2);
482			lon_min=radians_to_latlong( 4);
483			lon_max=radians_to_latlong(-4);
484
485	amb	555	/* Re-open the file read-only and a new file writeable */
486	amb	263
487	amb	555	nodesx->fd=ReOpenFile(nodesx->filename);
488
489	amb	263	DeleteFile(nodesx->filename);
490
491	amb	502	fd=OpenFileNew(nodesx->filename);
492	amb	263
493	amb	555	/* Modify the on-disk image */
494
495	amb	263	while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX)))
496	amb	110	{
497	amb	655	if(!IsBitSet(segmentsx->usednode,total))
498	amb	271	nothighway++;
499			else
500	amb	263	{
501	amb	280	nodex.id=highway;
502
503	amb	263	WriteFile(fd,&nodex,sizeof(NodeX));
504
505			nodesx->idata[highway]=nodesx->idata[total];
506	amb	110	highway++;
507	amb	281
508			if(nodex.latitude<lat_min)
509			lat_min=nodex.latitude;
510			if(nodex.latitude>lat_max)
511			lat_max=nodex.latitude;
512			if(nodex.longitude<lon_min)
513			lon_min=nodex.longitude;
514			if(nodex.longitude>lon_max)
515			lon_max=nodex.longitude;
516	amb	263	}
517	amb	110
518	amb	263	total++;
519
520			if(!(total%10000))
521	amb	790	printf_middle("Checking Nodes: Nodes=%"Pindex_t" Highway=%"Pindex_t" not-Highway=%"Pindex_t,total,highway,nothighway);
522	amb	110	}
523
524	amb	555	nodesx->number=highway;
525	amb	263
526	amb	555	/* Close the files */
527
528	amb	612	nodesx->fd=CloseFile(nodesx->fd);
529	amb	263	CloseFile(fd);
530
531	amb	281	/* Work out the number of bins */
532
533			lat_min_bin=latlong_to_bin(lat_min);
534			lon_min_bin=latlong_to_bin(lon_min);
535			lat_max_bin=latlong_to_bin(lat_max);
536			lon_max_bin=latlong_to_bin(lon_max);
537
538			nodesx->latzero=lat_min_bin;
539			nodesx->lonzero=lon_min_bin;
540
541			nodesx->latbins=(lat_max_bin-lat_min_bin)+1;
542			nodesx->lonbins=(lon_max_bin-lon_min_bin)+1;
543
544	amb	643	/* Free the now-unneeded index */
545
546			free(segmentsx->usednode);
547			segmentsx->usednode=NULL;
548
549	amb	263	/* Print the final message */
550
551	amb	790	printf_last("Checked Nodes: Nodes=%"Pindex_t" Highway=%"Pindex_t" not-Highway=%"Pindex_t,total,highway,nothighway);
552	amb	110	}
553
554
555			/*++++++++++++++++++++++++++++++++++++++
556	amb	643	Insert the super-node flag and the first segment indexes after geographical sorting.
557	amb	110
558	amb	681	NodesX *nodesx The set of nodes to modify.
559	amb	110
560	amb	643	SegmentsX *segmentsx The set of segments to use.
561	amb	110	++++++++++++++++++++++++++++++++++++++*/
562
563	amb	653	void UpdateNodes(NodesX nodesx,SegmentsX segmentsx)
564	amb	110	{
565	amb	214	index_t i;
566	amb	643	int fd;
567	amb	110
568	amb	275	/* Print the start message */
569
570	amb	643	printf_first("Updating Super Nodes: Nodes=0");
571	amb	227
572	amb	643	/* Re-open the file read-only and a new file writeable */
573	amb	275
574	amb	643	nodesx->fd=ReOpenFile(nodesx->filename);
575	amb	554
576	amb	643	DeleteFile(nodesx->filename);
577	amb	212
578	amb	643	fd=OpenFileNew(nodesx->filename);
579
580			/* Modify the on-disk image */
581
582	amb	110	for(i=0;i<nodesx->number;i++)
583			{
584	amb	643	NodeX nodex;
585	amb	208
586	amb	643	ReadFile(nodesx->fd,&nodex,sizeof(NodeX));
587	amb	212
588	amb	654	if(IsBitSet(nodesx->super,nodex.id))
589	amb	643	nodex.flags\|=NODE_SUPER;
590	amb	212
591	amb	674	nodex.id=segmentsx->firstnode[nodesx->gdata[nodex.id]];
592	amb	448
593	amb	643	WriteFile(fd,&nodex,sizeof(NodeX));
594
595	amb	110	if(!((i+1)%10000))
596	amb	790	printf_middle("Updating Super Nodes: Nodes=%"Pindex_t,i+1);
597	amb	110	}
598
599	amb	643	/* Close the files */
600
601			nodesx->fd=CloseFile(nodesx->fd);
602			CloseFile(fd);
603
604	amb	947	/* Free the memory */
605
606			free(nodesx->super);
607			nodesx->super=NULL;
608
609	amb	275	/* Print the final message */
610
611	amb	790	printf_last("Updated Super Nodes: Nodes=%"Pindex_t,nodesx->number);
612	amb	110	}
613
614
615			/*++++++++++++++++++++++++++++++++++++++
616	amb	680	Save the final node list database to a file.
617	amb	285
618	amb	681	NodesX *nodesx The set of nodes to save.
619	amb	285
620			const char *filename The name of the file to save.
621			++++++++++++++++++++++++++++++++++++++*/
622
623	amb	681	void SaveNodeList(NodesX nodesx,const char filename)
624	amb	285	{
625			index_t i;
626			int fd;
627	amb	500	NodesFile nodesfile={0};
628	amb	780	index_t super_number=0;
629	amb	788	ll_bin2_t latlonbin=0,maxlatlonbins;
630	amb	780	index_t *offsets;
631	amb	285
632			/* Print the start message */
633
634	amb	519	printf_first("Writing Nodes: Nodes=0");
635	amb	285
636	amb	553	/* Allocate the memory for the geographical offsets array */
637
638			offsets=(index_t)malloc((nodesx->latbinsnodesx->lonbins+1)*sizeof(index_t));
639
640			assert(offsets); /* Check malloc() worked */
641
642			latlonbin=0;
643
644	amb	556	/* Re-open the file */
645	amb	285
646	amb	555	nodesx->fd=ReOpenFile(nodesx->filename);
647	amb	285
648	amb	461	/* Write out the nodes data */
649	amb	285
650	amb	502	fd=OpenFileNew(filename);
651	amb	285
652	amb	553	SeekFile(fd,sizeof(NodesFile)+(nodesx->latbinsnodesx->lonbins+1)sizeof(index_t));
653	amb	285
654	amb	461	for(i=0;i<nodesx->number;i++)
655	amb	285	{
656	amb	556	NodeX nodex;
657	amb	944	Node node={0};
658	amb	553	ll_bin_t latbin,lonbin;
659	amb	780	ll_bin2_t llbin;
660	amb	285
661	amb	556	ReadFile(nodesx->fd,&nodex,sizeof(NodeX));
662
663	amb	553	/* Create the Node */
664
665	amb	556	node.latoffset=latlong_to_off(nodex.latitude);
666			node.lonoffset=latlong_to_off(nodex.longitude);
667			node.firstseg=nodex.id;
668			node.allow=nodex.allow;
669			node.flags=nodex.flags;
670	amb	552
671			if(node.flags&NODE_SUPER)
672	amb	461	super_number++;
673
674	amb	553	/* Work out the offsets */
675
676	amb	556	latbin=latlong_to_bin(nodex.latitude )-nodesx->latzero;
677			lonbin=latlong_to_bin(nodex.longitude)-nodesx->lonzero;
678	amb	553	llbin=lonbin*nodesx->latbins+latbin;
679
680			for(;latlonbin<=llbin;latlonbin++)
681			offsets[latlonbin]=i;
682
683			/* Write the data */
684
685	amb	552	WriteFile(fd,&node,sizeof(Node));
686	amb	285
687			if(!((i+1)%10000))
688	amb	790	printf_middle("Writing Nodes: Nodes=%"Pindex_t,i+1);
689	amb	285	}
690
691	amb	556	/* Close the file */
692
693	amb	612	nodesx->fd=CloseFile(nodesx->fd);
694	amb	556
695	amb	553	/* Finish off the offset indexing and write them out */
696
697	amb	788	maxlatlonbins=nodesx->latbins*nodesx->lonbins;
698
699			for(;latlonbin<=maxlatlonbins;latlonbin++)
700	amb	553	offsets[latlonbin]=nodesx->number;
701
702			SeekFile(fd,sizeof(NodesFile));
703			WriteFile(fd,offsets,(nodesx->latbinsnodesx->lonbins+1)sizeof(index_t));
704
705	amb	795	free(offsets);
706
707	amb	461	/* Write out the header structure */
708
709			nodesfile.number=nodesx->number;
710			nodesfile.snumber=super_number;
711
712			nodesfile.latbins=nodesx->latbins;
713			nodesfile.lonbins=nodesx->lonbins;
714
715			nodesfile.latzero=nodesx->latzero;
716			nodesfile.lonzero=nodesx->lonzero;
717
718			SeekFile(fd,0);
719			WriteFile(fd,&nodesfile,sizeof(NodesFile));
720
721	amb	285	CloseFile(fd);
722
723			/* Print the final message */
724
725	amb	790	printf_last("Wrote Nodes: Nodes=%"Pindex_t,nodesx->number);
726	amb	285	}