VirtualBox

source: vbox/trunk/include/iprt/vector.h@ 103224

Last change on this file since 103224 was 98103, checked in by vboxsync, 21 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: 18.6 KB
Line 
1/** @file
2 * IPRT - Vector - STL-inspired vector implementation in C.
3 */
4
5/*
6 * Copyright (C) 2011-2023 Oracle and/or its affiliates.
7 *
8 * This file is part of VirtualBox base platform packages, as
9 * available from https://www.virtualbox.org.
10 *
11 * This program is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU General Public License
13 * as published by the Free Software Foundation, in version 3 of the
14 * License.
15 *
16 * This program is distributed in the hope that it will be useful, but
17 * WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with this program; if not, see <https://www.gnu.org/licenses>.
23 *
24 * The contents of this file may alternatively be used under the terms
25 * of the Common Development and Distribution License Version 1.0
26 * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included
27 * in the VirtualBox distribution, in which case the provisions of the
28 * CDDL are applicable instead of those of the GPL.
29 *
30 * You may elect to license modified versions of this file under the
31 * terms and conditions of either the GPL or the CDDL or both.
32 *
33 * SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0
34 */
35
36/**
37 * @todo the right Doxygen tag here
38 * This file defines a set of macros which provide a functionality and an
39 * interface roughly similar to the C++ STL vector container. To create a
40 * vector of a particular type one must first explicitly instantiate such a
41 * vector in the source file, e.g.
42 * RTVEC_DECL(TopLevels, Window *)
43 * without a semi-colon. This macro will define a structure (struct TopLevels)
44 * which contains a dynamically resizeable array of Window * elements. It
45 * will also define a number of inline methods for manipulating the structure,
46 * such as
47 * Window *TopLevelsPushBack(struct TopLevels *)
48 * which adds a new element to the end of the array and returns it, optionally
49 * reallocating the array if there is not enough space for the new element.
50 * (This particular method prototype differs from the STL equivalent -
51 * push_back - more than most of the other methods).
52 *
53 * To create a vector, one simply needs to declare the structure, in this case
54 * struct TopLevels = RTVEC_INITIALIZER;
55 *
56 * There are various other macros for declaring vectors with different
57 * allocators (e.g. RTVEC_DECL_ALLOCATOR) or with clean-up functions
58 * (e.g. RTVEC_DECL_DELETE). See the descriptions of the generic methods and
59 * the declarator macros below.
60 *
61 * One particular use of vectors is to assemble an array of a particular type
62 * in heap memory without knowing - or counting - the number of elements in
63 * advance. To do this, add the elements onto the array using PushBack, then
64 * extract the array from the vector using the (non-STL) Detach method.
65 *
66 * @note functions in this file are inline to prevent warnings about
67 * unused static functions. I assume that in this day and age a
68 * compiler makes its own decisions about whether to actually
69 * inline a function.
70 * @note since vector structures must be explicitly instanciated unlike the
71 * C++ vector template, care must be taken not to instanciate a
72 * particular type twice, e.g. once in a header and once in a code file.
73 * Only using vectors in code files and keeping them out of interfaces
74 * (or passing them as anonymously) makes it easier to take care of this.
75 */
76
77#ifndef IPRT_INCLUDED_vector_h
78#define IPRT_INCLUDED_vector_h
79#ifndef RT_WITHOUT_PRAGMA_ONCE
80# pragma once
81#endif
82
83/*******************************************************************************
84* Header Files *
85*******************************************************************************/
86
87#include <iprt/assert.h>
88#include <iprt/cdefs.h>
89#include <iprt/errcore.h>
90#include <iprt/mem.h> /** @todo Should the caller include this if they need
91 * it? */
92
93
94/**
95 * Generic vector structure
96 */
97/** @todo perhaps we should include an additional member for a parameter to
98 * three-argument reallocators, so that we can support e.g. mempools? */
99#define RTVEC_DECL_STRUCT(name, type) \
100struct name \
101{ \
102 /** The number of elements in the vector */ \
103 size_t mcElements; \
104 /** The current capacity of the vector */ \
105 size_t mcCapacity; \
106 /** The elements themselves */ \
107 type *mpElements; \
108};
109
110/** Initialiser for an empty vector structure */
111#define RTVEC_INITIALIZER { 0, 0, NULL }
112
113/** The unit by which the vector capacity is increased */
114#define RTVECIMPL_ALLOC_UNIT 16
115
116/**
117 * Generic method - get the size of a vector
118 */
119/** @todo What is the correct way to do doxygen for this sort of macro? */
120#define RTVEC_DECLFN_SIZE(name, type) \
121DECLINLINE(size_t) name ## Size(struct name *pVec) \
122{ \
123 return(pVec->mcElements); \
124}
125
126/**
127 * Generic method - expand a vector
128 */
129#define RTVEC_DECLFN_RESERVE(name, type, pfnRealloc) \
130DECLINLINE(int) name ## Reserve(struct name *pVec, size_t cNewCapacity) \
131{ \
132 void *pvNew; \
133 \
134 if (cNewCapacity <= pVec->mcCapacity) \
135 return VINF_SUCCESS; \
136 pvNew = pfnRealloc(pVec->mpElements, cNewCapacity * sizeof(type)); \
137 if (!pvNew) \
138 return VERR_NO_MEMORY; \
139 pVec->mcCapacity = cNewCapacity; \
140 pVec->mpElements = (type *)pvNew; \
141 return VINF_SUCCESS; \
142}
143
144/**
145 * Generic method - return a pointer to the first element in the vector.
146 */
147#define RTVEC_DECLFN_BEGIN(name, type) \
148DECLINLINE(type *) name ## Begin(struct name *pVec) \
149{ \
150 return(pVec->mpElements); \
151}
152
153/**
154 * Generic method - return a pointer to one past the last element in the
155 * vector.
156 */
157#define RTVEC_DECLFN_END(name, type) \
158DECLINLINE(type *) name ## End(struct name *pVec) \
159{ \
160 return(&pVec->mpElements[pVec->mcElements]); \
161}
162
163/**
164 * Generic method - add a new, uninitialised element onto a vector and return
165 * it.
166 * @note this method differs from the STL equivalent by letting the caller
167 * post-initialise the new element rather than copying it from its
168 * argument.
169 */
170#define RTVEC_DECLFN_PUSHBACK(name, type) \
171DECLINLINE(type *) name ## PushBack(struct name *pVec) \
172{ \
173 Assert(pVec->mcElements <= pVec->mcCapacity); \
174 if ( pVec->mcElements == pVec->mcCapacity \
175 && RT_FAILURE(name ## Reserve(pVec, pVec->mcCapacity \
176 + RTVECIMPL_ALLOC_UNIT))) \
177 return NULL; \
178 ++pVec->mcElements; \
179 return &pVec->mpElements[pVec->mcElements - 1]; \
180}
181
182/**
183 * Generic method - drop the last element from the vector.
184 */
185#define RTVEC_DECLFN_POPBACK(name) \
186DECLINLINE(void) name ## PopBack(struct name *pVec) \
187{ \
188 Assert(pVec->mcElements <= pVec->mcCapacity); \
189 --pVec->mcElements; \
190}
191
192/**
193 * Generic method - drop the last element from the vector, calling a clean-up
194 * method first.
195 *
196 * By taking an adapter function for the element to be dropped as an
197 * additional macro parameter we can support clean-up by pointer
198 * (pfnAdapter maps T* -> T*) or by value (maps T* -> T). pfnAdapter takes
199 * one argument of type @a type * and must return whatever type pfnDelete
200 * expects.
201 */
202/** @todo find a better name for pfnAdapter? */
203#define RTVEC_DECLFN_POPBACK_DELETE(name, type, pfnDelete, pfnAdapter) \
204DECLINLINE(void) name ## PopBack(struct name *pVec) \
205{ \
206 Assert(pVec->mcElements <= pVec->mcCapacity); \
207 --pVec->mcElements; \
208 pfnDelete(pfnAdapter(&pVec->mpElements[pVec->mcElements])); \
209}
210
211/**
212 * Generic method - reset a vector to empty.
213 * @note This function does not free any memory
214 */
215#define RTVEC_DECLFN_CLEAR(name) \
216DECLINLINE(void) name ## Clear(struct name *pVec) \
217{ \
218 Assert(pVec->mcElements <= pVec->mcCapacity); \
219 pVec->mcElements = 0; \
220}
221
222/**
223 * Generic method - reset a vector to empty, calling a clean-up method on each
224 * element first.
225 * @note See @a RTVEC_DECLFN_POPBACK_DELETE for an explanation of pfnAdapter
226 * @note This function does not free any memory
227 * @note The cleanup function is currently called on the elements from first
228 * to last. The testcase expects this.
229 */
230#define RTVEC_DECLFN_CLEAR_DELETE(name, pfnDelete, pfnAdapter) \
231DECLINLINE(void) name ## Clear(struct name *pVec) \
232{ \
233 size_t i; \
234 \
235 Assert(pVec->mcElements <= pVec->mcCapacity); \
236 for (i = 0; i < pVec->mcElements; ++i) \
237 pfnDelete(pfnAdapter(&pVec->mpElements[i])); \
238 pVec->mcElements = 0; \
239}
240
241/**
242 * Generic method - detach the array contained inside a vector and reset the
243 * vector to empty.
244 * @note This function does not free any memory
245 */
246#define RTVEC_DECLFN_DETACH(name, type) \
247DECLINLINE(type *) name ## Detach(struct name *pVec) \
248{ \
249 type *pArray = pVec->mpElements; \
250 \
251 Assert(pVec->mcElements <= pVec->mcCapacity); \
252 pVec->mcElements = 0; \
253 pVec->mpElements = NULL; \
254 pVec->mcCapacity = 0; \
255 return pArray; \
256}
257
258/** Common declarations for all vector types */
259#define RTVEC_DECL_COMMON(name, type, pfnRealloc) \
260 RTVEC_DECL_STRUCT(name, type) \
261 RTVEC_DECLFN_SIZE(name, type) \
262 RTVEC_DECLFN_RESERVE(name, type, pfnRealloc) \
263 RTVEC_DECLFN_BEGIN(name, type) \
264 RTVEC_DECLFN_END(name, type) \
265 RTVEC_DECLFN_PUSHBACK(name, type) \
266 RTVEC_DECLFN_DETACH(name, type)
267
268/**
269 * Declarator macro - declare a vector type
270 * @param name the name of the C struct type describing the vector as
271 * well as the prefix of the functions for manipulating it
272 * @param type the type of the objects contained in the vector
273 * @param pfnRealloc the memory reallocation function used for expanding the
274 * vector
275 */
276#define RTVEC_DECL_ALLOCATOR(name, type, pfnRealloc) \
277 RTVEC_DECL_COMMON(name, type, pfnRealloc) \
278 RTVEC_DECLFN_POPBACK(name) \
279 RTVEC_DECLFN_CLEAR(name)
280
281/**
282 * Generic method - inline id mapping delete adapter function - see the
283 * explanation of pfnAdapter in @a RTVEC_DECLFN_POPBACK_DELETE.
284 */
285#define RTVEC_DECLFN_DELETE_ADAPTER_ID(name, type) \
286DECLINLINE(type *) name ## DeleteAdapterId(type *arg) \
287{ \
288 return arg; \
289}
290
291/**
292 * Generic method - inline pointer-to-value mapping delete adapter function -
293 * see the explanation of pfnAdapter in @a RTVEC_DECLFN_POPBACK_DELETE.
294 */
295#define RTVEC_DECLFN_DELETE_ADAPTER_TO_VALUE(name, type) \
296DECLINLINE(type) name ## DeleteAdapterToValue(type *arg) \
297{ \
298 return *arg; \
299}
300
301/**
302 * Declarator macro - declare a vector type with a cleanup callback to be used
303 * when elements are dropped from the vector. The callback takes a pointer to
304 * @a type,
305 * NOT a value of type @a type.
306 * @param name the name of the C struct type describing the vector as
307 * well as the prefix of the functions for manipulating it
308 * @param type the type of the objects contained in the vector
309 * @param pfnRealloc the memory reallocation function used for expanding the
310 * vector
311 * @param pfnDelete the cleanup callback function - signature
312 * void pfnDelete(type *)
313 */
314#define RTVEC_DECL_ALLOCATOR_DELETE(name, type, pfnRealloc, pfnDelete) \
315 RTVEC_DECL_COMMON(name, type, pfnRealloc) \
316 RTVEC_DECLFN_DELETE_ADAPTER_ID(name, type) \
317 RTVEC_DECLFN_POPBACK_DELETE(name, type, pfnDelete, \
318 name ## DeleteAdapterId) \
319 RTVEC_DECLFN_CLEAR_DELETE(name, pfnDelete, name ## DeleteAdapterId)
320
321/**
322 * Declarator macro - declare a vector type with a cleanup callback to be used
323 * when elements are dropped from the vector. The callback takes a parameter
324 * of type @a type, NOT a pointer to @a type.
325 * @param name the name of the C struct type describing the vector as
326 * well as the prefix of the functions for manipulating it
327 * @param type the type of the objects contained in the vector
328 * @param pfnRealloc the memory reallocation function used for expanding the
329 * vector
330 * @param pfnDelete the cleanup callback function - signature
331 * void pfnDelete(type)
332 */
333#define RTVEC_DECL_ALLOCATOR_DELETE_BY_VALUE(name, type, pfnRealloc, \
334 pfnDelete) \
335 RTVEC_DECL_COMMON(name, type, pfnRealloc) \
336 RTVEC_DECLFN_DELETE_ADAPTER_TO_VALUE(name, type) \
337 RTVEC_DECLFN_POPBACK_DELETE(name, type, pfnDelete, \
338 name ## DeleteAdapterToValue) \
339 RTVEC_DECLFN_CLEAR_DELETE(name, pfnDelete, \
340 name ## DeleteAdapterToValue)
341
342/**
343 * Inline wrapper around RTMemRealloc macro to get a function usable as a
344 * callback.
345 */
346DECLINLINE(void *) rtvecReallocDefTag(void *pv, size_t cbNew)
347{
348 return RTMemRealloc(pv, cbNew);
349}
350
351/**
352 * Declarator macro - declare a vector type (see @a RTVEC_DECL_ALLOCATOR)
353 * using RTMemRealloc as a memory allocator
354 * @param name the name of the C struct type describing the vector as
355 * well as the prefix of the functions for manipulating it
356 * @param type the type of the objects contained in the vector
357 */
358#define RTVEC_DECL(name, type) \
359 RTVEC_DECL_ALLOCATOR(name, type, rtvecReallocDefTag)
360
361/**
362 * Declarator macro - declare a vector type with a cleanup by pointer callback
363 * (see @a RTVEC_DECL_ALLOCATOR_DELETE) using RTMemRealloc as a memory
364 * allocator
365 * @param name the name of the C struct type describing the vector as
366 * well as the prefix of the functions for manipulating it
367 * @param type the type of the objects contained in the vector
368 * @param pfnDelete the cleanup callback function - signature
369 * void pfnDelete(type *)
370 */
371#define RTVEC_DECL_DELETE(name, type, pfnDelete) \
372 RTVEC_DECL_ALLOCATOR_DELETE(name, type, rtvecReallocDefTag, pfnDelete)
373
374/**
375 * Declarator macro - declare a vector type with a cleanup by value callback
376 * (see @a RTVEC_DECL_ALLOCATOR_DELETE_BY_VALUE) using RTMemRealloc as a memory
377 * allocator
378 * @param name the name of the C struct type describing the vector as
379 * well as the prefix of the functions for manipulating it
380 * @param type the type of the objects contained in the vector
381 * @param pfnDelete the cleanup callback function - signature
382 * void pfnDelete(type)
383 */
384#define RTVEC_DECL_DELETE_BY_VALUE(name, type, pfnDelete) \
385 RTVEC_DECL_ALLOCATOR_DELETE_BY_VALUE(name, type, rtvecReallocDefTag, \
386 pfnDelete)
387
388#endif /* !IPRT_INCLUDED_vector_h */
389
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