--- /dev/null
+/*
+ * Copyright (c) 2008 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-2007, 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__ */
+
projects / apple / cf.git / blobdiff