ThreadedLinkedList.cs

// Copyright 2020 Emzi0767
// 
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// 
//   http://www.apache.org/licenses/LICENSE-2.0
// 
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

using System;
using System.Collections;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Threading;

namespace ScratchPad
{
    public sealed class ThreadedLinkedList<T> : ICollection<T>
    {
        private Node _first;

        public int Count 
            => this.CountElements();

        public bool IsReadOnly 
            => false;

        public void Add(T item)
        {
            var node = new Node(item);

            if (this._first.HasValue)
            {
                var tail = this.GetLast();
                tail.SetNext(node);
            }
            else
                this._first = node;
        }

        public bool Remove(T item)
        {
            var node = this._first;
            var prev = node;
            while (node.HasValue)
            {
                if (Object.Equals(item, node.Value))
                {
                    var next = node.GetNext();
                    prev.SetNext(next);
                    node.Cleanup(false);

                    return true;
                }

                prev = node;
                node = node.GetNext();
            }

            return false;
        }

        public void Clear()
        {
            this._first.Cleanup(true);
            this._first = default;
        }

        public bool Contains(T item)
        {
            var node = this._first;
            while (node.HasValue)
            {
                if (Object.Equals(item, node.Value))
                    return true;

                node = node.GetNext();
            }

            return false;
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            var node = this._first;
            for (var i = arrayIndex; i < array.Length && node.HasValue; i++)
            {
                array[i] = node.Value;
                node = node.GetNext();
            }
        }

        public IEnumerator<T> GetEnumerator()
            => new Enumerator(this);

        IEnumerator IEnumerable.GetEnumerator()
            => new Enumerator(this);

        private int CountElements()
        {
            var node = this._first;
            var count = 0;
            while (node.HasValue)
            {
                count++;
                node = node.GetNext();
            }

            return count;
        }

        private Node GetLast()
        {
            if (!this._first.HasValue)
                return this._first;

            var node = this._first;
            while (node.HasNext())
                node = node.GetNext();

            return node;
        }

        private struct Node
        {
            [ThreadStatic]
            private static Node _next;

            public bool HasValue { get; }
            public T Value
                => this.HasValue ? this._value : throw new InvalidOperationException("This node has no value.");
            private readonly T _value;

            private readonly Thread _nodeThread;
            private readonly ConcurrentQueue<NodeThreadWorkItem> _nodeThreadWorkItems;

            public Node(T value)
            {
                this.HasValue = true;
                this._value = value;
                this._nodeThreadWorkItems = new ConcurrentQueue<NodeThreadWorkItem>();

                this._nodeThread = null; // fuck compilers
                this._nodeThread = new Thread(this.NodeThreadRunner);
                this._nodeThread.Start();
            }

            public Node GetNext()
            {
                Node next = default;
                var mre = new ManualResetEventSlim(false);
                this._nodeThreadWorkItems.Enqueue(new NodeThreadWorkItem
                {
                    Work = () =>
                    {
                        next = _next;
                        mre.Set();
                    }
                });
                mre.Wait();
                return next;
            }

            public void SetNext(Node next)
            {
                var mre = new ManualResetEventSlim(false);

                this._nodeThreadWorkItems.Enqueue(new NodeThreadWorkItem
                {
                    Work = () =>
                    {
                        _next = next;
                        mre.Set();
                    }
                });
                mre.Wait();
            }

            public bool HasNext()
            {
                bool has = false;
                var mre = new ManualResetEventSlim(false);
                this._nodeThreadWorkItems.Enqueue(new NodeThreadWorkItem
                {
                    Work = () =>
                    {
                        has = _next.HasValue;
                        mre.Set();
                    }
                });
                mre.Wait();
                return has;
            }

            public void Cleanup(bool recurse)
            {
                if (!this.HasValue)
                    return;

                var next = this.GetNext();
                this._nodeThreadWorkItems.Enqueue(new NodeThreadWorkItem { Work = () => throw new ThreadStopException() });
                this._nodeThread.Join();

                if (recurse)
                    next.Cleanup(recurse);
            }

            private void NodeThreadRunner()
            {
                _next = default;
                while (true)
                {
                    Thread.Yield();
                    if (!this._nodeThreadWorkItems.TryDequeue(out var item))
                        continue;

                    try
                    {
                        item.Work();
                    }
                    catch (ThreadStopException)
                    {
                        break;
                    }
                    catch { }
                }
            }

            private class NodeThreadWorkItem
            {
                public Action Work { get; set; }
            }
        }

        private class Enumerator : IEnumerator<T>
        {
            public T Current
                => this._current.Value;

            object IEnumerator.Current
                => this._current.Value;

            private Node _current;
            private ThreadedLinkedList<T> _list;
            private bool _started;

            public Enumerator(ThreadedLinkedList<T> list)
            {
                this._list = list;
            }

            public bool MoveNext()
            {
                if (!this._started)
                {
                    this._started = true;
                    this._current = this._list._first;
                    return this._current.HasValue;
                }

                if (!this._current.HasValue)
                    return false;

                this._current = this._current.GetNext();
                return this._current.HasValue;
            }

            public void Reset()
            {
                this._current = default;
                this._started = false;
            }

            public void Dispose()
            { }
        }

        private class ThreadStopException : Exception
        {
            public ThreadStopException()
                : base("Thread is stopping.")
            { }
        }
    }
}