trunk/src/results.c

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

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2012 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 <string.h>
#include <stdlib.h>

#include "results.h"

#include "logging.h"


/*+ The maximum number of collisions in a bin for the Results 'point' arrays before worrying. +*/
#define MAX_COLLISIONS 32
 

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

  Results *NewResultsList Returns the results list.

  int nbins The initial 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->npoint1=0;

 results->count=(uint8_t*)calloc(results->nbins,sizeof(uint8_t));
 results->point=(Result***)malloc(MAX_COLLISIONS*sizeof(Result**));

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

 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->npoint1;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 if we have hit the limit on the number of collisions per bin */

 if(results->count[bin]>MAX_COLLISIONS && results->count[bin]==results->npoint1)
   {
    int i,j,k;

    results->nbins<<=1;
    results->mask=(results->mask<<1)|1;

    results->count=(uint8_t*)realloc((void*)results->count,results->nbins*sizeof(uint8_t));

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

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

       results->count[i+results->nbins/2]=0;

       for(j=0,k=0;j<c;j++)
         {
          int newbin=results->point[j][i]->node&results->mask;

          if(newbin==i)
            {
             if(k!=j)
                results->point[k][i]=results->point[j][i];
             k++;
            }
          else
            {
             results->point[results->count[newbin]][newbin]=results->point[j][i];

             results->count[newbin]++;
             results->count[i]--;
            }
         }
      }

    bin=node&results->mask;
   }

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

 if(results->count[bin]==results->npoint1)
   {
    logassert(results->npoint1<255,"Results are more numerous than expected (report a bug)");

    results->npoint1++;

    if(results->npoint1>MAX_COLLISIONS)
       results->point=(Result***)realloc((void*)results->point,results->npoint1*sizeof(Result**));

    results->point[results->npoint1-1]=(Result**)malloc(results->nbins*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[results->count[bin]][bin]=&results->data[results->ndata1-1][results->number%results->ndata2];

 results->number++;

 results->count[bin]++;

 /* Initialise the result */

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

 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[i][bin]->node==node && results->point[i][bin]->score<best_score)
      {
       best_score=results->point[i][bin]->score;
       best_result=results->point[i][bin];
      }

 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[i][bin]->segment==segment && results->point[i][bin]->node==node)
       return(results->point[i][bin]);

 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-2012 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	/+ The maximum number of collisions in a bin for the Results 'point' arrays before worrying. +/
