trunk/src/waysx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.7 2009-06-25 18:25:46 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"


/* Constants */

/*+ The array size increment for ways - expect ~1,000,000 ways. +*/
#define INCREMENT_WAYS 256*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*)malloc(sizeof(WaysX));

 waysx->sorted=0;
 waysx->alloced=INCREMENT_WAYS;
 waysx->number=0;
 waysx->length=0;

 waysx->xdata=(WayX*)malloc(waysx->alloced*sizeof(WayX));
 waysx->idata=NULL;
 waysx->ndata=NULL;

 waysx->wnumber=0;

 waysx->wdata=(Way*)malloc(waysx->alloced*sizeof(Way));

 waysx->names=NULL;

 return(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)
{
 int i;
 int fd;
 Ways *ways=calloc(1,sizeof(Ways));

 assert(waysx->sorted);       /* Must be sorted */

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

 ways->number=waysx->wnumber;
 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],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->sorted);        /* Must be 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->sorted);      /* Must not be sorted */

 waysx->sorted=0;

 /* Check that the array has enough space. */

 if(waysx->number==waysx->alloced)
   {
    waysx->alloced+=INCREMENT_WAYS;

    waysx->xdata=(WayX*)realloc((void*)waysx->xdata,waysx->alloced*sizeof(WayX));

    waysx->wdata=(Way*)realloc((void*)waysx->wdata,waysx->alloced*sizeof(Way));
   }

 /* Insert the way */

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

 memset(&waysx->wdata[waysx->number],0,sizeof(Way));

 waysx->number++;

 return(&waysx->wdata[waysx->number-1]);
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the list of ways and fix the names.

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

