#nullable disable

namespace SharpCompress.Compressors.PPMd.I1;

/// Allocate a single, large array and then provide sections of this array to callers.  Callers are provided with
/// instances of <see cref="Pointer"/> (which simply contain a single address value, representing a location
/// in the large array).  Callers can then cast <see cref="Pointer"/> to one of the following structures (all
/// of which also simply contain a single address value):
internal class Allocator
{
    private const uint UNIT_SIZE = 12;
    private const uint LOCAL_OFFSET = 4; // reserve the first four bytes for Pointer.Zero
    private const uint NODE_OFFSET = LOCAL_OFFSET + MemoryNode.SIZE; // reserve space for a single memory node

    private const uint HEAP_OFFSET = NODE_OFFSET + (INDEX_COUNT * MemoryNode.SIZE);

    // reserve space for the array of memory nodes

    private const uint N1 = 4;
    private const uint N2 = 4;
    private const uint N3 = 4;
    private const uint N4 = (128 + 3 - (1 * N1) - (2 * N2) - (3 * N3)) / 4;
    private const uint INDEX_COUNT = N1 + N2 + N3 + N4;

    private static readonly byte[] INDEX_TO_UNITS;
    private static readonly byte[] UNITS_TO_INDEX;

    public uint _allocatorSize;
    public uint _glueCount;
    public Pointer _baseUnit;
    public Pointer _lowUnit;
    public Pointer _highUnit;
    public Pointer _text;
    public Pointer _heap;
    public MemoryNode[] _memoryNodes;

    public byte[] _memory;

    /// <summary>
    /// Initializes static read-only arrays used by the <see cref="Allocator"/>.
    /// </summary>
    static Allocator()
    {
        // Construct the static index to units lookup array.  It will contain the following values.
        //
        // 1 2 3 4 6 8 10 12 15 18 21 24 28 32 36 40 44 48 52 56 60 64 68 72 76 80 84 88 92 96 100 104 108
        // 112 116 120 124 128

        uint index;
        uint unitCount;

        INDEX_TO_UNITS = new byte[INDEX_COUNT];

        for (index = 0, unitCount = 1; index < N1; index++, unitCount += 1)
        {
            INDEX_TO_UNITS[index] = (byte)unitCount;
        }

        for (unitCount++; index < N1 + N2; index++, unitCount += 2)
        {
            INDEX_TO_UNITS[index] = (byte)unitCount;
        }

        for (unitCount++; index < N1 + N2 + N3; index++, unitCount += 3)
        {
            INDEX_TO_UNITS[index] = (byte)unitCount;
        }

        for (unitCount++; index < N1 + N2 + N3 + N4; index++, unitCount += 4)
        {
            INDEX_TO_UNITS[index] = (byte)unitCount;
        }

        // Construct the static units to index lookup array.  It will contain the following values.
        //
        // 00 01 02 03 04 04 05 05 06 06 07 07 08 08 08 09 09 09 10 10 10 11 11 11 12 12 12 12 13 13 13 13
        // 14 14 14 14 15 15 15 15 16 16 16 16 17 17 17 17 18 18 18 18 19 19 19 19 20 20 20 20 21 21 21 21
        // 22 22 22 22 23 23 23 23 24 24 24 24 25 25 25 25 26 26 26 26 27 27 27 27 28 28 28 28 29 29 29 29
        // 30 30 30 30 31 31 31 31 32 32 32 32 33 33 33 33 34 34 34 34 35 35 35 35 36 36 36 36 37 37 37 37

        UNITS_TO_INDEX = new byte[128];

        for (unitCount = index = 0; unitCount < 128; unitCount++)
        {
            index += (uint)((INDEX_TO_UNITS[index] < unitCount + 1) ? 1 : 0);
            UNITS_TO_INDEX[unitCount] = (byte)index;
        }
    }

    #region Public Methods

    public Allocator() => _memoryNodes = new MemoryNode[INDEX_COUNT];

