-
Notifications
You must be signed in to change notification settings - Fork 2
/
CFBinaryHeap.h
320 lines (295 loc) · 14.6 KB
/
CFBinaryHeap.h
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
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
/*
* Copyright (c) 2008-2012 Brent Fulgham <[email protected]>. All rights reserved.
*
* This source code is a modified version of the CoreFoundation sources released by Apple Inc. under
* the terms of the APSL version 2.0 (see below).
*
* For information about changes from the original Apple source release can be found by reviewing the
* source control system for the project at https://sourceforge.net/svn/?group_id=246198.
*
* The original license information is as follows:
*
* Copyright (c) 2011 Apple Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
* This file contains Original Code and/or Modifications of Original Code
* as defined in and that are subject to the Apple Public Source License
* Version 2.0 (the 'License'). You may not use this file except in
* compliance with the License. Please obtain a copy of the License at
* http://www.opensource.apple.com/apsl/ and read it before using this
* file.
*
* The Original Code and all software distributed under the License are
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
* Please see the License for the specific language governing rights and
* limitations under the License.
*
* @APPLE_LICENSE_HEADER_END@
*/
/* CFBinaryHeap.h
Copyright (c) 1998-2011, Apple Inc. All rights reserved.
*/
/*!
@header CFBinaryHeap
CFBinaryHeap implements a container which stores values sorted using
a binary search algorithm. CFBinaryHeaps can be useful as priority
queues.
*/
#if !defined(__COREFOUNDATION_CFBINARYHEAP__)
#define __COREFOUNDATION_CFBINARYHEAP__ 1
#include <CoreFoundation/CFBase.h>
CF_EXTERN_C_BEGIN
typedef struct {
CFIndex version;
void * info;
const void *(*retain)(const void *info);
void (*release)(const void *info);
CFStringRef (*copyDescription)(const void *info);
} CFBinaryHeapCompareContext;
/*!
@typedef CFBinaryHeapCallBacks
Structure containing the callbacks for values of a CFBinaryHeap.
@field version The version number of the structure type being passed
in as a parameter to the CFBinaryHeap creation functions.
This structure is version 0.
@field retain The callback used to add a retain for the binary heap
on values as they are put into the binary heap.
This callback returns the value to use as the value in the
binary heap, which is usually the value parameter passed to
this callback, but may be a different value if a different
value should be added to the binary heap. The binary heap's
allocator is passed as the first argument.
@field release The callback used to remove a retain previously added
for the binary heap from values as they are removed from
the binary heap. The binary heap's allocator is passed as the
first argument.
@field copyDescription The callback used to create a descriptive
string representation of each value in the binary heap. This
is used by the CFCopyDescription() function.
@field compare The callback used to compare values in the binary heap for
equality in some operations.
*/
typedef struct {
CFIndex version;
const void *(*retain)(CFAllocatorRef allocator, const void *ptr);
void (*release)(CFAllocatorRef allocator, const void *ptr);
CFStringRef (*copyDescription)(const void *ptr);
CFComparisonResult (*compare)(const void *ptr1, const void *ptr2, void *context);
} CFBinaryHeapCallBacks;
/*!
@constant kCFStringBinaryHeapCallBacks
Predefined CFBinaryHeapCallBacks structure containing a set
of callbacks appropriate for use when the values in a CFBinaryHeap
are all CFString types.
*/
CF_EXPORT const CFBinaryHeapCallBacks kCFStringBinaryHeapCallBacks;
/*!
@typedef CFBinaryHeapApplierFunction
Type of the callback function used by the apply functions of
CFBinaryHeap.
@param value The current value from the binary heap.
@param context The user-defined context parameter given to the apply
function.
*/
typedef void (*CFBinaryHeapApplierFunction)(const void *val, void *context);
/*!
@typedef CFBinaryHeapRef
This is the type of a reference to CFBinaryHeaps.
*/
typedef struct __CFBinaryHeap * CFBinaryHeapRef;
/*!
@function CFBinaryHeapGetTypeID
Returns the type identifier of all CFBinaryHeap instances.
*/
CF_EXPORT CFTypeID CFBinaryHeapGetTypeID(void);
/*!
@function CFBinaryHeapCreate
Creates a new mutable binary heap with the given values.
@param allocator The CFAllocator which should be used to allocate
memory for the binary heap and its storage for values. This
parameter may be NULL in which case the current default
CFAllocator is used. If this reference is not a valid
CFAllocator, the behavior is undefined.
@param capacity A hint about the number of values that will be held
by the CFBinaryHeap. Pass 0 for no hint. The implementation may
ignore this hint, or may use it to optimize various
operations. A heap's actual capacity is only limited by
address space and available memory constraints). If this
parameter is negative, the behavior is undefined.
@param callBacks A pointer to a CFBinaryHeapCallBacks structure
initialized with the callbacks for the binary heap to use on
each value in the binary heap. A copy of the contents of the
callbacks structure is made, so that a pointer to a structure
on the stack can be passed in, or can be reused for multiple
binary heap creations. If the version field of this callbacks
structure is not one of the defined ones for CFBinaryHeap, the
behavior is undefined. The retain field may be NULL, in which
case the CFBinaryHeap will do nothing to add a retain to values
as they are put into the binary heap. The release field may be
NULL, in which case the CFBinaryHeap will do nothing to remove
the binary heap's retain (if any) on the values when the
heap is destroyed or a key-value pair is removed. If the
copyDescription field is NULL, the binary heap will create a
simple description for a value. If the equal field is NULL, the
binary heap will use pointer equality to test for equality of
values. This callbacks parameter itself may be NULL, which is
treated as if a valid structure of version 0 with all fields
NULL had been passed in. Otherwise,
if any of the fields are not valid pointers to functions
of the correct type, or this parameter is not a valid
pointer to a CFBinaryHeapCallBacks callbacks structure,
the behavior is undefined. If any of the values put into the
binary heap is not one understood by one of the callback functions
the behavior when that callback function is used is undefined.
@param compareContext A pointer to a CFBinaryHeapCompareContext structure.
@result A reference to the new CFBinaryHeap.
*/
CF_EXPORT CFBinaryHeapRef CFBinaryHeapCreate(CFAllocatorRef allocator, CFIndex capacity, const CFBinaryHeapCallBacks *callBacks, const CFBinaryHeapCompareContext *compareContext);
/*!
@function CFBinaryHeapCreateCopy
Creates a new mutable binary heap with the values from the given binary heap.
@param allocator The CFAllocator which should be used to allocate
memory for the binary heap and its storage for values. This
parameter may be NULL in which case the current default
CFAllocator is used. If this reference is not a valid
CFAllocator, the behavior is undefined.
@param capacity A hint about the number of values that will be held
by the CFBinaryHeap. Pass 0 for no hint. The implementation may
ignore this hint, or may use it to optimize various
operations. A heap's actual capacity is only limited by
address space and available memory constraints).
This parameter must be greater than or equal
to the count of the heap which is to be copied, or the
behavior is undefined. If this parameter is negative, the
behavior is undefined.
@param heap The binary heap which is to be copied. The values from the
binary heap are copied as pointers into the new binary heap (that is,
the values themselves are copied, not that which the values
point to, if anything). However, the values are also
retained by the new binary heap. The count of the new binary will
be the same as the given binary heap. The new binary heap uses the same
callbacks as the binary heap to be copied. If this parameter is
not a valid CFBinaryHeap, the behavior is undefined.
@result A reference to the new mutable binary heap.
*/
CF_EXPORT CFBinaryHeapRef CFBinaryHeapCreateCopy(CFAllocatorRef allocator, CFIndex capacity, CFBinaryHeapRef heap);
/*!
@function CFBinaryHeapGetCount
Returns the number of values currently in the binary heap.
@param heap The binary heap to be queried. If this parameter is not a valid
CFBinaryHeap, the behavior is undefined.
@result The number of values in the binary heap.
*/
CF_EXPORT CFIndex CFBinaryHeapGetCount(CFBinaryHeapRef heap);
/*!
@function CFBinaryHeapGetCountOfValue
Counts the number of times the given value occurs in the binary heap.
@param heap The binary heap to be searched. If this parameter is not a
valid CFBinaryHeap, the behavior is undefined.
@param value The value for which to find matches in the binary heap. The
compare() callback provided when the binary heap was created is
used to compare. If the compare() callback was NULL, pointer
equality (in C, ==) is used. If value, or any of the values
in the binary heap, are not understood by the compare() callback,
the behavior is undefined.
@result The number of times the given value occurs in the binary heap.
*/
CF_EXPORT CFIndex CFBinaryHeapGetCountOfValue(CFBinaryHeapRef heap, const void *value);
/*!
@function CFBinaryHeapContainsValue
Reports whether or not the value is in the binary heap.
@param heap The binary heap to be searched. If this parameter is not a
valid CFBinaryHeap, the behavior is undefined.
@param value The value for which to find matches in the binary heap. The
compare() callback provided when the binary heap was created is
used to compare. If the compare() callback was NULL, pointer
equality (in C, ==) is used. If value, or any of the values
in the binary heap, are not understood by the compare() callback,
the behavior is undefined.
@result true, if the value is in the specified binary heap, otherwise false.
*/
CF_EXPORT Boolean CFBinaryHeapContainsValue(CFBinaryHeapRef heap, const void *value);
/*!
@function CFBinaryHeapGetMinimum
Returns the minimum value is in the binary heap. If the heap contains several equal
minimum values, any one may be returned.
@param heap The binary heap to be searched. If this parameter is not a
valid CFBinaryHeap, the behavior is undefined.
@result A reference to the minimum value in the binary heap, or NULL if the
binary heap contains no values.
*/
CF_EXPORT const void * CFBinaryHeapGetMinimum(CFBinaryHeapRef heap);
/*!
@function CFBinaryHeapGetMinimumIfPresent
Returns the minimum value is in the binary heap, if present. If the heap contains several equal
minimum values, any one may be returned.
@param heap The binary heap to be searched. If this parameter is not a
valid CFBinaryHeap, the behavior is undefined.
@param value A C pointer to pointer-sized storage to be filled with the minimum value in
the binary heap. If this value is not a valid C pointer to a pointer-sized block
of storage, the result is undefined. If the result of the function is false, the value
stored at this address is undefined.
@result true, if a minimum value was found in the specified binary heap, otherwise false.
*/
CF_EXPORT Boolean CFBinaryHeapGetMinimumIfPresent(CFBinaryHeapRef heap, const void **value);
/*!
@function CFBinaryHeapGetValues
Fills the buffer with values from the binary heap.
@param heap The binary heap to be queried. If this parameter is not a
valid CFBinaryHeap, the behavior is undefined.
@param values A C array of pointer-sized values to be filled with
values from the binary heap. The values in the C array are ordered
from least to greatest. If this parameter is not a valid pointer to a
C array of at least CFBinaryHeapGetCount() pointers, the behavior is undefined.
*/
CF_EXPORT void CFBinaryHeapGetValues(CFBinaryHeapRef heap, const void **values);
/*!
@function CFBinaryHeapApplyFunction
Calls a function once for each value in the binary heap.
@param heap The binary heap to be operated upon. If this parameter is not a
valid CFBinaryHeap, the behavior is undefined.
@param applier The callback function to call once for each value in
the given binary heap. If this parameter is not a
pointer to a function of the correct prototype, the behavior
is undefined. If there are values in the binary heap which the
applier function does not expect or cannot properly apply
to, the behavior is undefined.
@param context A pointer-sized user-defined value, which is passed
as the second parameter to the applier function, but is
otherwise unused by this function. If the context is not
what is expected by the applier function, the behavior is
undefined.
*/
CF_EXPORT void CFBinaryHeapApplyFunction(CFBinaryHeapRef heap, CFBinaryHeapApplierFunction applier, void *context);
/*!
@function CFBinaryHeapAddValue
Adds the value to the binary heap.
@param heap The binary heap to which the value is to be added. If this parameter is not a
valid mutable CFBinaryHeap, the behavior is undefined.
@param value The value to add to the binary heap. The value is retained by
the binary heap using the retain callback provided when the binary heap
was created. If the value is not of the sort expected by the
retain callback, the behavior is undefined.
*/
CF_EXPORT void CFBinaryHeapAddValue(CFBinaryHeapRef heap, const void *value);
/*!
@function CFBinaryHeapRemoveMinimumValue
Removes the minimum value from the binary heap.
@param heap The binary heap from which the minimum value is to be removed. If this
parameter is not a valid mutable CFBinaryHeap, the behavior is undefined.
*/
CF_EXPORT void CFBinaryHeapRemoveMinimumValue(CFBinaryHeapRef heap);
/*!
@function CFBinaryHeapRemoveAllValues
Removes all the values from the binary heap, making it empty.
@param heap The binary heap from which all of the values are to be
removed. If this parameter is not a valid mutable CFBinaryHeap,
the behavior is undefined.
*/
CF_EXPORT void CFBinaryHeapRemoveAllValues(CFBinaryHeapRef heap);
CF_EXTERN_C_END
#endif /* ! __COREFOUNDATION_CFBINARYHEAP__ */