trunk/src/waysx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.19 2009-08-19 18:02:08 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 */

/*+ The array size increment for WaysX (UK is ~1.3M raw ways, this is ~79 increments). +*/
#define INCREMENT_WAYSX (16*1024)

/*+ The array size increment for Ways (UK is ~240k compacted ways, this is ~59 increments). +*/
#define INCREMENT_WAYS   (4*1024)

/*+ The array size increment for names (UK is ~2.9MBytes of compacted names, this is ~22 increments). +*/
#define INCREMENT_NAMES (128*1024)


/* Functions */

static int sort_by_id(WayX **a,WayX **b);
static int sort_by_name_and_properties(WayX **a,WayX **b);


/*++++++++++++++++++++++++++++++++++++++
  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->row=-1;
 waysx->wrow=-1;

 return(waysx);
}


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

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

void FreeWayList(WaysX *waysx)
{
 if(waysx->xdata)
   {
    int i;
    for(i=0;i<(waysx->row*INCREMENT_WAYSX+waysx->col);i++)
       free(waysx->xdata[i/INCREMENT_WAYSX][i%INCREMENT_WAYSX].name);
    for(i=0;i<=waysx->row;i++)
       free(waysx->xdata[i]);
    free(waysx->xdata);
   }

 if(waysx->wxdata)
   {
    int i;
    for(i=0;i<=waysx->row;i++)
       free(waysx->wxdata[i]);
    free(waysx->wxdata);
   }

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

 if(waysx->wdata)
   {
    int i;
    for(i=0;i<=waysx->wrow;i++)
       free(waysx->wdata[i]);
    free(waysx->wdata);
   }

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

 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;

 assert(waysx->wdata);        /* Must have wdata filled in => compacted */
 assert(waysx->names);        /* Must have names filled in => compacted */

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

 /* 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->wrow*INCREMENT_WAYS+waysx->wcol;
 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<ways->number;i++)
   {
    WriteFile(fd,&waysx->wdata[i/INCREMENT_WAYS][i%INCREMENT_WAYS],sizeof(Way));

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

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

 WriteFile(fd,waysx->names,waysx->length);

 CloseFile(fd);

 /* Free the fake Ways */

 free(ways);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a particular way.

  WayX *FindWayX Returns the extended way with the specified id.

  WaysX* waysx The set of ways to process.

  way_t id The way id to look for.
  ++++++++++++++++++++++++++++++++++++++*/

