vector.h revision 5e768213e353675f7bb7deda92733ee25f27a20e
5b281ba489ca18f0380d7efc7a5108b606cce449vboxsync * STL-like vector implementation in C
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * @note functions in this file are inline to prevent warnings about
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * unused static functions. I assume that in this day and age a
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * compiler makes its own decisions about whether to actually
1c94c0a63ba68be1a7b2c640e70d7a06464e4fcavboxsync * inline a function.
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * Copyright (C) 2008-2010 Oracle Corporation
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * available from http://www.virtualbox.org. This file is free software;
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * you can redistribute it and/or modify it under the terms of the GNU
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * General Public License (GPL) as published by the Free Software
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * The contents of this file may alternatively be used under the terms
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * of the Common Development and Distribution License Version 1.0
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * VirtualBox OSE distribution, in which case the provisions of the
1c94c0a63ba68be1a7b2c640e70d7a06464e4fcavboxsync * CDDL are applicable instead of those of the GPL.
1c94c0a63ba68be1a7b2c640e70d7a06464e4fcavboxsync * You may elect to license modified versions of this file under the
1c94c0a63ba68be1a7b2c640e70d7a06464e4fcavboxsync * terms and conditions of either the GPL or the CDDL or both.
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync#define VECTOR_CONCAT(a, b) a ## b
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync/** A publicly visible (method, type, etc) name relating to the vector type */
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync#define VECTOR_PUBLIC(NAME) VECTOR_XCONCAT(VECTOR_TYPENAME, _ ## NAME)
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync/** An implementation-private (method, type, etc) name */
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync#define VECTOR_INTERNAL(NAME) VECTOR_XCONCAT(VECTOR_TYPENAME, _internal_ ## NAME)
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync/** The size of a vector element */
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync/** The unit by which the vector capacity is increased */
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync/** VECTOR_TYPE must be defined to the type that the vector will contain. The
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * macro will be undef-ed again by this header. */
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync# error You must define VECTOR_TYPE before including this header!
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync/** VECTOR_TYPENAME must be defined to the typename for the vector. The
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * macro will be undef-ed again by this header. */
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync# error You must define VECTOR_TYPENAME before including this header!
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync/** VECTOR_ALLOCATOR can be defined to an alternative allocator for the
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * vector's memory. The allocator must be a function with realloc semantics.
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * The macro will be undef-ed again by this header. */
1df297ea8319f3f3afddb73e6ea2fd9c7f0e5eb4vboxsync/** VECTOR_DESTRUCTOR can be defined to be a routine to clean up vector
3fd65c821ad93f378baf8c75b30dcb6a17a5dd77vboxsync * elements before they are freed. It must return void and take a pointer to
5c1381fc884d30a749517579368ff6cb4b43e809vboxsync * an element as a parameter. The macro will be undef-ed again by this header.
5c1381fc884d30a749517579368ff6cb4b43e809vboxsync# define VECTOR_DESTRUCTOR VECTOR_INTERNAL(empty_destructor)
3fd65c821ad93f378baf8c75b30dcb6a17a5dd77vboxsync/** Structure describing the vector itself */
1df297ea8319f3f3afddb73e6ea2fd9c7f0e5eb4vboxsync /** The beginning of the allocated memory */
3fd65c821ad93f378baf8c75b30dcb6a17a5dd77vboxsync /** Pointer to just after the end of the last element */
3fd65c821ad93f378baf8c75b30dcb6a17a5dd77vboxsync /** Pointer to just after the end of the allocated memory */
3fd65c821ad93f378baf8c75b30dcb6a17a5dd77vboxsync/*** Private methods ***/
3fd65c821ad93f378baf8c75b30dcb6a17a5dd77vboxsync/** Destructor that does nothing. */
3fd65c821ad93f378baf8c75b30dcb6a17a5dd77vboxsyncstatic inline void VECTOR_INTERNAL(empty_destructor)(VECTOR_TYPENAME *pSelf)
3fd65c821ad93f378baf8c75b30dcb6a17a5dd77vboxsync/** Expand an existing vector */
3fd65c821ad93f378baf8c75b30dcb6a17a5dd77vboxsyncstatic inline int VECTOR_INTERNAL(expand)(VECTOR_TYPENAME *pSelf)
2a560b28131ee7efa5b73a9e9cbfdb08eae28624vboxsync size_t cNewCap = pSelf->mCapacity - pSelf->mBegin + VECTOR_ALLOC_UNIT;
5e5603ae40c7a0a884fe91e269b7d6d6c0ba56f5vboxsync void *pRealloc = VECTOR_ALLOCATOR(pSelf->mBegin, cNewCap);
5e5603ae40c7a0a884fe91e269b7d6d6c0ba56f5vboxsync pSelf->mCapacity = pSelf->mBegin + cNewCap / VECTOR_ELEMENT_SIZE;
2a560b28131ee7efa5b73a9e9cbfdb08eae28624vboxsync memset(pSelf->mEnd, 0, pSelf->mCapacity - pSelf->mEnd);
ab7139411cba3600213877c953b69fc11a7ef0cfvboxsync/** Expand an existing vector */
ab7139411cba3600213877c953b69fc11a7ef0cfvboxsyncstatic inline void VECTOR_INTERNAL(destruct_all)(VECTOR_TYPENAME *pSelf)
ab7139411cba3600213877c953b69fc11a7ef0cfvboxsync for (pIter = pSelf->mBegin; pIter < pSelf->mEnd; ++pIter)
ab7139411cba3600213877c953b69fc11a7ef0cfvboxsync/*** Public methods ***/
ab7139411cba3600213877c953b69fc11a7ef0cfvboxsync/** Initialise a newly allocated vector. The vector will be zeroed on failure.
ab7139411cba3600213877c953b69fc11a7ef0cfvboxsyncstatic inline int VECTOR_PUBLIC(init)(VECTOR_TYPENAME *pSelf)
3c1c973ceaac2fdf7f3b0305f57ae30531acb9ccvboxsync/** Clean up a vector so that the memory can be returned. For convenience,
ab7139411cba3600213877c953b69fc11a7ef0cfvboxsync * this may be used safely on a zeroed vector structure. */
ab7139411cba3600213877c953b69fc11a7ef0cfvboxsyncstatic inline void VECTOR_PUBLIC(cleanup)(VECTOR_TYPENAME *pSelf)
2a560b28131ee7efa5b73a9e9cbfdb08eae28624vboxsync pSelf->mBegin = pSelf->mEnd = pSelf->mCapacity = NULL;
2a560b28131ee7efa5b73a9e9cbfdb08eae28624vboxsync/** Add a value onto the end of a vector */
2a560b28131ee7efa5b73a9e9cbfdb08eae28624vboxsyncstatic inline int VECTOR_PUBLIC(push_back)(VECTOR_TYPENAME *pSelf,
2a560b28131ee7efa5b73a9e9cbfdb08eae28624vboxsync if (pSelf->mEnd == pSelf->mCapacity && !VECTOR_INTERNAL(expand)(pSelf))
5a7d67754026bd3654a2464799f0db1790ecf183vboxsync/** Reset the vector */
1df297ea8319f3f3afddb73e6ea2fd9c7f0e5eb4vboxsyncstatic inline void VECTOR_PUBLIC(clear)(VECTOR_TYPENAME *pSelf)
1df297ea8319f3f3afddb73e6ea2fd9c7f0e5eb4vboxsync memset(pSelf->mBegin, 0, pSelf->mEnd - pSelf->mBegin);
5a7d67754026bd3654a2464799f0db1790ecf183vboxsync/** Number of elements in the vector */
5a7d67754026bd3654a2464799f0db1790ecf183vboxsyncstatic inline size_t VECTOR_PUBLIC(size)(VECTOR_TYPENAME *pSelf)
5a7d67754026bd3654a2464799f0db1790ecf183vboxsync return (pSelf->mEnd - pSelf->mBegin) / VECTOR_ELEMENT_SIZE;
1df297ea8319f3f3afddb73e6ea2fd9c7f0e5eb4vboxsync/*** Iterators ***/
2c19fa7a35e93931f995c196426585b16f8bf2c0vboxsync/** Non-constant iterator over the vector */
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync/** Initialise a newly allocated iterator */
165b506f4c024dabd5a4caaeda31c66712d154eavboxsyncstatic inline void VECTOR_PUBLIC(iter_init)(VECTOR_PUBLIC(iterator) *pSelf,
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync/** Dereference an iterator */
e0dec59adb362e8486c0622785420ad10e720972vboxsyncstatic inline VECTOR_TYPE *VECTOR_PUBLIC(iter_target)(VECTOR_PUBLIC(iterator) *pSelf)
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync/** Increment an iterator */
2c19fa7a35e93931f995c196426585b16f8bf2c0vboxsyncstatic inline void VECTOR_PUBLIC(iter_incr)(VECTOR_PUBLIC(iterator) *pSelf)
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync/** Get the special "begin" iterator for a vector */
2c19fa7a35e93931f995c196426585b16f8bf2c0vboxsyncstatic inline const VECTOR_PUBLIC(iterator) *VECTOR_PUBLIC(begin)
e0dec59adb362e8486c0622785420ad10e720972vboxsync/** Get the special "end" iterator for a vector */
165b506f4c024dabd5a4caaeda31c66712d154eavboxsyncstatic inline const VECTOR_PUBLIC(iterator) *VECTOR_PUBLIC(end)
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync/** Test whether an iterator is less than another. */
2c19fa7a35e93931f995c196426585b16f8bf2c0vboxsyncstatic inline int VECTOR_PUBLIC(iter_lt)(const VECTOR_PUBLIC(iterator) *pFirst,
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync/** Test whether an iterator is equal to another. The special values
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * ITERATOR_BEGIN and ITERATOR_END are recognised. */
e0dec59adb362e8486c0622785420ad10e720972vboxsyncstatic inline int VECTOR_PUBLIC(iter_eq)(const VECTOR_PUBLIC(iterator) *pFirst,
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync/* We need to undefine anything we have defined (and for convenience we also
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * undefine our "parameter" macros) as this header may be included multiple
165b506f4c024dabd5a4caaeda31c66712d154eavboxsync * times in one source file with different parameters. */