+++ /dev/null
-/*
- * Copyright (c) 2005 Apple Computer, 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-2005, 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>
-
-#if defined(__cplusplus)
-extern "C" {
-#endif
-
-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 or fixed-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 The maximum number of values that can be contained
- by the CFBinaryHeap. The binary heap starts empty, and can grow to this
- number of values (and it can have less). If this parameter
- is 0, the binary heap's maximum capacity is unlimited (or rather,
- 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 or fixed-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 The maximum number of values that can be contained
- by the CFBinaryHeap. The binary heap starts empty, and can grow to this
- number of values (and it can have less). If this parameter
- is 0, the binary heap's maximum capacity is unlimited (or rather,
- only limited by address space and available memory
- constraints). If this parameter is negative, or less than the number of
- values in the given binary heap, 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 or fixed-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.
- If the binary heap is a fixed-capacity binary heap and it
- is full before this operation, 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);
-
-#if defined(__cplusplus)
-}
-#endif
-
-#endif /* ! __COREFOUNDATION_CFBINARYHEAP__ */
-
projects / apple / cf.git / blobdiff