trunk/src/results.c

/***************************************
 Result data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2011 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ***************************************/


#include <sys/types.h>
#include <string.h>
#include <stdlib.h>

#include "results.h"

/*+ The size of the increment for the Results data structure. +*/
#define RESULTS_INCREMENT 64


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new results list.

  Results *NewResultsList Returns the results list.

  int nbins The number of bins in the results array.
  ++++++++++++++++++++++++++++++++++++++*/

Results *NewResultsList(int nbins)
{
 Results *results;
 uint32_t i;

 results=(Results*)malloc(sizeof(Results));

 results->nbins=1;
 results->mask=~0;

 while(nbins>>=1)
   {
    results->mask<<=1;
    results->nbins<<=1;
   }

 results->mask=~results->mask;

 results->alloced=RESULTS_INCREMENT;
 results->number=0;

 results->count=(uint32_t*)malloc(results->nbins*sizeof(uint32_t));
 results->point=(Result***)malloc(results->nbins*sizeof(Result**));

 for(i=0;i<results->nbins;i++)
   {
    results->count[i]=0;

    results->point[i]=(Result**)malloc(results->alloced*sizeof(Result*));
   }

 results->data=(Result**)malloc(1*sizeof(Result*));
 results->data[0]=(Result*)malloc(results->nbins*RESULTS_INCREMENT*sizeof(Result));

 results->start_node=NO_NODE;
 results->prev_segment=NO_SEGMENT;

 results->finish_node=NO_NODE;
 results->last_segment=NO_SEGMENT;

 return(results);
}


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new results list.

  Results *results The results list to be destroyed.
  ++++++++++++++++++++++++++++++++++++++*/

void FreeResultsList(Results *results)
{
 int i,c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);

 for(i=c;i>=0;i--)
    free(results->data[i]);

 free(results->data);

 for(i=0;i<results->nbins;i++)
    free(results->point[i]);

 free(results->point);

 free(results->count);

 free(results);
}


/*++++++++++++++++++++++++++++++++++++++
  Insert a new result into the results data structure in the right order.

  Result *InsertResult Returns the result that has been inserted.

  Results *results The results structure to insert into.

  index_t node The node that is to be inserted into the results.

  index_t segment The segment that is to be inserted into the results.
  ++++++++++++++++++++++++++++++++++++++*/

