trunk/src/waysx.c

/***************************************
 Extended Way 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 "ways.h"

#include "waysx.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 WaysX *sortwaysx;

/* Functions */

static int sort_by_id(WayX *a,WayX *b);
static int sort_by_name_and_id(WayX *a,WayX *b);
static int sort_by_name_and_prop_and_id(WayX *a,WayX *b);

static int deduplicate_and_index_by_id(WayX *wayx,index_t index);


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

  WaysX *NewWayList Returns the way list.

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

WaysX *NewWayList(int append)
{
 WaysX *waysx;

 waysx=(WaysX*)calloc(1,sizeof(WaysX));

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

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

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

 if(append)
   {
    off_t size,position=0;

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

    size=SizeFile(waysx->filename);

    while(position<size)
      {
       FILESORT_VARINT waysize;

       SeekFile(waysx->fd,position);
       ReadFile(waysx->fd,&waysize,FILESORT_VARSIZE);

       waysx->xnumber++;
       position+=waysize+FILESORT_VARSIZE;
      }

    SeekFile(waysx->fd,size);
   }
 else
    waysx->fd=OpenFileNew(waysx->filename);

 waysx->nfilename=(char*)malloc(strlen(option_tmpdirname)+32);
 sprintf(waysx->nfilename,"%s/waynames.%p.tmp",option_tmpdirname,waysx);

 return(waysx);
}


/*++++++++++++++++++++++++++++++++++++++
  Free a way list.

  WaysX *waysx The list to be freed.

  int keep Set to 1 if the file is to be kept.
  ++++++++++++++++++++++++++++++++++++++*/

void FreeWayList(WaysX *waysx,int keep)
{
 if(!keep)
    DeleteFile(waysx->filename);

 free(waysx->filename);

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

 DeleteFile(waysx->nfilename);

 free(waysx->nfilename);

 free(waysx);
}


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

  WaysX* waysx The set of ways to process.

  way_t id The ID of the way.

  Way *way The way data itself.

  const char *name The name or reference of the way.
  ++++++++++++++++++++++++++++++++++++++*/

void AppendWay(WaysX* waysx,way_t id,Way *way,const char *name)
{
 WayX wayx;
 FILESORT_VARINT size;

 wayx.id=id;
 wayx.prop=0;
 wayx.way=*way;

 size=sizeof(WayX)+strlen(name)+1;

 WriteFile(waysx->fd,&size,FILESORT_VARSIZE);
 WriteFile(waysx->fd,&wayx,sizeof(WayX));
 WriteFile(waysx->fd,name,strlen(name)+1);

 waysx->xnumber++;

 assert(!(waysx->xnumber==0)); /* Zero marks the high-water mark for ways. */
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the list of ways.

  WaysX* waysx The set of ways to process.
  ++++++++++++++++++++++++++++++++++++++*/

void SortWayList(WaysX* waysx)
{
 index_t i;
 int fd;
 char *names[2]={NULL,NULL};
 int namelen[2]={0,0};
 int nnames=0;
 uint32_t lastlength=0;

 /* Print the start message */

 printf_first("Sorting Ways by Name");

 /* Close the file (finished appending) */

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

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

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

 DeleteFile(waysx->filename);

 fd=OpenFileNew(waysx->filename);

 /* Sort the ways to allow separating the names */

 filesort_vary(waysx->fd,fd,(int (*)(const void*,const void*))sort_by_name_and_id,NULL);

 /* Close the files */

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

 /* Print the final message */

 printf_last("Sorted Ways by Name: Ways=%d",waysx->xnumber);


 /* Print the start message */

 printf_first("Separating Way Names: Ways=0 Names=0");

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

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

 DeleteFile(waysx->filename);

 fd=OpenFileNew(waysx->filename);

 waysx->nfd=OpenFileNew(waysx->nfilename);

 /* Copy from the single file into two files */

 for(i=0;i<waysx->xnumber;i++)
   {
    WayX wayx;
    FILESORT_VARINT size;

    ReadFile(waysx->fd,&size,FILESORT_VARSIZE);

    if(namelen[nnames%2]<size)
       names[nnames%2]=(char*)realloc((void*)names[nnames%2],namelen[nnames%2]=size);

    ReadFile(waysx->fd,&wayx,sizeof(WayX));
    ReadFile(waysx->fd,names[nnames%2],size-sizeof(WayX));

    if(nnames==0 || strcmp(names[0],names[1]))
      {
       WriteFile(waysx->nfd,names[nnames%2],size-sizeof(WayX));

       lastlength=waysx->nlength;
       waysx->nlength+=size-sizeof(WayX);

       nnames++;
      }

    wayx.way.name=lastlength;

    WriteFile(fd,&wayx,sizeof(WayX));

    if(!((i+1)%10000))
       printf_middle("Separating Way Names: Ways=%d Names=%d",i+1,nnames);
   }

 if(names[0]) free(names[0]);
 if(names[1]) free(names[1]);

 /* Close the files */

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

 waysx->nfd=CloseFile(waysx->nfd);

 /* Print the final message */

 printf_last("Separated Way Names: Ways=%d Names=%d ",waysx->xnumber,nnames);


 /* Print the start message */

 printf_first("Sorting Ways");

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

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

 DeleteFile(waysx->filename);

 fd=OpenFileNew(waysx->filename);

 /* Allocate the array of indexes */

 waysx->idata=(way_t*)malloc(waysx->xnumber*sizeof(way_t));

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

 /* Sort the ways by index and index them */

 waysx->number=0;

 sortwaysx=waysx;

 filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(const void*,const void*))sort_by_id,(int (*)(void*,index_t))deduplicate_and_index_by_id);

 /* Close the files */

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

 /* Print the final message */

 printf_last("Sorted Ways: Ways=%d Duplicates=%d",waysx->number,waysx->xnumber-waysx->number);
}


/*++++++++++++++++++++++++++++++++++++++
  Compact the list of ways.

  WaysX* waysx The set of ways to process.
  ++++++++++++++++++++++++++++++++++++++*/

void CompactWayList(WaysX* waysx)
{
 index_t i;
 int fd;
 Way lastway;

 /* Print the start message */

 printf_first("Sorting Ways by Properties");

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

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

 DeleteFile(waysx->filename);

 fd=OpenFileNew(waysx->filename);

 /* Sort the ways to allow compacting according to he properties */

 filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(const void*,const void*))sort_by_name_and_prop_and_id,NULL);

 /* Close the files */

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

 /* Print the final message */

 printf_last("Sorted Ways by Properties: Ways=%d",waysx->number);


 /* Print the start message */

 printf_first("Compacting Ways: Ways=0 Properties=0");

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

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

 DeleteFile(waysx->filename);

 fd=OpenFileNew(waysx->filename);

 /* Update the way as we go using the sorted index */

 waysx->cnumber=0;

 for(i=0;i<waysx->number;i++)
   {
    WayX wayx;

    ReadFile(waysx->fd,&wayx,sizeof(WayX));

    if(waysx->cnumber==0 || wayx.way.name!=lastway.name || WaysCompare(&lastway,&wayx.way))
      {
       lastway=wayx.way;

       waysx->cnumber++;
      }

    wayx.prop=waysx->cnumber-1;

    WriteFile(fd,&wayx,sizeof(WayX));

    if(!((i+1)%10000))
       printf_middle("Compacting Ways: Ways=%d Properties=%d",i+1,waysx->cnumber);
   }

 /* Close the files */

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

 /* Print the final message */

 printf_last("Compacted Ways: Ways=%d Properties=%d ",waysx->number,waysx->cnumber);


 /* Print the start message */

 printf_first("Sorting Ways");

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

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

 DeleteFile(waysx->filename);

 fd=OpenFileNew(waysx->filename);

 /* Sort the ways by index */

 filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(const void*,const void*))sort_by_id,NULL);

 /* Close the files */

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

 /* Print the final message */

 printf_last("Sorted Ways: Ways=%d",waysx->number);
}


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

  int sort_by_id Returns the comparison of the id fields.

  WayX *a The first extended way.

  WayX *b The second extended way.
  ++++++++++++++++++++++++++++++++++++++*/

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

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


