Do any array based, bounded, wait free stacks exist?

Question

I have a problem that requires me to use a highly concurrent, wait free implementation of a stack. I have to preallocate all memory (no garbage collection or mallocs) in advance and it is acceptable that the stack is bounded in size (push may return false if the stack if full).

I am familiar with the stack implementation from Nir Shavit: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.8728 ... But that relies on linked lists and garbage collection. I need something that is array based.

It looks like there is one on ACM here: http://dl.acm.org/citation.cfm?id=1532611 though I am sceptical about the low download rate and citations.

The ideal answer would be reference code (in C/C++) I could simply steal :-)

Answer 1

Have you looked at the windows DDI InterlockedPushEntrySList() and InterlockedPopEntrySList()? They are not array based but they are lock free and use processor atomic instructions to add and remove items from the stack. It is not wait free, but maybe it can be useful to you...