Skip to content

Instantly share code, notes, and snippets.

@jbandela
Last active January 14, 2025 09:46
Show Gist options
  • Select an option

  • Save jbandela/6073640 to your computer and use it in GitHub Desktop.

Select an option

Save jbandela/6073640 to your computer and use it in GitHub Desktop.
Atomic singly linked list
#include <atomic>
#include <memory>
#include <iterator>
#include <utility>
#include <assert.h>
//
// Lock free singly-linked using shared_ptr (if atomic_* for shared_ptr is lock_free)
// You can get the head, and push_front
// You can replace the head
// You may not change data
// You can only use push_front to add to a list
template<class T>
class slist{
class node{
std::shared_ptr<node> next_;
std::shared_ptr<const T> data_;
public:
std::shared_ptr<node> next(){
return next_;
}
std::shared_ptr<const T> data(){
return data_;
}
node(const std::shared_ptr<node>& n, const std::shared_ptr<const T> d):next_(n),data_(d){}
};
class slist_iterator : public std::iterator<std::forward_iterator_tag, const T>{
std::shared_ptr<node> node_;
public:
slist_iterator(){};
slist_iterator(const std::shared_ptr <node>& n) : node_(n){}
bool operator==(const slist_iterator& other)const{
return node_ == other.node_;
}
bool operator!=(const slist_iterator& other)const{
return node_ != other.node_;
}
// prefix
slist_iterator& operator++()
{
assert(node_);
auto n = node_->next();
node_ = n;
return *this;
}
// postfix
slist_iterator operator++(int)
{
assert(node_);
slist_iterator tmp(node_);
operator++(); // prefix-increment this instance
return tmp; // return value before increment
}
const T& operator*(){
assert(node_);
return *(node_->data());
}
std::shared_ptr<node> node(){
return node_;
}
};
std::shared_ptr < node> head_;
public:
slist() : head_(nullptr){}
bool empty(){ return (head().get() == nullptr); }
void push_front(const std::shared_ptr<const T>& h){
auto n = std::make_shared<node>(head(),h);
replace_head(n);
}
template<class... P>
void emplace_front(P&&... p){
auto n = std::make_shared<node>(head(),std::make_shared<const T>(std::forward<P>(p)...));
replace_head(n);
}
std::shared_ptr<node> head(){
return std::atomic_load(&head_);
}
void replace_head(const std::shared_ptr < node >& h){
std::atomic_store(&head_,h);
}
slist_iterator begin(){
return slist_iterator{head()};
}
slist_iterator end(){
return slist_iterator{};
}
slist_iterator cbegin()const{
return slist_iterator{head()};
}
slist_iterator cend()const{
return slist_iterator{};
}
// Non-copyable non-movable
private:
slist(const slist&);
slist& operator=(const slist&) ;
slist(const slist&&);
slist& operator=(const slist&&) ;
};
#include <string>
#include <iostream>
int main(){
slist<std::string> s;
s.emplace_front(std::string("Hello"));
s.push_front(std::make_shared<const std::string>("World"));
for (auto& pstr : s){
std::cout << pstr;
}
for (auto iter = s.begin(); iter != s.end(); ++iter){
auto n = iter.node();
}
slist<std::string> s2;
s2.emplace_front("C++");
s2.emplace_front("Go");
s.replace_head(s2.head());
s2.replace_head(nullptr);
for (auto& pstr : s){
std::cout << pstr;
}
}
@APokorny

Copy link
Copy Markdown

This is not atomic. There is a data update race between line 95 and 96, you first load head - use head as next for the new element then replace head. Multiple threads could load the same state of head in 95, prior to setting the new state of head in 96.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment