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	amb	2	/***************************************
2	amb	8	$Header: /home/amb/CVS/routino/src/nodes.c,v 1.3 2009-01-04 17:51:23 amb Exp $
3	amb	2
4			Node data type functions.
5			****************/ /****************
6			Written by Andrew M. Bishop
7
8	amb	4	This file Copyright 2008,2009 Andrew M. Bishop
9	amb	2	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	amb	8	#include <assert.h>
16	amb	2	#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	amb	8	/+ 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	amb	2	/* 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	amb	8	void LoadNodeList(const char *filename)
47	amb	2	{
48	amb	8	assert(!OSMNodes); /* Must be NULL */
49
50	amb	2	OSMNodes=(Nodes*)MapFile(filename);
51
52	amb	8	assert(OSMNodes); /* Must be non-NULL */
53	amb	2
54	amb	8	sorted=1;
55			loaded=1;
56	amb	2	}
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	amb	8	void SaveNodeList(const char *filename)
66	amb	2	{
67			int retval;
68
69	amb	8	assert(!loaded); /* Must not be loaded */
70	amb	2
71	amb	8	assert(sorted); /* Must be sorted */
72	amb	2
73			retval=WriteFile(filename,OSMNodes,sizeof(Nodes)-sizeof(OSMNodes->nodes)+OSMNodes->number*sizeof(Node));
74
75	amb	8	assert(!retval); /* Must be zero */
76	amb	2	}
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	amb	8	assert(sorted); /* Must be sorted */
94	amb	2
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	amb	8	assert(!loaded); /* Must not be loaded */
151
152	amb	4	/* Check that the whole thing is allocated. */
153
154			if(!OSMNodes)
155			{
156	amb	8	alloced=INCREMENT;
157			OSMNodes=(Nodes)malloc(sizeof(Nodes)-sizeof(OSMNodes->nodes)+allocedsizeof(Node));
158	amb	4
159			OSMNodes->number=0;
160			}
161
162			/* Check that the arrays have enough space. */
163
164	amb	8	if(OSMNodes->number==alloced)
165	amb	2	{
166	amb	8	alloced+=INCREMENT;
167			OSMNodes=(Nodes)realloc((void)OSMNodes,sizeof(Nodes)-sizeof(OSMNodes->nodes)+alloced*sizeof(Node));
168	amb	2	}
169
170	amb	4	/* Insert the node */
171
172	amb	2	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	amb	8	void SortNodeList(void)
187	amb	2	{
188	amb	8	assert(!loaded); /* Must not be loaded */
189
190	amb	2	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			}