diff options
Diffstat (limited to 'include/iprt/vector.h')
| -rw-r--r-- | include/iprt/vector.h | 389 |
1 files changed, 389 insertions, 0 deletions
diff --git a/include/iprt/vector.h b/include/iprt/vector.h new file mode 100644 index 00000000..0e3f6a8a --- /dev/null +++ b/include/iprt/vector.h @@ -0,0 +1,389 @@ +/** @file + * IPRT - Vector - STL-inspired vector implementation in C. + */ + +/* + * Copyright (C) 2011-2022 Oracle and/or its affiliates. + * + * This file is part of VirtualBox base platform packages, as + * available from https://www.virtualbox.org. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation, in version 3 of the + * License. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, see <https://www.gnu.org/licenses>. + * + * The contents of this file may alternatively be used under the terms + * of the Common Development and Distribution License Version 1.0 + * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included + * in the VirtualBox distribution, in which case the provisions of the + * CDDL are applicable instead of those of the GPL. + * + * You may elect to license modified versions of this file under the + * terms and conditions of either the GPL or the CDDL or both. + * + * SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0 + */ + +/** + * @todo the right Doxygen tag here + * This file defines a set of macros which provide a functionality and an + * interface roughly similar to the C++ STL vector container. To create a + * vector of a particular type one must first explicitly instantiate such a + * vector in the source file, e.g. + * RTVEC_DECL(TopLevels, Window *) + * without a semi-colon. This macro will define a structure (struct TopLevels) + * which contains a dynamically resizeable array of Window * elements. It + * will also define a number of inline methods for manipulating the structure, + * such as + * Window *TopLevelsPushBack(struct TopLevels *) + * which adds a new element to the end of the array and returns it, optionally + * reallocating the array if there is not enough space for the new element. + * (This particular method prototype differs from the STL equivalent - + * push_back - more than most of the other methods). + * + * To create a vector, one simply needs to declare the structure, in this case + * struct TopLevels = RTVEC_INITIALIZER; + * + * There are various other macros for declaring vectors with different + * allocators (e.g. RTVEC_DECL_ALLOCATOR) or with clean-up functions + * (e.g. RTVEC_DECL_DELETE). See the descriptions of the generic methods and + * the declarator macros below. + * + * One particular use of vectors is to assemble an array of a particular type + * in heap memory without knowing - or counting - the number of elements in + * advance. To do this, add the elements onto the array using PushBack, then + * extract the array from the vector using the (non-STL) Detach method. + * + * @note functions in this file are inline to prevent warnings about + * unused static functions. I assume that in this day and age a + * compiler makes its own decisions about whether to actually + * inline a function. + * @note since vector structures must be explicitly instanciated unlike the + * C++ vector template, care must be taken not to instanciate a + * particular type twice, e.g. once in a header and once in a code file. + * Only using vectors in code files and keeping them out of interfaces + * (or passing them as anonymously) makes it easier to take care of this. + */ + +#ifndef IPRT_INCLUDED_vector_h +#define IPRT_INCLUDED_vector_h +#ifndef RT_WITHOUT_PRAGMA_ONCE +# pragma once +#endif + +/******************************************************************************* +* Header Files * +*******************************************************************************/ + +#include <iprt/assert.h> +#include <iprt/cdefs.h> +#include <iprt/errcore.h> +#include <iprt/mem.h> /** @todo Should the caller include this if they need + * it? */ + + +/** + * Generic vector structure + */ +/** @todo perhaps we should include an additional member for a parameter to + * three-argument reallocators, so that we can support e.g. mempools? */ +#define RTVEC_DECL_STRUCT(name, type) \ +struct name \ +{ \ + /** The number of elements in the vector */ \ + size_t mcElements; \ + /** The current capacity of the vector */ \ + size_t mcCapacity; \ + /** The elements themselves */ \ + type *mpElements; \ +}; + +/** Initialiser for an empty vector structure */ +#define RTVEC_INITIALIZER { 0, 0, NULL } + +/** The unit by which the vector capacity is increased */ +#define RTVECIMPL_ALLOC_UNIT 16 + +/** + * Generic method - get the size of a vector + */ +/** @todo What is the correct way to do doxygen for this sort of macro? */ +#define RTVEC_DECLFN_SIZE(name, type) \ +DECLINLINE(size_t) name ## Size(struct name *pVec) \ +{ \ + return(pVec->mcElements); \ +} + +/** + * Generic method - expand a vector + */ +#define RTVEC_DECLFN_RESERVE(name, type, pfnRealloc) \ +DECLINLINE(int) name ## Reserve(struct name *pVec, size_t cNewCapacity) \ +{ \ + void *pvNew; \ + \ + if (cNewCapacity <= pVec->mcCapacity) \ + return VINF_SUCCESS; \ + pvNew = pfnRealloc(pVec->mpElements, cNewCapacity * sizeof(type)); \ + if (!pvNew) \ + return VERR_NO_MEMORY; \ + pVec->mcCapacity = cNewCapacity; \ + pVec->mpElements = (type *)pvNew; \ + return VINF_SUCCESS; \ +} + +/** + * Generic method - return a pointer to the first element in the vector. + */ +#define RTVEC_DECLFN_BEGIN(name, type) \ +DECLINLINE(type *) name ## Begin(struct name *pVec) \ +{ \ + return(pVec->mpElements); \ +} + +/** + * Generic method - return a pointer to one past the last element in the + * vector. + */ +#define RTVEC_DECLFN_END(name, type) \ +DECLINLINE(type *) name ## End(struct name *pVec) \ +{ \ + return(&pVec->mpElements[pVec->mcElements]); \ +} + +/** + * Generic method - add a new, uninitialised element onto a vector and return + * it. + * @note this method differs from the STL equivalent by letting the caller + * post-initialise the new element rather than copying it from its + * argument. + */ +#define RTVEC_DECLFN_PUSHBACK(name, type) \ +DECLINLINE(type *) name ## PushBack(struct name *pVec) \ +{ \ + Assert(pVec->mcElements <= pVec->mcCapacity); \ + if ( pVec->mcElements == pVec->mcCapacity \ + && RT_FAILURE(name ## Reserve(pVec, pVec->mcCapacity \ + + RTVECIMPL_ALLOC_UNIT))) \ + return NULL; \ + ++pVec->mcElements; \ + return &pVec->mpElements[pVec->mcElements - 1]; \ +} + +/** + * Generic method - drop the last element from the vector. + */ +#define RTVEC_DECLFN_POPBACK(name) \ +DECLINLINE(void) name ## PopBack(struct name *pVec) \ +{ \ + Assert(pVec->mcElements <= pVec->mcCapacity); \ + --pVec->mcElements; \ +} + +/** + * Generic method - drop the last element from the vector, calling a clean-up + * method first. + * + * By taking an adapter function for the element to be dropped as an + * additional macro parameter we can support clean-up by pointer + * (pfnAdapter maps T* -> T*) or by value (maps T* -> T). pfnAdapter takes + * one argument of type @a type * and must return whatever type pfnDelete + * expects. + */ +/** @todo find a better name for pfnAdapter? */ +#define RTVEC_DECLFN_POPBACK_DELETE(name, type, pfnDelete, pfnAdapter) \ +DECLINLINE(void) name ## PopBack(struct name *pVec) \ +{ \ + Assert(pVec->mcElements <= pVec->mcCapacity); \ + --pVec->mcElements; \ + pfnDelete(pfnAdapter(&pVec->mpElements[pVec->mcElements])); \ +} + +/** + * Generic method - reset a vector to empty. + * @note This function does not free any memory + */ +#define RTVEC_DECLFN_CLEAR(name) \ +DECLINLINE(void) name ## Clear(struct name *pVec) \ +{ \ + Assert(pVec->mcElements <= pVec->mcCapacity); \ + pVec->mcElements = 0; \ +} + +/** + * Generic method - reset a vector to empty, calling a clean-up method on each + * element first. + * @note See @a RTVEC_DECLFN_POPBACK_DELETE for an explanation of pfnAdapter + * @note This function does not free any memory + * @note The cleanup function is currently called on the elements from first + * to last. The testcase expects this. + */ +#define RTVEC_DECLFN_CLEAR_DELETE(name, pfnDelete, pfnAdapter) \ +DECLINLINE(void) name ## Clear(struct name *pVec) \ +{ \ + size_t i; \ + \ + Assert(pVec->mcElements <= pVec->mcCapacity); \ + for (i = 0; i < pVec->mcElements; ++i) \ + pfnDelete(pfnAdapter(&pVec->mpElements[i])); \ + pVec->mcElements = 0; \ +} + +/** + * Generic method - detach the array contained inside a vector and reset the + * vector to empty. + * @note This function does not free any memory + */ +#define RTVEC_DECLFN_DETACH(name, type) \ +DECLINLINE(type *) name ## Detach(struct name *pVec) \ +{ \ + type *pArray = pVec->mpElements; \ + \ + Assert(pVec->mcElements <= pVec->mcCapacity); \ + pVec->mcElements = 0; \ + pVec->mpElements = NULL; \ + pVec->mcCapacity = 0; \ + return pArray; \ +} + +/** Common declarations for all vector types */ +#define RTVEC_DECL_COMMON(name, type, pfnRealloc) \ + RTVEC_DECL_STRUCT(name, type) \ + RTVEC_DECLFN_SIZE(name, type) \ + RTVEC_DECLFN_RESERVE(name, type, pfnRealloc) \ + RTVEC_DECLFN_BEGIN(name, type) \ + RTVEC_DECLFN_END(name, type) \ + RTVEC_DECLFN_PUSHBACK(name, type) \ + RTVEC_DECLFN_DETACH(name, type) + +/** + * Declarator macro - declare a vector type + * @param name the name of the C struct type describing the vector as + * well as the prefix of the functions for manipulating it + * @param type the type of the objects contained in the vector + * @param pfnRealloc the memory reallocation function used for expanding the + * vector + */ +#define RTVEC_DECL_ALLOCATOR(name, type, pfnRealloc) \ + RTVEC_DECL_COMMON(name, type, pfnRealloc) \ + RTVEC_DECLFN_POPBACK(name) \ + RTVEC_DECLFN_CLEAR(name) + +/** + * Generic method - inline id mapping delete adapter function - see the + * explanation of pfnAdapter in @a RTVEC_DECLFN_POPBACK_DELETE. + */ +#define RTVEC_DECLFN_DELETE_ADAPTER_ID(name, type) \ +DECLINLINE(type *) name ## DeleteAdapterId(type *arg) \ +{ \ + return arg; \ +} + +/** + * Generic method - inline pointer-to-value mapping delete adapter function - + * see the explanation of pfnAdapter in @a RTVEC_DECLFN_POPBACK_DELETE. + */ +#define RTVEC_DECLFN_DELETE_ADAPTER_TO_VALUE(name, type) \ +DECLINLINE(type) name ## DeleteAdapterToValue(type *arg) \ +{ \ + return *arg; \ +} + +/** + * Declarator macro - declare a vector type with a cleanup callback to be used + * when elements are dropped from the vector. The callback takes a pointer to + * @a type, + * NOT a value of type @a type. + * @param name the name of the C struct type describing the vector as + * well as the prefix of the functions for manipulating it + * @param type the type of the objects contained in the vector + * @param pfnRealloc the memory reallocation function used for expanding the + * vector + * @param pfnDelete the cleanup callback function - signature + * void pfnDelete(type *) + */ +#define RTVEC_DECL_ALLOCATOR_DELETE(name, type, pfnRealloc, pfnDelete) \ + RTVEC_DECL_COMMON(name, type, pfnRealloc) \ + RTVEC_DECLFN_DELETE_ADAPTER_ID(name, type) \ + RTVEC_DECLFN_POPBACK_DELETE(name, type, pfnDelete, \ + name ## DeleteAdapterId) \ + RTVEC_DECLFN_CLEAR_DELETE(name, pfnDelete, name ## DeleteAdapterId) + +/** + * Declarator macro - declare a vector type with a cleanup callback to be used + * when elements are dropped from the vector. The callback takes a parameter + * of type @a type, NOT a pointer to @a type. + * @param name the name of the C struct type describing the vector as + * well as the prefix of the functions for manipulating it + * @param type the type of the objects contained in the vector + * @param pfnRealloc the memory reallocation function used for expanding the + * vector + * @param pfnDelete the cleanup callback function - signature + * void pfnDelete(type) + */ +#define RTVEC_DECL_ALLOCATOR_DELETE_BY_VALUE(name, type, pfnRealloc, \ + pfnDelete) \ + RTVEC_DECL_COMMON(name, type, pfnRealloc) \ + RTVEC_DECLFN_DELETE_ADAPTER_TO_VALUE(name, type) \ + RTVEC_DECLFN_POPBACK_DELETE(name, type, pfnDelete, \ + name ## DeleteAdapterToValue) \ + RTVEC_DECLFN_CLEAR_DELETE(name, pfnDelete, \ + name ## DeleteAdapterToValue) + +/** + * Inline wrapper around RTMemRealloc macro to get a function usable as a + * callback. + */ +DECLINLINE(void *) rtvecReallocDefTag(void *pv, size_t cbNew) +{ + return RTMemRealloc(pv, cbNew); +} + +/** + * Declarator macro - declare a vector type (see @a RTVEC_DECL_ALLOCATOR) + * using RTMemRealloc as a memory allocator + * @param name the name of the C struct type describing the vector as + * well as the prefix of the functions for manipulating it + * @param type the type of the objects contained in the vector + */ +#define RTVEC_DECL(name, type) \ + RTVEC_DECL_ALLOCATOR(name, type, rtvecReallocDefTag) + +/** + * Declarator macro - declare a vector type with a cleanup by pointer callback + * (see @a RTVEC_DECL_ALLOCATOR_DELETE) using RTMemRealloc as a memory + * allocator + * @param name the name of the C struct type describing the vector as + * well as the prefix of the functions for manipulating it + * @param type the type of the objects contained in the vector + * @param pfnDelete the cleanup callback function - signature + * void pfnDelete(type *) + */ +#define RTVEC_DECL_DELETE(name, type, pfnDelete) \ + RTVEC_DECL_ALLOCATOR_DELETE(name, type, rtvecReallocDefTag, pfnDelete) + +/** + * Declarator macro - declare a vector type with a cleanup by value callback + * (see @a RTVEC_DECL_ALLOCATOR_DELETE_BY_VALUE) using RTMemRealloc as a memory + * allocator + * @param name the name of the C struct type describing the vector as + * well as the prefix of the functions for manipulating it + * @param type the type of the objects contained in the vector + * @param pfnDelete the cleanup callback function - signature + * void pfnDelete(type) + */ +#define RTVEC_DECL_DELETE_BY_VALUE(name, type, pfnDelete) \ + RTVEC_DECL_ALLOCATOR_DELETE_BY_VALUE(name, type, rtvecReallocDefTag, \ + pfnDelete) + +#endif /* !IPRT_INCLUDED_vector_h */ + |