list.h revision 4520ec42b031779169b52cb9536f22937fd9bf97
/** @file
* IPRT - Generic List Class.
*/
/*
* 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;
* 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.
* -# 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() {}
};
/**
* General helper template for managing native values in RTCListBase.
*/
{
{
size_t i = 0;
while(i < cSize)
{
if (p[i] == v)
break;
++i;
}
return i;
}
{
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.
*/
{
{
size_t i = 0;
while(i < cSize)
{
if (*p[i] == v)
break;
++i;
}
return i;
}
{
}
{
delete p[i];
}
};
/**
* 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.
*/
{
/**
* 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_cSize(0)
, m_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 if the other list.
*
* @param other The list to copy.
* @throws std::bad_alloc
*/
: m_pArray(0)
, m_cSize(0)
, m_cCapacity(0)
{
}
/**
* Destructor.
*/
~RTCListBase()
{
if (m_pArray)
}
/**
* 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.
*/
/**
* Check if an list contains any items.
*
* @return True if there is more than zero items, false otherwise.
*/
/**
* Return the current count of elements within the list.
*
* @return The current element count.
*/
/**
* Inserts an item to the list at position @a i.
*
* @param i The position of the new item.
* @param val The new item.
* @return a reference to this list.
* @throws std::bad_alloc
*/
{
if (m_cSize == m_cCapacity)
++m_cSize;
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
*/
{
return *this;
}
/**
* Append an item to the list.
*
* @param val The new item.
* @return a reference to this list.
* @throws std::bad_alloc
*/
{
if (m_cSize == m_cCapacity)
++m_cSize;
return *this;
}
/**
* Append a list of type T to the list.
*
* @param other The list to append.
* @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;
/* Values cleanup */
/* Copy */
return *this;
}
/**
* Replace an item in the list.
*
* @note No boundary checks are done. Make sure @a i is equal or greater zero
* and smaller than RTCList::size.
*
* @param i The position of the item to replace.
* @param val The new value.
* @return a reference to this list.
*/
{
return *this;
}
/**
* Return the first item as constant object.
*
* @note No boundary checks are done. Make sure @a i is equal or greater zero
* and smaller than RTCList::size.
*
* @return The first item.
*/
GET_CRTYPE first() const
{
return res;
}
/**
* Return the first item.
*
* @note No boundary checks are done. Make sure @a i is equal or greater zero
* and smaller than RTCList::size.
*
* @return The first item.
*/
{
return res;
}
/**
* Return the last item as constant object.
*
* @note No boundary checks are done. Make sure @a i is equal or greater zero
* and smaller than RTCList::size.
*
* @return The last item.
*/
GET_CRTYPE last() const
{
return res;
}
/**
* Return the last item.
*
* @note No boundary checks are done. Make sure @a i is equal or greater zero
* and smaller than RTCList::size.
*
* @return The last item.
*/
{
return res;
}
/**
* Return the item at position @a i as constant object.
*
* @note No boundary checks are done. Make sure @a i is equal or greater zero
* and smaller than RTCList::size.
*
* @param i The position of the item to return.
* @return The item at position @a i.
*/
{
return res;
}
/**
* Return the item at position @a i.
*
* @note No boundary checks are done. Make sure @a i is equal or greater zero
* and smaller than RTCList::size.
*
* @param i The position of the item to return.
* @return The item at position @a i.
*/
{
return res;
}
/**
* Return the item at position @a i as mutable reference.
*
* @note No boundary checks are done. Make sure @a i is equal or greater zero
* and smaller than RTCList::size.
*
* @param i The position of the item to return.
* @return The item at position @a i.
*/
{
return res;
}
/**
* Return the item at position @a i. If @a i isn't valid within the list a
* default value is returned.
*
* @param i The position of the item to return.
* @return The item at position @a i.
*/
{
if (i >= m_cSize)
{
return T();
}
return res;
}
/**
* Return the item at position @a i. If @a i isn't valid within the list
* @a defaultVal is returned.
*
* @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.
*/
{
if (i >= m_cSize)
{
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 res;
}
/**
* Remove the first item.
*
* @note No boundary checks are done. Make sure @a i is equal or greater zero
* and smaller than RTCList::size.
*/
void removeFirst()
{
removeAt(0);
}
/**
* Remove the last item.
*
* @note No boundary checks are done. Make sure @a i is equal or greater zero
* and smaller than RTCList::size.
*/
void removeLast()
{
}
/**
* Remove the item at position @a i.
*
* @note No boundary checks are done. Make sure @a i is equal or greater zero
* and smaller than RTCList::size.
*
* @param i The position of the item to remove.
*/
{
/* Not last element? */
if (i < m_cSize - 1)
--m_cSize;
}
/**
* Remove a range of items from the list.
*
* @note No boundary checks are done. Make sure @a iFrom is equal or
* greater zero and smaller than RTCList::size. @a iTo has to be
* greater than @a iFrom and equal or smaller than RTCList::size.
*
* @param iFrom The start position of the items to remove.
* @param iTo The end position of the items to remove (excluded).
*/
{
/* Not last elements? */
}
/**
* Delete all items in the list.
*/
void clear()
{
/* Values cleanup */
if (m_cSize != DefaultCapacity)
m_cSize = 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 res;
}
/**
* The default capacity of the list. This is also used as grow factor.
*/
static const size_t DefaultCapacity;
/**
* Generic realloc, which does some kind of boundary checking.
*/
{
/* Same size? */
if (cNewSize == m_cCapacity)
return;
/* If we get smaller we have to delete some of the objects at the end
of the list. */
&& m_pArray)
{
}
/* If we get zero we delete the array it self. */
if ( cNewSize == 0
&& m_pArray)
{
m_pArray = 0;
}
/* Resize the array. */
if (cNewSize > 0)
{
if (!m_pArray)
{
/** @todo you leak memory. */
m_cCapacity = 0;
m_cSize = 0;
#ifdef RT_EXCEPTIONS_ENABLED
#endif
}
}
}
/**
* Special realloc method which require that the array will grow.
*
* @note No boundary checks are done!
*/
{
/* Resize the array. */
if (!m_pArray)
{
/** @todo you leak memory. */
m_cCapacity = 0;
m_cSize = 0;
#ifdef RT_EXCEPTIONS_ENABLED
#endif
}
}
/** 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
*/
{
};
/**
* Specialized class for using the native type list for unsigned 64-bit
* values even on a 32-bit host.
*
* @see RTCListBase
*/
template <>
{
};
/**
* Specialized class for using the native type list for signed 64-bit
* values even on a 32-bit host.
*
* @see RTCListBase
*/
template <>
{
};
/** @} */
#endif /* !___iprt_cpp_list_h */