    /// <summary>
    /// Initialize or reset the memory allocator (so that the single, large array can be re-used without destroying
    /// and re-creating it).
    /// </summary>
    public void Initialize()
    {
        for (var index = 0; index < INDEX_COUNT; index++)
        {
            _memoryNodes[index] = new MemoryNode(
                (uint)(NODE_OFFSET + (index * MemoryNode.SIZE)),
                _memory
            );
            _memoryNodes[index].Stamp = 0;
            _memoryNodes[index].Next = MemoryNode.ZERO;
            _memoryNodes[index].UnitCount = 0;
        }

        _text = _heap;

        var difference = UNIT_SIZE * (_allocatorSize / 8 / UNIT_SIZE * 7);

        _highUnit = _heap + _allocatorSize;
        _lowUnit = _highUnit - difference;
        _baseUnit = _highUnit - difference;

        _glueCount = 0;
    }

    /// <summary>
    /// Start the allocator (create a single, large array of bytes).
    /// </summary>
    /// <remarks>
    /// Note that .NET will create that array on the large object heap (because it is so large).
    /// </remarks>
    /// <param name="allocatorSize"></param>
    public void Start(int allocatorSize)
    {
        var size = (uint)allocatorSize;
        if (_allocatorSize != size)
        {
            Stop();
            _memory = new byte[HEAP_OFFSET + size]; // the single, large array of bytes
            _heap = new Pointer(HEAP_OFFSET, _memory); // reserve bytes in the range 0 .. HeapOffset - 1
            _allocatorSize = size;
        }
    }

    /// <summary>
    /// Stop the allocator (free the single, large array of bytes).  This can safely be called multiple times (without
    /// intervening calls to <see cref="Start"/>).
    /// </summary>
    /// <remarks>
    /// Because the array is on the large object heap it may not be freed immediately.
    /// </remarks>
    public void Stop()
    {
        if (_allocatorSize != 0)
        {
            _allocatorSize = 0;
            _memory = null;
            _heap = Pointer.ZERO;
        }
    }

    /// <summary>
    /// Determine how much memory (from the single, large array) is currenly in use.
    /// </summary>
    /// <returns></returns>
    public uint GetMemoryUsed()
    {
        var memoryUsed = _allocatorSize - (_highUnit - _lowUnit) - (_baseUnit - _text);
        for (uint index = 0; index < INDEX_COUNT; index++)
        {
            memoryUsed -= UNIT_SIZE * INDEX_TO_UNITS[index] * _memoryNodes[index].Stamp;
        }
        return memoryUsed;
    }

    /// <summary>
    /// Allocate a given number of units from the single, large array.  Each unit is <see cref="UNIT_SIZE"/> bytes
    /// in size.
    /// </summary>
    /// <param name="unitCount"></param>
    /// <returns></returns>
    public Pointer AllocateUnits(uint unitCount)
    {
        uint index = UNITS_TO_INDEX[unitCount - 1];
        if (_memoryNodes[index].Available)
        {
            return _memoryNodes[index].Remove();
        }

        var allocatedBlock = _lowUnit;
        _lowUnit += INDEX_TO_UNITS[index] * UNIT_SIZE;
        if (_lowUnit <= _highUnit)
        {
            return allocatedBlock;
        }

        _lowUnit -= INDEX_TO_UNITS[index] * UNIT_SIZE;
        return AllocateUnitsRare(index);
    }

    /// <summary>
    /// Allocate enough space for a PpmContext instance in the single, large array.
    /// </summary>
    /// <returns></returns>
    public Pointer AllocateContext()
    {
        if (_highUnit != _lowUnit)
        {
            return (_highUnit -= UNIT_SIZE);
        }
        if (_memoryNodes[0].Available)
        {
            return _memoryNodes[0].Remove();
        }
        return AllocateUnitsRare(0);
    }

    /// <summary>
    /// Increase the size of an existing allocation (represented by a <see cref="Pointer"/>).
    /// </summary>
    /// <param name="oldPointer"></param>
    /// <param name="oldUnitCount"></param>
    /// <returns></returns>
    public Pointer ExpandUnits(Pointer oldPointer, uint oldUnitCount)
    {
        uint oldIndex = UNITS_TO_INDEX[oldUnitCount - 1];
        uint newIndex = UNITS_TO_INDEX[oldUnitCount];

        if (oldIndex == newIndex)
        {
            return oldPointer;
        }

        var pointer = AllocateUnits(oldUnitCount + 1);

        if (pointer != Pointer.ZERO)
        {
            CopyUnits(pointer, oldPointer, oldUnitCount);
            _memoryNodes[oldIndex].Insert(oldPointer, oldUnitCount);
        }

        return pointer;
    }

