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
24static 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 */
60static 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. */
107static 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 */
144static 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
155int 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
179void 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
199bool 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
210bool 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
222bool 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
256bool 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
268void 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
275int 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
283int 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
332backpointer_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
339static 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
373int 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
389int 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
399int 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
404size_t aws_priority_queue_size(const struct aws_priority_queue *queue) {
405 return aws_array_list_length(&queue->container);
406}
407
408size_t aws_priority_queue_capacity(const struct aws_priority_queue *queue) {
409 return aws_array_list_capacity(&queue->container);
410}
411