path: root/include/iprt/vector.h

/** @file
 * IPRT - Vector
 * STL-inspired vector implementation in C
 */

/*
 * Copyright (C) 2011 Oracle Corporation
 *
 * This file is part of VirtualBox Open Source Edition (OSE), as
 * available from http://www.virtualbox.org. This file is free software;
 * you can redistribute it and/or modify it under the terms of the GNU
 * General Public License (GPL) as published by the Free Software
 * Foundation, in version 2 as it comes in the "COPYING" file of the
 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
 *
 * The contents of this file may alternatively be used under the terms
 * of the Common Development and Distribution License Version 1.0
 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
 * VirtualBox OSE 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.
 */

/**
 * @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_vector_h
# define ___iprt_vector_h

/*******************************************************************************
*   Header Files                                                               *
*******************************************************************************/

#include <iprt/assert.h>
#include <iprt/cdefs.h>
#include <iprt/err.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_vector_h */