vector.h@ 66218

Last change on this file since 66218 was 62473, checked in by vboxsync, 8 years ago
(C) 2016
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 18.2 KB

Line
1	/** @file
2	* IPRT - Vector - STL-inspired vector implementation in C.
3	*/
4
5	/*
6	* Copyright (C) 2011-2016 Oracle Corporation
7	*
8	* This file is part of VirtualBox Open Source Edition (OSE), as
9	* available from http://www.virtualbox.org. This file is free software;
10	* you can redistribute it and/or modify it under the terms of the GNU
11	* General Public License (GPL) as published by the Free Software
12	* Foundation, in version 2 as it comes in the "COPYING" file of the
13	* VirtualBox OSE distribution. VirtualBox OSE is distributed in the
14	* hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
15	*
16	* The contents of this file may alternatively be used under the terms
17	* of the Common Development and Distribution License Version 1.0
18	* (CDDL) only, as it comes in the "COPYING.CDDL" file of the
19	* VirtualBox OSE distribution, in which case the provisions of the
20	* CDDL are applicable instead of those of the GPL.
21	*
22	* You may elect to license modified versions of this file under the
23	* terms and conditions of either the GPL or the CDDL or both.
24	*/
25
26	/**
27	* @todo the right Doxygen tag here
28	* This file defines a set of macros which provide a functionality and an
29	* interface roughly similar to the C++ STL vector container. To create a
30	* vector of a particular type one must first explicitly instantiate such a
31	* vector in the source file, e.g.
32	* RTVEC_DECL(TopLevels, Window *)
33	* without a semi-colon. This macro will define a structure (struct TopLevels)
34	* which contains a dynamically resizeable array of Window * elements. It
35	* will also define a number of inline methods for manipulating the structure,
36	* such as
37	* Window TopLevelsPushBack(struct TopLevels )
38	* which adds a new element to the end of the array and returns it, optionally
39	* reallocating the array if there is not enough space for the new element.
40	* (This particular method prototype differs from the STL equivalent -
41	* push_back - more than most of the other methods).
42	*
43	* To create a vector, one simply needs to declare the structure, in this case
44	* struct TopLevels = RTVEC_INITIALIZER;
45	*
46	* There are various other macros for declaring vectors with different
47	* allocators (e.g. RTVEC_DECL_ALLOCATOR) or with clean-up functions
48	* (e.g. RTVEC_DECL_DELETE). See the descriptions of the generic methods and
49	* the declarator macros below.
50	*
51	* One particular use of vectors is to assemble an array of a particular type
52	* in heap memory without knowing - or counting - the number of elements in
53	* advance. To do this, add the elements onto the array using PushBack, then
54	* extract the array from the vector using the (non-STL) Detach method.
55	*
56	* @note functions in this file are inline to prevent warnings about
57	* unused static functions. I assume that in this day and age a
58	* compiler makes its own decisions about whether to actually
59	* inline a function.
60	* @note since vector structures must be explicitly instanciated unlike the
61	* C++ vector template, care must be taken not to instanciate a
62	* particular type twice, e.g. once in a header and once in a code file.
63	* Only using vectors in code files and keeping them out of interfaces
64	* (or passing them as anonymously) makes it easier to take care of this.
65	*/
66
67	#ifndef ___iprt_vector_h
68	#define ___iprt_vector_h
69
70	/*******************************************************************************
71	* Header Files *
72	*******************************************************************************/
73
74	#include <iprt/assert.h>
75	#include <iprt/cdefs.h>
76	#include <iprt/err.h>
77	#include <iprt/mem.h> /** @todo Should the caller include this if they need
78	* it? */
79
80
81	/**
82	* Generic vector structure
83	*/
84	/** @todo perhaps we should include an additional member for a parameter to
85	* three-argument reallocators, so that we can support e.g. mempools? */
86	#define RTVEC_DECL_STRUCT(name, type) \
87	struct name \
88	{ \
89	/** The number of elements in the vector */ \
90	size_t mcElements; \
91	/** The current capacity of the vector */ \
92	size_t mcCapacity; \
93	/** The elements themselves */ \
94	type *mpElements; \
95	};
96
97	/** Initialiser for an empty vector structure */
98	#define RTVEC_INITIALIZER { 0, 0, NULL }
99
100	/** The unit by which the vector capacity is increased */
101	#define RTVECIMPL_ALLOC_UNIT 16
102
103	/**
104	* Generic method - get the size of a vector
105	*/
106	/** @todo What is the correct way to do doxygen for this sort of macro? */
107	#define RTVEC_DECLFN_SIZE(name, type) \
108	DECLINLINE(size_t) name ## Size(struct name *pVec) \
109	{ \
110	return(pVec->mcElements); \
111	}
112
113	/**
114	* Generic method - expand a vector
115	*/
116	#define RTVEC_DECLFN_RESERVE(name, type, pfnRealloc) \
117	DECLINLINE(int) name ## Reserve(struct name *pVec, size_t cNewCapacity) \
118	{ \
119	void *pvNew; \
120	\
121	if (cNewCapacity <= pVec->mcCapacity) \
122	return VINF_SUCCESS; \
123	pvNew = pfnRealloc(pVec->mpElements, cNewCapacity * sizeof(type)); \
124	if (!pvNew) \
125	return VERR_NO_MEMORY; \
126	pVec->mcCapacity = cNewCapacity; \
127	pVec->mpElements = (type *)pvNew; \
128	return VINF_SUCCESS; \
129	}
130
131	/**
132	* Generic method - return a pointer to the first element in the vector.
133	*/
134	#define RTVEC_DECLFN_BEGIN(name, type) \
135	DECLINLINE(type ) name ## Begin(struct name pVec) \
136	{ \
137	return(pVec->mpElements); \
138	}
139
140	/**
141	* Generic method - return a pointer to one past the last element in the
142	* vector.
143	*/
144	#define RTVEC_DECLFN_END(name, type) \
145	DECLINLINE(type ) name ## End(struct name pVec) \
146	{ \
147	return(&pVec->mpElements[pVec->mcElements]); \
148	}
149
150	/**
151	* Generic method - add a new, uninitialised element onto a vector and return
152	* it.
153	* @note this method differs from the STL equivalent by letting the caller
154	* post-initialise the new element rather than copying it from its
155	* argument.
156	*/
157	#define RTVEC_DECLFN_PUSHBACK(name, type) \
158	DECLINLINE(type ) name ## PushBack(struct name pVec) \
159	{ \
160	Assert(pVec->mcElements <= pVec->mcCapacity); \
161	if ( pVec->mcElements == pVec->mcCapacity \
162	&& RT_FAILURE(name ## Reserve(pVec, pVec->mcCapacity \
163	+ RTVECIMPL_ALLOC_UNIT))) \
164	return NULL; \
165	++pVec->mcElements; \
166	return &pVec->mpElements[pVec->mcElements - 1]; \
167	}
168
169	/**
170	* Generic method - drop the last element from the vector.
171	*/
172	#define RTVEC_DECLFN_POPBACK(name) \
173	DECLINLINE(void) name ## PopBack(struct name *pVec) \
174	{ \
175	Assert(pVec->mcElements <= pVec->mcCapacity); \
176	--pVec->mcElements; \
177	}
178
179	/**
180	* Generic method - drop the last element from the vector, calling a clean-up
181	* method first.
182	*
183	* By taking an adapter function for the element to be dropped as an
184	* additional macro parameter we can support clean-up by pointer
185	* (pfnAdapter maps T* -> T) or by value (maps T -> T). pfnAdapter takes
186	* one argument of type @a type * and must return whatever type pfnDelete
187	* expects.
188	*/
189	/** @todo find a better name for pfnAdapter? */
190	#define RTVEC_DECLFN_POPBACK_DELETE(name, type, pfnDelete, pfnAdapter) \
191	DECLINLINE(void) name ## PopBack(struct name *pVec) \
192	{ \
193	Assert(pVec->mcElements <= pVec->mcCapacity); \
194	--pVec->mcElements; \
195	pfnDelete(pfnAdapter(&pVec->mpElements[pVec->mcElements])); \
196	}
197
198	/**
199	* Generic method - reset a vector to empty.
200	* @note This function does not free any memory
201	*/
202	#define RTVEC_DECLFN_CLEAR(name) \
203	DECLINLINE(void) name ## Clear(struct name *pVec) \
204	{ \
205	Assert(pVec->mcElements <= pVec->mcCapacity); \
206	pVec->mcElements = 0; \
207	}
208
209	/**
210	* Generic method - reset a vector to empty, calling a clean-up method on each
211	* element first.
212	* @note See @a RTVEC_DECLFN_POPBACK_DELETE for an explanation of pfnAdapter
213	* @note This function does not free any memory
214	* @note The cleanup function is currently called on the elements from first
215	* to last. The testcase expects this.
216	*/
217	#define RTVEC_DECLFN_CLEAR_DELETE(name, pfnDelete, pfnAdapter) \
218	DECLINLINE(void) name ## Clear(struct name *pVec) \
219	{ \
220	size_t i; \
221	\
222	Assert(pVec->mcElements <= pVec->mcCapacity); \
223	for (i = 0; i < pVec->mcElements; ++i) \
224	pfnDelete(pfnAdapter(&pVec->mpElements[i])); \
225	pVec->mcElements = 0; \
226	}
227
228	/**
229	* Generic method - detach the array contained inside a vector and reset the
230	* vector to empty.
231	* @note This function does not free any memory
232	*/
233	#define RTVEC_DECLFN_DETACH(name, type) \
234	DECLINLINE(type ) name ## Detach(struct name pVec) \
235	{ \
236	type *pArray = pVec->mpElements; \
237	\
238	Assert(pVec->mcElements <= pVec->mcCapacity); \
239	pVec->mcElements = 0; \
240	pVec->mpElements = NULL; \
241	pVec->mcCapacity = 0; \
242	return pArray; \
243	}
244
245	/** Common declarations for all vector types */
246	#define RTVEC_DECL_COMMON(name, type, pfnRealloc) \
247	RTVEC_DECL_STRUCT(name, type) \
248	RTVEC_DECLFN_SIZE(name, type) \
249	RTVEC_DECLFN_RESERVE(name, type, pfnRealloc) \
250	RTVEC_DECLFN_BEGIN(name, type) \
251	RTVEC_DECLFN_END(name, type) \
252	RTVEC_DECLFN_PUSHBACK(name, type) \
253	RTVEC_DECLFN_DETACH(name, type)
254
255	/**
256	* Declarator macro - declare a vector type
257	* @param name the name of the C struct type describing the vector as
258	* well as the prefix of the functions for manipulating it
259	* @param type the type of the objects contained in the vector
260	* @param pfnRealloc the memory reallocation function used for expanding the
261	* vector
262	*/
263	#define RTVEC_DECL_ALLOCATOR(name, type, pfnRealloc) \
264	RTVEC_DECL_COMMON(name, type, pfnRealloc) \
265	RTVEC_DECLFN_POPBACK(name) \
266	RTVEC_DECLFN_CLEAR(name)
267
268	/**
269	* Generic method - inline id mapping delete adapter function - see the
270	* explanation of pfnAdapter in @a RTVEC_DECLFN_POPBACK_DELETE.
271	*/
272	#define RTVEC_DECLFN_DELETE_ADAPTER_ID(name, type) \
273	DECLINLINE(type ) name ## DeleteAdapterId(type arg) \
274	{ \
275	return arg; \
276	}
277
278	/**
279	* Generic method - inline pointer-to-value mapping delete adapter function -
280	* see the explanation of pfnAdapter in @a RTVEC_DECLFN_POPBACK_DELETE.
281	*/
282	#define RTVEC_DECLFN_DELETE_ADAPTER_TO_VALUE(name, type) \
283	DECLINLINE(type) name ## DeleteAdapterToValue(type *arg) \
284	{ \
285	return *arg; \
286	}
287
288	/**
289	* Declarator macro - declare a vector type with a cleanup callback to be used
290	* when elements are dropped from the vector. The callback takes a pointer to
291	* @a type,
292	* NOT a value of type @a type.
293	* @param name the name of the C struct type describing the vector as
294	* well as the prefix of the functions for manipulating it
295	* @param type the type of the objects contained in the vector
296	* @param pfnRealloc the memory reallocation function used for expanding the
297	* vector
298	* @param pfnDelete the cleanup callback function - signature
299	* void pfnDelete(type *)
300	*/
301	#define RTVEC_DECL_ALLOCATOR_DELETE(name, type, pfnRealloc, pfnDelete) \
302	RTVEC_DECL_COMMON(name, type, pfnRealloc) \
303	RTVEC_DECLFN_DELETE_ADAPTER_ID(name, type) \
304	RTVEC_DECLFN_POPBACK_DELETE(name, type, pfnDelete, \
305	name ## DeleteAdapterId) \
306	RTVEC_DECLFN_CLEAR_DELETE(name, pfnDelete, name ## DeleteAdapterId)
307
308	/**
309	* Declarator macro - declare a vector type with a cleanup callback to be used
310	* when elements are dropped from the vector. The callback takes a parameter
311	* of type @a type, NOT a pointer to @a type.
312	* @param name the name of the C struct type describing the vector as
313	* well as the prefix of the functions for manipulating it
314	* @param type the type of the objects contained in the vector
315	* @param pfnRealloc the memory reallocation function used for expanding the
316	* vector
317	* @param pfnDelete the cleanup callback function - signature
318	* void pfnDelete(type)
319	*/
320	#define RTVEC_DECL_ALLOCATOR_DELETE_BY_VALUE(name, type, pfnRealloc, \
321	pfnDelete) \
322	RTVEC_DECL_COMMON(name, type, pfnRealloc) \
323	RTVEC_DECLFN_DELETE_ADAPTER_TO_VALUE(name, type) \
324	RTVEC_DECLFN_POPBACK_DELETE(name, type, pfnDelete, \
325	name ## DeleteAdapterToValue) \
326	RTVEC_DECLFN_CLEAR_DELETE(name, pfnDelete, \
327	name ## DeleteAdapterToValue)
328
329	/**
330	* Inline wrapper around RTMemRealloc macro to get a function usable as a
331	* callback.
332	*/
333	DECLINLINE(void ) rtvecReallocDefTag(void pv, size_t cbNew)
334	{
335	return RTMemRealloc(pv, cbNew);
336	}
337
338	/**
339	* Declarator macro - declare a vector type (see @a RTVEC_DECL_ALLOCATOR)
340	* using RTMemRealloc as a memory allocator
341	* @param name the name of the C struct type describing the vector as
342	* well as the prefix of the functions for manipulating it
343	* @param type the type of the objects contained in the vector
344	*/
345	#define RTVEC_DECL(name, type) \
346	RTVEC_DECL_ALLOCATOR(name, type, rtvecReallocDefTag)
347
348	/**
349	* Declarator macro - declare a vector type with a cleanup by pointer callback
350	* (see @a RTVEC_DECL_ALLOCATOR_DELETE) using RTMemRealloc as a memory
351	* allocator
352	* @param name the name of the C struct type describing the vector as
353	* well as the prefix of the functions for manipulating it
354	* @param type the type of the objects contained in the vector
355	* @param pfnDelete the cleanup callback function - signature
356	* void pfnDelete(type *)
357	*/
358	#define RTVEC_DECL_DELETE(name, type, pfnDelete) \
359	RTVEC_DECL_ALLOCATOR_DELETE(name, type, rtvecReallocDefTag, pfnDelete)
360
361	/**
362	* Declarator macro - declare a vector type with a cleanup by value callback
363	* (see @a RTVEC_DECL_ALLOCATOR_DELETE_BY_VALUE) using RTMemRealloc as a memory
364	* allocator
365	* @param name the name of the C struct type describing the vector as
366	* well as the prefix of the functions for manipulating it
367	* @param type the type of the objects contained in the vector
368	* @param pfnDelete the cleanup callback function - signature
369	* void pfnDelete(type)
370	*/
371	#define RTVEC_DECL_DELETE_BY_VALUE(name, type, pfnDelete) \
372	RTVEC_DECL_ALLOCATOR_DELETE_BY_VALUE(name, type, rtvecReallocDefTag, \
373	pfnDelete)
374
375	#endif /* !___iprt_vector_h */
376

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/include/iprt/vector.h@ 66218

Download in other formats: