trunk/src/results.c

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

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2015, 2017 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->number=0;

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

#ifndef LIBROUTINO
 log_malloc(results->point,results->nbins*sizeof(Result*));
#endif

 results->ndata1=0;
 results->nallocdata1=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;

 results->start_waypoint=NO_WAYPOINT;
 results->finish_waypoint=NO_WAYPOINT;

 return(results);
}


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

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

void ResetResultsList(Results *results)
{
 uint32_t i;

 results->number=0;
 results->ndata1=0;

 for(i=0;i<results->nbins;i++)
    results->point[i]=NULL;

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

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


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

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

void FreeResultsList(Results *results)
{
 uint32_t i;

 for(i=0;i<results->nallocdata1;i++)
   {
#ifndef LIBROUTINO
    log_free(results->data[i]);
#endif
    free(results->data[i]);
   }

 free(results->data);

#ifndef LIBROUTINO
 log_free(results->point);
#endif
 free(results->point);

 free(results);
}


/*++++++++++++++++++++++++++++++++++++++
  Insert a single entry into the hashed list.

  The data is stored in a hash table with "Linear Probing" https://en.wikipedia.org/wiki/Linear_probing
  for handling collisions and this operation is adding an item to the hash table.

  Results *results The results structure to insert into.

  Result *result The result to insert.

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

static inline void insert_result(Results *results,Result *result,index_t node,index_t segment)
{
 uint32_t bin=HASH_NODE_SEGMENT(node,segment)&results->mask;

 while(1)
   {
    Result *r=results->point[bin];

    if(!r)
       break;

    bin=(bin+1)%results->nbins;
   }

 results->point[bin]=result;
}


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

 /* Check if we have hit the limit on the number of entries */

 if(results->number==(results->nbins/2))
   {
    uint32_t n;

#ifndef LIBROUTINO
    log_free(results->point);
#endif

    free(results->point);

    results->nbins<<=1;
    results->mask=results->nbins-1;

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

#ifndef LIBROUTINO
    log_malloc(results->point,results->nbins*sizeof(Result*));
#endif

    for(n=0;n<results->number;n++)
      {
       uint32_t i=n/results->ndata2;
       uint32_t j=n%results->ndata2;

       result=&results->data[i][j];

       insert_result(results,result,result->node,result->segment);
      }
   }

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

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

    if(results->ndata1>=results->nallocdata1)
      {
       results->nallocdata1++;
       results->data=(Result**)realloc((void*)results->data,results->nallocdata1*sizeof(Result*));
       results->data[results->nallocdata1-1]=(Result*)malloc(results->ndata2*sizeof(Result));
#ifndef LIBROUTINO
       log_malloc(results->data[results->nallocdata1-1],results->ndata2*sizeof(Result));
#endif
      }
   }

 /* Insert the new entry */

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

 insert_result(results,result,node,segment);

 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.

  The data is stored in a hash table with "Linear Probing" https://en.wikipedia.org/wiki/Linear_probing
  for handling collisions and this operation is finding an item in the hash table.

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

 while(1)
   {
    Result *r=results->point[bin];

    if(!r)
       break;

    if(r->segment==segment && r->node==node)
       return(r);

    bin=(bin+1)%results->nbins;
   }

 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)
{
 uint32_t i;
 size_t j=0;

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

       if(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-2015, 2017 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
51	results->number=0;
52
53	results->point=(Result*)calloc(results->nbins,sizeof(Result));
54
55	#ifndef LIBROUTINO
56	log_malloc(results->point,results->nbinssizeof(Result));
57	#endif
58
59	results->ndata1=0;
60	results->nallocdata1=0;
61	results->ndata2=results->nbins>>2;
62
63	results->data=NULL;
64
65	results->start_node=NO_NODE;
66	results->prev_segment=NO_SEGMENT;
67
68	results->finish_node=NO_NODE;
69	results->last_segment=NO_SEGMENT;
70
71	results->start_waypoint=NO_WAYPOINT;
72	results->finish_waypoint=NO_WAYPOINT;
73
74	return(results);
75	}
76
77
78	/*++++++++++++++++++++++++++++++++++++++
79	Allocate a new results list.
80
81	Results *results The results list to be reset.
82	++++++++++++++++++++++++++++++++++++++*/
83
84	void ResetResultsList(Results *results)
85	{
86	uint32_t i;
87
88	results->number=0;
89	results->ndata1=0;
90
91	for(i=0;i<results->nbins;i++)
92	results->point[i]=NULL;
93
94	results->start_node=NO_NODE;
95	results->prev_segment=NO_SEGMENT;
96
97	results->finish_node=NO_NODE;
98	results->last_segment=NO_SEGMENT;
99	}
100
101
102	/*++++++++++++++++++++++++++++++++++++++
103	Free a results list.
104
105	Results *results The results list to be destroyed.
106	++++++++++++++++++++++++++++++++++++++*/
107
108	void FreeResultsList(Results *results)
109	{
110	uint32_t i;
111
112	for(i=0;i<results->nallocdata1;i++)
113	{
114	#ifndef LIBROUTINO
115	log_free(results->data[i]);
116	#endif
117	free(results->data[i]);
118	}
119
120	free(results->data);
121
122	#ifndef LIBROUTINO
123	log_free(results->point);
124	#endif
125	free(results->point);
126
127	free(results);
128	}
129
130
131	/*++++++++++++++++++++++++++++++++++++++
132	Insert a single entry into the hashed list.
133
134	The data is stored in a hash table with "Linear Probing" https://en.wikipedia.org/wiki/Linear_probing
135	for handling collisions and this operation is adding an item to the hash table.
136
137	Results *results The results structure to insert into.
138
139	Result *result The result to insert.
140
141	index_t node The node that is to be inserted into the results.
142
143	index_t segment The segment that is to be inserted into the results.
144	++++++++++++++++++++++++++++++++++++++*/
145
146	static inline void insert_result(Results results,Result result,index_t node,index_t segment)
147	{
148	uint32_t bin=HASH_NODE_SEGMENT(node,segment)&results->mask;
149
150	while(1)
151	{
152	Result *r=results->point[bin];
153
154	if(!r)
155	break;
156
157	bin=(bin+1)%results->nbins;
158	}
159
160	results->point[bin]=result;
161	}
162
163
164	/*++++++++++++++++++++++++++++++++++++++
165	Insert a new result into the results data structure in the right order.
166
167	Result *InsertResult Returns the result that has been inserted.
168
169	Results *results The results structure to insert into.
170
171	index_t node The node that is to be inserted into the results.
172
173	index_t segment The segment that is to be inserted into the results.
174	++++++++++++++++++++++++++++++++++++++*/
175
176	Result InsertResult(Results results,index_t node,index_t segment)
177	{
178	Result *result;
179
180	/* Check if we have hit the limit on the number of entries */
181
182	if(results->number==(results->nbins/2))
183	{
184	uint32_t n;
185
186	#ifndef LIBROUTINO
187	log_free(results->point);
188	#endif
189
190	free(results->point);
191
192	results->nbins<<=1;
193	results->mask=results->nbins-1;
194
195	results->point=(Result*)calloc(results->nbins,sizeof(Result));
196
197	#ifndef LIBROUTINO
198	log_malloc(results->point,results->nbinssizeof(Result));
199	#endif
200
201	for(n=0;n<results->number;n++)
202	{
203	uint32_t i=n/results->ndata2;
204	uint32_t j=n%results->ndata2;
205
206	result=&results->data[i][j];
207
208	insert_result(results,result,result->node,result->segment);
209	}
210	}
211
212	/* Check if we need more data space allocated */
213
214	if((results->number%results->ndata2)==0)
215	{
216	results->ndata1++;
217
218	if(results->ndata1>=results->nallocdata1)
219	{
220	results->nallocdata1++;
221	results->data=(Result*)realloc((void)results->data,results->nallocdata1sizeof(Result));
222	results->data[results->nallocdata1-1]=(Result)malloc(results->ndata2sizeof(Result));
223	#ifndef LIBROUTINO
224	log_malloc(results->data[results->nallocdata1-1],results->ndata2*sizeof(Result));
225	#endif
226	}
227	}
228
229	/* Insert the new entry */
230
231	result=&results->data[results->ndata1-1][results->number%results->ndata2];
232
233	insert_result(results,result,node,segment);
234
235	results->number++;
236
237	/* Initialise the result */
238
239	result->node=node;
240	result->segment=segment;
241
242	result->prev=NULL;
243	result->next=NULL;
244
245	result->score=0;
246	result->sortby=0;
247
248	result->queued=NOT_QUEUED;
249
250	return(result);
251	}
252
253
254	/*++++++++++++++++++++++++++++++++++++++
255	Find a result; search by node and segment.
256
257	The data is stored in a hash table with "Linear Probing" https://en.wikipedia.org/wiki/Linear_probing
258	for handling collisions and this operation is finding an item in the hash table.
259
260	Result *FindResult Returns the result that has been found.
261
262	Results *results The results structure to search.
263
264	index_t node The node that is to be found.
265
266	index_t segment The segment that was used to reach this node.
267	++++++++++++++++++++++++++++++++++++++*/
268
269	Result FindResult(Results results,index_t node,index_t segment)
270	{
271	uint32_t bin=HASH_NODE_SEGMENT(node,segment)&results->mask;
272
273	while(1)
274	{
275	Result *r=results->point[bin];
276
277	if(!r)
278	break;
279
280	if(r->segment==segment && r->node==node)
281	return(r);
282
283	bin=(bin+1)%results->nbins;
284	}
285
286	return(NULL);
287	}
288
289
290	/*++++++++++++++++++++++++++++++++++++++
291	Find the first result from a set of results.
292
293	Result *FirstResult Returns the first result.
294
295	Results *results The set of results.
296	++++++++++++++++++++++++++++++++++++++*/
297
298	Result FirstResult(Results results)
299	{
300	return(&results->data[0][0]);
301	}
302
303
304	/*++++++++++++++++++++++++++++++++++++++
305	Find the next result from a set of results.
306
307	Result *NextResult Returns the next result.
308
309	Results *results The set of results.
310
311	Result *result The previous result.
312	++++++++++++++++++++++++++++++++++++++*/
313
314	Result NextResult(Results results,Result *result)
315	{
316	uint32_t i;
317	size_t j=0;
318
319	for(i=0;i<results->ndata1;i++)
320	if(result>=results->data[i])
321	{
322	j=result-results->data[i];
323
324	if(j<results->ndata2)
325	break;
326	}
327
328	if(++j>=results->ndata2)
329	{i++;j=0;}
330
331	if((i*results->ndata2+j)>=results->number)
332	return(NULL);
333
334	return(&results->data[i][j]);
335	}