VirtualBox

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

Last change on this file since 98263 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: 14.0 KB
Line 
1/* $Id: vector.h 98103 2023-01-17 14:15: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-2023 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 */
96typedef struct VECTOR_OBJ VECTOR_STRUCT VECTOR_OBJ;
97
98/** A vector of pointer values. (A handy special case.) */
99typedef 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. */
119DECLINLINE(void) vecNoCleanup(void *pvElement)
120{
121 (void) pvElement;
122}
123
124/** Expand an existing vector, implementation */
125DECLINLINE(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. */
146DECLINLINE(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. */
157DECLINLINE(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 */
167DECLINLINE(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 */
175DECLINLINE(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. */
191DECLINLINE(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. */
198DECLINLINE(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 */
205DECLINLINE(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 */
220DECLINLINE(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.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette