trunk/src/nodesx.c

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

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2011 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 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;

 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;

    sortnodesx->number++;

    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;

 /* Print the start message */

 printf_first("Sorting Nodes Geographically");

 /* 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;

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

 /* Close the files */

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

 /* Print the final message */

 printf_last("Sorted Nodes Geographically");
}


/*++++++++++++++++++++++++++++++++++++++
  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)
{
 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);
      }
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Create the index between the sorted and unsorted nodes.

  int 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 index_by_lat_long(NodeX *nodex,index_t index)
{
 /* 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;

 /* Allocate and set the super-node markers */

 nodesx->super=(uint8_t*)malloc((1+nodesx->number/8)*sizeof(uint8_t));

 assert(nodesx->super); /* Check calloc() worked */

 memset(nodesx->super,~0,(1+nodesx->number/8));

 /* 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);

 /* 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	612	This file Copyright 2008-2011 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			static int 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	680	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	sortnodesx->number++;
257
258			return(1);
259			}
260	amb	812	else
261			{
262			logerror("Node %"Pnode_t" is duplicated\n",nodex->id);
263	amb	273
264	amb	812	return(0);
265			}
266	amb	271	}
267
268
269	amb	110	/*++++++++++++++++++++++++++++++++++++++
270	amb	212	Sort the node list geographically.
271
272	amb	681	NodesX *nodesx The set of nodes to modify.
273	amb	212	++++++++++++++++++++++++++++++++++++++*/
274
275	amb	681	void SortNodeListGeographically(NodesX *nodesx)
276	amb	212	{
277	amb	281	int fd;
278	amb	212
279	amb	263	/* Print the start message */
280
281	amb	519	printf_first("Sorting Nodes Geographically");
282	amb	212
283	amb	552	/* Allocate the memory for the geographical index array */
284
285			nodesx->gdata=(index_t)malloc(nodesx->numbersizeof(index_t));
286
287			assert(nodesx->gdata); /* Check malloc() worked */
288
289	amb	555	/* Re-open the file read-only and a new file writeable */
290	amb	212
291	amb	281	nodesx->fd=ReOpenFile(nodesx->filename);
292	amb	243
293	amb	281	DeleteFile(nodesx->filename);
294	amb	212
295	amb	502	fd=OpenFileNew(nodesx->filename);
296	amb	212
297	amb	281	/* Sort geographically */
298	amb	252
299	amb	281	sortnodesx=nodesx;
300	amb	257
301	amb	311	filesort_fixed(nodesx->fd,fd,sizeof(NodeX),(int ()(const void,const void))sort_by_lat_long,(int ()(void*,index_t))index_by_lat_long);
302	amb	257
303	amb	555	/* Close the files */
304	amb	257
305	amb	612	nodesx->fd=CloseFile(nodesx->fd);
306	amb	281	CloseFile(fd);
307	amb	257
308	amb	263	/* Print the final message */
309	amb	257
310	amb	519	printf_last("Sorted Nodes Geographically");
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	281	ll_bin_t a_lon=latlong_to_bin(a->longitude);
329			ll_bin_t b_lon=latlong_to_bin(b->longitude);
330	amb	110
331			if(a_lon<b_lon)
332			return(-1);
333			else if(a_lon>b_lon)
334			return(1);
335			else
336			{
337	amb	281	ll_bin_t a_lat=latlong_to_bin(a->latitude);
338			ll_bin_t b_lat=latlong_to_bin(b->latitude);
339	amb	110
340			if(a_lat<b_lat)
341			return(-1);
342			else if(a_lat>b_lat)
343			return(1);
344			else
345	amb	281	{
346	amb	664	if(a->longitude<b->longitude)
347	amb	281	return(-1);
348	amb	664	else if(a->longitude>b->longitude)
349	amb	281	return(1);
350			else
351	amb	664	{
352			if(a->latitude<b->latitude)
353			return(-1);
354			else if(a->latitude>b->latitude)
355			return(1);
356			}
357
358			return(0);
359	amb	281	}
360	amb	110	}
361			}
362
363
364			/*++++++++++++++++++++++++++++++++++++++
365	amb	680	Create the index between the sorted and unsorted nodes.
366	amb	281
367	amb	680	int index_by_lat_long Return 1 if the value is to be kept, otherwise 0.
368	amb	281
369			NodeX *nodex The extended node.
370
371			index_t index The index of this node in the total.
372			++++++++++++++++++++++++++++++++++++++*/
373
374			static int index_by_lat_long(NodeX *nodex,index_t index)
375			{
376	amb	552	/* Create the index from the previous sort to the current one */
377
378			sortnodesx->gdata[nodex->id]=index;
379
380	amb	281	return(1);
381			}
382
383
384			/*++++++++++++++++++++++++++++++++++++++
385	amb	285	Find a particular node index.
386
387			index_t IndexNodeX Returns the index of the extended node with the specified id.
388
389	amb	681	NodesX *nodesx The set of nodes to use.
390	amb	285
391			node_t id The node id to look for.
392			++++++++++++++++++++++++++++++++++++++*/
393
394	amb	681	index_t IndexNodeX(NodesX *nodesx,node_t id)
395	amb	285	{
396	amb	780	index_t start=0;
397			index_t end=nodesx->number-1;
398			index_t mid;
399	amb	285
400			/* Binary search - search key exact match only is required.
401			*
402			* # <- start \| Check mid and move start or end if it doesn't match
403			* # \|
404			* # \| Since an exact match is wanted we can set end=mid-1
405			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
406			* # \|
407			* # \| Eventually either end=start or end=start+1 and one of
408			* # <- end \| start or end is the wanted one.
409			*/
410
411			if(end<start) /* There are no nodes */
412			return(NO_NODE);
413			else if(id<nodesx->idata[start]) /* Check key is not before start */
414			return(NO_NODE);
415			else if(id>nodesx->idata[end]) /* Check key is not after end */
416			return(NO_NODE);
417			else
418			{
419			do
420			{
421			mid=(start+end)/2; /* Choose mid point */
422
423			if(nodesx->idata[mid]<id) /* Mid point is too low */
424			start=mid+1;
425			else if(nodesx->idata[mid]>id) /* Mid point is too high */
426	amb	843	end=mid?(mid-1):mid;
427	amb	285	else /* Mid point is correct */
428			return(mid);
429			}
430			while((end-start)>1);
431
432			if(nodesx->idata[start]==id) /* Start is correct */
433			return(start);
434
435			if(nodesx->idata[end]==id) /* End is correct */
436			return(end);
437			}
438
439			return(NO_NODE);
440			}
441
442
443			/*++++++++++++++++++++++++++++++++++++++
444	amb	110	Remove any nodes that are not part of a highway.
445
446	amb	681	NodesX *nodesx The set of nodes to modify.
447	amb	110
448	amb	680	SegmentsX *segmentsx The set of segments to use.
449	amb	110	++++++++++++++++++++++++++++++++++++++*/
450
451			void RemoveNonHighwayNodes(NodesX nodesx,SegmentsX segmentsx)
452			{
453	amb	263	NodeX nodex;
454	amb	780	index_t total=0,highway=0,nothighway=0;
455	amb	281	ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
456			latlong_t lat_min,lat_max,lon_min,lon_max;
457	amb	263	int fd;
458	amb	110
459	amb	263	/* Print the start message */
460
461	amb	627	printf_first("Checking Nodes: Nodes=0");
462	amb	227
463	amb	281	/* While we are here we can work out the range of data */
464
465			lat_min=radians_to_latlong( 2);
466			lat_max=radians_to_latlong(-2);
467			lon_min=radians_to_latlong( 4);
468			lon_max=radians_to_latlong(-4);
469
470	amb	555	/* Re-open the file read-only and a new file writeable */
471	amb	263
472	amb	555	nodesx->fd=ReOpenFile(nodesx->filename);
473
474	amb	263	DeleteFile(nodesx->filename);
475
476	amb	502	fd=OpenFileNew(nodesx->filename);
477	amb	263
478	amb	555	/* Modify the on-disk image */
479
480	amb	263	while(!ReadFile(nodesx->fd,&nodex,sizeof(NodeX)))
481	amb	110	{
482	amb	655	if(!IsBitSet(segmentsx->usednode,total))
483	amb	271	nothighway++;
484			else
485	amb	263	{
486	amb	280	nodex.id=highway;
487
488	amb	263	WriteFile(fd,&nodex,sizeof(NodeX));
489
490			nodesx->idata[highway]=nodesx->idata[total];
491	amb	110	highway++;
492	amb	281
493			if(nodex.latitude<lat_min)
494			lat_min=nodex.latitude;
495			if(nodex.latitude>lat_max)
496			lat_max=nodex.latitude;
497			if(nodex.longitude<lon_min)
498			lon_min=nodex.longitude;
499			if(nodex.longitude>lon_max)
500			lon_max=nodex.longitude;
501	amb	263	}
502	amb	110
503	amb	263	total++;
504
505			if(!(total%10000))
506	amb	790	printf_middle("Checking Nodes: Nodes=%"Pindex_t" Highway=%"Pindex_t" not-Highway=%"Pindex_t,total,highway,nothighway);
507	amb	110	}
508
509	amb	555	nodesx->number=highway;
510	amb	263
511	amb	555	/* Close the files */
512
513	amb	612	nodesx->fd=CloseFile(nodesx->fd);
514	amb	263	CloseFile(fd);
515
516	amb	281	/* Work out the number of bins */
517
518			lat_min_bin=latlong_to_bin(lat_min);
519			lon_min_bin=latlong_to_bin(lon_min);
520			lat_max_bin=latlong_to_bin(lat_max);
521			lon_max_bin=latlong_to_bin(lon_max);
522
523			nodesx->latzero=lat_min_bin;
524			nodesx->lonzero=lon_min_bin;
525
526			nodesx->latbins=(lat_max_bin-lat_min_bin)+1;
527			nodesx->lonbins=(lon_max_bin-lon_min_bin)+1;
528
529	amb	643	/* Free the now-unneeded index */
530
531			free(segmentsx->usednode);
532			segmentsx->usednode=NULL;
533
534	amb	653	/* Allocate and set the super-node markers */
535	amb	263
536	amb	654	nodesx->super=(uint8_t)malloc((1+nodesx->number/8)sizeof(uint8_t));
537	amb	263
538			assert(nodesx->super); /* Check calloc() worked */
539
540	amb	654	memset(nodesx->super,~0,(1+nodesx->number/8));
541	amb	653
542	amb	263	/* Print the final message */
543
544	amb	790	printf_last("Checked Nodes: Nodes=%"Pindex_t" Highway=%"Pindex_t" not-Highway=%"Pindex_t,total,highway,nothighway);
545	amb	110	}
546
547
548			/*++++++++++++++++++++++++++++++++++++++
549	amb	643	Insert the super-node flag and the first segment indexes after geographical sorting.
550	amb	110
551	amb	681	NodesX *nodesx The set of nodes to modify.
552	amb	110
553	amb	643	SegmentsX *segmentsx The set of segments to use.
554	amb	110	++++++++++++++++++++++++++++++++++++++*/
555
556	amb	653	void UpdateNodes(NodesX nodesx,SegmentsX segmentsx)
557	amb	110	{
558	amb	214	index_t i;
559	amb	643	int fd;
560	amb	110
561	amb	275	/* Print the start message */
562
563	amb	643	printf_first("Updating Super Nodes: Nodes=0");
564	amb	227
565	amb	643	/* Re-open the file read-only and a new file writeable */
566	amb	275
567	amb	643	nodesx->fd=ReOpenFile(nodesx->filename);
568	amb	554
569	amb	643	DeleteFile(nodesx->filename);
570	amb	212
571	amb	643	fd=OpenFileNew(nodesx->filename);
572
573			/* Modify the on-disk image */
574
575	amb	110	for(i=0;i<nodesx->number;i++)
576			{
577	amb	643	NodeX nodex;
578	amb	208
579	amb	643	ReadFile(nodesx->fd,&nodex,sizeof(NodeX));
580	amb	212
581	amb	654	if(IsBitSet(nodesx->super,nodex.id))
582	amb	643	nodex.flags\|=NODE_SUPER;
583	amb	212
584	amb	674	nodex.id=segmentsx->firstnode[nodesx->gdata[nodex.id]];
585	amb	448
586	amb	643	WriteFile(fd,&nodex,sizeof(NodeX));
587
588	amb	110	if(!((i+1)%10000))
589	amb	790	printf_middle("Updating Super Nodes: Nodes=%"Pindex_t,i+1);
590	amb	110	}
591
592	amb	643	/* Close the files */
593
594			nodesx->fd=CloseFile(nodesx->fd);
595			CloseFile(fd);
596
597	amb	275	/* Print the final message */
598
599	amb	790	printf_last("Updated Super Nodes: Nodes=%"Pindex_t,nodesx->number);
600	amb	110	}
601
602
603			/*++++++++++++++++++++++++++++++++++++++
604	amb	680	Save the final node list database to a file.
605	amb	285
606	amb	681	NodesX *nodesx The set of nodes to save.
607	amb	285
608			const char *filename The name of the file to save.
609			++++++++++++++++++++++++++++++++++++++*/
610
611	amb	681	void SaveNodeList(NodesX nodesx,const char filename)
612	amb	285	{
613			index_t i;
614			int fd;
615	amb	500	NodesFile nodesfile={0};
616	amb	780	index_t super_number=0;
617	amb	788	ll_bin2_t latlonbin=0,maxlatlonbins;
618	amb	780	index_t *offsets;
619	amb	285
620			/* Print the start message */
621
622	amb	519	printf_first("Writing Nodes: Nodes=0");
623	amb	285
624	amb	553	/* Allocate the memory for the geographical offsets array */
625
626			offsets=(index_t)malloc((nodesx->latbinsnodesx->lonbins+1)*sizeof(index_t));
627
628			assert(offsets); /* Check malloc() worked */
629
630			latlonbin=0;
631
632	amb	556	/* Re-open the file */
633	amb	285
634	amb	555	nodesx->fd=ReOpenFile(nodesx->filename);
635	amb	285
636	amb	461	/* Write out the nodes data */
637	amb	285
638	amb	502	fd=OpenFileNew(filename);
639	amb	285
640	amb	553	SeekFile(fd,sizeof(NodesFile)+(nodesx->latbinsnodesx->lonbins+1)sizeof(index_t));
641	amb	285
642	amb	461	for(i=0;i<nodesx->number;i++)
643	amb	285	{
644	amb	556	NodeX nodex;
645	amb	944	Node node={0};
646	amb	553	ll_bin_t latbin,lonbin;
647	amb	780	ll_bin2_t llbin;
648	amb	285
649	amb	556	ReadFile(nodesx->fd,&nodex,sizeof(NodeX));
650
651	amb	553	/* Create the Node */
652
653	amb	556	node.latoffset=latlong_to_off(nodex.latitude);
654			node.lonoffset=latlong_to_off(nodex.longitude);
655			node.firstseg=nodex.id;
656			node.allow=nodex.allow;
657			node.flags=nodex.flags;
658	amb	552
659			if(node.flags&NODE_SUPER)
660	amb	461	super_number++;
661
662	amb	553	/* Work out the offsets */
663
664	amb	556	latbin=latlong_to_bin(nodex.latitude )-nodesx->latzero;
665			lonbin=latlong_to_bin(nodex.longitude)-nodesx->lonzero;
666	amb	553	llbin=lonbin*nodesx->latbins+latbin;
667
668			for(;latlonbin<=llbin;latlonbin++)
669			offsets[latlonbin]=i;
670
671			/* Write the data */
672
673	amb	552	WriteFile(fd,&node,sizeof(Node));
674	amb	285
675			if(!((i+1)%10000))
676	amb	790	printf_middle("Writing Nodes: Nodes=%"Pindex_t,i+1);
677	amb	285	}
678
679	amb	556	/* Close the file */
680
681	amb	612	nodesx->fd=CloseFile(nodesx->fd);
682	amb	556
683	amb	553	/* Finish off the offset indexing and write them out */
684
685	amb	788	maxlatlonbins=nodesx->latbins*nodesx->lonbins;
686
687			for(;latlonbin<=maxlatlonbins;latlonbin++)
688	amb	553	offsets[latlonbin]=nodesx->number;
689
690			SeekFile(fd,sizeof(NodesFile));
691			WriteFile(fd,offsets,(nodesx->latbinsnodesx->lonbins+1)sizeof(index_t));
692
693	amb	795	free(offsets);
694
695	amb	461	/* Write out the header structure */
696
697			nodesfile.number=nodesx->number;
698			nodesfile.snumber=super_number;
699
700			nodesfile.latbins=nodesx->latbins;
701			nodesfile.lonbins=nodesx->lonbins;
702
703			nodesfile.latzero=nodesx->latzero;
704			nodesfile.lonzero=nodesx->lonzero;
705
706			SeekFile(fd,0);
707			WriteFile(fd,&nodesfile,sizeof(NodesFile));
708
709	amb	285	CloseFile(fd);
710
711			/* Print the final message */
712
713	amb	790	printf_last("Wrote Nodes: Nodes=%"Pindex_t,nodesx->number);
714	amb	285	}