trunk/src/nodes.c

/***************************************
 $Header: /home/amb/CVS/routino/src/nodes.c,v 1.3 2009-01-04 17:51:23 amb Exp $

 Node 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 "functions.h"
#include "types.h"

#define INCREMENT 256*1024

/*+ The list of nodes +*/
Nodes *OSMNodes=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;

/* Functions */

static int sort_by_id(Node *a,Node *b);


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

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

void LoadNodeList(const char *filename)
{
 assert(!OSMNodes);             /* Must be NULL */

 OSMNodes=(Nodes*)MapFile(filename);

 assert(OSMNodes);              /* Must be non-NULL */

 sorted=1;
 loaded=1;
}


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

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

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

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

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

 retval=WriteFile(filename,OSMNodes,sizeof(Nodes)-sizeof(OSMNodes->nodes)+OSMNodes->number*sizeof(Node));

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


/*++++++++++++++++++++++++++++++++++++++
  Find a particular node.

  Node *FindNode Returns a pointer to the node with the specified id.

  node_t id The node id to look for.
  ++++++++++++++++++++++++++++++++++++++*/

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

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

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

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

 return(NULL);
}


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

  node_t id The node identification.

  latlong_t latitude The latitude of the node.

  latlong_t longitude The longitude of the node.
  ++++++++++++++++++++++++++++++++++++++*/

