// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

#nullable enable

using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;

namespace Microsoft.CodeAnalysis.Collections.Internal
{
    internal static class SegmentedArrayHelper
    {
        // This is the threshold where Introspective sort switches to Insertion sort.
        // Empirically, 16 seems to speed up most cases without slowing down others, at least for integers.
        // Large value types may benefit from a smaller number.
        internal const int IntrosortSizeThreshold = 16;

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static int GetSegmentSize<T>()
        {
            return Unsafe.SizeOf<T>() switch
            {
                // Hard code common values since not all versions of the .NET JIT support reducing this computation to a
                // constant value at runtime. Values are validated against the reference implementation in
                // CalculateSegmentSize in unit tests.
                1 => 65536,
                2 => 32768,
                4 => 16384,
                8 => 8192,
                12 => 4096,
                16 => 4096,
                24 => 2048,
                28 => 2048,
                32 => 2048,
                40 => 2048,
                64 => 1024,
#if NETCOREAPP3_0_OR_GREATER
                _ => InlineCalculateSegmentSize(Unsafe.SizeOf<T>()),
#else
                _ => FallbackSegmentHelper<T>.SegmentSize,
#endif
            };
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static int GetSegmentShift<T>()
        {
            return Unsafe.SizeOf<T>() switch
            {
                // Hard code common values since not all versions of the .NET JIT support reducing this computation to a
                // constant value at runtime. Values are validated against the reference implementation in
                // CalculateSegmentSize in unit tests.
                1 => 16,
                2 => 15,
                4 => 14,
                8 => 13,
                12 => 12,
                16 => 12,
                24 => 11,
                28 => 11,
                32 => 11,
                40 => 11,
                64 => 10,
#if NETCOREAPP3_0_OR_GREATER
                _ => InlineCalculateSegmentShift(Unsafe.SizeOf<T>()),
#else
                _ => FallbackSegmentHelper<T>.SegmentShift,
#endif
            };
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        internal static int GetOffsetMask<T>()
        {
            return Unsafe.SizeOf<T>() switch
            {
                // Hard code common values since not all versions of the .NET JIT support reducing this computation to a
                // constant value at runtime. Values are validated against the reference implementation in
                // CalculateSegmentSize in unit tests.
                1 => 65535,
                2 => 32767,
                4 => 16383,
                8 => 8191,
                12 => 4095,
                16 => 4095,
                24 => 2047,
                28 => 2047,
                32 => 2047,
                40 => 2047,
                64 => 1023,
#if NETCOREAPP3_0_OR_GREATER
                _ => InlineCalculateOffsetMask(Unsafe.SizeOf<T>()),
#else
                _ => FallbackSegmentHelper<T>.OffsetMask,
#endif
            };
        }

        /// <summary>
        /// Calculates the maximum number of elements of size <paramref name="elementSize"/> which can fit into an array
        /// which has the following characteristics:
        /// <list type="bullet">
        /// <item><description>The array can be allocated in the small object heap.</description></item>
        /// <item><description>The array length is a power of 2.</description></item>
        /// </list>
        /// </summary>
        /// <param name="elementSize">The size of the elements in the array.</param>
        /// <returns>The segment size to use for small object heap segmented arrays.</returns>
        private static int CalculateSegmentSize(int elementSize)
        {
            // Default Large Object Heap size threshold
            // https://github.com/dotnet/runtime/blob/c9d69e38d0e54bea5d188593ef6c3b30139f3ab1/src/coreclr/src/gc/gc.h#L111
            const int Threshold = 85000;

            var segmentSize = 2;
            while (ArraySize(elementSize, segmentSize << 1) < Threshold)
            {
                segmentSize <<= 1;
            }

            return segmentSize;

            static int ArraySize(int elementSize, int segmentSize)
            {
                // Array object header, plus space for the elements
                return (2 * IntPtr.Size + 8) + (elementSize * segmentSize);
            }
        }

        /// <summary>
        /// Calculates a shift which can be applied to an absolute index to get the page index within a segmented array.
        /// </summary>
        /// <param name="segmentSize">The number of elements in each page of the segmented array. Must be a power of 2.</param>
        /// <returns>The shift to apply to the absolute index to get the page index within a segmented array.</returns>
        private static int CalculateSegmentShift(int segmentSize)
        {
            var segmentShift = 0;
            while (0 != (segmentSize >>= 1))
            {
                segmentShift++;
            }

            return segmentShift;
        }

        /// <summary>
        /// Calculates a mask, which can be applied to an absolute index to get the index within a page of a segmented
        /// array.
        /// </summary>
        /// <param name="segmentSize">The number of elements in each page of the segmented array. Must be a power of 2.</param>
        /// <returns>The bit mask to obtain the index within a page from an absolute index within a segmented array.</returns>
        private static int CalculateOffsetMask(int segmentSize)
        {
            Debug.Assert(segmentSize == 1 || (segmentSize & (segmentSize - 1)) == 0, "Expected size of 1, or a power of 2");
            return segmentSize - 1;
        }

        // Faster inline implementation for NETCOREAPP to avoid static constructors and non-inlineable
        // generics with runtime lookups
#if NETCOREAPP3_0_OR_GREATER
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int InlineCalculateSegmentSize(int elementSize)
        {
            return 1 << InlineCalculateSegmentShift(elementSize);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int InlineCalculateSegmentShift(int elementSize)
        {
            // Default Large Object Heap size threshold
            // https://github.com/dotnet/runtime/blob/c9d69e38d0e54bea5d188593ef6c3b30139f3ab1/src/coreclr/src/gc/gc.h#L111
            const uint Threshold = 85000;
            return System.Numerics.BitOperations.Log2((uint)((Threshold / elementSize) - (2 * Unsafe.SizeOf<object>() + 8)));
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int InlineCalculateOffsetMask(int elementSize)
        {
            return InlineCalculateSegmentSize(elementSize) - 1;
        }
#endif

        internal static class TestAccessor
        {
            public static int CalculateSegmentSize(int elementSize)
                => SegmentedArrayHelper.CalculateSegmentSize(elementSize);

            public static int CalculateSegmentShift(int segmentSize)
                => SegmentedArrayHelper.CalculateSegmentShift(segmentSize);

            public static int CalculateOffsetMask(int segmentSize)
                => SegmentedArrayHelper.CalculateOffsetMask(segmentSize);
        }

#if !NETCOREAPP3_0_OR_GREATER
        private static class FallbackSegmentHelper<T>
        {
            public static readonly int SegmentSize = CalculateSegmentSize(Unsafe.SizeOf<T>());
            public static readonly int SegmentShift = CalculateSegmentShift(SegmentSize);
            public static readonly int OffsetMask = CalculateOffsetMask(SegmentSize);
        }
#endif
    }
}