trunk/src/results.c

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

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2013 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"


#define HASH_NODE_SEGMENT(node,segment) ((node)^(segment<<4))


/*++++++++++++++++++++++++++++++++++++++
  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;
 results->ncollisions=0;

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

 results->number=0;

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

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

 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);

 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=HASH_NODE_SEGMENT(node,segment)&results->mask;

 /* Check if we have hit the limit on the number of collisions per bin */

 if(results->count[bin]==results->ncollisions)
   {
    int i;

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

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

    for(i=0;i<results->nbins/2;i++)
      {
       Result *r=results->point[i];
       Result **bin1,**bin2;

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

       bin1=&results->point[i];
       bin2=&results->point[i+results->nbins/2];

       while(r)
         {
          Result *rh=r->hashnext;
          int newbin=HASH_NODE_SEGMENT(r->node,r->segment)&results->mask;

          r->hashnext=NULL;

          if(newbin==i)
            { *bin1=r; bin1=&r->hashnext; }
          else
            { *bin2=r; bin2=&r->hashnext; }

          results->count[newbin]++;

          r=rh;
         }
      }

    bin=HASH_NODE_SEGMENT(node,segment)&results->mask;
   }

 /* Check if we need more data space allocated */

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

 result=&results->data[results->ndata1-1][results->number%results->ndata2];

 result->hashnext=results->point[bin];

 results->point[bin]=result;

 results->count[bin]++;

 results->number++;

 /* Initialise the result */

 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 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)
{
 Result *r;
 int bin=HASH_NODE_SEGMENT(node,segment)&results->mask;

 r=results->point[bin];

 while(r)
   {
    if(r->segment==segment && r->node==node)
       break;

    r=r->hashnext;
   }

 return(r);
}


/*++++++++++++++++++++++++++++++++++++++
  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-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->nbinssizeof(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->ndata1sizeof(Result));
171	results->data[results->ndata1-1]=(Result)malloc(results->ndata2sizeof(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	}