Multi-threaded lock-free doubly linked list using free-list

Stack Overflow Asked by Bruce Shen on October 19, 2020

I want a concurrent data structure that works like a singly linked list and only needs append and remove_iterator operations. In the end, one thread will iterate all nodes. From my research, I got an implementation that has append, remove_value and search_value operations with singly-linked lists. It is based on Harris’ algorithm.

The problem is that in Harris’ algorithm, remove_value only marks a node logically deleted, without actually delete it. search_value actually do the chores of removing logically deleted nodes. But since I don’t have a search operation for my use case. I keep a long list with lots of logically deleted nodes. It is just not efficient for speed in multi-threading, because all the work of deleting nodes is put on the iterate operation within a single thread.

I wonder if there are any other implementations that fit my needs. Any recommendation is appreciated.

If not, I wonder if I can implement something for this special case using a free-list with a lock-free stack implementation. In this case, an append operation becomes pop free-list, either put value to the node or append to our list if empty. A remove_iterator operation becomes mark the node logically removed, and push the node pointer to free-list.

I think lock-free stack if fairly easy to implement. I can use some implementations online.

Some code in mind.

struct node_t {
    node_t *next;
    int deleted;
    val_t val;
struct list_t {
    node_t *head;
struct fl_node_t {
    node_t *padding_1;
    int padding_2;
    fl_node_t *next; // assume sizeof(val_t) >= sizeof(fl_node_t*);

struct free_list_t {
    fl_node_t * head;
void append(val_t val) {
    fl_node_t *fl_head;
    fl_node_t *fl_next;
    node_t *head;
    node_t *new_node
    /* Try insert to one of the node in free-list */
    if (free_list.head) {
        do {
            fl_head = free_list.head;
            next = fl_head->next;
        } while(!CAS(&free_list.head, fl_head, fl_next)); 
        if (fl_head) {
           fl_head->node->val = val; 
    /* Append to head */
    new_node = malloc(sizeof(node_t));
    new_node.val = val;
    new_node.deleted = 0;
    do {
        head = list.head; = head;
    } while(!CAS(&list.head, head, new_node));

void remove(node_t *node) {
    fl_node_t *fl_node;
    fl_node_t *fl_head;

    /* Mark logically deleted */
    node->deleted = 1;
    fl_node = (fl_node_t*) node;

    /* Add to free-list */
    do {
        fl_head = free_list.head;
        fl_node->next =fl_head;
    } while(!CAS(&free_list.head, fl_head, fl_node)); 

2 Answers

I found gavra0's implementation on github. With a modification by adding a free-list (using lock-free stack implementation), I got some working code.

The repository is And the implementation is in this link in the dev branch.

Correct answer by Bruce Shen on October 19, 2020

When it comes to Lock free and wait free data structures, rather than try to reinvent the wheel or fix something and spend ages trying to prove that it's right, use a proven existing implementation where possible.

Lock free implementations are notoriously hard to get right and difficult to prove right. What is right on one CPU architecture, may be wrong on another.

In practice, where we've had to use them for performance reasons they can go and go, and then one day blow up. We've had good success with implementations adapted from here

He also has references to other libraries and provides good insight into concurrent programming. Well worth a read.

Answered by Matt on October 19, 2020

Add your own answers!

Related Questions

Avast blocks pip and Pyinstaller

1  Asked on December 9, 2020 by dripis


Trying to grasp callbacks javascript

2  Asked on December 9, 2020 by justaordinarymonkey


Typescript get distinct values from an object

3  Asked on December 9, 2020 by nikhila-reddy-c


Strip n from list created from txt file

1  Asked on December 9, 2020 by nataku62


Find match pattern and delete the first occurrence

4  Asked on December 8, 2020 by neha-choudhary


Weird scoping behavior in python

1  Asked on December 8, 2020 by snickerdoodles777


Sqlite foreign key mismatch?

1  Asked on December 8, 2020 by daisy


pandas remove for loop

1  Asked on December 8, 2020 by arne


Change File with extension txt to json in C#

0  Asked on December 8, 2020 by azeter09


Appending an item from one list to another

3  Asked on December 8, 2020 by retroactive


Combine two Xcode targets into one distributable app

1  Asked on December 8, 2020 by thecoolwinter


Sorting multi-index pd.Series using pd.Categorical?

2  Asked on December 8, 2020 by np8


Trying to map an Array to an Object – Javascript

3  Asked on December 7, 2020 by mike-varela


Ask a Question

Get help from others!

© 2023 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP