Multi producer/consumers lockfree list

As per a similar question, following a lockfree list implementation. Note that this list has a pre-defined maximum set of elements which can be inserted (N argument in the template declaration). Please let me know if I've missed anything.

```
// Lockfree FIFO list, with N pre-allocated slots
template
class list {
typedef union {
struct {
T *ptr;
size_t cnt;
} s;
__int128 intv;
} ptrcnt;

volatile size_t _head,
_tail;
ptrcnt _ptrbuf[N];
public:
// Initialise elements' cnt with a non-equal seed
list() {
_head = _tail = 0;
for(size_t i = 0; i v(new T(in));
while(true) {
// first, prepare pointer to use next
ptrcnt cur_ptr = _ptrbuf[_tail%N],
next_ptr = cur_ptr;
cur_ptr.s.ptr = 0;
next_ptr.s.ptr = v.get();
++next_ptr.s.cnt;
if(_tail - _head >= N) {
break;
}
// add new element
if(!__sync_bool_compare_and_swap(&_ptrbuf[_tail%N].intv, cur_ptr.intv, next_ptr.intv)) {
continue;
}
// if we're after this point, no other thread should have
// accessd the slot, set the tail
__sync_fetch_and_add(&_tail, 1);
// all done, return true
v.release();
return true;
}
return false;
}

bool pop(T& out) {
while(true) {
// get current pointer, then swap
ptrcnt lcl_ptr = _ptrbuf[_head%N],
next_ptr = lcl_ptr;
next_ptr.s.ptr = 0;
++next_ptr.s.cnt;
if(!lcl_ptr.s.ptr || _head == _tail) {
return false;
}
// first, swap pointer to use next
if(!__sync_bool_compare_and_swap(&_ptrbuf[_head%N].intv, lcl_ptr.intv, next_ptr.intv)) {
continue;

Problem with pop

Your pop() function could return false when there are still elements in the list. The problem is with this check:

if(!lcl_ptr.s.ptr || _head == _tail) {
          return false;
      }

Here, lcl_ptr.s.ptr could be NULL if some other thread just popped that element. If that happens, you should just move on to the next element instead of returning false. So for example:

if (_head == _tail) {
          return false;
      }
      if (!lcl_ptr.s.ptr) {
          continue;
      }

This solution spins until the other thread finishes incrementing the head pointer. There may be better ways of handling this case which involve searching forward for an element to pop.

StackExchange Code Review Q#38166, answer score: 5