trunk/src/waysx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.9 2009-07-02 16:33:31 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)
{
 int 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;
 int 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	/***************************************
2	$Header: /home/amb/CVS/routino/src/waysx.c,v 1.9 2009-07-02 16:33:31 amb Exp $
3
4	Extended Way data type functions.
5
6	Part of the Routino routing software.
7	****************/ /****************
8	This file Copyright 2008,2009 Andrew M. Bishop
9
10	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	***************************************/
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	static int sort_by_id(WayX a,WayX b);
42	static int sort_by_name_and_properties(WayX a,WayX b);
43
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*)calloc(1,sizeof(WaysX));
56
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	int i;
72	int fd;
73	Ways *ways=calloc(1,sizeof(Ways));
74
75	assert(waysx->sorted); /* Must be sorted */
76	assert(waysx->wdata); /* Must have wdata filled in */
77
78	/* Fill in a Ways structure with the offset of the real data in the file after
79	the Way structure itself. */
80
81	ways->number=waysx->wnumber;
82	ways->data=NULL;
83	ways->ways=(void*)sizeof(Ways);
84	ways->names=(void)sizeof(Ways)+ways->numbersizeof(Way);
85
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	for(i=0;i<ways->number;i++)
93	{
94	WriteFile(fd,&waysx->wdata[i],sizeof(Way));
95
96	if(!((i+1)%10000))
97	{
98	printf("\rWriting Ways: Ways=%d",i+1);
99	fflush(stdout);
100	}
101	}
102
103	printf("\rWrote Ways: Ways=%d \n",ways->number);
104	fflush(stdout);
105
106	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	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	assert(waysx->idata); /* Must have idata filled in */
134
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	else if(id<waysx->idata[start]->id) /* Check key is not before start */
149	return(NULL);
150	else if(id>waysx->idata[end]->id) /* Check key is not after end */
151	return(NULL);
152	else
153	{
154	do
155	{
156	mid=(start+end)/2; /* Choose mid point */
157
158	if(waysx->idata[mid]->id<id) /* Mid point is too low */
159	start=mid+1;
160	else if(waysx->idata[mid]->id>id) /* Mid point is too high */
161	end=mid-1;
162	else /* Mid point is correct */
163	return(waysx->idata[mid]);
164	}
165	while((end-start)>1);
166
167	if(waysx->idata[start]->id==id) /* Start is correct */
168	return(waysx->idata[start]);
169
170	if(waysx->idata[end]->id==id) /* End is correct */
171	return(waysx->idata[end]);
172	}
173
174	return(NULL);
175	}
176
177
178	/*++++++++++++++++++++++++++++++++++++++
179	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	way_t id The ID of the way.
186
187	const char *name The name or reference of the way.
188	++++++++++++++++++++++++++++++++++++++*/
189
190	Way AppendWay(WaysX waysx,way_t id,const char *name)
191	{
192	/* Check that the arrays have enough space. */
193
194	if(waysx->number==waysx->alloced)
195	{
196	waysx->alloced+=INCREMENT_WAYS;
197
198	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	}
202
203	/* Insert the way */
204
205	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
209	memset(&waysx->wdata[waysx->number],0,sizeof(Way));
210
211	waysx->number++;
212
213	return(&waysx->wdata[waysx->number-1]);
214
215	waysx->sorted=0;
216	}
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	Way *uniq_ways;
228	int i,j;
229
230	assert(waysx->xdata); /* Must have xdata filled in */
231
232	printf("Sorting Ways"); fflush(stdout);
233
234	/* Sort the ways by id */
235
236	waysx->idata=malloc(waysx->numbersizeof(WayX));
237
238	for(i=0;i<waysx->number;i++)
239	waysx->idata[i]=&waysx->xdata[i];
240
241	qsort(waysx->idata,waysx->number,sizeof(WayX),(int ()(const void,const void))sort_by_id);
242
243	/* Sort the ways by name and way properties */
244
245	waysx->ndata=malloc(waysx->numbersizeof(WayX));
246
247	for(i=0;i<waysx->number;i++)
248	waysx->ndata[i]=&waysx->xdata[i];
249
250	qsort(waysx->ndata,waysx->number,sizeof(WayX),(int ()(const void,const void))sort_by_name_and_properties);
251
252	/* Allocate the new data for names */
253
254	waysx->names=(char)malloc(waysx->allocedsizeof(char));
255
256	/* Allocate the data for unique ways */
257
258	uniq_ways=(Way)malloc(waysx->numbersizeof(Way));
259
260	/* Setup the offsets for the names in the way array */
261
262	for(i=0,j=0;i<waysx->number;i++)
263	{
264	if(i && !strcmp(waysx->ndata[i]->name,waysx->ndata[i-1]->name)) /* Same name */
265	{
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	uniq_ways[j]=*waysx->ndata[i]->way;
273	waysx->ndata[i]->way=&uniq_ways[j++];
274	}
275	}
276	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	waysx->ndata[i]->way->name=waysx->length;
288
289	waysx->length+=strlen(waysx->ndata[i]->name)+1;
290
291	uniq_ways[j]=*waysx->ndata[i]->way;
292	waysx->ndata[i]->way=&uniq_ways[j++];
293	}
294	}
295
296	waysx->wnumber=j;
297
298	free(waysx->wdata);
299
300	waysx->wdata=uniq_ways;
301
302	printf("\rSorted Ways \n"); fflush(stdout);
303
304	waysx->sorted=1;
305	}
306
307
308	/*++++++++++++++++++++++++++++++++++++++
309	Sort the ways into id order.
310
311	int sort_by_id Returns the comparison of the id fields.
312
313	Way **a The first Way.
314
315	Way **b The second Way.
316	++++++++++++++++++++++++++++++++++++++*/
317
318	static int sort_by_id(WayX a,WayX b)
319	{
320	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	char a_name=(a)->name;
345	char b_name=(b)->name;
346	int name_compare;
347
348	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	}