Concurrent, lock free, inlined linked list?

1

Consider the following C struct:

struct LinkedList<T> {
  next: AtomicPtr<LinkedList<T>>,
  prev: AtomicPtr<LinkedList<T>>,
  data: T
}

and imagine we allocate a whole bunch of them at once via malloc.

====

Is there something like this for Rust, where we can return a LinkedList<T> or get a LinkedList<T> from a pool, and have all this be concurrent and lock free ?

I understand this can be done via Atomics. I am wondering if someone has already done this. Only working on x86_64 linux is fine.

2

I vaguely remember someone blogging that such data structure is not possible to do safely, because removal of pointers to an element doesn't mean there are no in-progress uses of the element anywhere (like reading the data). It's not possible to guarantee there are no outstanding users without having a lock on the whole element, so it's not possible to free memory in such lock-free list.

This is why crossbeam has a garbage collector:

3

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.