3
\$\begingroup\$

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<typename T, size_t N = 128>
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 < N; ++i) {
            _ptrbuf[i].s.ptr = 0;
            _ptrbuf[i].s.cnt = i*100 + i*3 + i;
        }
    }

    bool push(const T& in) {
        std::auto_ptr<T>    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;
            }
            // then increment the head; no other thread should access 'head'
            // while performing this increment
            __sync_fetch_and_add(&_head, 1);
            // return the value
            out = *lcl_ptr.s.ptr;
            delete lcl_ptr.s.ptr;
            return true;
        }
        return false;
    }
};
\$\endgroup\$
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You're right mate, good changes. Everything else looks ok, am i right? \$\endgroup\$ – Emanuele Dec 25 '15 at 12:24
  • \$\begingroup\$ @Emanuele Honestly I didn't realize this question was a year old. It showed up near the top one day and I looked at it. \$\endgroup\$ – JS1 Dec 25 '15 at 18:21
  • 1
    \$\begingroup\$ Not an issue at all, in fact I saw your useful review today whilst accessing codereview for a long time. Thanks again! \$\endgroup\$ – Emanuele Dec 25 '15 at 18:23
3
\$\begingroup\$
  • As of C++11, std::auto_ptr has been deprecated. Consider switching to another type of supported smart pointer, such as std::unique_ptr.

  • Your use of whitespace and indentation in some places is odd:

    ptrcnt      cur_ptr = _ptrbuf[_tail%N],
            next_ptr = cur_ptr;
    

    It's also more readable to declare/initialize one variable per line.

    ptrcnt cur_ptr = _ptrbuf[_tail%N];
    ptrcnt next_ptr = cur_ptr;
    
  • I don't know what's required of this type of assignment:

    cur_ptr.s.ptr = 0;
    

    If it's supposed to be a pointer type and not specifically an integer, then use nullptr:

    cur_ptr.s.ptr = nullptr;
    
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.