9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * STL-inspired vector implementation in C
5e768213e353675f7bb7deda92733ee25f27a20evboxsync * @note functions in this file are inline to prevent warnings about
5e768213e353675f7bb7deda92733ee25f27a20evboxsync * unused static functions. I assume that in this day and age a
5e768213e353675f7bb7deda92733ee25f27a20evboxsync * compiler makes its own decisions about whether to actually
5e768213e353675f7bb7deda92733ee25f27a20evboxsync * inline a function.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @note as this header is included in rdesktop-vrdp, we do not include other
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * required header files here (to wit assert.h, err.h, mem.h and
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * types.h). These must be included first. If this moves to iprt, we
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * should write a wrapper around it doing that.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @todo can we do more of the type checking at compile time somehow?
5e768213e353675f7bb7deda92733ee25f27a20evboxsync * Copyright (C) 2008-2010 Oracle Corporation
5e768213e353675f7bb7deda92733ee25f27a20evboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
5e768213e353675f7bb7deda92733ee25f27a20evboxsync * available from http://www.virtualbox.org. This file is free software;
5e768213e353675f7bb7deda92733ee25f27a20evboxsync * you can redistribute it and/or modify it under the terms of the GNU
5e768213e353675f7bb7deda92733ee25f27a20evboxsync * General Public License (GPL) as published by the Free Software
5e768213e353675f7bb7deda92733ee25f27a20evboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
5e768213e353675f7bb7deda92733ee25f27a20evboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
5e768213e353675f7bb7deda92733ee25f27a20evboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
bbd8414a6c9e8c73fbe9cffd73b5747c0570b118vboxsync/*******************************************************************************
bbd8414a6c9e8c73fbe9cffd73b5747c0570b118vboxsync* Header Files *
bbd8414a6c9e8c73fbe9cffd73b5747c0570b118vboxsync*******************************************************************************/
bbd8414a6c9e8c73fbe9cffd73b5747c0570b118vboxsync/*******************************************************************************
bbd8414a6c9e8c73fbe9cffd73b5747c0570b118vboxsync* Helper macros and definitions *
bbd8414a6c9e8c73fbe9cffd73b5747c0570b118vboxsync*******************************************************************************/
5e768213e353675f7bb7deda92733ee25f27a20evboxsync/** The unit by which the vector capacity is increased */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Calculate a hash of a string of tokens for sanity type checking */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync ((unsigned) \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Helper macro for @a VECTOR_TOKEN_HASH */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync#define VECTOR_TOKEN_HASH_VALUE(token, place, mul) \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Helper macro for @a VECTOR_TOKEN_HASH */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync ^ VECTOR_TOKEN_HASH_VALUE(token, place + 1, 0x100) \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync ^ VECTOR_TOKEN_HASH_VALUE(token, place + 2, 0x10000) \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync ^ VECTOR_TOKEN_HASH_VALUE(token, place + 3, 0x1000000)
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Generic vector structure, used by @a VECTOR_OBJ and @a VECTOR_PTR */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync /** The number of elements in the vector */ \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync /** The current capacity of the vector */ \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync /** The size of an element */ \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync /** Hash value of the element type */ \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync /** The elements themselves */ \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync /** Destructor for elements - takes a pointer to an element. */ \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync void (*mpfnCleanup)(void *); \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/*** Structure definitions ***/
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** A vector of values or objects */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** A vector of pointer values. (A handy special case.) */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Convenience macro for annotating the type of the vector. Unfortunately the
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * type name is only cosmetic. */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** @todo can we do something useful with the type? */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Convenience macro for annotating the type of the vector. Unfortunately the
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * type name is only cosmetic. */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/*** Private helper functions and macros ***/
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync#define VEC_GET_ELEMENT_OBJ(pvaElements, cbElement, cElement) \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync ((void *)((char *)(pvaElements) + (cElement) * (cbElement)))
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync#define VEC_GET_ELEMENT_PTR(pvaElements, cElement) \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync (*(void **)VEC_GET_ELEMENT_OBJ(pvaElements, sizeof(void *), cElement))
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Default cleanup function that does nothing. */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Expand an existing vector, implementation */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsyncDECLINLINE(int) vecExpand(size_t *pcCapacity, void **ppvaElements,
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync pRealloc = RTMemRealloc(*ppvaElements, cNewCap * cbElement);
5e768213e353675f7bb7deda92733ee25f27a20evboxsync/** Expand an existing vector */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync#define VEC_EXPAND(pvec) vecExpand(&(pvec)->mcCapacity, &(pvec)->mpvaElements, \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Reset a vector, cleaning up all its elements. */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync unsigned i;
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync pvec->mpfnCleanup(VEC_GET_ELEMENT_OBJ(pvec->mpvaElements,
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Reset a pointer vector, cleaning up all its elements. */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync unsigned i;
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync pvec->mpfnCleanup(VEC_GET_ELEMENT_PTR(pvec->mpvaElements, i));
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Clean up a vector */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Clean up a pointer vector */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Initialise a vector structure, implementation */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync#define VEC_INIT(pvec, cbElement, uTypeHash, pfnCleanup) \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync pvec->mpfnCleanup = pfnCleanup ? pfnCleanup : vecNoCleanup; \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Initialise a vector. */
4ba684c495481036e2cd9ad27ef668841e21493evboxsyncDECLINLINE(void) vecInitObj(VECTOR_OBJ *pvec, size_t cbElement,
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Initialise a pointer vector. */
4ba684c495481036e2cd9ad27ef668841e21493evboxsyncDECLINLINE(void) vecInitPtr(VECTOR_PTR *pvec, size_t cbElement,
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Add an element onto the end of a vector */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsyncDECLINLINE(int) vecPushBackObj(VECTOR_OBJ *pvec, unsigned uTypeHash,
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync AssertReturn(pvec->muTypeHash == uTypeHash, VERR_INVALID_PARAMETER);
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync memcpy(VEC_GET_ELEMENT_OBJ(pvec->mpvaElements, pvec->mcbElement,
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync/** Add a pointer onto the end of a pointer vector */
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsyncDECLINLINE(int) vecPushBackPtr(VECTOR_PTR *pvec, unsigned uTypeHash,
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync AssertReturn(pvec->muTypeHash == uTypeHash, VERR_INVALID_PARAMETER);
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync VEC_GET_ELEMENT_PTR(pvec->mpvaElements, pvec->mcElements) = pv;
bbd8414a6c9e8c73fbe9cffd73b5747c0570b118vboxsync/*******************************************************************************
bbd8414a6c9e8c73fbe9cffd73b5747c0570b118vboxsync* Public interface macros *
bbd8414a6c9e8c73fbe9cffd73b5747c0570b118vboxsync*******************************************************************************/
4ba684c495481036e2cd9ad27ef668841e21493evboxsync * Initialise a vector structure. Always succeeds.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pvec pointer to an uninitialised vector structure
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param type the type of the objects in the vector. As this is
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * hashed by the preprocessor use of space etc is
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * important.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pfnCleanup cleanup function (void (*pfn)(void *)) that is called
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * on a pointer to a vector element when that element is
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync vecInitObj(pvec, sizeof(type), VECTOR_TOKEN_HASH(type), \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync (void (*)(void*)) pfnCleanup)
4ba684c495481036e2cd9ad27ef668841e21493evboxsync * Initialise a vector-of-pointers structure. Always succeeds.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pvec pointer to an uninitialised vector structure
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param type the type of the pointers in the vector, including the
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * final "*". As this is hashed by the preprocessor use
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * of space etc is important.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pfnCleanup cleanup function (void (*pfn)(void *)) that is called
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * directly on a vector element when that element is
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync vecInitPtr(pvec, sizeof(type), VECTOR_TOKEN_HASH(type), \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync (void (*)(void*)) pfnCleanup)
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * Clean up a vector.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pvec pointer to the vector to clean up. The clean up function
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * specified at initialisation (if any) is called for each element
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * in the vector. After clean up, the vector structure is invalid
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * until it is re-initialised
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * Clean up a vector-of-pointers.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pvec pointer to the vector to clean up. The clean up function
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * specified at initialisation (if any) is called for each element
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * in the vector. After clean up, the vector structure is invalid
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * until it is re-initialised
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * Reinitialises a vector structure to empty.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pvec pointer to the vector to re-initialise. The clean up function
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * specified at initialisation (if any) is called for each element
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * in the vector.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * Reinitialises a vector-of-pointers structure to empty.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pvec pointer to the vector to re-initialise. The clean up function
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * specified at initialisation (if any) is called for each element
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * in the vector.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * Adds an element to the back of a vector. The element will be byte-copied
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * and become owned by the vector, to be cleaned up by the vector's clean-up
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * routine when the element is dropped.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @returns iprt status code (VINF_SUCCESS or VERR_NO_MEMORY)
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @returns VERR_INVALID_PARAMETER if the type does not match the type given
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * when the vector was initialised (asserted)
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pvec pointer to the vector on to which the element should be
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param type the type of the vector as specified at initialisation.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * Spacing etc is important.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pvElement void pointer to the element to be added
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * Adds a pointer to the back of a vector-of-pointers. The pointer will become
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * owned by the vector, to be cleaned up by the vector's clean-up routine when
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * it is dropped.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @returns iprt status code (VINF_SUCCESS or VERR_NO_MEMORY)
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @returns VERR_INVALID_PARAMETER if the type does not match the type given
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * when the vector was initialised (asserted)
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pvec pointer to the vector on to which the element should be
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param type the type of the vector as specified at initialisation.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * Spacing etc is important.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pvElement the pointer to be added, typecast to pointer-to-void
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * Returns the count of elements in a vector.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pvec pointer to the vector.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * Returns the count of elements in a vector-of-pointers.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pvec pointer to the vector.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * Iterates over the vector elements from first to last and execute the
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * following instruction or block on each iteration with @a pIterator set to
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * point to the current element (that is, a pointer to the pointer element for
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * a vector-of-pointers). Use in the same way as a "for" statement.
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pvec pointer to the vector to be iterated over
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param type the type of the vector, must match the type specified at
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * vector initialisation (including whitespace etc)
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @todo can we assert the correctness of the type in some way?
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * @param pIterator a pointer to @a type which will be set to point to the
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync * current vector element on each iteration
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync && pIterator < (type *) (pvec)->mpvaElements + (pvec)->mcElements; \
9b509d9e7070174b3bd5c80ce9ea52d42dd3de98vboxsync#endif /* MAIN_VECTOR_H */