1#ifndef AWS_COMMON_PRIORITY_QUEUE_H
2#define AWS_COMMON_PRIORITY_QUEUE_H
3/*
4 * Copyright 2010-2018 Amazon.com, Inc. or its affiliates. All Rights Reserved.
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License").
7 * You may not use this file except in compliance with the License.
8 * A copy of the License is located at
9 *
10 * http://aws.amazon.com/apache2.0
11 *
12 * or in the "license" file accompanying this file. This file is distributed
13 * on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
14 * express or implied. See the License for the specific language governing
15 * permissions and limitations under the License.
16 */
17
18#include <aws/common/array_list.h>
19#include <aws/common/common.h>
20
21/* The comparator should return a positive value if the second argument has a
22 * higher priority than the first; Otherwise, it should return a negative value
23 * or zero. NOTE: priority_queue pops its highest priority element first. For
24 * example: int cmp(const void *a, const void *b) { return a < b; } would result
25 * in a max heap, while: int cmp(const void *a, const void *b) { return a > b; }
26 * would result in a min heap.
27 */
28typedef int(aws_priority_queue_compare_fn)(const void *a, const void *b);
29
30struct aws_priority_queue {
31 /**
32 * predicate that determines the priority of the elements in the queue.
33 */
34 aws_priority_queue_compare_fn *pred;
35
36 /**
37 * The underlying container storing the queue elements.
38 */
39 struct aws_array_list container;
40
41 /**
42 * An array of pointers to backpointer elements. This array is initialized when
43 * the first call to aws_priority_queue_push_bp is made, and is subsequently maintained
44 * through any heap node manipulations.
45 *
46 * Each element is a struct aws_priority_queue_node *, pointing to a backpointer field
47 * owned by the calling code, or a NULL. The backpointer field is continually updated
48 * with information needed to locate and remove a specific node later on.
49 */
50 struct aws_array_list backpointers;
51};
52
53struct aws_priority_queue_node {
54 /** The current index of the node in queuesion, or SIZE_MAX if the node has been removed. */
55 size_t current_index;
56};
57
58AWS_EXTERN_C_BEGIN
59
60/**
61 * Initializes a priority queue struct for use. This mode will grow memory automatically (exponential model)
62 * Default size is the inital size of the queue
63 * item_size is the size of each element in bytes. Mixing items types is not supported by this API.
64 * pred is the function that will be used to determine priority.
65 */
66AWS_COMMON_API
67int aws_priority_queue_init_dynamic(
68 struct aws_priority_queue *queue,
69 struct aws_allocator *alloc,
70 size_t default_size,
71 size_t item_size,
72 aws_priority_queue_compare_fn *pred);
73
74/**
75 * Initializes a priority queue struct for use. This mode will not allocate any additional memory. When the heap fills
76 * new enqueue operations will fail with AWS_ERROR_PRIORITY_QUEUE_FULL.
77 *
78 * Heaps initialized using this call do not support the aws_priority_queue_push_ref call with a non-NULL backpointer
79 * parameter.
80 *
81 * heap is the raw memory allocated for this priority_queue
82 * item_count is the maximum number of elements the raw heap can contain
83 * item_size is the size of each element in bytes. Mixing items types is not supported by this API.
84 * pred is the function that will be used to determine priority.
85 */
86AWS_COMMON_API
87void aws_priority_queue_init_static(
88 struct aws_priority_queue *queue,
89 void *heap,
90 size_t item_count,
91 size_t item_size,
92 aws_priority_queue_compare_fn *pred);
93
94/**
95 * Checks that the backpointer at a specific index of the queue is
96 * NULL or points to a correctly allocated aws_priority_queue_node.
97 */
98bool aws_priority_queue_backpointer_index_valid(const struct aws_priority_queue *const queue, size_t index);
99
100/**
101 * Checks that the backpointers of the priority queue are either NULL
102 * or correctly allocated to point at aws_priority_queue_nodes. This
103 * check is O(n), as it accesses every backpointer in a loop, and thus
104 * shouldn't be used carelessly.
105 */
106bool aws_priority_queue_backpointers_valid_deep(const struct aws_priority_queue *const queue);
107
108/**
109 * Checks that the backpointers of the priority queue satisfy validity
110 * constraints.
111 */
112bool aws_priority_queue_backpointers_valid(const struct aws_priority_queue *const queue);
113
114/**
115 * Set of properties of a valid aws_priority_queue.
116 */
117AWS_COMMON_API
118bool aws_priority_queue_is_valid(const struct aws_priority_queue *const queue);
119
120/**
121 * Cleans up any internally allocated memory and resets the struct for reuse or deletion.
122 */
123AWS_COMMON_API
124void aws_priority_queue_clean_up(struct aws_priority_queue *queue);
125
126/**
127 * Copies item into the queue and places it in the proper priority order. Complexity: O(log(n)).
128 */
129AWS_COMMON_API
130int aws_priority_queue_push(struct aws_priority_queue *queue, void *item);
131
132/**
133 * Copies item into the queue and places it in the proper priority order. Complexity: O(log(n)).
134 *
135 * If the backpointer parameter is non-null, the heap will continually update the pointed-to field
136 * with information needed to remove the node later on. *backpointer must remain valid until the node
137 * is removed from the heap, and may be updated on any mutating operation on the priority queue.
138 *
139 * If the node is removed, the backpointer will be set to a sentinel value that indicates that the
140 * node has already been removed. It is safe (and a no-op) to call aws_priority_queue_remove with
141 * such a sentinel value.
142 */
143AWS_COMMON_API
144int aws_priority_queue_push_ref(
145 struct aws_priority_queue *queue,
146 void *item,
147 struct aws_priority_queue_node *backpointer);
148
149/**
150 * Copies the element of the highest priority, and removes it from the queue.. Complexity: O(log(n)).
151 * If queue is empty, AWS_ERROR_PRIORITY_QUEUE_EMPTY will be raised.
152 */
153AWS_COMMON_API
154int aws_priority_queue_pop(struct aws_priority_queue *queue, void *item);
155
156/**
157 * Removes a specific node from the priority queue. Complexity: O(log(n))
158 * After removing a node (using either _remove or _pop), the backpointer set at push_ref time is set
159 * to a sentinel value. If this sentinel value is passed to aws_priority_queue_remove,
160 * AWS_ERROR_PRIORITY_QUEUE_BAD_NODE will be raised. Note, however, that passing uninitialized
161 * aws_priority_queue_nodes, or ones from different priority queues, results in undefined behavior.
162 */
163AWS_COMMON_API
164int aws_priority_queue_remove(struct aws_priority_queue *queue, void *item, const struct aws_priority_queue_node *node);
165
166/**
167 * Obtains a pointer to the element of the highest priority. Complexity: constant time.
168 * If queue is empty, AWS_ERROR_PRIORITY_QUEUE_EMPTY will be raised.
169 */
170AWS_COMMON_API
171int aws_priority_queue_top(const struct aws_priority_queue *queue, void **item);
172
173/**
174 * Current number of elements in the queue
175 */
176AWS_COMMON_API
177size_t aws_priority_queue_size(const struct aws_priority_queue *queue);
178
179/**
180 * Current allocated capacity for the queue, in dynamic mode this grows over time, in static mode, this will never
181 * change.
182 */
183AWS_COMMON_API
184size_t aws_priority_queue_capacity(const struct aws_priority_queue *queue);
185
186AWS_EXTERN_C_END
187
188#endif /* AWS_COMMON_PRIORITY_QUEUE_H */
189