patterncppMinor

C++11 lock free collection similar to std::forward_list - follow-up

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

thread-safety codereview cpp c++stackoverflow c++11 lock-free collections

stdfreecollectionforward_listfollowsimilarlock

Problem

This question has been superseded by C++11 lock free collection similar to std::forward_list - follow-up 2

Thread safe and lock free collections are very hard to write, so I'd appreciate any feedback, especially regarding bugs. The code below is a self contained cpp including some tests.

This question is a new iteration of the closed question:

https://codereview.stackexchange.com/questions/77293/c11-lock-free-collection-similar-to-stdforward-list

all methods are thread safe, baring the destructor

push, insert, pop, erase and iterator increment/dereference are O(1)

locks that do occur are per-element spin locks

push and insert operations are lock free.

clear is lock free

pop and erase are not lock free.

separate and concat are lock free, and can be used to almost do a lock free pop or erase.

begin, cbegin and incrementing iterators are not lock free

dereferencing iterators is lock free

uses reference counting to preserve iterators (and values) of removed elements

iterators of removed elements will increment to end()

insert_after or emplace_after on a removed iterator will return end() to indicate failure.

In addition to the creative commons license for code on this site, you may also use it under the MIT license.

```
// Is noexcept supported?
#if defined(__clang__) && __has_feature(cxx_noexcept) || \
defined(__GXX_EXPERIMENTAL_CXX0X__) && __GNUC__ * 10 + __GNUC_MINOR__ >= 46 || \
defined(_MSC_FULL_VER) && _MSC_FULL_VER >= 180021114
# define NOEXCEPT noexcept
#else
# define NOEXCEPT
#endif

#include
#include

inline void* lock_free_forward_list_get_deadDummy() {
static std::unique_ptr deadDummy_(new void* ());
return deadDummy_.get();
}

inline void* lock_free_forward_list_get_spinDummy() {
static std::unique_ptr spinDummy_(new void* ());
return spinDummy_.get();
}

#define deadDummy ((node*)lock_free_forward_list_get_deadDummy())
#define spinDummy ((node*)lock_free_forward

Solution

In order to get your code to compile, I needed to add #include , #include , and change ` to

 as suggested below.

inline void* lock_free_forward_list_get_deadDummy() {
    static std::unique_ptr deadDummy_(new void* ());
    return deadDummy_.get();
}


This is needlessly complicated (and confusing, because you reuse the name

void*

 for both the return value and the unrelated type pointed-to by the return value). I recommend

inline void* lock_free_forward_list_get_deadDummy() {
    static int dummy;
    return &dummy;
}


This gets you a globally unique

void* value, without the overhead of dynamic memory allocation. Also, notice that the thread-safe initialization of deadDummy_ in your original code will take a lock (for example, via __cxa_guard_acquire/__cxa_guard_release on OSX) because it needs to ensure that new

 is invoked only once. The plain-old-data version I recommend will not take a lock. (Verify by looking at the generated assembly code with

-O3 -S

.)

#define deadDummy ((node*)lock_free_forward_list_get_deadDummy())


This pollutes the user's namespace. I'm a strong advocate for the use of C-style macros, but this is not an appropriate place for one. Just make a static member function and resign yourself to typing those extra parentheses

()

:

static node* deadDummy() { return (node*)lock_free_forward_list_get_deadDummy(); }


You could reduce your typing a lot more if you made

static node deadDummy; a member of lock_free_forward_list

. I assume you wanted to avoid that bloat, so I will refrain from suggesting any refactor that would increase your memory footprint.

template
class ForwardIterator;


Excellently correct! Although I'd recommend

class CT instead of class T just to avoid confusion between the T in lock_free_forward_list and the CT in lock_free_forward_list::ForwardIterator. (These CTs will always be one or the other of T or const T

.)

EDITED TO ADD: in fact, Clang on OSX rejects the original code!

test.cc:51:20: error: declaration of 'T' shadows template parameter
    template
                   ^


T &operator*() { return current->value; }
T &operator->() { return current->value; }
ForwardIterator operator++()


The last should return

ForwardIterator& to avoid making an unnecessary copy, and the first two should be const

.

T &operator*() const { return current->value; }
T &operator->() const { return current->value; }
ForwardIterator& operator++()


friend void swap(ForwardIterator& a, ForwardIterator& b) NOEXCEPT
    {
        using std::swap; // bring in swap for built-in types
        std::swap(a.current, b.current);
    }


You brought in

std::swap

 for ADL, but then you didn't actually use ADL! You meant

using std::swap;
swap(a.current, b.current);


or simply (without ADL)

std::swap(a.current, b.current);


Consider making your

ForwardIterator::operator== a template, so that l.begin() == l.cbegin()

 works. (Right now it doesn't work.) Audit your code for issues with comparison/assignment of const_iterators to iterators and vice versa.

node(T const &value) : value(value), next(nullptr), referenceCount(1) {}
node(T &&value) : value(std::move(value)), next(nullptr), referenceCount(1) {}
template
node(U... params) : value(std::forward(params)...), next(nullptr), referenceCount(1) {}


You're doing forwarding wrong. Remove these constructors, and replace them with a single correctly written forwarding constructor:

template
node(U&&... params) : value(std::forward(params)...), next(nullptr), referenceCount(1) {}


Notice the added

&& and . You should never ever use std::forward

 without angle brackets, and you should never use it on anything that isn't a forwarding reference.

static void loseOwnership(node *&n, std::memory_order loadOrder, std::memory_order storeOrder) {


I don't understand the point of passing around both

loadOrder and storeOrder all the time, especially to methods such as loseOwnership() which don't use either of them (but instead use combine_memory_order(loadOrder, storeOrder)); and then in other places you hardcode memory_order_seq_cst, which seems to obviate all this messing around with memory orders in the first place. And then in methods such as exchange()

, you allow passing in a memory order at runtime, even though I'm pretty sure it doesn't make any sense; if you passed in the wrong order by accident, your spinlock wouldn't work! What would this code look like if you just "constant-propagated" the memory orders through the code everywhere possible?

See https://stackoverflow.com/questions/13941136/why-is-memory-order-given-as-a-runtime-argument-to-stdatomic-functions for more information on how C++11 expects you to use memory-order hints. I'm no expert myself, but I would recommend using the following "traits" idiom to enable compiler optimization:

``
struct foo_order {
static const

Code Snippets

inline void* lock_free_forward_list_get_deadDummy() {
    static std::unique_ptr<void*> deadDummy_(new void* ());
    return deadDummy_.get();
}

inline void* lock_free_forward_list_get_deadDummy() {
    static int dummy;
    return &dummy;
}

#define deadDummy ((node*)lock_free_forward_list_get_deadDummy())

static node* deadDummy() { return (node*)lock_free_forward_list_get_deadDummy(); }

template<class T>
class ForwardIterator;

Context

StackExchange Code Review Q#77840, answer score: 5

Revisions (0)

No revisions yet.