ConcurrentNonShiftingList.cs

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace ABSoftware.ABSave.Helpers
{
    /// <summary>
    /// A thread-safe list that can be iterated many times at once but can't be modified at the same time.
    /// </summary>
    internal class ConcurrentNonShiftingList<T>
    {
        public int Length { get; private set; }
        List<T> _data = new List<T>(8);
        Stack<int> _freeSpaces;

        // Used to lock the variable when possibly going from modifying to iterating 
        // or iterating to modifying.
        SpinLock _stateChanging;

        volatile bool _currentlyModifying;
        volatile int _currentlyIterating;
        
        ManualResetEventSlim _modifyWait = new ManualResetEventSlim();
        ManualResetEventSlim _iterationWait = new ManualResetEventSlim();

        public void EnterIterationLock()
        {
            bool lockAcquired = false;

            try
            {
                _stateChanging.Enter(ref lockAcquired);
                WaitForNotModifying();
                _currentlyIterating++;
            }
            finally
            {
                if (lockAcquired) _stateChanging.Exit();
            }
        }

        public void ExitIterationLock()
        {
            Interlocked.Decrement(ref _currentlyIterating);
        }

        public void Add(T item)
        {
            LockModification();

            // If there are no free spaces, try to place at the end of the array.
            if (_freeSpaces.Count == 0)
            {
                if (Length > _data.Length)
                    Array.Resize(ref _data, _data.Length * 2);

                _data[Length++] = item;
            }
            else _data[_freeSpaces.Pop()] = item;

            _data[Length++] = item;

            // Stop modifying.
            _currentlyModifying = false;
            _modifyWait.Set();
        }

        public void Remove(int index)
        {
            LockModification();
            _freeSpaces.Push(index);
        }

        private void LockModification()
        {
            bool lockAcquired = false;

            try
            {
                _stateChanging.Enter(ref lockAcquired);

                WaitForNotModifying();

                // While "_stateChanging" is locked, we know "_currentIterating" will only ever decrease
                // and never increase. So we don't need to worry about it going up.
                var wait = new SpinWait();
                while (_currentlyIterating > 0) wait.SpinOnce();

                _modifyWait.Reset();
            }
            finally
            {
                if (lockAcquired) _stateChanging.Exit();
            }
        }


        void WaitForNotModifying()
        {
            if (_currentlyModifying) _modifyWait.Wait();            
        }

        T this[int index] => _data[index];
    }
}