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.

  uint8_t log2bins The base 2 logarithm of the initial number of bins in the results array.
  ++++++++++++++++++++++++++++++++++++++*/

Results *NewResultsList(uint8_t log2bins)
{
 Results *results;

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

 results->nbins=1<<log2bins;
 results->mask=results->nbins-1;
 results->ncollisions=log2bins-4;

 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->nbins-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	uint8_t log2bins The base 2 logarithm of the initial number of bins in the results array.
40	++++++++++++++++++++++++++++++++++++++*/
41
42	Results *NewResultsList(uint8_t log2bins)
43	{
44	Results *results;
45
46	results=(Results*)malloc(sizeof(Results));
47
48	results->nbins=1<<log2bins;
49	results->mask=results->nbins-1;
50	results->ncollisions=log2bins-4;
51
52	results->number=0;
53
54	results->count=(uint8_t*)calloc(results->nbins,sizeof(uint8_t));
55	results->point=(Result*)calloc(results->nbins,sizeof(Result));
56
57	results->ndata1=0;
58	results->ndata2=results->nbins>>2;
59
60	results->data=NULL;
61
62	results->start_node=NO_NODE;
63	results->prev_segment=NO_SEGMENT;
64
65	results->finish_node=NO_NODE;
66	results->last_segment=NO_SEGMENT;
67
68	return(results);
69	}
70
71
72	/*++++++++++++++++++++++++++++++++++++++
73	Free a results list.
74
75	Results *results The results list to be destroyed.
76	++++++++++++++++++++++++++++++++++++++*/
77
78	void FreeResultsList(Results *results)
79	{
80	int i;
81
82	for(i=0;i<results->ndata1;i++)
83	free(results->data[i]);
84
85	free(results->data);
86
87	free(results->point);
88
89	free(results->count);
90
91	free(results);
92	}
93
94
95	/*++++++++++++++++++++++++++++++++++++++
96	Insert a new result into the results data structure in the right order.
97
98	Result *InsertResult Returns the result that has been inserted.
99
100	Results *results The results structure to insert into.
101
102	index_t node The node that is to be inserted into the results.
103
104	index_t segment The segment that is to be inserted into the results.
105	++++++++++++++++++++++++++++++++++++++*/
106
107	Result InsertResult(Results results,index_t node,index_t segment)
108	{
109	Result *result;
110	int bin=HASH_NODE_SEGMENT(node,segment)&results->mask;
111
112	/* Check if we have hit the limit on the number of collisions per bin */
113
114	if(results->count[bin]==results->ncollisions)
115	{
116	int i;
117
118	results->nbins<<=1;
119	results->mask=results->nbins-1;
120	results->ncollisions++;
121
122	results->count=(uint8_t)realloc((void)results->count,results->nbins*sizeof(uint8_t));
123	results->point=(Result*)realloc((void)results->point,results->nbinssizeof(Result));
124
125	for(i=0;i<results->nbins/2;i++)
126	{
127	Result *r=results->point[i];
128	Result bin1,bin2;
129
130	results->count[i] =0;
131	results->count[i+results->nbins/2]=0;
132
133	bin1=&results->point[i];
134	bin2=&results->point[i+results->nbins/2];
135
136	while(r)
137	{
138	Result *rh=r->hashnext;
139	int newbin=HASH_NODE_SEGMENT(r->node,r->segment)&results->mask;
140
141	r->hashnext=NULL;
142
143	if(newbin==i)
144	{ *bin1=r; bin1=&r->hashnext; }
145	else
146	{ *bin2=r; bin2=&r->hashnext; }
147
148	results->count[newbin]++;
149
150	r=rh;
151	}
152	}
153
154	bin=HASH_NODE_SEGMENT(node,segment)&results->mask;
155	}
156
157	/* Check if we need more data space allocated */
158
159	if((results->number%results->ndata2)==0)
160	{
161	results->ndata1++;
162
163	results->data=(Result*)realloc((void)results->data,results->ndata1sizeof(Result));
164	results->data[results->ndata1-1]=(Result)malloc(results->ndata2sizeof(Result));
165	}
166
167	/* Insert the new entry */
168
169	result=&results->data[results->ndata1-1][results->number%results->ndata2];
170
171	result->hashnext=results->point[bin];
172
173	results->point[bin]=result;
174
175	results->count[bin]++;
176
177	results->number++;
178
179	/* Initialise the result */
180
181	result->node=node;
182	result->segment=segment;
183
184	result->prev=NULL;
185	result->next=NULL;
186
187	result->score=0;
188	result->sortby=0;
189
190	result->queued=NOT_QUEUED;
191
192	return(result);
193	}
194
195
196	/*++++++++++++++++++++++++++++++++++++++
197	Find a result; search by node and segment.
198
199	Result *FindResult Returns the result that has been found.
200
201	Results *results The results structure to search.
202
203	index_t node The node that is to be found.
204
205	index_t segment The segment that was used to reach this node.
206	++++++++++++++++++++++++++++++++++++++*/
207
208	Result FindResult(Results results,index_t node,index_t segment)
209	{
210	Result *r;
211	int bin=HASH_NODE_SEGMENT(node,segment)&results->mask;
212
213	r=results->point[bin];
214
215	while(r)
216	{
217	if(r->segment==segment && r->node==node)
218	break;
219
220	r=r->hashnext;
221	}
222
223	return(r);
224	}
225
226
227	/*++++++++++++++++++++++++++++++++++++++
228	Find the first result from a set of results.
229
230	Result *FirstResult Returns the first result.
231
232	Results *results The set of results.
233	++++++++++++++++++++++++++++++++++++++*/
234
235	Result FirstResult(Results results)
236	{
237	return(&results->data[0][0]);
238	}
239
240
241	/*++++++++++++++++++++++++++++++++++++++
242	Find the next result from a set of results.
243
244	Result *NextResult Returns the next result.
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	int i,j=0;
254
255	for(i=0;i<results->ndata1;i++)
256	{
257	j=result-results->data[i];
258
259	if(j>=0 && j<results->ndata2)
260	break;
261	}
262
263	if(++j>=results->ndata2)
264	{i++;j=0;}
265
266	if((i*results->ndata2+j)>=results->number)
267	return(NULL);
268
269	return(&results->data[i][j]);
270	}