1 files changed, 218 insertions, 0 deletions
diff --git a/src/Ryujinx.Cpu/LightningJit/Cache/PageAlignedRangeList.cs b/src/Ryujinx.Cpu/LightningJit/Cache/PageAlignedRangeList.cs
new file mode 100644
index 00000000..b6b38671
--- /dev/null
+++ b/src/Ryujinx.Cpu/LightningJit/Cache/PageAlignedRangeList.cs
@@ -0,0 +1,218 @@
+using Ryujinx.Common;
+using Ryujinx.Memory;
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Diagnostics.CodeAnalysis;
+
+namespace Ryujinx.Cpu.LightningJit.Cache
+{
+    class PageAlignedRangeList
+    {
+        private readonly struct Range : IComparable<Range>
+        {
+            public int Offset { get; }
+            public int Size { get; }
+
+            public Range(int offset, int size)
+            {
+                Offset = offset;
+                Size = size;
+            }
+
+            public int CompareTo([AllowNull] Range other)
+            {
+                return Offset.CompareTo(other.Offset);
+            }
+        }
+
+        private readonly Action<int, int> _alignedRangeAction;
+        private readonly Action<ulong, TranslatedFunction> _alignedFunctionAction;
+        private readonly List<(Range, ulong, TranslatedFunction)> _pendingFunctions;
+        private readonly List<Range> _ranges;
+
+        public PageAlignedRangeList(Action<int, int> alignedRangeAction, Action<ulong, TranslatedFunction> alignedFunctionAction)
+        {
+            _alignedRangeAction = alignedRangeAction;
+            _alignedFunctionAction = alignedFunctionAction;
+            _pendingFunctions = new();
+            _ranges = new();
+        }
+
+        public bool Has(ulong address)
+        {
+            foreach ((_, ulong guestAddress, _) in _pendingFunctions)
+            {
+                if (guestAddress == address)
+                {
+                    return true;
+                }
+            }
+
+            return false;
+        }
+
+        public void Add(int offset, int size, ulong address, TranslatedFunction function)
+        {
+            Range range = new(offset, size);
+
+            Insert(range);
+            _pendingFunctions.Add((range, address, function));
+            ProcessAlignedRanges();
+        }
+
+        public void Pad(CacheMemoryAllocator allocator)
+        {
+            int pageSize = (int)MemoryBlock.GetPageSize();
+
+            for (int index = 0; index < _ranges.Count; index++)
+            {
+                Range range = _ranges[index];
+
+                int endOffset = range.Offset + range.Size;
+
+                int alignedStart = BitUtils.AlignDown(range.Offset, pageSize);
+                int alignedEnd = BitUtils.AlignUp(endOffset, pageSize);
+                int alignedSize = alignedEnd - alignedStart;
+
+                if (alignedStart < range.Offset)
+                {
+                    allocator.ForceAllocation(alignedStart, range.Offset - alignedStart);
+                }
+
+                if (alignedEnd > endOffset)
+                {
+                    allocator.ForceAllocation(endOffset, alignedEnd - endOffset);
+                }
+
+                _alignedRangeAction(alignedStart, alignedSize);
+                _ranges.RemoveAt(index--);
+                ProcessPendingFunctions(index, alignedEnd);
+            }
+        }
+
+        private void ProcessAlignedRanges()
+        {
+            int pageSize = (int)MemoryBlock.GetPageSize();
+
+            for (int index = 0; index < _ranges.Count; index++)
+            {
+                Range range = _ranges[index];
+
+                int alignedStart = BitUtils.AlignUp(range.Offset, pageSize);
+                int alignedEnd = BitUtils.AlignDown(range.Offset + range.Size, pageSize);
+                int alignedSize = alignedEnd - alignedStart;
+
+                if (alignedSize <= 0)
+                {
+                    continue;
+                }
+
+                _alignedRangeAction(alignedStart, alignedSize);
+                SplitAt(ref index, alignedStart, alignedEnd);
+                ProcessPendingFunctions(index, alignedEnd);
+            }
+        }
+
+        private void ProcessPendingFunctions(int rangeIndex, int alignedEnd)
+        {
+            if ((rangeIndex > 0 && rangeIndex == _ranges.Count) ||
+                (rangeIndex >= 0 && rangeIndex < _ranges.Count && _ranges[rangeIndex].Offset >= alignedEnd))
+            {
+                rangeIndex--;
+            }
+
+            int alignedStart;
+
+            if (rangeIndex >= 0)
+            {
+                alignedStart = _ranges[rangeIndex].Offset + _ranges[rangeIndex].Size;
+            }
+            else
+            {
+                alignedStart = 0;
+            }
+
+            if (rangeIndex < _ranges.Count - 1)
+            {
+                alignedEnd = _ranges[rangeIndex + 1].Offset;
+            }
+            else
+            {
+                alignedEnd = int.MaxValue;
+            }
+
+            for (int index = 0; index < _pendingFunctions.Count; index++)
+            {
+                (Range range, ulong address, TranslatedFunction function) = _pendingFunctions[index];
+
+                if (range.Offset >= alignedStart && range.Offset + range.Size <= alignedEnd)
+                {
+                    _alignedFunctionAction(address, function);
+                    _pendingFunctions.RemoveAt(index--);
+                }
+            }
+        }
+
+        private void Insert(Range range)
+        {
+            int index = _ranges.BinarySearch(range);
+
+            if (index < 0)
+            {
+                index = ~index;
+            }
+
+            if (index < _ranges.Count)
+            {
+                Range next = _ranges[index];
+
+                int endOffs = range.Offset + range.Size;
+
+                if (next.Offset == endOffs)
+                {
+                    range = new Range(range.Offset, range.Size + next.Size);
+                    _ranges.RemoveAt(index);
+                }
+            }
+
+            if (index > 0)
+            {
+                Range prev = _ranges[index - 1];
+
+                if (prev.Offset + prev.Size == range.Offset)
+                {
+                    range = new Range(range.Offset - prev.Size, range.Size + prev.Size);
+                    _ranges.RemoveAt(--index);
+                }
+            }
+
+            _ranges.Insert(index, range);
+        }
+
+        private void SplitAt(ref int index, int alignedStart, int alignedEnd)
+        {
+            Range range = _ranges[index];
+
+            if (range.Offset < alignedStart)
+            {
+                _ranges[index++] = new(range.Offset, alignedStart - range.Offset);
+
+                if (range.Offset + range.Size > alignedEnd)
+                {
+                    _ranges.Insert(index, new(alignedEnd, (range.Offset + range.Size) - alignedEnd));
+                }
+            }
+            else if (range.Offset + range.Size > alignedEnd)
+            {
+                _ranges[index] = new(alignedEnd, (range.Offset + range.Size) - alignedEnd);
+            }
+            else if (range.Offset == alignedStart && range.Offset + range.Size == alignedEnd)
+            {
+                Debug.Assert(range.Offset == alignedStart && range.Offset + range.Size == alignedEnd);
+
+                _ranges.RemoveAt(index--);
+            }
+        }
+    }
+}