1/* 2 * Copyright (c) 2014 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-2013, 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 39CF_IMPLICIT_BRIDGING_ENABLED 40CF_EXTERN_C_BEGIN 41 42typedef 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*/ 73typedef 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*/ 87CF_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*/ 97typedef void (*CFBinaryHeapApplierFunction)(const void *val, void *context); 98 99/*! 100 @typedef CFBinaryHeapRef 101 This is the type of a reference to CFBinaryHeaps. 102*/ 103typedef struct __CFBinaryHeap * CFBinaryHeapRef; 104 105/*! 106 @function CFBinaryHeapGetTypeID 107 Returns the type identifier of all CFBinaryHeap instances. 108*/ 109CF_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*/ 153CF_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*/ 182CF_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*/ 191CF_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*/ 206CF_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*/ 221CF_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*/ 232CF_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*/ 246CF_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*/ 258CF_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*/ 277CF_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*/ 289CF_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*/ 297CF_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*/ 306CF_EXPORT void CFBinaryHeapRemoveAllValues(CFBinaryHeapRef heap); 307 308CF_EXTERN_C_END 309CF_IMPLICIT_BRIDGING_DISABLED 310 311#endif /* ! __COREFOUNDATION_CFBINARYHEAP__ */ 312 313