trunk/src/waysx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.27 2009-10-12 17:35:26 amb Exp $

 Extended Way data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008,2009 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 "functions.h"
#include "waysx.h"
#include "ways.h"


/* Constants */

#define SORT_RAMSIZE (64*1024*1024)

/* Variables */

extern int option_slim;
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 index_by_id(WayX *wayx,index_t index);

static int sort_by_name(char *a,char *b);
static index_t index_way_name(char** names,int number,char *name);
static int sort_by_name_and_properties(Way *a,Way *b);
static index_t index_way(Way** data,int number,Way *way);


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new way list.

  WaysX *NewWayList Returns the way list.
  ++++++++++++++++++++++++++++++++++++++*/

WaysX *NewWayList(void)
{
 WaysX *waysx;

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

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

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

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

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

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

 return(waysx);
}


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

  WaysX *waysx The list to be freed.
  ++++++++++++++++++++++++++++++++++++++*/

void FreeWayList(WaysX *waysx)
{
 DeleteFile(waysx->filename);
 free(waysx->filename);

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

 DeleteFile(waysx->nfilename);
 free(waysx->nfilename);

 free(waysx);
}


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

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

 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->data=NULL;

 ways->ways=(void*)sizeof(Ways);
 ways->names=(void*)(sizeof(Ways)+ways->number*sizeof(Way));

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

 fd=OpenFile(filename);

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

 for(i=0;i<waysx->number;i++)
   {
    SeekFile(fd,sizeof(Ways)+waysx->xdata[i].id*sizeof(Way));
    WriteFile(fd,&waysx->xdata[i].way,sizeof(Way));

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

 waysx->xdata=UnmapFile(waysx->filename);

 waysx->names=MapFile(waysx->nfilename);

 SeekFile(fd,sizeof(Ways)+waysx->cnumber*sizeof(Way));
 WriteFile(fd,waysx->names,waysx->nlength);

 waysx->names=UnmapFile(waysx->nfilename);

 CloseFile(fd);

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

 /* Free the fake Ways */

 free(ways);
}


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


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

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

 wayx.id=id;
 wayx.way=*way;
 wayx.name=waysx->nlength;

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

 waysx->xnumber++;

 WriteFile(waysx->nfd,name,strlen(name)+1);

 waysx->nlength+=strlen(name)+1;
}


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

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

