Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Annotation of /trunk/src/results.c
Parent Directory
|
Revision Log
Revision 67 -
(hide annotations)
(download)
(as text)
Thu Jan 22 19:26:17 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 10645 byte(s)
Thu Jan 22 19:26:17 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 10645 byte(s)
Move queue functions into results.c.
1 | amb | 29 | /*************************************** |
2 | amb | 67 | $Header: /home/amb/CVS/routino/src/results.c,v 1.3 2009-01-22 19:26:17 amb Exp $ |
3 | amb | 29 | |
4 | Result 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 <string.h> | ||
17 | #include <stdlib.h> | ||
18 | |||
19 | #include "results.h" | ||
20 | |||
21 | |||
22 | amb | 67 | #define QUEUE_INCREMENT 1024 |
23 | |||
24 | /*+ A queue of results. +*/ | ||
25 | typedef struct _Queue | ||
26 | { | ||
27 | uint32_t alloced; /*+ The amount of space allocated for results in the array. +*/ | ||
28 | uint32_t number; /*+ The number of occupied results in the array. +*/ | ||
29 | uint32_t *queue; /*+ An array of offsets into the results array. +*/ | ||
30 | } | ||
31 | Queue; | ||
32 | |||
33 | /*+ The queue of nodes. +*/ | ||
34 | static Queue queue={0,0,NULL}; | ||
35 | |||
36 | |||
37 | amb | 29 | /*++++++++++++++++++++++++++++++++++++++ |
38 | Allocate a new results list. | ||
39 | |||
40 | Results *NewResultsList Returns the results list. | ||
41 | ++++++++++++++++++++++++++++++++++++++*/ | ||
42 | |||
43 | Results *NewResultsList(void) | ||
44 | { | ||
45 | Results *results; | ||
46 | #if NBINS_RESULTS | ||
47 | int i; | ||
48 | #endif | ||
49 | |||
50 | results=(Results*)malloc(sizeof(Results)); | ||
51 | |||
52 | results->alloced=INCREMENT_RESULTS; | ||
53 | amb | 45 | results->number=0; |
54 | amb | 29 | |
55 | #if NBINS_RESULTS | ||
56 | for(i=0;i<NBINS_RESULTS;i++) | ||
57 | { | ||
58 | amb | 45 | results->numbin[i]=0; |
59 | |||
60 | results->offsets[i]=(uint32_t*)malloc(results->alloced*sizeof(uint32_t)); | ||
61 | amb | 29 | } |
62 | amb | 45 | |
63 | results->results=(Result*)malloc(results->alloced*NBINS_RESULTS*sizeof(Result)); | ||
64 | amb | 29 | #else |
65 | amb | 45 | results->offsets=(uint32_t*)malloc(results->alloced*sizeof(uint32_t)); |
66 | |||
67 | results->data=(Result*)malloc(results->alloced*sizeof(Result)); | ||
68 | amb | 29 | #endif |
69 | |||
70 | return(results); | ||
71 | } | ||
72 | |||
73 | |||
74 | /*++++++++++++++++++++++++++++++++++++++ | ||
75 | Allocate a new results list. | ||
76 | |||
77 | Results *results The results list to be destroyed. | ||
78 | ++++++++++++++++++++++++++++++++++++++*/ | ||
79 | |||
80 | void FreeResultsList(Results *results) | ||
81 | { | ||
82 | #if NBINS_RESULTS | ||
83 | int i; | ||
84 | #endif | ||
85 | |||
86 | #if NBINS_RESULTS | ||
87 | for(i=0;i<NBINS_RESULTS;i++) | ||
88 | amb | 45 | free(results->offsets[i]); |
89 | amb | 29 | #else |
90 | amb | 45 | free(results->offsets); |
91 | amb | 29 | #endif |
92 | |||
93 | amb | 45 | free(results->results); |
94 | |||
95 | amb | 29 | free(results); |
96 | } | ||
97 | |||
98 | |||
99 | /*++++++++++++++++++++++++++++++++++++++ | ||
100 | Insert a new result into the results data structure in the right order. | ||
101 | |||
102 | Result *insert_result Returns the result that has been inserted. | ||
103 | |||
104 | Results *results The results structure to insert into. | ||
105 | |||
106 | node_t node The node that is to be inserted into the results. | ||
107 | ++++++++++++++++++++++++++++++++++++++*/ | ||
108 | |||
109 | Result *InsertResult(Results *results,node_t node) | ||
110 | { | ||
111 | #ifdef NBINS_RESULTS | ||
112 | int bin=node%NBINS_RESULTS; | ||
113 | int start=0; | ||
114 | amb | 45 | int end=results->numbin[bin]-1; |
115 | uint32_t *offsetsp=results->offsets[bin]; | ||
116 | amb | 29 | int i; |
117 | #else | ||
118 | int start=0; | ||
119 | int end=results->number-1; | ||
120 | amb | 45 | uint32_t *offsetsp=results->offsets; |
121 | amb | 29 | #endif |
122 | int mid; | ||
123 | int insert=-1; | ||
124 | |||
125 | /* Check that the arrays have enough space. */ | ||
126 | |||
127 | amb | 45 | #ifdef NBINS_RESULTS |
128 | if(results->numbin[bin]==results->alloced) | ||
129 | amb | 29 | { |
130 | results->alloced+=INCREMENT_RESULTS; | ||
131 | |||
132 | for(i=0;i<NBINS_RESULTS;i++) | ||
133 | amb | 45 | results->offsets[i]=(uint32_t*)realloc((void*)results->offsets[i],results->alloced*sizeof(uint32_t)); |
134 | amb | 29 | |
135 | amb | 45 | offsetsp=results->offsets[bin]; |
136 | |||
137 | results->results=(Result*)realloc((void*)results->results,results->alloced*NBINS_RESULTS*sizeof(Result)); | ||
138 | } | ||
139 | amb | 29 | #else |
140 | amb | 45 | if(results->number==results->alloced) |
141 | { | ||
142 | results->alloced+=INCREMENT_RESULTS; | ||
143 | amb | 29 | |
144 | amb | 45 | results->offsets=(uint32_t*)realloc((void*)results->offsets[i],results->alloced*sizeof(uint32_t)); |
145 | |||
146 | offsetsp=results->offsets; | ||
147 | |||
148 | results->results=(Result*)realloc((void*)results->results,results->alloced*sizeof(Result)); | ||
149 | } | ||
150 | amb | 29 | #endif |
151 | |||
152 | /* Binary search - search key may not match, if not then insertion point required | ||
153 | * | ||
154 | * # <- start | Check mid and move start or end if it doesn't match | ||
155 | * # | | ||
156 | * # | Since there may not be an exact match we must set end=mid | ||
157 | * # <- mid | or start=mid because we know that mid doesn't match. | ||
158 | * # | | ||
159 | * # | Eventually end=start+1 and the insertion point is before | ||
160 | * # <- end | end (since it cannot be before the initial start or end). | ||
161 | */ | ||
162 | |||
163 | amb | 45 | if(end<start) /* There are no results */ |
164 | amb | 29 | insert=start; |
165 | amb | 45 | else if(node<results->results[offsetsp[start]].node) /* Check key is not before start */ |
166 | amb | 29 | insert=start; |
167 | amb | 45 | else if(node>results->results[offsetsp[end]].node) /* Check key is not after end */ |
168 | amb | 29 | insert=end+1; |
169 | else | ||
170 | { | ||
171 | do | ||
172 | { | ||
173 | amb | 45 | mid=(start+end)/2; /* Choose mid point */ |
174 | amb | 29 | |
175 | amb | 45 | if(results->results[offsetsp[mid]].node<node) /* Mid point is too low */ |
176 | amb | 29 | start=mid; |
177 | amb | 45 | else if(results->results[offsetsp[mid]].node>node) /* Mid point is too high */ |
178 | amb | 29 | end=mid; |
179 | else | ||
180 | assert(0); | ||
181 | } | ||
182 | while((end-start)>1); | ||
183 | |||
184 | insert=end; | ||
185 | } | ||
186 | |||
187 | /* Shuffle the array up */ | ||
188 | |||
189 | amb | 45 | #ifdef NBINS_RESULTS |
190 | if(insert!=results->numbin[bin]) | ||
191 | memmove(&offsetsp[insert+1],&offsetsp[insert],(results->numbin[bin]-insert)*sizeof(uint32_t)); | ||
192 | #else | ||
193 | if(insert!=results->number) | ||
194 | memmove(&offsetsp[insert+1],&offsetsp[insert],(results->number-insert)*sizeof(uint32_t)); | ||
195 | #endif | ||
196 | amb | 29 | |
197 | /* Insert the new entry */ | ||
198 | |||
199 | amb | 45 | offsetsp[insert]=results->number; |
200 | amb | 29 | |
201 | amb | 45 | results->number++; |
202 | amb | 29 | |
203 | amb | 45 | #ifdef NBINS_RESULTS |
204 | results->numbin[bin]++; | ||
205 | #endif | ||
206 | |||
207 | return(&results->results[offsetsp[insert]]); | ||
208 | amb | 29 | } |
209 | |||
210 | |||
211 | /*++++++++++++++++++++++++++++++++++++++ | ||
212 | Find a result, ordered by node. | ||
213 | |||
214 | Result *insert_result Returns the result that has been found. | ||
215 | |||
216 | Results *results The results structure to search. | ||
217 | |||
218 | node_t node The node that is to be found. | ||
219 | ++++++++++++++++++++++++++++++++++++++*/ | ||
220 | |||
221 | Result *FindResult(Results *results,node_t node) | ||
222 | { | ||
223 | #ifdef NBINS_RESULTS | ||
224 | int bin=node%NBINS_RESULTS; | ||
225 | int start=0; | ||
226 | amb | 45 | int end=results->numbin[bin]-1; |
227 | uint32_t *offsetsp=results->offsets[bin]; | ||
228 | amb | 29 | #else |
229 | int start=0; | ||
230 | int end=results->number-1; | ||
231 | amb | 45 | uint32_t *offsetsp=results->offsets; |
232 | amb | 29 | #endif |
233 | int mid; | ||
234 | |||
235 | /* Binary search - search key exact match only is required. | ||
236 | * | ||
237 | * # <- start | Check mid and move start or end if it doesn't match | ||
238 | * # | | ||
239 | * # | Since an exact match is wanted we can set end=mid-1 | ||
240 | * # <- mid | or start=mid+1 because we know that mid doesn't match. | ||
241 | * # | | ||
242 | * # | Eventually either end=start or end=start+1 and one of | ||
243 | * # <- end | start or end is the wanted one. | ||
244 | */ | ||
245 | |||
246 | amb | 45 | if(end<start) /* There are no results */ |
247 | amb | 29 | return(NULL); |
248 | amb | 45 | else if(node<results->results[offsetsp[start]].node) /* Check key is not before start */ |
249 | amb | 29 | return(NULL); |
250 | amb | 45 | else if(node>results->results[offsetsp[end]].node) /* Check key is not after end */ |
251 | amb | 29 | return(NULL); |
252 | else | ||
253 | { | ||
254 | do | ||
255 | { | ||
256 | amb | 45 | mid=(start+end)/2; /* Choose mid point */ |
257 | amb | 29 | |
258 | amb | 45 | if(results->results[offsetsp[mid]].node<node) /* Mid point is too low */ |
259 | amb | 29 | start=mid+1; |
260 | amb | 45 | else if(results->results[offsetsp[mid]].node>node) /* Mid point is too high */ |
261 | amb | 29 | end=mid-1; |
262 | amb | 45 | else /* Mid point is correct */ |
263 | return(&results->results[offsetsp[mid]]); | ||
264 | amb | 29 | } |
265 | while((end-start)>1); | ||
266 | |||
267 | amb | 45 | if(results->results[offsetsp[start]].node==node) /* Start is correct */ |
268 | return(&results->results[offsetsp[start]]); | ||
269 | amb | 29 | |
270 | amb | 45 | if(results->results[offsetsp[end]].node==node) /* End is correct */ |
271 | return(&results->results[offsetsp[end]]); | ||
272 | amb | 29 | } |
273 | |||
274 | return(NULL); | ||
275 | } | ||
276 | amb | 67 | |
277 | |||
278 | /*++++++++++++++++++++++++++++++++++++++ | ||
279 | Insert an item into the queue in the right order. | ||
280 | |||
281 | Results *results The set of results. | ||
282 | |||
283 | Result *result The result to insert into the queue. | ||
284 | ++++++++++++++++++++++++++++++++++++++*/ | ||
285 | |||
286 | void insert_in_queue(Results *results,Result *result) | ||
287 | { | ||
288 | int start=0; | ||
289 | int end=queue.number-1; | ||
290 | int mid; | ||
291 | int insert=-1; | ||
292 | |||
293 | /* Check that the whole thing is allocated. */ | ||
294 | |||
295 | if(!queue.queue) | ||
296 | { | ||
297 | queue.alloced=QUEUE_INCREMENT; | ||
298 | queue.number=0; | ||
299 | queue.queue=(uint32_t*)malloc(queue.alloced*sizeof(uint32_t)); | ||
300 | } | ||
301 | |||
302 | /* Check that the arrays have enough space. */ | ||
303 | |||
304 | if(queue.number==queue.alloced) | ||
305 | { | ||
306 | queue.alloced+=QUEUE_INCREMENT; | ||
307 | queue.queue=(uint32_t*)realloc((void*)queue.queue,queue.alloced*sizeof(uint32_t)); | ||
308 | } | ||
309 | |||
310 | /* Binary search - search key may not match, new insertion point required | ||
311 | * | ||
312 | * # <- start | Check mid and move start or end if it doesn't match | ||
313 | * # | | ||
314 | * # | Since there may not be an exact match we must set end=mid | ||
315 | * # <- mid | or start=mid because we know that mid doesn't match. | ||
316 | * # | | ||
317 | * # | Eventually end=start+1 and the insertion point is before | ||
318 | * # <- end | end (since it cannot be before the initial start or end). | ||
319 | */ | ||
320 | |||
321 | if(queue.number==0) /* There is nothing in the queue */ | ||
322 | insert=0; | ||
323 | else if(result->shortest.distance>results->results[queue.queue[start]].shortest.distance) /* Check key is not before start */ | ||
324 | insert=start; | ||
325 | else if(result->shortest.distance<results->results[queue.queue[end]].shortest.distance) /* Check key is not after end */ | ||
326 | insert=end+1; | ||
327 | else | ||
328 | { | ||
329 | do | ||
330 | { | ||
331 | mid=(start+end)/2; /* Choose mid point */ | ||
332 | |||
333 | if(results->results[queue.queue[mid]].shortest.distance>result->shortest.distance) /* Mid point is too low */ | ||
334 | start=mid; | ||
335 | else if(results->results[queue.queue[mid]].shortest.distance<result->shortest.distance) /* Mid point is too high */ | ||
336 | end=mid; | ||
337 | else /* Mid point is correct */ | ||
338 | { | ||
339 | if(&results->results[queue.queue[mid]]==result) | ||
340 | return; | ||
341 | |||
342 | insert=mid; | ||
343 | break; | ||
344 | } | ||
345 | } | ||
346 | while((end-start)>1); | ||
347 | |||
348 | if(insert==-1) | ||
349 | insert=end; | ||
350 | } | ||
351 | |||
352 | /* Shuffle the array up */ | ||
353 | |||
354 | if(insert!=queue.number) | ||
355 | memmove(&queue.queue[insert+1],&queue.queue[insert],(queue.number-insert)*sizeof(uint32_t)); | ||
356 | |||
357 | /* Insert the new entry */ | ||
358 | |||
359 | queue.queue[insert]=result-results->results; | ||
360 | |||
361 | queue.number++; | ||
362 | } | ||
363 | |||
364 | |||
365 | /*++++++++++++++++++++++++++++++++++++++ | ||
366 | Pop an item from the end of the queue. | ||
367 | |||
368 | Result *pop_from_queue Returns the top item. | ||
369 | |||
370 | Results *results The set of results that the queue is processing. | ||
371 | ++++++++++++++++++++++++++++++++++++++*/ | ||
372 | |||
373 | Result *pop_from_queue(Results *results) | ||
374 | { | ||
375 | if(queue.number) | ||
376 | return LookupResult(results,queue.queue[--queue.number]); | ||
377 | else | ||
378 | return NULL; | ||
379 | } |
Properties
Name | Value |
---|---|
cvs:description | Results data type. |