VirtualBox

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

Last change on this file since 101505 was 98296, checked in by vboxsync, 23 months ago

Main/include: rc -> hrc/vrc. Enabled scm rc checks. bugref:10223
  • 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 98296 2023-01-25 01:28:38Z 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 AssertReturn(pvec->muTypeHash == uTypeHash, VERR_INVALID_PARAMETER);
209 if (pvec->mcElements == pvec->mcCapacity)
210 {
211 int vrc2 = VEC_EXPAND(pvec);
212 if (RT_FAILURE(vrc2))
213 return vrc2;
214 }
215 memcpy(VEC_GET_ELEMENT_OBJ(pvec->mpvaElements, pvec->mcbElement,
216 pvec->mcElements), pvElement, pvec->mcbElement);
217 ++pvec->mcElements;
218 return VINF_SUCCESS;
219}
220
221/** Add a pointer onto the end of a pointer vector */
222DECLINLINE(int) vecPushBackPtr(VECTOR_PTR *pvec, unsigned uTypeHash,
223 void *pv)
224{
225 AssertReturn(pvec->muTypeHash == uTypeHash, VERR_INVALID_PARAMETER);
226 if (pvec->mcElements == pvec->mcCapacity)
227 {
228 int vrc2 = VEC_EXPAND(pvec);
229 if (RT_FAILURE(vrc2))
230 return vrc2;
231 }
232 VEC_GET_ELEMENT_PTR(pvec->mpvaElements, pvec->mcElements) = pv;
233 ++pvec->mcElements;
234 return VINF_SUCCESS;
235}
236
237
238/*********************************************************************************************************************************
239* Public interface macros *
240*********************************************************************************************************************************/
241
242/**
243 * Initialise a vector structure. Always succeeds.
244 * @param pvec pointer to an uninitialised vector structure
245 * @param type the type of the objects in the vector. As this is
246 * hashed by the preprocessor use of space etc is
247 * important.
248 * @param pfnCleanup cleanup function (void (*pfn)(void *)) that is called
249 * on a pointer to a vector element when that element is
250 * dropped
251 */
252#define VEC_INIT_OBJ(pvec, type, pfnCleanup) \
253 vecInitObj(pvec, sizeof(type), VECTOR_TOKEN_HASH(type), \
254 (void (*)(void*)) pfnCleanup)
255
256/**
257 * Initialise a vector-of-pointers structure. Always succeeds.
258 * @param pvec pointer to an uninitialised vector structure
259 * @param type the type of the pointers in the vector, including the
260 * final "*". As this is hashed by the preprocessor use
261 * of space etc is important.
262 * @param pfnCleanup cleanup function (void (*pfn)(void *)) that is called
263 * directly on a vector element when that element is
264 * dropped
265 */
266#define VEC_INIT_PTR(pvec, type, pfnCleanup) \
267 vecInitPtr(pvec, sizeof(type), VECTOR_TOKEN_HASH(type), \
268 (void (*)(void*)) pfnCleanup)
269
270/**
271 * Clean up a vector.
272 * @param pvec pointer to the vector to clean up. The clean up function
273 * specified at initialisation (if any) is called for each element
274 * in the vector. After clean up, the vector structure is invalid
275 * until it is re-initialised
276 */
277#define VEC_CLEANUP_OBJ vecCleanupObj
278
279/**
280 * Clean up a vector-of-pointers.
281 * @param pvec pointer to the vector to clean up. The clean up function
282 * specified at initialisation (if any) is called for each element
283 * in the vector. After clean up, the vector structure is invalid
284 * until it is re-initialised
285 */
286#define VEC_CLEANUP_PTR vecCleanupPtr
287
288/**
289 * Reinitialises a vector structure to empty.
290 * @param pvec pointer to the vector to re-initialise. The clean up function
291 * specified at initialisation (if any) is called for each element
292 * in the vector.
293 */
294#define VEC_CLEAR_OBJ vecClearObj
295
296/**
297 * Reinitialises a vector-of-pointers structure to empty.
298 * @param pvec pointer to the vector to re-initialise. The clean up function
299 * specified at initialisation (if any) is called for each element
300 * in the vector.
301 */
302#define VEC_CLEAR_PTR vecClearPtr
303
304/**
305 * Adds an element to the back of a vector. The element will be byte-copied
306 * and become owned by the vector, to be cleaned up by the vector's clean-up
307 * routine when the element is dropped.
308 * @returns iprt status code (VINF_SUCCESS or VERR_NO_MEMORY)
309 * @returns VERR_INVALID_PARAMETER if the type does not match the type given
310 * when the vector was initialised (asserted)
311 * @param pvec pointer to the vector on to which the element should be
312 * added
313 * @param type the type of the vector as specified at initialisation.
314 * Spacing etc is important.
315 * @param pvElement void pointer to the element to be added
316 */
317#define VEC_PUSH_BACK_OBJ(pvec, type, pvElement) \
318 vecPushBackObj(pvec, VECTOR_TOKEN_HASH(type), \
319 (pvElement) + ((pvElement) - (type *)(pvElement)))
320
321/**
322 * Adds a pointer to the back of a vector-of-pointers. The pointer will become
323 * owned by the vector, to be cleaned up by the vector's clean-up routine when
324 * it is dropped.
325 * @returns iprt status code (VINF_SUCCESS or VERR_NO_MEMORY)
326 * @returns VERR_INVALID_PARAMETER if the type does not match the type given
327 * when the vector was initialised (asserted)
328 * @param pvec pointer to the vector on to which the element should be
329 * added
330 * @param type the type of the vector as specified at initialisation.
331 * Spacing etc is important.
332 * @param pvElement the pointer to be added, typecast to pointer-to-void
333 */
334#define VEC_PUSH_BACK_PTR(pvec, type, pvElement) \
335 vecPushBackPtr(pvec, VECTOR_TOKEN_HASH(type), \
336 (pvElement) + ((pvElement) - (type)(pvElement)))
337
338/**
339 * Returns the count of elements in a vector.
340 * @param pvec pointer to the vector.
341 */
342#define VEC_SIZE_OBJ(pvec) (pvec)->mcElements
343
344/**
345 * Returns the count of elements in a vector-of-pointers.
346 * @param pvec pointer to the vector.
347 */
348#define VEC_SIZE_PTR VEC_SIZE_OBJ
349
350/**
351 * Iterates over a vector.
352 *
353 * Iterates over the vector elements from first to last and execute the
354 * following instruction or block on each iteration with @a pIterator set to
355 * point to the current element (that is, a pointer to the pointer element for
356 * a vector-of-pointers). Use in the same way as a "for" statement.
357 *
358 * @param pvec Pointer to the vector to be iterated over.
359 * @param type The type of the vector, must match the type specified at
360 * vector initialisation (including whitespace etc).
361 * @param pIterator A pointer to @a type which will be set to point to the
362 * current vector element on each iteration.
363 *
364 * @todo can we assert the correctness of the type in some way?
365 */
366#define VEC_FOR_EACH(pvec, type, pIterator) \
367 for (pIterator = (type *) (pvec)->mpvaElements; \
368 (pvec)->muTypeHash == VECTOR_TOKEN_HASH(type) \
369 && pIterator < (type *) (pvec)->mpvaElements + (pvec)->mcElements; \
370 ++pIterator)
371
372#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