/*++++++++++++++++++++++++++++++++++++++
  Sort the ways into name and id order.

  int sort_by_name_and_id Returns the comparison of the name and id fields.

  WayX *a The first extended Way.

  WayX *b The second extended Way.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_name_and_id(WayX *a,WayX *b)
{
 int compare;
 char *a_name=(char*)a+sizeof(WayX);
 char *b_name=(char*)b+sizeof(WayX);

 compare=strcmp(a_name,b_name);

 if(compare)
    return(compare);

 return(sort_by_id(a,b));
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the ways into name, properties and id order.

  int sort_by_name_and_prop_and_id Returns the comparison of the name, properties and id fields.

  WayX *a The first extended Way.

  WayX *b The second extended Way.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_name_and_prop_and_id(WayX *a,WayX *b)
{
 int compare;
 index_t a_name=a->way.name;
 index_t b_name=b->way.name;

 if(a_name<b_name)
    return(-1);
 else if(a_name>b_name)
    return(1);

 compare=WaysCompare(&a->way,&b->way);

 if(compare)
    return(compare);

 return(sort_by_id(a,b));
}


/*++++++++++++++++++++++++++++++++++++++
  Deduplicate the extended ways using the id after sorting and create the index.

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

  WayX *wayx The extended way.

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

static int deduplicate_and_index_by_id(WayX *wayx,index_t index)
{
 static way_t previd;

 if(index==0 || wayx->id!=previd)
   {
    previd=wayx->id;

    sortwaysx->number++;

    sortwaysx->idata[index]=wayx->id;

    return(1);
   }

 return(0);
}


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

  index_t IndexWayX Returns the index of the extended way with the specified id.

  WaysX* waysx The set of ways to process.

  way_t id The way id to look for.
  ++++++++++++++++++++++++++++++++++++++*/

