diff options
Diffstat (limited to 'mp/src/public/tier1/utlqueue.h')
| -rw-r--r-- | mp/src/public/tier1/utlqueue.h | 535 |
1 files changed, 486 insertions, 49 deletions
diff --git a/mp/src/public/tier1/utlqueue.h b/mp/src/public/tier1/utlqueue.h index 8624a3db..05c89ee3 100644 --- a/mp/src/public/tier1/utlqueue.h +++ b/mp/src/public/tier1/utlqueue.h @@ -11,104 +11,541 @@ #pragma once #endif -#include "utlvector.h" +#include "utlmemory.h" -// T is the type stored in the stack -template< class T > +//#define TEST_UTLQUEUE + +enum QueueIter_t { QUEUE_ITERATOR_INVALID = 0xffffffff }; + +// T is the type stored in the queue +template< class T, class M = CUtlMemory< T > > class CUtlQueue { public: - // constructor: lessfunc is required, but may be set after the constructor with - // SetLessFunc CUtlQueue( int growSize = 0, int initSize = 0 ); CUtlQueue( T *pMemory, int numElements ); // return the item from the front of the queue and delete it - T const& RemoveAtHead(); + T RemoveAtHead(); + bool RemoveAtHead( T &removedElement ); + // return the item from the end of the queue and delete it - T const& RemoveAtTail(); + T RemoveAtTail(); + bool RemoveAtTail( T &removedElement ); // return item at the front of the queue - T const& Head(); + T const& Head() const; // return item at the end of the queue - T const& Tail(); + T const& Tail() const; // Add a new item to the end of the queue void Insert( T const &element ); // checks if an element of this value already exists on the stack, returns true if it does - bool Check( T const element ); + bool Check( T const element ) const; + + // iterators may be invalidated by Insert() + QueueIter_t First() const; + QueueIter_t Next( QueueIter_t it ) const; + QueueIter_t Last() const; + QueueIter_t Previous( QueueIter_t it ) const; + bool IsValid( QueueIter_t it ) const; + T const& Element( QueueIter_t it ) const; + + // Returns the count of elements in the queue + int Count() const; + + // Return whether the queue is empty or not, faster than Count(). + bool IsEmpty() const; - // Returns the count of elements in the stack - int Count() const { return m_heap.Count(); } - // doesn't deallocate memory - void RemoveAll() { m_heap.RemoveAll(); } + void RemoveAll(); // Memory deallocation - void Purge() { m_heap.Purge(); } + void Purge(); protected: - CUtlVector<T> m_heap; - T m_current; + QueueIter_t Next_Unchecked( QueueIter_t it ) const; + QueueIter_t Previous_Unchecked( QueueIter_t it ) const; + + M m_memory; + + // if m_head == m_tail == QUEUE_ITERATOR_INVALID, then the queue is empty + QueueIter_t m_head; + QueueIter_t m_tail; + +#ifdef TEST_UTLQUEUE + friend void CUtlQueue_Test(); +#endif +}; + +//----------------------------------------------------------------------------- +// The CUtlQueueFixed class: +// A queue class with a fixed allocation scheme +//----------------------------------------------------------------------------- +template< class T, size_t MAX_SIZE > +class CUtlQueueFixed : public CUtlQueue< T, CUtlMemoryFixed<T, MAX_SIZE > > +{ + typedef CUtlQueue< T, CUtlMemoryFixed<T, MAX_SIZE > > BaseClass; +public: + + // constructor, destructor + CUtlQueueFixed( int growSize = 0, int initSize = 0 ) : BaseClass( growSize, initSize ) {} + CUtlQueueFixed( T* pMemory, int numElements ) : BaseClass( pMemory, numElements ) {} }; -template< class T > -inline CUtlQueue<T>::CUtlQueue( int growSize, int initSize ) : - m_heap(growSize, initSize) +template< class T, class M > +inline CUtlQueue<T, M>::CUtlQueue( int growSize, int initSize ) : + m_memory( growSize, initSize ), m_head( QUEUE_ITERATOR_INVALID ), m_tail( QUEUE_ITERATOR_INVALID ) { } -template< class T > -inline CUtlQueue<T>::CUtlQueue( T *pMemory, int numElements ) : - m_heap(pMemory, numElements) +template< class T, class M > +inline CUtlQueue<T, M>::CUtlQueue( T *pMemory, int numElements ) : + m_memory( pMemory, numElements ), m_head( QUEUE_ITERATOR_INVALID ), m_tail( QUEUE_ITERATOR_INVALID ) { } -template <class T> -inline T const& CUtlQueue<T>::RemoveAtHead() +template <class T, class M> +inline T CUtlQueue<T, M>::RemoveAtHead() { - m_current = m_heap[0]; - m_heap.Remove((int)0); - return m_current; + T temp; + RemoveAtHead( temp ); + return temp; } -template <class T> -inline T const& CUtlQueue<T>::RemoveAtTail() +template <class T, class M> +inline bool CUtlQueue<T, M>::RemoveAtHead( T &removedElement ) { - m_current = m_heap[ m_heap.Count() - 1 ]; - m_heap.Remove((int)(m_heap.Count() - 1)); - return m_current; + Assert( m_head != QUEUE_ITERATOR_INVALID ); + if ( m_head == QUEUE_ITERATOR_INVALID ) + { + Construct( &removedElement ); + return false; + } + + QueueIter_t it = m_head; + removedElement = m_memory[ it ]; + Destruct( &m_memory[ it ] ); + if ( m_head == m_tail ) + { + m_head = m_tail = QUEUE_ITERATOR_INVALID; + } + else + { + m_head = Next_Unchecked( m_head ); + } + return true; +} + +template <class T, class M> +inline T CUtlQueue<T, M>::RemoveAtTail() +{ + T temp; + RemoveAtTail( temp ); + return temp; +} + +template <class T, class M> +inline bool CUtlQueue<T, M>::RemoveAtTail( T &removedElement ) +{ + Assert( m_tail != QUEUE_ITERATOR_INVALID ); + if ( m_tail == QUEUE_ITERATOR_INVALID ) + { + Construct( &removedElement ); + return false; + } + + removedElement = m_memory[ m_tail ]; + Destruct( &m_memory[ m_tail ] ); + if ( m_head == m_tail ) + { + m_head = m_tail = QUEUE_ITERATOR_INVALID; + } + else + { + m_tail = Previous_Unchecked( m_tail ); + } + return true; } -template <class T> -inline T const& CUtlQueue<T>::Head() +template <class T, class M> +inline T const& CUtlQueue<T, M>::Head() const { - m_current = m_heap[0]; - return m_current; + Assert( m_head != QUEUE_ITERATOR_INVALID ); + if ( m_head == QUEUE_ITERATOR_INVALID ) + { + static T dummy; + return dummy; + } + + return m_memory[ m_head ]; } -template <class T> -inline T const& CUtlQueue<T>::Tail() +template <class T, class M> +inline T const& CUtlQueue<T, M>::Tail() const { - m_current = m_heap[ m_heap.Count() - 1 ]; - return m_current; + Assert( m_tail != QUEUE_ITERATOR_INVALID ); + if ( m_tail == QUEUE_ITERATOR_INVALID ) + { + static T dummy; + return dummy; + } + + return m_memory[ m_tail ]; } -template <class T> -void CUtlQueue<T>::Insert( T const &element ) +template <class T, class M> +void CUtlQueue<T, M>::Insert( T const &element ) { - int index = m_heap.AddToTail(); - m_heap[index] = element; + if ( m_tail == QUEUE_ITERATOR_INVALID ) + { + // empty + m_memory.EnsureCapacity( 1 ); + m_head = m_tail = QueueIter_t( 0 ); + } + else + { + // non-empty + QueueIter_t nextTail = Next_Unchecked( m_tail ); + if ( nextTail == m_head ) // if non-empty, and growing by 1 appears to make the queue of length 1, then we were already full before the Insert + { + int nOldAllocCount = m_memory.NumAllocated(); + m_memory.Grow(); + int nNewAllocCount = m_memory.NumAllocated(); + int nGrowAmount = nNewAllocCount - nOldAllocCount; + + nextTail = Next_Unchecked( m_tail ); // if nextTail was 0, then it now should be nOldAllocCount + + if ( m_head != QueueIter_t( 0 ) ) + { + // if the queue wraps around the end of m_memory, move the part at the end of memory to the new end of memory + Q_memmove( &m_memory[ m_head + nGrowAmount ], &m_memory[ m_head ], ( nOldAllocCount - m_head ) * sizeof( T ) ); +#ifdef _DEBUG + Q_memset( &m_memory[ m_head ], 0xdd, nGrowAmount * sizeof( T ) ); +#endif + m_head = QueueIter_t( m_head + nGrowAmount ); + } + } + m_tail = nextTail; + } + + CopyConstruct( &m_memory[ m_tail ], element ); } -template <class T> -bool CUtlQueue<T>::Check( T const element ) +template <class T, class M> +bool CUtlQueue<T, M>::Check( T const element ) const { - int index = m_heap.Find(element); - return ( index != -1 ); + for ( QueueIter_t it = First(); it != QUEUE_ITERATOR_INVALID; it = Next( it ) ) + { + if ( m_memory[ it ] == element ) + return true; + } + return false; +} + +template <class T, class M> +QueueIter_t CUtlQueue<T, M>::First() const +{ + return m_head; +} + +template <class T, class M> +QueueIter_t CUtlQueue<T, M>::Next( QueueIter_t it ) const +{ + if ( it == QUEUE_ITERATOR_INVALID ) + return QUEUE_ITERATOR_INVALID; + + if ( it == m_tail ) + return QUEUE_ITERATOR_INVALID; + + Assert( IsValid( it ) ); + if ( !IsValid( it ) ) + return QUEUE_ITERATOR_INVALID; + + return Next_Unchecked( it ); +} + +template <class T, class M> +QueueIter_t CUtlQueue<T, M>::Last() const +{ + return m_tail; +} + +template <class T, class M> +QueueIter_t CUtlQueue<T, M>::Previous( QueueIter_t it ) const +{ + if ( it == QUEUE_ITERATOR_INVALID ) + return QUEUE_ITERATOR_INVALID; + + if ( it == m_head ) + return QUEUE_ITERATOR_INVALID; + + Assert( IsValid( it ) ); + if ( !IsValid( it ) ) + return QUEUE_ITERATOR_INVALID; + + return Previous_Unchecked( it ); +} + +template <class T, class M> +QueueIter_t CUtlQueue<T, M>::Next_Unchecked( QueueIter_t it ) const +{ + return it == m_memory.Count() - 1 ? QueueIter_t( 0 ) : QueueIter_t( it + 1 ); +} + +template <class T, class M> +QueueIter_t CUtlQueue<T, M>::Previous_Unchecked( QueueIter_t it ) const +{ + return it == 0 ? QueueIter_t( m_memory.Count() - 1 ) : QueueIter_t( it - 1 ); +} + +template <class T, class M> +bool CUtlQueue<T, M>::IsValid( QueueIter_t it ) const +{ + if ( it == QUEUE_ITERATOR_INVALID ) + return false; + + if ( m_head == QUEUE_ITERATOR_INVALID ) + return false; + + if ( m_head <= m_tail ) + return it >= m_head && it <= m_tail; + + return ( it >= m_head && it < m_memory.Count() ) || ( it >= 0 && it <= m_tail ); +} + +template <class T, class M> +T const& CUtlQueue<T, M>::Element( QueueIter_t it ) const +{ + Assert( it != QUEUE_ITERATOR_INVALID ); + if ( it == QUEUE_ITERATOR_INVALID ) + { + static T dummy; + return dummy; + } + + Assert( IsValid( it ) ); + return m_memory[ it ]; +} + +template <class T, class M> +int CUtlQueue<T, M>::Count() const +{ + if ( m_head == QUEUE_ITERATOR_INVALID ) + { + Assert( m_tail == QUEUE_ITERATOR_INVALID ); + return 0; + } + Assert( m_tail != QUEUE_ITERATOR_INVALID ); + + if ( m_head <= m_tail ) + return m_tail + 1 - m_head; + + return m_tail + 1 - m_head + m_memory.Count(); +} + +template <class T, class M> +bool CUtlQueue<T, M>::IsEmpty() const +{ + Assert( ( m_head == QUEUE_ITERATOR_INVALID ) == ( m_tail == QUEUE_ITERATOR_INVALID ) ); + return ( m_head == QUEUE_ITERATOR_INVALID ); +} + +template <class T, class M> +void CUtlQueue<T, M>::RemoveAll() +{ + m_head = m_tail = QUEUE_ITERATOR_INVALID; +} + +template <class T, class M> +void CUtlQueue<T, M>::Purge() +{ + m_head = m_tail = QUEUE_ITERATOR_INVALID; + m_memory.Purge(); +} + + +#ifdef TEST_UTLQUEUE + +#include <stdlib.h> + +struct Data_t +{ + Data_t( int i = 0xffffffff ) : m_id( i ) {} + Data_t( const Data_t &that ) : m_id( that.m_id ) {} + ~Data_t() { m_id = 0xdddddddd; } + Data_t &operator=( const Data_t &that ) { m_id = that.m_id; return *this; } + + int m_id; +}; + +inline void CUtlQueue_Test() +{ + CUtlQueue< Data_t > queue; + + for ( int n = 1; n < 100; ++n ) + { + Assert( queue.Count() == 0 ); + Assert( queue.m_head == QUEUE_ITERATOR_INVALID ); + Assert( queue.m_tail == QUEUE_ITERATOR_INVALID ); + + int w = rand() % n; + for ( int i = 0; i < w; ++i ) + { + queue.Insert( Data_t( i ) ); + } + + if ( w > 0 ) + { + Assert( queue.Head().m_id == queue.First() ); + Assert( queue.Tail().m_id == queue.Last() ); + Assert( queue.Head().m_id == 0 ); + Assert( queue.Tail().m_id == w - 1 ); + } + Assert( queue.Count() == w ); + + for ( int j = 0; j < n; ++j ) + { + queue.Insert( Data_t( w + j ) ); + + if ( j == 0 ) + { + Assert( queue.Count() == w + j + 1 ); + + for ( int i = 0; i < w; ++i ) + { + queue.RemoveAtHead(); + } + } + + Assert( queue.Count() == j + 1 ); + + Assert( queue.m_head != QUEUE_ITERATOR_INVALID ); + Assert( queue.m_tail != QUEUE_ITERATOR_INVALID ); + + int id = queue.Head().m_id % queue.m_memory.Count(); + for ( QueueIter_t it = queue.First(); it != QUEUE_ITERATOR_INVALID; it = queue.Next( it ) ) + { + Assert( queue.Element( it ).m_id % queue.m_memory.Count() == id ); + id = ( id + 1 ) % queue.m_memory.Count(); + } + + id = queue.Tail().m_id % queue.m_memory.Count(); + for ( QueueIter_t it = queue.Last(); it != QUEUE_ITERATOR_INVALID; it = queue.Previous( it ) ) + { + Assert( queue.Element( it ).m_id % queue.m_memory.Count() == id ); + id = ( id + queue.m_memory.Count() - 1 ) % queue.m_memory.Count(); + } + + for ( int i = 0; i < j; ++i ) + { + int id = queue.m_memory[ i ].m_id; + if ( queue.IsValid( QueueIter_t( i ) ) ) + { + Assert( ( id & 0xff000000 ) == 0 ); + } + else + { + Assert( id == 0xdddddddd ); + } + } + } + + Assert( queue.Count() == n ); +#if 0 + for ( int j = 0; j < n; ++j ) + { + Assert( queue.m_head != QUEUE_ITERATOR_INVALID ); + Assert( queue.m_tail != QUEUE_ITERATOR_INVALID ); + + Assert( queue.Count() == n - j ); + + Data_t data = queue.RemoveAtHead(); + + Assert( queue.Count() == n - j - 1 ); + + if ( queue.Count() > 0 ) + { + int id = queue.Head().m_id % queue.m_memory.Count(); + for ( QueueIter_t it = queue.First(); it != QUEUE_ITERATOR_INVALID; it = queue.Next( it ) ) + { + Assert( queue.Element( it ).m_id % queue.m_memory.Count() == id ); + id = ( id + 1 ) % queue.m_memory.Count(); + } + + id = queue.Tail().m_id % queue.m_memory.Count(); + for ( QueueIter_t it = queue.Last(); it != QUEUE_ITERATOR_INVALID; it = queue.Previous( it ) ) + { + Assert( queue.Element( it ).m_id % queue.m_memory.Count() == id ); + id = ( id + queue.m_memory.Count() - 1 ) % queue.m_memory.Count(); + } + } + + for ( int i = 0; i < j; ++i ) + { + int id = queue.m_memory[ i ].m_id; + if ( queue.IsValid( QueueIter_t( i ) ) ) + { + Assert( ( id & 0xff000000 ) == 0 ); + } + else + { + Assert( id == 0xdddddddd ); + } + } + } +#else + for ( int j = n - 1; j >= 0; --j ) + { + Assert( queue.m_head != QUEUE_ITERATOR_INVALID ); + Assert( queue.m_tail != QUEUE_ITERATOR_INVALID ); + + Assert( queue.Count() == j + 1 ); + + Data_t data = queue.RemoveAtTail(); + + Assert( queue.Count() == j ); + + if ( queue.Count() > 0 ) + { + int id = queue.Head().m_id % queue.m_memory.Count(); + for ( QueueIter_t it = queue.First(); it != QUEUE_ITERATOR_INVALID; it = queue.Next( it ) ) + { + Assert( queue.Element( it ).m_id % queue.m_memory.Count() == id ); + id = ( id + 1 ) % queue.m_memory.Count(); + } + + id = queue.Tail().m_id % queue.m_memory.Count(); + for ( QueueIter_t it = queue.Last(); it != QUEUE_ITERATOR_INVALID; it = queue.Previous( it ) ) + { + Assert( queue.Element( it ).m_id % queue.m_memory.Count() == id ); + id = ( id + queue.m_memory.Count() - 1 ) % queue.m_memory.Count(); + } + } + + for ( int i = 0; i < j; ++i ) + { + int id = queue.m_memory[ i ].m_id; + if ( queue.IsValid( QueueIter_t( i ) ) ) + { + Assert( ( id & 0xff000000 ) == 0 ); + } + else + { + Assert( id == 0xdddddddd ); + } + } + } +#endif + + Assert( queue.Count() == 0 ); + Assert( queue.m_head == QUEUE_ITERATOR_INVALID ); + Assert( queue.m_tail == QUEUE_ITERATOR_INVALID ); + } } +#endif // TEST_UTLQUEUE #endif // UTLQUEUE_H |