[apple/cf.git] / Collections.subproj / CFStorage.h

/*
 * 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@
 */
/*	CFStorage.h
	Copyright (c) 1999-2005, Apple, Inc. All rights reserved.
*/
/*!
        @header CFStorage
CFStorage stores an array of arbitrary-sized values. There are no callbacks;
all that is provided about the values is the size, and the appropriate number
of bytes are copied in and out of the CFStorage.

CFStorage uses a balanced tree to store the values, and is most appropriate
for situations where potentially a large number values (more than a hundred
bytes' worth) will be stored and there will be a lot of editing (insertions and deletions).

Getting to an item is O(log n), although caching the last result often reduces this
to a constant time.

The overhead of CFStorage is 48 bytes. There is no per item overhead; the 
non-leaf nodes in the tree cost 20 bytes each, and the worst case extra
capacity (unused space in the leaves) is 12%, typically much less.

Because CFStorage does not necessarily use a single block of memory to store the values,
when you ask for a value, you get back the pointer to the value and optionally
the range of other values that are consecutive and thus reachable as if the
storage was a single block.
*/

#if !defined(__COREFOUNDATION_CFSTORAGE__)
#define __COREFOUNDATION_CFSTORAGE__ 1

#include <CoreFoundation/CFBase.h>

#if defined(__cplusplus)
extern "C" {
#endif

/*!
        @typedef CFStorageRef
	This is the type of a reference to a CFStorage instance.
*/
typedef struct __CFStorage *CFStorageRef;

/*!
	@typedef CFStorageApplierFunction
	Type of the callback function used by the apply functions of
		CFStorage.
	@param value The current value from the storage.
	@param context The user-defined context parameter given to the apply
		function.
*/
typedef void (*CFStorageApplierFunction)(const void *val, void *context);

/*!
        @function CFStorageGetTypeID
        Returns the type identifier of all CFStorage instances.
*/
CF_EXPORT CFTypeID CFStorageGetTypeID(void);

/*!
        @function CFStorageCreate
        Creates a new mutable storage with elements of the given size.
	@param alloc The CFAllocator which should be used to allocate
		memory for the set 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 valueSizeInBytes The size in bytes of each of the elements 
                to be stored in the storage.  If this value is zero or
                negative, the result is undefined.
	@result A reference to the new CFStorage instance.
*/
CF_EXPORT CFStorageRef CFStorageCreate(CFAllocatorRef alloc, CFIndex valueSizeInBytes);

/*!
	@function CFStorageInsertValues
	Allocates space for range.length values at location range.location.  Use
        CFStorageReplaceValues() to set those values.
	@param storage The storage to which the values are to be inserted.
                If this parameter is not a valid CFStorage, the behavior is undefined.
	@param range The range of values within the storage to delete. If the
		range location or end point (defined by the location plus
		length minus 1) are outside the index space of the storage (0
		to N inclusive, where N is the count of the storage), the
		behavior is undefined. If the range length is negative, the
		behavior is undefined. The range may be empty (length 0),
		in which case the no values are inserted.
*/
CF_EXPORT void CFStorageInsertValues(CFStorageRef storage, CFRange range);

/*!
	@function CFStorageDeleteValues
	Deletes the values of the storage in the specified range.
	@param storage The storage from which the values are to be deleted.
                If this parameter is not a valid CFStorage, the behavior is undefined.
	@param range The range of values within the storage to delete. If the
		range location or end point (defined by the location plus
		length minus 1) are outside the index space of the storage (0
		to N inclusive, where N is the count of the storage), the
		behavior is undefined. If the range length is negative, the
		behavior is undefined. The range may be empty (length 0),
		in which case the no values are deleted.
*/
CF_EXPORT void CFStorageDeleteValues(CFStorageRef storage, CFRange range);

/*!
	@function CFStorageGetCount
	Returns the number of values currently in the storage.
	@param storage The storage to be queried. If this parameter is not a valid
		CFStorage, the behavior is undefined.
	@result The number of values in the storage.
*/
CF_EXPORT CFIndex CFStorageGetCount(CFStorageRef storage);

/*!
        @function CFStorageGetValueAtIndex
        Returns a pointer to the specified value.  The pointer is mutable and may be used to
        get or set the value.
	@param storage The storage to be queried. If this parameter is not a
		valid CFStorage, the behavior is undefined.
	@param idx The index of the value to retrieve. If the index is
		outside the index space of the storage (0 to N-1 inclusive,
		where N is the count of the storage), the behavior is
		undefined.
        @param validConsecutiveValueRange This parameter is a C pointer to a CFRange.
                If NULL is specified, this argument is ignored; otherwise, the range
                is set to the range of values that may be accessed via an offset from the result pointer.
                The range location is set to the index of the lowest consecutive
                value and the range length is set to the count of consecutive values.
	@result The value with the given index in the storage.
*/
CF_EXPORT void *CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange *validConsecutiveValueRange);

