Revert "[heap_tracker] Use ankerl map instead of rb tree (#249)" (#382)

This reverts commit c9a3baab5d5ba524778492027ef8961da947df2d.

this commit caused issues in ender magnolia or something, need to make
sure I didn't mess up the revert

Reviewed-on: https://git.eden-emu.dev/eden-emu/eden/pulls/382
Reviewed-by: Shinmegumi <shinmegumi@eden-emu.dev>
Reviewed-by: Lizzie <lizzie@eden-emu.dev>
Reviewed-by: MaranBr <maranbr@outlook.com>

1 files changed, 60 insertions, 22 deletions

diff --git a/src/common/heap_tracker.h b/src/common/heap_tracker.h
index 14b5401c18..ee5b0bf43a 100644
--- a/src/common/heap_tracker.h
+++ b/src/common/heap_tracker.h
@@ -1,55 +1,93 @@
-// SPDX-FileCopyrightText: Copyright 2025 Eden Emulator Project
-// SPDX-License-Identifier: GPL-3.0-or-later
 // SPDX-FileCopyrightText: Copyright 2023 yuzu Emulator Project
 // SPDX-License-Identifier: GPL-2.0-or-later
 
 #pragma once
 
+#include <atomic>
 #include <mutex>
+#include <set>
 #include <shared_mutex>
-#include <ankerl/unordered_dense.h>
+
 #include "common/host_memory.h"
+#include "common/intrusive_red_black_tree.h"
 
 namespace Common {
 
 struct SeparateHeapMap {
-    PAddr paddr{}; //8
-    std::size_t size{}; //8 (16)
-    std::size_t tick{}; //8 (24)
-    // 4 bits needed, sync with host_memory.h if needed
-    MemoryPermission perm : 4 = MemoryPermission::Read;
-    bool is_resident : 1 = false;
+    Common::IntrusiveRedBlackTreeNode addr_node{};
+    Common::IntrusiveRedBlackTreeNode tick_node{};
+    VAddr vaddr{};
+    PAddr paddr{};
+    size_t size{};
+    size_t tick{};
+    MemoryPermission perm{};
+    bool is_resident{};
+};
+
+struct SeparateHeapMapAddrComparator {
+    static constexpr int Compare(const SeparateHeapMap& lhs, const SeparateHeapMap& rhs) {
+        if (lhs.vaddr < rhs.vaddr) {
+            return -1;
+        } else if (lhs.vaddr <= (rhs.vaddr + rhs.size - 1)) {
+            return 0;
+        } else {
+            return 1;
+        }
+    }
+};
+
+struct SeparateHeapMapTickComparator {
+    static constexpr int Compare(const SeparateHeapMap& lhs, const SeparateHeapMap& rhs) {
+        if (lhs.tick < rhs.tick) {
+            return -1;
+        } else if (lhs.tick > rhs.tick) {
+            return 1;
+        } else {
+            return SeparateHeapMapAddrComparator::Compare(lhs, rhs);
+        }
+    }
 };
-static_assert(sizeof(SeparateHeapMap) == 32); //half a cache line! good for coherency
 
 class HeapTracker {
 public:
     explicit HeapTracker(Common::HostMemory& buffer);
     ~HeapTracker();
-    void Map(size_t virtual_offset, size_t host_offset, size_t length, MemoryPermission perm, bool is_separate_heap);
+
+    void Map(size_t virtual_offset, size_t host_offset, size_t length, MemoryPermission perm,
+             bool is_separate_heap);
     void Unmap(size_t virtual_offset, size_t size, bool is_separate_heap);
     void Protect(size_t virtual_offset, size_t length, MemoryPermission perm);
-    inline u8* VirtualBasePointer() noexcept {
+    u8* VirtualBasePointer() {
         return m_buffer.VirtualBasePointer();
     }
+
+    bool DeferredMapSeparateHeap(u8* fault_address);
+    bool DeferredMapSeparateHeap(size_t virtual_offset);
+
 private:
-    // TODO: You may want to "fake-map" the first 2GB of 64-bit address space
-    // and dedicate it entirely to a recursive PTE mapping :)
-    // However Ankerl is way better than using an RB tree, in all senses
-    using AddrTree = ankerl::unordered_dense::map<VAddr, SeparateHeapMap>;
-    AddrTree m_mappings;
-    using TicksTree = ankerl::unordered_dense::map<VAddr, SeparateHeapMap>;
-    TicksTree m_resident_mappings;
+    using AddrTreeTraits =
+        Common::IntrusiveRedBlackTreeMemberTraitsDeferredAssert<&SeparateHeapMap::addr_node>;
+    using AddrTree = AddrTreeTraits::TreeType<SeparateHeapMapAddrComparator>;
+
+    using TickTreeTraits =
+        Common::IntrusiveRedBlackTreeMemberTraitsDeferredAssert<&SeparateHeapMap::tick_node>;
+    using TickTree = TickTreeTraits::TreeType<SeparateHeapMapTickComparator>;
+
+    AddrTree m_mappings{};
+    TickTree m_resident_mappings{};
+
 private:
     void SplitHeapMap(VAddr offset, size_t size);
     void SplitHeapMapLocked(VAddr offset);
+
+    AddrTree::iterator GetNearestHeapMapLocked(VAddr offset);
+
     void RebuildSeparateHeapAddressSpace();
-    inline HeapTracker::AddrTree::iterator GetNearestHeapMapLocked(VAddr offset) noexcept {
-        return m_mappings.find(offset);
-    }
+
 private:
     Common::HostMemory& m_buffer;
     const s64 m_max_resident_map_count;
+
     std::shared_mutex m_rebuild_lock{};
     std::mutex m_lock{};
     s64 m_map_count{};