void AppendNode(node_t id,latlong_t latitude,latlong_t longitude)
{
 assert(!loaded);               /* Must not be loaded */

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

 if(!OSMNodes)
   {
    alloced=INCREMENT;
    OSMNodes=(Nodes*)malloc(sizeof(Nodes)-sizeof(OSMNodes->nodes)+alloced*sizeof(Node));

    OSMNodes->number=0;
   }

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

 if(OSMNodes->number==alloced)
   {
    alloced+=INCREMENT;
    OSMNodes=(Nodes*)realloc((void*)OSMNodes,sizeof(Nodes)-sizeof(OSMNodes->nodes)+alloced*sizeof(Node));
   }

 /* Insert the node */

 OSMNodes->nodes[OSMNodes->number].id=id;
 OSMNodes->nodes[OSMNodes->number].latitude=latitude;
 OSMNodes->nodes[OSMNodes->number].longitude=longitude;

 OSMNodes->number++;

 sorted=0;
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the node list.
  ++++++++++++++++++++++++++++++++++++++*/

void SortNodeList(void)
{
 assert(!loaded);               /* Must not be loaded */

 qsort(OSMNodes->nodes,OSMNodes->number,sizeof(Node),(int (*)(const void*,const void*))sort_by_id);

 sorted=1;
}


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

  int sort_by_id Returns the comparison of the id fields.

  Node *a The first Node.

  Node *b The second Node.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_id(Node *a,Node *b)
{
 node_t a_id=a->id;
 node_t b_id=b->id;

 return(a_id-b_id);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/nodes.c,v 1.3 2009-01-04 17:51:23 amb Exp $
3
4	Node 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
18	#include "functions.h"
19	#include "types.h"
20
21	#define INCREMENT 256*1024
22
23	/+ The list of nodes +/
24	Nodes *OSMNodes=NULL;
25
26	/+ Is the data sorted and therefore searchable? +/
27	static int sorted=0;
28
29	/+ Is the data loaded from a file and therefore read-only? +/
30	static int loaded=0;
31
32	/+ How many entries are allocated? +/
33	static size_t alloced=0;
34
35	/* Functions */
36
37	static int sort_by_id(Node a,Node b);
38
39
40	/*++++++++++++++++++++++++++++++++++++++
41	Load in a node list from a file.
42
43	const char *filename The name of the file to load.
44	++++++++++++++++++++++++++++++++++++++*/
45
46	void LoadNodeList(const char *filename)
47	{
48	assert(!OSMNodes); /* Must be NULL */
49
50	OSMNodes=(Nodes*)MapFile(filename);
51
52	assert(OSMNodes); /* Must be non-NULL */
53
54	sorted=1;
55	loaded=1;
56	}
57
58
59	/*++++++++++++++++++++++++++++++++++++++
60	Save the node list to a file.
61
62	const char *filename The name of the file to save.
63	++++++++++++++++++++++++++++++++++++++*/
64
65	void SaveNodeList(const char *filename)
66	{
67	int retval;
68
69	assert(!loaded); /* Must not be loaded */
70
71	assert(sorted); /* Must be sorted */
72
73	retval=WriteFile(filename,OSMNodes,sizeof(Nodes)-sizeof(OSMNodes->nodes)+OSMNodes->number*sizeof(Node));
74
75	assert(!retval); /* Must be zero */
76	}
77
78
79	/*++++++++++++++++++++++++++++++++++++++
80	Find a particular node.
81
82	Node *FindNode Returns a pointer to the node with the specified id.
83
84	node_t id The node id to look for.
85	++++++++++++++++++++++++++++++++++++++*/
86
87	Node *FindNode(node_t id)
88	{
89	int start=0;
90	int end=OSMNodes->number-1;
91	int mid;
92
93	assert(sorted); /* Must be sorted */
94
95	/* Binary search - search key exact match only is required.
96	*
97	* # <- start \| Check mid and move start or end if it doesn't match
98	* # \|
99	* # \| Since an exact match is wanted we can set end=mid-1
100	* # <- mid \| or start=mid+1 because we know that mid doesn't match.
101	* # \|
102	* # \| Eventually either end=start or end=start+1 and one of
103	* # <- end \| start or end is the wanted one.
104	*/
105
106	if(OSMNodes->number==0) /* There are no nodes */
107	return(NULL);
108	else if(id<OSMNodes->nodes[start].id) /* Check key is not before start */
109	return(NULL);
110	else if(id>OSMNodes->nodes[end].id) /* Check key is not after end */
111	return(NULL);
112	else
113	{
114	do
115	{
116	mid=(start+end)/2; /* Choose mid point */
117
118	if(OSMNodes->nodes[mid].id<id) /* Mid point is too low */
119	start=mid+1;
120	else if(OSMNodes->nodes[mid].id>id) /* Mid point is too high */
121	end=mid-1;
122	else /* Mid point is correct */
123	return(&OSMNodes->nodes[mid]);
124	}
125	while((end-start)>1);
126
127	if(OSMNodes->nodes[start].id==id) /* Start is correct */
128	return(&OSMNodes->nodes[start]);
129
130	if(OSMNodes->nodes[end].id==id) /* End is correct */
131	return(&OSMNodes->nodes[end]);
132	}
133
134	return(NULL);
135	}
136
137
138	/*++++++++++++++++++++++++++++++++++++++
139	Append a node to a newly created node list (unsorted).
140
141	node_t id The node identification.
142
143	latlong_t latitude The latitude of the node.
144
145	latlong_t longitude The longitude of the node.
146	++++++++++++++++++++++++++++++++++++++*/
147
148	void AppendNode(node_t id,latlong_t latitude,latlong_t longitude)
149	{
150	assert(!loaded); /* Must not be loaded */
151
152	/* Check that the whole thing is allocated. */
153
154	if(!OSMNodes)
155	{
156	alloced=INCREMENT;
157	OSMNodes=(Nodes)malloc(sizeof(Nodes)-sizeof(OSMNodes->nodes)+allocedsizeof(Node));
158
159	OSMNodes->number=0;
160	}
161
162	/* Check that the arrays have enough space. */
163
164	if(OSMNodes->number==alloced)
165	{
166	alloced+=INCREMENT;
167	OSMNodes=(Nodes)realloc((void)OSMNodes,sizeof(Nodes)-sizeof(OSMNodes->nodes)+alloced*sizeof(Node));
168	}
169
170	/* Insert the node */
171
172	OSMNodes->nodes[OSMNodes->number].id=id;
173	OSMNodes->nodes[OSMNodes->number].latitude=latitude;
174	OSMNodes->nodes[OSMNodes->number].longitude=longitude;
175
176	OSMNodes->number++;
177
178	sorted=0;
179	}
180
181
182	/*++++++++++++++++++++++++++++++++++++++
183	Sort the node list.
184	++++++++++++++++++++++++++++++++++++++*/
185
186	void SortNodeList(void)
187	{
188	assert(!loaded); /* Must not be loaded */
189
190	qsort(OSMNodes->nodes,OSMNodes->number,sizeof(Node),(int ()(const void,const void*))sort_by_id);
191
192	sorted=1;
193	}
194
195
196	/*++++++++++++++++++++++++++++++++++++++
197	Sort the nodes into id order.
198
199	int sort_by_id Returns the comparison of the id fields.
200
201	Node *a The first Node.
202
203	Node *b The second Node.
204	++++++++++++++++++++++++++++++++++++++*/
205
206	static int sort_by_id(Node a,Node b)
207	{
208	node_t a_id=a->id;
209	node_t b_id=b->id;
210
211	return(a_id-b_id);
212	}