void SortWayList(WaysX* waysx)
{
 Way *uniq_ways;
 int i,j;

 assert(!waysx->sorted);      /* Must not be sorted */

 waysx->sorted=1;

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

 /* Sort the ways by id */

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

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

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

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

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

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

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

 /* Allocate the new data for names */

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

 /* Allocate the data for unique ways */

 uniq_ways=(Way*)malloc(waysx->number*sizeof(Way));

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

 for(i=0,j=0;i<waysx->number;i++)
   {
    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
         {
          memmove(&uniq_ways[j],waysx->ndata[i]->way,sizeof(Way));
          waysx->ndata[i]->way=&uniq_ways[j++];
         }
      }
    else                                                          /* Different name */
      {
       if((waysx->length+strlen(waysx->ndata[i]->name)+1)>=waysx->alloced)
         {
          waysx->alloced+=INCREMENT_WAYS;

          waysx->names=(char*)realloc((void*)waysx->names,waysx->alloced*sizeof(char));
         }

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

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

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

       memmove(&uniq_ways[j],waysx->ndata[i]->way,sizeof(Way));
       waysx->ndata[i]->way=&uniq_ways[j++];
      }
   }

 waysx->wnumber=j;

 free(waysx->wdata);

 waysx->wdata=uniq_ways;

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


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

  int sort_by_id Returns the comparison of the id fields.

  Way **a The first Way.

  Way **b The second 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.

  Way **a The first Way.

  Way **b The second 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));
   }
}
1	amb	110	/***************************************
2	amb	205	$Header: /home/amb/CVS/routino/src/waysx.c,v 1.7 2009-06-25 18:25:46 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
32
33			/* Constants */
34
35			/+ The array size increment for ways - expect ~1,000,000 ways. +/
36			#define INCREMENT_WAYS 256*1024
37
38
39			/* Functions */
40
41	amb	203	static int sort_by_id(WayX a,WayX b);
42			static int sort_by_name_and_properties(WayX a,WayX b);
43	amb	110
44
45			/*++++++++++++++++++++++++++++++++++++++
46			Allocate a new way list.
47
48			WaysX *NewWayList Returns the way list.
49			++++++++++++++++++++++++++++++++++++++*/
50
51			WaysX *NewWayList(void)
52			{
53			WaysX *waysx;
54
55			waysx=(WaysX*)malloc(sizeof(WaysX));
56
57			waysx->sorted=0;
58			waysx->alloced=INCREMENT_WAYS;
59			waysx->number=0;
60			waysx->length=0;
61
62	amb	203	waysx->xdata=(WayX)malloc(waysx->allocedsizeof(WayX));
63	amb	205	waysx->idata=NULL;
64	amb	110	waysx->ndata=NULL;
65
66	amb	203	waysx->wnumber=0;
67
68			waysx->wdata=(Way)malloc(waysx->allocedsizeof(Way));
69
70			waysx->names=NULL;
71
72	amb	110	return(waysx);
73			}
74
75
76			/*++++++++++++++++++++++++++++++++++++++
77			Save the way list to a file.
78
79			WaysX* waysx The set of ways to save.
80
81			const char *filename The name of the file to save.
82			++++++++++++++++++++++++++++++++++++++*/
83
84			void SaveWayList(WaysX* waysx,const char *filename)
85			{
86			int i;
87			int fd;
88			Ways *ways=calloc(1,sizeof(Ways));
89
90			assert(waysx->sorted); /* Must be sorted */
91
92			/* Fill in a Ways structure with the offset of the real data in the file after
93			the Way structure itself. */
94
95	amb	203	ways->number=waysx->wnumber;
96	amb	110	ways->data=NULL;
97			ways->ways=(void*)sizeof(Ways);
98			ways->names=(void)sizeof(Ways)+ways->numbersizeof(Way);
99
100			/* Write out the Ways structure and then the real data. */
101
102			fd=OpenFile(filename);
103
104			WriteFile(fd,ways,sizeof(Ways));
105
106	amb	203	for(i=0;i<ways->number;i++)
107	amb	132	{
108	amb	203	WriteFile(fd,&waysx->wdata[i],sizeof(Way));
109	amb	110
110	amb	132	if(!((i+1)%10000))
111			{
112			printf("\rWriting Ways: Ways=%d",i+1);
113			fflush(stdout);
114			}
115			}
116
117	amb	203	printf("\rWrote Ways: Ways=%d \n",ways->number);
118	amb	132	fflush(stdout);
119
120	amb	110	WriteFile(fd,waysx->names,waysx->length);
121
122			CloseFile(fd);
123
124			/* Free the fake Ways */
125
126			free(ways);
127			}
128
129
130			/*++++++++++++++++++++++++++++++++++++++
131	amb	203	Find a particular way.
132
133			WayX *FindWayX Returns the extended way with the specified id.
134
135			WaysX* waysx The set of ways to process.
136
137			way_t id The way id to look for.
138			++++++++++++++++++++++++++++++++++++++*/
139
140			WayX FindWayX(WaysX waysx,way_t id)
141			{
142			int start=0;
143			int end=waysx->number-1;
144			int mid;
145
146			assert(waysx->sorted); /* Must be sorted */
147
148			/* Binary search - search key exact match only is required.
149			*
150			* # <- start \| Check mid and move start or end if it doesn't match
151			* # \|
152			* # \| Since an exact match is wanted we can set end=mid-1
153			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
154			* # \|
155			* # \| Eventually either end=start or end=start+1 and one of
156			* # <- end \| start or end is the wanted one.
157			*/
158
159			if(end<start) /* There are no ways */
160			return(NULL);
161	amb	205	else if(id<waysx->idata[start]->id) /* Check key is not before start */
162	amb	203	return(NULL);
163	amb	205	else if(id>waysx->idata[end]->id) /* Check key is not after end */
164	amb	203	return(NULL);
165			else
166			{
167			do
168			{
169			mid=(start+end)/2; /* Choose mid point */
170
171	amb	205	if(waysx->idata[mid]->id<id) /* Mid point is too low */
172	amb	203	start=mid+1;
173	amb	205	else if(waysx->idata[mid]->id>id) /* Mid point is too high */
174	amb	203	end=mid-1;
175	amb	205	else /* Mid point is correct */
176			return(waysx->idata[mid]);
177	amb	203	}
178			while((end-start)>1);
179
180	amb	205	if(waysx->idata[start]->id==id) /* Start is correct */
181			return(waysx->idata[start]);
182	amb	203
183	amb	205	if(waysx->idata[end]->id==id) /* End is correct */
184			return(waysx->idata[end]);
185	amb	203	}
186
187			return(NULL);
188			}
189
190
191			/*++++++++++++++++++++++++++++++++++++++
192	amb	110	Append a way to a way list.
193
194			Way *AppendWay Returns the newly appended way.
195
196			WaysX* waysx The set of ways to process.
197
198	amb	203	way_t id The ID of the way.
199
200	amb	110	const char *name The name or reference of the way.
201			++++++++++++++++++++++++++++++++++++++*/
202
203	amb	203	Way AppendWay(WaysX waysx,way_t id,const char *name)
204	amb	110	{
205			assert(!waysx->sorted); /* Must not be sorted */
206
207			waysx->sorted=0;
208
209			/* Check that the array has enough space. */
210
211			if(waysx->number==waysx->alloced)
212			{
213			waysx->alloced+=INCREMENT_WAYS;
214
215	amb	203	waysx->xdata=(WayX)realloc((void)waysx->xdata,waysx->alloced*sizeof(WayX));
216
217			waysx->wdata=(Way)realloc((void)waysx->wdata,waysx->alloced*sizeof(Way));
218	amb	110	}
219
220			/* Insert the way */
221
222	amb	203	waysx->xdata[waysx->number].id=id;
223			waysx->xdata[waysx->number].name=strcpy((char*)malloc(strlen(name)+1),name);
224			waysx->xdata[waysx->number].way=&waysx->wdata[waysx->number];
225	amb	110
226	amb	203	memset(&waysx->wdata[waysx->number],0,sizeof(Way));
227	amb	110
228			waysx->number++;
229
230	amb	203	return(&waysx->wdata[waysx->number-1]);
231	amb	110	}
232
233
234			/*++++++++++++++++++++++++++++++++++++++
235			Sort the list of ways and fix the names.
236
237			WaysX* waysx The set of ways to process.
238			++++++++++++++++++++++++++++++++++++++*/
239
240			void SortWayList(WaysX* waysx)
241			{
242	amb	203	Way *uniq_ways;
243			int i,j;
244	amb	110
245			assert(!waysx->sorted); /* Must not be sorted */
246
247			waysx->sorted=1;
248
249	amb	132	printf("Sorting Ways"); fflush(stdout);
250
251	amb	203	/* Sort the ways by id */
252	amb	110
253	amb	205	waysx->idata=malloc(waysx->numbersizeof(WayX));
254	amb	203
255			for(i=0;i<waysx->number;i++)
256	amb	205	waysx->idata[i]=&waysx->xdata[i];
257	amb	203
258	amb	205	qsort(waysx->idata,waysx->number,sizeof(WayX),(int ()(const void,const void))sort_by_id);
259	amb	203
260			/* Sort the ways by name and way properties */
261
262	amb	110	waysx->ndata=malloc(waysx->numbersizeof(WayX));
263
264			for(i=0;i<waysx->number;i++)
265	amb	203	waysx->ndata[i]=&waysx->xdata[i];
266	amb	110
267	amb	203	qsort(waysx->ndata,waysx->number,sizeof(WayX),(int ()(const void,const void))sort_by_name_and_properties);
268	amb	110
269	amb	203	/* Allocate the new data for names */
270	amb	110
271			waysx->names=(char)malloc(waysx->allocedsizeof(char));
272
273	amb	203	/* Allocate the data for unique ways */
274
275			uniq_ways=(Way)malloc(waysx->numbersizeof(Way));
276
277	amb	110	/* Setup the offsets for the names in the way array */
278
279	amb	203	for(i=0,j=0;i<waysx->number;i++)
280	amb	110	{
281			if(i && !strcmp(waysx->ndata[i]->name,waysx->ndata[i-1]->name)) /* Same name */
282	amb	203	{
283			waysx->ndata[i]->way->name=waysx->ndata[i-1]->way->name;
284
285			if(!WaysCompare(waysx->ndata[i]->way,waysx->ndata[i-1]->way)) /* Same properties */
286			waysx->ndata[i]->way=waysx->ndata[i-1]->way;
287			else
288			{
289			memmove(&uniq_ways[j],waysx->ndata[i]->way,sizeof(Way));
290			waysx->ndata[i]->way=&uniq_ways[j++];
291			}
292			}
293	amb	110	else /* Different name */
294			{
295			if((waysx->length+strlen(waysx->ndata[i]->name)+1)>=waysx->alloced)
296			{
297			waysx->alloced+=INCREMENT_WAYS;
298
299			waysx->names=(char)realloc((void)waysx->names,waysx->alloced*sizeof(char));
300			}
301
302			strcpy(&waysx->names[waysx->length],waysx->ndata[i]->name);
303
304	amb	203	waysx->ndata[i]->way->name=waysx->length;
305	amb	110
306			waysx->length+=strlen(waysx->ndata[i]->name)+1;
307	amb	203
308			memmove(&uniq_ways[j],waysx->ndata[i]->way,sizeof(Way));
309			waysx->ndata[i]->way=&uniq_ways[j++];
310	amb	110	}
311			}
312	amb	132
313	amb	203	waysx->wnumber=j;
314
315			free(waysx->wdata);
316
317			waysx->wdata=uniq_ways;
318
319	amb	132	printf("\rSorted Ways \n"); fflush(stdout);
320	amb	110	}
321
322
323			/*++++++++++++++++++++++++++++++++++++++
324	amb	203	Sort the ways into id order.
325	amb	110
326	amb	203	int sort_by_id Returns the comparison of the id fields.
327	amb	110
328			Way **a The first Way.
329
330			Way **b The second Way.
331			++++++++++++++++++++++++++++++++++++++*/
332
333	amb	203	static int sort_by_id(WayX a,WayX b)
334	amb	110	{
335	amb	203	way_t a_id=(*a)->id;
336			way_t b_id=(*b)->id;
337
338			if(a_id<b_id)
339			return(-1);
340			else if(a_id>b_id)
341			return(1);
342			else
343			return(0);
344			}
345
346
347			/*++++++++++++++++++++++++++++++++++++++
348			Sort the ways into name and properties order.
349
350			int sort_by_name_and_properties Returns the comparison of the name and properties fields.
351
352			Way **a The first Way.
353
354			Way **b The second Way.
355			++++++++++++++++++++++++++++++++++++++*/
356
357			static int sort_by_name_and_properties(WayX a,WayX b)
358			{
359	amb	110	char a_name=(a)->name;
360			char b_name=(b)->name;
361	amb	203	int name_compare;
362	amb	110
363	amb	203	name_compare=strcmp(a_name,b_name);
364
365			if(name_compare)
366			return(name_compare);
367			else
368			{
369			Way a_way=(a)->way;
370			Way b_way=(b)->way;
371
372			return(WaysCompare(a_way,b_way));
373			}
374	amb	110	}