Result *InsertResult(Results *results,index_t node,index_t segment)
{
 Result *result;
 int bin=node&results->mask;
 uint32_t i;

 /* Check that the arrays have enough space. */

 if(results->count[bin]==results->alloced)
   {
    results->alloced+=RESULTS_INCREMENT;

    for(i=0;i<results->nbins;i++)
       results->point[i]=(Result**)realloc((void*)results->point[i],results->alloced*sizeof(Result*));
   }

 if(results->number && (results->number%RESULTS_INCREMENT)==0 && (results->number%(RESULTS_INCREMENT*results->nbins))==0)
   {
    int c=results->number/(results->nbins*RESULTS_INCREMENT);

    results->data=(Result**)realloc((void*)results->data,(c+1)*sizeof(Result*));
    results->data[c]=(Result*)malloc(results->nbins*RESULTS_INCREMENT*sizeof(Result));
   }

 /* Insert the new entry */

 results->point[bin][results->count[bin]]=&results->data[results->number/(results->nbins*RESULTS_INCREMENT)][results->number%(results->nbins*RESULTS_INCREMENT)];

 results->number++;

 results->count[bin]++;

 /* Initialise the result */

 result=results->point[bin][results->count[bin]-1];

 result->node=node;
 result->segment=segment;

 result->prev=NULL;
 result->next=NULL;

 result->score=0;
 result->sortby=0;

 result->queued=NOT_QUEUED;

 return(result);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a result; search by node only (don't care about the segment but find the shortest).

  Result *FindResult Returns the result that has been found.

  Results *results The results structure to search.

  index_t node The node that is to be found.
  ++++++++++++++++++++++++++++++++++++++*/

Result *FindResult1(Results *results,index_t node)
{
 int bin=node&results->mask;
 score_t best_score=INF_SCORE;
 Result *best_result=NULL;
 int i;

 for(i=results->count[bin]-1;i>=0;i--)
    if(results->point[bin][i]->node==node && results->point[bin][i]->score<best_score)
      {
       best_score=results->point[bin][i]->score;
       best_result=results->point[bin][i];
      }

 return(best_result);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a result; search by node and segment.

  Result *FindResult Returns the result that has been found.

  Results *results The results structure to search.

  index_t node The node that is to be found.

  index_t segment The segment that was used to reach this node.
  ++++++++++++++++++++++++++++++++++++++*/

Result *FindResult(Results *results,index_t node,index_t segment)
{
 int bin=node&results->mask;
 int i;

 for(i=results->count[bin]-1;i>=0;i--)
    if(results->point[bin][i]->node==node && results->point[bin][i]->segment==segment)
       return(results->point[bin][i]);

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a result from a set of results.

  Result *FirstResult Returns the first results from a set of results.

  Results *results The set of results.
  ++++++++++++++++++++++++++++++++++++++*/

Result *FirstResult(Results *results)
{
 return(&results->data[0][0]);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a result from a set of results.

  Result *NextResult Returns the next result from a set of results.

  Results *results The set of results.

  Result *result The previous result.
  ++++++++++++++++++++++++++++++++++++++*/

Result *NextResult(Results *results,Result *result)
{
 int i,j=0,c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);

 for(i=0;i<=c;i++)
   {
    j=result-results->data[i];

    if(j>=0 && j<(results->nbins*RESULTS_INCREMENT))
       break;
   }

 if(++j>=(results->nbins*RESULTS_INCREMENT))
   {i++;j=0;}

 if((i*(results->nbins*RESULTS_INCREMENT)+j)>=results->number)
    return(NULL);

 return(&results->data[i][j]);
}
1	amb	29	/***************************************
2			Result data type functions.
3	amb	151
4			Part of the Routino routing software.
5	amb	29	****************/ /****************
6	amb	603	This file Copyright 2008-2011 Andrew M. Bishop
7	amb	29
8	amb	151	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	amb	29	***************************************/
21
22
23	amb	214	#include <sys/types.h>
24	amb	29	#include <string.h>
25			#include <stdlib.h>
26
27			#include "results.h"
28
29	amb	228	/+ The size of the increment for the Results data structure. +/
30	amb	441	#define RESULTS_INCREMENT 64
31	amb	29
32	amb	67
33	amb	29	/*++++++++++++++++++++++++++++++++++++++
34			Allocate a new results list.
35
36			Results *NewResultsList Returns the results list.
37	amb	71
38			int nbins The number of bins in the results array.
39	amb	29	++++++++++++++++++++++++++++++++++++++*/
40
41	amb	71	Results *NewResultsList(int nbins)
42	amb	29	{
43			Results *results;
44	amb	214	uint32_t i;
45	amb	29
46			results=(Results*)malloc(sizeof(Results));
47
48	amb	71	results->nbins=1;
49			results->mask=~0;
50
51			while(nbins>>=1)
52			{
53			results->mask<<=1;
54			results->nbins<<=1;
55			}
56
57			results->mask=~results->mask;
58
59			results->alloced=RESULTS_INCREMENT;
60	amb	45	results->number=0;
61	amb	29
62	amb	79	results->count=(uint32_t)malloc(results->nbinssizeof(uint32_t));
63			results->point=(Result**)malloc(results->nbinssizeof(Result**));
64	amb	71
65			for(i=0;i<results->nbins;i++)
66	amb	29	{
67	amb	79	results->count[i]=0;
68	amb	45
69	amb	79	results->point[i]=(Result*)malloc(results->allocedsizeof(Result*));
70	amb	29	}
71	amb	45
72	amb	79	results->data=(Result*)malloc(1sizeof(Result*));
73			results->data[0]=(Result)malloc(results->nbinsRESULTS_INCREMENT*sizeof(Result));
74	amb	45
75	amb	605	results->start_node=NO_NODE;
76			results->prev_segment=NO_SEGMENT;
77	amb	165
78	amb	605	results->finish_node=NO_NODE;
79			results->last_segment=NO_SEGMENT;
80
81	amb	29	return(results);
82			}
83
84
85			/*++++++++++++++++++++++++++++++++++++++
86			Allocate a new results list.
87
88			Results *results The results list to be destroyed.
89			++++++++++++++++++++++++++++++++++++++*/
90
91			void FreeResultsList(Results *results)
92			{
93	amb	214	int i,c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
94	amb	29
95	amb	79	for(i=c;i>=0;i--)
96			free(results->data[i]);
97	amb	71
98	amb	79	free(results->data);
99
100	amb	71	for(i=0;i<results->nbins;i++)
101	amb	79	free(results->point[i]);
102	amb	71
103	amb	79	free(results->point);
104	amb	29
105	amb	79	free(results->count);
106
107	amb	29	free(results);
108			}
109
110
111			/*++++++++++++++++++++++++++++++++++++++
112			Insert a new result into the results data structure in the right order.
113
114	amb	228	Result *InsertResult Returns the result that has been inserted.
115	amb	29
116			Results *results The results structure to insert into.
117
118	amb	116	index_t node The node that is to be inserted into the results.
119	amb	605
120			index_t segment The segment that is to be inserted into the results.
121	amb	29	++++++++++++++++++++++++++++++++++++++*/
122
123	amb	605	Result InsertResult(Results results,index_t node,index_t segment)
124	amb	29	{
125	amb	605	Result *result;
126	amb	71	int bin=node&results->mask;
127	amb	214	uint32_t i;
128	amb	29
129			/* Check that the arrays have enough space. */
130
131	amb	79	if(results->count[bin]==results->alloced)
132	amb	29	{
133	amb	71	results->alloced+=RESULTS_INCREMENT;
134	amb	29
135	amb	71	for(i=0;i<results->nbins;i++)
136	amb	79	results->point[i]=(Result*)realloc((void)results->point[i],results->allocedsizeof(Result));
137			}
138	amb	29
139	amb	79	if(results->number && (results->number%RESULTS_INCREMENT)==0 && (results->number%(RESULTS_INCREMENT*results->nbins))==0)
140			{
141			int c=results->number/(results->nbins*RESULTS_INCREMENT);
142
143			results->data=(Result*)realloc((void)results->data,(c+1)sizeof(Result));
144			results->data[c]=(Result)malloc(results->nbinsRESULTS_INCREMENT*sizeof(Result));
145	amb	45	}
146	amb	29
147			/* Insert the new entry */
148
149	amb	111	results->point[bin][results->count[bin]]=&results->data[results->number/(results->nbinsRESULTS_INCREMENT)][results->number%(results->nbinsRESULTS_INCREMENT)];
150	amb	29
151	amb	45	results->number++;
152	amb	29
153	amb	79	results->count[bin]++;
154	amb	45
155	amb	605	/* Initialise the result */
156	amb	166
157	amb	605	result=results->point[bin][results->count[bin]-1];
158
159			result->node=node;
160			result->segment=segment;
161
162			result->prev=NULL;
163			result->next=NULL;
164
165			result->score=0;
166			result->sortby=0;
167
168			result->queued=NOT_QUEUED;
169
170			return(result);
171	amb	29	}
172
173
174			/*++++++++++++++++++++++++++++++++++++++
175	amb	605	Find a result; search by node only (don't care about the segment but find the shortest).
176	amb	166
177	amb	605	Result *FindResult Returns the result that has been found.
178
179			Results *results The results structure to search.
180
181			index_t node The node that is to be found.
182	amb	166	++++++++++++++++++++++++++++++++++++++*/
183
184	amb	605	Result FindResult1(Results results,index_t node)
185	amb	166	{
186	amb	605	int bin=node&results->mask;
187			score_t best_score=INF_SCORE;
188			Result *best_result=NULL;
189			int i;
190	amb	457
191	amb	605	for(i=results->count[bin]-1;i>=0;i--)
192			if(results->point[bin][i]->node==node && results->point[bin][i]->score<best_score)
193			{
194			best_score=results->point[bin][i]->score;
195			best_result=results->point[bin][i];
196			}
197	amb	166
198	amb	605	return(best_result);
199	amb	166	}
200
201
202			/*++++++++++++++++++++++++++++++++++++++
203	amb	605	Find a result; search by node and segment.
204	amb	29
205	amb	228	Result *FindResult Returns the result that has been found.
206	amb	29
207			Results *results The results structure to search.
208
209	amb	116	index_t node The node that is to be found.
210	amb	605
211			index_t segment The segment that was used to reach this node.
212	amb	29	++++++++++++++++++++++++++++++++++++++*/
213
214	amb	605	Result FindResult(Results results,index_t node,index_t segment)
215	amb	29	{
216	amb	71	int bin=node&results->mask;
217	amb	111	int i;
218	amb	29
219	amb	111	for(i=results->count[bin]-1;i>=0;i--)
220	amb	605	if(results->point[bin][i]->node==node && results->point[bin][i]->segment==segment)
221	amb	111	return(results->point[bin][i]);
222	amb	29
223			return(NULL);
224			}
225	amb	67
226
227			/*++++++++++++++++++++++++++++++++++++++
228	amb	79	Find a result from a set of results.
229	amb	67
230	amb	79	Result *FirstResult Returns the first results from a set of results.
231
232	amb	67	Results *results The set of results.
233	amb	79	++++++++++++++++++++++++++++++++++++++*/
234	amb	67
235	amb	79	Result FirstResult(Results results)
236			{
237			return(&results->data[0][0]);
238			}
239
240
241			/*++++++++++++++++++++++++++++++++++++++
242			Find a result from a set of results.
243
244			Result *NextResult Returns the next result from a set of results.
245
246			Results *results The set of results.
247
248			Result *result The previous result.
249			++++++++++++++++++++++++++++++++++++++*/
250
251			Result NextResult(Results results,Result *result)
252			{
253	amb	214	int i,j=0,c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
254	amb	79
255			for(i=0;i<=c;i++)
256			{
257	amb	214	j=result-results->data[i];
258	amb	79
259			if(j>=0 && j<(results->nbins*RESULTS_INCREMENT))
260			break;
261			}
262
263			if(++j>=(results->nbins*RESULTS_INCREMENT))
264			{i++;j=0;}
265
266			if((i(results->nbinsRESULTS_INCREMENT)+j)>=results->number)
267			return(NULL);
268
269			return(&results->data[i][j]);
270			}