/** @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 #include #include #include /** @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 */