Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Contents of /trunk/src/results.h
Parent Directory
| 
Revision Log
Revision 1501 -
(show annotations)
(download)
(as text)
Wed Jan 29 19:57:08 2014 UTC (11 years, 2 months ago) by amb
File MIME type: text/x-chdr
File size: 4548 byte(s)
Wed Jan 29 19:57:08 2014 UTC (11 years, 2 months ago) by amb
File MIME type: text/x-chdr
File size: 4548 byte(s)
Refactor the code so that the Results data type has the start and finish waypoints defined within it and the array passed to the PrintRoute() function doesn't have holes in it.
| 1 | /*************************************** |
| 2 | A header file for the results. |
| 3 | |
| 4 | Part of the Routino routing software. |
| 5 | ******************/ /****************** |
| 6 | This file Copyright 2008-2014 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 | waypoint_t start_waypoint; /*+ The number of the starting waypoint. +*/ |
| 88 | waypoint_t finish_waypoint; /*+ The number of the finish waypoint. +*/ |
| 89 | } |
| 90 | Results; |
| 91 | |
| 92 | |
| 93 | /* Forward definition for opaque type */ |
| 94 | |
| 95 | typedef struct _Queue Queue; |
| 96 | |
| 97 | |
| 98 | /* Results functions in results.c */ |
| 99 | |
| 100 | Results *NewResultsList(uint8_t log2bins); |
| 101 | void ResetResultsList(Results *results); |
| 102 | void FreeResultsList(Results *results); |
| 103 | |
| 104 | Result *InsertResult(Results *results,index_t node,index_t segment); |
| 105 | |
| 106 | Result *FindResult(Results *results,index_t node,index_t segment); |
| 107 | |
| 108 | Result *FirstResult(Results *results); |
| 109 | Result *NextResult(Results *results,Result *result); |
| 110 | |
| 111 | |
| 112 | /* Queue functions in queue.c */ |
| 113 | |
| 114 | Queue *NewQueueList(uint8_t log2bins); |
| 115 | void ResetQueueList(Queue *queue); |
| 116 | void FreeQueueList(Queue *queue); |
| 117 | |
| 118 | void InsertInQueue(Queue *queue,Result *result,score_t score); |
| 119 | Result *PopFromQueue(Queue *queue); |
| 120 | |
| 121 | |
| 122 | #endif /* RESULTS_H */ |
Properties
| Name | Value |
|---|---|
| cvs:description | Results data type. |