trunk/src/results.h

/***************************************
 A header file for the results.

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


#ifndef RESULTS_H
#define RESULTS_H    /*+ To stop multiple inclusions. +*/

#include <stdint.h>

#include "types.h"


/* Constants */

/*+ A result is not currently queued. +*/
#define NOT_QUEUED (uint32_t)(0)


/* Data structures */

typedef struct _Result Result;

/*+ The result for a node. +*/
struct _Result
{
 index_t   node;                /*+ The node for which this result applies. +*/
 index_t   segment;             /*+ The segmemt used to get to the node for which this result applies. +*/

 Result   *prev;                /*+ The previous result following the best path to get to this node via the segment. +*/
 Result   *next;                /*+ The next result following the best path from this node that was reached via the segment. +*/

 score_t   score;               /*+ The best actual weighted distance or duration score from the start to the node. +*/
 score_t   sortby;              /*+ The best possible weighted distance or duration score from the start to the finish. +*/

 uint32_t  queued;              /*+ The position of this result in the queue. +*/

 Result   *hashnext;            /*+ The next result in the linked list for this hash bin. +*/
};

/*+ A list of results. +*/
typedef struct _Results
{
 uint32_t  nbins;               /*+ The number of bins in the has table. +*/
 uint32_t  mask;                /*+ A bit mask to select the bottom log2(nbins) bits. +*/

 uint32_t  number;              /*+ The total number of occupied results. +*/

 uint8_t   ncollisions;         /*+ The number of results allowed in each hash bin. +*/
 uint8_t  *count;               /*+ An array of nbins counters of results in each hash bin. +*/

 Result  **point;               /*+ An array of nbins linked lists of results for one hash bin. +*/

 uint32_t  ndata1;              /*+ The size of the first dimension of the 'data' array. +*/
 uint32_t  ndata2;              /*+ The size of the second dimension of the 'data' array. +*/

 uint32_t  nallocdata1;         /*+ The amount of allocated space in the first dimension of the 'data' array. +*/

 Result  **data;                /*+ An array of arrays containing the actual results, the first
                                    dimension is reallocated but the second dimension is not.
                                    Most importantly pointers into the real data don't change
                                    as more space is allocated (since realloc is not being used). +*/

 index_t start_node;            /*+ The start node. +*/
 index_t prev_segment;          /*+ The previous segment to get to the start node (if any). +*/

 index_t finish_node;           /*+ The finish node. +*/
 index_t last_segment;          /*+ The last segment (to arrive at the finish node). +*/
}
 Results;


/* Forward definition for opaque type */

typedef struct _Queue Queue;


/* Results functions in results.c */

Results *NewResultsList(uint8_t log2bins);
void ResetResultsList(Results *results);
void FreeResultsList(Results *results);

Result *InsertResult(Results *results,index_t node,index_t segment);

Result *FindResult(Results *results,index_t node,index_t segment);

Result *FirstResult(Results *results);
Result *NextResult(Results *results,Result *result);


/* Queue functions in queue.c */

Queue *NewQueueList(uint8_t log2bins);
void ResetQueueList(Queue *queue);
void FreeQueueList(Queue *queue);

void InsertInQueue(Queue *queue,Result *result,score_t score);
Result *PopFromQueue(Queue *queue);


#endif /* RESULTS_H */
1	/***************************************
2	A header file for the results.
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	#ifndef RESULTS_H
24	#define RESULTS_H /+ To stop multiple inclusions. +/
25
26	#include <stdint.h>
27
28	#include "types.h"
29
30
31	/* Constants */
32
33	/+ A result is not currently queued. +/
34	#define NOT_QUEUED (uint32_t)(0)
35
36
37	/* Data structures */
38
39	typedef struct _Result Result;
40
41	/+ The result for a node. +/
42	struct _Result
43	{
44	index_t node; /+ The node for which this result applies. +/
45	index_t segment; /+ The segmemt used to get to the node for which this result applies. +/
46
47	Result prev; /+ The previous result following the best path to get to this node via the segment. +*/
48	Result next; /+ The next result following the best path from this node that was reached via the segment. +*/
49
50	score_t score; /+ The best actual weighted distance or duration score from the start to the node. +/
51	score_t sortby; /+ The best possible weighted distance or duration score from the start to the finish. +/
52
53	uint32_t queued; /+ The position of this result in the queue. +/
54
55	Result hashnext; /+ The next result in the linked list for this hash bin. +*/
56	};
57
58	/+ A list of results. +/
59	typedef struct _Results
60	{
61	uint32_t nbins; /+ The number of bins in the has table. +/
62	uint32_t mask; /+ A bit mask to select the bottom log2(nbins) bits. +/
63
64	uint32_t number; /+ The total number of occupied results. +/
65
66	uint8_t ncollisions; /+ The number of results allowed in each hash bin. +/
67	uint8_t count; /+ An array of nbins counters of results in each hash bin. +*/
68
69	Result *point; /+ An array of nbins linked lists of results for one hash bin. +*/
70
71	uint32_t ndata1; /+ The size of the first dimension of the 'data' array. +/
72	uint32_t ndata2; /+ The size of the second dimension of the 'data' array. +/
73
74	uint32_t nallocdata1; /+ The amount of allocated space in the first dimension of the 'data' array. +/
75
76	Result *data; /+ An array of arrays containing the actual results, the first
77	dimension is reallocated but the second dimension is not.
78	Most importantly pointers into the real data don't change
79	as more space is allocated (since realloc is not being used). +*/
80
81	index_t start_node; /+ The start node. +/
82	index_t prev_segment; /+ The previous segment to get to the start node (if any). +/
83
84	index_t finish_node; /+ The finish node. +/
85	index_t last_segment; /+ The last segment (to arrive at the finish node). +/
86	}
87	Results;
88
89
90	/* Forward definition for opaque type */
91
92	typedef struct _Queue Queue;
93
94
95	/* Results functions in results.c */
96
97	Results *NewResultsList(uint8_t log2bins);
98	void ResetResultsList(Results *results);
99	void FreeResultsList(Results *results);
100
101	Result InsertResult(Results results,index_t node,index_t segment);
102
103	Result FindResult(Results results,index_t node,index_t segment);
104
105	Result FirstResult(Results results);
106	Result NextResult(Results results,Result *result);
107
108
109	/* Queue functions in queue.c */
110
111	Queue *NewQueueList(uint8_t log2bins);
112	void ResetQueueList(Queue *queue);
113	void FreeQueueList(Queue *queue);
114
115	void InsertInQueue(Queue queue,Result result,score_t score);
116	Result PopFromQueue(Queue queue);
117
118
119	#endif /* RESULTS_H */