I need a concurrent data structure with the following properties:
- Low overhead for enumeration
- Insert only at end.
- Removal from any point.
- Enumeration should be safe with concurrent writing
- Enumeration does not require the list to be in a constant state
- Not a problem if I enumerate over removed items
I have designed the following linked list class which should meet my requirements.
using System.Collections;
using System.Collections.Generic;
internal class ConcurrentLinkedList<T> : IEnumerable<Node<T>> {
private readonly BaseNode<T> _root;
private BaseNode<T> _end;
public ConcurrentLinkedList() {
_end = _root = new BaseNode<T>();
}
public Node<T> Insert(T value) {
var node = new Node<T>(value);
lock (node) {
lock (_end) {
node.Previous = _end;
_end = _end.Next = node;
return node;
}
}
}
public void Remove(Node<T> node) {
lock (node.Previous) {
lock (node) {
if (node.Next == null) {
if (node.Previous.Next != node) return;
node.Previous.Next = null;
if (_end == node) _end = node.Previous;
} else {
lock (node.Next) {
if (node.Previous.Next == node) node.Previous.Next = node.Next;
if (node.Next.Previous == node) node.Next.Previous = node.Previous;
}
}
}
}
}
public IEnumerator<Node<T>> GetEnumerator() {
for (var current = _root.Next; current != null; current = current.Next) {
yield return current;
}
}
IEnumerator IEnumerable.GetEnumerator() {
return GetEnumerator();
}
}
internal class BaseNode<T> {
internal volatile Node<T> Next;
}
internal class Node<T> : BaseNode<T> {
internal BaseNode<T> Previous;
public T Value { get; }
public Node(T value) {
Value = value;
}
}
I am aware the calls is vary easy to misuse but as it is only for internal use i am not concerned about this. I am considering making the all the class private subclass to ensure that there is no accidental misuse.
In the code all the writing is in a lock but there are shared volatile which are read out of lock. Apart from the possibility of enumerating deleted nodes, is there any other danger with this?
For the locking, I lock no all the node being changed. This should allow other parts of the list to be concurrency modified, the list can get long. Is this sufficient?
To avoid deadlock I always lock from the lowest node to the last.
Is the provided locking sufficient to protect the _end
field? I believe that according to the logic used the current _end
will always be locked when changing the value of _end
. Is this sufficient?
Is this code trying to be too clever and would it better to either:
- have one write lock and continue using the volatile for reading.
- use a standard
ReadWriteLock
for the whole list.
_end
points to the same object as_root
._end.Next
is assigned to. \$\endgroup\$readonly _root
is the only internal-persistent node,_end
is just a pointer to last node. My apologies. \$\endgroup\$