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

   1 /***************************************
   2  $Header: /home/amb/routino/src/RCS/queue.c,v 1.7 2009/11/13 19:24:11 amb Exp $
   3
   4  Queue data type functions.
   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 #include <sys/types.h>
  26 #include <string.h>
  27 #include <stdlib.h>
  28
  29 #include "results.h"
  30
  31
  32 /*+ A queue of results. +*/
  33 struct _Queue
  34 {
  35  uint32_t nallocated;           /*+ The number of entries allocated. +*/
  36  uint32_t noccupied;            /*+ The number of entries occupied. +*/
  37
  38  Result **data;                 /*+ The queue of pointers to results. +*/
  39 };
  40
  41
  42 /*++++++++++++++++++++++++++++++++++++++
  43   Allocate a new queue.
  44
  45   Queue *NewQueueList Returns the queue.
  46   ++++++++++++++++++++++++++++++++++++++*/
  47
  48 Queue *NewQueueList(void)
  49 {
  50  Queue *queue;
  51
  52  queue=(Queue*)malloc(sizeof(Queue));
  53
  54  queue->nallocated=1023;
  55  queue->noccupied=0;
  56
  57  queue->data=(Result**)malloc(queue->nallocated*sizeof(Result*));
  58
  59  return(queue);
  60 }
  61
  62
  63 /*++++++++++++++++++++++++++++++++++++++
  64   Free a queue.
  65
  66   Queue *queue The queue to be freed.
  67   ++++++++++++++++++++++++++++++++++++++*/
  68
  69 void FreeQueueList(Queue *queue)
  70 {
  71  free(queue->data);
  72
  73  free(queue);
  74 }
  75
  76
  77 /*++++++++++++++++++++++++++++++++++++++
  78   Insert a new item into the queue in the right place.
  79
  80   The data is stored in a "Binary Heap" http://en.wikipedia.org/wiki/Binary_heap
  81   and this operation is adding an item to the heap.
  82
  83   Queue *queue The queue to insert the result into.
  84
  85   Result *result The result to insert into the queue.
  86   ++++++++++++++++++++++++++++++++++++++*/
  87
  88 void InsertInQueue(Queue *queue,Result *result)
  89 {
  90  uint32_t index;
  91
  92  if(result->queued==NOT_QUEUED)
  93    {
  94     if(queue->noccupied==queue->nallocated)
  95       {
  96        queue->nallocated=2*queue->nallocated+1;
  97        queue->data=(Result**)realloc((void*)queue->data,queue->nallocated*sizeof(Result*));
  98       }
  99
 100     index=queue->noccupied;
 101     queue->noccupied++;
 102
 103     queue->data[index]=result;
 104     queue->data[index]->queued=index;
 105    }
 106  else
 107    {
 108     index=result->queued;
 109    }
 110
 111  /* Bubble up the new value */
 112
 113  while(index>0 &&
 114        queue->data[index]->sortby<queue->data[(index-1)/2]->sortby)
 115    {
 116     uint32_t newindex;
 117     Result *temp;
 118
 119     newindex=(index-1)/2;
 120
 121     temp=queue->data[index];
 122     queue->data[index]=queue->data[newindex];
 123     queue->data[newindex]=temp;
 124
 125     queue->data[index]->queued=index;
 126     queue->data[newindex]->queued=newindex;
 127
 128     index=newindex;
 129    }
 130 }
 131
 132
 133 /*++++++++++++++++++++++++++++++++++++++
 134   Pop an item from the front of the queue.
 135
 136   The data is stored in a "Binary Heap" http://en.wikipedia.org/wiki/Binary_heap
 137   and this operation is deleting the root item from the heap.
 138
 139   Result *PopFromQueue Returns the top item.
 140
 141   Queue *queue The queue to remove the result from.
 142   ++++++++++++++++++++++++++++++++++++++*/
 143
 144 Result *PopFromQueue(Queue *queue)
 145 {
 146  uint32_t index;
 147  Result *retval;
 148
 149  if(queue->noccupied==0)
 150     return(NULL);
 151
 152  retval=queue->data[0];
 153  retval->queued=NOT_QUEUED;
 154
 155  index=0;
 156  queue->noccupied--;
 157
 158  queue->data[index]=queue->data[queue->noccupied];
 159
 160  /* Bubble down the newly promoted value */
 161
 162  while((2*index+2)<queue->noccupied &&
 163        (queue->data[index]->sortby>queue->data[2*index+1]->sortby ||
 164         queue->data[index]->sortby>queue->data[2*index+2]->sortby))
 165    {
 166     uint32_t newindex;
 167     Result *temp;
 168
 169     if(queue->data[2*index+1]->sortby<queue->data[2*index+2]->sortby)
 170        newindex=2*index+1;
 171     else
 172        newindex=2*index+2;
 173
 174     temp=queue->data[newindex];
 175     queue->data[newindex]=queue->data[index];
 176     queue->data[index]=temp;
 177
 178     queue->data[index]->queued=index;
 179     queue->data[newindex]->queued=newindex;
 180
 181     index=newindex;
 182    }
 183
 184  if((2*index+2)==queue->noccupied &&
 185     queue->data[index]->sortby>queue->data[2*index+1]->sortby)
 186    {
 187     uint32_t newindex;
 188     Result *temp;
 189
 190     newindex=2*index+1;
 191
 192     temp=queue->data[newindex];
 193     queue->data[newindex]=queue->data[index];
 194     queue->data[index]=temp;
 195
 196     queue->data[index]->queued=index;
 197     queue->data[newindex]->queued=newindex;
 198    }
 199
 200  return(retval);
 201 }