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/* CFStorage.h 25 Copyright (c) 1999-2013, Apple Inc. All rights reserved. 26*/ 27/*! 28 @header CFStorage 29CFStorage stores an array of arbitrary-sized values. There are no callbacks; 30all that is provided about the values is the size, and the appropriate number 31of bytes are copied in and out of the CFStorage. 32 33CFStorage uses a balanced tree to store the values, and is most appropriate 34for situations where potentially a large number values (more than a hundred 35bytes' worth) will be stored and there will be a lot of editing (insertions and deletions). 36 37Getting to an item is O(log n), although caching the last result often reduces this 38to a constant time. 39 40The overhead of CFStorage is 48 bytes. There is no per item overhead; the 41non-leaf nodes in the tree cost 20 bytes each, and the worst case extra 42capacity (unused space in the leaves) is 12%, typically much less. 43 44Because CFStorage does not necessarily use a single block of memory to store the values, 45when you ask for a value, you get back the pointer to the value and optionally 46the range of other values that are consecutive and thus reachable as if the 47storage was a single block. 48*/ 49 50#if !defined(__COREFOUNDATION_CFSTORAGE__) 51#define __COREFOUNDATION_CFSTORAGE__ 1 52 53#include <CoreFoundation/CFBase.h> 54 55typedef CF_OPTIONS(CFOptionFlags, CFStorageEnumerationOptionFlags) { 56 kCFStorageEnumerationConcurrent = (1UL << 0) /* Allow enumeration to proceed concurrently */ 57}; 58 59CF_EXTERN_C_BEGIN 60 61/*! 62 @typedef CFStorageRef 63 This is the type of a reference to a CFStorage instance. 64*/ 65typedef struct __CFStorage *CFStorageRef; 66 67/*! 68 @typedef CFStorageApplierFunction 69 Type of the callback function used by the apply functions of 70 CFStorage. 71 @param value The current value from the storage. 72 @param context The user-defined context parameter given to the apply 73 function. 74*/ 75typedef void (*CFStorageApplierFunction)(const void *val, void *context); 76 77/*! 78 @typedef CFStorageRangeApplierBlock 79 Type of the callback block used by the apply functions of 80 CFStorage 81 @param val A pointer to a range of values, numbering range.length 82 @param range The range of values. This will always be a subrange of the range 83 passed to the apply function. Do not try to modify the contents of the vals pointer, because 84 there is no guarantee it points into the contents of the CFStorage object. 85 @param stop An "out" parameter that, if set to true from within the block, indicates that the enumeration may stop. 86 87*/ 88#if __BLOCKS__ 89typedef void (^CFStorageApplierBlock)(const void *vals, CFRange range, bool *stop); 90#endif 91 92/*! 93 @function CFStorageGetTypeID 94 Returns the type identifier of all CFStorage instances. 95*/ 96CF_EXPORT CFTypeID CFStorageGetTypeID(void); 97 98/*! 99 @function CFStorageCreate 100 Creates a new mutable storage with elements of the given size. 101 @param alloc The CFAllocator which should be used to allocate 102 memory for the set and its storage for values. This 103 parameter may be NULL in which case the current default 104 CFAllocator is used. If this reference is not a valid 105 CFAllocator, the behavior is undefined. 106 @param valueSizeInBytes The size in bytes of each of the elements 107 to be stored in the storage. If this value is zero or 108 negative, the result is undefined. 109 @result A reference to the new CFStorage instance. 110*/ 111CF_EXPORT CFStorageRef CFStorageCreate(CFAllocatorRef alloc, CFIndex valueSizeInBytes); 112 113/*! 114 @function CFStorageInsertValues 115 Allocates space for range.length values at location range.location. Use 116 CFStorageReplaceValues() to set those values. 117 @param storage The storage to which the values are to be inserted. 118 If this parameter is not a valid CFStorage, the behavior is undefined. 119 @param range The range of values within the storage to insert. The 120 range location must be at least zero and not exceed the count of the storage. 121 Values at indexes equal to or greater than the range location have their indexes 122 increased by the length of the range. Thus this creates a gap in the storage 123 equal to the length of the given range. If the range length is negative, the 124 behavior is undefined. The range may be empty (length 0), 125 in which case there is no effect. 126 127*/ 128CF_EXPORT void CFStorageInsertValues(CFStorageRef storage, CFRange range); 129 130/*! 131 @function CFStorageDeleteValues 132 Deletes the values of the storage in the specified range. 133 @param storage The storage from which the values are to be deleted. 134 If this parameter is not a valid CFStorage, the behavior is undefined. 135 @param range The range of values within the storage to delete. If the 136 range location or end point (defined by the location plus 137 length minus 1) are outside the index space of the storage (0 138 to N inclusive, where N is the count of the storage), the 139 behavior is undefined. If the range length is negative, the 140 behavior is undefined. The range may be empty (length 0), 141 in which case no values are deleted. 142*/ 143CF_EXPORT void CFStorageDeleteValues(CFStorageRef storage, CFRange range); 144 145/*! 146 @function CFStorageGetCount 147 Returns the number of values currently in the storage. 148 @param storage The storage to be queried. If this parameter is not a valid 149 CFStorage, the behavior is undefined. 150 @result The number of values in the storage. 151*/ 152CF_EXPORT CFIndex CFStorageGetCount(CFStorageRef storage); 153 154/*! 155 @function CFStorageGetValueAtIndex 156 Returns a pointer to the specified value. The pointer is mutable and may be used to 157 get or set the value. This is considered to be a mutating function, and so calling this 158 while accessing the CFStorage from another thread is undefined behavior, 159 even if you do not set a value. To access the CFStorage in a non-mutating 160 manner, use the more efficient CFStorageGetConstValueAtIndex(). 161 @param storage The storage to be queried. If this parameter is not a 162 valid CFStorage, the behavior is undefined. 163 @param idx The index of the value to retrieve. If the index is 164 outside the index space of the storage (0 to N-1 inclusive, 165 where N is the count of the storage), the behavior is 166 undefined. 167 @param validConsecutiveValueRange This parameter is a C pointer to a CFRange. 168 If NULL is specified, this argument is ignored; otherwise, the range 169 is set to the range of values that may be accessed via an offset from the result pointer. 170 The range location is set to the index of the lowest consecutive 171 value and the range length is set to the count of consecutive values. 172 @result The value with the given index in the storage. 173*/ 174CF_EXPORT void *CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange); 175 176/*! 177 @function CFStorageGetConstValueAtIndex 178 Returns a pointer to the specified value. The pointer is immutable and may 179 only be used to get the value. This is not considered to be a mutating function, 180 so it is safe to call this concurrently with other non-mutating functions. Furthermore, 181 this is often more efficient than CFStorageGetValueAtIndex(), so it should be used 182 in preference to that function when possible. 183 @param storage The storage to be queried. If this parameter is not a 184 valid CFStorage, the behavior is undefined. 185 @param idx The index of the value to retrieve. If the index is 186 outside the index space of the storage (0 to N-1 inclusive, 187 where N is the count of the storage), the behavior is 188 undefined. 189 @param validConsecutiveValueRange This parameter is a C pointer to a CFRange. 190 If NULL is specified, this argument is ignored; otherwise, the range 191 is set to the range of values that may be accessed via an offset from the result pointer. 192 The range location is set to the index of the lowest consecutive 193 value and the range length is set to the count of consecutive values. 194 @result The value with the given index in the storage. 195*/ 196CF_EXPORT const void *CFStorageGetConstValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange); 197 198/*! 199 @function CFStorageGetValues 200 Fills the buffer with values from the storage. 201 @param storage The storage to be queried. If this parameter is not a 202 valid CFStorage, the behavior is undefined. 203 @param range The range of values within the storage to retrieve. If 204 the range location or end point (defined by the location 205 plus length minus 1) are outside the index space of the 206 storage (0 to N-1 inclusive, where N is the count of the 207 storage), the behavior is undefined. If the range length is 208 negative, the behavior is undefined. The range may be empty 209 (length 0), in which case no values are put into the buffer. 210 @param values A C array of to be filled with values from the storage. 211 The values in the C array are ordered 212 in the same order in which they appear in the storage. If this 213 parameter is not a valid pointer to a C array of at least 214 range.length pointers, the behavior is undefined. 215*/ 216CF_EXPORT void CFStorageGetValues(CFStorageRef storage, CFRange range, void *values); 217 218/*! 219 @function CFStorageApplyFunction 220 Calls a function once for each value in the set. 221 @param storage The storage to be operated upon. If this parameter is not 222 a valid CFStorage, the behavior is undefined. 223 @param range The range of values within the storage to operate on. If the 224 range location or end point (defined by the location plus 225 length minus 1) are outside the index space of the storage (0 226 to N inclusive, where N is the count of the storage), the 227 behavior is undefined. If the range length is negative, the 228 behavior is undefined. The range may be empty (length 0), 229 in which case the no values are operated on. 230 @param applier The callback function to call once for each value in 231 the given storage. If this parameter is not a 232 pointer to a function of the correct prototype, the behavior 233 is undefined. If there are values in the storage which the 234 applier function does not expect or cannot properly apply 235 to, the behavior is undefined. 236 @param context A pointer-sized user-defined value, which is passed 237 as the second parameter to the applier function, but is 238 otherwise unused by this function. If the context is not 239 what is expected by the applier function, the behavior is 240 undefined. 241*/ 242CF_EXPORT void CFStorageApplyFunction(CFStorageRef storage, CFRange range, CFStorageApplierFunction applier, void *context); 243 244/*! 245 @function CFStorageApplyBlock 246 Enumerates ranges of stored objects with a block. 247 @param storage The storage to be operated upon. If this parameter is not 248 a valid CFStorage, the behavior is undefined. 249 @param range The range of values within the storage to operate on. If the 250 sum of the range location and length is larger than the 251 count of the storage, the behavior is undefined. If the 252 range location or length is negative, the behavior is undefined. 253 @param options Options controlling how the enumeration may proceed. 254 @param applier The callback block. The block is passed a pointer to 255 a buffer of contiguous objects in the storage, and the range of stored 256 values represented by the buffer. If the block modifies the 257 contents of the buffer, the behavior is undefined. If the block modifies 258 the contents of the CFStorage, the behavior is undefined. 259 260 */ 261#if __BLOCKS__ 262CF_EXPORT void CFStorageApplyBlock(CFStorageRef storage, CFRange range, CFStorageEnumerationOptionFlags options, CFStorageApplierBlock applier); 263#endif 264 265 266/*! 267 @function CFStorageCreateWithSubrange 268 Returns a new CFStorage that contains a portion of an existing CFStorage. 269 @param storage The storage to be operated upon. If this parameter is not 270 a valid CFStorage, the behavior is undefined. 271 @param range The range of values within the storage to operate on. If the 272 sum of the range location and length is larger than the 273 count of the storage, the behavior is undefined. If the 274 range location or length is negative, the behavior is undefined. 275 @result A reference to a new CFStorage containing a byte-for-byte copy of 276 the objects in the range. This may use copy-on-write techniques 277 to allow efficient implementation. 278 */ 279CF_EXPORT CFStorageRef CFStorageCreateWithSubrange(CFStorageRef storage, CFRange range); 280 281/*! 282 @function CFStorageReplaceValues 283 Replaces a range of values in the storage. 284 @param storage The storage from which the specified values are to be 285 removed. If this parameter is not a valid CFStorage, 286 the behavior is undefined. 287 @param range The range of values within the storage to replace. If the 288 range location or end point (defined by the location plus 289 length minus 1) are outside the index space of the storage (0 290 to N inclusive, where N is the count of the storage), the 291 behavior is undefined. If the range length is negative, the 292 behavior is undefined. The range may be empty (length 0), 293 in which case the new values are merely inserted at the 294 range location. 295 @param values A C array of the values to be copied into the storage. 296 The new values in the storage are ordered in the same order 297 in which they appear in this C array. This parameter may be NULL 298 if the range length is 0. This C array is not changed or freed by 299 this function. If this parameter is not a valid pointer to a C array of at least 300 range length pointers, the behavior is undefined. 301*/ 302CF_EXPORT void CFStorageReplaceValues(CFStorageRef storage, CFRange range, const void *values); 303 304/* Private stuff... 305*/ 306CF_EXPORT CFIndex __CFStorageGetCapacity(CFStorageRef storage); 307CF_EXPORT CFIndex __CFStorageGetValueSize(CFStorageRef storage); 308CF_EXPORT void __CFStorageSetAlwaysFrozen(CFStorageRef storage, bool alwaysFrozen); 309 310 311CF_EXTERN_C_END 312 313#endif /* ! __COREFOUNDATION_CFSTORAGE__ */ 314 315