trunk/src/queue.c

/***************************************
 Queue data type functions.

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


#include <string.h>
#include <stdlib.h>

#include "results.h"


/*+ A queue of results. +*/
struct _Queue
{
 int      nincrement;           /*+ The amount to increment the queue when full. +*/
 int      nallocated;           /*+ The number of entries allocated. +*/
 int      noccupied;            /*+ The number of entries occupied. +*/

 Result **results;              /*+ The queue of pointers to results. +*/
 score_t *scores;               /*+ The queue of scores. +*/
};


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new queue.

  Queue *NewQueueList Returns the queue.

  uint8_t log2bins The base 2 logarithm of the initial number of bins in the queue.
  ++++++++++++++++++++++++++++++++++++++*/

Queue *NewQueueList(uint8_t log2bins)
{
 Queue *queue;

 queue=(Queue*)malloc(sizeof(Queue));

 queue->nincrement=1<<log2bins;

 queue->nallocated=queue->nincrement;
 queue->noccupied=0;

 queue->results=(Result**)malloc(queue->nallocated*sizeof(Result*));
 queue->scores =(score_t*)malloc(queue->nallocated*sizeof(score_t));

 return(queue);
}


/*++++++++++++++++++++++++++++++++++++++
  Free a queue.

  Queue *queue The queue to be freed.
  ++++++++++++++++++++++++++++++++++++++*/

void FreeQueueList(Queue *queue)
{
 free(queue->results);
 free(queue->scores);

 free(queue);
}


/*++++++++++++++++++++++++++++++++++++++
  Insert a new item into the queue in the right place.

  The data is stored in a "Binary Heap" http://en.wikipedia.org/wiki/Binary_heap
  and this operation is adding an item to the heap.

  Queue *queue The queue to insert the result into.

  Result *result The result to insert into the queue.

  score_t score The score to use for sorting the node.
  ++++++++++++++++++++++++++++++++++++++*/

void InsertInQueue(Queue *queue,Result *result,score_t score)
{
 int index;

 if(result->queued==NOT_QUEUED)
   {
    queue->noccupied++;
    index=queue->noccupied;

    if(queue->noccupied==queue->nallocated)
      {
       queue->nallocated=queue->nallocated+queue->nincrement;
       queue->results=(Result**)realloc((void*)queue->results,queue->nallocated*sizeof(Result*));
       queue->scores=(score_t*)realloc((void*)queue->scores,queue->nallocated*sizeof(score_t));
      }

    queue->results[index]=result;

    queue->scores[index]=score;

    queue->results[index]->queued=index;
   }
 else
    index=result->queued;

 /* Bubble up the new value */

 while(index>1 &&
       queue->scores[index]<queue->scores[index/2])
   {
    int newindex;
    Result *rtemp;
    score_t stemp;

    newindex=index/2;

    rtemp=queue->results[index];
    queue->results[index]=queue->results[newindex];
    queue->results[newindex]=rtemp;

    stemp=queue->scores[index];
    queue->scores[index]=queue->scores[newindex];
    queue->scores[newindex]=stemp;

    queue->results[index]->queued=index;
    queue->results[newindex]->queued=newindex;

    index=newindex;
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Pop an item from the front of the queue.

  The data is stored in a "Binary Heap" http://en.wikipedia.org/wiki/Binary_heap
  and this operation is deleting the root item from the heap.

  Result *PopFromQueue Returns the top item.

  Queue *queue The queue to remove the result from.
  ++++++++++++++++++++++++++++++++++++++*/

Result *PopFromQueue(Queue *queue)
{
 int index;
 Result *retval;

 if(queue->noccupied==0)
    return(NULL);

 retval=queue->results[1];
 retval->queued=NOT_QUEUED;

 index=1;

 queue->results[index]=queue->results[queue->noccupied];
 queue->scores [index]=queue->scores [queue->noccupied];

 queue->noccupied--;

 /* Bubble down the newly promoted value */

 while((2*index)<queue->noccupied &&
       (queue->scores[index]>queue->scores[2*index  ] ||
        queue->scores[index]>queue->scores[2*index+1]))
   {
    int newindex;
    Result *rtemp;
    score_t stemp;

    if(queue->scores[2*index]<queue->scores[2*index+1])
       newindex=2*index;
    else
       newindex=2*index+1;

    rtemp=queue->results[newindex];
    queue->results[newindex]=queue->results[index];
    queue->results[index]=rtemp;

    stemp=queue->scores[newindex];
    queue->scores[newindex]=queue->scores[index];
    queue->scores[index]=stemp;

    queue->results[index]->queued=index;
    queue->results[newindex]->queued=newindex;

    index=newindex;
   }

 if((2*index)==queue->noccupied &&
    queue->scores[index]>queue->scores[2*index])
   {
    int newindex;
    Result *rtemp;
    score_t stemp;

    newindex=2*index;

    rtemp=queue->results[newindex];
    queue->results[newindex]=queue->results[index];
    queue->results[index]=rtemp;

    stemp=queue->scores[newindex];
    queue->scores[newindex]=queue->scores[index];
    queue->scores[index]=stemp;

    queue->results[index]->queued=index;
    queue->results[newindex]->queued=newindex;
   }

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