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