VirtualBox

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

Last change on this file since 94521 was 93115, checked in by vboxsync, 2 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 */
86typedef struct VECTOR_OBJ VECTOR_STRUCT VECTOR_OBJ;
87
88/** A vector of pointer values. (A handy special case.) */
89typedef 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. */
109DECLINLINE(void) vecNoCleanup(void *pvElement)
110{
111 (void) pvElement;
112}
113
114/** Expand an existing vector, implementation */
115DECLINLINE(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. */
136DECLINLINE(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. */
147DECLINLINE(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 */
157DECLINLINE(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 */
165DECLINLINE(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. */
181DECLINLINE(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. */
188DECLINLINE(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 */
195DECLINLINE(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 */
210DECLINLINE(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.

© 2023 Oracle
Contact – Privacy policy – Terms of Use