trunk/src/ways.c

/***************************************
 $Header: /home/amb/CVS/routino/src/ways.c,v 1.2 2009-01-04 17:51:24 amb Exp $

 Way data type functions.
 ******************/ /******************
 Written by Andrew M. Bishop

 This file Copyright 2008,2009 Andrew M. Bishop
 It may be distributed under the GNU Public License, version 2, or
 any higher version.  See section COPYING of the GNU Public license
 for conditions under which this file may be redistributed.
 ***************************************/


#include <assert.h>
#include <stdlib.h>
#include <string.h>

#include "functions.h"
#include "types.h"

#define INCREMENT 256*1024

/*+ The list of ways +*/
Ways *OSMWays=NULL;

/*+ Is the data sorted and therefore searchable? +*/
static int sorted=0;

/*+ Is the data loaded from a file and therefore read-only? +*/
static int loaded=0;

/*+ How many entries are allocated? +*/
static size_t alloced=0;

/*+ The list of names for the ways before they are merged into the main data structure. +*/
static char **names=NULL;

/* Functions */

static int sort_by_id(Way *a,Way *b);
static int sort_by_name(Way *a,Way *b);


/*++++++++++++++++++++++++++++++++++++++
  Load in a way list from a file.

  const char *filename The name of the file to load.
  ++++++++++++++++++++++++++++++++++++++*/

void LoadWayList(const char *filename)
{
 assert(!OSMWays);

 OSMWays=(Ways*)MapFile(filename);

 assert(OSMWays);

 sorted=1;
 loaded=1;
}


/*++++++++++++++++++++++++++++++++++++++
  Save the way list to a file.

  const char *filename The name of the file to save.
  ++++++++++++++++++++++++++++++++++++++*/

void SaveWayList(const char *filename)
{
 int retval;

 assert(!loaded);               /* Must not be loaded */

 assert(sorted);                /* Must be sorted */

 retval=WriteFile(filename,OSMWays,sizeof(Ways)-sizeof(OSMWays->ways)+(OSMWays->number+OSMWays->number_str)*sizeof(Way));

 assert(!retval);               /* Must be zero */
}


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

  Way *FindWay Returns a pointer to the way with the specified id.

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

