trunk/src/queue.c

/***************************************
 $Header: /home/amb/CVS/routino/src/queue.c,v 1.2 2009-08-15 14:18:23 amb Exp $

 Queue data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008,2009 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 *NewQueue Returns the queue.
  ++++++++++++++++++++++++++++++++++++++*/

Queue *NewQueueList(void)
{
 Queue *queue;

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

 queue->nallocated=1023;
 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.

  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==~0)
   {
    if(queue->noccupied==queue->nallocated)
      {
       queue->nallocated=2*queue->nallocated+1;
       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 &&
       queue->data[index]->sortby<queue->data[index/2]->sortby)
   {
    uint32_t newindex;
    Result *temp;

    newindex=index/2;

    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 end of the queue.

  Result *PopFromQueue Returns the top item.

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

Result *PopFromQueue(Queue *queue)
{
 uint32_t index;
 Result *retval=queue->data[0];

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

 index=0;
 queue->noccupied--;

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

 /* Bubble down the newly promoted value */

 while((2*index+2)<queue->noccupied &&
       (queue->data[index]->sortby>queue->data[2*index+1]->sortby ||
        queue->data[index]->sortby>queue->data[2*index+2]->sortby))
   {
    uint32_t newindex;
    Result *temp;

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

    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((2*index+2)==queue->noccupied &&
    queue->data[index]->sortby>queue->data[2*index+1]->sortby) /* only one child and needs bubbling */
   {
    uint32_t newindex;
    Result *temp;

    newindex=2*index+1;

    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	$Header: /home/amb/CVS/routino/src/queue.c,v 1.2 2009-08-15 14:18:23 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 *NewQueue 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->nallocatedsizeof(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	Queue *queue The queue to insert the result into.
81
82	Result *result The result to insert into the queue.
83	++++++++++++++++++++++++++++++++++++++*/
84
85	void InsertInQueue(Queue queue,Result result)
86	{
87	uint32_t index;
88
89	if(result->queued==~0)
90	{
91	if(queue->noccupied==queue->nallocated)
92	{
93	queue->nallocated=2*queue->nallocated+1;
94	queue->data=(Result*)realloc((void)queue->data,queue->nallocatedsizeof(Result));
95	}
96
97	index=queue->noccupied;
98	queue->noccupied++;
99
100	queue->data[index]=result;
101	queue->data[index]->queued=index;
102	}
103	else
104	{
105	index=result->queued;
106	}
107
108	/* Bubble up the new value */
109
110	while(index>0 &&
111	queue->data[index]->sortby<queue->data[index/2]->sortby)
112	{
113	uint32_t newindex;
114	Result *temp;
115
116	newindex=index/2;
117
118	temp=queue->data[index];
119	queue->data[index]=queue->data[newindex];
120	queue->data[newindex]=temp;
121
122	queue->data[index]->queued=index;
123	queue->data[newindex]->queued=newindex;
124
125	index=newindex;
126	}
127	}
128
129
130	/*++++++++++++++++++++++++++++++++++++++
131	Pop an item from the end of the queue.
132
133	Result *PopFromQueue Returns the top item.
134
135	Queue *queue The queue to remove the result from.
136	++++++++++++++++++++++++++++++++++++++*/
137
138	Result PopFromQueue(Queue queue)
139	{
140	uint32_t index;
141	Result *retval=queue->data[0];
142
143	if(queue->noccupied==0)
144	return(NULL);
145
146	index=0;
147	queue->noccupied--;
148
149	queue->data[index]=queue->data[queue->noccupied];
150
151	/* Bubble down the newly promoted value */
152
153	while((2*index+2)<queue->noccupied &&
154	(queue->data[index]->sortby>queue->data[2*index+1]->sortby \|\|
155	queue->data[index]->sortby>queue->data[2*index+2]->sortby))
156	{
157	uint32_t newindex;
158	Result *temp;
159
160	if(queue->data[2index+1]->sortby<queue->data[2index+2]->sortby)
161	newindex=2*index+1;
162	else
163	newindex=2*index+2;
164
165	temp=queue->data[newindex];
166	queue->data[newindex]=queue->data[index];
167	queue->data[index]=temp;
168
169	queue->data[index]->queued=index;
170	queue->data[newindex]->queued=newindex;
171
172	index=newindex;
173	}
174
175	if((2*index+2)==queue->noccupied &&
176	queue->data[index]->sortby>queue->data[2index+1]->sortby) / only one child and needs bubbling */
177	{
178	uint32_t newindex;
179	Result *temp;
180
181	newindex=2*index+1;
182
183	temp=queue->data[newindex];
184	queue->data[newindex]=queue->data[index];
185	queue->data[index]=temp;
186
187	queue->data[index]->queued=index;
188	queue->data[newindex]->queued=newindex;
189	}
190
191	return(retval);
192	}