index_t IndexWayX(WaysX* waysx,way_t id)
{
 int start=0;
 int end=waysx->number-1;
 int 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 ways */
    return(NO_WAY);
 else if(id<waysx->idata[start]) /* Check key is not before start */
    return(NO_WAY);
 else if(id>waysx->idata[end])   /* Check key is not after end */
    return(NO_WAY);
 else
   {
    do
      {
       mid=(start+end)/2;            /* Choose mid point */

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

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

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

 return(NO_WAY);
}


/*++++++++++++++++++++++++++++++++++++++
  Save the way list to a file.

  WaysX* waysx The set of ways to save.

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

void SaveWayList(WaysX* waysx,const char *filename)
{
 index_t i;
 int fd;
 int position=0;
 WaysFile waysfile={0};
 highways_t   highways=0;
 transports_t allow=0;
 properties_t props=0;

 /* Print the start message */

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

 /* Map into memory /  open the file */

#if !SLIM
 waysx->xdata=MapFile(waysx->filename);
#else
 waysx->fd=ReOpenFile(waysx->filename);
#endif

 /* Write out the ways data */

 fd=OpenFileNew(filename);

 SeekFile(fd,sizeof(WaysFile));

 for(i=0;i<waysx->number;i++)
   {
    WayX *wayx=LookupWayX(waysx,i,1);

    highways|=HIGHWAYS(wayx->way.type);
    allow   |=wayx->way.allow;
    props   |=wayx->way.props;

    SeekFile(fd,sizeof(WaysFile)+(off_t)wayx->prop*sizeof(Way));
    WriteFile(fd,&wayx->way,sizeof(Way));

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

 /* Unmap from memory / close the file */

#if !SLIM
 waysx->xdata=UnmapFile(waysx->filename);
#else
 waysx->fd=CloseFile(waysx->fd);
#endif

 /* Write out the ways names */

 SeekFile(fd,sizeof(WaysFile)+(off_t)waysx->cnumber*sizeof(Way));

 waysx->nfd=ReOpenFile(waysx->nfilename);

 while(position<waysx->nlength)
   {
    int len=1024;
    char temp[1024];

    if((waysx->nlength-position)<1024)
       len=waysx->nlength-position;

    ReadFile(waysx->nfd,temp,len);
    WriteFile(fd,temp,len);

    position+=len;
   }

 /* Close the file */

 waysx->nfd=CloseFile(waysx->nfd);

 /* Write out the header structure */

 waysfile.number =waysx->cnumber;
 waysfile.onumber=waysx->number;

 waysfile.highways=highways;
 waysfile.allow   =allow;
 waysfile.props   =props;

 SeekFile(fd,0);
 WriteFile(fd,&waysfile,sizeof(WaysFile));

 CloseFile(fd);

 /* Print the final message */

 printf_last("Wrote Ways: Ways=%d",waysx->number);
}
1	amb	110	/***************************************
2			Extended Way 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	amb	449	#include <stdio.h>
26	amb	110	#include <string.h>
27	amb	326	#include <sys/stat.h>
28	amb	110
29	amb	228	#include "ways.h"
30	amb	110
31	amb	449	#include "waysx.h"
32	amb	110
33	amb	449	#include "files.h"
34	amb	519	#include "logging.h"
35	amb	532	#include "sorting.h"
36	amb	449
37
38	amb	262	/* Variables */
39	amb	110
40	amb	289	/+ The command line '--tmpdir' option or its default value. +/
41	amb	284	extern char *option_tmpdirname;
42	amb	110
43	amb	284	/+ A temporary file-local variable for use by the sort functions. +/
44			static WaysX *sortwaysx;
45
46	amb	110	/* Functions */
47
48	amb	499	static int sort_by_id(WayX a,WayX b);
49			static int sort_by_name_and_id(WayX a,WayX b);
50	amb	310	static int sort_by_name_and_prop_and_id(WayX a,WayX b);
51
52	amb	499	static int deduplicate_and_index_by_id(WayX *wayx,index_t index);
53	amb	272
54	amb	110
55			/*++++++++++++++++++++++++++++++++++++++
56	amb	326	Allocate a new way list (create a new file or open an existing one).
57	amb	110
58			WaysX *NewWayList Returns the way list.
59	amb	326
60			int append Set to 1 if the file is to be opened for appending (now or later).
61	amb	110	++++++++++++++++++++++++++++++++++++++*/
62
63	amb	326	WaysX *NewWayList(int append)
64	amb	110	{
65			WaysX *waysx;
66
67	amb	213	waysx=(WaysX*)calloc(1,sizeof(WaysX));
68	amb	110
69	amb	243	assert(waysx); /* Check calloc() worked */
70
71	amb	284	waysx->filename=(char*)malloc(strlen(option_tmpdirname)+32);
72	amb	216
73	amb	326	if(append)
74	amb	447	sprintf(waysx->filename,"%s/waysx.input.tmp",option_tmpdirname);
75	amb	326	else
76	amb	447	sprintf(waysx->filename,"%s/waysx.%p.tmp",option_tmpdirname,waysx);
77	amb	262
78	amb	326	if(append)
79			{
80	amb	331	off_t size,position=0;
81	amb	326
82	amb	502	waysx->fd=OpenFileAppend(waysx->filename);
83	amb	326
84	amb	331	size=SizeFile(waysx->filename);
85	amb	326
86	amb	331	while(position<size)
87	amb	326	{
88	amb	331	FILESORT_VARINT waysize;
89	amb	326
90			SeekFile(waysx->fd,position);
91	amb	331	ReadFile(waysx->fd,&waysize,FILESORT_VARSIZE);
92	amb	326
93			waysx->xnumber++;
94	amb	331	position+=waysize+FILESORT_VARSIZE;
95	amb	326	}
96
97	amb	331	SeekFile(waysx->fd,size);
98	amb	326	}
99			else
100	amb	502	waysx->fd=OpenFileNew(waysx->filename);
101	amb	326
102	amb	284	waysx->nfilename=(char*)malloc(strlen(option_tmpdirname)+32);
103			sprintf(waysx->nfilename,"%s/waynames.%p.tmp",option_tmpdirname,waysx);
104	amb	262
105	amb	110	return(waysx);
106			}
107
108
109			/*++++++++++++++++++++++++++++++++++++++
110	amb	226	Free a way list.
111
112			WaysX *waysx The list to be freed.
113	amb	326
114			int keep Set to 1 if the file is to be kept.
115	amb	226	++++++++++++++++++++++++++++++++++++++*/
116
117	amb	326	void FreeWayList(WaysX *waysx,int keep)
118	amb	226	{
119	amb	326	if(!keep)
120			DeleteFile(waysx->filename);
121
122	amb	283	free(waysx->filename);
123	amb	262
124	amb	226	if(waysx->idata)
125			free(waysx->idata);
126
127	amb	262	DeleteFile(waysx->nfilename);
128	amb	326
129	amb	283	free(waysx->nfilename);
130	amb	226
131			free(waysx);
132			}
133
134
135			/*++++++++++++++++++++++++++++++++++++++
136	amb	493	Append a single way to an unsorted way list.
137	amb	203
138	amb	262	WaysX* waysx The set of ways to process.
139	amb	110
140	amb	262	way_t id The ID of the way.
141	amb	110
142	amb	262	Way *way The way data itself.
143	amb	110
144	amb	262	const char *name The name or reference of the way.
145			++++++++++++++++++++++++++++++++++++++*/
146	amb	110
147	amb	262	void AppendWay(WaysX* waysx,way_t id,Way way,const char name)
148			{
149			WayX wayx;
150	amb	311	FILESORT_VARINT size;
151	amb	110
152	amb	262	wayx.id=id;
153	amb	310	wayx.prop=0;
154	amb	262	wayx.way=*way;
155
156	amb	310	size=sizeof(WayX)+strlen(name)+1;
157
158	amb	311	WriteFile(waysx->fd,&size,FILESORT_VARSIZE);
159	amb	262	WriteFile(waysx->fd,&wayx,sizeof(WayX));
160	amb	310	WriteFile(waysx->fd,name,strlen(name)+1);
161	amb	262
162			waysx->xnumber++;
163	amb	466
164			assert(!(waysx->xnumber==0)); /* Zero marks the high-water mark for ways. */
165	amb	110	}
166
167
168			/*++++++++++++++++++++++++++++++++++++++
169	amb	224	Sort the list of ways.
170	amb	110
171			WaysX* waysx The set of ways to process.
172			++++++++++++++++++++++++++++++++++++++*/
173
174			void SortWayList(WaysX* waysx)
175			{
176	amb	310	index_t i;
177	amb	555	int fd;
178	amb	310	char *names[2]={NULL,NULL};
179			int namelen[2]={0,0};
180	amb	499	int nnames=0;
181	amb	310	uint32_t lastlength=0;
182	amb	110
183	amb	266	/* Print the start message */
184
185	amb	519	printf_first("Sorting Ways by Name");
186	amb	110
187	amb	555	/* Close the file (finished appending) */
188	amb	203
189	amb	612	waysx->fd=CloseFile(waysx->fd);
190	amb	555
191			/* Re-open the file read-only and a new file writeable */
192
193	amb	262	waysx->fd=ReOpenFile(waysx->filename);
194	amb	216
195	amb	310	DeleteFile(waysx->filename);
196	amb	262
197	amb	502	fd=OpenFileNew(waysx->filename);
198	amb	310
199	amb	499	/* Sort the ways to allow separating the names */
200	amb	310
201	amb	499	filesort_vary(waysx->fd,fd,(int ()(const void,const void*))sort_by_name_and_id,NULL);
202	amb	310
203			/* Close the files */
204
205	amb	612	waysx->fd=CloseFile(waysx->fd);
206	amb	310	CloseFile(fd);
207
208			/* Print the final message */
209
210	amb	519	printf_last("Sorted Ways by Name: Ways=%d",waysx->xnumber);
211	amb	310
212
213			/* Print the start message */
214
215	amb	519	printf_first("Separating Way Names: Ways=0 Names=0");
216	amb	310
217	amb	555	/* Re-open the file read-only and new files writeable */
218	amb	310
219			waysx->fd=ReOpenFile(waysx->filename);
220
221	amb	272	DeleteFile(waysx->filename);
222	amb	262
223	amb	502	fd=OpenFileNew(waysx->filename);
224	amb	272
225	amb	555	waysx->nfd=OpenFileNew(waysx->nfilename);
226
227	amb	499	/* Copy from the single file into two files */
228	amb	310
229	amb	499	for(i=0;i<waysx->xnumber;i++)
230	amb	310	{
231			WayX wayx;
232	amb	311	FILESORT_VARINT size;
233	amb	310
234	amb	311	ReadFile(waysx->fd,&size,FILESORT_VARSIZE);
235	amb	310
236			if(namelen[nnames%2]<size)
237			names[nnames%2]=(char)realloc((void)names[nnames%2],namelen[nnames%2]=size);
238
239			ReadFile(waysx->fd,&wayx,sizeof(WayX));
240			ReadFile(waysx->fd,names[nnames%2],size-sizeof(WayX));
241
242			if(nnames==0 \|\| strcmp(names[0],names[1]))
243			{
244	amb	555	WriteFile(waysx->nfd,names[nnames%2],size-sizeof(WayX));
245	amb	310
246			lastlength=waysx->nlength;
247			waysx->nlength+=size-sizeof(WayX);
248
249			nnames++;
250			}
251
252			wayx.way.name=lastlength;
253
254			WriteFile(fd,&wayx,sizeof(WayX));
255
256			if(!((i+1)%10000))
257	amb	519	printf_middle("Separating Way Names: Ways=%d Names=%d",i+1,nnames);
258	amb	310	}
259
260			if(names[0]) free(names[0]);
261			if(names[1]) free(names[1]);
262
263			/* Close the files */
264
265	amb	612	waysx->fd=CloseFile(waysx->fd);
266	amb	310	CloseFile(fd);
267
268	amb	612	waysx->nfd=CloseFile(waysx->nfd);
269	amb	310
270			/* Print the final message */
271
272	amb	519	printf_last("Separated Way Names: Ways=%d Names=%d ",waysx->xnumber,nnames);
273	amb	310
274
275			/* Print the start message */
276
277	amb	519	printf_first("Sorting Ways");
278	amb	310
279	amb	555	/* Re-open the file read-only and a new file writeable */
280	amb	310
281			waysx->fd=ReOpenFile(waysx->filename);
282
283			DeleteFile(waysx->filename);
284
285	amb	502	fd=OpenFileNew(waysx->filename);
286	amb	310
287	amb	272	/* Allocate the array of indexes */
288
289	amb	499	waysx->idata=(way_t)malloc(waysx->xnumbersizeof(way_t));
290	amb	262
291	amb	243	assert(waysx->idata); /* Check malloc() worked */
292
293	amb	310	/* Sort the ways by index and index them */
294	amb	203
295	amb	499	waysx->number=0;
296
297	amb	272	sortwaysx=waysx;
298	amb	215
299	amb	499	filesort_fixed(waysx->fd,fd,sizeof(WayX),(int ()(const void,const void))sort_by_id,(int ()(void*,index_t))deduplicate_and_index_by_id);
300	amb	215
301	amb	555	/* Close the files */
302	amb	262
303	amb	612	waysx->fd=CloseFile(waysx->fd);
304	amb	262	CloseFile(fd);
305
306	amb	266	/* Print the final message */
307
308	amb	519	printf_last("Sorted Ways: Ways=%d Duplicates=%d",waysx->number,waysx->xnumber-waysx->number);
309	amb	499	}
310
311
312			/*++++++++++++++++++++++++++++++++++++++
313			Compact the list of ways.
314
315			WaysX* waysx The set of ways to process.
316			++++++++++++++++++++++++++++++++++++++*/
317
318			void CompactWayList(WaysX* waysx)
319			{
320			index_t i;
321			int fd;
322			Way lastway;
323
324			/* Print the start message */
325
326	amb	519	printf_first("Sorting Ways by Properties");
327	amb	499
328	amb	555	/* Re-open the file read-only and a new file writeable */
329	amb	499
330			waysx->fd=ReOpenFile(waysx->filename);
331
332			DeleteFile(waysx->filename);
333
334	amb	502	fd=OpenFileNew(waysx->filename);
335	amb	499
336			/* Sort the ways to allow compacting according to he properties */
337
338			filesort_fixed(waysx->fd,fd,sizeof(WayX),(int ()(const void,const void*))sort_by_name_and_prop_and_id,NULL);
339
340			/* Close the files */
341
342	amb	612	waysx->fd=CloseFile(waysx->fd);
343	amb	499	CloseFile(fd);
344
345			/* Print the final message */
346
347	amb	519	printf_last("Sorted Ways by Properties: Ways=%d",waysx->number);
348	amb	499
349
350			/* Print the start message */
351
352	amb	519	printf_first("Compacting Ways: Ways=0 Properties=0");
353	amb	499
354	amb	555	/* Re-open the file read-only and a new file writeable */
355	amb	499
356			waysx->fd=ReOpenFile(waysx->filename);
357
358			DeleteFile(waysx->filename);
359
360	amb	502	fd=OpenFileNew(waysx->filename);
361	amb	499
362			/* Update the way as we go using the sorted index */
363
364			waysx->cnumber=0;
365
366			for(i=0;i<waysx->number;i++)
367			{
368			WayX wayx;
369
370			ReadFile(waysx->fd,&wayx,sizeof(WayX));
371
372			if(waysx->cnumber==0 \|\| wayx.way.name!=lastway.name \|\| WaysCompare(&lastway,&wayx.way))
373			{
374			lastway=wayx.way;
375
376			waysx->cnumber++;
377			}
378
379			wayx.prop=waysx->cnumber-1;
380
381			WriteFile(fd,&wayx,sizeof(WayX));
382
383			if(!((i+1)%10000))
384	amb	519	printf_middle("Compacting Ways: Ways=%d Properties=%d",i+1,waysx->cnumber);
385	amb	499	}
386
387			/* Close the files */
388
389	amb	612	waysx->fd=CloseFile(waysx->fd);
390	amb	499	CloseFile(fd);
391
392			/* Print the final message */
393
394	amb	519	printf_last("Compacted Ways: Ways=%d Properties=%d ",waysx->number,waysx->cnumber);
395	amb	499
396
397			/* Print the start message */
398
399	amb	519	printf_first("Sorting Ways");
400	amb	499
401	amb	555	/* Re-open the file read-only and a new file writeable */
402	amb	499
403			waysx->fd=ReOpenFile(waysx->filename);
404
405			DeleteFile(waysx->filename);
406
407	amb	502	fd=OpenFileNew(waysx->filename);
408	amb	499
409			/* Sort the ways by index */
410
411			filesort_fixed(waysx->fd,fd,sizeof(WayX),(int ()(const void,const void*))sort_by_id,NULL);
412
413	amb	555	/* Close the files */
414	amb	499
415	amb	612	waysx->fd=CloseFile(waysx->fd);
416	amb	499	CloseFile(fd);
417
418			/* Print the final message */
419
420	amb	519	printf_last("Sorted Ways: Ways=%d",waysx->number);
421	amb	224	}
422
423
424			/*++++++++++++++++++++++++++++++++++++++
425	amb	262	Sort the ways into id order.
426	amb	224
427	amb	262	int sort_by_id Returns the comparison of the id fields.
428
429	amb	272	WayX *a The first extended way.
430	amb	262
431	amb	272	WayX *b The second extended way.
432	amb	262	++++++++++++++++++++++++++++++++++++++*/
433
434	amb	272	static int sort_by_id(WayX a,WayX b)
435	amb	262	{
436	amb	272	way_t a_id=a->id;
437			way_t b_id=b->id;
438	amb	262
439			if(a_id<b_id)
440			return(-1);
441			else if(a_id>b_id)
442			return(1);
443			else
444			return(0);
445			}
446
447
448			/*++++++++++++++++++++++++++++++++++++++
449	amb	499	Sort the ways into name and id order.
450	amb	272
451	amb	499	int sort_by_name_and_id Returns the comparison of the name and id fields.
452	amb	272
453	amb	310	WayX *a The first extended Way.
454
455			WayX *b The second extended Way.
456			++++++++++++++++++++++++++++++++++++++*/
457
458	amb	499	static int sort_by_name_and_id(WayX a,WayX b)
459	amb	310	{
460			int compare;
461			char a_name=(char)a+sizeof(WayX);
462			char b_name=(char)b+sizeof(WayX);
463
464			compare=strcmp(a_name,b_name);
465
466			if(compare)
467			return(compare);
468
469	amb	499	return(sort_by_id(a,b));
470			}
471
472
473			/*++++++++++++++++++++++++++++++++++++++
474			Sort the ways into name, properties and id order.
475
476			int sort_by_name_and_prop_and_id Returns the comparison of the name, properties and id fields.
477
478			WayX *a The first extended Way.
479
480			WayX *b The second extended Way.
481			++++++++++++++++++++++++++++++++++++++*/
482
483			static int sort_by_name_and_prop_and_id(WayX a,WayX b)
484			{
485			int compare;
486			index_t a_name=a->way.name;
487			index_t b_name=b->way.name;
488
489			if(a_name<b_name)
490			return(-1);
491			else if(a_name>b_name)
492			return(1);
493
494	amb	310	compare=WaysCompare(&a->way,&b->way);
495
496			if(compare)
497			return(compare);
498
499			return(sort_by_id(a,b));
500			}
501
502
503			/*++++++++++++++++++++++++++++++++++++++
504	amb	499	Deduplicate the extended ways using the id after sorting and create the index.
505	amb	310
506	amb	499	int deduplicate_and_index_by_id Return 1 if the value is to be kept, otherwise zero.
507	amb	310
508	amb	272	WayX *wayx The extended way.
509
510			index_t index The index of this way in the total.
511			++++++++++++++++++++++++++++++++++++++*/
512
513	amb	499	static int deduplicate_and_index_by_id(WayX *wayx,index_t index)
514	amb	272	{
515	amb	310	static way_t previd;
516
517			if(index==0 \|\| wayx->id!=previd)
518	amb	272	{
519	amb	310	previd=wayx->id;
520	amb	272
521			sortwaysx->number++;
522
523	amb	499	sortwaysx->idata[index]=wayx->id;
524
525	amb	272	return(1);
526			}
527
528			return(0);
529			}
530
531
532			/*++++++++++++++++++++++++++++++++++++++
533	amb	285	Find a particular way index.
534
535			index_t IndexWayX Returns the index of the extended way with the specified id.
536
537			WaysX* waysx The set of ways to process.
538
539			way_t id The way id to look for.
540			++++++++++++++++++++++++++++++++++++++*/
541
542			index_t IndexWayX(WaysX* waysx,way_t id)
543			{
544			int start=0;
545			int end=waysx->number-1;
546			int mid;
547
548			/* Binary search - search key exact match only is required.
549			*
550			* # <- start \| Check mid and move start or end if it doesn't match
551			* # \|
552			* # \| Since an exact match is wanted we can set end=mid-1
553			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
554			* # \|
555			* # \| Eventually either end=start or end=start+1 and one of
556			* # <- end \| start or end is the wanted one.
557			*/
558
559			if(end<start) /* There are no ways */
560			return(NO_WAY);
561			else if(id<waysx->idata[start]) /* Check key is not before start */
562			return(NO_WAY);
563			else if(id>waysx->idata[end]) /* Check key is not after end */
564			return(NO_WAY);
565			else
566			{
567			do
568			{
569			mid=(start+end)/2; /* Choose mid point */
570
571			if(waysx->idata[mid]<id) /* Mid point is too low */
572			start=mid+1;
573			else if(waysx->idata[mid]>id) /* Mid point is too high */
574			end=mid-1;
575			else /* Mid point is correct */
576			return(mid);
577			}
578			while((end-start)>1);
579
580			if(waysx->idata[start]==id) /* Start is correct */
581			return(start);
582
583			if(waysx->idata[end]==id) /* End is correct */
584			return(end);
585			}
586
587			return(NO_WAY);
588			}
589
590
591			/*++++++++++++++++++++++++++++++++++++++
592			Save the way list to a file.
593
594			WaysX* waysx The set of ways to save.
595
596			const char *filename The name of the file to save.
597			++++++++++++++++++++++++++++++++++++++*/
598
599	amb	398	void SaveWayList(WaysX* waysx,const char *filename)
600	amb	285	{
601			index_t i;
602	amb	555	int fd;
603	amb	310	int position=0;
604	amb	499	WaysFile waysfile={0};
605	amb	529	highways_t highways=0;
606			transports_t allow=0;
607	amb	530	properties_t props=0;
608	amb	285
609	amb	461	/* Print the start message */
610
611	amb	519	printf_first("Writing Ways: Ways=0");
612	amb	285
613	amb	555	/* Map into memory / open the file */
614	amb	461
615	amb	452	#if !SLIM
616			waysx->xdata=MapFile(waysx->filename);
617	amb	555	#else
618			waysx->fd=ReOpenFile(waysx->filename);
619	amb	452	#endif
620	amb	285
621	amb	461	/* Write out the ways data */
622	amb	285
623	amb	502	fd=OpenFileNew(filename);
624	amb	285
625	amb	461	SeekFile(fd,sizeof(WaysFile));
626	amb	285
627			for(i=0;i<waysx->number;i++)
628			{
629	amb	309	WayX *wayx=LookupWayX(waysx,i,1);
630	amb	285
631	amb	526	highways\|=HIGHWAYS(wayx->way.type);
632			allow \|=wayx->way.allow;
633			props \|=wayx->way.props;
634	amb	398
635	amb	464	SeekFile(fd,sizeof(WaysFile)+(off_t)wayx->prop*sizeof(Way));
636	amb	309	WriteFile(fd,&wayx->way,sizeof(Way));
637
638	amb	285	if(!((i+1)%10000))
639	amb	519	printf_middle("Writing Ways: Ways=%d",i+1);
640	amb	285	}
641
642	amb	555	/* Unmap from memory / close the file */
643	amb	398
644	amb	452	#if !SLIM
645			waysx->xdata=UnmapFile(waysx->filename);
646	amb	555	#else
647	amb	612	waysx->fd=CloseFile(waysx->fd);
648	amb	452	#endif
649	amb	285
650	amb	461	/* Write out the ways names */
651	amb	285
652	amb	464	SeekFile(fd,sizeof(WaysFile)+(off_t)waysx->cnumber*sizeof(Way));
653	amb	461
654	amb	555	waysx->nfd=ReOpenFile(waysx->nfilename);
655	amb	285
656	amb	309	while(position<waysx->nlength)
657			{
658			int len=1024;
659			char temp[1024];
660
661			if((waysx->nlength-position)<1024)
662			len=waysx->nlength-position;
663
664	amb	555	ReadFile(waysx->nfd,temp,len);
665	amb	309	WriteFile(fd,temp,len);
666
667			position+=len;
668			}
669
670	amb	555	/* Close the file */
671	amb	309
672	amb	612	waysx->nfd=CloseFile(waysx->nfd);
673	amb	555
674	amb	461	/* Write out the header structure */
675
676	amb	526	waysfile.number =waysx->cnumber;
677	amb	461	waysfile.onumber=waysx->number;
678
679	amb	526	waysfile.highways=highways;
680			waysfile.allow =allow;
681			waysfile.props =props;
682	amb	461
683			SeekFile(fd,0);
684			WriteFile(fd,&waysfile,sizeof(WaysFile));
685
686	amb	285	CloseFile(fd);
687
688	amb	461	/* Print the final message */
689
690	amb	519	printf_last("Wrote Ways: Ways=%d",waysx->number);
691	amb	285	}