// (C) 2006 Jagoon Software. All Rights Reserved.
// 自由に利用していただいて構いませんが、無保証です。

struct SIListData {
	SIListData *next;
	void *val;
};

class CInterlockedList {
public:
	// コンストラクタ
	CInterlockedList() {
		m_semaphoreA = CreateSemaphore( NULL, 0, 1, NULL );
		m_semaphoreB = CreateSemaphore( NULL, 0, 1, NULL );
		for( int i = 0; i < m_MaxItem; i++ ) {
			m_item[i].next = &m_item[i+1];
		}
		m_first_node = NULL;
		m_first_free = &m_item[0];
		m_item[m_MaxItem-1].next = NULL;
	}
	// デストラクタ
	~CInterlockedList() {
		CloseHandle( m_semaphoreA );
		CloseHandle( m_semaphoreB );
	}
	// リストにプッシュ
	void Push( void *pData ) {
		SIListData *pOld, *pNew, *pRet;
		// 未使用リストから削除(POP)
		do {
			pOld = (SIListData*)m_first_free;
			if( pOld == NULL ) {
				WaitForSingleObject( m_semaphoreA, INFINITE );
				pRet = pOld + 1;
			} else {
				pNew = pOld->next; // この時点で free( pOld ) されてない事は保証済み
				pRet = (SIListData*)InterlockedCompareExchangePointer( (void**)&m_first_free, pNew, pOld );
			}
		} while( pRet != pOld );
		// 使用済みリストに挿入(PUSH)
		pNew      = pOld;
		pNew->val = pData;
		do {
			pOld = (SIListData*)m_first_node;
			pNew->next = pOld;
			pRet = (SIListData*)InterlockedCompareExchangePointer( (void**)&m_first_node, pNew, pOld );
		} while( pRet != pOld );
		if( pOld == NULL ) {
			ReleaseSemaphore( m_semaphoreB, 1, NULL );
		}
	}
	// リストからポップ
	void* Pop( void ) {
		void *pVal;
		SIListData *pOld, *pNew, *pRet;
		// 使用済みリストから削除(POP)
		do {
			pOld = (SIListData*)m_first_node;
			if( pOld == NULL ) {
				WaitForSingleObject( m_semaphoreB, INFINITE );
				pRet = pOld + 1;
			} else {
				pNew = pOld->next; // この時点で free( pOld ) されてない事は保証済み
				pRet = (SIListData*)InterlockedCompareExchangePointer( (void**)&m_first_node, pNew, pOld );
			}
		} while( pRet != pOld );
		// 未使用リストに挿入(PUSH)
		pVal      = pOld->val;
		pNew      = pOld;
		pNew->val = NULL;
		do {
			pOld = (SIListData*)m_first_free;
			pNew->next = pOld;
			pRet = (SIListData*)InterlockedCompareExchangePointer( (void**)&m_first_free, pNew, pOld );
		} while( pRet != pOld );
		if( pOld == NULL ) {
			ReleaseSemaphore( m_semaphoreA, 1, NULL );
		}
		return pVal;
	}
	// リストが空かどうか
	BOOL IsEmpty( void ) {
		return m_first_node == NULL;
	}

private:
	static const int m_MaxItem = 256; // リストの最大要素数
	HANDLE m_semaphoreA, m_semaphoreB;
	SIListData m_item[m_MaxItem]; // 作業が終わるまで解放されないことを保証する為
	volatile SIListData* m_first_free;
	volatile SIListData* m_first_node;
};