    /// <summary>
    /// Decrease the size of an existing allocation (represented by a <see cref="Pointer"/>).
    /// </summary>
    /// <param name="oldPointer"></param>
    /// <param name="oldUnitCount"></param>
    /// <param name="newUnitCount"></param>
    /// <returns></returns>
    public Pointer ShrinkUnits(Pointer oldPointer, uint oldUnitCount, uint newUnitCount)
    {
        uint oldIndex = UNITS_TO_INDEX[oldUnitCount - 1];
        uint newIndex = UNITS_TO_INDEX[newUnitCount - 1];

        if (oldIndex == newIndex)
        {
            return oldPointer;
        }

        if (_memoryNodes[newIndex].Available)
        {
            Pointer pointer = _memoryNodes[newIndex].Remove();
            CopyUnits(pointer, oldPointer, newUnitCount);
            _memoryNodes[oldIndex].Insert(oldPointer, INDEX_TO_UNITS[oldIndex]);
            return pointer;
        }
        SplitBlock(oldPointer, oldIndex, newIndex);
        return oldPointer;
    }

    /// <summary>
    /// Free previously allocated space (the location and amount of space to free must be specified by using
    /// a <see cref="Pointer"/> to indicate the location and a number of units to indicate the amount).
    /// </summary>
    /// <param name="pointer"></param>
    /// <param name="unitCount"></param>
    public void FreeUnits(Pointer pointer, uint unitCount)
    {
        uint index = UNITS_TO_INDEX[unitCount - 1];
        _memoryNodes[index].Insert(pointer, INDEX_TO_UNITS[index]);
    }

    public void SpecialFreeUnits(Pointer pointer)
    {
        if (pointer != _baseUnit)
        {
            _memoryNodes[0].Insert(pointer, 1);
        }
        else
        {
            MemoryNode memoryNode = pointer;
            memoryNode.Stamp = uint.MaxValue;
            _baseUnit += UNIT_SIZE;
        }
    }

    public Pointer MoveUnitsUp(Pointer oldPointer, uint unitCount)
    {
        uint index = UNITS_TO_INDEX[unitCount - 1];

        if (oldPointer > _baseUnit + (16 * 1024) || oldPointer > _memoryNodes[index].Next)
        {
            return oldPointer;
        }

        Pointer pointer = _memoryNodes[index].Remove();
        CopyUnits(pointer, oldPointer, unitCount);
        unitCount = INDEX_TO_UNITS[index];

        if (oldPointer != _baseUnit)
        {
            _memoryNodes[index].Insert(oldPointer, unitCount);
        }
        else
        {
            _baseUnit += unitCount * UNIT_SIZE;
        }

        return pointer;
    }

    /// <summary>
    /// Expand the space allocated (in the single, large array) for the bytes of the data (ie. the "text") that is
    /// being encoded or decoded.
    /// </summary>
    public void ExpandText()
    {
        MemoryNode memoryNode;
        var counts = new uint[INDEX_COUNT];

        while ((memoryNode = _baseUnit).Stamp == uint.MaxValue)
        {
            _baseUnit = memoryNode + memoryNode.UnitCount;
            counts[UNITS_TO_INDEX[memoryNode.UnitCount - 1]]++;
            memoryNode.Stamp = 0;
        }

        for (uint index = 0; index < INDEX_COUNT; index++)
        {
            for (memoryNode = _memoryNodes[index]; counts[index] != 0; memoryNode = memoryNode.Next)
            {
                while (memoryNode.Next.Stamp == 0)
                {
                    memoryNode.Unlink();
                    _memoryNodes[index].Stamp--;
                    if (--counts[index] == 0)
                    {
                        break;
                    }
                }
            }
        }
    }

    #endregion

    #region Private Methods

