trunk/src/waysx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.28 2009-10-12 17:54:18 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);
}


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


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


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


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