Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Contents of /trunk/src/results.c
Parent Directory
|
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)
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. |