trunk/src/queue.c

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

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2013, 2017 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"
#include "logging.h"


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

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


/*++++++++++++++++++++++++++++++++++++++
  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*));

#ifndef LIBROUTINO
 log_malloc(queue->results,queue->nallocated*sizeof(Result*));
#endif

 return(queue);
}


/*++++++++++++++++++++++++++++++++++++++
  Re-use an existing queue.

  Queue *queue The queue to reset for re-use.
  ++++++++++++++++++++++++++++++++++++++*/

void ResetQueueList(Queue *queue)
{
 queue->noccupied=0;
}


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

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

void FreeQueueList(Queue *queue)
{
#ifndef LIBROUTINO
 log_free(queue->results);
#endif

 free(queue->results);

 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)
{
 uint32_t 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*));

#ifndef LIBROUTINO
       log_malloc(queue->results,queue->nallocated*sizeof(Result*));
#endif
      }

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

 queue->results[index]->sortby=score;

 /* Bubble up the new value */

 while(index>1)
   {
    uint32_t newindex;
    Result *temp;

    newindex=index/2;

    if(queue->results[index]->sortby>=queue->results[newindex]->sortby)
       break;

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

    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)
{
 uint32_t 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->noccupied--;

 /* Bubble down the newly promoted value */

 while((2*index)<queue->noccupied)
   {
    uint32_t newindex;
    Result *temp;

    newindex=2*index;

    if(queue->results[newindex]->sortby>queue->results[newindex+1]->sortby)
       newindex=newindex+1;

    if(queue->results[index]->sortby<=queue->results[newindex]->sortby)
       break;

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

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

    index=newindex;
   }

 if((2*index)==queue->noccupied)
   {
    uint32_t newindex;
    Result *temp;

    newindex=2*index;

    if(queue->results[index]->sortby<=queue->results[newindex]->sortby)
       ; /* break */
    else
      {
       temp=queue->results[newindex];
       queue->results[newindex]=queue->results[index];
       queue->results[index]=temp;

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

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