trunk/src/waysx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.39 2010-07-11 08:16:32 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 <string.h>
#include <sys/stat.h>

#include "functions.h"
#include "waysx.h"
#include "ways.h"


/* Variables */

/*+ The command line '--slim' option. +*/
extern int option_slim;

/*+ 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_name_and_prop_and_id(WayX *a,WayX *b);
static int deduplicate_by_id(WayX *wayx,index_t index);

static int sort_by_id(WayX *a,WayX *b);
static int 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 way to a way list.

  void AppendWay Returns the newly appended way.

  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;

 assert(!waysx->idata);       /* Must not have idata filled in => unsorted */

 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++;
}


/*++++++++++++++++++++++++++++++++++++++
  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,nprops=0;
 uint32_t lastlength=0;
 Way lastway;

 /* Check the start conditions */

 assert(!waysx->idata);         /* Must not have idata filled in => unsorted */

 /* Print the start message */

 printf("Sorting Ways");
 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 compacting them and remove duplicates */

 sortwaysx=waysx;

 filesort_vary(waysx->fd,fd,(int (*)(const void*,const void*))sort_by_name_and_prop_and_id,(int (*)(void*,index_t))deduplicate_by_id);

 /* Close the files */

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

 /* Print the final message */

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


 /* Print the start message */

 printf("Compacting Ways: Ways=0 Names=0 Properties=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 and index as we go. */

 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(nfd,names[nnames%2],size-sizeof(WayX));

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

       nnames++;
      }

    wayx.way.name=lastlength;

    if(nprops==0 || wayx.way.name!=lastway.name || WaysCompare(&lastway,&wayx.way))
      {
       lastway=wayx.way;

       waysx->cnumber++;

       nprops++;
      }

    wayx.prop=nprops-1;

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

    if(!((i+1)%10000))
      {
       printf("\rCompacting Ways: Ways=%d Names=%d Properties=%d",i+1,nnames,nprops);
       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("\rCompacted Ways: Ways=%d Names=%d Properties=%d \n",waysx->number,nnames,nprops);
 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->number*sizeof(way_t));

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

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

 sortwaysx=waysx;

 filesort_fixed(waysx->fd,fd,sizeof(WayX),(int (*)(const void*,const void*))sort_by_id,(int (*)(void*,index_t))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\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, 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;
 char *a_name=(char*)a+sizeof(WayX);
 char *b_name=(char*)b+sizeof(WayX);

 compare=strcmp(a_name,b_name);

 if(compare)
    return(compare);

 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.

  int deduplicate_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_by_id(WayX *wayx,index_t index)
{
 static way_t previd;

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

    sortwaysx->number++;

    return(1);
   }

 return(0);
}


/*++++++++++++++++++++++++++++++++++++++
  Index the ways after sorting.

  int 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 index_by_id(WayX *wayx,index_t index)
{
 sortwaysx->idata[index]=wayx->id;

 return(1);
}


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

 assert(waysx->idata);         /* Must have idata filled in => sorted */

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


/*++++++++++++++++++++++++++++++++++++++
  Lookup a particular way.

  WayX *LookupWayX Returns a pointer to the extended way with the specified id.

  WaysX* waysx The set of ways to process.

  index_t index The way index to look for.

  int position The position in the cache to use.
  ++++++++++++++++++++++++++++++++++++++*/

WayX *LookupWayX(WaysX* waysx,index_t index,int position)
{
 assert(index!=NO_WAY);     /* Must be a valid way */

 if(option_slim)
   {
    SeekFile(waysx->fd,index*sizeof(WayX));

    ReadFile(waysx->fd,&waysx->cached[position-1],sizeof(WayX));

    return(&waysx->cached[position-1]);
   }
 else
   {
    return(&waysx->xdata[index]);
   }
}


