vector.h@ 104212

Last change on this file since 104212 was 98103, checked in by vboxsync, 23 months ago
Copyright year updates by scm.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 18.6 KB

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

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

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

Download in other formats: