git.maemo.org Git - routino/blob - src/results.h

   1 /***************************************
   2  $Header: /home/amb/routino/src/RCS/results.h,v 1.17 2009/11/13 19:24:11 amb Exp $
   3
   4  A header file for the results.
   5
   6  Part of the Routino routing software.
   7  ******************/ /******************
   8  This file Copyright 2008,2009 Andrew M. Bishop
   9
  10  This program is free software: you can redistribute it and/or modify
  11  it under the terms of the GNU Affero General Public License as published by
  12  the Free Software Foundation, either version 3 of the License, or
  13  (at your option) any later version.
  14
  15  This program is distributed in the hope that it will be useful,
  16  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  GNU Affero General Public License for more details.
  19
  20  You should have received a copy of the GNU Affero General Public License
  21  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  22  ***************************************/
  23
  24
  25 #ifndef RESULTS_H
  26 #define RESULTS_H    /*+ To stop multiple inclusions. +*/
  27
  28 #include <stdint.h>
  29
  30 #include "types.h"
  31
  32
  33 /* Constants */
  34
  35 /*+ A result is not currently queued. +*/
  36 #define NOT_QUEUED (uint32_t)(~0)
  37
  38
  39 /* Data structures */
  40
  41 /*+ The result for a node. +*/
  42 typedef struct _Result
  43 {
  44  index_t   node;                /*+ The node for which this result applies. +*/
  45
  46  index_t   prev;                /*+ The previous node following the best path. +*/
  47  index_t   next;                /*+ The next node following the best path. +*/
  48
  49  score_t   score;               /*+ The best actual weighted distance or duration score from the start to the node. +*/
  50
  51  score_t   sortby;              /*+ The best possible weighted distance or duration score from the start to the finish. +*/
  52  uint32_t  queued;              /*+ The position of this result in the queue. +*/
  53
  54  Segment  *segment;             /*+ The segment for the path to here (from prev). +*/
  55 }
  56  Result;
  57
  58 /*+ A list of results. +*/
  59 typedef struct _Results
  60 {
  61  uint32_t  nbins;               /*+ The number of bins. +*/
  62  uint32_t  mask;                /*+ A bit mask to select the bottom 'nbins' bits. +*/
  63
  64  uint32_t  alloced;             /*+ The amount of space allocated for results
  65                                     (the length of the number and pointers arrays and
  66                                      1/nbins times the amount in the real results). +*/
  67  uint32_t  number;              /*+ The total number of occupied results. +*/
  68
  69  uint32_t *count;               /*+ An array of nbins counters of results in each array. +*/
  70  Result ***point;               /*+ An array of nbins arrays of pointers to actual results. +*/
  71
  72  Result  **data;                /*+ An array of arrays containing the actual results
  73                                     (don't need to realloc the array of data when adding more,
  74                                     only realloc the array that points to the array of data).
  75                                     Most importantly pointers into the real data don't change
  76                                     as more space is allocated (since realloc is not being used). +*/
  77
  78  index_t start;                 /*+ The start node. +*/
  79  index_t finish;                /*+ The finish node. +*/
  80 }
  81  Results;
  82
  83
  84 /* Forward definitions for opaque type */
  85
  86 typedef struct _Queue Queue;
  87
  88
  89 /* Results Functions */
  90
  91 Results *NewResultsList(int nbins);
  92 void FreeResultsList(Results *results);
  93
  94 Result *InsertResult(Results *results,index_t node);
  95 void ZeroResult(Result *result);
  96
  97 Result *FindResult(Results *results,index_t node);
  98
  99 Result *FirstResult(Results *results);
 100 Result *NextResult(Results *results,Result *result);
 101
 102
 103 /* Queue Functions */
 104
 105 Queue *NewQueueList(void);
 106 void FreeQueueList(Queue *queue);
 107
 108 void InsertInQueue(Queue *queue,Result *result);
 109 Result *PopFromQueue(Queue *queue);
 110
 111
 112 #endif /* RESULTS_H */