    private Pointer AllocateUnitsRare(uint index)
    {
        if (_glueCount == 0)
        {
            GlueFreeBlocks();
            if (_memoryNodes[index].Available)
            {
                return _memoryNodes[index].Remove();
            }
        }

        var oldIndex = index;
        do
        {
            if (++oldIndex == INDEX_COUNT)
            {
                _glueCount--;
                oldIndex = INDEX_TO_UNITS[index] * UNIT_SIZE;
                return (_baseUnit - _text > oldIndex) ? (_baseUnit -= oldIndex) : Pointer.ZERO;
            }
        } while (!_memoryNodes[oldIndex].Available);

        Pointer allocatedBlock = _memoryNodes[oldIndex].Remove();
        SplitBlock(allocatedBlock, oldIndex, index);
        return allocatedBlock;
    }

    private void SplitBlock(Pointer pointer, uint oldIndex, uint newIndex)
    {
        var unitCountDifference = (uint)(INDEX_TO_UNITS[oldIndex] - INDEX_TO_UNITS[newIndex]);
        var newPointer = pointer + (INDEX_TO_UNITS[newIndex] * UNIT_SIZE);

        uint index = UNITS_TO_INDEX[unitCountDifference - 1];
        if (INDEX_TO_UNITS[index] != unitCountDifference)
        {
            uint unitCount = INDEX_TO_UNITS[--index];
            _memoryNodes[index].Insert(newPointer, unitCount);
            newPointer += unitCount * UNIT_SIZE;
            unitCountDifference -= unitCount;
        }

        _memoryNodes[UNITS_TO_INDEX[unitCountDifference - 1]]
            .Insert(newPointer, unitCountDifference);
    }

    private void GlueFreeBlocks()
    {
        var memoryNode = new MemoryNode(LOCAL_OFFSET, _memory);
        memoryNode.Stamp = 0;
        memoryNode.Next = MemoryNode.ZERO;
        memoryNode.UnitCount = 0;

        MemoryNode memoryNode0;
        MemoryNode memoryNode1;
        MemoryNode memoryNode2;

        if (_lowUnit != _highUnit)
        {
            _lowUnit[0] = 0;
        }

        // Find all unused memory nodes.

        memoryNode1 = memoryNode;
        for (uint index = 0; index < INDEX_COUNT; index++)
        {
            while (_memoryNodes[index].Available)
            {
                memoryNode0 = _memoryNodes[index].Remove();
                if (memoryNode0.UnitCount != 0)
                {
                    while (
                        (memoryNode2 = memoryNode0 + memoryNode0.UnitCount).Stamp == uint.MaxValue
                    )
                    {
                        memoryNode0.UnitCount += memoryNode2.UnitCount;
                        memoryNode2.UnitCount = 0;
                    }
                    memoryNode1.Link(memoryNode0);
                    memoryNode1 = memoryNode0;
                }
            }
        }

        // Coalesce the memory represented by the unused memory nodes.

        while (memoryNode.Available)
        {
            memoryNode0 = memoryNode.Remove();
            var unitCount = memoryNode0.UnitCount;
            if (unitCount != 0)
            {
                for (; unitCount > 128; unitCount -= 128, memoryNode0 += 128)
                {
                    _memoryNodes[INDEX_COUNT - 1].Insert(memoryNode0, 128);
                }

                uint index = UNITS_TO_INDEX[unitCount - 1];
                if (INDEX_TO_UNITS[index] != unitCount)
                {
                    var unitCountDifference = unitCount - INDEX_TO_UNITS[--index];
                    _memoryNodes[unitCountDifference - 1]
                        .Insert(
                            memoryNode0 + (unitCount - unitCountDifference),
                            unitCountDifference
                        );
                }

                _memoryNodes[index].Insert(memoryNode0, INDEX_TO_UNITS[index]);
            }
        }

        _glueCount = 1 << 13;
    }

    private void CopyUnits(Pointer target, Pointer source, uint unitCount)
    {
        do
        {
            target[0] = source[0];
            target[1] = source[1];
            target[2] = source[2];
            target[3] = source[3];
            target[4] = source[4];
            target[5] = source[5];
            target[6] = source[6];
            target[7] = source[7];
            target[8] = source[8];
            target[9] = source[9];
            target[10] = source[10];
            target[11] = source[11];
            target += UNIT_SIZE;
            source += UNIT_SIZE;
        } while (--unitCount != 0);
    }

    #endregion
}