WayX *FindWayX(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(NULL);
 else if(id<waysx->idata[start]->id) /* Check key is not before start */
    return(NULL);
 else if(id>waysx->idata[end]->id)   /* Check key is not after end */
    return(NULL);
 else
   {
    do
      {
       mid=(start+end)/2;                /* Choose mid point */

       if(waysx->idata[mid]->id<id)      /* Mid point is too low */
          start=mid+1;
       else if(waysx->idata[mid]->id>id) /* Mid point is too high */
          end=mid-1;
       else                              /* Mid point is correct */
          return(waysx->idata[mid]);
      }
    while((end-start)>1);

    if(waysx->idata[start]->id==id)      /* Start is correct */
       return(waysx->idata[start]);

    if(waysx->idata[end]->id==id)        /* End is correct */
       return(waysx->idata[end]);
   }

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Append a way to a way list.

  Way *AppendWay Returns the newly appended way.

  WaysX* waysx The set of ways to process.

  way_t id The ID of the way.

  const char *name The name or reference of the way.
  ++++++++++++++++++++++++++++++++++++++*/

Way *AppendWay(WaysX* waysx,way_t id,const char *name)
{
 assert(!waysx->idata);       /* Must not have idata filled in => unsorted */

 /* Check that the arrays have enough space. */

 if(waysx->row==-1 || waysx->col==INCREMENT_WAYSX)
   {
    waysx->row++;
    waysx->col=0;

    if((waysx->row%16)==0)
      {
       waysx->xdata=(WayX**)realloc((void*)waysx->xdata,(waysx->row+16)*sizeof(WayX*));
       waysx->wxdata=(Way**)realloc((void*)waysx->wxdata,(waysx->row+16)*sizeof(Way*));

       assert(waysx->xdata); /* Check realloc() worked */
       assert(waysx->wxdata); /* Check realloc() worked */
      }

    waysx->xdata[waysx->row]=(WayX*)malloc(INCREMENT_WAYSX*sizeof(WayX));
    waysx->wxdata[waysx->row]=(Way*)malloc(INCREMENT_WAYSX*sizeof(Way));

    assert(waysx->xdata[waysx->row]); /* Check malloc() worked */
    assert(waysx->wxdata[waysx->row]); /* Check malloc() worked */
   }

 /* Insert the way */

 waysx->xdata[waysx->row][waysx->col].id=id;
 waysx->xdata[waysx->row][waysx->col].name=strcpy((char*)malloc(strlen(name)+1),name);
 waysx->xdata[waysx->row][waysx->col].way=&waysx->wxdata[waysx->row][waysx->col];

 memset(&waysx->wxdata[waysx->row][waysx->col],0,sizeof(Way));

 waysx->col++;

 return(&waysx->wxdata[waysx->row][waysx->col-1]);
}


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

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

void SortWayList(WaysX* waysx)
{
 index_t i;
 int duplicate;

 assert(waysx->xdata);          /* Must have xdata filled in => data exists */
 assert(waysx->wxdata);         /* Must have wxdata filled in => data exists */
 assert(!waysx->idata);         /* Must not have idata filled in => unsorted */
 assert(!waysx->ndata);         /* Must not have ndata filled in => unsorted */

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

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

 waysx->idata=(WayX**)malloc((waysx->row*INCREMENT_WAYSX+waysx->col)*sizeof(WayX*));

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

 do
   {
    waysx->number=0;

    for(i=0;i<(waysx->row*INCREMENT_WAYSX+waysx->col);i++)
       if(waysx->xdata[i/INCREMENT_WAYSX][i%INCREMENT_WAYSX].id!=NO_WAY)
         {
          waysx->idata[waysx->number]=&waysx->xdata[i/INCREMENT_WAYSX][i%INCREMENT_WAYSX];
          waysx->number++;
         }

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

    duplicate=0;

    for(i=1;i<waysx->number;i++)
      {
       if(waysx->idata[i]->id==waysx->idata[i-1]->id &&
          waysx->idata[i]->id!=NO_WAY)
         {
          waysx->idata[i-1]->id=NO_WAY;
          duplicate++;
         }
      }

    if(duplicate)
      {
       printf(" - %d duplicates found; trying again.\nSorting Ways",duplicate);
       fflush(stdout);
      }
   }
 while(duplicate);

 /* Sort the ways by name and way properties */

 waysx->ndata=(WayX**)malloc(waysx->number*sizeof(WayX*));

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

 for(i=0;i<waysx->number;i++)
    waysx->ndata[i]=waysx->idata[i];

 qsort(waysx->ndata,waysx->number,sizeof(WayX*),(int (*)(const void*,const void*))sort_by_name_and_properties);

 printf("\rSorted Ways \n");
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Compact the list of ways and reduce the names.

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

void CompactWays(WaysX* waysx)
{
 index_t i;

 assert(waysx->ndata);          /* Must have ndata filled in => sorted */
 assert(waysx->wxdata);         /* Must have wxdata filled in => data exists */
 assert(!waysx->names);         /* Must not have names filled in => uncompacted */
 assert(!waysx->wdata);         /* Must not have wdata filled in => uncompacted */

 printf("\rCompacting Ways: Ways=0 Compacted=0 Names=0 Bytes");
 fflush(stdout);

 /* Allocate the new data for names */

 waysx->names=(char*)malloc(INCREMENT_NAMES*sizeof(char));

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

 /* Setup the offsets for the names in the way array */

 for(i=0;i<waysx->number;i++)
   {
    int copy=0;

    if(i && !strcmp(waysx->ndata[i]->name,waysx->ndata[i-1]->name)) /* Same name */
      {
       waysx->ndata[i]->way->name=waysx->ndata[i-1]->way->name;

       if(!WaysCompare(waysx->ndata[i]->way,waysx->ndata[i-1]->way)) /* Same properties */
          waysx->ndata[i]->way=waysx->ndata[i-1]->way;
       else
          copy=1;
      }
    else                                                          /* Different name */
      {
       if(((waysx->length+strlen(waysx->ndata[i]->name)+1)/INCREMENT_NAMES)>(waysx->length/INCREMENT_NAMES))
         {
          waysx->names=(char*)realloc((void*)waysx->names,(waysx->length/INCREMENT_NAMES+2)*INCREMENT_NAMES*sizeof(char));

          assert(waysx->names); /* Check realloc() worked */
         }

       strcpy(&waysx->names[waysx->length],waysx->ndata[i]->name);

       waysx->ndata[i]->way->name=waysx->length;

       waysx->length+=strlen(waysx->ndata[i]->name)+1;

       copy=1;
      }

    if(copy)
      {
       /* Check that the array has enough space. */

       if(waysx->wrow==-1 || waysx->wcol==INCREMENT_WAYS)
         {
          waysx->wrow++;
          waysx->wcol=0;

          if((waysx->wrow%16)==0)
            {
             waysx->wdata=(Way **)realloc((void*)waysx->wdata,(waysx->wrow+16)*sizeof(Way*));

             assert(waysx->wdata); /* Check realloc() worked */
            }

          waysx->wdata[waysx->wrow]=(Way *)malloc(INCREMENT_WAYSX*sizeof(Way));

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

       waysx->wdata[waysx->wrow][waysx->wcol]=*waysx->ndata[i]->way;

       waysx->ndata[i]->way=&waysx->wdata[waysx->wrow][waysx->wcol];

       waysx->wcol++;
      }

    if(!((i+1)%10000))
      {
       printf("\rCompacting Ways: Ways=%d Compacted=%d Names=%d Bytes",i+1,waysx->wrow*INCREMENT_WAYS+waysx->wcol,waysx->length);
       fflush(stdout);
      }
   }

 printf("\rCompacted Ways: Ways=%d Compacted=%d Names=%d Bytes \n",waysx->number,waysx->wrow*INCREMENT_WAYS+waysx->wcol,waysx->length);
 fflush(stdout);

 for(i=0;i<=waysx->row;i++)
    free(waysx->wxdata[i]);
 free(waysx->wxdata);
 waysx->wxdata=NULL;
}


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


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

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

  WayX **a The first extended Way.

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

static int sort_by_name_and_properties(WayX **a,WayX **b)
{
 char *a_name=(*a)->name;
 char *b_name=(*b)->name;
 int name_compare;

 name_compare=strcmp(a_name,b_name);

 if(name_compare)
    return(name_compare);
 else
   {
    Way *a_way=(*a)->way;
    Way *b_way=(*b)->way;

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


/*++++++++++++++++++++++++++++++++++++++
  Work out the index of the Way in the final data.

  index_t IndexWayInWaysX Returns the index of the Way.

  WaysX *waysx The Ways to use.

  WayX *wayx The extended way attached to the way.
  ++++++++++++++++++++++++++++++++++++++*/

index_t IndexWayInWaysX(WaysX *waysx,WayX *wayx)
{
 int row;

 assert(waysx->wdata);          /* Must have wdata filled in => data exists */

 for(row=waysx->wrow;row>=0;row--)
    if((wayx->way-waysx->wdata[row])>=0 &&
       (wayx->way-waysx->wdata[row])<INCREMENT_WAYSX)
       break;

 return(row*INCREMENT_WAYS+(off_t)(wayx->way-waysx->wdata[row]));
}
1	amb	110	/***************************************
2	amb	243	$Header: /home/amb/CVS/routino/src/waysx.c,v 1.19 2009-08-19 18:02:08 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			/* Constants */
35
36	amb	216	/+ The array size increment for WaysX (UK is ~1.3M raw ways, this is ~79 increments). +/
37			#define INCREMENT_WAYSX (16*1024)
38	amb	110
39	amb	216	/+ The array size increment for Ways (UK is ~240k compacted ways, this is ~59 increments). +/
40			#define INCREMENT_WAYS (4*1024)
41	amb	110
42	amb	216	/+ The array size increment for names (UK is ~2.9MBytes of compacted names, this is ~22 increments). +/
43			#define INCREMENT_NAMES (128*1024)
44
45
46	amb	110	/* Functions */
47
48	amb	203	static int sort_by_id(WayX a,WayX b);
49			static int sort_by_name_and_properties(WayX a,WayX b);
50	amb	110
51
52			/*++++++++++++++++++++++++++++++++++++++
53			Allocate a new way list.
54
55			WaysX *NewWayList Returns the way list.
56			++++++++++++++++++++++++++++++++++++++*/
57
58			WaysX *NewWayList(void)
59			{
60			WaysX *waysx;
61
62	amb	213	waysx=(WaysX*)calloc(1,sizeof(WaysX));
63	amb	110
64	amb	243	assert(waysx); /* Check calloc() worked */
65
66	amb	216	waysx->row=-1;
67			waysx->wrow=-1;
68
69	amb	110	return(waysx);
70			}
71
72
73			/*++++++++++++++++++++++++++++++++++++++
74	amb	226	Free a way list.
75
76			WaysX *waysx The list to be freed.
77			++++++++++++++++++++++++++++++++++++++*/
78
79			void FreeWayList(WaysX *waysx)
80			{
81			if(waysx->xdata)
82			{
83			int i;
84			for(i=0;i<(waysx->row*INCREMENT_WAYSX+waysx->col);i++)
85			free(waysx->xdata[i/INCREMENT_WAYSX][i%INCREMENT_WAYSX].name);
86			for(i=0;i<=waysx->row;i++)
87			free(waysx->xdata[i]);
88			free(waysx->xdata);
89			}
90
91			if(waysx->wxdata)
92			{
93			int i;
94			for(i=0;i<=waysx->row;i++)
95			free(waysx->wxdata[i]);
96			free(waysx->wxdata);
97			}
98
99			if(waysx->ndata)
100			free(waysx->ndata);
101			if(waysx->idata)
102			free(waysx->idata);
103
104			if(waysx->wdata)
105			{
106			int i;
107			for(i=0;i<=waysx->wrow;i++)
108			free(waysx->wdata[i]);
109			free(waysx->wdata);
110			}
111
112			if(waysx->names)
113			free(waysx->names);
114
115			free(waysx);
116			}
117
118
119			/*++++++++++++++++++++++++++++++++++++++
120	amb	110	Save the way list to a file.
121
122			WaysX* waysx The set of ways to save.
123
124			const char *filename The name of the file to save.
125			++++++++++++++++++++++++++++++++++++++*/
126
127			void SaveWayList(WaysX* waysx,const char *filename)
128			{
129	amb	214	index_t i;
130	amb	110	int fd;
131	amb	243	Ways *ways;
132	amb	110
133	amb	243	assert(waysx->wdata); /* Must have wdata filled in => compacted */
134			assert(waysx->names); /* Must have names filled in => compacted */
135	amb	110
136	amb	227	printf("Writing Ways: Ways=0");
137			fflush(stdout);
138
139	amb	110	/* Fill in a Ways structure with the offset of the real data in the file after
140			the Way structure itself. */
141
142	amb	243	ways=calloc(1,sizeof(Ways));
143
144			assert(ways); /* Check calloc() worked */
145
146	amb	216	ways->number=waysx->wrow*INCREMENT_WAYS+waysx->wcol;
147	amb	232	ways->onumber=waysx->number;
148
149	amb	110	ways->data=NULL;
150	amb	232
151	amb	110	ways->ways=(void*)sizeof(Ways);
152	amb	214	ways->names=(void)(sizeof(Ways)+ways->numbersizeof(Way));
153	amb	110
154			/* Write out the Ways structure and then the real data. */
155
156			fd=OpenFile(filename);
157
158			WriteFile(fd,ways,sizeof(Ways));
159
160	amb	203	for(i=0;i<ways->number;i++)
161	amb	132	{
162	amb	216	WriteFile(fd,&waysx->wdata[i/INCREMENT_WAYS][i%INCREMENT_WAYS],sizeof(Way));
163	amb	110
164	amb	132	if(!((i+1)%10000))
165			{
166			printf("\rWriting Ways: Ways=%d",i+1);
167			fflush(stdout);
168			}
169			}
170
171	amb	203	printf("\rWrote Ways: Ways=%d \n",ways->number);
172	amb	132	fflush(stdout);
173
174	amb	110	WriteFile(fd,waysx->names,waysx->length);
175
176			CloseFile(fd);
177
178			/* Free the fake Ways */
179
180			free(ways);
181			}
182
183
184			/*++++++++++++++++++++++++++++++++++++++
185	amb	203	Find a particular way.
186
187			WayX *FindWayX Returns the extended way with the specified id.
188
189			WaysX* waysx The set of ways to process.
190
191			way_t id The way id to look for.
192			++++++++++++++++++++++++++++++++++++++*/
193
194			WayX FindWayX(WaysX waysx,way_t id)
195			{
196			int start=0;
197			int end=waysx->number-1;
198			int mid;
199
200	amb	243	assert(waysx->idata); /* Must have idata filled in => sorted */
201	amb	203
202			/* Binary search - search key exact match only is required.
203			*
204			* # <- start \| Check mid and move start or end if it doesn't match
205			* # \|
206			* # \| Since an exact match is wanted we can set end=mid-1
207			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
208			* # \|
209			* # \| Eventually either end=start or end=start+1 and one of
210			* # <- end \| start or end is the wanted one.
211			*/
212
213			if(end<start) /* There are no ways */
214			return(NULL);
215	amb	205	else if(id<waysx->idata[start]->id) /* Check key is not before start */
216	amb	203	return(NULL);
217	amb	205	else if(id>waysx->idata[end]->id) /* Check key is not after end */
218	amb	203	return(NULL);
219			else
220			{
221			do
222			{
223			mid=(start+end)/2; /* Choose mid point */
224
225	amb	205	if(waysx->idata[mid]->id<id) /* Mid point is too low */
226	amb	203	start=mid+1;
227	amb	205	else if(waysx->idata[mid]->id>id) /* Mid point is too high */
228	amb	203	end=mid-1;
229	amb	205	else /* Mid point is correct */
230			return(waysx->idata[mid]);
231	amb	203	}
232			while((end-start)>1);
233
234	amb	205	if(waysx->idata[start]->id==id) /* Start is correct */
235			return(waysx->idata[start]);
236	amb	203
237	amb	205	if(waysx->idata[end]->id==id) /* End is correct */
238			return(waysx->idata[end]);
239	amb	203	}
240
241			return(NULL);
242			}
243
244
245			/*++++++++++++++++++++++++++++++++++++++
246	amb	110	Append a way to a way list.
247
248			Way *AppendWay Returns the newly appended way.
249
250			WaysX* waysx The set of ways to process.
251
252	amb	203	way_t id The ID of the way.
253
254	amb	110	const char *name The name or reference of the way.
255			++++++++++++++++++++++++++++++++++++++*/
256
257	amb	203	Way AppendWay(WaysX waysx,way_t id,const char *name)
258	amb	110	{
259	amb	243	assert(!waysx->idata); /* Must not have idata filled in => unsorted */
260	amb	216
261	amb	213	/* Check that the arrays have enough space. */
262	amb	110
263	amb	216	if(waysx->row==-1 \|\| waysx->col==INCREMENT_WAYSX)
264	amb	110	{
265	amb	216	waysx->row++;
266			waysx->col=0;
267	amb	110
268	amb	216	if((waysx->row%16)==0)
269			{
270			waysx->xdata=(WayX*)realloc((void)waysx->xdata,(waysx->row+16)sizeof(WayX));
271			waysx->wxdata=(Way*)realloc((void)waysx->wxdata,(waysx->row+16)sizeof(Way));
272	amb	243
273			assert(waysx->xdata); /* Check realloc() worked */
274			assert(waysx->wxdata); /* Check realloc() worked */
275	amb	216	}
276	amb	203
277	amb	216	waysx->xdata[waysx->row]=(WayX)malloc(INCREMENT_WAYSXsizeof(WayX));
278			waysx->wxdata[waysx->row]=(Way)malloc(INCREMENT_WAYSXsizeof(Way));
279	amb	243
280			assert(waysx->xdata[waysx->row]); /* Check malloc() worked */
281			assert(waysx->wxdata[waysx->row]); /* Check malloc() worked */
282	amb	110	}
283
284			/* Insert the way */
285
286	amb	216	waysx->xdata[waysx->row][waysx->col].id=id;
287			waysx->xdata[waysx->row][waysx->col].name=strcpy((char*)malloc(strlen(name)+1),name);
288			waysx->xdata[waysx->row][waysx->col].way=&waysx->wxdata[waysx->row][waysx->col];
289	amb	110
290	amb	216	memset(&waysx->wxdata[waysx->row][waysx->col],0,sizeof(Way));
291	amb	110
292	amb	216	waysx->col++;
293	amb	110
294	amb	216	return(&waysx->wxdata[waysx->row][waysx->col-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	224	index_t i;
307	amb	215	int duplicate;
308	amb	110
309	amb	243	assert(waysx->xdata); /* Must have xdata filled in => data exists */
310			assert(waysx->wxdata); /* Must have wxdata filled in => data exists */
311			assert(!waysx->idata); /* Must not have idata filled in => unsorted */
312			assert(!waysx->ndata); /* Must not have ndata filled in => unsorted */
313	amb	110
314	amb	227	printf("Sorting Ways");
315			fflush(stdout);
316	amb	110
317	amb	216	/* Allocate the array of pointers and sort them */
318	amb	203
319	amb	216	waysx->idata=(WayX*)malloc((waysx->rowINCREMENT_WAYSX+waysx->col)sizeof(WayX));
320
321	amb	243	assert(waysx->idata); /* Check malloc() worked */
322
323	amb	215	do
324			{
325			waysx->number=0;
326	amb	203
327	amb	216	for(i=0;i<(waysx->row*INCREMENT_WAYSX+waysx->col);i++)
328			if(waysx->xdata[i/INCREMENT_WAYSX][i%INCREMENT_WAYSX].id!=NO_WAY)
329	amb	215	{
330	amb	216	waysx->idata[waysx->number]=&waysx->xdata[i/INCREMENT_WAYSX][i%INCREMENT_WAYSX];
331	amb	215	waysx->number++;
332			}
333	amb	203
334	amb	215	qsort(waysx->idata,waysx->number,sizeof(WayX),(int ()(const void,const void))sort_by_id);
335
336			duplicate=0;
337
338			for(i=1;i<waysx->number;i++)
339			{
340			if(waysx->idata[i]->id==waysx->idata[i-1]->id &&
341			waysx->idata[i]->id!=NO_WAY)
342			{
343			waysx->idata[i-1]->id=NO_WAY;
344			duplicate++;
345			}
346			}
347
348			if(duplicate)
349	amb	227	{
350			printf(" - %d duplicates found; trying again.\nSorting Ways",duplicate);
351			fflush(stdout);
352			}
353	amb	215	}
354			while(duplicate);
355
356	amb	203	/* Sort the ways by name and way properties */
357
358	amb	215	waysx->ndata=(WayX*)malloc(waysx->numbersizeof(WayX*));
359	amb	110
360	amb	243	assert(waysx->ndata); /* Check malloc() worked */
361
362	amb	110	for(i=0;i<waysx->number;i++)
363	amb	215	waysx->ndata[i]=waysx->idata[i];
364	amb	110
365	amb	203	qsort(waysx->ndata,waysx->number,sizeof(WayX),(int ()(const void,const void))sort_by_name_and_properties);
366	amb	110
367	amb	227	printf("\rSorted Ways \n");
368			fflush(stdout);
369	amb	224	}
370
371
372			/*++++++++++++++++++++++++++++++++++++++
373			Compact the list of ways and reduce the names.
374
375			WaysX* waysx The set of ways to process.
376			++++++++++++++++++++++++++++++++++++++*/
377
378			void CompactWays(WaysX* waysx)
379			{
380			index_t i;
381
382	amb	243	assert(waysx->ndata); /* Must have ndata filled in => sorted */
383			assert(waysx->wxdata); /* Must have wxdata filled in => data exists */
384			assert(!waysx->names); /* Must not have names filled in => uncompacted */
385			assert(!waysx->wdata); /* Must not have wdata filled in => uncompacted */
386	amb	224
387	amb	227	printf("\rCompacting Ways: Ways=0 Compacted=0 Names=0 Bytes");
388			fflush(stdout);
389	amb	224
390	amb	203	/* Allocate the new data for names */
391	amb	110
392	amb	216	waysx->names=(char)malloc(INCREMENT_NAMESsizeof(char));
393	amb	110
394	amb	243	assert(waysx->names); /* Check malloc() worked */
395
396	amb	110	/* Setup the offsets for the names in the way array */
397
398	amb	224	for(i=0;i<waysx->number;i++)
399	amb	110	{
400	amb	216	int copy=0;
401
402	amb	110	if(i && !strcmp(waysx->ndata[i]->name,waysx->ndata[i-1]->name)) /* Same name */
403	amb	203	{
404			waysx->ndata[i]->way->name=waysx->ndata[i-1]->way->name;
405
406			if(!WaysCompare(waysx->ndata[i]->way,waysx->ndata[i-1]->way)) /* Same properties */
407			waysx->ndata[i]->way=waysx->ndata[i-1]->way;
408			else
409	amb	216	copy=1;
410	amb	203	}
411	amb	110	else /* Different name */
412			{
413	amb	230	if(((waysx->length+strlen(waysx->ndata[i]->name)+1)/INCREMENT_NAMES)>(waysx->length/INCREMENT_NAMES))
414	amb	243	{
415	amb	230	waysx->names=(char)realloc((void)waysx->names,(waysx->length/INCREMENT_NAMES+2)INCREMENT_NAMESsizeof(char));
416	amb	110
417	amb	243	assert(waysx->names); /* Check realloc() worked */
418			}
419
420	amb	110	strcpy(&waysx->names[waysx->length],waysx->ndata[i]->name);
421
422	amb	203	waysx->ndata[i]->way->name=waysx->length;
423	amb	110
424			waysx->length+=strlen(waysx->ndata[i]->name)+1;
425	amb	203
426	amb	216	copy=1;
427	amb	110	}
428	amb	216
429			if(copy)
430			{
431			/* Check that the array has enough space. */
432
433			if(waysx->wrow==-1 \|\| waysx->wcol==INCREMENT_WAYS)
434			{
435			waysx->wrow++;
436			waysx->wcol=0;
437
438			if((waysx->wrow%16)==0)
439	amb	243	{
440	amb	216	waysx->wdata=(Way *)realloc((void)waysx->wdata,(waysx->wrow+16)sizeof(Way));
441
442	amb	243	assert(waysx->wdata); /* Check realloc() worked */
443			}
444
445	amb	216	waysx->wdata[waysx->wrow]=(Way )malloc(INCREMENT_WAYSXsizeof(Way));
446	amb	243
447			assert(waysx->wdata); /* Check malloc() worked */
448	amb	216	}
449
450			waysx->wdata[waysx->wrow][waysx->wcol]=*waysx->ndata[i]->way;
451
452			waysx->ndata[i]->way=&waysx->wdata[waysx->wrow][waysx->wcol];
453
454			waysx->wcol++;
455			}
456	amb	224
457			if(!((i+1)%10000))
458			{
459	amb	227	printf("\rCompacting Ways: Ways=%d Compacted=%d Names=%d Bytes",i+1,waysx->wrow*INCREMENT_WAYS+waysx->wcol,waysx->length);
460	amb	224	fflush(stdout);
461			}
462	amb	110	}
463	amb	132
464	amb	227	printf("\rCompacted Ways: Ways=%d Compacted=%d Names=%d Bytes \n",waysx->number,waysx->wrow*INCREMENT_WAYS+waysx->wcol,waysx->length);
465	amb	224	fflush(stdout);
466
467	amb	226	for(i=0;i<=waysx->row;i++)
468	amb	216	free(waysx->wxdata[i]);
469			free(waysx->wxdata);
470			waysx->wxdata=NULL;
471	amb	110	}
472
473
474			/*++++++++++++++++++++++++++++++++++++++
475	amb	203	Sort the ways into id order.
476	amb	110
477	amb	203	int sort_by_id Returns the comparison of the id fields.
478	amb	110
479	amb	228	WayX **a The first extended Way.
480	amb	110
481	amb	228	WayX **b The second extended Way.
482	amb	110	++++++++++++++++++++++++++++++++++++++*/
483
484	amb	203	static int sort_by_id(WayX a,WayX b)
485	amb	110	{
486	amb	203	way_t a_id=(*a)->id;
487			way_t b_id=(*b)->id;
488
489			if(a_id<b_id)
490			return(-1);
491			else if(a_id>b_id)
492			return(1);
493			else
494			return(0);
495			}
496
497
498			/*++++++++++++++++++++++++++++++++++++++
499			Sort the ways into name and properties order.
500
501			int sort_by_name_and_properties Returns the comparison of the name and properties fields.
502
503	amb	228	WayX **a The first extended Way.
504	amb	203
505	amb	228	WayX **b The second extended Way.
506	amb	203	++++++++++++++++++++++++++++++++++++++*/
507
508			static int sort_by_name_and_properties(WayX a,WayX b)
509			{
510	amb	110	char a_name=(a)->name;
511			char b_name=(b)->name;
512	amb	203	int name_compare;
513	amb	110
514	amb	203	name_compare=strcmp(a_name,b_name);
515
516			if(name_compare)
517			return(name_compare);
518			else
519			{
520			Way a_way=(a)->way;
521			Way b_way=(b)->way;
522
523			return(WaysCompare(a_way,b_way));
524			}
525	amb	110	}
526	amb	216
527
528			/*++++++++++++++++++++++++++++++++++++++
529			Work out the index of the Way in the final data.
530
531			index_t IndexWayInWaysX Returns the index of the Way.
532
533			WaysX *waysx The Ways to use.
534
535			WayX *wayx The extended way attached to the way.
536			++++++++++++++++++++++++++++++++++++++*/
537
538			index_t IndexWayInWaysX(WaysX waysx,WayX wayx)
539			{
540			int row;
541
542	amb	243	assert(waysx->wdata); /* Must have wdata filled in => data exists */
543	amb	216
544			for(row=waysx->wrow;row>=0;row--)
545			if((wayx->way-waysx->wdata[row])>=0 &&
546			(wayx->way-waysx->wdata[row])<INCREMENT_WAYSX)
547			break;
548
549			return(row*INCREMENT_WAYS+(off_t)(wayx->way-waysx->wdata[row]));
550			}