/*!
        @function CFStorageGetValues
	Fills the buffer with values from the storage.
	@param storage The storage to be queried. If this parameter is not a
		valid CFStorage, the behavior is undefined.
	@param range The range of values within the storage to retrieve. If
		the range location or end point (defined by the location
		plus length minus 1) are outside the index space of the
		storage (0 to N-1 inclusive, where N is the count of the
		storage), the behavior is undefined. If the range length is
		negative, the behavior is undefined. The range may be empty
		(length 0), in which case no values are put into the buffer.
	@param values A C array of to be filled with values from the storage. 
                The values in the C array are ordered
		in the same order in which they appear in the storage. If this
		parameter is not a valid pointer to a C array of at least
		range.length pointers, the behavior is undefined.
*/
CF_EXPORT void CFStorageGetValues(CFStorageRef storage, CFRange range, void *values);

/*!
	@function CFStorageApplyFunction
	Calls a function once for each value in the set.
	@param storage The storage to be operated upon. If this parameter is not
		a valid CFStorage, the behavior is undefined.
	@param range The range of values within the storage to operate on. If the
		range location or end point (defined by the location plus
		length minus 1) are outside the index space of the storage (0
		to N inclusive, where N is the count of the storage), the
		behavior is undefined. If the range length is negative, the
		behavior is undefined. The range may be empty (length 0),
		in which case the no values are operated on.
	@param applier The callback function to call once for each value in
		the given storage. If this parameter is not a
		pointer to a function of the correct prototype, the behavior
		is undefined. If there are values in the storage 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 CFStorageApplyFunction(CFStorageRef storage, CFRange range, CFStorageApplierFunction applier, void *context);

/*!
        @function CFStorageReplaceValues
	Replaces a range of values in the storage.
	@param storage The storage from which the specified values are to be
		removed. If this parameter is not a valid CFStorage,
		the behavior is undefined.
	@param range The range of values within the storage to replace. If the
		range location or end point (defined by the location plus
		length minus 1) are outside the index space of the storage (0
		to N inclusive, where N is the count of the storage), the
		behavior is undefined. If the range length is negative, the
		behavior is undefined. The range may be empty (length 0),
		in which case the new values are merely inserted at the
		range location.
	@param values A C array of the values to be copied into the storage. 
                The new values in the storage are ordered in the same order 
                in which they appear in this C array. This parameter may be NULL 
                if the range length is 0.  This C array is not changed or freed by
                this function. If this parameter is not a valid pointer to a C array of at least
		range length pointers, the behavior is undefined.
*/
CF_EXPORT void CFStorageReplaceValues(CFStorageRef storage, CFRange range, const void *values);

/* Private stuff...
*/
CF_EXPORT CFIndex __CFStorageGetCapacity(CFStorageRef storage);
CF_EXPORT CFIndex __CFStorageGetValueSize(CFStorageRef storage);


#if defined(__cplusplus)
}
#endif

