1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
|
/*
* Copyright (c) 2017 Cisco and/or its affiliates.
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at:
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/**
* @file parc_PriorityQueue.h
* @ingroup datastructures
* @brief A priority queue (heap), where the top item is the minimum by the sort function.
*
* The user provides a sort function and the top item will be the minimum
* as per the < relation.
*
*/
#ifndef libparc_parc_PriorityQueue_h
#define libparc_parc_PriorityQueue_h
#include <stdlib.h>
#include <stdbool.h>
struct parc_priority_queue;
typedef struct parc_priority_queue PARCPriorityQueue;
typedef int (PARCPriorityQueueCompareTo)(const void *a, const void *b);
typedef void (PARCPriorityQueueDestroyer)(void **elementPtr);
/**
* Calls {@link parcMemory_Deallocate} to free the element
*
* A simple destroyer that only uses {@link parcMemory_Deallocate}.
*
* @param [in,out] elementPtr Double pointer to data item, will be NULL'd
*
* Example:
* @code
*
* PARCPriorityQueue *q = parcPriorityQueue_Create(parcPriorityQueue_Uint64CompareTo, parcPriorityQueue_ParcFreeDestroyer);
* uint64_t *objectid = parcMemory_Allocate(sizeof(uint64_t));
* objectid = 100;
*
* // this will use parcPriorityQueue_Uint64CompareTo sort order
* parcPriorityQueue_Add(q, objectid);
*
* // this will use the ParcFreeDestroyer
* parcPriorityQueue_Destroy(&q);
* @endcode
*/
void parcPriorityQueue_ParcFreeDestroyer(void **elementPtr);
/**
* Treats the parameters as `uint64_t` pointers and compares them via natural sort order.
*
* Treats the parameters as `uint64_t` pointers and compares them via natural sort order.
* Obeys standared CompareTo semantics.
*
* @param [in] a uint64_t pointer
* @param [in] b uint64_t pointer
*
* @return -1 if a < b
* @return 0 if a == b
* @return +1 if a > b
*
* Example:
* @code
*
* PARCPriorityQueue *q = parcPriorityQueue_Create(parcPriorityQueue_Uint64CompareTo, parcPriorityQueue_ParcFreeDestroyer);
* uint64_t *objectid = parcMemory_Allocate(sizeof(uint64_t));
* objectid = 100;
*
* // this will use parcPriorityQueue_Uint64CompareTo sort order
* parcPriorityQueue_Add(q, objectid);
*
* // this will use the ParcFreeDestroyer
* parcPriorityQueue_Destroy(&q);
* @endcode
*/
int parcPriorityQueue_Uint64CompareTo(const void *a, const void *b);
/**
* Creates a priority queue with a given sort function.
*
* The sort function defines the ordering of the Priorty Queue. The minimum element
* will always be the head of the queue.
*
* The destroyer is called on data elements from {@link parcPriorityQueue_Clear()} and
* {@link parcPriorityQueue_Destroy()}. You may use {@linkparcPriorityQueue_ParcFreeDestroyer()} for
* elements that can be freed by only calling {@link parcMemory_Deallocate}.
*
* @param [in] compare Defines the sort order of the priority queue
* @param [in] destroyer Called for Clear and Destroy operations, may be NULL.
*
* @return non-null A pointer to a `PARCPriorityQueue`
*
* Example:
* @code
* PARCPriorityQueue *q = parcPriorityQueue_Create(parcPriorityQueue_Uint64CompareTo, parcPriorityQueue_ParcFreeDestroyer);
* uint64_t *objectid = parcMemory_Allocate(sizeof(uint64_t));
* objectid = 100;
*
* // this will use parcPriorityQueue_Uint64CompareTo sort order
* parcPriorityQueue_Add(q, objectid);
*
* // this will use the ParcFreeDestroyer
* parcPriorityQueue_Destroy(&q);
* @endcode
*/
PARCPriorityQueue *parcPriorityQueue_Create(PARCPriorityQueueCompareTo *compare, PARCPriorityQueueDestroyer *destroyer);
/**
* Destroy the queue and free remaining elements.
*
* Destroys the queue. If the destroyer was set in Create, then it will be called
* on all the remaining elements.
*
* @param [in,out] queuePtr Double pointer to allocated queue.
*
* Example:
* @code
* <#example#>
* @endcode
*/
void parcPriorityQueue_Destroy(PARCPriorityQueue **queuePtr);
/**
* Add an element to the priority queue, returning true if changed
*
* A "duplicate" is a data item that compares as equal to another item. The priority
* queue supports duplicates. It is not stable in regard to the ordering of duplicates.
* Because it supports duplicates, Add will always return true.
*
* The priority queue is unbounded.
*
* @param [in,out] queue The queue to modify
* @param [in] data The data to add to the queue, which must be comparable and not NULL
*
* @return true The data structure was modified by adding the new value
* @return false The data structure was not modified
*
* Example:
* @code
* <#example#>
* @endcode
*/
bool parcPriorityQueue_Add(PARCPriorityQueue *queue, void *data);
/**
* Removes all elements, calling the data structure's destroyer on each
*
* Remvoes all elements. If the data structure's destroyer is non-NULL, it will be called
* on each element.
*
* @param [in,out] queue The queue to modify
*
* Example:
* @code
* <#example#>
* @endcode
*/
void parcPriorityQueue_Clear(PARCPriorityQueue *queue);
/**
* Returns the head element, but does not remove it.
*
* Returns the head element. The data structure is not modified. If the
* priority queue is empty, will return NULL.
*
* @param [in] queue The `PARCPriorityQueue` to query.
*
* @return non-null The head element
* @return null The queue is empty
*
* Example:
* @code
* <#example#>
* @endcode
*/
void *parcPriorityQueue_Peek(PARCPriorityQueue *queue);
/**
* Removes the head element from the queue and returns it.
*
* Removes the head element from the queue and returns it. If the queue is empty,
* it returns NULL.
*
* @param [in,out] queue The queue to query and modify.
*
* @return non-null The head element
* @return null The queue is empty
*
* Example:
* @code
* <#example#>
* @endcode
*/
void *parcPriorityQueue_Poll(PARCPriorityQueue *queue);
/**
* Returns the number of elements in the queue.
*
* @param [in] queue The `PARCPriorityQueue` to query.
*
* @return number The number of elements in the queue.
*
* Example:
* @code
* <#example#>
* @endcode
*/
size_t parcPriorityQueue_Size(const PARCPriorityQueue *queue);
#endif // libparc_parc_PriorityQueue_h
|
