Adding upstream version 7.0.6-dfsg.upstream/7.0.6-dfsgupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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 */
+