Routino SVN Repository Browser

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

ViewVC logotype

Annotation of /trunk/src/results.c

Parent Directory Parent Directory | Revision Log 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)
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.