Thread safe lock-free stack using win32 threading primitives

Question

class CSList
{
public:
 CSList()
 {
 ::InitializeSListHead(&m_head);
 }
 USHORT Depth()
 {
 return ::QueryDepthSList(&m_head);
 }
 PSLIST_ENTRY Flush()
 {
 return ::InterlockedFlushSList(&m_head);
 }
 PSLIST_ENTRY First()
 {
 return ::RtlFirstEntrySList(&m_head);
 }
 PSLIST_ENTRY Push(PSLIST_ENTRY ListEntry)
 {
 return ::InterlockedPushEntrySList(&m_head, ListEntry);
 }
 PSLIST_ENTRY Pop()
 {
 return ::InterlockedPopEntrySList(&m_head);
 }
private:
 SLIST_HEADER m_head;
};
template <typename T>
class TSimpleStack
{
public:
 typedef struct DATA_ENTRY : SINGLE_LIST_ENTRY
 {
 T Data;
 DATA_ENTRY(const T& val) : Data(val)
 {
 SINGLE_LIST_ENTRY::Next = NULL;
 }
 } *LPDATA_ENTRY;
 ~TSimpleStack()
 {
 while (m_list.Depth() > 0)
 {
 LPDATA_ENTRY lpEntry = (LPDATA_ENTRY) m_list.Pop();
 if (lpEntry != NULL)
 {
 lpEntry->~DATA_ENTRY();
 }
 _aligned_free(lpEntry);
 }
 }
 USHORT Count()
 {
 return m_list.Depth();
 }
 LPDATA_ENTRY Push(const T& data)
 {
 LPVOID lpMemBuff = _aligned_malloc(sizeof(DATA_ENTRY), MEMORY_ALLOCATION_ALIGNMENT);
 LPDATA_ENTRY lpEntry = new (lpMemBuff) DATA_ENTRY(data);
 return (LPDATA_ENTRY)m_list.Push(lpEntry);
 }
 BOOL Pop(T& outVal)
 {
 BOOL bOut = FALSE;
 if (m_list.Depth() > 0)
 {
 LPDATA_ENTRY lpEntry = static_cast<LPDATA_ENTRY>(m_list.Pop());
 if (lpEntry != NULL)
 {
 outVal = lpEntry->Data;
 lpEntry->~DATA_ENTRY();
 _aligned_free(lpEntry);
 bOut = TRUE;
 }
 }
 return bOut;
 }
private:
 CSList m_list;
};

Answer 1

In TSimpleStack::Pop you don't need to check the depth as m_list.Pop() will return null if the stack is empty.

The repeated allocations and frees kind of rub me the wrong way. Instead you can add a CSList m_freeList; member and allocate from that:

DATA_ENTRY* AllocEntry(){
 DATA_ENTRY* result = m_freeList.Pop();
 if(!result) 
 result = _aligned_malloc(sizeof(DATA_ENTRY), MEMORY_ALLOCATION_ALIGNMENT);
 return result;
}
void FreeEntry(DATA_ENTRY* entry){
 m_freeList.Push(entry);
}

A destructor to CSList with at least an assert that m_head is empty.

CSList should probably disallow copying and moving. But TSimpleStack should definatley have a copy constructor and assignment operator (plus the move variants) to follow the rule of 3 (5) or disallow them which is saner because it is hard to ensure thread safety when copying/moving.

• Minor Threat: Thank you very much for your feedback. I've found another very serious issue in this code: 1) the Count() method is a useless O(N) waste for a linked list, 2) this particular implementation returns (count mod 2^16), hence it couldn't be reliably used for lists which size may exceed 65536 items. So, method like bool IsEmpty() based on RtlFirstEntrySList() should be implemented instead.

Answer 2

const correctness

A number of your member functions could (and in my opinion should) be const, but currently aren't. In a couple of cases we have functions that aren't "physically const", but are still "logically const", so they should be marked const. This means they don't change the visible state of the data structure, even though they might cause some changes in memory. For these cases, we mark the member function const, and add a const_cast to allow the const point to be passed to a function that takes a non-const pointer:

// Physically const
PSLIST_ENTRY First() const
{
 return ::RtlFirstEntrySList(&m_head);
}
// logically const:
USHORT Depth() const
{
 return ::QueryDepthSList(const_cast<PSLIST_HEADER>(&m_head));
}
PSLIST_ENTRY Flush() const
{
 return ::InterlockedFlushSList(const_cast<PSLIST_HEADER>(&m_head));
}

simpler code

At least in my opinion, some of the code can be simplified at least a little bit. For example, Pop can be rewritten to something like this:

BOOL Pop(T& outVal)
{
 if (m_list.Depth() > 0)
 {
 LPDATA_ENTRY lpEntry = static_cast<LPDATA_ENTRY>(m_list.Pop());
 if (lpEntry != NULL)
 {
 outVal = lpEntry->Data;
 lpEntry->~DATA_ENTRY();
 _aligned_free(lpEntry);
 return true;
 }
 }
 return false;
}

Some prefer the single-entry, single-exit style of code, but in my opinion, this code ends up simpler and cleaner this way.

Don't repeat yourself

Much of the code for TSimpleStack's destructor is basically the same as code in Pop. I think I'd change the code to use Pop instead:

size_t depth = Depth();
T temp;
for (int i=0; i<depth; i++)
 Pop(temp);

I'm tempted to recommend moving the memory allocation functionality into an Allocator object, but in this case that's probably more open to debate than usual--many of the functions you're using require aligned allocations, but at least in theory you could still switch to some other allocator that met the same requirements (e.g., possibly one that still used the same allocation functions, but also did things like keeping track of the memory usage.