#endif /* ! __COREFOUNDATION_CFSTORAGE__ */
Commit	Line	Data
9ce05555	1	/*
d8925383	2	* Copyright (c) 2005 Apple Computer, Inc. All rights reserved.
9ce05555 A	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
9ce05555 A	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	/* CFStorage.h
d8925383	24	Copyright (c) 1999-2005, Apple, Inc. All rights reserved.
9ce05555 A	25	*/
	26	/*!
	27	@header CFStorage
	28	CFStorage stores an array of arbitrary-sized values. There are no callbacks;
	29	all that is provided about the values is the size, and the appropriate number
	30	of bytes are copied in and out of the CFStorage.
	31
	32	CFStorage uses a balanced tree to store the values, and is most appropriate
	33	for situations where potentially a large number values (more than a hundred
	34	bytes' worth) will be stored and there will be a lot of editing (insertions and deletions).
	35
	36	Getting to an item is O(log n), although caching the last result often reduces this
	37	to a constant time.
	38
	39	The overhead of CFStorage is 48 bytes. There is no per item overhead; the
	40	non-leaf nodes in the tree cost 20 bytes each, and the worst case extra
	41	capacity (unused space in the leaves) is 12%, typically much less.
	42
	43	Because CFStorage does not necessarily use a single block of memory to store the values,
	44	when you ask for a value, you get back the pointer to the value and optionally
	45	the range of other values that are consecutive and thus reachable as if the
	46	storage was a single block.
	47	*/
	48
	49	#if !defined(__COREFOUNDATION_CFSTORAGE__)
	50	#define __COREFOUNDATION_CFSTORAGE__ 1
	51
	52	#include <CoreFoundation/CFBase.h>
	53
	54	#if defined(__cplusplus)
	55	extern "C" {
	56	#endif
	57
	58	/*!
	59	@typedef CFStorageRef
	60	This is the type of a reference to a CFStorage instance.
	61	*/
	62	typedef struct __CFStorage *CFStorageRef;
	63
	64	/*!
	65	@typedef CFStorageApplierFunction
	66	Type of the callback function used by the apply functions of
	67	CFStorage.
	68	@param value The current value from the storage.
	69	@param context The user-defined context parameter given to the apply
	70	function.
	71	*/
	72	typedef void (CFStorageApplierFunction)(const void val, void *context);
	73
	74	/*!
	75	@function CFStorageGetTypeID
	76	Returns the type identifier of all CFStorage instances.
	77	*/
	78	CF_EXPORT CFTypeID CFStorageGetTypeID(void);
	79
	80	/*!
	81	@function CFStorageCreate
	82	Creates a new mutable storage with elements of the given size.
	83	@param alloc The CFAllocator which should be used to allocate
	84	memory for the set and its storage for values. This
	85	parameter may be NULL in which case the current default
	86	CFAllocator is used. If this reference is not a valid
	87	CFAllocator, the behavior is undefined.
	88	@param valueSizeInBytes The size in bytes of each of the elements
89	to be stored in the storage. If this value is zero or
90	negative, the result is undefined.
91	@result A reference to the new CFStorage instance.
92	*/
93	CF_EXPORT CFStorageRef CFStorageCreate(CFAllocatorRef alloc, CFIndex valueSizeInBytes);
94
95	/*!
96	@function CFStorageInsertValues
97	Allocates space for range.length values at location range.location. Use
98	CFStorageReplaceValues() to set those values.
99	@param storage The storage to which the values are to be inserted.
100	If this parameter is not a valid CFStorage, the behavior is undefined.
101	@param range The range of values within the storage to delete. If the
102	range location or end point (defined by the location plus
103	length minus 1) are outside the index space of the storage (0
104	to N inclusive, where N is the count of the storage), the
105	behavior is undefined. If the range length is negative, the
106	behavior is undefined. The range may be empty (length 0),
107	in which case the no values are inserted.
108	*/
109	CF_EXPORT void CFStorageInsertValues(CFStorageRef storage, CFRange range);
110
111	/*!
112	@function CFStorageDeleteValues
113	Deletes the values of the storage in the specified range.
114	@param storage The storage from which the values are to be deleted.
115	If this parameter is not a valid CFStorage, the behavior is undefined.
116	@param range The range of values within the storage to delete. If the
117	range location or end point (defined by the location plus
118	length minus 1) are outside the index space of the storage (0
119	to N inclusive, where N is the count of the storage), the
120	behavior is undefined. If the range length is negative, the
121	behavior is undefined. The range may be empty (length 0),
122	in which case the no values are deleted.
123	*/
124	CF_EXPORT void CFStorageDeleteValues(CFStorageRef storage, CFRange range);
125
126	/*!
127	@function CFStorageGetCount
128	Returns the number of values currently in the storage.
129	@param storage The storage to be queried. If this parameter is not a valid
130	CFStorage, the behavior is undefined.
131	@result The number of values in the storage.
132	*/
133	CF_EXPORT CFIndex CFStorageGetCount(CFStorageRef storage);
134
135	/*!
136	@function CFStorageGetValueAtIndex
137	Returns a pointer to the specified value. The pointer is mutable and may be used to
138	get or set the value.
139	@param storage The storage to be queried. If this parameter is not a
140	valid CFStorage, the behavior is undefined.
141	@param idx The index of the value to retrieve. If the index is
142	outside the index space of the storage (0 to N-1 inclusive,
143	where N is the count of the storage), the behavior is
144	undefined.
145	@param validConsecutiveValueRange This parameter is a C pointer to a CFRange.
146	If NULL is specified, this argument is ignored; otherwise, the range
147	is set to the range of values that may be accessed via an offset from the result pointer.
148	The range location is set to the index of the lowest consecutive
149	value and the range length is set to the count of consecutive values.
150	@result The value with the given index in the storage.
151	*/
152	CF_EXPORT void CFStorageGetValueAtIndex(CFStorageRef storage, CFIndex idx, CFRange validConsecutiveValueRange);
153
154	/*!
155	@function CFStorageGetValues
156	Fills the buffer with values from the storage.
157	@param storage The storage to be queried. If this parameter is not a
158	valid CFStorage, the behavior is undefined.
159	@param range The range of values within the storage to retrieve. If
160	the range location or end point (defined by the location
161	plus length minus 1) are outside the index space of the
162	storage (0 to N-1 inclusive, where N is the count of the
163	storage), the behavior is undefined. If the range length is
164	negative, the behavior is undefined. The range may be empty
165	(length 0), in which case no values are put into the buffer.
166	@param values A C array of to be filled with values from the storage.
167	The values in the C array are ordered
168	in the same order in which they appear in the storage. If this
169	parameter is not a valid pointer to a C array of at least
170	range.length pointers, the behavior is undefined.
171	*/
172	CF_EXPORT void CFStorageGetValues(CFStorageRef storage, CFRange range, void *values);
173
174	/*!
175	@function CFStorageApplyFunction
176	Calls a function once for each value in the set.
177	@param storage The storage to be operated upon. If this parameter is not
178	a valid CFStorage, the behavior is undefined.
179	@param range The range of values within the storage to operate on. If the
180	range location or end point (defined by the location plus
181	length minus 1) are outside the index space of the storage (0
182	to N inclusive, where N is the count of the storage), the
183	behavior is undefined. If the range length is negative, the
184	behavior is undefined. The range may be empty (length 0),
185	in which case the no values are operated on.
186	@param applier The callback function to call once for each value in
187	the given storage. If this parameter is not a
188	pointer to a function of the correct prototype, the behavior
189	is undefined. If there are values in the storage which the
190	applier function does not expect or cannot properly apply
191	to, the behavior is undefined.
192	@param context A pointer-sized user-defined value, which is passed
193	as the second parameter to the applier function, but is
194	otherwise unused by this function. If the context is not
195	what is expected by the applier function, the behavior is
196	undefined.
197	*/
198	CF_EXPORT void CFStorageApplyFunction(CFStorageRef storage, CFRange range, CFStorageApplierFunction applier, void *context);
199
200	/*!
201	@function CFStorageReplaceValues
202	Replaces a range of values in the storage.
203	@param storage The storage from which the specified values are to be
204	removed. If this parameter is not a valid CFStorage,
205	the behavior is undefined.
206	@param range The range of values within the storage to replace. If the
207	range location or end point (defined by the location plus
208	length minus 1) are outside the index space of the storage (0
209	to N inclusive, where N is the count of the storage), the
210	behavior is undefined. If the range length is negative, the
211	behavior is undefined. The range may be empty (length 0),
212	in which case the new values are merely inserted at the
213	range location.
214	@param values A C array of the values to be copied into the storage.
215	The new values in the storage are ordered in the same order
216	in which they appear in this C array. This parameter may be NULL
217	if the range length is 0. This C array is not changed or freed by
218	this function. If this parameter is not a valid pointer to a C array of at least
219	range length pointers, the behavior is undefined.
220	*/
221	CF_EXPORT void CFStorageReplaceValues(CFStorageRef storage, CFRange range, const void *values);
222
223	/* Private stuff...
224	*/
225	CF_EXPORT CFIndex __CFStorageGetCapacity(CFStorageRef storage);
226	CF_EXPORT CFIndex __CFStorageGetValueSize(CFStorageRef storage);
227
228
229	#if defined(__cplusplus)
230	}
231	#endif
232
233	#endif /* ! __COREFOUNDATION_CFSTORAGE__ */
234