trunk/src/ways.c

/***************************************
 $Header: /home/amb/CVS/routino/src/ways.c,v 1.4 2009-01-10 11:53:48 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 "ways.h"


/*+ A temporary variable used when sorting +*/
static char **sort_names;

/* Functions */

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


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new way list.

  WaysMem *NewWayList Returns the way list.
  ++++++++++++++++++++++++++++++++++++++*/

WaysMem *NewWayList(void)
{
 WaysMem *ways;

 ways=(WaysMem*)malloc(sizeof(WaysMem));

 ways->alloced=INCREMENT_WAYS;
 ways->number=0;
 ways->number_str=0;
 ways->sorted=0;

 ways->ways=(Ways*)malloc(sizeof(Ways)+ways->alloced*sizeof(Way));
 ways->names=(char**)malloc(ways->alloced*sizeof(char*));

 return(ways);
}


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

  Ways* LoadWayList Returns the way list.

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

Ways *LoadWayList(const char *filename)
{
 return((Ways*)MapFile(filename));
}


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

  Ways* SaveWayList Returns the way list that has just been saved.

  WaysMem* ways The set of ways to save.

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

Ways *SaveWayList(WaysMem* ways,const char *filename)
{
#ifdef NBINS_WAYS
 int i,bin=0;
#endif

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

 ways->ways->number=ways->number;

#ifdef NBINS_WAYS
 for(i=0;i<ways->number;i++)
    for(;bin<=(ways->ways->ways[i].id%NBINS_WAYS);bin++)
       ways->ways->offset[bin]=i;

 for(;bin<=NBINS_WAYS;bin++)
    ways->ways->offset[bin]=ways->number;
#endif

 if(WriteFile(filename,(void*)ways->ways,sizeof(Ways)-sizeof(ways->ways->ways)+(ways->number+ways->number_str)*sizeof(Way)))
    assert(0);

 free(ways->names);
 free(ways->ways);
 free(ways);

 return(LoadWayList(filename));
}


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

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

  Ways* ways The set of ways to process.

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

Way *FindWay(Ways* ways,way_t id)
{
#ifdef NBINS_WAYS
 int bin=id%NBINS_WAYS;
 int start=ways->offset[bin];
 int end=ways->offset[bin+1]-1;
#else
 int start=0;
 int end=ways->number-1;
#endif
 int mid;

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

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

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

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

 return(NULL);
}


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

  const char *WayName Returns the name.

  Ways* ways The set of ways to process.

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

const char *WayName(Ways* ways,Way *way)
{
 return((char*)&ways->ways[way->name]);
}


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

  WaysMem* ways The set of ways to process.

  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(WaysMem* ways,way_t id,const char *name,speed_t speed)
{
 /* Check that the array has enough space. */

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

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

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

 /* Insert the way */

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

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

 ways->number++;

 ways->sorted=0;
}


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

  WaysMem* ways The set of ways to process.
  ++++++++++++++++++++++++++++++++++++++*/

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

 /* Sort the ways by name */

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

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

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

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

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

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

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

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

 /* Sort the ways by id */

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

 ways->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;

#ifdef NBINS_WAYS
 int a_bin=a->id%NBINS_WAYS;
 int b_bin=b->id%NBINS_WAYS;

 if(a_bin!=b_bin)
    return(a_bin-b_bin);
