diff options
Diffstat (limited to 'external/vpc/public/tier1/utlmultilist.h')
| -rw-r--r-- | external/vpc/public/tier1/utlmultilist.h | 769 |
1 files changed, 769 insertions, 0 deletions
diff --git a/external/vpc/public/tier1/utlmultilist.h b/external/vpc/public/tier1/utlmultilist.h new file mode 100644 index 0000000..68e2a98 --- /dev/null +++ b/external/vpc/public/tier1/utlmultilist.h @@ -0,0 +1,769 @@ +//========= Copyright � 1996-2005, Valve Corporation, All rights reserved. ============// +// +// Purpose: Multiple linked list container class +// +// $Revision: $ +// $NoKeywords: $ +//=============================================================================// + +#ifndef UTLMULTILIST_H +#define UTLMULTILIST_H + +#ifdef _WIN32 +#pragma once +#endif + +#include "utllinkedlist.h" + +// memdbgon must be the last include file in a .h file!!! +#include "tier0/memdbgon.h" + + +//----------------------------------------------------------------------------- +// class CUtlMultiList: +// description: +// A lovely index-based linked list! T is the class type, I is the index +// type, which usually should be an unsigned short or smaller. +// This list can contain multiple lists +//----------------------------------------------------------------------------- +template <class T, class I> +class CUtlMultiList +{ +protected: + // What the linked list element looks like + struct ListElem_t + { + T m_Element; + I m_Previous; + I m_Next; + }; + + struct List_t + { + I m_Head; + I m_Tail; + I m_Count; + }; + + typedef CUtlMemory<ListElem_t> M; // Keep naming similar to CUtlLinkedList +public: + typedef I ListHandle_t; + + // constructor, destructor + CUtlMultiList( int growSize = 0, int initSize = 0 ); + CUtlMultiList( void *pMemory, int memsize ); + ~CUtlMultiList( ); + + // gets particular elements + T& Element( I i ); + T const& Element( I i ) const; + T& operator[]( I i ); + T const& operator[]( I i ) const; + + // Make sure we have a particular amount of memory + void EnsureCapacity( int num ); + + // Memory deallocation + void Purge(); + + // List Creation/deletion + ListHandle_t CreateList(); + void DestroyList( ListHandle_t list ); + bool IsValidList( ListHandle_t list ) const; + + // Insertion methods (call default constructor).... + I InsertBefore( ListHandle_t list, I before ); + I InsertAfter( ListHandle_t list, I after ); + I AddToHead( ListHandle_t list ); + I AddToTail( ListHandle_t list ); + + // Insertion methods (call copy constructor).... + I InsertBefore( ListHandle_t list, I before, T const& src ); + I InsertAfter( ListHandle_t list, I after, T const& src ); + I AddToHead( ListHandle_t list, T const& src ); + I AddToTail( ListHandle_t list, T const& src ); + + // Removal methods + void Remove( ListHandle_t list, I elem ); + + // Removes all items in a single list + void RemoveAll( ListHandle_t list ); + + // Removes all items in all lists + void RemoveAll(); + + // Allocation/deallocation methods + // NOTE: To free, it must *not* be in a list! + I Alloc( ); + void Free( I elem ); + + // list modification + void LinkBefore( ListHandle_t list, I before, I elem ); + void LinkAfter( ListHandle_t list, I after, I elem ); + void Unlink( ListHandle_t list, I elem ); + void LinkToHead( ListHandle_t list, I elem ); + void LinkToTail( ListHandle_t list, I elem ); + + // invalid index + static I InvalidIndex() { return (I)~0; } + static bool IndexInRange( int index ); + static size_t ElementSize() { return sizeof(ListElem_t); } + + // list statistics + int Count( ListHandle_t list ) const; + int TotalCount( ) const; + I MaxElementIndex() const; + + // Traversing the list + I Head( ListHandle_t list ) const; + I Tail( ListHandle_t list ) const; + I Previous( I element ) const; + I Next( I element ) const; + + // Are nodes in a list or valid? + bool IsValidIndex( I i ) const; + bool IsInList( I i ) const; + +protected: + // constructs the class + void ConstructList( ); + + // Gets at the list element.... + ListElem_t& InternalElement( I i ) { return m_Memory[i]; } + ListElem_t const& InternalElement( I i ) const { return m_Memory[i]; } + + // A test for debug mode only... + bool IsElementInList( ListHandle_t list, I elem ) const; + + // copy constructors not allowed + CUtlMultiList( CUtlMultiList<T, I> const& list ) { Assert(0); } + + M m_Memory; + CUtlLinkedList<List_t, I> m_List; + I* m_pElementList; + + I m_FirstFree; + I m_TotalElements; + int m_MaxElementIndex; // The number allocated (use int so we can catch overflow) + + void ResetDbgInfo() + { + m_pElements = m_Memory.Base(); + +#ifdef _DEBUG + // Allocate space for the element list (which list is each element in) + if (m_Memory.NumAllocated() > 0) + { + if (!m_pElementList) + { + m_pElementList = (I*)malloc( m_Memory.NumAllocated() * sizeof(I) ); + } + else + { + m_pElementList = (I*)realloc( m_pElementList, m_Memory.NumAllocated() * sizeof(I) ); + } + } +#endif + } + + // For debugging purposes; + // it's in release builds so this can be used in libraries correctly + ListElem_t *m_pElements; +}; + + +//----------------------------------------------------------------------------- +// constructor, destructor +//----------------------------------------------------------------------------- + +template <class T, class I> +CUtlMultiList<T,I>::CUtlMultiList( int growSize, int initSize ) : + m_Memory(growSize, initSize), m_pElementList(0) +{ + ConstructList(); +} + +template <class T, class I> +CUtlMultiList<T,I>::CUtlMultiList( void* pMemory, int memsize ) : + m_Memory((ListElem_t *)pMemory, memsize/sizeof(ListElem_t)), m_pElementList(0) +{ + ConstructList(); +} + +template <class T, class I> +CUtlMultiList<T,I>::~CUtlMultiList( ) +{ + RemoveAll(); + if (m_pElementList) + free(m_pElementList); +} + +template <class T, class I> +void CUtlMultiList<T,I>::ConstructList( ) +{ + m_FirstFree = InvalidIndex(); + m_TotalElements = 0; + m_MaxElementIndex = 0; + ResetDbgInfo(); +} + + +//----------------------------------------------------------------------------- +// gets particular elements +//----------------------------------------------------------------------------- +template <class T, class I> +inline T& CUtlMultiList<T,I>::Element( I i ) +{ + return m_Memory[i].m_Element; +} + +template <class T, class I> +inline T const& CUtlMultiList<T,I>::Element( I i ) const +{ + return m_Memory[i].m_Element; +} + +template <class T, class I> +inline T& CUtlMultiList<T,I>::operator[]( I i ) +{ + return m_Memory[i].m_Element; +} + +template <class T, class I> +inline T const& CUtlMultiList<T,I>::operator[]( I i ) const +{ + return m_Memory[i].m_Element; +} + + +//----------------------------------------------------------------------------- +// list creation/destruction +//----------------------------------------------------------------------------- +template <class T, class I> +typename CUtlMultiList<T,I>::ListHandle_t CUtlMultiList<T,I>::CreateList() +{ + ListHandle_t l = m_List.AddToTail(); + m_List[l].m_Head = m_List[l].m_Tail = InvalidIndex(); + m_List[l].m_Count = 0; + return l; +} + +template <class T, class I> +void CUtlMultiList<T,I>::DestroyList( ListHandle_t list ) +{ + Assert( IsValidList(list) ); + RemoveAll( list ); + m_List.Remove(list); +} + +template <class T, class I> +bool CUtlMultiList<T,I>::IsValidList( ListHandle_t list ) const +{ + return m_List.IsValidIndex(list); +} + + +//----------------------------------------------------------------------------- +// list statistics +//----------------------------------------------------------------------------- +template <class T, class I> +inline int CUtlMultiList<T,I>::TotalCount() const +{ + return m_TotalElements; +} + +template <class T, class I> +inline int CUtlMultiList<T,I>::Count( ListHandle_t list ) const +{ + Assert( IsValidList(list) ); + return m_List[list].m_Count; +} + +template <class T, class I> +inline I CUtlMultiList<T,I>::MaxElementIndex() const +{ + return m_MaxElementIndex; +} + + +//----------------------------------------------------------------------------- +// Traversing the list +//----------------------------------------------------------------------------- +template <class T, class I> +inline I CUtlMultiList<T,I>::Head(ListHandle_t list) const +{ + Assert( IsValidList(list) ); + return m_List[list].m_Head; +} + +template <class T, class I> +inline I CUtlMultiList<T,I>::Tail(ListHandle_t list) const +{ + Assert( IsValidList(list) ); + return m_List[list].m_Tail; +} + +template <class T, class I> +inline I CUtlMultiList<T,I>::Previous( I i ) const +{ + Assert( IsValidIndex(i) ); + return InternalElement(i).m_Previous; +} + +template <class T, class I> +inline I CUtlMultiList<T,I>::Next( I i ) const +{ + Assert( IsValidIndex(i) ); + return InternalElement(i).m_Next; +} + + +//----------------------------------------------------------------------------- +// Are nodes in the list or valid? +//----------------------------------------------------------------------------- + +template <class T, class I> +inline bool CUtlMultiList<T,I>::IndexInRange( int index ) // Static method +{ + // Since I is not necessarily the type returned by M (int), we need to check that M returns + // indices which are representable by I. A common case is 'I === unsigned short', in which case + // case CUtlMemory will have 'InvalidIndex == (int)-1' (which casts to 65535 in I), and will + // happily return elements at index 65535 and above. + + // Do a couple of static checks here: the invalid index should be (I)~0 given how we use m_MaxElementIndex, + // and 'I' should be unsigned (to avoid signed arithmetic errors for plausibly exhaustible ranges). + COMPILE_TIME_ASSERT( (I)M::INVALID_INDEX == (I)~0 ); + COMPILE_TIME_ASSERT( ( sizeof(I) > 2 ) || ( ( (I)-1 ) > 0 ) ); + + return ( ( (I)index == index ) && ( (I)index != InvalidIndex() ) ); +} + +template <class T, class I> +inline bool CUtlMultiList<T,I>::IsValidIndex( I i ) const +{ + // GCC warns if I is an unsigned type and we do a ">= 0" against it (since the comparison is always 0). + // We get the warning even if we cast inside the expression. It only goes away if we assign to another variable. + long x = i; + + return (i < m_MaxElementIndex) && (x >= 0) && + ((m_Memory[i].m_Previous != i) || (m_Memory[i].m_Next == i)); +} + +template <class T, class I> +inline bool CUtlMultiList<T,I>::IsInList( I i ) const +{ + // GCC warns if I is an unsigned type and we do a ">= 0" against it (since the comparison is always 0). + // We get the warning even if we cast inside the expression. It only goes away if we assign to another variable. + long x = i; + return (i < m_MaxElementIndex) && (x >= 0) && (Previous(i) != i); +} + + +//----------------------------------------------------------------------------- +// Makes sure we have enough memory allocated to store a requested # of elements +//----------------------------------------------------------------------------- +template< class T, class I > +void CUtlMultiList<T, I>::EnsureCapacity( int num ) +{ + m_Memory.EnsureCapacity(num); + ResetDbgInfo(); +} + + +//----------------------------------------------------------------------------- +// Deallocate memory +//----------------------------------------------------------------------------- +template <class T, class I> +void CUtlMultiList<T,I>::Purge() +{ + RemoveAll(); + m_List.Purge(); + m_Memory.Purge( ); + m_List.Purge(); + m_FirstFree = InvalidIndex(); + m_TotalElements = 0; + m_MaxElementIndex = 0; + ResetDbgInfo(); +} + + +//----------------------------------------------------------------------------- +// Node allocation/deallocation +//----------------------------------------------------------------------------- +template <class T, class I> +I CUtlMultiList<T,I>::Alloc( ) +{ + I elem; + if (m_FirstFree == InvalidIndex()) + { + // We can overflow before the utlmemory overflows, since we have have I != int + if ( !IndexInRange( m_MaxElementIndex ) ) + { + ExecuteNTimes( 10, Warning( "CUtlMultiList overflow! (exhausted index range)\n" ) ); + return InvalidIndex(); + } + + // Nothing in the free list; add. + // Since nothing is in the free list, m_TotalElements == total # of elements + // the list knows about. + if (m_MaxElementIndex == m_Memory.NumAllocated()) + { + m_Memory.Grow(); + ResetDbgInfo(); + + if ( m_MaxElementIndex >= m_Memory.NumAllocated() ) + { + ExecuteNTimes( 10, Warning( "CUtlMultiList overflow! (exhausted memory allocator)\n" ) ); + return InvalidIndex(); + } + } + + elem = (I)m_MaxElementIndex; + ++m_MaxElementIndex; + } + else + { + elem = m_FirstFree; + m_FirstFree = InternalElement(m_FirstFree).m_Next; + } + + // Mark the element as not being in a list + InternalElement(elem).m_Next = InternalElement(elem).m_Previous = elem; + + ++m_TotalElements; + + Construct( &Element(elem) ); + + return elem; +} + +template <class T, class I> +void CUtlMultiList<T,I>::Free( I elem ) +{ + Assert( IsValidIndex(elem) && !IsInList(elem) ); + Destruct( &Element(elem) ); + InternalElement(elem).m_Next = m_FirstFree; + m_FirstFree = elem; + --m_TotalElements; +} + + +//----------------------------------------------------------------------------- +// A test for debug mode only... +//----------------------------------------------------------------------------- +template <class T, class I> +inline bool CUtlMultiList<T,I>::IsElementInList( ListHandle_t list, I elem ) const +{ + if (!m_pElementList) + return true; + + return m_pElementList[elem] == list; +} + + +//----------------------------------------------------------------------------- +// list modification +//----------------------------------------------------------------------------- +template <class T, class I> +void CUtlMultiList<T,I>::LinkBefore( ListHandle_t list, I before, I elem ) +{ + Assert( IsValidIndex(elem) && IsValidList(list) ); + + // Unlink it if it's in the list at the moment + Unlink(list, elem); + + ListElem_t& newElem = InternalElement(elem); + + // The element *after* our newly linked one is the one we linked before. + newElem.m_Next = before; + + if (before == InvalidIndex()) + { + // In this case, we're linking to the end of the list, so reset the tail + newElem.m_Previous = m_List[list].m_Tail; + m_List[list].m_Tail = elem; + } + else + { + // Here, we're not linking to the end. Set the prev pointer to point to + // the element we're linking. + Assert( IsInList(before) ); + ListElem_t& beforeElem = InternalElement(before); + newElem.m_Previous = beforeElem.m_Previous; + beforeElem.m_Previous = elem; + } + + // Reset the head if we linked to the head of the list + if (newElem.m_Previous == InvalidIndex()) + m_List[list].m_Head = elem; + else + InternalElement(newElem.m_Previous).m_Next = elem; + + // one more element baby + ++m_List[list].m_Count; + + // Store the element into the list + if (m_pElementList) + m_pElementList[elem] = list; +} + +template <class T, class I> +void CUtlMultiList<T,I>::LinkAfter( ListHandle_t list, I after, I elem ) +{ + Assert( IsValidIndex(elem) ); + + // Unlink it if it's in the list at the moment + Unlink(list, elem); + + ListElem_t& newElem = InternalElement(elem); + + // The element *before* our newly linked one is the one we linked after + newElem.m_Previous = after; + if (after == InvalidIndex()) + { + // In this case, we're linking to the head of the list, reset the head + newElem.m_Next = m_List[list].m_Head; + m_List[list].m_Head = elem; + } + else + { + // Here, we're not linking to the end. Set the next pointer to point to + // the element we're linking. + Assert( IsInList(after) ); + ListElem_t& afterElem = InternalElement(after); + newElem.m_Next = afterElem.m_Next; + afterElem.m_Next = elem; + } + + // Reset the tail if we linked to the tail of the list + if (newElem.m_Next == InvalidIndex()) + m_List[list].m_Tail = elem; + else + InternalElement(newElem.m_Next).m_Previous = elem; + + // one more element baby + ++m_List[list].m_Count; + + // Store the element into the list + if (m_pElementList) + m_pElementList[elem] = list; +} + +template <class T, class I> +void CUtlMultiList<T,I>::Unlink( ListHandle_t list, I elem ) +{ + Assert( IsValidIndex(elem) && IsValidList(list) ); + + if (IsInList(elem)) + { + // Make sure the element is in the right list + Assert( IsElementInList( list, elem ) ); + ListElem_t& oldElem = InternalElement(elem); + + // If we're the first guy, reset the head + // otherwise, make our previous node's next pointer = our next + if (oldElem.m_Previous != InvalidIndex()) + InternalElement(oldElem.m_Previous).m_Next = oldElem.m_Next; + else + m_List[list].m_Head = oldElem.m_Next; + + // If we're the last guy, reset the tail + // otherwise, make our next node's prev pointer = our prev + if (oldElem.m_Next != InvalidIndex()) + InternalElement(oldElem.m_Next).m_Previous = oldElem.m_Previous; + else + m_List[list].m_Tail = oldElem.m_Previous; + + // This marks this node as not in the list, + // but not in the free list either + oldElem.m_Previous = oldElem.m_Next = elem; + + // One less puppy + --m_List[list].m_Count; + + // Store the element into the list + if (m_pElementList) + m_pElementList[elem] = m_List.InvalidIndex(); + } +} + +template <class T, class I> +inline void CUtlMultiList<T,I>::LinkToHead( ListHandle_t list, I elem ) +{ + LinkAfter( list, InvalidIndex(), elem ); +} + +template <class T, class I> +inline void CUtlMultiList<T,I>::LinkToTail( ListHandle_t list, I elem ) +{ + LinkBefore( list, InvalidIndex(), elem ); +} + + +//----------------------------------------------------------------------------- +// Insertion methods; allocates and links (uses default constructor) +//----------------------------------------------------------------------------- +template <class T, class I> +I CUtlMultiList<T,I>::InsertBefore( ListHandle_t list, I before ) +{ + // Make a new node + I newNode = Alloc(); + if ( newNode == InvalidIndex() ) + return newNode; + + // Link it in + LinkBefore( list, before, newNode ); + + // Construct the data + Construct( &Element(newNode) ); + + return newNode; +} + +template <class T, class I> +I CUtlMultiList<T,I>::InsertAfter( ListHandle_t list, I after ) +{ + // Make a new node + I newNode = Alloc(); + if ( newNode == InvalidIndex() ) + return newNode; + + // Link it in + LinkAfter( list, after, newNode ); + + // Construct the data + Construct( &Element(newNode) ); + + return newNode; +} + +template <class T, class I> +inline I CUtlMultiList<T,I>::AddToHead( ListHandle_t list ) +{ + return InsertAfter( list, InvalidIndex() ); +} + +template <class T, class I> +inline I CUtlMultiList<T,I>::AddToTail( ListHandle_t list ) +{ + return InsertBefore( list, InvalidIndex() ); +} + + +//----------------------------------------------------------------------------- +// Insertion methods; allocates and links (uses copy constructor) +//----------------------------------------------------------------------------- +template <class T, class I> +I CUtlMultiList<T,I>::InsertBefore( ListHandle_t list, I before, T const& src ) +{ + // Make a new node + I newNode = Alloc(); + if ( newNode == InvalidIndex() ) + return newNode; + + // Link it in + LinkBefore( list, before, newNode ); + + // Construct the data + CopyConstruct( &Element(newNode), src ); + + return newNode; +} + +template <class T, class I> +I CUtlMultiList<T,I>::InsertAfter( ListHandle_t list, I after, T const& src ) +{ + // Make a new node + I newNode = Alloc(); + if ( newNode == InvalidIndex() ) + return newNode; + + // Link it in + LinkAfter( list, after, newNode ); + + // Construct the data + CopyConstruct( &Element(newNode), src ); + + return newNode; +} + +template <class T, class I> +inline I CUtlMultiList<T,I>::AddToHead( ListHandle_t list, T const& src ) +{ + return InsertAfter( list, InvalidIndex(), src ); +} + +template <class T, class I> +inline I CUtlMultiList<T,I>::AddToTail( ListHandle_t list, T const& src ) +{ + return InsertBefore( list, InvalidIndex(), src ); +} + + +//----------------------------------------------------------------------------- +// Removal methods +//----------------------------------------------------------------------------- +template <class T, class I> +void CUtlMultiList<T,I>::Remove( ListHandle_t list, I elem ) +{ + if (IsInList(elem)) + Unlink(list, elem); + Free( elem ); +} + +// Removes all items in a single list +template <class T, class I> +void CUtlMultiList<T,I>::RemoveAll( ListHandle_t list ) +{ + Assert( IsValidList(list) ); + I i = Head(list); + I next; + while( i != InvalidIndex() ) + { + next = Next(i); + Remove(list, i); + i = next; + } +} + + +template <class T, class I> +void CUtlMultiList<T,I>::RemoveAll() +{ + if (m_MaxElementIndex == 0) + return; + + // Put everything into the free list + I prev = InvalidIndex(); + for (int i = (int)m_MaxElementIndex; --i >= 0; ) + { + // Invoke the destructor + if (IsValidIndex((I)i)) + Destruct( &Element((I)i) ); + + // next points to the next free list item + InternalElement((I)i).m_Next = prev; + + // Indicates it's in the free list + InternalElement((I)i).m_Previous = (I)i; + prev = (I)i; + } + + // First free points to the first element + m_FirstFree = 0; + + // Clear everything else out + for (I list = m_List.Head(); list != m_List.InvalidIndex(); list = m_List.Next(list) ) + { + m_List[list].m_Head = InvalidIndex(); + m_List[list].m_Tail = InvalidIndex(); + m_List[list].m_Count = 0; + } + + m_TotalElements = 0; +} + + +#include "tier0/memdbgoff.h" + +#endif // UTLMULTILIST_H |