// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
 
namespace System.Composition.Hosting.Util
{
    // Extremely performance-sensitive.
    // Always safe for reading, even under concurrent writes,
    // only one writer at a time allowed.
    internal sealed class SmallSparseInitonlyArray
    {
        private sealed class Element { public int Index; public object Value; }
 
        private const int ElementsCapacity = 128;
        private const int ElementIndexMask = 127;
        private const int LocalOffsetMax = 3;
 
        private Element[] _elements;
        private SmallSparseInitonlyArray _overflow;
 
        public void Add(int index, object value)
        {
            _elements ??= new Element[ElementsCapacity];
 
            var newElement = new Element { Index = index, Value = value };
 
            var elementIndex = index & ElementIndexMask;
            var e = _elements[elementIndex];
            if (e == null)
            {
                _elements[elementIndex] = newElement;
                return;
            }
 
            if (e.Index == index)
            {
                throw new ArgumentException(SR.Format(SR.Key_Already_Exist, index), nameof(index));
            }
 
            for (int offset = 1; offset <= LocalOffsetMax; ++offset)
            {
                var nextIndex = (index + offset) & ElementIndexMask;
                e = _elements[nextIndex];
                if (e == null)
                {
                    _elements[nextIndex] = newElement;
                    return;
                }
 
                if (e.Index == index)
                {
                    throw new ArgumentException(SR.Format(SR.Key_Already_Exist, index), nameof(index));
                }
            }
 
            _overflow ??= new SmallSparseInitonlyArray();
 
            _overflow.Add(index, value);
        }
 
        public bool TryGetValue(int index, out object value)
        {
            if (_elements == null)
            {
                value = null;
                return false;
            }
 
            var elementIndex = index & ElementIndexMask;
            var e = _elements[elementIndex];
            if (e != null && e.Index == index)
            {
                value = e.Value;
                return true;
            }
 
            for (int offset = 1; offset <= LocalOffsetMax; ++offset)
            {
                e = _elements[(index + offset) & ElementIndexMask];
                if (e == null)
                {
                    value = null;
                    return false;
                }
 
                if (e.Index == index)
                {
                    value = e.Value;
                    return true;
                }
            }
 
            if (_overflow != null)
                return _overflow.TryGetValue(index, out value);
 
            value = null;
            return false;
        }
    }
}