trunk/src/queue.c

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

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2011 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 <sys/types.h>
#include <string.h>
#include <stdlib.h>

#include "results.h"


/*+ A queue of results. +*/
struct _Queue
{
 uint32_t nallocated;           /*+ The number of entries allocated. +*/
 uint32_t noccupied;            /*+ The number of entries occupied. +*/

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


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

  Queue *NewQueueList Returns the queue.
  ++++++++++++++++++++++++++++++++++++++*/

Queue *NewQueueList(void)
{
 Queue *queue;

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

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

 queue->data=(Result**)malloc(queue->nallocated*sizeof(Result*));

 return(queue);
}


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

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

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

 free(queue);
}


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

  The data is stored in a "3-ary Heap" http://en.wikipedia.org/wiki/D-ary_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.
  ++++++++++++++++++++++++++++++++++++++*/

void InsertInQueue(Queue *queue,Result *result)
{
 uint32_t index;

 if(result->queued==NOT_QUEUED)
   {
    if(queue->noccupied==queue->nallocated)
      {
       queue->nallocated=2*queue->nallocated;
       queue->data=(Result**)realloc((void*)queue->data,queue->nallocated*sizeof(Result*));
      }

    index=queue->noccupied;
    queue->noccupied++;

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

 /* Bubble up the new value */

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

    newindex=(index-1)/3;

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

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

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

    index=newindex;
   }
}


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

  The data is stored in a "3-ary Heap" http://en.wikipedia.org/wiki/D-ary_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->data[0];
 retval->queued=NOT_QUEUED;

 index=0;
 queue->noccupied--;

 queue->data[index]=queue->data[queue->noccupied];

 /* Bubble down the newly promoted value */

 while((3*index+3)<queue->noccupied)
   {
    uint32_t childindex,newindex;
    Result *temp;

    childindex=newindex=3*index+1;

    if(queue->data[newindex]->sortby>queue->data[++childindex]->sortby)
       newindex=childindex;
    if(queue->data[newindex]->sortby>queue->data[++childindex]->sortby)
       newindex=childindex;

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

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

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

    index=newindex;
   }

 if((3*index+3)==queue->noccupied)
   {
    uint32_t childindex,newindex;
    Result *temp;

    childindex=newindex=3*index+1;

    if(queue->data[newindex]->sortby>queue->data[++childindex]->sortby)
       newindex=childindex;

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

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

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

    newindex=3*index+1;

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

       queue->data[index]->queued=index;
       queue->data[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-2011 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 <sys/types.h>
24	#include <string.h>
25	#include <stdlib.h>
26
27	#include "results.h"
28
29
30	/+ A queue of results. +/
31	struct _Queue
32	{
33	uint32_t nallocated; /+ The number of entries allocated. +/
34	uint32_t noccupied; /+ The number of entries occupied. +/
35
36	Result *data; /+ The queue of pointers to results. +*/
37	};
38
39
40	/*++++++++++++++++++++++++++++++++++++++
41	Allocate a new queue.
42
43	Queue *NewQueueList Returns the queue.
44	++++++++++++++++++++++++++++++++++++++*/
45
46	Queue *NewQueueList(void)
47	{
48	Queue *queue;
49
50	queue=(Queue*)malloc(sizeof(Queue));
51
52	queue->nallocated=1024;
53	queue->noccupied=0;
54
55	queue->data=(Result*)malloc(queue->nallocatedsizeof(Result*));
56
57	return(queue);
58	}
59
60
61	/*++++++++++++++++++++++++++++++++++++++
62	Free a queue.
63
64	Queue *queue The queue to be freed.
65	++++++++++++++++++++++++++++++++++++++*/
66
67	void FreeQueueList(Queue *queue)
68	{
69	free(queue->data);
70
71	free(queue);
72	}
73
74
75	/*++++++++++++++++++++++++++++++++++++++
76	Insert a new item into the queue in the right place.
77
78	The data is stored in a "3-ary Heap" http://en.wikipedia.org/wiki/D-ary_heap
79	and this operation is adding an item to the heap.
80
81	Queue *queue The queue to insert the result into.
82
83	Result *result The result to insert into the queue.
84	++++++++++++++++++++++++++++++++++++++*/
85
86	void InsertInQueue(Queue queue,Result result)
87	{
88	uint32_t index;
89
90	if(result->queued==NOT_QUEUED)
91	{
92	if(queue->noccupied==queue->nallocated)
93	{
94	queue->nallocated=2*queue->nallocated;
95	queue->data=(Result*)realloc((void)queue->data,queue->nallocatedsizeof(Result));
96	}
97
98	index=queue->noccupied;
99	queue->noccupied++;
100
101	queue->data[index]=result;
102	queue->data[index]->queued=index;
103	}
104	else
105	{
106	index=result->queued;
107	}
108
109	/* Bubble up the new value */
110
111	while(index>0)
112	{
113	uint32_t newindex;
114	Result *temp;
115
116	newindex=(index-1)/3;
117
118	if(queue->data[index]->sortby>=queue->data[newindex]->sortby)
119	break;
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 "3-ary Heap" http://en.wikipedia.org/wiki/D-ary_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((3*index+3)<queue->noccupied)
163	{
164	uint32_t childindex,newindex;
165	Result *temp;
166
167	childindex=newindex=3*index+1;
168
169	if(queue->data[newindex]->sortby>queue->data[++childindex]->sortby)
170	newindex=childindex;
171	if(queue->data[newindex]->sortby>queue->data[++childindex]->sortby)
172	newindex=childindex;
173
174	if(queue->data[index]->sortby<=queue->data[newindex]->sortby)
175	break;
176
177	temp=queue->data[newindex];
178	queue->data[newindex]=queue->data[index];
179	queue->data[index]=temp;
180
181	queue->data[index]->queued=index;
182	queue->data[newindex]->queued=newindex;
183
184	index=newindex;
185	}
186
187	if((3*index+3)==queue->noccupied)
188	{
189	uint32_t childindex,newindex;
190	Result *temp;
191
192	childindex=newindex=3*index+1;
193
194	if(queue->data[newindex]->sortby>queue->data[++childindex]->sortby)
195	newindex=childindex;
196
197	if(queue->data[index]->sortby<=queue->data[newindex]->sortby)
198	; /* break */
199	else
200	{
201	temp=queue->data[newindex];
202	queue->data[newindex]=queue->data[index];
203	queue->data[index]=temp;
204
205	queue->data[index]->queued=index;
206	queue->data[newindex]->queued=newindex;
207	}
208	}
209
210	else if((3*index+2)==queue->noccupied)
211	{
212	uint32_t newindex;
213	Result *temp;
214
215	newindex=3*index+1;
216
217	if(queue->data[index]->sortby<=queue->data[newindex]->sortby)
218	; /* break */
219	else
220	{
221	temp=queue->data[newindex];
222	queue->data[newindex]=queue->data[index];
223	queue->data[index]=temp;
224
225	queue->data[index]->queued=index;
226	queue->data[newindex]->queued=newindex;
227	}
228	}
229
230	return(retval);
231	}