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

   1 /***************************************
   2  $Header: /home/amb/routino/src/RCS/results.c,v 1.22 2010/07/23 14:32:16 amb Exp $
   3
   4  Result data type functions.
   5
   6  Part of the Routino routing software.
   7  ******************/ /******************
   8  This file Copyright 2008-2010 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 #include <sys/types.h>
  26 #include <string.h>
  27 #include <stdlib.h>
  28
  29 #include "results.h"
  30
  31 /*+ The size of the increment for the Results data structure. +*/
  32 #define RESULTS_INCREMENT 64
  33
  34
  35 /*++++++++++++++++++++++++++++++++++++++
  36   Allocate a new results list.
  37
  38   Results *NewResultsList Returns the results list.
  39
  40   int nbins The number of bins in the results array.
  41   ++++++++++++++++++++++++++++++++++++++*/
  42
  43 Results *NewResultsList(int nbins)
  44 {
  45  Results *results;
  46  uint32_t i;
  47
  48  results=(Results*)malloc(sizeof(Results));
  49
  50  results->nbins=1;
  51  results->mask=~0;
  52
  53  while(nbins>>=1)
  54    {
  55     results->mask<<=1;
  56     results->nbins<<=1;
  57    }
  58
  59  results->mask=~results->mask;
  60
  61  results->alloced=RESULTS_INCREMENT;
  62  results->number=0;
  63
  64  results->count=(uint32_t*)malloc(results->nbins*sizeof(uint32_t));
  65  results->point=(Result***)malloc(results->nbins*sizeof(Result**));
  66
  67  for(i=0;i<results->nbins;i++)
  68    {
  69     results->count[i]=0;
  70
  71     results->point[i]=(Result**)malloc(results->alloced*sizeof(Result*));
  72    }
  73
  74  results->data=(Result**)malloc(1*sizeof(Result*));
  75  results->data[0]=(Result*)malloc(results->nbins*RESULTS_INCREMENT*sizeof(Result));
  76
  77  results->start=NO_NODE;
  78  results->finish=NO_NODE;
  79
  80  return(results);
  81 }
  82
  83
  84 /*++++++++++++++++++++++++++++++++++++++
  85   Allocate a new results list.
  86
  87   Results *results The results list to be destroyed.
  88   ++++++++++++++++++++++++++++++++++++++*/
  89
  90 void FreeResultsList(Results *results)
  91 {
  92  int i,c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
  93
  94  for(i=c;i>=0;i--)
  95     free(results->data[i]);
  96
  97  free(results->data);
  98
  99  for(i=0;i<results->nbins;i++)
 100     free(results->point[i]);
 101
 102  free(results->point);
 103
 104  free(results->count);
 105
 106  free(results);
 107 }
 108
 109
 110 /*++++++++++++++++++++++++++++++++++++++
 111   Insert a new result into the results data structure in the right order.
 112
 113   Result *InsertResult Returns the result that has been inserted.
 114
 115   Results *results The results structure to insert into.
 116
 117   index_t node The node that is to be inserted into the results.
 118   ++++++++++++++++++++++++++++++++++++++*/
 119
 120 Result *InsertResult(Results *results,index_t node)
 121 {
 122  int bin=node&results->mask;
 123  uint32_t i;
 124
 125  /* Check that the arrays have enough space. */
 126
 127  if(results->count[bin]==results->alloced)
 128    {
 129     results->alloced+=RESULTS_INCREMENT;
 130
 131     for(i=0;i<results->nbins;i++)
 132        results->point[i]=(Result**)realloc((void*)results->point[i],results->alloced*sizeof(Result*));
 133    }
 134
 135  if(results->number && (results->number%RESULTS_INCREMENT)==0 && (results->number%(RESULTS_INCREMENT*results->nbins))==0)
 136    {
 137     int c=results->number/(results->nbins*RESULTS_INCREMENT);
 138
 139     results->data=(Result**)realloc((void*)results->data,(c+1)*sizeof(Result*));
 140     results->data[c]=(Result*)malloc(results->nbins*RESULTS_INCREMENT*sizeof(Result));
 141    }
 142
 143  /* Insert the new entry */
 144
 145  results->point[bin][results->count[bin]]=&results->data[results->number/(results->nbins*RESULTS_INCREMENT)][results->number%(results->nbins*RESULTS_INCREMENT)];
 146
 147  results->number++;
 148
 149  results->count[bin]++;
 150
 151  results->point[bin][results->count[bin]-1]->node=node;
 152  results->point[bin][results->count[bin]-1]->queued=NOT_QUEUED;
 153
 154  return(results->point[bin][results->count[bin]-1]);
 155 }
 156
 157
 158 /*++++++++++++++++++++++++++++++++++++++
 159   Zero the values in a result structure.
 160
 161   Result *result The result to modify.
 162   ++++++++++++++++++++++++++++++++++++++*/
 163
 164 void ZeroResult(Result *result)
 165 {
 166  result->segment=NO_SEGMENT;
 167
 168  result->prev=NO_NODE;
 169  result->next=NO_NODE;
 170
 171  result->score=0;
 172  result->sortby=0;
 173 }
 174
 175
 176 /*++++++++++++++++++++++++++++++++++++++
 177   Find a result; search by node.
 178
 179   Result *FindResult Returns the result that has been found.
 180
 181   Results *results The results structure to search.
 182
 183   index_t node The node that is to be found.
 184   ++++++++++++++++++++++++++++++++++++++*/
 185
 186 Result *FindResult(Results *results,index_t node)
 187 {
 188  int bin=node&results->mask;
 189  int i;
 190
 191  for(i=results->count[bin]-1;i>=0;i--)
 192     if(results->point[bin][i]->node==node)
 193        return(results->point[bin][i]);
 194
 195  return(NULL);
 196 }
 197
 198
 199 /*++++++++++++++++++++++++++++++++++++++
 200   Find a result from a set of results.
 201
 202   Result *FirstResult Returns the first results from a set of results.
 203
 204   Results *results The set of results.
 205   ++++++++++++++++++++++++++++++++++++++*/
 206
 207 Result *FirstResult(Results *results)
 208 {
 209  return(&results->data[0][0]);
 210 }
 211
 212
 213 /*++++++++++++++++++++++++++++++++++++++
 214   Find a result from a set of results.
 215
 216   Result *NextResult Returns the next result from a set of results.
 217
 218   Results *results The set of results.
 219
 220   Result *result The previous result.
 221   ++++++++++++++++++++++++++++++++++++++*/
 222
 223 Result *NextResult(Results *results,Result *result)
 224 {
 225  int i,j=0,c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
 226
 227  for(i=0;i<=c;i++)
 228    {
 229     j=result-results->data[i];
 230
 231     if(j>=0 && j<(results->nbins*RESULTS_INCREMENT))
 232        break;
 233    }
 234
 235  if(++j>=(results->nbins*RESULTS_INCREMENT))
 236    {i++;j=0;}
 237
 238  if((i*(results->nbins*RESULTS_INCREMENT)+j)>=results->number)
 239     return(NULL);
 240
 241  return(&results->data[i][j]);
 242 }