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

       *bin1=NULL;
       *bin2=NULL;

       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->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	*bin1=NULL;
137	*bin2=NULL;
138
139	while(r)
140	{
141	Result *rh=r->hashnext;
142	int newbin=HASH_NODE_SEGMENT(r->node,r->segment)&results->mask;
143
144	r->hashnext=NULL;
145
146	if(newbin==i)
147	{ *bin1=r; bin1=&r->hashnext; }
148	else
149	{ *bin2=r; bin2=&r->hashnext; }
150
151	results->count[newbin]++;
152
153	r=rh;
154	}
155	}
156
157	bin=HASH_NODE_SEGMENT(node,segment)&results->mask;
158	}
159
160	/* Check if we need more data space allocated */
161
162	if((results->number%results->ndata2)==0)
163	{
164	results->ndata1++;
165
166	results->data=(Result*)realloc((void)results->data,results->ndata1sizeof(Result));
167	results->data[results->ndata1-1]=(Result)malloc(results->ndata2sizeof(Result));
168	}
169
170	/* Insert the new entry */
171
172	result=&results->data[results->ndata1-1][results->number%results->ndata2];
173
174	result->hashnext=results->point[bin];
175
176	results->point[bin]=result;
177
178	results->count[bin]++;
179
180	results->number++;
181
182	/* Initialise the result */
183
184	result->node=node;
185	result->segment=segment;
186
187	result->prev=NULL;
188	result->next=NULL;
189
190	result->score=0;
191
192	result->queued=NOT_QUEUED;
193
194	return(result);
195	}
196
197
198	/*++++++++++++++++++++++++++++++++++++++
199	Find a result; search by node and segment.
200
201	Result *FindResult Returns the result that has been found.
202
203	Results *results The results structure to search.
204
205	index_t node The node that is to be found.
206
207	index_t segment The segment that was used to reach this node.
208	++++++++++++++++++++++++++++++++++++++*/
209
210	Result FindResult(Results results,index_t node,index_t segment)
211	{
212	Result *r;
213	int bin=HASH_NODE_SEGMENT(node,segment)&results->mask;
214
215	r=results->point[bin];
216
217	while(r)
218	{
219	if(r->segment==segment && r->node==node)
220	break;
221
222	r=r->hashnext;
223	}
224
225	return(r);
226	}
227
228
229	/*++++++++++++++++++++++++++++++++++++++
230	Find the first result from a set of results.
231
232	Result *FirstResult Returns the first result.
233
234	Results *results The set of results.
235	++++++++++++++++++++++++++++++++++++++*/
236
237	Result FirstResult(Results results)
238	{
239	return(&results->data[0][0]);
240	}
241
242
243	/*++++++++++++++++++++++++++++++++++++++
244	Find the next result from a set of results.
245
246	Result *NextResult Returns the next result.
247
248	Results *results The set of results.
249
250	Result *result The previous result.
251	++++++++++++++++++++++++++++++++++++++*/
252
253	Result NextResult(Results results,Result *result)
254	{
255	int i,j=0;
256
257	for(i=0;i<results->ndata1;i++)
258	{
259	j=result-results->data[i];
260
261	if(j>=0 && j<results->ndata2)
262	break;
263	}
264
265	if(++j>=results->ndata2)
266	{i++;j=0;}
267
268	if((i*results->ndata2+j)>=results->number)
269	return(NULL);
270
271	return(&results->data[i][j]);
272	}