Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

ViewVC logotype

Contents of /trunk/src/queue.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 873 - (show annotations) (download) (as text)
Sat Oct 22 14:04:52 2011 UTC (13 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 4842 byte(s)
Revert back to r864 zero-based binary heap but with r868/r869 refactored code.

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

Properties

Name Value
cvs:description Functions for handling the queue of partial routes.