nest-open-source / nest-cam / 4320010 / corefoundation / 7eab647e5e6a5940038f7c798bada8e32e5fda21 / . / CoreFoundation / CFBinaryHeap.h

/* | |

* Copyright (c) 2008-2009 Brent Fulgham <bfulgham@gmail.org>. 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) 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__ */ | |