]>
Commit | Line | Data |
---|---|---|
1 | /* | |
2 | * Copyright (c) 2015 Apple Inc. All rights reserved. | |
3 | * | |
4 | * @APPLE_LICENSE_HEADER_START@ | |
5 | * | |
6 | * This file contains Original Code and/or Modifications of Original Code | |
7 | * as defined in and that are subject to the Apple Public Source License | |
8 | * Version 2.0 (the 'License'). You may not use this file except in | |
9 | * compliance with the License. Please obtain a copy of the License at | |
10 | * http://www.opensource.apple.com/apsl/ and read it before using this | |
11 | * file. | |
12 | * | |
13 | * The Original Code and all software distributed under the License are | |
14 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER | |
15 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, | |
16 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, | |
17 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. | |
18 | * Please see the License for the specific language governing rights and | |
19 | * limitations under the License. | |
20 | * | |
21 | * @APPLE_LICENSE_HEADER_END@ | |
22 | */ | |
23 | ||
24 | /* CFBinaryHeap.h | |
25 | Copyright (c) 1998-2014, Apple Inc. All rights reserved. | |
26 | */ | |
27 | /*! | |
28 | @header CFBinaryHeap | |
29 | CFBinaryHeap implements a container which stores values sorted using | |
30 | a binary search algorithm. CFBinaryHeaps can be useful as priority | |
31 | queues. | |
32 | */ | |
33 | ||
34 | #if !defined(__COREFOUNDATION_CFBINARYHEAP__) | |
35 | #define __COREFOUNDATION_CFBINARYHEAP__ 1 | |
36 | ||
37 | #include <CoreFoundation/CFBase.h> | |
38 | ||
39 | CF_IMPLICIT_BRIDGING_ENABLED | |
40 | CF_EXTERN_C_BEGIN | |
41 | ||
42 | typedef struct { | |
43 | CFIndex version; | |
44 | void * info; | |
45 | const void *(*retain)(const void *info); | |
46 | void (*release)(const void *info); | |
47 | CFStringRef (*copyDescription)(const void *info); | |
48 | } CFBinaryHeapCompareContext; | |
49 | ||
50 | /*! | |
51 | @typedef CFBinaryHeapCallBacks | |
52 | Structure containing the callbacks for values of a CFBinaryHeap. | |
53 | @field version The version number of the structure type being passed | |
54 | in as a parameter to the CFBinaryHeap creation functions. | |
55 | This structure is version 0. | |
56 | @field retain The callback used to add a retain for the binary heap | |
57 | on values as they are put into the binary heap. | |
58 | This callback returns the value to use as the value in the | |
59 | binary heap, which is usually the value parameter passed to | |
60 | this callback, but may be a different value if a different | |
61 | value should be added to the binary heap. The binary heap's | |
62 | allocator is passed as the first argument. | |
63 | @field release The callback used to remove a retain previously added | |
64 | for the binary heap from values as they are removed from | |
65 | the binary heap. The binary heap's allocator is passed as the | |
66 | first argument. | |
67 | @field copyDescription The callback used to create a descriptive | |
68 | string representation of each value in the binary heap. This | |
69 | is used by the CFCopyDescription() function. | |
70 | @field compare The callback used to compare values in the binary heap for | |
71 | equality in some operations. | |
72 | */ | |
73 | typedef struct { | |
74 | CFIndex version; | |
75 | const void *(*retain)(CFAllocatorRef allocator, const void *ptr); | |
76 | void (*release)(CFAllocatorRef allocator, const void *ptr); | |
77 | CFStringRef (*copyDescription)(const void *ptr); | |
78 | CFComparisonResult (*compare)(const void *ptr1, const void *ptr2, void *context); | |
79 | } CFBinaryHeapCallBacks; | |
80 | ||
81 | /*! | |
82 | @constant kCFStringBinaryHeapCallBacks | |
83 | Predefined CFBinaryHeapCallBacks structure containing a set | |
84 | of callbacks appropriate for use when the values in a CFBinaryHeap | |
85 | are all CFString types. | |
86 | */ | |
87 | CF_EXPORT const CFBinaryHeapCallBacks kCFStringBinaryHeapCallBacks; | |
88 | ||
89 | /*! | |
90 | @typedef CFBinaryHeapApplierFunction | |
91 | Type of the callback function used by the apply functions of | |
92 | CFBinaryHeap. | |
93 | @param value The current value from the binary heap. | |
94 | @param context The user-defined context parameter given to the apply | |
95 | function. | |
96 | */ | |
97 | typedef void (*CFBinaryHeapApplierFunction)(const void *val, void *context); | |
98 | ||
99 | /*! | |
100 | @typedef CFBinaryHeapRef | |
101 | This is the type of a reference to CFBinaryHeaps. | |
102 | */ | |
103 | typedef struct __CFBinaryHeap * CFBinaryHeapRef; | |
104 | ||
105 | /*! | |
106 | @function CFBinaryHeapGetTypeID | |
107 | Returns the type identifier of all CFBinaryHeap instances. | |
108 | */ | |
109 | CF_EXPORT CFTypeID CFBinaryHeapGetTypeID(void); | |
110 | ||
111 | /*! | |
112 | @function CFBinaryHeapCreate | |
113 | Creates a new mutable binary heap with the given values. | |
114 | @param allocator The CFAllocator which should be used to allocate | |
115 | memory for the binary heap and its storage for values. This | |
116 | parameter may be NULL in which case the current default | |
117 | CFAllocator is used. If this reference is not a valid | |
118 | CFAllocator, the behavior is undefined. | |
119 | @param capacity A hint about the number of values that will be held | |
120 | by the CFBinaryHeap. Pass 0 for no hint. The implementation may | |
121 | ignore this hint, or may use it to optimize various | |
122 | operations. A heap's actual capacity is only limited by | |
123 | address space and available memory constraints). If this | |
124 | parameter is negative, the behavior is undefined. | |
125 | @param callBacks A pointer to a CFBinaryHeapCallBacks structure | |
126 | initialized with the callbacks for the binary heap to use on | |
127 | each value in the binary heap. A copy of the contents of the | |
128 | callbacks structure is made, so that a pointer to a structure | |
129 | on the stack can be passed in, or can be reused for multiple | |
130 | binary heap creations. If the version field of this callbacks | |
131 | structure is not one of the defined ones for CFBinaryHeap, the | |
132 | behavior is undefined. The retain field may be NULL, in which | |
133 | case the CFBinaryHeap will do nothing to add a retain to values | |
134 | as they are put into the binary heap. The release field may be | |
135 | NULL, in which case the CFBinaryHeap will do nothing to remove | |
136 | the binary heap's retain (if any) on the values when the | |
137 | heap is destroyed or a key-value pair is removed. If the | |
138 | copyDescription field is NULL, the binary heap will create a | |
139 | simple description for a value. If the equal field is NULL, the | |
140 | binary heap will use pointer equality to test for equality of | |
141 | values. This callbacks parameter itself may be NULL, which is | |
142 | treated as if a valid structure of version 0 with all fields | |
143 | NULL had been passed in. Otherwise, | |
144 | if any of the fields are not valid pointers to functions | |
145 | of the correct type, or this parameter is not a valid | |
146 | pointer to a CFBinaryHeapCallBacks callbacks structure, | |
147 | the behavior is undefined. If any of the values put into the | |
148 | binary heap is not one understood by one of the callback functions | |
149 | the behavior when that callback function is used is undefined. | |
150 | @param compareContext A pointer to a CFBinaryHeapCompareContext structure. | |
151 | @result A reference to the new CFBinaryHeap. | |
152 | */ | |
153 | CF_EXPORT CFBinaryHeapRef CFBinaryHeapCreate(CFAllocatorRef allocator, CFIndex capacity, const CFBinaryHeapCallBacks *callBacks, const CFBinaryHeapCompareContext *compareContext); | |
154 | ||
155 | /*! | |
156 | @function CFBinaryHeapCreateCopy | |
157 | Creates a new mutable binary heap with the values from the given binary heap. | |
158 | @param allocator The CFAllocator which should be used to allocate | |
159 | memory for the binary heap and its storage for values. This | |
160 | parameter may be NULL in which case the current default | |
161 | CFAllocator is used. If this reference is not a valid | |
162 | CFAllocator, the behavior is undefined. | |
163 | @param capacity A hint about the number of values that will be held | |
164 | by the CFBinaryHeap. Pass 0 for no hint. The implementation may | |
165 | ignore this hint, or may use it to optimize various | |
166 | operations. A heap's actual capacity is only limited by | |
167 | address space and available memory constraints). | |
168 | This parameter must be greater than or equal | |
169 | to the count of the heap which is to be copied, or the | |
170 | behavior is undefined. If this parameter is negative, the | |
171 | behavior is undefined. | |
172 | @param heap The binary heap which is to be copied. The values from the | |
173 | binary heap are copied as pointers into the new binary heap (that is, | |
174 | the values themselves are copied, not that which the values | |
175 | point to, if anything). However, the values are also | |
176 | retained by the new binary heap. The count of the new binary will | |
177 | be the same as the given binary heap. The new binary heap uses the same | |
178 | callbacks as the binary heap to be copied. If this parameter is | |
179 | not a valid CFBinaryHeap, the behavior is undefined. | |
180 | @result A reference to the new mutable binary heap. | |
181 | */ | |
182 | CF_EXPORT CFBinaryHeapRef CFBinaryHeapCreateCopy(CFAllocatorRef allocator, CFIndex capacity, CFBinaryHeapRef heap); | |
183 | ||
184 | /*! | |
185 | @function CFBinaryHeapGetCount | |
186 | Returns the number of values currently in the binary heap. | |
187 | @param heap The binary heap to be queried. If this parameter is not a valid | |
188 | CFBinaryHeap, the behavior is undefined. | |
189 | @result The number of values in the binary heap. | |
190 | */ | |
191 | CF_EXPORT CFIndex CFBinaryHeapGetCount(CFBinaryHeapRef heap); | |
192 | ||
193 | /*! | |
194 | @function CFBinaryHeapGetCountOfValue | |
195 | Counts the number of times the given value occurs in the binary heap. | |
196 | @param heap The binary heap to be searched. If this parameter is not a | |
197 | valid CFBinaryHeap, the behavior is undefined. | |
198 | @param value The value for which to find matches in the binary heap. The | |
199 | compare() callback provided when the binary heap was created is | |
200 | used to compare. If the compare() callback was NULL, pointer | |
201 | equality (in C, ==) is used. If value, or any of the values | |
202 | in the binary heap, are not understood by the compare() callback, | |
203 | the behavior is undefined. | |
204 | @result The number of times the given value occurs in the binary heap. | |
205 | */ | |
206 | CF_EXPORT CFIndex CFBinaryHeapGetCountOfValue(CFBinaryHeapRef heap, const void *value); | |
207 | ||
208 | /*! | |
209 | @function CFBinaryHeapContainsValue | |
210 | Reports whether or not the value is in the binary heap. | |
211 | @param heap The binary heap to be searched. If this parameter is not a | |
212 | valid CFBinaryHeap, the behavior is undefined. | |
213 | @param value The value for which to find matches in the binary heap. The | |
214 | compare() callback provided when the binary heap was created is | |
215 | used to compare. If the compare() callback was NULL, pointer | |
216 | equality (in C, ==) is used. If value, or any of the values | |
217 | in the binary heap, are not understood by the compare() callback, | |
218 | the behavior is undefined. | |
219 | @result true, if the value is in the specified binary heap, otherwise false. | |
220 | */ | |
221 | CF_EXPORT Boolean CFBinaryHeapContainsValue(CFBinaryHeapRef heap, const void *value); | |
222 | ||
223 | /*! | |
224 | @function CFBinaryHeapGetMinimum | |
225 | Returns the minimum value is in the binary heap. If the heap contains several equal | |
226 | minimum values, any one may be returned. | |
227 | @param heap The binary heap to be searched. If this parameter is not a | |
228 | valid CFBinaryHeap, the behavior is undefined. | |
229 | @result A reference to the minimum value in the binary heap, or NULL if the | |
230 | binary heap contains no values. | |
231 | */ | |
232 | CF_EXPORT const void * CFBinaryHeapGetMinimum(CFBinaryHeapRef heap); | |
233 | ||
234 | /*! | |
235 | @function CFBinaryHeapGetMinimumIfPresent | |
236 | Returns the minimum value is in the binary heap, if present. If the heap contains several equal | |
237 | minimum values, any one may be returned. | |
238 | @param heap The binary heap to be searched. If this parameter is not a | |
239 | valid CFBinaryHeap, the behavior is undefined. | |
240 | @param value A C pointer to pointer-sized storage to be filled with the minimum value in | |
241 | the binary heap. If this value is not a valid C pointer to a pointer-sized block | |
242 | of storage, the result is undefined. If the result of the function is false, the value | |
243 | stored at this address is undefined. | |
244 | @result true, if a minimum value was found in the specified binary heap, otherwise false. | |
245 | */ | |
246 | CF_EXPORT Boolean CFBinaryHeapGetMinimumIfPresent(CFBinaryHeapRef heap, const void **value); | |
247 | ||
248 | /*! | |
249 | @function CFBinaryHeapGetValues | |
250 | Fills the buffer with values from the binary heap. | |
251 | @param heap The binary heap to be queried. If this parameter is not a | |
252 | valid CFBinaryHeap, the behavior is undefined. | |
253 | @param values A C array of pointer-sized values to be filled with | |
254 | values from the binary heap. The values in the C array are ordered | |
255 | from least to greatest. If this parameter is not a valid pointer to a | |
256 | C array of at least CFBinaryHeapGetCount() pointers, the behavior is undefined. | |
257 | */ | |
258 | CF_EXPORT void CFBinaryHeapGetValues(CFBinaryHeapRef heap, const void **values); | |
259 | ||
260 | /*! | |
261 | @function CFBinaryHeapApplyFunction | |
262 | Calls a function once for each value in the binary heap. | |
263 | @param heap The binary heap to be operated upon. If this parameter is not a | |
264 | valid CFBinaryHeap, the behavior is undefined. | |
265 | @param applier The callback function to call once for each value in | |
266 | the given binary heap. If this parameter is not a | |
267 | pointer to a function of the correct prototype, the behavior | |
268 | is undefined. If there are values in the binary heap which the | |
269 | applier function does not expect or cannot properly apply | |
270 | to, the behavior is undefined. | |
271 | @param context A pointer-sized user-defined value, which is passed | |
272 | as the second parameter to the applier function, but is | |
273 | otherwise unused by this function. If the context is not | |
274 | what is expected by the applier function, the behavior is | |
275 | undefined. | |
276 | */ | |
277 | CF_EXPORT void CFBinaryHeapApplyFunction(CFBinaryHeapRef heap, CFBinaryHeapApplierFunction applier, void *context); | |
278 | ||
279 | /*! | |
280 | @function CFBinaryHeapAddValue | |
281 | Adds the value to the binary heap. | |
282 | @param heap The binary heap to which the value is to be added. If this parameter is not a | |
283 | valid mutable CFBinaryHeap, the behavior is undefined. | |
284 | @param value The value to add to the binary heap. The value is retained by | |
285 | the binary heap using the retain callback provided when the binary heap | |
286 | was created. If the value is not of the sort expected by the | |
287 | retain callback, the behavior is undefined. | |
288 | */ | |
289 | CF_EXPORT void CFBinaryHeapAddValue(CFBinaryHeapRef heap, const void *value); | |
290 | ||
291 | /*! | |
292 | @function CFBinaryHeapRemoveMinimumValue | |
293 | Removes the minimum value from the binary heap. | |
294 | @param heap The binary heap from which the minimum value is to be removed. If this | |
295 | parameter is not a valid mutable CFBinaryHeap, the behavior is undefined. | |
296 | */ | |
297 | CF_EXPORT void CFBinaryHeapRemoveMinimumValue(CFBinaryHeapRef heap); | |
298 | ||
299 | /*! | |
300 | @function CFBinaryHeapRemoveAllValues | |
301 | Removes all the values from the binary heap, making it empty. | |
302 | @param heap The binary heap from which all of the values are to be | |
303 | removed. If this parameter is not a valid mutable CFBinaryHeap, | |
304 | the behavior is undefined. | |
305 | */ | |
306 | CF_EXPORT void CFBinaryHeapRemoveAllValues(CFBinaryHeapRef heap); | |
307 | ||
308 | CF_EXTERN_C_END | |
309 | CF_IMPLICIT_BRIDGING_DISABLED | |
310 | ||
311 | #endif /* ! __COREFOUNDATION_CFBINARYHEAP__ */ | |
312 |