32	#define MAX_COLLISIONS 32
33
34
35	/*++++++++++++++++++++++++++++++++++++++
36	Allocate a new results list.
37
38	Results *NewResultsList Returns the results list.
39
40	int nbins The initial number of bins in the results array.
41	++++++++++++++++++++++++++++++++++++++*/
42
43	Results *NewResultsList(int nbins)
44	{
45	Results *results;
46
47	results=(Results*)malloc(sizeof(Results));
48
49	results->nbins=1;
50	results->mask=~0;
51
52	while(nbins>>=1)
53	{
54	results->mask<<=1;
55	results->nbins<<=1;
56	}
57
58	results->mask=~results->mask;
59
60	results->number=0;
61
62	results->npoint1=0;
63
64	results->count=(uint8_t*)calloc(results->nbins,sizeof(uint8_t));
65	results->point=(Result**)malloc(MAX_COLLISIONSsizeof(Result**));
66
67	results->ndata1=0;
68	results->ndata2=results->nbins;
69
70	results->data=NULL;
71
72	results->start_node=NO_NODE;
73	results->prev_segment=NO_SEGMENT;
74
75	results->finish_node=NO_NODE;
76	results->last_segment=NO_SEGMENT;
77
78	return(results);
79	}
80
81
82	/*++++++++++++++++++++++++++++++++++++++
83	Free a results list.
84
85	Results *results The results list to be destroyed.
86	++++++++++++++++++++++++++++++++++++++*/
87
88	void FreeResultsList(Results *results)
89	{
90	int i;
91
92	for(i=0;i<results->ndata1;i++)
93	free(results->data[i]);
94
95	free(results->data);
96
97	for(i=0;i<results->npoint1;i++)
98	free(results->point[i]);
99
100	free(results->point);
101
102	free(results->count);
103
104	free(results);
105	}
106
107
108	/*++++++++++++++++++++++++++++++++++++++
109	Insert a new result into the results data structure in the right order.
110
111	Result *InsertResult Returns the result that has been inserted.
112
113	Results *results The results structure to insert into.
114
115	index_t node The node that is to be inserted into the results.
116
117	index_t segment The segment that is to be inserted into the results.
118	++++++++++++++++++++++++++++++++++++++*/
119
120	Result InsertResult(Results results,index_t node,index_t segment)
121	{
122	Result *result;
123	int bin=node&results->mask;
124
125	/* Check if we have hit the limit on the number of collisions per bin */
126
127	if(results->count[bin]>MAX_COLLISIONS && results->count[bin]==results->npoint1)
128	{
129	int i,j,k;
130
131	results->nbins<<=1;
132	results->mask=(results->mask<<1)\|1;
133
134	results->count=(uint8_t)realloc((void)results->count,results->nbins*sizeof(uint8_t));
135
136	for(i=0;i<results->npoint1;i++)
137	results->point[i]=(Result*)realloc((void)results->point[i],results->nbinssizeof(Result));
138
139	for(i=0;i<results->nbins/2;i++)
140	{
141	int c=results->count[i];
142
143	results->count[i+results->nbins/2]=0;
144
145	for(j=0,k=0;j<c;j++)
146	{
147	int newbin=results->point[j][i]->node&results->mask;
148
149	if(newbin==i)
150	{
151	if(k!=j)
152	results->point[k][i]=results->point[j][i];
153	k++;
154	}
155	else
156	{
157	results->point[results->count[newbin]][newbin]=results->point[j][i];
158
159	results->count[newbin]++;
160	results->count[i]--;
161	}
162	}
163	}
164
165	bin=node&results->mask;
166	}
167
168	/* Check that the arrays have enough space or allocate more. */
169
170	if(results->count[bin]==results->npoint1)
171	{
172	logassert(results->npoint1<255,"Results are more numerous than expected (report a bug)");
173
174	results->npoint1++;
175
176	if(results->npoint1>MAX_COLLISIONS)
177	results->point=(Result**)realloc((void)results->point,results->npoint1sizeof(Result*));
178
179	results->point[results->npoint1-1]=(Result*)malloc(results->nbinssizeof(Result*));
180	}
181
182	if((results->number%results->ndata2)==0)
183	{
184	results->ndata1++;
185
186	results->data=(Result*)realloc((void)results->data,results->ndata1sizeof(Result));
187	results->data[results->ndata1-1]=(Result)malloc(results->ndata2sizeof(Result));
188	}
189
190	/* Insert the new entry */
191
192	results->point[results->count[bin]][bin]=&results->data[results->ndata1-1][results->number%results->ndata2];
193
194	results->number++;
195
196	results->count[bin]++;
197
198	/* Initialise the result */
199
200	result=results->point[results->count[bin]-1][bin];
201
202	result->node=node;
203	result->segment=segment;
204
205	result->prev=NULL;
206	result->next=NULL;
207
208	result->score=0;
209	result->sortby=0;
210
211	result->queued=NOT_QUEUED;
212
213	return(result);
214	}
215
216
217	/*++++++++++++++++++++++++++++++++++++++
218	Find a result; search by node only (don't care about the segment but find the shortest).
219
220	Result *FindResult1 Returns the result that has been found.
221
222	Results *results The results structure to search.
223
224	index_t node The node that is to be found.
225	++++++++++++++++++++++++++++++++++++++*/
226
227	Result FindResult1(Results results,index_t node)
228	{
229	int bin=node&results->mask;
230	score_t best_score=INF_SCORE;
231	Result *best_result=NULL;
232	int i;
233
234	for(i=results->count[bin]-1;i>=0;i--)
235	if(results->point[i][bin]->node==node && results->point[i][bin]->score<best_score)
236	{
237	best_score=results->point[i][bin]->score;
238	best_result=results->point[i][bin];
239	}
240
241	return(best_result);
242	}
243
244
245	/*++++++++++++++++++++++++++++++++++++++
246	Find a result; search by node and segment.
247
248	Result *FindResult Returns the result that has been found.
249
250	Results *results The results structure to search.
251
252	index_t node The node that is to be found.
253
254	index_t segment The segment that was used to reach this node.
255	++++++++++++++++++++++++++++++++++++++*/
256
257	Result FindResult(Results results,index_t node,index_t segment)
258	{
259	int bin=node&results->mask;
260	int i;
261
262	for(i=results->count[bin]-1;i>=0;i--)
263	if(results->point[i][bin]->segment==segment && results->point[i][bin]->node==node)
264	return(results->point[i][bin]);
265
266	return(NULL);
267	}
268
269
270	/*++++++++++++++++++++++++++++++++++++++
271	Find the first result from a set of results.
272
273	Result *FirstResult Returns the first result.
274
275	Results *results The set of results.
276	++++++++++++++++++++++++++++++++++++++*/
277
278	Result FirstResult(Results results)
279	{
280	return(&results->data[0][0]);
281	}
282
283
284	/*++++++++++++++++++++++++++++++++++++++
285	Find the next result from a set of results.
286
287	Result *NextResult Returns the next result.
288
289	Results *results The set of results.
290
291	Result *result The previous result.
292	++++++++++++++++++++++++++++++++++++++*/
293
294	Result NextResult(Results results,Result *result)
295	{
296	int i,j=0;
297
298	for(i=0;i<results->ndata1;i++)
299	{
300	j=result-results->data[i];
301
302	if(j>=0 && j<results->ndata2)
303	break;
304	}
305
306	if(++j>=results->ndata2)
307	{i++;j=0;}
308
309	if((i*results->ndata2+j)>=results->number)
310	return(NULL);
311
312	return(&results->data[i][j]);
313	}