trunk/src/waysx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.50 2010-09-17 18:38:39 amb Exp $

 Extended Way data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2010 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 "functions.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=AppendFile(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=OpenFile(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,nfd;
 char *names[2]={NULL,NULL};
 int namelen[2]={0,0};
 int nnames=0;
 uint32_t lastlength=0;

 /* Print the start message */

 printf("Sorting Ways by Name");
 fflush(stdout);

 /* Close the file and re-open it (finished appending) */

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

 DeleteFile(waysx->filename);

 fd=OpenFile(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 */

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

 /* Print the final message */

 printf("\rSorted Ways by Name: Ways=%d\n",waysx->xnumber);
 fflush(stdout);


 /* Print the start message */

 printf("Separating Way Names: Ways=0 Names=0");
 fflush(stdout);

 /* Open the files */

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

 DeleteFile(waysx->filename);

 fd=OpenFile(waysx->filename);
 nfd=OpenFile(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(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("\rSeparating Way Names: Ways=%d Names=%d",i+1,nnames);
       fflush(stdout);
      }
   }

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

 /* Close the files */

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

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

 CloseFile(nfd);

 /* Print the final message */

 printf("\rSeparated Way Names: Ways=%d Names=%d \n",waysx->xnumber,nnames);
 fflush(stdout);


 /* Print the start message */

 printf("Sorting Ways");
 fflush(stdout);

 /* Open the files */

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

 DeleteFile(waysx->filename);

 fd=OpenFile(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 and re-open them */

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

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

 /* Print the final message */

 printf("\rSorted Ways: Ways=%d Duplicates=%d\n",waysx->number,waysx->xnumber-waysx->number);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  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("Sorting Ways by Properties");
 fflush(stdout);

 /* Close the file and re-open it */

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

 DeleteFile(waysx->filename);

 fd=OpenFile(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 */

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

 /* Print the final message */

 printf("\rSorted Ways by Properties: Ways=%d\n",waysx->number);
 fflush(stdout);


 /* Print the start message */

 printf("Compacting Ways: Ways=0 Properties=0");
 fflush(stdout);

 /* Open the files */

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

 DeleteFile(waysx->filename);

 fd=OpenFile(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("\rCompacting Ways: Ways=%d Properties=%d",i+1,waysx->cnumber);
       fflush(stdout);
      }
   }

 /* Close the files */

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

 /* Print the final message */

 printf("\rCompacted Ways: Ways=%d Properties=%d \n",waysx->number,waysx->cnumber);
 fflush(stdout);


 /* Print the start message */

 printf("Sorting Ways");
 fflush(stdout);

 /* Open the files */

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

 DeleteFile(waysx->filename);

 fd=OpenFile(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 and re-open them */

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

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

 /* Print the final message */

 printf("\rSorted Ways: Ways=%d\n",waysx->number);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  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,nfd;
 int position=0;
 WaysFile waysfile={0};
 allow_t allow=0;
 wayprop_t  props=0;

 /* Print the start message */

 printf("Writing Ways: Ways=0");
 fflush(stdout);

 /* Map into memory */

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

 /* Write out the ways data */

 fd=OpenFile(filename);

 SeekFile(fd,sizeof(WaysFile));

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

    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("\rWriting Ways: Ways=%d",i+1);
       fflush(stdout);
      }
   }

 /* Unmap from memory */

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

 /* Write out the ways names */

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

 nfd=ReOpenFile(waysx->nfilename);

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

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

    ReadFile(nfd,temp,len);
    WriteFile(fd,temp,len);

    position+=len;
   }

 CloseFile(nfd);

 /* Write out the header structure */

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

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

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

 CloseFile(fd);

 /* Print the final message */

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