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 'point' arrays. +*/
#define RESULTS_POINT_INCREMENT 4

/*+ The size of the increment for the Results 'data' arrays. +*/
#define RESULTS_DATA_INCREMENT 1


/*++++++++++++++++++++++++++++++++++++++
  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;

 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->number=0;

 results->npoint2=0;

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

 results->ndata1=0;
 results->ndata2=results->nbins*RESULTS_DATA_INCREMENT;

 results->data=NULL;

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

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

 return(results);
}


/*++++++++++++++++++++++++++++++++++++++
  Free a results list.

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

void FreeResultsList(Results *results)
{
 int i;

 for(i=0;i<results->ndata1;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;

 /* Check that the arrays have enough space or allocate more. */

 if(results->count[bin]==results->npoint2)
   {
    uint32_t i;

    results->npoint2+=RESULTS_POINT_INCREMENT;

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

 if((results->number%results->ndata2)==0)
   {
    results->ndata1++;

    results->data=(Result**)realloc((void*)results->data,results->ndata1*sizeof(Result*));
    results->data[results->ndata1-1]=(Result*)malloc(results->ndata2*sizeof(Result));
   }

 /* Insert the new entry */

 results->point[bin][results->count[bin]]=&results->data[results->ndata1-1][results->number%results->ndata2];

 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 *FindResult1 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 the first result from a set of results.

  Result *FirstResult Returns the first result.

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

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


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

  Result *NextResult Returns the next result.

  Results *results The set of results.

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

Result *NextResult(Results *results,Result *result)
{
 int i,j=0;

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

    if(j>=0 && j<results->ndata2)
       break;
   }

 if(++j>=results->ndata2)
   {i++;j=0;}

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

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