Way *FindWay(way_t id)
{
 int start=0;
 int end=OSMWays->number-1;
 int mid;

 assert(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(OSMWays->number==0)              /* There are no ways */
    return(NULL);
 else if(id<OSMWays->ways[start].id) /* Check key is not before start */
    return(NULL);
 else if(id>OSMWays->ways[end].id)   /* Check key is not after end */
    return(NULL);
 else
   {
    do
      {
       mid=(start+end)/2;                /* Choose mid point */

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

    if(OSMWays->ways[start].id==id)      /* Start is correct */
       return(&OSMWays->ways[start]);

    if(OSMWays->ways[end].id==id)        /* End is correct */
       return(&OSMWays->ways[end]);
   }

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Return the name of the way.

  const char *WayName Returns the name.

  Way *way The way whose name is to be found.
  ++++++++++++++++++++++++++++++++++++++*/

const char *WayName(Way *way)
{
 assert(sorted);                /* Must be sorted */

 return((char*)&OSMWays->ways[(off_t)way->name]);
}


/*++++++++++++++++++++++++++++++++++++++
  Append a way to a newly created way list (unsorted).

  way_t id The way identification.

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

  speed_t speed The speed on the way.
  ++++++++++++++++++++++++++++++++++++++*/

void AppendWay(way_t id,const char *name,speed_t speed)
{
 assert(!loaded);               /* Must not be loaded */

 assert(!sorted);               /* Must not be sorted */

 /* Check that the whole thing is allocated. */

 if(!OSMWays)
   {
    alloced=INCREMENT;
    OSMWays=(Ways*)malloc(sizeof(Ways)-sizeof(OSMWays->ways)+alloced*sizeof(Way));

    OSMWays->number=0;
    OSMWays->number_str=0;

    names=(char**)malloc(alloced*sizeof(char*));
   }

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

 if(OSMWays->number==alloced)
   {
    alloced+=INCREMENT;
    OSMWays=(Ways*)realloc((void*)OSMWays,sizeof(Ways)-sizeof(OSMWays->ways)+alloced*sizeof(Way));

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

 /* Insert the way */

 names[OSMWays->number]=strcpy((char*)malloc(strlen(name)+1),name);

 OSMWays->ways[OSMWays->number].id=id;
 OSMWays->ways[OSMWays->number].name=OSMWays->number;
 OSMWays->ways[OSMWays->number].speed=speed;

 OSMWays->number++;

 sorted=0;
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the way list.
  ++++++++++++++++++++++++++++++++++++++*/

void SortWayList(void)
{
 char *name=NULL;
 int i;

 assert(!loaded);               /* Must not be loaded */

 /* Sort the ways by name */

 qsort(OSMWays->ways,OSMWays->number,sizeof(Way),(int (*)(const void*,const void*))sort_by_name);

 for(i=0;i<OSMWays->number;i++)
   {
    if(name && !strcmp(name,names[OSMWays->ways[i].name])) /* Same name */
      {
       free(names[OSMWays->ways[i].name]);
       OSMWays->ways[i].name=OSMWays->ways[i-1].name;
      }
    else                                            /* Different name */
      {
       name=names[OSMWays->ways[i].name];

       if((OSMWays->number+OSMWays->number_str+strlen(name)/sizeof(Way)+1)>=alloced)
         {
          alloced+=INCREMENT;

          OSMWays=(Ways*)realloc((void*)OSMWays,sizeof(Ways)-sizeof(OSMWays->ways)+alloced*sizeof(Way));
         }

       strcpy((char*)&OSMWays->ways[OSMWays->number+OSMWays->number_str],name);
       free(name);

       OSMWays->ways[i].name=OSMWays->number+OSMWays->number_str;
       name=(char*)&OSMWays->ways[OSMWays->ways[i].name];

       OSMWays->number_str+=strlen(name)/sizeof(Way)+1;
      }
   }

 /* Sort the ways by id */

 qsort(OSMWays->ways,OSMWays->number,sizeof(Way),(int (*)(const void*,const void*))sort_by_id);

 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(Way *a,Way *b)
{
 way_t a_id=a->id;
 way_t b_id=b->id;

 return(a_id-b_id);
}


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

  int sort_by_name Returns the comparison of the name fields.

  Way *a The first Way.

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

static int sort_by_name(Way *a,Way *b)
{
 char *a_name=names[a->name];
 char *b_name=names[b->name];

 return(strcmp(a_name,b_name));
}
1	amb	7	/***************************************
2	amb	8	$Header: /home/amb/CVS/routino/src/ways.c,v 1.2 2009-01-04 17:51:24 amb Exp $
3	amb	7
4			Way data type functions.
5			****************/ /****************
6			Written by Andrew M. Bishop
7
8			This file Copyright 2008,2009 Andrew M. Bishop
9			It may be distributed under the GNU Public License, version 2, or
10			any higher version. See section COPYING of the GNU Public license
11			for conditions under which this file may be redistributed.
12			***************************************/
13
14
15			#include <assert.h>
16			#include <stdlib.h>
17			#include <string.h>
18
19			#include "functions.h"
20			#include "types.h"
21
22			#define INCREMENT 256*1024
23
24			/+ The list of ways +/
25			Ways *OSMWays=NULL;
26
27			/+ Is the data sorted and therefore searchable? +/
28			static int sorted=0;
29
30	amb	8	/+ Is the data loaded from a file and therefore read-only? +/
31			static int loaded=0;
32
33			/+ How many entries are allocated? +/
34			static size_t alloced=0;
35
36	amb	7	/+ The list of names for the ways before they are merged into the main data structure. +/
37			static char **names=NULL;
38
39			/* Functions */
40
41			static int sort_by_id(Way a,Way b);
42			static int sort_by_name(Way a,Way b);
43
44
45			/*++++++++++++++++++++++++++++++++++++++
46			Load in a way list from a file.
47
48			const char *filename The name of the file to load.
49			++++++++++++++++++++++++++++++++++++++*/
50
51	amb	8	void LoadWayList(const char *filename)
52	amb	7	{
53	amb	8	assert(!OSMWays);
54
55	amb	7	OSMWays=(Ways*)MapFile(filename);
56
57	amb	8	assert(OSMWays);
58	amb	7
59	amb	8	sorted=1;
60			loaded=1;
61	amb	7	}
62
63
64			/*++++++++++++++++++++++++++++++++++++++
65			Save the way list to a file.
66
67			const char *filename The name of the file to save.
68			++++++++++++++++++++++++++++++++++++++*/
69
70	amb	8	void SaveWayList(const char *filename)
71	amb	7	{
72			int retval;
73
74	amb	8	assert(!loaded); /* Must not be loaded */
75	amb	7
76	amb	8	assert(sorted); /* Must be sorted */
77	amb	7
78			retval=WriteFile(filename,OSMWays,sizeof(Ways)-sizeof(OSMWays->ways)+(OSMWays->number+OSMWays->number_str)*sizeof(Way));
79
80	amb	8	assert(!retval); /* Must be zero */
81	amb	7	}
82
83
84			/*++++++++++++++++++++++++++++++++++++++
85			Find a particular way.
86
87			Way *FindWay Returns a pointer to the way with the specified id.
88
89			way_t id The way id to look for.
90			++++++++++++++++++++++++++++++++++++++*/
91
92			Way *FindWay(way_t id)
93			{
94			int start=0;
95			int end=OSMWays->number-1;
96			int mid;
97
98	amb	8	assert(sorted); /* Must be sorted */
99	amb	7
100			/* Binary search - search key exact match only is required.
101			*
102			* # <- start \| Check mid and move start or end if it doesn't match
103			* # \|
104			* # \| Since an exact match is wanted we can set end=mid-1
105			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
106			* # \|
107			* # \| Eventually either end=start or end=start+1 and one of
108			* # <- end \| start or end is the wanted one.
109			*/
110
111			if(OSMWays->number==0) /* There are no ways */
112			return(NULL);
113			else if(id<OSMWays->ways[start].id) /* Check key is not before start */
114			return(NULL);
115			else if(id>OSMWays->ways[end].id) /* Check key is not after end */
116			return(NULL);
117			else
118			{
119			do
120			{
121			mid=(start+end)/2; /* Choose mid point */
122
123			if(OSMWays->ways[mid].id<id) /* Mid point is too low */
124			start=mid+1;
125			else if(OSMWays->ways[mid].id>id) /* Mid point is too high */
126			end=mid-1;
127			else /* Mid point is correct */
128			return(&OSMWays->ways[mid]);
129			}
130			while((end-start)>1);
131
132			if(OSMWays->ways[start].id==id) /* Start is correct */
133			return(&OSMWays->ways[start]);
134
135			if(OSMWays->ways[end].id==id) /* End is correct */
136			return(&OSMWays->ways[end]);
137			}
138
139			return(NULL);
140			}
141
142
143			/*++++++++++++++++++++++++++++++++++++++
144			Return the name of the way.
145
146			const char *WayName Returns the name.
147
148			Way *way The way whose name is to be found.
149			++++++++++++++++++++++++++++++++++++++*/
150
151			const char WayName(Way way)
152			{
153	amb	8	assert(sorted); /* Must be sorted */
154	amb	7
155			return((char*)&OSMWays->ways[(off_t)way->name]);
156			}
157
158
159			/*++++++++++++++++++++++++++++++++++++++
160			Append a way to a newly created way list (unsorted).
161
162			way_t id The way identification.
163
164			const char *name The name or reference of the way.
165	amb	8
166			speed_t speed The speed on the way.
167	amb	7	++++++++++++++++++++++++++++++++++++++*/
168
169	amb	8	void AppendWay(way_t id,const char *name,speed_t speed)
170	amb	7	{
171	amb	8	assert(!loaded); /* Must not be loaded */
172	amb	7
173	amb	8	assert(!sorted); /* Must not be sorted */
174
175	amb	7	/* Check that the whole thing is allocated. */
176
177			if(!OSMWays)
178			{
179	amb	8	alloced=INCREMENT;
180			OSMWays=(Ways)malloc(sizeof(Ways)-sizeof(OSMWays->ways)+allocedsizeof(Way));
181	amb	7
182			OSMWays->number=0;
183			OSMWays->number_str=0;
184
185	amb	8	names=(char*)malloc(allocedsizeof(char*));
186	amb	7	}
187
188			/* Check that the arrays have enough space. */
189
190	amb	8	if(OSMWays->number==alloced)
191	amb	7	{
192	amb	8	alloced+=INCREMENT;
193			OSMWays=(Ways)realloc((void)OSMWays,sizeof(Ways)-sizeof(OSMWays->ways)+alloced*sizeof(Way));
194	amb	7
195	amb	8	names=(char*)realloc((void)names,allocedsizeof(char));
196	amb	7	}
197
198			/* Insert the way */
199
200			names[OSMWays->number]=strcpy((char*)malloc(strlen(name)+1),name);
201
202			OSMWays->ways[OSMWays->number].id=id;
203	amb	8	OSMWays->ways[OSMWays->number].name=OSMWays->number;
204			OSMWays->ways[OSMWays->number].speed=speed;
205	amb	7
206			OSMWays->number++;
207
208			sorted=0;
209			}
210
211
212			/*++++++++++++++++++++++++++++++++++++++
213			Sort the way list.
214			++++++++++++++++++++++++++++++++++++++*/
215
216	amb	8	void SortWayList(void)
217	amb	7	{
218			char *name=NULL;
219			int i;
220
221	amb	8	assert(!loaded); /* Must not be loaded */
222
223	amb	7	/* Sort the ways by name */
224
225			qsort(OSMWays->ways,OSMWays->number,sizeof(Way),(int ()(const void,const void*))sort_by_name);
226
227			for(i=0;i<OSMWays->number;i++)
228			{
229	amb	8	if(name && !strcmp(name,names[OSMWays->ways[i].name])) /* Same name */
230	amb	7	{
231	amb	8	free(names[OSMWays->ways[i].name]);
232	amb	7	OSMWays->ways[i].name=OSMWays->ways[i-1].name;
233			}
234			else /* Different name */
235			{
236	amb	8	name=names[OSMWays->ways[i].name];
237	amb	7
238	amb	8	if((OSMWays->number+OSMWays->number_str+strlen(name)/sizeof(Way)+1)>=alloced)
239	amb	7	{
240	amb	8	alloced+=INCREMENT;
241	amb	7
242	amb	8	OSMWays=(Ways)realloc((void)OSMWays,sizeof(Ways)-sizeof(OSMWays->ways)+alloced*sizeof(Way));
243	amb	7	}
244
245			strcpy((char*)&OSMWays->ways[OSMWays->number+OSMWays->number_str],name);
246			free(name);
247
248	amb	8	OSMWays->ways[i].name=OSMWays->number+OSMWays->number_str;
249			name=(char*)&OSMWays->ways[OSMWays->ways[i].name];
250	amb	7
251			OSMWays->number_str+=strlen(name)/sizeof(Way)+1;
252			}
253			}
254
255			/* Sort the ways by id */
256
257			qsort(OSMWays->ways,OSMWays->number,sizeof(Way),(int ()(const void,const void*))sort_by_id);
258
259			sorted=1;
260			}
261
262
263			/*++++++++++++++++++++++++++++++++++++++
264			Sort the ways into id order.
265
266			int sort_by_id Returns the comparison of the id fields.
267
268			Way *a The first Way.
269
270			Way *b The second Way.
271			++++++++++++++++++++++++++++++++++++++*/
272
273			static int sort_by_id(Way a,Way b)
274			{
275			way_t a_id=a->id;
276			way_t b_id=b->id;
277
278			return(a_id-b_id);
279			}
280
281
282			/*++++++++++++++++++++++++++++++++++++++
283			Sort the ways into name order.
284
285			int sort_by_name Returns the comparison of the name fields.
286
287			Way *a The first Way.
288
289			Way *b The second Way.
290			++++++++++++++++++++++++++++++++++++++*/
291
292			static int sort_by_name(Way a,Way b)
293			{
294	amb	8	char *a_name=names[a->name];
295			char *b_name=names[b->name];
296	amb	7
297			return(strcmp(a_name,b_name));
298			}