vector.h@ 93444

Last change on this file since 93444 was 93115, checked in by vboxsync, 3 years ago
scm --update-copyright-year
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 13.7 KB

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

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

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

Download in other formats: