VirtualBox

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

Last change on this file since 77807 was 76585, checked in by vboxsync, 6 years ago

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

© 2024 Oracle
Contact – Privacy/Do Not Sell My Info – Terms of Use