#endif

 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=sort_names[a->name];
 char *b_name=sort_names[b->name];

 return(strcmp(a_name,b_name));
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/ways.c,v 1.4 2009-01-10 11:53:48 amb Exp $
3
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 "ways.h"
21
22
23	/+ A temporary variable used when sorting +/
24	static char **sort_names;
25
26	/* Functions */
27
28	static int sort_by_id(Way a,Way b);
29	static int sort_by_name(Way a,Way b);
30
31
32	/*++++++++++++++++++++++++++++++++++++++
33	Allocate a new way list.
34
35	WaysMem *NewWayList Returns the way list.
36	++++++++++++++++++++++++++++++++++++++*/
37
38	WaysMem *NewWayList(void)
39	{
40	WaysMem *ways;
41
42	ways=(WaysMem*)malloc(sizeof(WaysMem));
43
44	ways->alloced=INCREMENT_WAYS;
45	ways->number=0;
46	ways->number_str=0;
47	ways->sorted=0;
48
49	ways->ways=(Ways)malloc(sizeof(Ways)+ways->allocedsizeof(Way));
50	ways->names=(char*)malloc(ways->allocedsizeof(char*));
51
52	return(ways);
53	}
54
55
56	/*++++++++++++++++++++++++++++++++++++++
57	Load in a way list from a file.
58
59	Ways* LoadWayList Returns the way list.
60
61	const char *filename The name of the file to load.
62	++++++++++++++++++++++++++++++++++++++*/
63
64	Ways LoadWayList(const char filename)
65	{
66	return((Ways*)MapFile(filename));
67	}
68
69
70	/*++++++++++++++++++++++++++++++++++++++
71	Save the way list to a file.
72
73	Ways* SaveWayList Returns the way list that has just been saved.
74
75	WaysMem* ways The set of ways to save.
76
77	const char *filename The name of the file to save.
78	++++++++++++++++++++++++++++++++++++++*/
79
80	Ways SaveWayList(WaysMem ways,const char *filename)
81	{
82	#ifdef NBINS_WAYS
83	int i,bin=0;
84	#endif
85
86	assert(ways->sorted); /* Must be sorted */
87
88	ways->ways->number=ways->number;
89
90	#ifdef NBINS_WAYS
91	for(i=0;i<ways->number;i++)
92	for(;bin<=(ways->ways->ways[i].id%NBINS_WAYS);bin++)
93	ways->ways->offset[bin]=i;
94
95	for(;bin<=NBINS_WAYS;bin++)
96	ways->ways->offset[bin]=ways->number;
97	#endif
98
99	if(WriteFile(filename,(void)ways->ways,sizeof(Ways)-sizeof(ways->ways->ways)+(ways->number+ways->number_str)sizeof(Way)))
100	assert(0);
101
102	free(ways->names);
103	free(ways->ways);
104	free(ways);
105
106	return(LoadWayList(filename));
107	}
108
109
110	/*++++++++++++++++++++++++++++++++++++++
111	Find a particular way.
112
113	Way *FindWay Returns a pointer to the way with the specified id.
114
115	Ways* ways The set of ways to process.
116
117	way_t id The way id to look for.
118	++++++++++++++++++++++++++++++++++++++*/
119
120	Way FindWay(Ways ways,way_t id)
121	{
122	#ifdef NBINS_WAYS
123	int bin=id%NBINS_WAYS;
124	int start=ways->offset[bin];
125	int end=ways->offset[bin+1]-1;
126	#else
127	int start=0;
128	int end=ways->number-1;
129	#endif
130	int mid;
131
132	/* Binary search - search key exact match only is required.
133	*
134	* # <- start \| Check mid and move start or end if it doesn't match
135	* # \|
136	* # \| Since an exact match is wanted we can set end=mid-1
137	* # <- mid \| or start=mid+1 because we know that mid doesn't match.
138	* # \|
139	* # \| Eventually either end=start or end=start+1 and one of
140	* # <- end \| start or end is the wanted one.
141	*/
142
143	if(end<start) /* There are no ways */
144	return(NULL);
145	else if(id<ways->ways[start].id) /* Check key is not before start */
146	return(NULL);
147	else if(id>ways->ways[end].id) /* Check key is not after end */
148	return(NULL);
149	else
150	{
151	do
152	{
153	mid=(start+end)/2; /* Choose mid point */
154
155	if(ways->ways[mid].id<id) /* Mid point is too low */
156	start=mid+1;
157	else if(ways->ways[mid].id>id) /* Mid point is too high */
158	end=mid-1;
159	else /* Mid point is correct */
160	return(&ways->ways[mid]);
161	}
162	while((end-start)>1);
163
164	if(ways->ways[start].id==id) /* Start is correct */
165	return(&ways->ways[start]);
166
167	if(ways->ways[end].id==id) /* End is correct */
168	return(&ways->ways[end]);
169	}
170
171	return(NULL);
172	}
173
174
175	/*++++++++++++++++++++++++++++++++++++++
176	Return the name of the way.
177
178	const char *WayName Returns the name.
179
180	Ways* ways The set of ways to process.
181
182	Way *way The way whose name is to be found.
183	++++++++++++++++++++++++++++++++++++++*/
184
185	const char WayName(Ways ways,Way *way)
186	{
187	return((char*)&ways->ways[way->name]);
188	}
189
190
191	/*++++++++++++++++++++++++++++++++++++++
192	Append a way to a newly created way list (unsorted).
193
194	WaysMem* ways The set of ways to process.
195
196	way_t id The way identification.
197
198	const char *name The name or reference of the way.
199
200	speed_t speed The speed on the way.
201	++++++++++++++++++++++++++++++++++++++*/
202
203	void AppendWay(WaysMem* ways,way_t id,const char *name,speed_t speed)
204	{
205	/* Check that the array has enough space. */
206
207	if(ways->number==ways->alloced)
208	{
209	ways->alloced+=INCREMENT_WAYS;
210
211	ways->ways=(Ways)realloc((void)ways->ways,sizeof(Ways)+ways->alloced*sizeof(Way));
212	ways->names=(char*)realloc((void)ways->names,ways->allocedsizeof(char));
213	}
214
215	assert(!ways->sorted); /* Must be sorted */
216
217	/* Insert the way */
218
219	ways->names[ways->number]=strcpy((char*)malloc(strlen(name)+1),name);
220
221	ways->ways->ways[ways->number].id=id;
222	ways->ways->ways[ways->number].name=ways->number;
223	ways->ways->ways[ways->number].speed=speed;
224
225	ways->number++;
226
227	ways->sorted=0;
228	}
229
230
231	/*++++++++++++++++++++++++++++++++++++++
232	Sort the way list.
233
234	WaysMem* ways The set of ways to process.
235	++++++++++++++++++++++++++++++++++++++*/
236
237	void SortWayList(WaysMem* ways)
238	{
239	char *name=NULL;
240	int i;
241
242	/* Sort the ways by name */
243
244	sort_names=ways->names;
245	qsort(ways->ways->ways,ways->number,sizeof(Way),(int ()(const void,const void*))sort_by_name);
246
247	/* Setup the offsets for the names in the way array */
248
249	for(i=0;i<ways->number;i++)
250	{
251	if(name && !strcmp(name,ways->names[ways->ways->ways[i].name])) /* Same name */
252	{
253	free(ways->names[ways->ways->ways[i].name]);
254	ways->ways->ways[i].name=ways->ways->ways[i-1].name;
255	}
256	else /* Different name */
257	{
258	name=ways->names[ways->ways->ways[i].name];
259
260	if((ways->number+ways->number_str+strlen(name)/sizeof(Way)+1)>=ways->alloced)
261	{
262	ways->alloced+=INCREMENT_WAYS;
263
264	ways->ways=(Ways)realloc((void)ways->ways,sizeof(Ways)+ways->alloced*sizeof(Way));
265	}
266
267	strcpy((char*)&ways->ways->ways[ways->number+ways->number_str],name);
268	free(name);
269
270	ways->ways->ways[i].name=ways->number+ways->number_str;
271	name=(char*)&ways->ways->ways[ways->ways->ways[i].name];
272
273	ways->number_str+=strlen(name)/sizeof(Way)+1;
274	}
275	}
276
277	/* Sort the ways by id */
278
279	qsort(ways->ways->ways,ways->number,sizeof(Way),(int ()(const void,const void*))sort_by_id);
280
281	ways->sorted=1;
282	}
283
284
285	/*++++++++++++++++++++++++++++++++++++++
286	Sort the ways into id order.
287
288	int sort_by_id Returns the comparison of the id fields.
289
290	Way *a The first Way.
291
292	Way *b The second Way.
293	++++++++++++++++++++++++++++++++++++++*/
294
295	static int sort_by_id(Way a,Way b)
296	{
297	way_t a_id=a->id;
298	way_t b_id=b->id;
299
300	#ifdef NBINS_WAYS
301	int a_bin=a->id%NBINS_WAYS;
302	int b_bin=b->id%NBINS_WAYS;
303
304	if(a_bin!=b_bin)
305	return(a_bin-b_bin);
306	#endif
307
308	return(a_id-b_id);
309	}
310
311
312	/*++++++++++++++++++++++++++++++++++++++
313	Sort the ways into name order.
314
315	int sort_by_name Returns the comparison of the name fields.
316
317	Way *a The first Way.
318
319	Way *b The second Way.
320	++++++++++++++++++++++++++++++++++++++*/
321
322	static int sort_by_name(Way a,Way b)
323	{
324	char *a_name=sort_names[a->name];
325	char *b_name=sort_names[b->name];
326
327	return(strcmp(a_name,b_name));
328	}