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