vector.h revision b0a3d0ec5780199a2f379da63c59ccf48f1a73b9
/** @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 */