/*++++++++++++++++++++++++++++++++++++++
  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;
 Ways *ways;

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

 if(!option_slim)
    waysx->xdata=MapFile(waysx->filename);

 /* Fill in a Ways structure with the offset of the real data in the file after
    the Way structure itself. */

 ways=calloc(1,sizeof(Ways));

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

 ways->number=waysx->cnumber;
 ways->onumber=waysx->number;

 ways->allow=0;
 ways->props=0;

 ways->data=NULL;
 ways->ways=NULL;
 ways->names=NULL;

 /* Write out the Ways structure and then the real data. */

 fd=OpenFile(filename);

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

    ways->allow|=wayx->way.allow;
    ways->props|=wayx->way.props;

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

    if(!((i+1)%10000))
      {
       printf("\rWriting Ways: Ways=%d",i+1);
       fflush(stdout);
      }
   }

 SeekFile(fd,0);
 WriteFile(fd,ways,sizeof(Ways));

 if(!option_slim)
    waysx->xdata=UnmapFile(waysx->filename);

 SeekFile(fd,sizeof(Ways)+ways->number*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);

 CloseFile(fd);

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

 /* Free the fake Ways */

 free(ways);
}
1	amb	110	/***************************************
2	amb	447	$Header: /home/amb/CVS/routino/src/waysx.c,v 1.39 2010-07-11 08:16:32 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			#include <string.h>
28	amb	326	#include <sys/stat.h>
29	amb	110
30			#include "functions.h"
31			#include "waysx.h"
32	amb	228	#include "ways.h"
33	amb	110
34
35	amb	262	/* Variables */
36	amb	110
37	amb	289	/+ The command line '--slim' option. +/
38	amb	262	extern int option_slim;
39	amb	289
40			/+ 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	310	static int sort_by_name_and_prop_and_id(WayX a,WayX b);
49			static int deduplicate_by_id(WayX *wayx,index_t index);
50
51	amb	272	static int sort_by_id(WayX a,WayX b);
52			static int index_by_id(WayX *wayx,index_t index);
53
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			waysx->fd=AppendFile(waysx->filename);
83
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			waysx->fd=OpenFile(waysx->filename);
101
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	262	Append a way to a way list.
137	amb	203
138	amb	262	void AppendWay Returns the newly appended way.
139	amb	243
140	amb	262	WaysX* waysx The set of ways to process.
141	amb	110
142	amb	262	way_t id The ID of the way.
143	amb	110
144	amb	262	Way *way The way data itself.
145	amb	110
146	amb	262	const char *name The name or reference of the way.
147			++++++++++++++++++++++++++++++++++++++*/
148	amb	110
149	amb	262	void AppendWay(WaysX* waysx,way_t id,Way way,const char name)
150			{
151			WayX wayx;
152	amb	311	FILESORT_VARINT size;
153	amb	110
154	amb	262	assert(!waysx->idata); /* Must not have idata filled in => unsorted */
155
156			wayx.id=id;
157	amb	310	wayx.prop=0;
158	amb	262	wayx.way=*way;
159
160	amb	310	size=sizeof(WayX)+strlen(name)+1;
161
162	amb	311	WriteFile(waysx->fd,&size,FILESORT_VARSIZE);
163	amb	262	WriteFile(waysx->fd,&wayx,sizeof(WayX));
164	amb	310	WriteFile(waysx->fd,name,strlen(name)+1);
165	amb	262
166			waysx->xnumber++;
167	amb	110	}
168
169
170			/*++++++++++++++++++++++++++++++++++++++
171	amb	224	Sort the list of ways.
172	amb	110
173			WaysX* waysx The set of ways to process.
174			++++++++++++++++++++++++++++++++++++++*/
175
176			void SortWayList(WaysX* waysx)
177			{
178	amb	310	index_t i;
179			int fd,nfd;
180			char *names[2]={NULL,NULL};
181			int namelen[2]={0,0};
182			int nnames=0,nprops=0;
183			uint32_t lastlength=0;
184			Way lastway;
185	amb	110
186	amb	266	/* Check the start conditions */
187
188	amb	243	assert(!waysx->idata); /* Must not have idata filled in => unsorted */
189	amb	110
190	amb	266	/* Print the start message */
191
192	amb	227	printf("Sorting Ways");
193			fflush(stdout);
194	amb	110
195	amb	310	/* Close the file and re-open it (finished appending) */
196	amb	203
197	amb	262	CloseFile(waysx->fd);
198			waysx->fd=ReOpenFile(waysx->filename);
199	amb	216
200	amb	310	DeleteFile(waysx->filename);
201	amb	262
202	amb	310	fd=OpenFile(waysx->filename);
203
204			/* Sort the ways to allow compacting them and remove duplicates */
205
206			sortwaysx=waysx;
207
208	amb	311	filesort_vary(waysx->fd,fd,(int ()(const void,const void))sort_by_name_and_prop_and_id,(int ()(void*,index_t))deduplicate_by_id);
209	amb	310
210			/* Close the files */
211
212			CloseFile(waysx->fd);
213			CloseFile(fd);
214
215			/* Print the final message */
216
217			printf("\rSorted Ways: Ways=%d Duplicates=%d\n",waysx->xnumber,waysx->xnumber-waysx->number);
218			fflush(stdout);
219
220
221			/* Print the start message */
222
223			printf("Compacting Ways: Ways=0 Names=0 Properties=0");
224			fflush(stdout);
225
226			/* Open the files */
227
228			waysx->fd=ReOpenFile(waysx->filename);
229
230	amb	272	DeleteFile(waysx->filename);
231	amb	262
232	amb	272	fd=OpenFile(waysx->filename);
233	amb	310	nfd=OpenFile(waysx->nfilename);
234	amb	272
235	amb	310	/* Copy from the single file into two files and index as we go. */
236
237			for(i=0;i<waysx->number;i++)
238			{
239			WayX wayx;
240	amb	311	FILESORT_VARINT size;
241	amb	310
242	amb	311	ReadFile(waysx->fd,&size,FILESORT_VARSIZE);
243	amb	310
244			if(namelen[nnames%2]<size)
245			names[nnames%2]=(char)realloc((void)names[nnames%2],namelen[nnames%2]=size);
246
247			ReadFile(waysx->fd,&wayx,sizeof(WayX));
248			ReadFile(waysx->fd,names[nnames%2],size-sizeof(WayX));
249
250			if(nnames==0 \|\| strcmp(names[0],names[1]))
251			{
252			WriteFile(nfd,names[nnames%2],size-sizeof(WayX));
253
254			lastlength=waysx->nlength;
255			waysx->nlength+=size-sizeof(WayX);
256
257			nnames++;
258			}
259
260			wayx.way.name=lastlength;
261
262			if(nprops==0 \|\| wayx.way.name!=lastway.name \|\| WaysCompare(&lastway,&wayx.way))
263			{
264			lastway=wayx.way;
265
266			waysx->cnumber++;
267
268			nprops++;
269			}
270
271			wayx.prop=nprops-1;
272
273			WriteFile(fd,&wayx,sizeof(WayX));
274
275			if(!((i+1)%10000))
276			{
277			printf("\rCompacting Ways: Ways=%d Names=%d Properties=%d",i+1,nnames,nprops);
278			fflush(stdout);
279			}
280			}
281
282			if(names[0]) free(names[0]);
283			if(names[1]) free(names[1]);
284
285			/* Close the files */
286
287			CloseFile(waysx->fd);
288			CloseFile(fd);
289
290			waysx->fd=ReOpenFile(waysx->filename);
291
292			CloseFile(nfd);
293
294			/* Print the final message */
295
296			printf("\rCompacted Ways: Ways=%d Names=%d Properties=%d \n",waysx->number,nnames,nprops);
297			fflush(stdout);
298
299
300			/* Print the start message */
301
302			printf("Sorting Ways");
303			fflush(stdout);
304
305			/* Open the files */
306
307			waysx->fd=ReOpenFile(waysx->filename);
308
309			DeleteFile(waysx->filename);
310
311			fd=OpenFile(waysx->filename);
312
313	amb	272	/* Allocate the array of indexes */
314
315	amb	310	waysx->idata=(way_t)malloc(waysx->numbersizeof(way_t));
316	amb	262
317	amb	243	assert(waysx->idata); /* Check malloc() worked */
318
319	amb	310	/* Sort the ways by index and index them */
320	amb	203
321	amb	272	sortwaysx=waysx;
322	amb	215
323	amb	311	filesort_fixed(waysx->fd,fd,sizeof(WayX),(int ()(const void,const void))sort_by_id,(int ()(void*,index_t))index_by_id);
324	amb	215
325	amb	262	/* Close the files and re-open them */
326
327			CloseFile(waysx->fd);
328			CloseFile(fd);
329
330			waysx->fd=ReOpenFile(waysx->filename);
331
332	amb	266	/* Print the final message */
333
334	amb	310	printf("\rSorted Ways: Ways=%d\n",waysx->number);
335	amb	227	fflush(stdout);
336	amb	224	}
337
338
339			/*++++++++++++++++++++++++++++++++++++++
340	amb	262	Sort the ways into id order.
341	amb	224
342	amb	262	int sort_by_id Returns the comparison of the id fields.
343
344	amb	272	WayX *a The first extended way.
345	amb	262
346	amb	272	WayX *b The second extended way.
347	amb	262	++++++++++++++++++++++++++++++++++++++*/
348
349	amb	272	static int sort_by_id(WayX a,WayX b)
350	amb	262	{
351	amb	272	way_t a_id=a->id;
352			way_t b_id=b->id;
353	amb	262
354			if(a_id<b_id)
355			return(-1);
356			else if(a_id>b_id)
357			return(1);
358			else
359			return(0);
360			}
361
362
363			/*++++++++++++++++++++++++++++++++++++++
364	amb	310	Sort the ways into name, properties and id order.
365	amb	272
366	amb	310	int sort_by_name_and_prop_and_id Returns the comparison of the name, properties and id fields.
367	amb	272
368	amb	310	WayX *a The first extended Way.
369
370			WayX *b The second extended Way.
371			++++++++++++++++++++++++++++++++++++++*/
372
373			static int sort_by_name_and_prop_and_id(WayX a,WayX b)
374			{
375			int compare;
376			char a_name=(char)a+sizeof(WayX);
377			char b_name=(char)b+sizeof(WayX);
378
379			compare=strcmp(a_name,b_name);
380
381			if(compare)
382			return(compare);
383
384			compare=WaysCompare(&a->way,&b->way);
385
386			if(compare)
387			return(compare);
388
389			return(sort_by_id(a,b));
390			}
391
392
393			/*++++++++++++++++++++++++++++++++++++++
394			Deduplicate the extended ways using the id after sorting.
395
396			int deduplicate_by_id Return 1 if the value is to be kept, otherwise zero.
397
398	amb	272	WayX *wayx The extended way.
399
400			index_t index The index of this way in the total.
401			++++++++++++++++++++++++++++++++++++++*/
402
403	amb	310	static int deduplicate_by_id(WayX *wayx,index_t index)
404	amb	272	{
405	amb	310	static way_t previd;
406
407			if(index==0 \|\| wayx->id!=previd)
408	amb	272	{
409	amb	310	previd=wayx->id;
410	amb	272
411			sortwaysx->number++;
412
413			return(1);
414			}
415
416			return(0);
417			}
418
419
420			/*++++++++++++++++++++++++++++++++++++++
421	amb	310	Index the ways after sorting.
422
423			int index_by_id Return 1 if the value is to be kept, otherwise zero.
424
425			WayX *wayx The extended way.
426
427			index_t index The index of this way in the total.
428			++++++++++++++++++++++++++++++++++++++*/
429
430			static int index_by_id(WayX *wayx,index_t index)
431			{
432			sortwaysx->idata[index]=wayx->id;
433
434			return(1);
435			}
436
437
438			/*++++++++++++++++++++++++++++++++++++++
439	amb	285	Find a particular way index.
440
441			index_t IndexWayX Returns the index of the extended way with the specified id.
442
443			WaysX* waysx The set of ways to process.
444
445			way_t id The way id to look for.
446			++++++++++++++++++++++++++++++++++++++*/
447
448			index_t IndexWayX(WaysX* waysx,way_t id)
449			{
450			int start=0;
451			int end=waysx->number-1;
452			int mid;
453
454			assert(waysx->idata); /* Must have idata filled in => sorted */
455
456			/* Binary search - search key exact match only is required.
457			*
458			* # <- start \| Check mid and move start or end if it doesn't match
459			* # \|
460			* # \| Since an exact match is wanted we can set end=mid-1
461			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
462			* # \|
463			* # \| Eventually either end=start or end=start+1 and one of
464			* # <- end \| start or end is the wanted one.
465			*/
466
467			if(end<start) /* There are no ways */
468			return(NO_WAY);
469			else if(id<waysx->idata[start]) /* Check key is not before start */
470			return(NO_WAY);
471			else if(id>waysx->idata[end]) /* Check key is not after end */
472			return(NO_WAY);
473			else
474			{
475			do
476			{
477			mid=(start+end)/2; /* Choose mid point */
478
479			if(waysx->idata[mid]<id) /* Mid point is too low */
480			start=mid+1;
481			else if(waysx->idata[mid]>id) /* Mid point is too high */
482			end=mid-1;
483			else /* Mid point is correct */
484			return(mid);
485			}
486			while((end-start)>1);
487
488			if(waysx->idata[start]==id) /* Start is correct */
489			return(start);
490
491			if(waysx->idata[end]==id) /* End is correct */
492			return(end);
493			}
494
495			return(NO_WAY);
496			}
497
498
499			/*++++++++++++++++++++++++++++++++++++++
500			Lookup a particular way.
501
502			WayX *LookupWayX Returns a pointer to the extended way with the specified id.
503
504			WaysX* waysx The set of ways to process.
505
506			index_t index The way index to look for.
507
508			int position The position in the cache to use.
509			++++++++++++++++++++++++++++++++++++++*/
510
511			WayX LookupWayX(WaysX waysx,index_t index,int position)
512			{
513			assert(index!=NO_WAY); /* Must be a valid way */
514
515			if(option_slim)
516			{
517			SeekFile(waysx->fd,index*sizeof(WayX));
518
519			ReadFile(waysx->fd,&waysx->cached[position-1],sizeof(WayX));
520
521			return(&waysx->cached[position-1]);
522			}
523			else
524			{
525			return(&waysx->xdata[index]);
526			}
527			}
528
529
530			/*++++++++++++++++++++++++++++++++++++++
531			Save the way list to a file.
532
533			WaysX* waysx The set of ways to save.
534
535			const char *filename The name of the file to save.
536			++++++++++++++++++++++++++++++++++++++*/
537
538	amb	398	void SaveWayList(WaysX* waysx,const char *filename)
539	amb	285	{
540			index_t i;
541	amb	310	int fd,nfd;
542			int position=0;
543	amb	285	Ways *ways;
544
545			printf("Writing Ways: Ways=0");
546			fflush(stdout);
547
548	amb	309	if(!option_slim)
549			waysx->xdata=MapFile(waysx->filename);
550	amb	285
551			/* Fill in a Ways structure with the offset of the real data in the file after
552			the Way structure itself. */
553
554			ways=calloc(1,sizeof(Ways));
555
556			assert(ways); /* Check calloc() worked */
557
558			ways->number=waysx->cnumber;
559			ways->onumber=waysx->number;
560
561	amb	398	ways->allow=0;
562	amb	307	ways->props=0;
563
564	amb	285	ways->data=NULL;
565	amb	385	ways->ways=NULL;
566			ways->names=NULL;
567	amb	285
568			/* Write out the Ways structure and then the real data. */
569
570			fd=OpenFile(filename);
571
572			for(i=0;i<waysx->number;i++)
573			{
574	amb	309	WayX *wayx=LookupWayX(waysx,i,1);
575	amb	285
576	amb	398	ways->allow\|=wayx->way.allow;
577			ways->props\|=wayx->way.props;
578
579	amb	310	SeekFile(fd,sizeof(Ways)+wayx->prop*sizeof(Way));
580	amb	309	WriteFile(fd,&wayx->way,sizeof(Way));
581
582	amb	285	if(!((i+1)%10000))
583			{
584			printf("\rWriting Ways: Ways=%d",i+1);
585			fflush(stdout);
586			}
587			}
588
589	amb	398	SeekFile(fd,0);
590			WriteFile(fd,ways,sizeof(Ways));
591
592	amb	309	if(!option_slim)
593			waysx->xdata=UnmapFile(waysx->filename);
594	amb	285
595	amb	310	SeekFile(fd,sizeof(Ways)+ways->number*sizeof(Way));
596	amb	285
597	amb	310	nfd=ReOpenFile(waysx->nfilename);
598	amb	285
599	amb	309	while(position<waysx->nlength)
600			{
601			int len=1024;
602			char temp[1024];
603
604			if((waysx->nlength-position)<1024)
605			len=waysx->nlength-position;
606
607	amb	310	ReadFile(nfd,temp,len);
608	amb	309	WriteFile(fd,temp,len);
609
610			position+=len;
611			}
612
613	amb	310	CloseFile(nfd);
614	amb	309
615	amb	285	CloseFile(fd);
616
617			printf("\rWrote Ways: Ways=%d \n",waysx->number);
618			fflush(stdout);
619
620			/* Free the fake Ways */
621
622			free(ways);
623			}