void SortWayList(WaysX* waysx)
{
 int fd;

 /* 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 files and re-open them (finished appending) */

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

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

 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 way indexes and remove duplicates */

 sortwaysx=waysx;

 filesort(waysx->fd,fd,sizeof(WayX),SORT_RAMSIZE,(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 Duplicates=%d\n",waysx->xnumber,waysx->xnumber-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);
}


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

  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)
{
 if(index==0 || sortwaysx->idata[index-1]!=wayx->id)
   {
    sortwaysx->idata[index]=wayx->id;

    sortwaysx->number++;

    return(1);
   }

 return(0);
}


/*++++++++++++++++++++++++++++++++++++++
  Compact the list of way names.

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

void CompactWayNames(WaysX* waysx)
{
 index_t i,j,*offsets;
 char **cnames;
 WayX wayx;
 int duplicate=0;
 int fd,nfd;

 /* Print the start message for sorting names */

 printf("Sorting Way names");
 fflush(stdout);

 /* Get the uncompacted name data and create list for compacted */

 waysx->xdata=MapFile(waysx->filename);

 waysx->names=MapFile(waysx->nfilename);

 cnames=(char**)malloc(waysx->number*sizeof(char*));

 assert(cnames); /* Check malloc() worked */

 /* Create the index of names, sort it and remove duplicates */

 for(i=0;i<waysx->number;i++)
    cnames[i]=&waysx->names[waysx->xdata[i].name];

 heapsort((void**)cnames,waysx->number,(int (*)(const void*,const void*))sort_by_name);

 j=0;
 for(i=1;i<waysx->number;i++)
    if(strcmp(cnames[i],cnames[j]))
       cnames[++j]=cnames[i];
    else
       duplicate++;

 waysx->nnumber=++j;

 /* Sort the on-disk image */

 DeleteFile(waysx->nfilename);

 nfd=OpenFile(waysx->nfilename);

 offsets=(index_t*)malloc(waysx->nnumber*sizeof(index_t));

 assert(offsets); /* Check malloc() worked */

 waysx->nlength=0;

 for(i=0;i<waysx->nnumber;i++)
   {
    offsets[i]=waysx->nlength;
    waysx->nlength+=strlen(cnames[i])+1;
    WriteFile(nfd,cnames[i],strlen(cnames[i])+1);
   }

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

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

 /* Print the final message for sorting names */

 printf("\rSorted Way names: Names=%d Duplicate=%d\n",waysx->number,duplicate);
 fflush(stdout);

 /* Print the start message for compacting names */

 printf("Compacting Way names");
 fflush(stdout);

 /* Update the on-disk image */

 DeleteFile(waysx->filename);

 fd=OpenFile(waysx->filename);
 SeekFile(waysx->fd,0);

 while(!ReadFile(waysx->fd,&wayx,sizeof(WayX)))
   {
    wayx.way.name=offsets[index_way_name(cnames,waysx->nnumber,&waysx->names[wayx.name])];

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

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

 waysx->xdata=UnmapFile(waysx->filename);
 waysx->names=UnmapFile(waysx->nfilename);

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

 /* Print the final message for compacting names */

 printf("\rCompacted Way names: Names=%d Unique=%d\n",waysx->number,waysx->nnumber);
 fflush(stdout);

 free(cnames);
 free(offsets);
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the way names.

  int sort_by_name Returns the comparison of the name fields.

  char *a The first extended Way.

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

static int sort_by_name(char *a,char *b)
{
 if(a==NULL)
    return(1);
 else if(b==NULL)
    return(-1);
 else
    return(strcmp(a,b));
}


/*++++++++++++++++++++++++++++++++++++++
  Find a particular name within the sorted list of names.

  index_t index_way_name Returns the index of the name within the list.

  char **names The set of names to search.

  int number The number of names.

  char *name The name to look for.
  ++++++++++++++++++++++++++++++++++++++*/

static index_t index_way_name(char** names,int number,char *name)
{
 int start=0;
 int end=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.
  */

 do
   {
    mid=(start+end)/2;                 /* Choose mid point */

    if(strcmp(name,names[mid])>0)      /* Mid point is too low */
       start=mid+1;
    else if(strcmp(name,names[mid])<0) /* Mid point is too high */
       end=mid-1;
    else                               /* Mid point is correct */
       return(mid);
   }
 while((end-start)>1);

 if(strcmp(name,names[start])==0)      /* Start is correct */
    return(start);

 if(strcmp(name,names[end])==0)        /* End is correct */
    return(end);

 assert(0);

 return(NO_WAY);
}


/*++++++++++++++++++++++++++++++++++++++
  Compact the list of way properties.

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

void CompactWayProperties(WaysX* waysx)
{
 index_t i,j;
 WayX wayx;
 Way **cdata;
 int duplicate=0;
 int fd;

 /* Print the start message for sorting properties */

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

 /* Get the uncompacted data and create list for compacted */

 waysx->xdata=MapFile(waysx->filename);

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

 assert(cdata); /* Check malloc() worked */

 for(i=0;i<waysx->number;i++)
    cdata[i]=&waysx->xdata[i].way;

 /* Create the index of names, sort it and remove duplicates */

 heapsort((void**)cdata,waysx->number,(int (*)(const void*,const void*))sort_by_name_and_properties);

 j=0;
 for(i=1;i<waysx->number;i++)
    if(cdata[i-1]->name!=cdata[i]->name || WaysCompare(cdata[i-1],cdata[i]))
       cdata[++j]=cdata[i];
    else
       duplicate++;

 waysx->cnumber=++j;

 /* Print the final message for sorting properties */

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

 /* Print the start message for compacting properties */

 printf("Compacting Way properties");
 fflush(stdout);

 /* Update the on-disk image */

 DeleteFile(waysx->filename);

 fd=OpenFile(waysx->filename);
 SeekFile(waysx->fd,0);

 while(!ReadFile(waysx->fd,&wayx,sizeof(WayX)))
   {
    wayx.id=index_way(cdata,waysx->cnumber,&wayx.way);

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

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

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

 waysx->xdata=UnmapFile(waysx->filename);

 /* Print the final message for compacting properties */

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

 free(cdata);
}


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

  int sort_by_name_and_properties Returns the comparison of the name and properties fields.

  Way *a The first Way.

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

static int sort_by_name_and_properties(Way *a,Way *b)
{
 if(a==NULL)
    return(1);
 else if(b==NULL)
    return(-1);
 else
   {
    index_t a_name=a->name;
    index_t b_name=b->name;

    if(a_name<b_name)
       return(-1);
    else if(a_name>b_name)
       return(1);
    else
       return(WaysCompare(a,b));
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Find a particular Way within the sorted list of ways.

  index_t index_way Returns the index of the Way within the list.

  Way **data The set of Ways to search.

  int number The number of Ways.

  Way *way The name to look for.
  ++++++++++++++++++++++++++++++++++++++*/

static index_t index_way(Way** data,int number,Way *way)
{
 int start=0;
 int end=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.
  */

 do
   {
    mid=(start+end)/2;                    /* Choose mid point */

    if(way->name>data[mid]->name)         /* Mid point is too low */
       start=mid+1;
    else if(way->name<data[mid]->name)    /* Mid point is too high */
       end=mid-1;
    else if(WaysCompare(way,data[mid])>0) /* Mid point is too low */
       start=mid+1;
    else if(WaysCompare(way,data[mid])<0) /* Mid point is too high */
       end=mid-1;
    else                                  /* Mid point is correct */
       return(mid);
   }
 while((end-start)>1);

 if(way->name==data[start]->name && !WaysCompare(way,data[start]))   /* Start is correct */
    return(start);

 if(way->name==data[end]->name && !WaysCompare(way,data[end]))       /* End is correct */
    return(end);

 assert(0);

 return(NO_WAY);
}
1	amb	110	/***************************************
2	amb	284	$Header: /home/amb/CVS/routino/src/waysx.c,v 1.27 2009-10-12 17:35:26 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	151	This file Copyright 2008,2009 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
29			#include "functions.h"
30			#include "waysx.h"
31	amb	228	#include "ways.h"
32	amb	110
33
34	amb	272	/* Constants */
35
36			#define SORT_RAMSIZE (6410241024)
37
38	amb	262	/* Variables */
39	amb	110
40	amb	262	extern int option_slim;
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	272	static int sort_by_id(WayX a,WayX b);
49			static int index_by_id(WayX *wayx,index_t index);
50
51	amb	276	static int sort_by_name(char a,char b);
52	amb	262	static index_t index_way_name(char** names,int number,char *name);
53	amb	276	static int sort_by_name_and_properties(Way a,Way b);
54	amb	262	static index_t index_way(Way** data,int number,Way *way);
55	amb	110
56
57			/*++++++++++++++++++++++++++++++++++++++
58			Allocate a new way list.
59
60			WaysX *NewWayList Returns the way list.
61			++++++++++++++++++++++++++++++++++++++*/
62
63			WaysX *NewWayList(void)
64			{
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			sprintf(waysx->filename,"%s/ways.%p.tmp",option_tmpdirname,waysx);
73	amb	216
74	amb	262	waysx->fd=OpenFile(waysx->filename);
75
76	amb	284	waysx->nfilename=(char*)malloc(strlen(option_tmpdirname)+32);
77			sprintf(waysx->nfilename,"%s/waynames.%p.tmp",option_tmpdirname,waysx);
78	amb	262
79			waysx->nfd=OpenFile(waysx->nfilename);
80
81	amb	110	return(waysx);
82			}
83
84
85			/*++++++++++++++++++++++++++++++++++++++
86	amb	226	Free a way list.
87
88			WaysX *waysx The list to be freed.
89			++++++++++++++++++++++++++++++++++++++*/
90
91			void FreeWayList(WaysX *waysx)
92			{
93	amb	262	DeleteFile(waysx->filename);
94	amb	283	free(waysx->filename);
95	amb	262
96	amb	226	if(waysx->idata)
97			free(waysx->idata);
98
99	amb	262	DeleteFile(waysx->nfilename);
100	amb	283	free(waysx->nfilename);
101	amb	226
102			free(waysx);
103			}
104
105
106			/*++++++++++++++++++++++++++++++++++++++
107	amb	110	Save the way list to a file.
108
109			WaysX* waysx The set of ways to save.
110
111			const char *filename The name of the file to save.
112			++++++++++++++++++++++++++++++++++++++*/
113
114			void SaveWayList(WaysX* waysx,const char *filename)
115			{
116	amb	214	index_t i;
117	amb	110	int fd;
118	amb	243	Ways *ways;
119	amb	110
120	amb	227	printf("Writing Ways: Ways=0");
121			fflush(stdout);
122
123	amb	275	waysx->xdata=MapFile(waysx->filename);
124	amb	262
125	amb	110	/* Fill in a Ways structure with the offset of the real data in the file after
126			the Way structure itself. */
127
128	amb	243	ways=calloc(1,sizeof(Ways));
129
130			assert(ways); /* Check calloc() worked */
131
132	amb	262	ways->number=waysx->cnumber;
133	amb	232	ways->onumber=waysx->number;
134
135	amb	110	ways->data=NULL;
136	amb	232
137	amb	110	ways->ways=(void*)sizeof(Ways);
138	amb	214	ways->names=(void)(sizeof(Ways)+ways->numbersizeof(Way));
139	amb	110
140			/* Write out the Ways structure and then the real data. */
141
142			fd=OpenFile(filename);
143
144			WriteFile(fd,ways,sizeof(Ways));
145
146	amb	262	for(i=0;i<waysx->number;i++)
147	amb	132	{
148	amb	280	SeekFile(fd,sizeof(Ways)+waysx->xdata[i].id*sizeof(Way));
149	amb	262	WriteFile(fd,&waysx->xdata[i].way,sizeof(Way));
150	amb	110
151	amb	132	if(!((i+1)%10000))
152			{
153			printf("\rWriting Ways: Ways=%d",i+1);
154			fflush(stdout);
155			}
156			}
157
158	amb	275	waysx->xdata=UnmapFile(waysx->filename);
159	amb	132
160	amb	262	waysx->names=MapFile(waysx->nfilename);
161	amb	110
162	amb	262	SeekFile(fd,sizeof(Ways)+waysx->cnumber*sizeof(Way));
163			WriteFile(fd,waysx->names,waysx->nlength);
164
165			waysx->names=UnmapFile(waysx->nfilename);
166
167	amb	110	CloseFile(fd);
168
169	amb	262	printf("\rWrote Ways: Ways=%d \n",waysx->number);
170			fflush(stdout);
171
172	amb	110	/* Free the fake Ways */
173
174			free(ways);
175			}
176
177
178			/*++++++++++++++++++++++++++++++++++++++
179	amb	262	Find a particular way index.
180	amb	203
181	amb	262	index_t IndexWayX Returns the index of the extended way with the specified id.
182	amb	203
183			WaysX* waysx The set of ways to process.
184
185			way_t id The way id to look for.
186			++++++++++++++++++++++++++++++++++++++*/
187
188	amb	262	index_t IndexWayX(WaysX* waysx,way_t id)
189	amb	203	{
190			int start=0;
191			int end=waysx->number-1;
192			int mid;
193
194	amb	243	assert(waysx->idata); /* Must have idata filled in => sorted */
195	amb	203
196			/* Binary search - search key exact match only is required.
197			*
198			* # <- start \| Check mid and move start or end if it doesn't match
199			* # \|
200			* # \| Since an exact match is wanted we can set end=mid-1
201			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
202			* # \|
203			* # \| Eventually either end=start or end=start+1 and one of
204			* # <- end \| start or end is the wanted one.
205			*/
206
207	amb	262	if(end<start) /* There are no ways */
208			return(NO_WAY);
209			else if(id<waysx->idata[start]) /* Check key is not before start */
210			return(NO_WAY);
211			else if(id>waysx->idata[end]) /* Check key is not after end */
212			return(NO_WAY);
213	amb	203	else
214			{
215			do
216			{
217	amb	262	mid=(start+end)/2; /* Choose mid point */
218	amb	203
219	amb	262	if(waysx->idata[mid]<id) /* Mid point is too low */
220	amb	203	start=mid+1;
221	amb	262	else if(waysx->idata[mid]>id) /* Mid point is too high */
222	amb	203	end=mid-1;
223	amb	262	else /* Mid point is correct */
224			return(mid);
225	amb	203	}
226			while((end-start)>1);
227
228	amb	262	if(waysx->idata[start]==id) /* Start is correct */
229			return(start);
230	amb	203
231	amb	262	if(waysx->idata[end]==id) /* End is correct */
232			return(end);
233	amb	203	}
234
235	amb	262	return(NO_WAY);
236	amb	203	}
237
238
239			/*++++++++++++++++++++++++++++++++++++++
240	amb	262	Lookup a particular way.
241	amb	110
242	amb	262	WayX *LookupWayX Returns a pointer to the extended way with the specified id.
243	amb	110
244			WaysX* waysx The set of ways to process.
245
246	amb	262	index_t index The way index to look for.
247	amb	203
248	amb	262	int position The position in the cache to use.
249	amb	110	++++++++++++++++++++++++++++++++++++++*/
250
251	amb	262	WayX LookupWayX(WaysX waysx,index_t index,int position)
252	amb	110	{
253	amb	262	assert(index!=NO_WAY); /* Must be a valid way */
254	amb	216
255	amb	262	if(option_slim)
256			{
257			SeekFile(waysx->fd,index*sizeof(WayX));
258	amb	110
259	amb	262	ReadFile(waysx->fd,&waysx->cached[position-1],sizeof(WayX));
260
261			return(&waysx->cached[position-1]);
262			}
263			else
264	amb	110	{
265	amb	262	return(&waysx->xdata[index]);
266			}
267			}
268	amb	110
269	amb	243
270	amb	262	/*++++++++++++++++++++++++++++++++++++++
271			Append a way to a way list.
272	amb	203
273	amb	262	void AppendWay Returns the newly appended way.
274	amb	243
275	amb	262	WaysX* waysx The set of ways to process.
276	amb	110
277	amb	262	way_t id The ID of the way.
278	amb	110
279	amb	262	Way *way The way data itself.
280	amb	110
281	amb	262	const char *name The name or reference of the way.
282			++++++++++++++++++++++++++++++++++++++*/
283	amb	110
284	amb	262	void AppendWay(WaysX* waysx,way_t id,Way way,const char name)
285			{
286			WayX wayx;
287	amb	110
288	amb	262	assert(!waysx->idata); /* Must not have idata filled in => unsorted */
289
290			wayx.id=id;
291			wayx.way=*way;
292			wayx.name=waysx->nlength;
293
294			WriteFile(waysx->fd,&wayx,sizeof(WayX));
295
296			waysx->xnumber++;
297
298			WriteFile(waysx->nfd,name,strlen(name)+1);
299
300			waysx->nlength+=strlen(name)+1;
301	amb	110	}
302
303
304			/*++++++++++++++++++++++++++++++++++++++
305	amb	224	Sort the list of ways.
306	amb	110
307			WaysX* waysx The set of ways to process.
308			++++++++++++++++++++++++++++++++++++++*/
309
310			void SortWayList(WaysX* waysx)
311			{
312	amb	262	int fd;
313	amb	110
314	amb	266	/* Check the start conditions */
315
316	amb	243	assert(!waysx->idata); /* Must not have idata filled in => unsorted */
317	amb	110
318	amb	266	/* Print the start message */
319
320	amb	227	printf("Sorting Ways");
321			fflush(stdout);
322	amb	110
323	amb	272	/* Close the files and re-open them (finished appending) */
324	amb	203
325	amb	262	CloseFile(waysx->fd);
326			waysx->fd=ReOpenFile(waysx->filename);
327	amb	216
328	amb	262	CloseFile(waysx->nfd);
329			waysx->nfd=ReOpenFile(waysx->nfilename);
330
331	amb	272	DeleteFile(waysx->filename);
332	amb	262
333	amb	272	fd=OpenFile(waysx->filename);
334
335			/* Allocate the array of indexes */
336
337	amb	262	waysx->idata=(way_t)malloc(waysx->xnumbersizeof(way_t));
338
339	amb	243	assert(waysx->idata); /* Check malloc() worked */
340
341	amb	266	/* Sort the way indexes and remove duplicates */
342	amb	203
343	amb	272	sortwaysx=waysx;
344	amb	215
345	amb	272	filesort(waysx->fd,fd,sizeof(WayX),SORT_RAMSIZE,(int ()(const void,const void))sort_by_id,(int ()(void*,index_t))index_by_id);
346	amb	215
347	amb	262	/* Close the files and re-open them */
348
349			CloseFile(waysx->fd);
350			CloseFile(fd);
351
352			waysx->fd=ReOpenFile(waysx->filename);
353
354	amb	266	/* Print the final message */
355
356	amb	272	printf("\rSorted Ways: Ways=%d Duplicates=%d\n",waysx->xnumber,waysx->xnumber-waysx->number);
357	amb	227	fflush(stdout);
358	amb	224	}
359
360
361			/*++++++++++++++++++++++++++++++++++++++
362	amb	262	Sort the ways into id order.
363	amb	224
364	amb	262	int sort_by_id Returns the comparison of the id fields.
365
366	amb	272	WayX *a The first extended way.
367	amb	262
368	amb	272	WayX *b The second extended way.
369	amb	262	++++++++++++++++++++++++++++++++++++++*/
370
371	amb	272	static int sort_by_id(WayX a,WayX b)
372	amb	262	{
373	amb	272	way_t a_id=a->id;
374			way_t b_id=b->id;
375	amb	262
376			if(a_id<b_id)
377			return(-1);
378			else if(a_id>b_id)
379			return(1);
380			else
381			return(0);
382			}
383
384
385			/*++++++++++++++++++++++++++++++++++++++
386	amb	272	Index the ways after sorting.
387
388			index_by_id Return 1 if the value is to be kept, otherwise zero.
389
390			WayX *wayx The extended way.
391
392			index_t index The index of this way in the total.
393			++++++++++++++++++++++++++++++++++++++*/
394
395			static int index_by_id(WayX *wayx,index_t index)
396			{
397			if(index==0 \|\| sortwaysx->idata[index-1]!=wayx->id)
398			{
399			sortwaysx->idata[index]=wayx->id;
400
401			sortwaysx->number++;
402
403			return(1);
404			}
405
406			return(0);
407			}
408
409
410			/*++++++++++++++++++++++++++++++++++++++
411	amb	262	Compact the list of way names.
412
413	amb	224	WaysX* waysx The set of ways to process.
414			++++++++++++++++++++++++++++++++++++++*/
415
416	amb	262	void CompactWayNames(WaysX* waysx)
417	amb	224	{
418	amb	266	index_t i,j,*offsets;
419	amb	262	char **cnames;
420			WayX wayx;
421	amb	266	int duplicate=0;
422	amb	262	int fd,nfd;
423	amb	224
424	amb	266	/* Print the start message for sorting names */
425	amb	224
426	amb	262	printf("Sorting Way names");
427	amb	227	fflush(stdout);
428	amb	224
429	amb	266	/* Get the uncompacted name data and create list for compacted */
430
431	amb	275	waysx->xdata=MapFile(waysx->filename);
432	amb	110
433	amb	262	waysx->names=MapFile(waysx->nfilename);
434	amb	110
435	amb	280	cnames=(char*)malloc(waysx->numbersizeof(char*));
436	amb	243
437	amb	262	assert(cnames); /* Check malloc() worked */
438
439	amb	266	/* Create the index of names, sort it and remove duplicates */
440
441	amb	280	for(i=0;i<waysx->number;i++)
442	amb	262	cnames[i]=&waysx->names[waysx->xdata[i].name];
443
444	amb	280	heapsort((void*)cnames,waysx->number,(int ()(const void,const void))sort_by_name);
445	amb	216
446	amb	266	j=0;
447	amb	280	for(i=1;i<waysx->number;i++)
448	amb	266	if(strcmp(cnames[i],cnames[j]))
449			cnames[++j]=cnames[i];
450			else
451			duplicate++;
452	amb	203
453	amb	266	waysx->nnumber=++j;
454	amb	262
455	amb	266	/* Sort the on-disk image */
456	amb	243
457	amb	262	DeleteFile(waysx->nfilename);
458	amb	110
459	amb	262	nfd=OpenFile(waysx->nfilename);
460	amb	203
461	amb	262	offsets=(index_t)malloc(waysx->nnumbersizeof(index_t));
462	amb	216
463	amb	262	assert(offsets); /* Check malloc() worked */
464	amb	216
465	amb	262	waysx->nlength=0;
466	amb	216
467	amb	262	for(i=0;i<waysx->nnumber;i++)
468			{
469			offsets[i]=waysx->nlength;
470			waysx->nlength+=strlen(cnames[i])+1;
471			WriteFile(nfd,cnames[i],strlen(cnames[i])+1);
472			}
473	amb	216
474	amb	262	CloseFile(waysx->nfd);
475			CloseFile(nfd);
476	amb	243
477	amb	262	waysx->nfd=ReOpenFile(waysx->nfilename);
478	amb	243
479	amb	266	/* Print the final message for sorting names */
480
481			printf("\rSorted Way names: Names=%d Duplicate=%d\n",waysx->number,duplicate);
482	amb	262	fflush(stdout);
483	amb	216
484	amb	266	/* Print the start message for compacting names */
485	amb	216
486	amb	262	printf("Compacting Way names");
487			fflush(stdout);
488	amb	216
489	amb	262	/* Update the on-disk image */
490	amb	224
491	amb	262	DeleteFile(waysx->filename);
492
493			fd=OpenFile(waysx->filename);
494			SeekFile(waysx->fd,0);
495
496			while(!ReadFile(waysx->fd,&wayx,sizeof(WayX)))
497			{
498			wayx.way.name=offsets[index_way_name(cnames,waysx->nnumber,&waysx->names[wayx.name])];
499
500			WriteFile(fd,&wayx,sizeof(WayX));
501	amb	110	}
502	amb	132
503	amb	262	CloseFile(waysx->fd);
504			CloseFile(fd);
505
506			waysx->xdata=UnmapFile(waysx->filename);
507			waysx->names=UnmapFile(waysx->nfilename);
508
509			waysx->fd=ReOpenFile(waysx->filename);
510
511	amb	266	/* Print the final message for compacting names */
512
513			printf("\rCompacted Way names: Names=%d Unique=%d\n",waysx->number,waysx->nnumber);
514	amb	224	fflush(stdout);
515
516	amb	262	free(cnames);
517			free(offsets);
518	amb	110	}
519
520
521			/*++++++++++++++++++++++++++++++++++++++
522	amb	262	Sort the way names.
523	amb	110
524	amb	262	int sort_by_name Returns the comparison of the name fields.
525	amb	110
526	amb	276	char *a The first extended Way.
527	amb	110
528	amb	276	char *b The second extended Way.
529	amb	110	++++++++++++++++++++++++++++++++++++++*/
530
531	amb	276	static int sort_by_name(char a,char b)
532	amb	110	{
533	amb	276	if(a==NULL)
534	amb	262	return(1);
535	amb	276	else if(b==NULL)
536	amb	203	return(-1);
537			else
538	amb	276	return(strcmp(a,b));
539	amb	203	}
540
541
542			/*++++++++++++++++++++++++++++++++++++++
543	amb	262	Find a particular name within the sorted list of names.
544
545			index_t index_way_name Returns the index of the name within the list.
546
547			char **names The set of names to search.
548
549			int number The number of names.
550
551			char *name The name to look for.
552			++++++++++++++++++++++++++++++++++++++*/
553
554			static index_t index_way_name(char** names,int number,char *name)
555			{
556			int start=0;
557			int end=number-1;
558			int mid;
559
560			/* Binary search - search key exact match only is required.
561			*
562			* # <- start \| Check mid and move start or end if it doesn't match
563			* # \|
564			* # \| Since an exact match is wanted we can set end=mid-1
565			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
566			* # \|
567			* # \| Eventually either end=start or end=start+1 and one of
568			* # <- end \| start or end is the wanted one.
569			*/
570
571			do
572			{
573			mid=(start+end)/2; /* Choose mid point */
574
575			if(strcmp(name,names[mid])>0) /* Mid point is too low */
576			start=mid+1;
577			else if(strcmp(name,names[mid])<0) /* Mid point is too high */
578			end=mid-1;
579			else /* Mid point is correct */
580			return(mid);
581			}
582			while((end-start)>1);
583
584			if(strcmp(name,names[start])==0) /* Start is correct */
585			return(start);
586
587			if(strcmp(name,names[end])==0) /* End is correct */
588			return(end);
589
590			assert(0);
591
592			return(NO_WAY);
593			}
594
595
596			/*++++++++++++++++++++++++++++++++++++++
597			Compact the list of way properties.
598
599			WaysX* waysx The set of ways to process.
600			++++++++++++++++++++++++++++++++++++++*/
601
602			void CompactWayProperties(WaysX* waysx)
603			{
604	amb	266	index_t i,j;
605	amb	262	WayX wayx;
606			Way **cdata;
607	amb	266	int duplicate=0;
608	amb	262	int fd;
609
610	amb	266	/* Print the start message for sorting properties */
611	amb	262
612			printf("Sorting Ways by properties");
613			fflush(stdout);
614
615	amb	266	/* Get the uncompacted data and create list for compacted */
616
617	amb	275	waysx->xdata=MapFile(waysx->filename);
618	amb	262
619	amb	280	cdata=(Way*)malloc(waysx->numbersizeof(Way*));
620	amb	262
621			assert(cdata); /* Check malloc() worked */
622
623	amb	280	for(i=0;i<waysx->number;i++)
624	amb	262	cdata[i]=&waysx->xdata[i].way;
625
626	amb	266	/* Create the index of names, sort it and remove duplicates */
627	amb	262
628	amb	280	heapsort((void*)cdata,waysx->number,(int ()(const void,const void))sort_by_name_and_properties);
629	amb	262
630	amb	266	j=0;
631	amb	280	for(i=1;i<waysx->number;i++)
632	amb	266	if(cdata[i-1]->name!=cdata[i]->name \|\| WaysCompare(cdata[i-1],cdata[i]))
633			cdata[++j]=cdata[i];
634			else
635			duplicate++;
636	amb	262
637	amb	266	waysx->cnumber=++j;
638	amb	262
639	amb	266	/* Print the final message for sorting properties */
640	amb	262
641	amb	266	printf("\rSorted Ways by properties: Properties=%d Duplicate=%d\n",waysx->number,duplicate);
642	amb	262	fflush(stdout);
643
644	amb	266	/* Print the start message for compacting properties */
645	amb	262
646			printf("Compacting Way properties");
647			fflush(stdout);
648
649			/* Update the on-disk image */
650
651			DeleteFile(waysx->filename);
652
653			fd=OpenFile(waysx->filename);
654			SeekFile(waysx->fd,0);
655
656			while(!ReadFile(waysx->fd,&wayx,sizeof(WayX)))
657			{
658	amb	280	wayx.id=index_way(cdata,waysx->cnumber,&wayx.way);
659	amb	262
660			WriteFile(fd,&wayx,sizeof(WayX));
661			}
662
663			CloseFile(waysx->fd);
664			CloseFile(fd);
665
666			waysx->fd=ReOpenFile(waysx->filename);
667
668			waysx->xdata=UnmapFile(waysx->filename);
669
670	amb	266	/* Print the final message for compacting properties */
671
672			printf("\rCompacted Way properties: Properties=%d Unique=%d\n",waysx->number,waysx->cnumber);
673	amb	262	fflush(stdout);
674
675			free(cdata);
676			}
677
678
679			/*++++++++++++++++++++++++++++++++++++++
680	amb	203	Sort the ways into name and properties order.
681
682			int sort_by_name_and_properties Returns the comparison of the name and properties fields.
683
684	amb	276	Way *a The first Way.
685	amb	203
686	amb	276	Way *b The second Way.
687	amb	203	++++++++++++++++++++++++++++++++++++++*/
688
689	amb	276	static int sort_by_name_and_properties(Way a,Way b)
690	amb	203	{
691	amb	276	if(a==NULL)
692	amb	262	return(1);
693	amb	276	else if(b==NULL)
694	amb	262	return(-1);
695	amb	203	else
696			{
697	amb	276	index_t a_name=a->name;
698			index_t b_name=b->name;
699	amb	203
700	amb	262	if(a_name<b_name)
701			return(-1);
702			else if(a_name>b_name)
703			return(1);
704			else
705	amb	276	return(WaysCompare(a,b));
706	amb	203	}
707	amb	110	}
708	amb	216
709
710			/*++++++++++++++++++++++++++++++++++++++
711	amb	262	Find a particular Way within the sorted list of ways.
712	amb	216
713	amb	262	index_t index_way Returns the index of the Way within the list.
714	amb	216
715	amb	262	Way **data The set of Ways to search.
716	amb	216
717	amb	262	int number The number of Ways.
718
719			Way *way The name to look for.
720	amb	216	++++++++++++++++++++++++++++++++++++++*/
721
722	amb	262	static index_t index_way(Way** data,int number,Way *way)
723	amb	216	{
724	amb	262	int start=0;
725			int end=number-1;
726			int mid;
727	amb	216
728	amb	262	/* Binary search - search key exact match only is required.
729			*
730			* # <- start \| Check mid and move start or end if it doesn't match
731			* # \|
732			* # \| Since an exact match is wanted we can set end=mid-1
733			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
734			* # \|
735			* # \| Eventually either end=start or end=start+1 and one of
736			* # <- end \| start or end is the wanted one.
737			*/
738	amb	216
739	amb	262	do
740			{
741	amb	280	mid=(start+end)/2; /* Choose mid point */
742	amb	216
743	amb	280	if(way->name>data[mid]->name) /* Mid point is too low */
744	amb	262	start=mid+1;
745	amb	280	else if(way->name<data[mid]->name) /* Mid point is too high */
746	amb	262	end=mid-1;
747			else if(WaysCompare(way,data[mid])>0) /* Mid point is too low */
748			start=mid+1;
749			else if(WaysCompare(way,data[mid])<0) /* Mid point is too high */
750			end=mid-1;
751	amb	280	else /* Mid point is correct */
752	amb	262	return(mid);
753			}
754			while((end-start)>1);
755
756	amb	280	if(way->name==data[start]->name && !WaysCompare(way,data[start])) /* Start is correct */
757	amb	262	return(start);
758
759	amb	280	if(way->name==data[end]->name && !WaysCompare(way,data[end])) /* End is correct */
760	amb	262	return(end);
761
762			assert(0);
763
764			return(NO_WAY);
765	amb	216	}