vector.h@ 98102

Last change on this file since 98102 was 96407, checked in by vboxsync, 2 years ago
scm copyright and license note update
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 14.0 KB

Line
1	/* $Id: vector.h 96407 2022-08-22 17:43:14Z vboxsync $ */
2	/** @file
3	* STL-inspired vector implementation in C
4	* @note functions in this file are inline to prevent warnings about
5	* unused static functions. I assume that in this day and age a
6	* compiler makes its own decisions about whether to actually
7	* inline a function.
8	* @note as this header is included in rdesktop-vrdp, we do not include other
9	* required header files here (to wit assert.h, err.h, mem.h and
10	* types.h). These must be included first. If this moves to iprt, we
11	* should write a wrapper around it doing that.
12	* @todo can we do more of the type checking at compile time somehow?
13	*/
14
15	/*
16	* Copyright (C) 2008-2022 Oracle and/or its affiliates.
17	*
18	* This file is part of VirtualBox base platform packages, as
19	* available from https://www.virtualbox.org.
20	*
21	* This program is free software; you can redistribute it and/or
22	* modify it under the terms of the GNU General Public License
23	* as published by the Free Software Foundation, in version 3 of the
24	* License.
25	*
26	* This program is distributed in the hope that it will be useful, but
27	* WITHOUT ANY WARRANTY; without even the implied warranty of
28	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
29	* General Public License for more details.
30	*
31	* You should have received a copy of the GNU General Public License
32	* along with this program; if not, see <https://www.gnu.org/licenses>.
33	*
34	* SPDX-License-Identifier: GPL-3.0-only
35	*/
36
37	#ifndef MAIN_INCLUDED_vector_h
38	#define MAIN_INCLUDED_vector_h
39	#ifndef RT_WITHOUT_PRAGMA_ONCE
40	# pragma once
41	#endif
42
43
44	/*********************************************************************************************************************************
45	* Header Files *
46	*********************************************************************************************************************************/
47	#include <stdlib.h>
48
49
50	/*********************************************************************************************************************************
51	* Helper macros and definitions *
52	*********************************************************************************************************************************/
53
54	/** The unit by which the vector capacity is increased */
55	#define VECTOR_ALLOC_UNIT 16
56
57	/** Calculate a hash of a string of tokens for sanity type checking */
58	#define VECTOR_TOKEN_HASH(token) \
59	((unsigned) \
60	( VECTOR_TOKEN_HASH4(token, 0) \
61	^ VECTOR_TOKEN_HASH4(token, 4) \
62	^ VECTOR_TOKEN_HASH4(token, 8) \
63	^ VECTOR_TOKEN_HASH4(token, 12)))
64
65	/** Helper macro for @a VECTOR_TOKEN_HASH */
66	#define VECTOR_TOKEN_HASH_VALUE(token, place, mul) \
67	(sizeof(#token) > place ? #token[place] * mul : 0)
68
69	/** Helper macro for @a VECTOR_TOKEN_HASH */
70	#define VECTOR_TOKEN_HASH4(token, place) \
71	VECTOR_TOKEN_HASH_VALUE(token, place, 0x1) \
72	^ VECTOR_TOKEN_HASH_VALUE(token, place + 1, 0x100) \
73	^ VECTOR_TOKEN_HASH_VALUE(token, place + 2, 0x10000) \
74	^ VECTOR_TOKEN_HASH_VALUE(token, place + 3, 0x1000000)
75
76	/** Generic vector structure, used by @a VECTOR_OBJ and @a VECTOR_PTR */
77	#define VECTOR_STRUCT \
78	{ \
79	/** The number of elements in the vector */ \
80	size_t mcElements; \
81	/** The current capacity of the vector */ \
82	size_t mcCapacity; \
83	/** The size of an element */ \
84	size_t mcbElement; \
85	/** Hash value of the element type */ \
86	unsigned muTypeHash; \
87	/** The elements themselves */ \
88	void *mpvaElements; \
89	/** Destructor for elements - takes a pointer to an element. */ \
90	void (mpfnCleanup)(void ); \
91	}
92
93	/* Structure definitions */
94
95	/** A vector of values or objects */
96	typedef struct VECTOR_OBJ VECTOR_STRUCT VECTOR_OBJ;
97
98	/** A vector of pointer values. (A handy special case.) */
99	typedef struct VECTOR_PTR VECTOR_STRUCT VECTOR_PTR;
100
101	/** Convenience macro for annotating the type of the vector. Unfortunately the
102	* type name is only cosmetic. */
103	/** @todo can we do something useful with the type? */
104	#define VECTOR_OBJ(type) VECTOR_OBJ
105
106	/** Convenience macro for annotating the type of the vector. Unfortunately the
107	* type name is only cosmetic. */
108	#define VECTOR_PTR(type) VECTOR_PTR
109
110	/* Private helper functions and macros */
111
112	#define VEC_GET_ELEMENT_OBJ(pvaElements, cbElement, cElement) \
113	((void )((char )(pvaElements) + (cElement) * (cbElement)))
114
115	#define VEC_GET_ELEMENT_PTR(pvaElements, cElement) \
116	((void )VEC_GET_ELEMENT_OBJ(pvaElements, sizeof(void ), cElement))
117
118	/** Default cleanup function that does nothing. */
119	DECLINLINE(void) vecNoCleanup(void *pvElement)
120	{
121	(void) pvElement;
122	}
123
124	/** Expand an existing vector, implementation */
125	DECLINLINE(int) vecExpand(size_t pcCapacity, void *ppvaElements,
126	size_t cbElement)
127	{
128	size_t cOldCap, cNewCap;
129	void *pRealloc;
130
131	cOldCap = *pcCapacity;
132	cNewCap = cOldCap + VECTOR_ALLOC_UNIT;
133	pRealloc = RTMemRealloc(ppvaElements, cNewCap cbElement);
134	if (!pRealloc)
135	return VERR_NO_MEMORY;
136	*pcCapacity = cNewCap;
137	*ppvaElements = pRealloc;
138	return VINF_SUCCESS;
139	}
140
141	/** Expand an existing vector */
142	#define VEC_EXPAND(pvec) vecExpand(&(pvec)->mcCapacity, &(pvec)->mpvaElements, \
143	(pvec)->mcbElement)
144
145	/** Reset a vector, cleaning up all its elements. */
146	DECLINLINE(void) vecClearObj(VECTOR_OBJ *pvec)
147	{
148	unsigned i;
149
150	for (i = 0; i < pvec->mcElements; ++i)
151	pvec->mpfnCleanup(VEC_GET_ELEMENT_OBJ(pvec->mpvaElements,
152	pvec->mcbElement, i));
153	pvec->mcElements = 0;
154	}
155
156	/** Reset a pointer vector, cleaning up all its elements. */
157	DECLINLINE(void) vecClearPtr(VECTOR_PTR *pvec)
158	{
159	unsigned i;
160
161	for (i = 0; i < pvec->mcElements; ++i)
162	pvec->mpfnCleanup(VEC_GET_ELEMENT_PTR(pvec->mpvaElements, i));
163	pvec->mcElements = 0;
164	}
165
166	/** Clean up a vector */
167	DECLINLINE(void) vecCleanupObj(VECTOR_OBJ *pvec)
168	{
169	vecClearObj(pvec);
170	RTMemFree(pvec->mpvaElements);
171	pvec->mpvaElements = NULL;
172	}
173
174	/** Clean up a pointer vector */
175	DECLINLINE(void) vecCleanupPtr(VECTOR_PTR *pvec)
176	{
177	vecClearPtr(pvec);
178	RTMemFree(pvec->mpvaElements);
179	pvec->mpvaElements = NULL;
180	}
181
182	/** Initialise a vector structure, implementation */
183	#define VEC_INIT(pvec, cbElement, uTypeHash, pfnCleanup) \
184	pvec->mcElements = pvec->mcCapacity = 0; \
185	pvec->mcbElement = cbElement; \
186	pvec->muTypeHash = uTypeHash; \
187	pvec->mpfnCleanup = pfnCleanup ? pfnCleanup : vecNoCleanup; \
188	pvec->mpvaElements = NULL;
189
190	/** Initialise a vector. */
191	DECLINLINE(void) vecInitObj(VECTOR_OBJ *pvec, size_t cbElement,
192	unsigned uTypeHash, void (pfnCleanup)(void ))
193	{
194	VEC_INIT(pvec, cbElement, uTypeHash, pfnCleanup)
195	}
196
197	/** Initialise a pointer vector. */
198	DECLINLINE(void) vecInitPtr(VECTOR_PTR *pvec, size_t cbElement,
199	unsigned uTypeHash, void (pfnCleanup)(void ))
200	{
201	VEC_INIT(pvec, cbElement, uTypeHash, pfnCleanup)
202	}
203
204	/** Add an element onto the end of a vector */
205	DECLINLINE(int) vecPushBackObj(VECTOR_OBJ *pvec, unsigned uTypeHash,
206	void *pvElement)
207	{
208	int rc2;
209	AssertReturn(pvec->muTypeHash == uTypeHash, VERR_INVALID_PARAMETER);
210	if ( pvec->mcElements == pvec->mcCapacity
211	&& RT_FAILURE((rc2 = VEC_EXPAND(pvec))))
212	return rc2;
213	memcpy(VEC_GET_ELEMENT_OBJ(pvec->mpvaElements, pvec->mcbElement,
214	pvec->mcElements), pvElement, pvec->mcbElement);
215	++pvec->mcElements;
216	return VINF_SUCCESS;
217	}
218
219	/** Add a pointer onto the end of a pointer vector */
220	DECLINLINE(int) vecPushBackPtr(VECTOR_PTR *pvec, unsigned uTypeHash,
221	void *pv)
222	{
223	int rc2;
224	AssertReturn(pvec->muTypeHash == uTypeHash, VERR_INVALID_PARAMETER);
225	if ( pvec->mcElements == pvec->mcCapacity
226	&& RT_FAILURE((rc2 = VEC_EXPAND(pvec))))
227	return rc2;
228	VEC_GET_ELEMENT_PTR(pvec->mpvaElements, pvec->mcElements) = pv;
229	++pvec->mcElements;
230	return VINF_SUCCESS;
231	}
232
233
234	/*********************************************************************************************************************************
235	* Public interface macros *
236	*********************************************************************************************************************************/
237
238	/**
239	* Initialise a vector structure. Always succeeds.
240	* @param pvec pointer to an uninitialised vector structure
241	* @param type the type of the objects in the vector. As this is
242	* hashed by the preprocessor use of space etc is
243	* important.
244	* @param pfnCleanup cleanup function (void (pfn)(void )) that is called
245	* on a pointer to a vector element when that element is
246	* dropped
247	*/
248	#define VEC_INIT_OBJ(pvec, type, pfnCleanup) \
249	vecInitObj(pvec, sizeof(type), VECTOR_TOKEN_HASH(type), \
250	(void ()(void)) pfnCleanup)
251
252	/**
253	* Initialise a vector-of-pointers structure. Always succeeds.
254	* @param pvec pointer to an uninitialised vector structure
255	* @param type the type of the pointers in the vector, including the
256	* final "*". As this is hashed by the preprocessor use
257	* of space etc is important.
258	* @param pfnCleanup cleanup function (void (pfn)(void )) that is called
259	* directly on a vector element when that element is
260	* dropped
261	*/
262	#define VEC_INIT_PTR(pvec, type, pfnCleanup) \
263	vecInitPtr(pvec, sizeof(type), VECTOR_TOKEN_HASH(type), \
264	(void ()(void)) pfnCleanup)
265
266	/**
267	* Clean up a vector.
268	* @param pvec pointer to the vector to clean up. The clean up function
269	* specified at initialisation (if any) is called for each element
270	* in the vector. After clean up, the vector structure is invalid
271	* until it is re-initialised
272	*/
273	#define VEC_CLEANUP_OBJ vecCleanupObj
274
275	/**
276	* Clean up a vector-of-pointers.
277	* @param pvec pointer to the vector to clean up. The clean up function
278	* specified at initialisation (if any) is called for each element
279	* in the vector. After clean up, the vector structure is invalid
280	* until it is re-initialised
281	*/
282	#define VEC_CLEANUP_PTR vecCleanupPtr
283
284	/**
285	* Reinitialises a vector structure to empty.
286	* @param pvec pointer to the vector to re-initialise. The clean up function
287	* specified at initialisation (if any) is called for each element
288	* in the vector.
289	*/
290	#define VEC_CLEAR_OBJ vecClearObj
291
292	/**
293	* Reinitialises a vector-of-pointers structure to empty.
294	* @param pvec pointer to the vector to re-initialise. The clean up function
295	* specified at initialisation (if any) is called for each element
296	* in the vector.
297	*/
298	#define VEC_CLEAR_PTR vecClearPtr
299
300	/**
301	* Adds an element to the back of a vector. The element will be byte-copied
302	* and become owned by the vector, to be cleaned up by the vector's clean-up
303	* routine when the element is dropped.
304	* @returns iprt status code (VINF_SUCCESS or VERR_NO_MEMORY)
305	* @returns VERR_INVALID_PARAMETER if the type does not match the type given
306	* when the vector was initialised (asserted)
307	* @param pvec pointer to the vector on to which the element should be
308	* added
309	* @param type the type of the vector as specified at initialisation.
310	* Spacing etc is important.
311	* @param pvElement void pointer to the element to be added
312	*/
313	#define VEC_PUSH_BACK_OBJ(pvec, type, pvElement) \
314	vecPushBackObj(pvec, VECTOR_TOKEN_HASH(type), \
315	(pvElement) + ((pvElement) - (type *)(pvElement)))
316
317	/**
318	* Adds a pointer to the back of a vector-of-pointers. The pointer will become
319	* owned by the vector, to be cleaned up by the vector's clean-up routine when
320	* it is dropped.
321	* @returns iprt status code (VINF_SUCCESS or VERR_NO_MEMORY)
322	* @returns VERR_INVALID_PARAMETER if the type does not match the type given
323	* when the vector was initialised (asserted)
324	* @param pvec pointer to the vector on to which the element should be
325	* added
326	* @param type the type of the vector as specified at initialisation.
327	* Spacing etc is important.
328	* @param pvElement the pointer to be added, typecast to pointer-to-void
329	*/
330	#define VEC_PUSH_BACK_PTR(pvec, type, pvElement) \
331	vecPushBackPtr(pvec, VECTOR_TOKEN_HASH(type), \
332	(pvElement) + ((pvElement) - (type)(pvElement)))
333
334	/**
335	* Returns the count of elements in a vector.
336	* @param pvec pointer to the vector.
337	*/
338	#define VEC_SIZE_OBJ(pvec) (pvec)->mcElements
339
340	/**
341	* Returns the count of elements in a vector-of-pointers.
342	* @param pvec pointer to the vector.
343	*/
344	#define VEC_SIZE_PTR VEC_SIZE_OBJ
345
346	/**
347	* Iterates over a vector.
348	*
349	* Iterates over the vector elements from first to last and execute the
350	* following instruction or block on each iteration with @a pIterator set to
351	* point to the current element (that is, a pointer to the pointer element for
352	* a vector-of-pointers). Use in the same way as a "for" statement.
353	*
354	* @param pvec Pointer to the vector to be iterated over.
355	* @param type The type of the vector, must match the type specified at
356	* vector initialisation (including whitespace etc).
357	* @param pIterator A pointer to @a type which will be set to point to the
358	* current vector element on each iteration.
359	*
360	* @todo can we assert the correctness of the type in some way?
361	*/
362	#define VEC_FOR_EACH(pvec, type, pIterator) \
363	for (pIterator = (type *) (pvec)->mpvaElements; \
364	(pvec)->muTypeHash == VECTOR_TOKEN_HASH(type) \
365	&& pIterator < (type *) (pvec)->mpvaElements + (pvec)->mcElements; \
366	++pIterator)
367
368	#endif /* !MAIN_INCLUDED_vector_h */

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

source: vbox/trunk/src/VBox/Main/include/vector.h@ 98102

Download in other formats: