Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

ViewVC logotype

Contents of /trunk/src/waysx.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 215 - (show annotations) (download) (as text)
Thu Jul 2 19:41:38 2009 UTC (15 years, 9 months ago) by amb
File MIME type: text/x-csrc
File size: 9446 byte(s)
Handle duplicate ways.

1 /***************************************
2 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.11 2009-07-02 19:41:38 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 index_t 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->number*sizeof(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->xnumber==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->xnumber].id=id;
206 waysx->xdata[waysx->xnumber].name=strcpy((char*)malloc(strlen(name)+1),name);
207 waysx->xdata[waysx->xnumber].way=&waysx->wdata[waysx->xnumber];
208
209 memset(&waysx->wdata[waysx->xnumber],0,sizeof(Way));
210
211 waysx->xnumber++;
212
213 waysx->sorted=0;
214
215 return(&waysx->wdata[waysx->xnumber-1]);
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 index_t i,j;
229 int duplicate;
230
231 assert(waysx->xdata); /* Must have xdata filled in */
232 assert(waysx->wdata); /* Must have wdata filled in */
233
234 /* Sort the ways by id */
235
236 waysx->idata=(WayX**)malloc(waysx->xnumber*sizeof(WayX*));
237
238 do
239 {
240 waysx->number=0;
241
242 for(i=0;i<waysx->xnumber;i++)
243 if(waysx->xdata[i].id!=NO_WAY)
244 {
245 waysx->idata[waysx->number]=&waysx->xdata[i];
246 waysx->number++;
247 }
248
249 qsort(waysx->idata,waysx->number,sizeof(WayX*),(int (*)(const void*,const void*))sort_by_id);
250
251 duplicate=0;
252
253 for(i=1;i<waysx->number;i++)
254 {
255 if(waysx->idata[i]->id==waysx->idata[i-1]->id &&
256 waysx->idata[i]->id!=NO_WAY)
257 {
258 waysx->idata[i-1]->id=NO_WAY;
259 duplicate++;
260 }
261 }
262
263 if(duplicate)
264 printf(" - %d duplicates found; trying again.\nSorting Ways",duplicate); fflush(stdout);
265 }
266 while(duplicate);
267
268 /* Sort the ways by name and way properties */
269
270 waysx->ndata=(WayX**)malloc(waysx->number*sizeof(WayX*));
271
272 for(i=0;i<waysx->number;i++)
273 waysx->ndata[i]=waysx->idata[i];
274
275 qsort(waysx->ndata,waysx->number,sizeof(WayX*),(int (*)(const void*,const void*))sort_by_name_and_properties);
276
277 /* Allocate the new data for names */
278
279 waysx->names=(char*)malloc(waysx->alloced*sizeof(char));
280
281 /* Allocate the data for unique ways */
282
283 uniq_ways=(Way*)malloc(waysx->number*sizeof(Way));
284
285 /* Setup the offsets for the names in the way array */
286
287 for(i=0,j=0;i<waysx->number;i++)
288 {
289 if(i && !strcmp(waysx->ndata[i]->name,waysx->ndata[i-1]->name)) /* Same name */
290 {
291 waysx->ndata[i]->way->name=waysx->ndata[i-1]->way->name;
292
293 if(!WaysCompare(waysx->ndata[i]->way,waysx->ndata[i-1]->way)) /* Same properties */
294 waysx->ndata[i]->way=waysx->ndata[i-1]->way;
295 else
296 {
297 uniq_ways[j]=*waysx->ndata[i]->way;
298 waysx->ndata[i]->way=&uniq_ways[j++];
299 }
300 }
301 else /* Different name */
302 {
303 if((waysx->length+strlen(waysx->ndata[i]->name)+1)>=waysx->alloced)
304 {
305 waysx->alloced+=INCREMENT_WAYS;
306
307 waysx->names=(char*)realloc((void*)waysx->names,waysx->alloced*sizeof(char));
308 }
309
310 strcpy(&waysx->names[waysx->length],waysx->ndata[i]->name);
311
312 waysx->ndata[i]->way->name=waysx->length;
313
314 waysx->length+=strlen(waysx->ndata[i]->name)+1;
315
316 uniq_ways[j]=*waysx->ndata[i]->way;
317 waysx->ndata[i]->way=&uniq_ways[j++];
318 }
319 }
320
321 waysx->wnumber=j;
322
323 free(waysx->wdata);
324
325 waysx->wdata=uniq_ways;
326
327 waysx->sorted=1;
328 }
329
330
331 /*++++++++++++++++++++++++++++++++++++++
332 Sort the ways into id order.
333
334 int sort_by_id Returns the comparison of the id fields.
335
336 Way **a The first Way.
337
338 Way **b The second Way.
339 ++++++++++++++++++++++++++++++++++++++*/
340
341 static int sort_by_id(WayX **a,WayX **b)
342 {
343 way_t a_id=(*a)->id;
344 way_t b_id=(*b)->id;
345
346 if(a_id<b_id)
347 return(-1);
348 else if(a_id>b_id)
349 return(1);
350 else
351 return(0);
352 }
353
354
355 /*++++++++++++++++++++++++++++++++++++++
356 Sort the ways into name and properties order.
357
358 int sort_by_name_and_properties Returns the comparison of the name and properties fields.
359
360 Way **a The first Way.
361
362 Way **b The second Way.
363 ++++++++++++++++++++++++++++++++++++++*/
364
365 static int sort_by_name_and_properties(WayX **a,WayX **b)
366 {
367 char *a_name=(*a)->name;
368 char *b_name=(*b)->name;
369 int name_compare;
370
371 name_compare=strcmp(a_name,b_name);
372
373 if(name_compare)
374 return(name_compare);
375 else
376 {
377 Way *a_way=(*a)->way;
378 Way *b_way=(*b)->way;
379
380 return(WaysCompare(a_way,b_way));
381 }
382 }

Properties

Name Value
cvs:description Extended ways functions.