1 /***************************************
2 $Header: /home/amb/routino/src/RCS/results.c,v 1.21 2010/07/07 19:04:18 amb Exp $
4 Result data type functions.
6 Part of the Routino routing software.
7 ******************/ /******************
8 This file Copyright 2008-2010 Andrew M. Bishop
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.
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.
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 ***************************************/
25 #include <sys/types.h>
31 /*+ The size of the increment for the Results data structure. +*/
32 #define RESULTS_INCREMENT 64
35 /*++++++++++++++++++++++++++++++++++++++
36 Allocate a new results list.
38 Results *NewResultsList Returns the results list.
40 int nbins The number of bins in the results array.
41 ++++++++++++++++++++++++++++++++++++++*/
43 Results *NewResultsList(int nbins)
48 results=(Results*)malloc(sizeof(Results));
59 results->mask=~results->mask;
61 results->alloced=RESULTS_INCREMENT;
64 results->count=(uint32_t*)malloc(results->nbins*sizeof(uint32_t));
65 results->point=(Result***)malloc(results->nbins*sizeof(Result**));
67 for(i=0;i<results->nbins;i++)
71 results->point[i]=(Result**)malloc(results->alloced*sizeof(Result*));
74 results->data=(Result**)malloc(1*sizeof(Result*));
75 results->data[0]=(Result*)malloc(results->nbins*RESULTS_INCREMENT*sizeof(Result));
77 results->start=NO_NODE;
78 results->finish=NO_NODE;
84 /*++++++++++++++++++++++++++++++++++++++
85 Allocate a new results list.
87 Results *results The results list to be destroyed.
88 ++++++++++++++++++++++++++++++++++++++*/
90 void FreeResultsList(Results *results)
92 int i,c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
95 free(results->data[i]);
99 for(i=0;i<results->nbins;i++)
100 free(results->point[i]);
102 free(results->point);
104 free(results->count);
110 /*++++++++++++++++++++++++++++++++++++++
111 Insert a new result into the results data structure in the right order.
113 Result *InsertResult Returns the result that has been inserted.
115 Results *results The results structure to insert into.
117 index_t node The node that is to be inserted into the results.
118 ++++++++++++++++++++++++++++++++++++++*/
120 Result *InsertResult(Results *results,index_t node)
122 int bin=node&results->mask;
125 /* Check that the arrays have enough space. */
127 if(results->count[bin]==results->alloced)
129 results->alloced+=RESULTS_INCREMENT;
131 for(i=0;i<results->nbins;i++)
132 results->point[i]=(Result**)realloc((void*)results->point[i],results->alloced*sizeof(Result*));
135 if(results->number && (results->number%RESULTS_INCREMENT)==0 && (results->number%(RESULTS_INCREMENT*results->nbins))==0)
137 int c=results->number/(results->nbins*RESULTS_INCREMENT);
139 results->data=(Result**)realloc((void*)results->data,(c+1)*sizeof(Result*));
140 results->data[c]=(Result*)malloc(results->nbins*RESULTS_INCREMENT*sizeof(Result));
143 /* Insert the new entry */
145 results->point[bin][results->count[bin]]=&results->data[results->number/(results->nbins*RESULTS_INCREMENT)][results->number%(results->nbins*RESULTS_INCREMENT)];
149 results->count[bin]++;
151 results->point[bin][results->count[bin]-1]->node=node;
152 results->point[bin][results->count[bin]-1]->queued=NOT_QUEUED;
154 return(results->point[bin][results->count[bin]-1]);
158 /*++++++++++++++++++++++++++++++++++++++
159 Zero the values in a result structure.
161 Result *result The result to modify.
162 ++++++++++++++++++++++++++++++++++++++*/
164 void ZeroResult(Result *result)
166 result->prev=NO_NODE;
167 result->next=NO_NODE;
172 result->segment=NULL;
176 /*++++++++++++++++++++++++++++++++++++++
177 Find a result; search by node.
179 Result *FindResult Returns the result that has been found.
181 Results *results The results structure to search.
183 index_t node The node that is to be found.
184 ++++++++++++++++++++++++++++++++++++++*/
186 Result *FindResult(Results *results,index_t node)
188 int bin=node&results->mask;
191 for(i=results->count[bin]-1;i>=0;i--)
192 if(results->point[bin][i]->node==node)
193 return(results->point[bin][i]);
199 /*++++++++++++++++++++++++++++++++++++++
200 Find a result from a set of results.
202 Result *FirstResult Returns the first results from a set of results.
204 Results *results The set of results.
205 ++++++++++++++++++++++++++++++++++++++*/
207 Result *FirstResult(Results *results)
209 return(&results->data[0][0]);
213 /*++++++++++++++++++++++++++++++++++++++
214 Find a result from a set of results.
216 Result *NextResult Returns the next result from a set of results.
218 Results *results The set of results.
220 Result *result The previous result.
221 ++++++++++++++++++++++++++++++++++++++*/
223 Result *NextResult(Results *results,Result *result)
225 int i,j=0,c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
229 j=result-results->data[i];
231 if(j>=0 && j<(results->nbins*RESULTS_INCREMENT))
235 if(++j>=(results->nbins*RESULTS_INCREMENT))
238 if((i*(results->nbins*RESULTS_INCREMENT)+j)>=results->number)
241 return(&results->data[i][j]);