//========== Copyright 2005, Valve Corporation, All rights reserved. ======== // // Purpose: // // LIFO from disassembly of Windows API and http://perso.wanadoo.fr/gmem/evenements/jim2002/articles/L17_Fober.pdf // FIFO from http://perso.wanadoo.fr/gmem/evenements/jim2002/articles/L17_Fober.pdf // //============================================================================= #ifndef TSLIST_H #define TSLIST_H #if defined( _WIN32 ) #pragma once #endif #if ( defined(_WIN64) || defined(_X360) ) #define USE_NATIVE_SLIST #endif #if defined( USE_NATIVE_SLIST ) #ifdef _XBOX #include "xbox/xbox_platform.h" #include "xbox/xbox_win32stubs.h" #include "xbox/xbox_core.h" #else #define WIN32_LEAN_AND_MEAN #include <windows.h> #endif #endif // _WIN32 #include "tier0/threadtools.h" //----------------------------------------------------------------------------- #if defined(_WIN64) #define TSLIST_HEAD_ALIGNMENT MEMORY_ALLOCATION_ALIGNMENT #define TSLIST_NODE_ALIGNMENT MEMORY_ALLOCATION_ALIGNMENT #else #define TSLIST_HEAD_ALIGNMENT 8 #define TSLIST_NODE_ALIGNMENT 4 #endif #define TSLIST_HEAD_ALIGN __declspec(align(TSLIST_HEAD_ALIGNMENT)) #define TSLIST_NODE_ALIGN __declspec(align(TSLIST_NODE_ALIGNMENT)) //----------------------------------------------------------------------------- // Lock free list. //----------------------------------------------------------------------------- #ifdef USE_NATIVE_SLIST typedef SLIST_ENTRY TSLNodeBase_t; typedef SLIST_HEADER TSLHead_t; #else struct TSLIST_NODE_ALIGN TSLNodeBase_t { TSLNodeBase_t *Next; // name to match Windows }; union TSLHead_t { struct Value_t { TSLNodeBase_t *Next; int16 Depth; int16 Sequence; } value; int64 value64; }; #endif //------------------------------------- template <typename T> class TSLIST_HEAD_ALIGN CTSList { public: struct TSLIST_NODE_ALIGN Node_t : public TSLNodeBase_t { Node_t() {} Node_t( const T &init ) : elem( init ) {} T elem; void *operator new( size_t size ) { return ( TSLIST_NODE_ALIGNMENT > 4 ) ? _aligned_malloc( size, TSLIST_NODE_ALIGNMENT ) : malloc( size ); } void *operator new( size_t size, int nBlockUse, const char *pFileName, int nLine ) { return operator new( size ); } void operator delete( void *p ) { if ( TSLIST_NODE_ALIGNMENT > 4 ) _aligned_free( p ); else free( p ); } void operator delete( void *p, int nBlockUse, const char *pFileName, int nLine ) { operator delete(p); } }; CTSList() { if ( ((size_t)&m_Head) % TSLIST_HEAD_ALIGNMENT != 0 ) DebuggerBreak(); #ifdef USE_NATIVE_SLIST InitializeSListHead( &m_Head ); #else m_Head.value64 = (int64)0; #endif } void *operator new( size_t size ) { return _aligned_malloc( size, TSLIST_HEAD_ALIGNMENT ); } void *operator new( size_t size, int nBlockUse, const char *pFileName, int nLine ) { return operator new( size ); } void operator delete( void *pMem ) { _aligned_free( pMem ); } void operator delete( void *pMem, int nBlockUse, const char *pFileName, int nLine ) { operator delete(pMem); } Node_t *Push( Node_t *pNode ) { Assert( (size_t)pNode % TSLIST_NODE_ALIGNMENT == 0 ); #ifdef USE_NATIVE_SLIST return (Node_t *)InterlockedPushEntrySList( &m_Head, pNode ); #else TSLHead_t oldHead; TSLHead_t newHead; do { oldHead.value64 = m_Head.value64; pNode->Next = oldHead.value.Next; newHead.value.Next = pNode; *((uint32 *)&newHead.value.Depth) = *((uint32 *)&oldHead.value.Depth) + 0x10001; } while( !ThreadInterlockedAssignIf64( &m_Head.value64, newHead.value64, oldHead.value64 ) ); return (Node_t *)oldHead.value.Next; #endif } Node_t *Pop() { #ifdef USE_NATIVE_SLIST return (Node_t *)InterlockedPopEntrySList( &m_Head ); #else TSLHead_t oldHead; TSLHead_t newHead; do { oldHead.value64 = m_Head.value64; if ( !oldHead.value.Next ) return NULL; newHead.value.Next = oldHead.value.Next->Next; *((uint32 *)&newHead.value.Depth) = *((uint32 *)&oldHead.value.Depth) - 1; } while( !ThreadInterlockedAssignIf64( &m_Head.value64, newHead.value64, oldHead.value64 ) ); return (Node_t *)oldHead.value.Next; #endif } void PushItem( const T &init ) { Push( new Node_t( init ) ); } bool PopItem( T *pResult) { Node_t *pNode = Pop(); if ( !pNode ) return false; *pResult = pNode->elem; delete pNode; return true; } Node_t *Detach() { #ifdef USE_NATIVE_SLIST return (Node_t *)InterlockedFlushSList( &m_Head ); #else TSLHead_t oldHead; TSLHead_t newHead; do { oldHead.value64 = m_Head.value64; if ( !oldHead.value.Next ) return NULL; newHead.value.Next = NULL; *((uint32 *)&newHead.value.Depth) = *((uint32 *)&oldHead.value.Depth) & 0xffff0000; } while( !ThreadInterlockedAssignIf64( &m_Head.value64, newHead.value64, oldHead.value64 ) ); return (Node_t *)oldHead.value.Next; #endif } int Count() { #ifdef USE_NATIVE_SLIST return QueryDepthSList( &m_Head ); #else return m_Head.value.Depth; #endif } private: TSLHead_t m_Head; }; //----------------------------------------------------------------------------- // Lock free queue //----------------------------------------------------------------------------- template <typename T> class TSLIST_HEAD_ALIGN CTSQueue { public: struct TSLIST_NODE_ALIGN Node_t { Node_t() {} Node_t( const T &init ) : elem( init ) {} Node_t *pNext; T elem; }; union TSLIST_HEAD_ALIGN NodeLink_t { struct Value_t { Node_t *pNode; int32 sequence; } value; int64 value64; }; CTSQueue() { if ( ((size_t)&m_Head) % TSLIST_HEAD_ALIGNMENT != 0 ) DebuggerBreak(); m_Count = 0; m_Head.value.sequence = m_Tail.value.sequence = 0; m_Head.value.pNode = m_Tail.value.pNode = &m_Dummy; m_Dummy.pNext = End(); } Node_t *Push( Node_t *pNode ) { Assert( (size_t)pNode % TSLIST_NODE_ALIGNMENT == 0 ); NodeLink_t oldTail; NodeLink_t newTail; pNode->pNext = End(); for (;;) { oldTail = m_Tail; if ( InterlockedCompareExchangeNode( &(oldTail.value.pNode->pNext), pNode, End() ) == End() ) { break; } else { newTail.value.pNode = oldTail.value.pNode->pNext; newTail.value.sequence = oldTail.value.sequence + 1; InterlockedCompareExchangeNodeLink( &m_Tail, newTail, oldTail ); } } newTail.value.pNode = pNode; newTail.value.sequence = oldTail.value.sequence + 1; InterlockedCompareExchangeNodeLink( &m_Tail, newTail, oldTail ); m_Count++; return oldTail.value.pNode; } Node_t *Pop() { NodeLink_t head; NodeLink_t newHead; Node_t *pNext; int tailSequence; T elem; for (;;) { head = m_Head; tailSequence = m_Tail.value.sequence; pNext = head.value.pNode->pNext; if ( head.value.sequence == m_Head.value.sequence ) { if ( head.value.pNode == m_Tail.value.pNode ) { if ( pNext == End() ) { return NULL; } NodeLink_t &newTail = newHead; // just reuse locals memory NodeLink_t &oldTail = head; oldTail.value.sequence = tailSequence; // reuse head pNode newTail.value.pNode = pNext; newTail.value.sequence = tailSequence + 1; InterlockedCompareExchangeNodeLink( &m_Tail, newTail, oldTail ); } else if ( pNext != End() ) { elem = pNext->elem; newHead.value.pNode = pNext; newHead.value.sequence = head.value.sequence + 1; if ( InterlockedAssignNodeLinkIf( &m_Head, newHead, head ) ) { break; } } } } m_Count--; head.value.pNode->elem = elem; return newHead.value.pNode; } void PushItem( const T &init ) { Push( new Node_t( init ) ); } bool PopItem( T *pResult) { Node_t *pNode = Pop(); if ( !pNode ) return false; *pResult = pNode->elem; delete pNode; return true; } int Count() { return m_Count; } private: Node_t *End() { return (Node_t *)this; } // just need a unique signifier #ifndef _WIN64 Node_t *InterlockedCompareExchangeNode( Node_t * volatile *ppNode, Node_t *value, Node_t *comperand ) { return (Node_t *)::ThreadInterlockedCompareExchangePointer( (void **)ppNode, value, comperand ); } void InterlockedCompareExchangeNodeLink( NodeLink_t volatile *pLink, const NodeLink_t &value, const NodeLink_t &comperand ) { ThreadInterlockedAssignIf64( (int64 *)pLink, value.value64, comperand.value64 ); } bool InterlockedAssignNodeLinkIf( NodeLink_t volatile *pLink, const NodeLink_t &value, const NodeLink_t &comperand ) { return ThreadInterlockedAssignIf64( (int64 *)pLink, value.value64, comperand.value64 ); } #else Node_t *InterlockedCompareExchangeNode( Node_t * volatile *ppNode, Node_t *value, Node_t *comperand ) { AUTO_LOCK( m_ExchangeMutex ); Node_t *retVal = *ppNode; if ( *ppNode == comperand ) *ppNode = value; return retVal; } NodeLink_t InterlockedCompareExchangeNodeLink( NodeLink_t volatile *pLink, const NodeLink_t &value, const NodeLink_t &comperand ) { AUTO_LOCK( m_ExchangeMutex ); NodeLink_t retVal; retVal.value64 = pLink->value64; if ( pLink->value64 == comperand.value64 ) pLink->value64 = value.value64; return retVal; } bool InterlockedAssignNodeLinkIf( NodeLink_t volatile *pLink, const NodeLink_t &value, const NodeLink_t &comperand ) { return ( InterlockedCompareExchangeNodeLink( (int64 *)pLink, value.value64, comperand.value64 ).value64 == comperand.value64 ); } CThreadFastMutex m_ExchangeMutex; #endif NodeLink_t m_Head; NodeLink_t m_Tail; Node_t m_Dummy; CInterlockedInt m_Count; }; #endif // TSLIST_H
# | Change | User | Description | Committed | |
---|---|---|---|---|---|
#1 | 5821 | Knut Wikstrom |
Added Valve Source code. This is NOT to be commited to other than new code from Valve. |