Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Contents of /trunk/src/queue.c
Parent Directory
|
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)
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. |