trunk/src/waysx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.25 2009-10-09 18:47:40 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 *tmpdirname;

/* 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(tmpdirname)+24);
 sprintf(waysx->filename,"%s/ways.%p.tmp",tmpdirname,waysx);

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

 waysx->nfilename=(char*)malloc(strlen(tmpdirname)+24);
 sprintf(waysx->nfilename,"%s/waynames.%p.tmp",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);

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

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

 DeleteFile(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;
}


/*+ A temporary file-local variable for use by the sort functions. +*/
static WaysX *sortwaysx;


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