summaryrefslogtreecommitdiffstats
path: root/include/iprt/vector.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/iprt/vector.h')
-rw-r--r--include/iprt/vector.h389
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 */
+