trunk/src/waysx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.10 2009-07-02 17:49:16 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*)calloc(1,sizeof(WaysX));

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

 assert(waysx->sorted);       /* Must be sorted */
 assert(waysx->wdata);        /* Must have wdata filled in */

 /* 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 */
 assert(waysx->idata);         /* Must have idata filled in */

 /* 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)
{
 /* Check that the arrays have 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]);

 waysx->sorted=0;
}


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

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

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

 assert(waysx->xdata);         /* Must have xdata filled in */

 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
         {
          uniq_ways[j]=*waysx->ndata[i]->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;

       uniq_ways[j]=*waysx->ndata[i]->way;
       waysx->ndata[i]->way=&uniq_ways[j++];
      }
   }

 waysx->wnumber=j;

 free(waysx->wdata);

 waysx->wdata=uniq_ways;

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

 waysx->sorted=1;
}


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