trunk/src/waysx.c

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

#include "types.h"
#include "ways.h"

#include "typesx.h"
#include "segmentsx.h"
#include "waysx.h"

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


/* Global variables */

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


/* Local variables */

/*+ 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,(void*)waysx);

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

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

    size=SizeFile(waysx->filename);

    while(position<size)
      {
       FILESORT_VARINT waysize;

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

       waysx->number++;
       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,(void*)waysx);

 return(waysx);
}


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

  WaysX *waysx The set of ways to be freed.

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

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

 free(waysx->filename);

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

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

 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.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->number++;

 assert(waysx->number!=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,xnumber;
 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=%"Pindex_t,waysx->number);


 /* 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->number;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)%1000))
       printf_middle("Separating Way Names: Ways=%"Pindex_t" Names=%"Pindex_t,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=%"Pindex_t" Names=%"Pindex_t,waysx->number,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->number*sizeof(way_t));

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

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

 xnumber=waysx->number;
 waysx->number=0;

 sortwaysx=waysx;

 waysx->number=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=%"Pindex_t" Duplicates=%"Pindex_t,xnumber,xnumber-waysx->number);
}


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

  SegmentsX *segmentsx The set of segments to modify.

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

void CompactWayList(SegmentsX *segmentsx,WaysX *waysx)
{
 index_t i,unused=0;
 int fd;
 Way lastway;
 BitMask *waysused;
 char *filename_tmp=(char*)malloc(strlen(waysx->filename)+1);

 strcpy(filename_tmp,waysx->filename);
 strcat(filename_tmp,"c");


 /* Print the start message */

 printf_first("Sorting Ways by Properties");

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

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

 fd=OpenFileNew(filename_tmp);

 /* Sort the ways to allow compacting according to the 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=%"Pindex_t,waysx->number);


 /* Print the start message */

 printf_first("Checking Used Ways: Segments=0");

 /* Allocate the bitmask */

 waysused=AllocBitMask(waysx->number);

 assert(waysused); /* Check AllocBitMask() worked */

 /* Open the segments file and read through it */

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

 for(i=0;i<segmentsx->number;i++)
   {
    SegmentX segmentx;

    ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX));

    SetBit(waysused,segmentx.way);

    if(!(i%10000))
       printf_middle("Checking Used Ways: Segments=%"Pindex_t,i);
   }

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

 /* Print the final message */

 printf_last("Checked Used Ways: Segments=%"Pindex_t,segmentsx->number);


 /* Print the start message */

 printf_first("Compacting Ways: Ways=0 Unique=0 Unused=0");

 /* Allocate the array of indexes */

 waysx->cdata=(index_t*)malloc(waysx->number*sizeof(index_t));

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

 /* Re-open the temporary file read-only */

 fd=ReOpenFile(filename_tmp);

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

 waysx->cnumber=0;

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

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

    if(!IsBitSet(waysused,wayx.id))
      {
       unused++;

       waysx->cdata[wayx.id]=NO_WAY;
      }
    else
      {
       if(waysx->cnumber==0 || wayx.way.name!=lastway.name || WaysCompare(&lastway,&wayx.way))
         {
          lastway=wayx.way;

          waysx->cnumber++;
         }

       waysx->cdata[wayx.id]=waysx->cnumber-1;
      }

    if(!((i+1)%1000))
       printf_middle("Compacting Ways: Ways=%"Pindex_t" Unique=%"Pindex_t" Unused=%"Pindex_t,i+1,waysx->cnumber,unused);
   }

 /* Close the file and delete it */

 CloseFile(fd);
 DeleteFile(filename_tmp);

 /* Print the final message */

 printf_last("Compacted Ways: Ways=%"Pindex_t" Unique=%"Pindex_t" Unused=%"Pindex_t,waysx->number,waysx->cnumber,unused);

 free(waysused);

 free(filename_tmp);
}


/*++++++++++++++++++++++++++++++++++++++
  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 order and then 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));
}


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

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

  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->idata[index]=wayx->id;

    wayx->id=index;

    return(1);
   }
 else
   {
    logerror("Way %"Pway_t" is duplicated.\n",wayx->id);

    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)
{
 index_t start=0;
 index_t end=waysx->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 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?(mid-1):mid;
       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->data=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;

    if(waysx->cdata[i]!=NO_WAY)
       SeekWriteFile(fd,&wayx->way,sizeof(Way),sizeof(WaysFile)+(off_t)waysx->cdata[i]*sizeof(Way));

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

 /* Unmap from memory / close the file */

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