trunk/src/waysx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.24 2009-10-07 18:17:27 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].cid*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);

 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];

 heapsort((void**)cnames,waysx->nnumber,(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);

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

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

 heapsort((void**)cdata,waysx->cnumber,(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);

 /* 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])==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	276	$Header: /home/amb/CVS/routino/src/waysx.c,v 1.24 2009-10-07 18:17:27 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	262	SeekFile(fd,sizeof(Ways)+waysx->xdata[i].cid*sizeof(Way));
147			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	262	waysx->nnumber=waysx->number;
438	amb	243
439	amb	262	cnames=(char*)malloc(waysx->nnumbersizeof(char*));
440	amb	110
441	amb	262	assert(cnames); /* Check malloc() worked */
442
443	amb	266	/* Create the index of names, sort it and remove duplicates */
444
445	amb	262	for(i=0;i<waysx->nnumber;i++)
446			cnames[i]=&waysx->names[waysx->xdata[i].name];
447
448	amb	276	heapsort((void*)cnames,waysx->nnumber,(int ()(const void,const void))sort_by_name);
449	amb	216
450	amb	266	j=0;
451			for(i=1;i<waysx->nnumber;i++)
452			if(strcmp(cnames[i],cnames[j]))
453			cnames[++j]=cnames[i];
454			else
455			duplicate++;
456	amb	203
457	amb	266	waysx->nnumber=++j;
458	amb	262
459	amb	266	/* Sort the on-disk image */
460	amb	243
461	amb	262	DeleteFile(waysx->nfilename);
462	amb	110
463	amb	262	nfd=OpenFile(waysx->nfilename);
464	amb	203
465	amb	262	offsets=(index_t)malloc(waysx->nnumbersizeof(index_t));
466	amb	216
467	amb	262	assert(offsets); /* Check malloc() worked */
468	amb	216
469	amb	262	waysx->nlength=0;
470	amb	216
471	amb	262	for(i=0;i<waysx->nnumber;i++)
472			{
473			offsets[i]=waysx->nlength;
474			waysx->nlength+=strlen(cnames[i])+1;
475			WriteFile(nfd,cnames[i],strlen(cnames[i])+1);
476			}
477	amb	216
478	amb	262	CloseFile(waysx->nfd);
479			CloseFile(nfd);
480	amb	243
481	amb	262	waysx->nfd=ReOpenFile(waysx->nfilename);
482	amb	243
483	amb	266	/* Print the final message for sorting names */
484
485			printf("\rSorted Way names: Names=%d Duplicate=%d\n",waysx->number,duplicate);
486	amb	262	fflush(stdout);
487	amb	216
488	amb	266	/* Print the start message for compacting names */
489	amb	216
490	amb	262	printf("Compacting Way names");
491			fflush(stdout);
492	amb	216
493	amb	262	/* Update the on-disk image */
494	amb	224
495	amb	262	DeleteFile(waysx->filename);
496
497			fd=OpenFile(waysx->filename);
498			SeekFile(waysx->fd,0);
499
500			while(!ReadFile(waysx->fd,&wayx,sizeof(WayX)))
501			{
502			wayx.way.name=offsets[index_way_name(cnames,waysx->nnumber,&waysx->names[wayx.name])];
503
504			WriteFile(fd,&wayx,sizeof(WayX));
505	amb	110	}
506	amb	132
507	amb	262	CloseFile(waysx->fd);
508			CloseFile(fd);
509
510			waysx->xdata=UnmapFile(waysx->filename);
511			waysx->names=UnmapFile(waysx->nfilename);
512
513			waysx->fd=ReOpenFile(waysx->filename);
514
515	amb	266	/* Print the final message for compacting names */
516
517			printf("\rCompacted Way names: Names=%d Unique=%d\n",waysx->number,waysx->nnumber);
518	amb	224	fflush(stdout);
519
520	amb	262	free(cnames);
521			free(offsets);
522	amb	110	}
523
524
525			/*++++++++++++++++++++++++++++++++++++++
526	amb	262	Sort the way names.
527	amb	110
528	amb	262	int sort_by_name Returns the comparison of the name fields.
529	amb	110
530	amb	276	char *a The first extended Way.
531	amb	110
532	amb	276	char *b The second extended Way.
533	amb	110	++++++++++++++++++++++++++++++++++++++*/
534
535	amb	276	static int sort_by_name(char a,char b)
536	amb	110	{
537	amb	276	if(a==NULL)
538	amb	262	return(1);
539	amb	276	else if(b==NULL)
540	amb	203	return(-1);
541			else
542	amb	276	return(strcmp(a,b));
543	amb	203	}
544
545
546			/*++++++++++++++++++++++++++++++++++++++
547	amb	262	Find a particular name within the sorted list of names.
548
549			index_t index_way_name Returns the index of the name within the list.
550
551			char **names The set of names to search.
552
553			int number The number of names.
554
555			char *name The name to look for.
556			++++++++++++++++++++++++++++++++++++++*/
557
558			static index_t index_way_name(char** names,int number,char *name)
559			{
560			int start=0;
561			int end=number-1;
562			int mid;
563
564			/* Binary search - search key exact match only is required.
565			*
566			* # <- start \| Check mid and move start or end if it doesn't match
567			* # \|
568			* # \| Since an exact match is wanted we can set end=mid-1
569			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
570			* # \|
571			* # \| Eventually either end=start or end=start+1 and one of
572			* # <- end \| start or end is the wanted one.
573			*/
574
575			do
576			{
577			mid=(start+end)/2; /* Choose mid point */
578
579			if(strcmp(name,names[mid])>0) /* Mid point is too low */
580			start=mid+1;
581			else if(strcmp(name,names[mid])<0) /* Mid point is too high */
582			end=mid-1;
583			else /* Mid point is correct */
584			return(mid);
585			}
586			while((end-start)>1);
587
588			if(strcmp(name,names[start])==0) /* Start is correct */
589			return(start);
590
591			if(strcmp(name,names[end])==0) /* End is correct */
592			return(end);
593
594			assert(0);
595
596			return(NO_WAY);
597			}
598
599
600			/*++++++++++++++++++++++++++++++++++++++
601			Compact the list of way properties.
602
603			WaysX* waysx The set of ways to process.
604			++++++++++++++++++++++++++++++++++++++*/
605
606			void CompactWayProperties(WaysX* waysx)
607			{
608	amb	266	index_t i,j;
609	amb	262	WayX wayx;
610			Way **cdata;
611	amb	266	int duplicate=0;
612	amb	262	int fd;
613
614	amb	266	/* Print the start message for sorting properties */
615	amb	262
616			printf("Sorting Ways by properties");
617			fflush(stdout);
618
619	amb	266	/* Get the uncompacted data and create list for compacted */
620
621	amb	275	waysx->xdata=MapFile(waysx->filename);
622	amb	262
623			waysx->cnumber=waysx->number;
624
625			cdata=(Way*)malloc(waysx->cnumbersizeof(Way*));
626
627			assert(cdata); /* Check malloc() worked */
628
629			for(i=0;i<waysx->cnumber;i++)
630			cdata[i]=&waysx->xdata[i].way;
631
632	amb	266	/* Create the index of names, sort it and remove duplicates */
633	amb	262
634	amb	276	heapsort((void*)cdata,waysx->cnumber,(int ()(const void,const void))sort_by_name_and_properties);
635	amb	262
636	amb	266	j=0;
637			for(i=1;i<waysx->cnumber;i++)
638			if(cdata[i-1]->name!=cdata[i]->name \|\| WaysCompare(cdata[i-1],cdata[i]))
639			cdata[++j]=cdata[i];
640			else
641			duplicate++;
642	amb	262
643	amb	266	waysx->cnumber=++j;
644	amb	262
645	amb	266	/* Print the final message for sorting properties */
646	amb	262
647	amb	266	printf("\rSorted Ways by properties: Properties=%d Duplicate=%d\n",waysx->number,duplicate);
648	amb	262	fflush(stdout);
649
650	amb	266	/* Print the start message for compacting properties */
651	amb	262
652			printf("Compacting Way properties");
653			fflush(stdout);
654
655			/* Update the on-disk image */
656
657			DeleteFile(waysx->filename);
658
659			fd=OpenFile(waysx->filename);
660			SeekFile(waysx->fd,0);
661
662			while(!ReadFile(waysx->fd,&wayx,sizeof(WayX)))
663			{
664			wayx.cid=index_way(cdata,waysx->cnumber,&wayx.way);
665
666			WriteFile(fd,&wayx,sizeof(WayX));
667			}
668
669			CloseFile(waysx->fd);
670			CloseFile(fd);
671
672			waysx->fd=ReOpenFile(waysx->filename);
673
674			waysx->xdata=UnmapFile(waysx->filename);
675
676	amb	266	/* Print the final message for compacting properties */
677
678			printf("\rCompacted Way properties: Properties=%d Unique=%d\n",waysx->number,waysx->cnumber);
679	amb	262	fflush(stdout);
680
681			free(cdata);
682			}
683
684
685			/*++++++++++++++++++++++++++++++++++++++
686	amb	203	Sort the ways into name and properties order.
687
688			int sort_by_name_and_properties Returns the comparison of the name and properties fields.
689
690	amb	276	Way *a The first Way.
691	amb	203
692	amb	276	Way *b The second Way.
693	amb	203	++++++++++++++++++++++++++++++++++++++*/
694
695	amb	276	static int sort_by_name_and_properties(Way a,Way b)
696	amb	203	{
697	amb	276	if(a==NULL)
698	amb	262	return(1);
699	amb	276	else if(b==NULL)
700	amb	262	return(-1);
701	amb	203	else
702			{
703	amb	276	index_t a_name=a->name;
704			index_t b_name=b->name;
705	amb	203
706	amb	262	if(a_name<b_name)
707			return(-1);
708			else if(a_name>b_name)
709			return(1);
710			else
711	amb	276	return(WaysCompare(a,b));
712	amb	203	}
713	amb	110	}
714	amb	216
715
716			/*++++++++++++++++++++++++++++++++++++++
717	amb	262	Find a particular Way within the sorted list of ways.
718	amb	216
719	amb	262	index_t index_way Returns the index of the Way within the list.
720	amb	216
721	amb	262	Way **data The set of Ways to search.
722	amb	216
723	amb	262	int number The number of Ways.
724
725			Way *way The name to look for.
726	amb	216	++++++++++++++++++++++++++++++++++++++*/
727
728	amb	262	static index_t index_way(Way** data,int number,Way *way)
729	amb	216	{
730	amb	262	int start=0;
731			int end=number-1;
732			int mid;
733	amb	216
734	amb	262	/* Binary search - search key exact match only is required.
735			*
736			* # <- start \| Check mid and move start or end if it doesn't match
737			* # \|
738			* # \| Since an exact match is wanted we can set end=mid-1
739			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
740			* # \|
741			* # \| Eventually either end=start or end=start+1 and one of
742			* # <- end \| start or end is the wanted one.
743			*/
744	amb	216
745	amb	262	do
746			{
747			mid=(start+end)/2; /* Choose mid point */
748	amb	216
749	amb	262	if(way->name>data[mid]->name) /* Mid point is too low */
750			start=mid+1;
751			else if(way->name<data[mid]->name) /* Mid point is too high */
752			end=mid-1;
753			else if(WaysCompare(way,data[mid])>0) /* Mid point is too low */
754			start=mid+1;
755			else if(WaysCompare(way,data[mid])<0) /* Mid point is too high */
756			end=mid-1;
757			else /* Mid point is correct */
758			return(mid);
759			}
760			while((end-start)>1);
761
762			if(way->name==data[start]->name && WaysCompare(way,data[start])==0) /* Start is correct */
763			return(start);
764
765			if(way->name==data[end]->name && WaysCompare(way,data[end])==0) /* End is correct */
766			return(end);
767
768			assert(0);
769
770			return(NO_WAY);
771	amb	216	}