CFStorage.h

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