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 | */ |
28 | typedef int(aws_priority_queue_compare_fn)(const void *a, const void *b); |
29 | |
30 | struct 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 | |
53 | struct 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 | |
58 | AWS_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 | */ |
66 | AWS_COMMON_API |
67 | int 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 | */ |
86 | AWS_COMMON_API |
87 | void 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 | */ |
98 | bool 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 | */ |
106 | bool 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 | */ |
112 | bool 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 | */ |
117 | AWS_COMMON_API |
118 | bool 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 | */ |
123 | AWS_COMMON_API |
124 | void 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 | */ |
129 | AWS_COMMON_API |
130 | int 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 | */ |
143 | AWS_COMMON_API |
144 | int 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 | */ |
153 | AWS_COMMON_API |
154 | int 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 | */ |
163 | AWS_COMMON_API |
164 | int 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 | */ |
170 | AWS_COMMON_API |
171 | int aws_priority_queue_top(const struct aws_priority_queue *queue, void **item); |
172 | |
173 | /** |
174 | * Current number of elements in the queue |
175 | */ |
176 | AWS_COMMON_API |
177 | size_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 | */ |
183 | AWS_COMMON_API |
184 | size_t aws_priority_queue_capacity(const struct aws_priority_queue *queue); |
185 | |
186 | AWS_EXTERN_C_END |
187 | |
188 | #endif /* AWS_COMMON_PRIORITY_QUEUE_H */ |
189 | |