trunk/src/waysx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.21 2009-09-23 18:36:58 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"


/* Variables */

extern int option_slim;
extern char *tmpdirname;

/* Functions */

static int sort_by_id(way_t *a,way_t *b);
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);

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

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

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

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

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

 ways->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].cid*sizeof(Way));
    WriteFile(fd,&waysx->xdata[i].way,sizeof(Way));

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

 if(option_slim)
    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)
{
 WayX wayx;
 index_t i,j;
 int duplicate=0;
 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 */

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

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

 /* Allocate the array of pointers and fill them */

 waysx->idata=(way_t*)malloc(waysx->xnumber*sizeof(way_t));

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

 waysx->number=0;

 while(!ReadFile(waysx->fd,&wayx,sizeof(WayX)))
   {
    waysx->idata[waysx->number]=wayx.id;
    waysx->number++;
   }

 /* Sort the way indexes and remove duplicates */

 qsort(waysx->idata,waysx->number,sizeof(way_t),(int (*)(const void*,const void*))sort_by_id);

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

 waysx->number=++j;

 /* Sort the on-disk image */

 DeleteFile(waysx->filename);

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

 while(!ReadFile(waysx->fd,&wayx,sizeof(WayX)))
   {
    index_t index=IndexWayX(waysx,wayx.id);

    if(index!=NO_WAY)
      {
       SeekFile(fd,index*sizeof(WayX));
       WriteFile(fd,&wayx,sizeof(WayX));
      }
   }

 /* Close the files and re-open them */

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

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

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

 /* Print the final message */

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


/*++++++++++++++++++++++++++++++++++++++
  Sort the ways into id order.

  int sort_by_id Returns the comparison of the id fields.

  way_t *a The first way id.

  way_t *b The second way id.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_id(way_t *a,way_t *b)
{
 node_t a_id=*a;
 node_t b_id=*b;

 if(a_id<b_id)
    return(-1);
 else if(a_id>b_id)
    return(1);
 else
    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 */

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

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

 waysx->nnumber=waysx->number;

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

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

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

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

 qsort(cnames,waysx->nnumber,sizeof(char*),(int (*)(const void*,const void*))sort_by_name);

 j=0;
 for(i=1;i<waysx->nnumber;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);

 if(!option_slim)
    waysx->xdata=MapFile(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 */

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

 waysx->cnumber=waysx->number;

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

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

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

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

 qsort(cdata,waysx->cnumber,sizeof(Way*),(int (*)(const void*,const void*))sort_by_name_and_properties);

 j=0;
 for(i=1;i<waysx->cnumber;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.cid=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);

 if(!option_slim)
    waysx->xdata=MapFile(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
      {
       Way *a_way=*a;
       Way *b_way=*b;

       return(WaysCompare(a_way,b_way));
      }
   }
}


/*++++++++++++++++++++++++++++++++++++++
  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])==0)   /* Start is correct */
    return(start);

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

 assert(0);

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