vector.h@ 63562

Last change on this file since 63562 was 62485, 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: 13.2 KB

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

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

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

Download in other formats: