/** @file
* IPRT - Generic List Class.
*/
/*
* Copyright (C) 2011-2013 Oracle Corporation
*
* This file is part of VirtualBox Open Source Edition (OSE), as
* available from http://www.virtualbox.org. This file is free software;
* 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.
*/
#ifndef ___iprt_cpp_list_h
#define ___iprt_cpp_list_h
#include <new> /* For std::bad_alloc */
/** @defgroup grp_rt_cpp_list C++ List support
* @ingroup grp_rt_cpp
*
* @brief Generic C++ list class support.
*
* This list classes manage any amount of data in a fast and easy to use way.
* They have no dependencies on STL, only on generic memory management methods
* of IRPT. This allows list handling in situations where the use of STL
* container classes is forbidden.
*
* Not all of the functionality of STL container classes is implemented. There
* std::algorithms).
*
* The implementation is array based which allows fast access to the items.
* Appending items is usually also fast, cause the internal array is
* preallocated. To minimize the memory overhead, native types (that is
* everything smaller then the size of void*) are directly saved in the array.
* If bigger types are used (e.g. RTCString) the internal array is an array of
* pointers to the objects.
*
* The size of the internal array will usually not shrink, but grow
* automatically. Only certain methods, like RTCList::clear or the "=" operator
* will reset any previously allocated memory. You can call
* RTCList::setCapacity for manual adjustment. If the size of an new list will
* be known, calling the constructor with the necessary capacity will speed up
* the insertion of the new items.
*
* For the full public interface these list classes offer see RTCListBase.
*
* There are some requirements for the types used which follow:
* -# They need a default and a copy constructor.
* -# Some methods (e.g. RTCList::contains) need an equal operator.
* -# If the type is some complex class (that is, having a constructor which
* allocates members on the heap) it has to be greater than sizeof(void*) to
* be used correctly. If this is not the case you can manually overwrite the
* list behavior. Just add T* as a second parameter to the list template if
* your class is called T. Another possibility is to specialize the list for
* your target class. See below for more information.
*
* The native types like int, bool, ptr, ..., are meeting this criteria, so
* they are save to use.
*
* Please note that the return type of some of the getter methods are slightly
* different depending on the list type. Native types return the item by value,
* items with a size greater than sizeof(void*) by reference. As native types
* saved directly in the internal array, returning a reference to them (and
* saving them in a reference as well) would make them invalid (or pointing to
* a wrong item) when the list is changed in the meanwhile. Returning a
* reference for bigger types isn't problematic and makes sure we get out the
* best speed of the list. The one exception to this rule is the index
* operator[]. This operator always return a reference to make it possible to
* use it as a lvalue. Its your responsibility to make sure the list isn't
* changed when using the value as reference returned by this operator.
*
* The list class is reentrant. For a thread-safe variant see RTCMTList.
*
* Implementation details:
* It is possible to specialize any type. This might be necessary to get the
* best speed out of the list. Examples are the 64-bit types, which use the
* native (no pointers) implementation even on a 32-bit host. Consult the
* source code for more details.
*
* Current specialized implementations:
* - int64_t: RTCList<int64_t>
* - uint64_t: RTCList<uint64_t>
*
* @{
*/
/**
* The guard definition.
*/
template <bool G>
/**
* The default guard which does nothing.
*/
template <>
{
inline void enterRead() const {}
inline void leaveRead() const {}
inline void enterWrite() {}
inline void leaveWrite() {}
/* Define our own new and delete. */
};
/**
* General helper template for managing native values in RTCListBase.
*/
{
{
while (i-- > 0)
if (p[i] == v)
return i;
return cElements;
}
{
if (cSize > 0)
}
static inline void eraseRange(T2 * /* p */, size_t /* cFrom */, size_t /* cSize */) { /* Nothing to do here. */ }
};
/**
* Specialized helper template for managing pointer values in RTCListBase.
*/
{
{
while (i-- > 0)
if (*p[i] == v)
return i;
return cElements;
}
{
}
{
while (cItems-- > 0)
}
};
/**
* This is the base class for all other list classes. It implements the
* necessary list functionality in a type independent way and offers the public
* list interface to the user.
*/
{
/** @name Traits.
*
* Defines the return type of most of the getter methods. If the internal
* used type is a pointer, we return a reference. If not we return by
* value.
*
* @{
*/
/** @} */
/**
* Creates a new list.
*
* This preallocates @a cCapacity elements within the list.
*
* @param cCapacitiy The initial capacity the list has.
* @throws std::bad_alloc
*/
: m_pArray(0)
, m_cElements(0)
, m_cCapacity(0)
{
if (cCapacity > 0)
}
/**
* Creates a copy of another list.
*
* The other list will be fully copied and the capacity will be the same as
* the size of the other list.
*
* @param other The list to copy.
* @throws std::bad_alloc
*/
: m_pArray(0)
, m_cElements(0)
, m_cCapacity(0)
{
}
/**
* Destructor.
*/
~RTCListBase()
{
if (m_pArray)
{
}
m_cElements = m_cCapacity = 0;
}
/**
* Sets a new capacity within the list.
*
* If the new capacity is bigger than the old size, it will be simply
* preallocated more space for the new items. If the new capacity is
* smaller than the previous size, items at the end of the list will be
* deleted.
*
* @param cCapacity The new capacity within the list.
* @throws std::bad_alloc
*/
{
}
/**
* Return the current capacity of the list.
*
* @return The actual capacity.
*/
{
return cRet;
}
/**
* Check if an list contains any items.
*
* @return True if there is more than zero items, false otherwise.
*/
bool isEmpty() const
{
return fEmpty;
}
/**
* Return the current count of elements within the list.
*
* @return The current element count.
*/
{
return cRet;
}
/**
* Inserts an item to the list at position @a i.
*
* @param i The position of the new item. The must be within or at the
* exact end of the list. Indexes specified beyond the end of
* the list will be changed to an append() operation and strict
* builds will raise an assert.
* @param val The new item.
* @return a reference to this list.
* @throws std::bad_alloc
*/
{
if (m_cElements == m_cCapacity)
++m_cElements;
return *this;
}
/**
* Inserts a list to the list at position @a i.
*
* @param i The position of the new item. The must be within or at the
* exact end of the list. Indexes specified beyond the end of
* the list will be changed to an append() operation and strict
* builds will raise an assert.
* @param other The other list. This MUST not be the same as the destination
* list, will assert and return without doing anything if this
* happens.
* @return a reference to this list.
* @throws std::bad_alloc
*/
{
if (RT_LIKELY(cElementsOther > 0))
{
if (i < m_cElements)
}
return *this;
}
/**
* Prepend an item to the list.
*
* @param val The new item.
* @return a reference to this list.
* @throws std::bad_alloc
*/
{
}
/**
* Prepend a list of type T to the list.
*
* @param other The list to prepend.
* @return a reference to this list.
* @throws std::bad_alloc
*/
{
}
/**
* Append an item to the list.
*
* @param val The new item.
* @return a reference to this list.
* @throws std::bad_alloc
*/
{
if (m_cElements == m_cCapacity)
++m_cElements;
return *this;
}
/**
* Append a list of type T to the list.
*
* @param other The list to append. Must not be the same as the destination
* list, will assert and return without doing anything.
* @return a reference to this list.
* @throws std::bad_alloc
*/
{
return *this;
}
/**
* Copy the items of the other list into this list.
*
* All previous items of this list are deleted.
*
* @param other The list to copy.
* @return a reference to this list.
*/
{
/* Prevent self assignment */
return *this;
/* Delete all items. */
/* Need we to realloc memory. */
/* Copy new items. */
return *this;
}
/**
* Replace an item in the list.
*
* @param i The position of the item to replace. If this is out of range,
* the request will be ignored, strict builds will assert.
* @param val The new value.
* @return a reference to this list.
*/
{
if (i < m_cElements)
{
}
else
return *this;
}
/**
* Return the first item as constant object.
*
* @return A reference or pointer to the first item.
*
* @note No boundary checks are done. Make sure there is at least one
* element.
*/
{
Assert(m_cElements > 0);
return res;
}
/**
* Return the first item.
*
* @return A reference or pointer to the first item.
*
* @note No boundary checks are done. Make sure there is at least one
* element.
*/
{
Assert(m_cElements > 0);
return res;
}
/**
* Return the last item as constant object.
*
* @return A reference or pointer to the last item.
*
* @note No boundary checks are done. Make sure there is at least one
* element.
*/
{
Assert(m_cElements > 0);
return res;
}
/**
* Return the last item.
*
* @return A reference or pointer to the last item.
*
* @note No boundary checks are done. Make sure there is at least one
* element.
*/
{
Assert(m_cElements > 0);
return res;
}
/**
* Return the item at position @a i as constant object.
*
* @param i The position of the item to return. This better not be out of
* bounds, however should it be the last element of the array
* will be return and strict builds will raise an assertion.
* Should the array be empty, a crash is very likely.
* @return The item at position @a i.
*/
{
return res;
}
/**
* Return the item at position @a i.
*
* @param i The position of the item to return. This better not be out of
* bounds, however should it be the last element of the array
* will be return and strict builds will raise an assertion.
* Should the array be empty, a crash is very likely.
* @return The item at position @a i.
*/
{
return res;
}
/**
* Return the item at position @a i as mutable reference.
*
* @param i The position of the item to return. This better not be out of
* bounds, however should it be the last element of the array
* will be return and strict builds will raise an assertion.
* Should the array be empty, a crash is very likely.
* @return The item at position @a i.
*/
{
return res;
}
/**
* Return the item at position @a i or default value if out of range.
*
* @param i The position of the item to return.
* @return The item at position @a i or default value.
*/
{
if (RT_UNLIKELY(i >= m_cElements))
{
return T();
}
return res;
}
/**
* Return the item at position @a i, or @a defaultVal if out of range.
*
* @param i The position of the item to return.
* @param defaultVal The value to return in case @a i is invalid.
* @return The item at position @a i or @a defaultVal.
*/
{
if (RT_UNLIKELY(i >= m_cElements))
{
return defaultVal;
}
return res;
}
/**
* Check if @a val is contained in the array.
*
* @param val The value to check for.
* @return true if it is found, false otherwise.
*/
{
return fRc;
}
/**
* Remove the first item.
*
* @note You should make sure the list isn't empty. Strict builds will assert.
* The other builds will quietly ignore the request.
*/
void removeFirst()
{
removeAt(0);
}
/**
* Remove the last item.
*
* @note You should make sure the list isn't empty. Strict builds will assert.
* The other builds will quietly ignore the request.
*/
void removeLast()
{
}
/**
* Remove the item at position @a i.
*
* @param i The position of the item to remove. Out of bounds values will
* be ignored and an assertion will be raised in strict builds.
*/
{
removeAtLocked(i);
}
/**
* Remove a range of items from the list.
*
* @param iStart The start position of the items to remove.
* @param iEnd The end position of the items to remove (excluded).
*/
{
AssertMsgStmt(iEnd <= m_cElements, ("iEnd=%zu m_cElements=%zu\n", iEnd, m_cElements), iEnd = m_cElements);
AssertMsgStmt(iStart < m_cElements, ("iStart=%zu m_cElements=%zu\n", iStart, m_cElements), iStart = m_cElements);
if (cElements > 0)
{
if (m_cElements > iEnd)
m_cElements -= cElements;
}
}
/**
* Delete all items in the list.
*/
void clear()
{
/* Values cleanup */
if (m_cElements != kDefaultCapacity)
m_cElements = 0;
}
/**
* Return the raw array.
*
* For native types this is a pointer to continuous memory of the items. For
* pointer types this is a continuous memory of pointers to the items.
*
* @warning If you change anything in the underlaying list, this memory
* will very likely become invalid. So take care when using this
* method and better try to avoid using it.
*
* @returns the raw memory.
*/
{
return pRet;
}
{
}
/* Define our own new and delete. */
/**
* The default capacity of the list. This is also used as grow factor.
*/
static const size_t kDefaultCapacity;
/**
* Generic resizes the array, surplus elements are erased.
*
* @param cElementsNew The new array size.
* @throws std::bad_alloc.
*/
{
/* Same size? */
if (cElementsNew == m_cCapacity)
return;
/* If we get smaller we have to delete some of the objects at the end
of the list. */
if ( cElementsNew < m_cElements
&& m_pArray)
}
/**
* Resizes the array without doing the erase() thing on surplus elements.
*
* @param cElementsNew The new array size.
* @throws std::bad_alloc.
*/
{
/* Same size? */
if (cElementsNew == m_cCapacity)
return;
/* Resize the array. */
if (cElementsNew > 0)
{
if (!pvNew)
{
#ifdef RT_EXCEPTIONS_ENABLED
#endif
return;
}
}
/* If we get zero we delete the array it self. */
else if (m_pArray)
{
}
if (m_cElements > cElementsNew)
}
/**
* Special realloc method which require that the array will grow.
*
* @param cElementsNew The new array size.
* @throws std::bad_alloc.
* @note No boundary checks are done!
*/
{
if (pvNew)
{
}
else
{
#ifdef RT_EXCEPTIONS_ENABLED
#endif
}
}
/**
* Remove the item at position @a i.
*
* @param i The position of the item to remove. Out of bounds values will
* be ignored and an assertion will be raised in strict builds.
* @remarks
*/
void removeAtLocked(size_t i)
{
if (i < m_cElements - 1)
--m_cElements;
}
/** The internal list array. */
/** The current count of items in use. */
/** The current capacity of the internal array. */
/** The guard used to serialize the access to the items. */
};
/**
* Template class which automatically determines the type of list to use.
*
* @see RTCListBase
*/
{
/* Traits */
/**
* Creates a new list.
*
* This preallocates @a cCapacity elements within the list.
*
* @param cCapacitiy The initial capacity the list has.
* @throws std::bad_alloc
*/
/* Define our own new and delete. */
};
/**
* Specialized class for using the native type list for unsigned 64-bit
* values even on a 32-bit host.
*
* @see RTCListBase
*/
template <>
{
/* Traits */
/**
* Creates a new list.
*
* This preallocates @a cCapacity elements within the list.
*
* @param cCapacitiy The initial capacity the list has.
* @throws std::bad_alloc
*/
/* Define our own new and delete. */
};
/**
* Specialized class for using the native type list for signed 64-bit
* values even on a 32-bit host.
*
* @see RTCListBase
*/
template <>
{
/* Traits */
/**
* Creates a new list.
*
* This preallocates @a cCapacity elements within the list.
*
* @param cCapacitiy The initial capacity the list has.
* @throws std::bad_alloc
*/
/* Define our own new and delete. */
};
/** @} */
#endif /* !___iprt_cpp_list_h */