1 | /* |
2 | * Copyright 2010-2017 Amazon.com, Inc. or its affiliates. All Rights Reserved. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"). |
5 | * You may not use this file except in compliance with the License. |
6 | * A copy of the License is located at |
7 | * |
8 | * http://aws.amazon.com/apache2.0 |
9 | * |
10 | * or in the "license" file accompanying this file. This file is distributed |
11 | * on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either |
12 | * express or implied. See the License for the specific language governing |
13 | * permissions and limitations under the License. |
14 | */ |
15 | |
16 | #include <aws/common/priority_queue.h> |
17 | |
18 | #include <string.h> |
19 | |
20 | #define PARENT_OF(index) (((index)&1) ? (index) >> 1 : (index) > 1 ? ((index)-2) >> 1 : 0) |
21 | #define LEFT_OF(index) (((index) << 1) + 1) |
22 | #define RIGHT_OF(index) (((index) << 1) + 2) |
23 | |
24 | static void s_swap(struct aws_priority_queue *queue, size_t a, size_t b) { |
25 | AWS_PRECONDITION(aws_priority_queue_is_valid(queue)); |
26 | AWS_PRECONDITION(a < queue->container.length); |
27 | AWS_PRECONDITION(b < queue->container.length); |
28 | AWS_PRECONDITION(aws_priority_queue_backpointer_index_valid(queue, a)); |
29 | AWS_PRECONDITION(aws_priority_queue_backpointer_index_valid(queue, b)); |
30 | |
31 | aws_array_list_swap(&queue->container, a, b); |
32 | |
33 | /* Invariant: If the backpointer array is initialized, we have enough room for all elements */ |
34 | if (!AWS_IS_ZEROED(queue->backpointers)) { |
35 | AWS_ASSERT(queue->backpointers.length > a); |
36 | AWS_ASSERT(queue->backpointers.length > b); |
37 | |
38 | struct aws_priority_queue_node **bp_a = &((struct aws_priority_queue_node **)queue->backpointers.data)[a]; |
39 | struct aws_priority_queue_node **bp_b = &((struct aws_priority_queue_node **)queue->backpointers.data)[b]; |
40 | |
41 | struct aws_priority_queue_node *tmp = *bp_a; |
42 | *bp_a = *bp_b; |
43 | *bp_b = tmp; |
44 | |
45 | if (*bp_a) { |
46 | (*bp_a)->current_index = a; |
47 | } |
48 | |
49 | if (*bp_b) { |
50 | (*bp_b)->current_index = b; |
51 | } |
52 | } |
53 | AWS_POSTCONDITION(aws_priority_queue_is_valid(queue)); |
54 | AWS_POSTCONDITION(aws_priority_queue_backpointer_index_valid(queue, a)); |
55 | AWS_POSTCONDITION(aws_priority_queue_backpointer_index_valid(queue, b)); |
56 | } |
57 | |
58 | /* Precondition: with the exception of the given root element, the container must be |
59 | * in heap order */ |
60 | static bool s_sift_down(struct aws_priority_queue *queue, size_t root) { |
61 | AWS_PRECONDITION(aws_priority_queue_is_valid(queue)); |
62 | AWS_PRECONDITION(root < queue->container.length); |
63 | |
64 | bool did_move = false; |
65 | |
66 | size_t len = aws_array_list_length(&queue->container); |
67 | |
68 | while (LEFT_OF(root) < len) { |
69 | size_t left = LEFT_OF(root); |
70 | size_t right = RIGHT_OF(root); |
71 | size_t first = root; |
72 | void *first_item = NULL, *other_item = NULL; |
73 | |
74 | aws_array_list_get_at_ptr(&queue->container, &first_item, root); |
75 | aws_array_list_get_at_ptr(&queue->container, &other_item, left); |
76 | |
77 | if (queue->pred(first_item, other_item) > 0) { |
78 | first = left; |
79 | first_item = other_item; |
80 | } |
81 | |
82 | if (right < len) { |
83 | aws_array_list_get_at_ptr(&queue->container, &other_item, right); |
84 | |
85 | /* choose the larger/smaller of the two in case of a max/min heap |
86 | * respectively */ |
87 | if (queue->pred(first_item, other_item) > 0) { |
88 | first = right; |
89 | first_item = other_item; |
90 | } |
91 | } |
92 | |
93 | if (first != root) { |
94 | s_swap(queue, first, root); |
95 | did_move = true; |
96 | root = first; |
97 | } else { |
98 | break; |
99 | } |
100 | } |
101 | |
102 | AWS_POSTCONDITION(aws_priority_queue_is_valid(queue)); |
103 | return did_move; |
104 | } |
105 | |
106 | /* Precondition: Elements prior to the specified index must be in heap order. */ |
107 | static bool s_sift_up(struct aws_priority_queue *queue, size_t index) { |
108 | AWS_PRECONDITION(aws_priority_queue_is_valid(queue)); |
109 | AWS_PRECONDITION(index < queue->container.length); |
110 | |
111 | bool did_move = false; |
112 | |
113 | void *parent_item, *child_item; |
114 | size_t parent = PARENT_OF(index); |
115 | while (index) { |
116 | /* |
117 | * These get_ats are guaranteed to be successful; if they are not, we have |
118 | * serious state corruption, so just abort. |
119 | */ |
120 | |
121 | if (aws_array_list_get_at_ptr(&queue->container, &parent_item, parent) || |
122 | aws_array_list_get_at_ptr(&queue->container, &child_item, index)) { |
123 | abort(); |
124 | } |
125 | |
126 | if (queue->pred(parent_item, child_item) > 0) { |
127 | s_swap(queue, index, parent); |
128 | did_move = true; |
129 | index = parent; |
130 | parent = PARENT_OF(index); |
131 | } else { |
132 | break; |
133 | } |
134 | } |
135 | |
136 | AWS_POSTCONDITION(aws_priority_queue_is_valid(queue)); |
137 | return did_move; |
138 | } |
139 | |
140 | /* |
141 | * Precondition: With the exception of the given index, the heap condition holds for all elements. |
142 | * In particular, the parent of the current index is a predecessor of all children of the current index. |
143 | */ |
144 | static void s_sift_either(struct aws_priority_queue *queue, size_t index) { |
145 | AWS_PRECONDITION(aws_priority_queue_is_valid(queue)); |
146 | AWS_PRECONDITION(index < queue->container.length); |
147 | |
148 | if (!index || !s_sift_up(queue, index)) { |
149 | s_sift_down(queue, index); |
150 | } |
151 | |
152 | AWS_POSTCONDITION(aws_priority_queue_is_valid(queue)); |
153 | } |
154 | |
155 | int aws_priority_queue_init_dynamic( |
156 | struct aws_priority_queue *queue, |
157 | struct aws_allocator *alloc, |
158 | size_t default_size, |
159 | size_t item_size, |
160 | aws_priority_queue_compare_fn *pred) { |
161 | |
162 | AWS_FATAL_PRECONDITION(queue != NULL); |
163 | AWS_FATAL_PRECONDITION(alloc != NULL); |
164 | AWS_FATAL_PRECONDITION(item_size > 0); |
165 | |
166 | queue->pred = pred; |
167 | AWS_ZERO_STRUCT(queue->backpointers); |
168 | |
169 | int ret = aws_array_list_init_dynamic(&queue->container, alloc, default_size, item_size); |
170 | if (ret == AWS_OP_SUCCESS) { |
171 | AWS_POSTCONDITION(aws_priority_queue_is_valid(queue)); |
172 | } else { |
173 | AWS_POSTCONDITION(AWS_IS_ZEROED(queue->container)); |
174 | AWS_POSTCONDITION(AWS_IS_ZEROED(queue->backpointers)); |
175 | } |
176 | return ret; |
177 | } |
178 | |
179 | void aws_priority_queue_init_static( |
180 | struct aws_priority_queue *queue, |
181 | void *heap, |
182 | size_t item_count, |
183 | size_t item_size, |
184 | aws_priority_queue_compare_fn *pred) { |
185 | |
186 | AWS_FATAL_PRECONDITION(queue != NULL); |
187 | AWS_FATAL_PRECONDITION(heap != NULL); |
188 | AWS_FATAL_PRECONDITION(item_count > 0); |
189 | AWS_FATAL_PRECONDITION(item_size > 0); |
190 | |
191 | queue->pred = pred; |
192 | AWS_ZERO_STRUCT(queue->backpointers); |
193 | |
194 | aws_array_list_init_static(&queue->container, heap, item_count, item_size); |
195 | |
196 | AWS_POSTCONDITION(aws_priority_queue_is_valid(queue)); |
197 | } |
198 | |
199 | bool aws_priority_queue_backpointer_index_valid(const struct aws_priority_queue *const queue, size_t index) { |
200 | if (AWS_IS_ZEROED(queue->backpointers)) { |
201 | return true; |
202 | } |
203 | if (index < queue->backpointers.length) { |
204 | struct aws_priority_queue_node *node = ((struct aws_priority_queue_node **)queue->backpointers.data)[index]; |
205 | return (node == NULL) || AWS_MEM_IS_WRITABLE(node, sizeof(struct aws_priority_queue_node)); |
206 | } |
207 | return false; |
208 | } |
209 | |
210 | bool aws_priority_queue_backpointers_valid_deep(const struct aws_priority_queue *const queue) { |
211 | if (!queue) { |
212 | return false; |
213 | } |
214 | for (size_t i = 0; i < queue->backpointers.length; i++) { |
215 | if (!aws_priority_queue_backpointer_index_valid(queue, i)) { |
216 | return false; |
217 | } |
218 | } |
219 | return true; |
220 | } |
221 | |
222 | bool aws_priority_queue_backpointers_valid(const struct aws_priority_queue *const queue) { |
223 | if (!queue) { |
224 | return false; |
225 | } |
226 | |
227 | /* Internal container validity */ |
228 | bool backpointer_list_is_valid = |
229 | ((aws_array_list_is_valid(&queue->backpointers) && (queue->backpointers.current_size != 0) && |
230 | (queue->backpointers.data != NULL))); |
231 | |
232 | /* Backpointer struct should either be zero or should be |
233 | * initialized to be at most as long as the container, and having |
234 | * as elements potentially null pointers to |
235 | * aws_priority_queue_nodes */ |
236 | bool backpointer_list_item_size = queue->backpointers.item_size == sizeof(struct aws_priority_queue_node *); |
237 | bool lists_equal_lengths = queue->backpointers.length == queue->container.length; |
238 | bool backpointers_non_zero_current_size = queue->backpointers.current_size > 0; |
239 | |
240 | /* This check must be guarded, as it is not efficient, neither |
241 | * when running tests nor CBMC */ |
242 | #if (AWS_DEEP_CHECKS == 1) |
243 | bool backpointers_valid_deep = aws_priority_queue_backpointers_valid_deep(queue); |
244 | #else |
245 | bool backpointers_valid_deep = true; |
246 | #endif |
247 | bool backpointers_zero = |
248 | (queue->backpointers.current_size == 0 && queue->backpointers.length == 0 && queue->backpointers.data == NULL); |
249 | bool backpointer_struct_is_valid = |
250 | backpointers_zero || (backpointer_list_item_size && lists_equal_lengths && backpointers_non_zero_current_size && |
251 | backpointers_valid_deep); |
252 | |
253 | return ((backpointer_list_is_valid && backpointer_struct_is_valid) || AWS_IS_ZEROED(queue->backpointers)); |
254 | } |
255 | |
256 | bool aws_priority_queue_is_valid(const struct aws_priority_queue *const queue) { |
257 | /* Pointer validity checks */ |
258 | if (!queue) { |
259 | return false; |
260 | } |
261 | bool pred_is_valid = (queue->pred != NULL); |
262 | bool container_is_valid = aws_array_list_is_valid(&queue->container); |
263 | |
264 | bool backpointers_valid = aws_priority_queue_backpointers_valid(queue); |
265 | return pred_is_valid && container_is_valid && backpointers_valid; |
266 | } |
267 | |
268 | void aws_priority_queue_clean_up(struct aws_priority_queue *queue) { |
269 | aws_array_list_clean_up(&queue->container); |
270 | if (!AWS_IS_ZEROED(queue->backpointers)) { |
271 | aws_array_list_clean_up(&queue->backpointers); |
272 | } |
273 | } |
274 | |
275 | int aws_priority_queue_push(struct aws_priority_queue *queue, void *item) { |
276 | AWS_PRECONDITION(aws_priority_queue_is_valid(queue)); |
277 | AWS_PRECONDITION(item && AWS_MEM_IS_READABLE(item, queue->container.item_size)); |
278 | int rval = aws_priority_queue_push_ref(queue, item, NULL); |
279 | AWS_POSTCONDITION(aws_priority_queue_is_valid(queue)); |
280 | return rval; |
281 | } |
282 | |
283 | int aws_priority_queue_push_ref( |
284 | struct aws_priority_queue *queue, |
285 | void *item, |
286 | struct aws_priority_queue_node *backpointer) { |
287 | AWS_PRECONDITION(aws_priority_queue_is_valid(queue)); |
288 | AWS_PRECONDITION(item && AWS_MEM_IS_READABLE(item, queue->container.item_size)); |
289 | |
290 | int err = aws_array_list_push_back(&queue->container, item); |
291 | if (err) { |
292 | AWS_POSTCONDITION(aws_priority_queue_is_valid(queue)); |
293 | return err; |
294 | } |
295 | size_t index = aws_array_list_length(&queue->container) - 1; |
296 | |
297 | if (backpointer && !queue->backpointers.alloc) { |
298 | if (!queue->container.alloc) { |
299 | aws_raise_error(AWS_ERROR_UNSUPPORTED_OPERATION); |
300 | goto backpointer_update_failed; |
301 | } |
302 | |
303 | if (aws_array_list_init_dynamic( |
304 | &queue->backpointers, queue->container.alloc, index + 1, sizeof(struct aws_priority_queue_node *))) { |
305 | goto backpointer_update_failed; |
306 | } |
307 | |
308 | /* When we initialize the backpointers array we need to zero out all existing entries */ |
309 | memset(queue->backpointers.data, 0, queue->backpointers.current_size); |
310 | } |
311 | |
312 | /* |
313 | * Once we have any backpointers, we want to make sure we always have room in the backpointers array |
314 | * for all elements; otherwise, sift_down gets complicated if it runs out of memory when sifting an |
315 | * element with a backpointer down in the array. |
316 | */ |
317 | if (!AWS_IS_ZEROED(queue->backpointers)) { |
318 | if (aws_array_list_set_at(&queue->backpointers, &backpointer, index)) { |
319 | goto backpointer_update_failed; |
320 | } |
321 | } |
322 | |
323 | if (backpointer) { |
324 | backpointer->current_index = index; |
325 | } |
326 | |
327 | s_sift_up(queue, aws_array_list_length(&queue->container) - 1); |
328 | |
329 | AWS_POSTCONDITION(aws_priority_queue_is_valid(queue)); |
330 | return AWS_OP_SUCCESS; |
331 | |
332 | backpointer_update_failed: |
333 | /* Failed to initialize or grow the backpointer array, back out the node addition */ |
334 | aws_array_list_pop_back(&queue->container); |
335 | AWS_POSTCONDITION(aws_priority_queue_is_valid(queue)); |
336 | return AWS_OP_ERR; |
337 | } |
338 | |
339 | static int s_remove_node(struct aws_priority_queue *queue, void *item, size_t item_index) { |
340 | AWS_PRECONDITION(aws_priority_queue_is_valid(queue)); |
341 | AWS_PRECONDITION(item && AWS_MEM_IS_WRITABLE(item, queue->container.item_size)); |
342 | if (aws_array_list_get_at(&queue->container, item, item_index)) { |
343 | /* shouldn't happen, but if it does we've already raised an error... */ |
344 | AWS_POSTCONDITION(aws_priority_queue_is_valid(queue)); |
345 | return AWS_OP_ERR; |
346 | } |
347 | |
348 | size_t swap_with = aws_array_list_length(&queue->container) - 1; |
349 | struct aws_priority_queue_node *backpointer = NULL; |
350 | |
351 | if (item_index != swap_with) { |
352 | s_swap(queue, item_index, swap_with); |
353 | } |
354 | |
355 | aws_array_list_pop_back(&queue->container); |
356 | |
357 | if (!AWS_IS_ZEROED(queue->backpointers)) { |
358 | aws_array_list_get_at(&queue->backpointers, &backpointer, swap_with); |
359 | if (backpointer) { |
360 | backpointer->current_index = SIZE_MAX; |
361 | } |
362 | aws_array_list_pop_back(&queue->backpointers); |
363 | } |
364 | |
365 | if (item_index != swap_with) { |
366 | s_sift_either(queue, item_index); |
367 | } |
368 | |
369 | AWS_POSTCONDITION(aws_priority_queue_is_valid(queue)); |
370 | return AWS_OP_SUCCESS; |
371 | } |
372 | |
373 | int aws_priority_queue_remove( |
374 | struct aws_priority_queue *queue, |
375 | void *item, |
376 | const struct aws_priority_queue_node *node) { |
377 | AWS_PRECONDITION(aws_priority_queue_is_valid(queue)); |
378 | AWS_PRECONDITION(item && AWS_MEM_IS_WRITABLE(item, queue->container.item_size)); |
379 | AWS_PRECONDITION(node && AWS_MEM_IS_READABLE(node, sizeof(struct aws_priority_queue_node))); |
380 | AWS_ERROR_PRECONDITION( |
381 | node->current_index < aws_array_list_length(&queue->container), AWS_ERROR_PRIORITY_QUEUE_BAD_NODE); |
382 | AWS_ERROR_PRECONDITION(queue->backpointers.data, AWS_ERROR_PRIORITY_QUEUE_BAD_NODE); |
383 | |
384 | int rval = s_remove_node(queue, item, node->current_index); |
385 | AWS_POSTCONDITION(aws_priority_queue_is_valid(queue)); |
386 | return rval; |
387 | } |
388 | |
389 | int aws_priority_queue_pop(struct aws_priority_queue *queue, void *item) { |
390 | AWS_PRECONDITION(aws_priority_queue_is_valid(queue)); |
391 | AWS_PRECONDITION(item && AWS_MEM_IS_WRITABLE(item, queue->container.item_size)); |
392 | AWS_ERROR_PRECONDITION(aws_array_list_length(&queue->container) != 0, AWS_ERROR_PRIORITY_QUEUE_EMPTY); |
393 | |
394 | int rval = s_remove_node(queue, item, 0); |
395 | AWS_POSTCONDITION(aws_priority_queue_is_valid(queue)); |
396 | return rval; |
397 | } |
398 | |
399 | int aws_priority_queue_top(const struct aws_priority_queue *queue, void **item) { |
400 | AWS_ERROR_PRECONDITION(aws_array_list_length(&queue->container) != 0, AWS_ERROR_PRIORITY_QUEUE_EMPTY); |
401 | return aws_array_list_get_at_ptr(&queue->container, item, 0); |
402 | } |
403 | |
404 | size_t aws_priority_queue_size(const struct aws_priority_queue *queue) { |
405 | return aws_array_list_length(&queue->container); |
406 | } |
407 | |
408 | size_t aws_priority_queue_capacity(const struct aws_priority_queue *queue) { |
409 | return aws_array_list_capacity(&queue->container); |
410 | } |
411 | |