vector.h@ 76585

Last change on this file since 76585 was 76585, checked in by vboxsync, 6 years ago
*: scm --fix-header-guard-endif
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 18.3 KB

Line
1	/** @file
2	* IPRT - Vector - STL-inspired vector implementation in C.
3	*/
4
5	/*
6	* Copyright (C) 2011-2019 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_INCLUDED_vector_h
68	#define IPRT_INCLUDED_vector_h
69	#ifndef RT_WITHOUT_PRAGMA_ONCE
70	# pragma once
71	#endif
72
73	/*******************************************************************************
74	* Header Files *
75	*******************************************************************************/
76
77	#include <iprt/assert.h>
78	#include <iprt/cdefs.h>
79	#include <iprt/errcore.h>
80	#include <iprt/mem.h> /** @todo Should the caller include this if they need
81	* it? */
82
83
84	/**
85	* Generic vector structure
86	*/
87	/** @todo perhaps we should include an additional member for a parameter to
88	* three-argument reallocators, so that we can support e.g. mempools? */
89	#define RTVEC_DECL_STRUCT(name, type) \
90	struct name \
91	{ \
92	/** The number of elements in the vector */ \
93	size_t mcElements; \
94	/** The current capacity of the vector */ \
95	size_t mcCapacity; \
96	/** The elements themselves */ \
97	type *mpElements; \
98	};
99
100	/** Initialiser for an empty vector structure */
101	#define RTVEC_INITIALIZER { 0, 0, NULL }
102
103	/** The unit by which the vector capacity is increased */
104	#define RTVECIMPL_ALLOC_UNIT 16
105
106	/**
107	* Generic method - get the size of a vector
108	*/
109	/** @todo What is the correct way to do doxygen for this sort of macro? */
110	#define RTVEC_DECLFN_SIZE(name, type) \
111	DECLINLINE(size_t) name ## Size(struct name *pVec) \
112	{ \
113	return(pVec->mcElements); \
114	}
115
116	/**
117	* Generic method - expand a vector
118	*/
119	#define RTVEC_DECLFN_RESERVE(name, type, pfnRealloc) \
120	DECLINLINE(int) name ## Reserve(struct name *pVec, size_t cNewCapacity) \
121	{ \
122	void *pvNew; \
123	\
124	if (cNewCapacity <= pVec->mcCapacity) \
125	return VINF_SUCCESS; \
126	pvNew = pfnRealloc(pVec->mpElements, cNewCapacity * sizeof(type)); \
127	if (!pvNew) \
128	return VERR_NO_MEMORY; \
129	pVec->mcCapacity = cNewCapacity; \
130	pVec->mpElements = (type *)pvNew; \
131	return VINF_SUCCESS; \
132	}
133
134	/**
135	* Generic method - return a pointer to the first element in the vector.
136	*/
137	#define RTVEC_DECLFN_BEGIN(name, type) \
138	DECLINLINE(type ) name ## Begin(struct name pVec) \
139	{ \
140	return(pVec->mpElements); \
141	}
142
143	/**
144	* Generic method - return a pointer to one past the last element in the
145	* vector.
146	*/
147	#define RTVEC_DECLFN_END(name, type) \
148	DECLINLINE(type ) name ## End(struct name pVec) \
149	{ \
150	return(&pVec->mpElements[pVec->mcElements]); \
151	}
152
153	/**
154	* Generic method - add a new, uninitialised element onto a vector and return
155	* it.
156	* @note this method differs from the STL equivalent by letting the caller
157	* post-initialise the new element rather than copying it from its
158	* argument.
159	*/
160	#define RTVEC_DECLFN_PUSHBACK(name, type) \
161	DECLINLINE(type ) name ## PushBack(struct name pVec) \
162	{ \
163	Assert(pVec->mcElements <= pVec->mcCapacity); \
164	if ( pVec->mcElements == pVec->mcCapacity \
165	&& RT_FAILURE(name ## Reserve(pVec, pVec->mcCapacity \
166	+ RTVECIMPL_ALLOC_UNIT))) \
167	return NULL; \
168	++pVec->mcElements; \
169	return &pVec->mpElements[pVec->mcElements - 1]; \
170	}
171
172	/**
173	* Generic method - drop the last element from the vector.
174	*/
175	#define RTVEC_DECLFN_POPBACK(name) \
176	DECLINLINE(void) name ## PopBack(struct name *pVec) \
177	{ \
178	Assert(pVec->mcElements <= pVec->mcCapacity); \
179	--pVec->mcElements; \
180	}
181
182	/**
183	* Generic method - drop the last element from the vector, calling a clean-up
184	* method first.
185	*
186	* By taking an adapter function for the element to be dropped as an
187	* additional macro parameter we can support clean-up by pointer
188	* (pfnAdapter maps T* -> T) or by value (maps T -> T). pfnAdapter takes
189	* one argument of type @a type * and must return whatever type pfnDelete
190	* expects.
191	*/
192	/** @todo find a better name for pfnAdapter? */
193	#define RTVEC_DECLFN_POPBACK_DELETE(name, type, pfnDelete, pfnAdapter) \
194	DECLINLINE(void) name ## PopBack(struct name *pVec) \
195	{ \
196	Assert(pVec->mcElements <= pVec->mcCapacity); \
197	--pVec->mcElements; \
198	pfnDelete(pfnAdapter(&pVec->mpElements[pVec->mcElements])); \
199	}
200
201	/**
202	* Generic method - reset a vector to empty.
203	* @note This function does not free any memory
204	*/
205	#define RTVEC_DECLFN_CLEAR(name) \
206	DECLINLINE(void) name ## Clear(struct name *pVec) \
207	{ \
208	Assert(pVec->mcElements <= pVec->mcCapacity); \
209	pVec->mcElements = 0; \
210	}
211
212	/**
213	* Generic method - reset a vector to empty, calling a clean-up method on each
214	* element first.
215	* @note See @a RTVEC_DECLFN_POPBACK_DELETE for an explanation of pfnAdapter
216	* @note This function does not free any memory
217	* @note The cleanup function is currently called on the elements from first
218	* to last. The testcase expects this.
219	*/
220	#define RTVEC_DECLFN_CLEAR_DELETE(name, pfnDelete, pfnAdapter) \
221	DECLINLINE(void) name ## Clear(struct name *pVec) \
222	{ \
223	size_t i; \
224	\
225	Assert(pVec->mcElements <= pVec->mcCapacity); \
226	for (i = 0; i < pVec->mcElements; ++i) \
227	pfnDelete(pfnAdapter(&pVec->mpElements[i])); \
228	pVec->mcElements = 0; \
229	}
230
231	/**
232	* Generic method - detach the array contained inside a vector and reset the
233	* vector to empty.
234	* @note This function does not free any memory
235	*/
236	#define RTVEC_DECLFN_DETACH(name, type) \
237	DECLINLINE(type ) name ## Detach(struct name pVec) \
238	{ \
239	type *pArray = pVec->mpElements; \
240	\
241	Assert(pVec->mcElements <= pVec->mcCapacity); \
242	pVec->mcElements = 0; \
243	pVec->mpElements = NULL; \
244	pVec->mcCapacity = 0; \
245	return pArray; \
246	}
247
248	/** Common declarations for all vector types */
249	#define RTVEC_DECL_COMMON(name, type, pfnRealloc) \
250	RTVEC_DECL_STRUCT(name, type) \
251	RTVEC_DECLFN_SIZE(name, type) \
252	RTVEC_DECLFN_RESERVE(name, type, pfnRealloc) \
253	RTVEC_DECLFN_BEGIN(name, type) \
254	RTVEC_DECLFN_END(name, type) \
255	RTVEC_DECLFN_PUSHBACK(name, type) \
256	RTVEC_DECLFN_DETACH(name, type)
257
258	/**
259	* Declarator macro - declare a vector type
260	* @param name the name of the C struct type describing the vector as
261	* well as the prefix of the functions for manipulating it
262	* @param type the type of the objects contained in the vector
263	* @param pfnRealloc the memory reallocation function used for expanding the
264	* vector
265	*/
266	#define RTVEC_DECL_ALLOCATOR(name, type, pfnRealloc) \
267	RTVEC_DECL_COMMON(name, type, pfnRealloc) \
268	RTVEC_DECLFN_POPBACK(name) \
269	RTVEC_DECLFN_CLEAR(name)
270
271	/**
272	* Generic method - inline id mapping delete adapter function - see the
273	* explanation of pfnAdapter in @a RTVEC_DECLFN_POPBACK_DELETE.
274	*/
275	#define RTVEC_DECLFN_DELETE_ADAPTER_ID(name, type) \
276	DECLINLINE(type ) name ## DeleteAdapterId(type arg) \
277	{ \
278	return arg; \
279	}
280
281	/**
282	* Generic method - inline pointer-to-value mapping delete adapter function -
283	* see the explanation of pfnAdapter in @a RTVEC_DECLFN_POPBACK_DELETE.
284	*/
285	#define RTVEC_DECLFN_DELETE_ADAPTER_TO_VALUE(name, type) \
286	DECLINLINE(type) name ## DeleteAdapterToValue(type *arg) \
287	{ \
288	return *arg; \
289	}
290
291	/**
292	* Declarator macro - declare a vector type with a cleanup callback to be used
293	* when elements are dropped from the vector. The callback takes a pointer to
294	* @a type,
295	* NOT a value of type @a type.
296	* @param name the name of the C struct type describing the vector as
297	* well as the prefix of the functions for manipulating it
298	* @param type the type of the objects contained in the vector
299	* @param pfnRealloc the memory reallocation function used for expanding the
300	* vector
301	* @param pfnDelete the cleanup callback function - signature
302	* void pfnDelete(type *)
303	*/
304	#define RTVEC_DECL_ALLOCATOR_DELETE(name, type, pfnRealloc, pfnDelete) \
305	RTVEC_DECL_COMMON(name, type, pfnRealloc) \
306	RTVEC_DECLFN_DELETE_ADAPTER_ID(name, type) \
307	RTVEC_DECLFN_POPBACK_DELETE(name, type, pfnDelete, \
308	name ## DeleteAdapterId) \
309	RTVEC_DECLFN_CLEAR_DELETE(name, pfnDelete, name ## DeleteAdapterId)
310
311	/**
312	* Declarator macro - declare a vector type with a cleanup callback to be used
313	* when elements are dropped from the vector. The callback takes a parameter
314	* of type @a type, NOT a pointer to @a type.
315	* @param name the name of the C struct type describing the vector as
316	* well as the prefix of the functions for manipulating it
317	* @param type the type of the objects contained in the vector
318	* @param pfnRealloc the memory reallocation function used for expanding the
319	* vector
320	* @param pfnDelete the cleanup callback function - signature
321	* void pfnDelete(type)
322	*/
323	#define RTVEC_DECL_ALLOCATOR_DELETE_BY_VALUE(name, type, pfnRealloc, \
324	pfnDelete) \
325	RTVEC_DECL_COMMON(name, type, pfnRealloc) \
326	RTVEC_DECLFN_DELETE_ADAPTER_TO_VALUE(name, type) \
327	RTVEC_DECLFN_POPBACK_DELETE(name, type, pfnDelete, \
328	name ## DeleteAdapterToValue) \
329	RTVEC_DECLFN_CLEAR_DELETE(name, pfnDelete, \
330	name ## DeleteAdapterToValue)
331
332	/**
333	* Inline wrapper around RTMemRealloc macro to get a function usable as a
334	* callback.
335	*/
336	DECLINLINE(void ) rtvecReallocDefTag(void pv, size_t cbNew)
337	{
338	return RTMemRealloc(pv, cbNew);
339	}
340
341	/**
342	* Declarator macro - declare a vector type (see @a RTVEC_DECL_ALLOCATOR)
343	* using RTMemRealloc as a memory allocator
344	* @param name the name of the C struct type describing the vector as
345	* well as the prefix of the functions for manipulating it
346	* @param type the type of the objects contained in the vector
347	*/
348	#define RTVEC_DECL(name, type) \
349	RTVEC_DECL_ALLOCATOR(name, type, rtvecReallocDefTag)
350
351	/**
352	* Declarator macro - declare a vector type with a cleanup by pointer callback
353	* (see @a RTVEC_DECL_ALLOCATOR_DELETE) using RTMemRealloc as a memory
354	* allocator
355	* @param name the name of the C struct type describing the vector as
356	* well as the prefix of the functions for manipulating it
357	* @param type the type of the objects contained in the vector
358	* @param pfnDelete the cleanup callback function - signature
359	* void pfnDelete(type *)
360	*/
361	#define RTVEC_DECL_DELETE(name, type, pfnDelete) \
362	RTVEC_DECL_ALLOCATOR_DELETE(name, type, rtvecReallocDefTag, pfnDelete)
363
364	/**
365	* Declarator macro - declare a vector type with a cleanup by value callback
366	* (see @a RTVEC_DECL_ALLOCATOR_DELETE_BY_VALUE) using RTMemRealloc as a memory
367	* allocator
368	* @param name the name of the C struct type describing the vector as
369	* well as the prefix of the functions for manipulating it
370	* @param type the type of the objects contained in the vector
371	* @param pfnDelete the cleanup callback function - signature
372	* void pfnDelete(type)
373	*/
374	#define RTVEC_DECL_DELETE_BY_VALUE(name, type, pfnDelete) \
375	RTVEC_DECL_ALLOCATOR_DELETE_BY_VALUE(name, type, rtvecReallocDefTag, \
376	pfnDelete)
377
378	#endif /* !IPRT_INCLUDED_vector_h */
379

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

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

Download in other formats: