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/results.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1285 - (show annotations) (download) (as text)
Sat Apr 27 18:27:45 2013 UTC (11 years, 10 months ago) by amb
File MIME type: text/x-csrc
File size: 6246 byte(s)
Use a linked list to store the results in each bin rather than pre-allocated
pointers.

1 /***************************************
2 Result data type functions.
3
4 Part of the Routino routing software.
5 ******************/ /******************
6 This file Copyright 2008-2013 Andrew M. Bishop
7
8 This program is free software: you can redistribute it and/or modify
9 it under the terms of the GNU Affero General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU Affero General Public License for more details.
17
18 You should have received a copy of the GNU Affero General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>.
20 ***************************************/
21
22
23 #include <string.h>
24 #include <stdlib.h>
25
26 #include "results.h"
27
28 #include "logging.h"
29
30
31 #define HASH_NODE_SEGMENT(node,segment) ((node)^(segment<<4))
32
33
34 /*++++++++++++++++++++++++++++++++++++++
35 Allocate a new results list.
36
37 Results *NewResultsList Returns the results list.
38
39 int nbins The initial number of bins in the results array.
40 ++++++++++++++++++++++++++++++++++++++*/
41
42 Results *NewResultsList(int nbins)
43 {
44 Results *results;
45
46 results=(Results*)malloc(sizeof(Results));
47
48 results->nbins=1;
49 results->mask=0;
50 results->ncollisions=0;
51
52 while(nbins>>=1)
53 {
54 results->nbins<<=1;
55 results->mask=(results->mask<<1)|1;
56 results->ncollisions++;
57 }
58
59 results->number=0;
60
61 results->count=(uint8_t*)calloc(results->nbins,sizeof(uint8_t));
62 results->point=(Result**)calloc(results->nbins,sizeof(Result*));
63
64 results->ndata1=0;
65 results->ndata2=results->nbins>>2;
66
67 results->data=NULL;
68
69 results->start_node=NO_NODE;
70 results->prev_segment=NO_SEGMENT;
71
72 results->finish_node=NO_NODE;
73 results->last_segment=NO_SEGMENT;
74
75 return(results);
76 }
77
78
79 /*++++++++++++++++++++++++++++++++++++++
80 Free a results list.
81
82 Results *results The results list to be destroyed.
83 ++++++++++++++++++++++++++++++++++++++*/
84
85 void FreeResultsList(Results *results)
86 {
87 int i;
88
89 for(i=0;i<results->ndata1;i++)
90 free(results->data[i]);
91
92 free(results->data);
93
94 free(results->point);
95
96 free(results->count);
97
98 free(results);
99 }
100
101
102 /*++++++++++++++++++++++++++++++++++++++
103 Insert a new result into the results data structure in the right order.
104
105 Result *InsertResult Returns the result that has been inserted.
106
107 Results *results The results structure to insert into.
108
109 index_t node The node that is to be inserted into the results.
110
111 index_t segment The segment that is to be inserted into the results.
112 ++++++++++++++++++++++++++++++++++++++*/
113
114 Result *InsertResult(Results *results,index_t node,index_t segment)
115 {
116 Result *result;
117 int bin=HASH_NODE_SEGMENT(node,segment)&results->mask;
118
119 /* Check if we have hit the limit on the number of collisions per bin */
120
121 if(results->count[bin]==results->ncollisions)
122 {
123 int i;
124
125 results->nbins<<=1;
126 results->mask=(results->mask<<1)|1;
127 results->ncollisions++;
128
129 results->count=(uint8_t*)realloc((void*)results->count,results->nbins*sizeof(uint8_t));
130 results->point=(Result**)realloc((void*)results->point,results->nbins*sizeof(Result*));
131
132 for(i=0;i<results->nbins/2;i++)
133 {
134 Result *r=results->point[i];
135 Result **bin1,**bin2;
136
137 results->count[i] =0;
138 results->count[i+results->nbins/2]=0;
139
140 bin1=&results->point[i];
141 bin2=&results->point[i+results->nbins/2];
142
143 while(r)
144 {
145 Result *rh=r->hashnext;
146 int newbin=HASH_NODE_SEGMENT(r->node,r->segment)&results->mask;
147
148 r->hashnext=NULL;
149
150 if(newbin==i)
151 { *bin1=r; bin1=&r->hashnext; }
152 else
153 { *bin2=r; bin2=&r->hashnext; }
154
155 results->count[newbin]++;
156
157 r=rh;
158 }
159 }
160
161 bin=HASH_NODE_SEGMENT(node,segment)&results->mask;
162 }
163
164 /* Check if we need more data space allocated */
165
166 if((results->number%results->ndata2)==0)
167 {
168 results->ndata1++;
169
170 results->data=(Result**)realloc((void*)results->data,results->ndata1*sizeof(Result*));
171 results->data[results->ndata1-1]=(Result*)malloc(results->ndata2*sizeof(Result));
172 }
173
174 /* Insert the new entry */
175
176 result=&results->data[results->ndata1-1][results->number%results->ndata2];
177
178 result->hashnext=results->point[bin];
179
180 results->point[bin]=result;
181
182 results->count[bin]++;
183
184 results->number++;
185
186 /* Initialise the result */
187
188 result->node=node;
189 result->segment=segment;
190
191 result->prev=NULL;
192 result->next=NULL;
193
194 result->score=0;
195 result->sortby=0;
196
197 result->queued=NOT_QUEUED;
198
199 return(result);
200 }
201
202
203 /*++++++++++++++++++++++++++++++++++++++
204 Find a result; search by node and segment.
205
206 Result *FindResult Returns the result that has been found.
207
208 Results *results The results structure to search.
209
210 index_t node The node that is to be found.
211
212 index_t segment The segment that was used to reach this node.
213 ++++++++++++++++++++++++++++++++++++++*/
214
215 Result *FindResult(Results *results,index_t node,index_t segment)
216 {
217 Result *r;
218 int bin=HASH_NODE_SEGMENT(node,segment)&results->mask;
219
220 r=results->point[bin];
221
222 while(r)
223 {
224 if(r->segment==segment && r->node==node)
225 break;
226
227 r=r->hashnext;
228 }
229
230 return(r);
231 }
232
233
234 /*++++++++++++++++++++++++++++++++++++++
235 Find the first result from a set of results.
236
237 Result *FirstResult Returns the first result.
238
239 Results *results The set of results.
240 ++++++++++++++++++++++++++++++++++++++*/
241
242 Result *FirstResult(Results *results)
243 {
244 return(&results->data[0][0]);
245 }
246
247
248 /*++++++++++++++++++++++++++++++++++++++
249 Find the next result from a set of results.
250
251 Result *NextResult Returns the next result.
252
253 Results *results The set of results.
254
255 Result *result The previous result.
256 ++++++++++++++++++++++++++++++++++++++*/
257
258 Result *NextResult(Results *results,Result *result)
259 {
260 int i,j=0;
261
262 for(i=0;i<results->ndata1;i++)
263 {
264 j=result-results->data[i];
265
266 if(j>=0 && j<results->ndata2)
267 break;
268 }
269
270 if(++j>=results->ndata2)
271 {i++;j=0;}
272
273 if((i*results->ndata2+j)>=results->number)
274 return(NULL);
275
276 return(&results->data[i][j]);
277 }

Properties

Name Value
cvs:description Results data type.