16 files changed, 1696 insertions, 716 deletions
diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt
index 2c2bd2ee8..f77575a00 100644
--- a/src/common/CMakeLists.txt
+++ b/src/common/CMakeLists.txt
@@ -98,7 +98,6 @@ add_library(common STATIC
     algorithm.h
     alignment.h
     assert.h
-    atomic_ops.cpp
     atomic_ops.h
     detached_tasks.cpp
     detached_tasks.h
@@ -108,7 +107,6 @@ add_library(common STATIC
     bit_util.h
     cityhash.cpp
     cityhash.h
-    color.h
     common_funcs.h
     common_paths.h
     common_types.h
@@ -123,6 +121,7 @@ add_library(common STATIC
     hash.h
     hex_util.cpp
     hex_util.h
+    intrusive_red_black_tree.h
     logging/backend.cpp
     logging/backend.h
     logging/filter.cpp
@@ -143,6 +142,7 @@ add_library(common STATIC
     page_table.h
     param_package.cpp
     param_package.h
+    parent_of_member.h
     quaternion.h
     ring_buffer.h
     scm_rev.cpp
@@ -165,8 +165,7 @@ add_library(common STATIC
     threadsafe_queue.h
     time_zone.cpp
     time_zone.h
-    timer.cpp
-    timer.h
+    tree.h
     uint128.cpp
     uint128.h
     uuid.cpp
diff --git a/src/common/alignment.h b/src/common/alignment.h
index 5040043de..fb81f10d8 100644
--- a/src/common/alignment.h
+++ b/src/common/alignment.h
@@ -9,50 +9,45 @@
 namespace Common {
 
 template <typename T>
-[[nodiscard]] constexpr T AlignUp(T value, std::size_t size) {
-    static_assert(std::is_unsigned_v<T>, "T must be an unsigned value.");
+requires std::is_unsigned_v<T>[[nodiscard]] constexpr T AlignUp(T value, size_t size) {
     auto mod{static_cast<T>(value % size)};
     value -= mod;
     return static_cast<T>(mod == T{0} ? value : value + size);
 }
 
 template <typename T>
-[[nodiscard]] constexpr T AlignDown(T value, std::size_t size) {
-    static_assert(std::is_unsigned_v<T>, "T must be an unsigned value.");
-    return static_cast<T>(value - value % size);
+requires std::is_unsigned_v<T>[[nodiscard]] constexpr T AlignUpLog2(T value, size_t align_log2) {
+    return static_cast<T>((value + ((1ULL << align_log2) - 1)) >> align_log2 << align_log2);
 }
 
 template <typename T>
-[[nodiscard]] constexpr T AlignBits(T value, std::size_t align) {
-    static_assert(std::is_unsigned_v<T>, "T must be an unsigned value.");
-    return static_cast<T>((value + ((1ULL << align) - 1)) >> align << align);
+requires std::is_unsigned_v<T>[[nodiscard]] constexpr T AlignDown(T value, size_t size) {
+    return static_cast<T>(value - value % size);
 }
 
 template <typename T>
-[[nodiscard]] constexpr bool Is4KBAligned(T value) {
-    static_assert(std::is_unsigned_v<T>, "T must be an unsigned value.");
+requires std::is_unsigned_v<T>[[nodiscard]] constexpr bool Is4KBAligned(T value) {
     return (value & 0xFFF) == 0;
 }
 
 template <typename T>
-[[nodiscard]] constexpr bool IsWordAligned(T value) {
-    static_assert(std::is_unsigned_v<T>, "T must be an unsigned value.");
+requires std::is_unsigned_v<T>[[nodiscard]] constexpr bool IsWordAligned(T value) {
     return (value & 0b11) == 0;
 }
 
 template <typename T>
-[[nodiscard]] constexpr bool IsAligned(T value, std::size_t alignment) {
-    using U = typename std::make_unsigned<T>::type;
+requires std::is_integral_v<T>[[nodiscard]] constexpr bool IsAligned(T value, size_t alignment) {
+    using U = typename std::make_unsigned_t<T>;
     const U mask = static_cast<U>(alignment - 1);
     return (value & mask) == 0;
 }
 
-template <typename T, std::size_t Align = 16>
+template <typename T, size_t Align = 16>
 class AlignmentAllocator {
 public:
     using value_type = T;
-    using size_type = std::size_t;
-    using difference_type = std::ptrdiff_t;
+    using size_type = size_t;
+    using difference_type = ptrdiff_t;
 
     using propagate_on_container_copy_assignment = std::true_type;
     using propagate_on_container_move_assignment = std::true_type;
diff --git a/src/common/atomic_ops.cpp b/src/common/atomic_ops.cpp
deleted file mode 100644
index 1612d0e67..000000000
--- a/src/common/atomic_ops.cpp
+++ /dev/null
@@ -1,75 +0,0 @@
-// Copyright 2020 yuzu Emulator Project
-// Licensed under GPLv2 or any later version
-// Refer to the license.txt file included.
-
-#include <cstring>
-
-#include "common/atomic_ops.h"
-
-#if _MSC_VER
-#include <intrin.h>
-#endif
-
-namespace Common {
-
-#if _MSC_VER
-
-bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected) {
-    const u8 result =
-        _InterlockedCompareExchange8(reinterpret_cast<volatile char*>(pointer), value, expected);
-    return result == expected;
-}
-
-bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected) {
-    const u16 result =
-        _InterlockedCompareExchange16(reinterpret_cast<volatile short*>(pointer), value, expected);
-    return result == expected;
-}
-
-bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected) {
-    const u32 result =
-        _InterlockedCompareExchange(reinterpret_cast<volatile long*>(pointer), value, expected);
-    return result == expected;
-}
-
-bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected) {
-    const u64 result = _InterlockedCompareExchange64(reinterpret_cast<volatile __int64*>(pointer),
-                                                     value, expected);
-    return result == expected;
-}
-
-bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected) {
-    return _InterlockedCompareExchange128(reinterpret_cast<volatile __int64*>(pointer), value[1],
-                                          value[0],
-                                          reinterpret_cast<__int64*>(expected.data())) != 0;
-}
-
-#else
-
-bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected) {
-    return __sync_bool_compare_and_swap(pointer, expected, value);
-}
-
-bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected) {
-    return __sync_bool_compare_and_swap(pointer, expected, value);
-}
-
-bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected) {
-    return __sync_bool_compare_and_swap(pointer, expected, value);
-}
-
-bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected) {
-    return __sync_bool_compare_and_swap(pointer, expected, value);
-}
-
-bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected) {
-    unsigned __int128 value_a;
-    unsigned __int128 expected_a;
-    std::memcpy(&value_a, value.data(), sizeof(u128));
-    std::memcpy(&expected_a, expected.data(), sizeof(u128));
-    return __sync_bool_compare_and_swap((unsigned __int128*)pointer, expected_a, value_a);
-}
-
-#endif
-
-} // namespace Common
diff --git a/src/common/atomic_ops.h b/src/common/atomic_ops.h
index b46888589..2b1f515e8 100644
--- a/src/common/atomic_ops.h
+++ b/src/common/atomic_ops.h
@@ -4,14 +4,75 @@
 
 #pragma once
 
+#include <cstring>
+#include <memory>
+
 #include "common/common_types.h"
 
+#if _MSC_VER
+#include <intrin.h>
+#endif
+
 namespace Common {
 
-[[nodiscard]] bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected);
-[[nodiscard]] bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected);
-[[nodiscard]] bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected);
-[[nodiscard]] bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected);
-[[nodiscard]] bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected);
+#if _MSC_VER
+
+[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected) {
+    const u8 result =
+        _InterlockedCompareExchange8(reinterpret_cast<volatile char*>(pointer), value, expected);
+    return result == expected;
+}
+
+[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected) {
+    const u16 result =
+        _InterlockedCompareExchange16(reinterpret_cast<volatile short*>(pointer), value, expected);
+    return result == expected;
+}
+
+[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected) {
+    const u32 result =
+        _InterlockedCompareExchange(reinterpret_cast<volatile long*>(pointer), value, expected);
+    return result == expected;
+}
+
+[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected) {
+    const u64 result = _InterlockedCompareExchange64(reinterpret_cast<volatile __int64*>(pointer),
+                                                     value, expected);
+    return result == expected;
+}
+
+[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected) {
+    return _InterlockedCompareExchange128(reinterpret_cast<volatile __int64*>(pointer), value[1],
+                                          value[0],
+                                          reinterpret_cast<__int64*>(expected.data())) != 0;
+}
+
+#else
+
+[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected) {
+    return __sync_bool_compare_and_swap(pointer, expected, value);
+}
+
+[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected) {
+    return __sync_bool_compare_and_swap(pointer, expected, value);
+}
+
+[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected) {
+    return __sync_bool_compare_and_swap(pointer, expected, value);
+}
+
+[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected) {
+    return __sync_bool_compare_and_swap(pointer, expected, value);
+}
+
+[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected) {
+    unsigned __int128 value_a;
+    unsigned __int128 expected_a;
+    std::memcpy(&value_a, value.data(), sizeof(u128));
+    std::memcpy(&expected_a, expected.data(), sizeof(u128));
+    return __sync_bool_compare_and_swap((unsigned __int128*)pointer, expected_a, value_a);
+}
+
+#endif
 
 } // namespace Common
diff --git a/src/common/bit_util.h b/src/common/bit_util.h
index 29f59a9a3..64520ca4e 100644
--- a/src/common/bit_util.h
+++ b/src/common/bit_util.h
@@ -4,13 +4,10 @@
 
 #pragma once
 
+#include <bit>
 #include <climits>
 #include <cstddef>
 
-#ifdef _MSC_VER
-#include <intrin.h>
-#endif
-
 #include "common/common_types.h"
 
 namespace Common {
@@ -21,124 +18,30 @@ template <typename T>
     return sizeof(T) * CHAR_BIT;
 }
 
-#ifdef _MSC_VER
-[[nodiscard]] inline u32 CountLeadingZeroes32(u32 value) {
-    unsigned long leading_zero = 0;
-
-    if (_BitScanReverse(&leading_zero, value) != 0) {
-        return 31 - leading_zero;
-    }
-
-    return 32;
-}
-
-[[nodiscard]] inline u32 CountLeadingZeroes64(u64 value) {
-    unsigned long leading_zero = 0;
-
-    if (_BitScanReverse64(&leading_zero, value) != 0) {
-        return 63 - leading_zero;
-    }
-
-    return 64;
-}
-#else
-[[nodiscard]] inline u32 CountLeadingZeroes32(u32 value) {
-    if (value == 0) {
-        return 32;
-    }
-
-    return static_cast<u32>(__builtin_clz(value));
-}
-
-[[nodiscard]] inline u32 CountLeadingZeroes64(u64 value) {
-    if (value == 0) {
-        return 64;
-    }
-
-    return static_cast<u32>(__builtin_clzll(value));
-}
-#endif
-
-#ifdef _MSC_VER
-[[nodiscard]] inline u32 CountTrailingZeroes32(u32 value) {
-    unsigned long trailing_zero = 0;
-
-    if (_BitScanForward(&trailing_zero, value) != 0) {
-        return trailing_zero;
-    }
-
-    return 32;
-}
-
-[[nodiscard]] inline u32 CountTrailingZeroes64(u64 value) {
-    unsigned long trailing_zero = 0;
-
-    if (_BitScanForward64(&trailing_zero, value) != 0) {
-        return trailing_zero;
-    }
-
-    return 64;
-}
-#else
-[[nodiscard]] inline u32 CountTrailingZeroes32(u32 value) {
-    if (value == 0) {
-        return 32;
-    }
-
-    return static_cast<u32>(__builtin_ctz(value));
-}
-
-[[nodiscard]] inline u32 CountTrailingZeroes64(u64 value) {
-    if (value == 0) {
-        return 64;
-    }
-
-    return static_cast<u32>(__builtin_ctzll(value));
+[[nodiscard]] constexpr u32 MostSignificantBit32(const u32 value) {
+    return 31U - static_cast<u32>(std::countl_zero(value));
 }
-#endif
-
-#ifdef _MSC_VER
 
-[[nodiscard]] inline u32 MostSignificantBit32(const u32 value) {
-    unsigned long result;
-    _BitScanReverse(&result, value);
-    return static_cast<u32>(result);
+[[nodiscard]] constexpr u32 MostSignificantBit64(const u64 value) {
+    return 63U - static_cast<u32>(std::countl_zero(value));
 }
 
-[[nodiscard]] inline u32 MostSignificantBit64(const u64 value) {
-    unsigned long result;
-    _BitScanReverse64(&result, value);
-    return static_cast<u32>(result);
-}
-
-#else
-
-[[nodiscard]] inline u32 MostSignificantBit32(const u32 value) {
-    return 31U - static_cast<u32>(__builtin_clz(value));
-}
-
-[[nodiscard]] inline u32 MostSignificantBit64(const u64 value) {
-    return 63U - static_cast<u32>(__builtin_clzll(value));
-}
-
-#endif
-
-[[nodiscard]] inline u32 Log2Floor32(const u32 value) {
+[[nodiscard]] constexpr u32 Log2Floor32(const u32 value) {
     return MostSignificantBit32(value);
 }
 
-[[nodiscard]] inline u32 Log2Ceil32(const u32 value) {
-    const u32 log2_f = Log2Floor32(value);
-    return log2_f + ((value ^ (1U << log2_f)) != 0U);
+[[nodiscard]] constexpr u32 Log2Floor64(const u64 value) {
+    return MostSignificantBit64(value);
 }
 
-[[nodiscard]] inline u32 Log2Floor64(const u64 value) {
-    return MostSignificantBit64(value);
+[[nodiscard]] constexpr u32 Log2Ceil32(const u32 value) {
+    const u32 log2_f = Log2Floor32(value);
+    return log2_f + static_cast<u32>((value ^ (1U << log2_f)) != 0U);
 }
 
-[[nodiscard]] inline u32 Log2Ceil64(const u64 value) {
-    const u64 log2_f = static_cast<u64>(Log2Floor64(value));
-    return static_cast<u32>(log2_f + ((value ^ (1ULL << log2_f)) != 0ULL));
+[[nodiscard]] constexpr u32 Log2Ceil64(const u64 value) {
+    const u64 log2_f = Log2Floor64(value);
+    return static_cast<u32>(log2_f + static_cast<u64>((value ^ (1ULL << log2_f)) != 0ULL));
 }
 
 } // namespace Common
diff --git a/src/common/color.h b/src/common/color.h
deleted file mode 100644
index bbcac858e..000000000
--- a/src/common/color.h
+++ /dev/null
@@ -1,271 +0,0 @@
-// Copyright 2014 Citra Emulator Project
-// Licensed under GPLv2 or any later version
-// Refer to the license.txt file included.
-
-#pragma once
-
-#include <cstring>
-
-#include "common/common_types.h"
-#include "common/swap.h"
-#include "common/vector_math.h"
-
-namespace Common::Color {
-
-/// Convert a 1-bit color component to 8 bit
-[[nodiscard]] constexpr u8 Convert1To8(u8 value) {
-    return value * 255;
-}
-
-/// Convert a 4-bit color component to 8 bit
-[[nodiscard]] constexpr u8 Convert4To8(u8 value) {
-    return (value << 4) | value;
-}
-
-/// Convert a 5-bit color component to 8 bit
-[[nodiscard]] constexpr u8 Convert5To8(u8 value) {
-    return (value << 3) | (value >> 2);
-}
-
-/// Convert a 6-bit color component to 8 bit
-[[nodiscard]] constexpr u8 Convert6To8(u8 value) {
-    return (value << 2) | (value >> 4);
-}
-
-/// Convert a 8-bit color component to 1 bit
-[[nodiscard]] constexpr u8 Convert8To1(u8 value) {
-    return value >> 7;
-}
-
-/// Convert a 8-bit color component to 4 bit
-[[nodiscard]] constexpr u8 Convert8To4(u8 value) {
-    return value >> 4;
-}
-
-/// Convert a 8-bit color component to 5 bit
-[[nodiscard]] constexpr u8 Convert8To5(u8 value) {
-    return value >> 3;
-}
-
-/// Convert a 8-bit color component to 6 bit
-[[nodiscard]] constexpr u8 Convert8To6(u8 value) {
-    return value >> 2;
-}
-
-/**
- * Decode a color stored in RGBA8 format
- * @param bytes Pointer to encoded source color
- * @return Result color decoded as Common::Vec4<u8>
- */
-[[nodiscard]] inline Common::Vec4<u8> DecodeRGBA8(const u8* bytes) {
-    return {bytes[3], bytes[2], bytes[1], bytes[0]};
-}
-
-/**
- * Decode a color stored in RGB8 format
- * @param bytes Pointer to encoded source color
- * @return Result color decoded as Common::Vec4<u8>
- */
-[[nodiscard]] inline Common::Vec4<u8> DecodeRGB8(const u8* bytes) {
-    return {bytes[2], bytes[1], bytes[0], 255};
-}
-
-/**
- * Decode a color stored in RG8 (aka HILO8) format
- * @param bytes Pointer to encoded source color
- * @return Result color decoded as Common::Vec4<u8>
- */
-[[nodiscard]] inline Common::Vec4<u8> DecodeRG8(const u8* bytes) {
-    return {bytes[1], bytes[0], 0, 255};
-}
-
-/**
- * Decode a color stored in RGB565 format
- * @param bytes Pointer to encoded source color
- * @return Result color decoded as Common::Vec4<u8>
- */
-[[nodiscard]] inline Common::Vec4<u8> DecodeRGB565(const u8* bytes) {
-    u16_le pixel;
-    std::memcpy(&pixel, bytes, sizeof(pixel));
-    return {Convert5To8((pixel >> 11) & 0x1F), Convert6To8((pixel >> 5) & 0x3F),
-            Convert5To8(pixel & 0x1F), 255};
-}
-
-/**
- * Decode a color stored in RGB5A1 format
- * @param bytes Pointer to encoded source color
- * @return Result color decoded as Common::Vec4<u8>
- */
-[[nodiscard]] inline Common::Vec4<u8> DecodeRGB5A1(const u8* bytes) {
-    u16_le pixel;
-    std::memcpy(&pixel, bytes, sizeof(pixel));
-    return {Convert5To8((pixel >> 11) & 0x1F), Convert5To8((pixel >> 6) & 0x1F),
-            Convert5To8((pixel >> 1) & 0x1F), Convert1To8(pixel & 0x1)};
-}
-
-/**
- * Decode a color stored in RGBA4 format
- * @param bytes Pointer to encoded source color
- * @return Result color decoded as Common::Vec4<u8>
- */
-[[nodiscard]] inline Common::Vec4<u8> DecodeRGBA4(const u8* bytes) {
-    u16_le pixel;
-    std::memcpy(&pixel, bytes, sizeof(pixel));
-    return {Convert4To8((pixel >> 12) & 0xF), Convert4To8((pixel >> 8) & 0xF),
-            Convert4To8((pixel >> 4) & 0xF), Convert4To8(pixel & 0xF)};
-}
-
-/**
- * Decode a depth value stored in D16 format
- * @param bytes Pointer to encoded source value
- * @return Depth value as an u32
- */
-[[nodiscard]] inline u32 DecodeD16(const u8* bytes) {
-    u16_le data;
-    std::memcpy(&data, bytes, sizeof(data));
-    return data;
-}
-
-/**
- * Decode a depth value stored in D24 format
- * @param bytes Pointer to encoded source value
- * @return Depth value as an u32
- */
-[[nodiscard]] inline u32 DecodeD24(const u8* bytes) {
-    return (bytes[2] << 16) | (bytes[1] << 8) | bytes[0];
-}
-
-/**
- * Decode a depth value and a stencil value stored in D24S8 format
- * @param bytes Pointer to encoded source values
- * @return Resulting values stored as a Common::Vec2
- */
-[[nodiscard]] inline Common::Vec2<u32> DecodeD24S8(const u8* bytes) {
-    return {static_cast<u32>((bytes[2] << 16) | (bytes[1] << 8) | bytes[0]), bytes[3]};
-}
-
-/**
- * Encode a color as RGBA8 format
- * @param color Source color to encode
- * @param bytes Destination pointer to store encoded color
- */
-inline void EncodeRGBA8(const Common::Vec4<u8>& color, u8* bytes) {
-    bytes[3] = color.r();
-    bytes[2] = color.g();
-    bytes[1] = color.b();
-    bytes[0] = color.a();
-}
-
-/**
- * Encode a color as RGB8 format
- * @param color Source color to encode
- * @param bytes Destination pointer to store encoded color
- */
-inline void EncodeRGB8(const Common::Vec4<u8>& color, u8* bytes) {
-    bytes[2] = color.r();
-    bytes[1] = color.g();
-    bytes[0] = color.b();
-}
-
-/**
- * Encode a color as RG8 (aka HILO8) format
- * @param color Source color to encode
- * @param bytes Destination pointer to store encoded color
- */
-inline void EncodeRG8(const Common::Vec4<u8>& color, u8* bytes) {
-    bytes[1] = color.r();
-    bytes[0] = color.g();
-}
-/**
- * Encode a color as RGB565 format
- * @param color Source color to encode
- * @param bytes Destination pointer to store encoded color
- */
-inline void EncodeRGB565(const Common::Vec4<u8>& color, u8* bytes) {
-    const u16_le data =
-        (Convert8To5(color.r()) << 11) | (Convert8To6(color.g()) << 5) | Convert8To5(color.b());
-
-    std::memcpy(bytes, &data, sizeof(data));
-}
-
-/**
- * Encode a color as RGB5A1 format
- * @param color Source color to encode
- * @param bytes Destination pointer to store encoded color
- */
-inline void EncodeRGB5A1(const Common::Vec4<u8>& color, u8* bytes) {
-    const u16_le data = (Convert8To5(color.r()) << 11) | (Convert8To5(color.g()) << 6) |
-                        (Convert8To5(color.b()) << 1) | Convert8To1(color.a());
-
-    std::memcpy(bytes, &data, sizeof(data));
-}
-
-/**
- * Encode a color as RGBA4 format
- * @param color Source color to encode
- * @param bytes Destination pointer to store encoded color
- */
-inline void EncodeRGBA4(const Common::Vec4<u8>& color, u8* bytes) {
-    const u16 data = (Convert8To4(color.r()) << 12) | (Convert8To4(color.g()) << 8) |
-                     (Convert8To4(color.b()) << 4) | Convert8To4(color.a());
-
-    std::memcpy(bytes, &data, sizeof(data));
-}
-
-/**
- * Encode a 16 bit depth value as D16 format
- * @param value 16 bit source depth value to encode
- * @param bytes Pointer where to store the encoded value
- */
-inline void EncodeD16(u32 value, u8* bytes) {
-    const u16_le data = static_cast<u16>(value);
-    std::memcpy(bytes, &data, sizeof(data));
-}
-
-/**
- * Encode a 24 bit depth value as D24 format
- * @param value 24 bit source depth value to encode
- * @param bytes Pointer where to store the encoded value
- */
-inline void EncodeD24(u32 value, u8* bytes) {
-    bytes[0] = value & 0xFF;
-    bytes[1] = (value >> 8) & 0xFF;
-    bytes[2] = (value >> 16) & 0xFF;
-}
-
-/**
- * Encode a 24 bit depth and 8 bit stencil values as D24S8 format
- * @param depth 24 bit source depth value to encode
- * @param stencil 8 bit source stencil value to encode
- * @param bytes Pointer where to store the encoded value
- */
-inline void EncodeD24S8(u32 depth, u8 stencil, u8* bytes) {
-    bytes[0] = depth & 0xFF;
-    bytes[1] = (depth >> 8) & 0xFF;
-    bytes[2] = (depth >> 16) & 0xFF;
-    bytes[3] = stencil;
-}
-
-/**
- * Encode a 24 bit depth value as D24X8 format (32 bits per pixel with 8 bits unused)
- * @param depth 24 bit source depth value to encode
- * @param bytes Pointer where to store the encoded value
- * @note unused bits will not be modified
- */
-inline void EncodeD24X8(u32 depth, u8* bytes) {
-    bytes[0] = depth & 0xFF;
-    bytes[1] = (depth >> 8) & 0xFF;
-    bytes[2] = (depth >> 16) & 0xFF;
-}
-
-/**
- * Encode an 8 bit stencil value as X24S8 format (32 bits per pixel with 24 bits unused)
- * @param stencil 8 bit source stencil value to encode
- * @param bytes Pointer where to store the encoded value
- * @note unused bits will not be modified
- */
-inline void EncodeX24S8(u8 stencil, u8* bytes) {
-    bytes[3] = stencil;
-}
-
-} // namespace Common::Color
diff --git a/src/common/common_funcs.h b/src/common/common_funcs.h
index 367b6bf6e..75f3027fb 100644
--- a/src/common/common_funcs.h
+++ b/src/common/common_funcs.h
@@ -24,10 +24,10 @@
 #define INSERT_PADDING_WORDS(num_words)                                                            \
     std::array<u32, num_words> CONCAT2(pad, __LINE__) {}
 
-/// These are similar to the INSERT_PADDING_* macros, but are needed for padding unions. This is
-/// because unions can only be initialized by one member.
-#define INSERT_UNION_PADDING_BYTES(num_bytes) std::array<u8, num_bytes> CONCAT2(pad, __LINE__)
-#define INSERT_UNION_PADDING_WORDS(num_words) std::array<u32, num_words> CONCAT2(pad, __LINE__)
+/// These are similar to the INSERT_PADDING_* macros but do not zero-initialize the contents.
+/// This keeps the structure trivial to construct.
+#define INSERT_PADDING_BYTES_NOINIT(num_bytes) std::array<u8, num_bytes> CONCAT2(pad, __LINE__)
+#define INSERT_PADDING_WORDS_NOINIT(num_words) std::array<u32, num_words> CONCAT2(pad, __LINE__)
 
 #ifndef _MSC_VER
 
@@ -93,6 +93,14 @@ __declspec(dllimport) void __stdcall DebugBreak(void);
         return static_cast<T>(key) == 0;                                                           \
     }
 
+/// Evaluates a boolean expression, and returns a result unless that expression is true.
+#define R_UNLESS(expr, res)                                                                        \
+    {                                                                                              \
+        if (!(expr)) {                                                                             \
+            return res;                                                                            \
+        }                                                                                          \
+    }
+
 namespace Common {
 
 [[nodiscard]] constexpr u32 MakeMagic(char a, char b, char c, char d) {
diff --git a/src/common/intrusive_red_black_tree.h b/src/common/intrusive_red_black_tree.h
new file mode 100644
index 000000000..c0bbcd457
--- /dev/null
+++ b/src/common/intrusive_red_black_tree.h
@@ -0,0 +1,602 @@
+// Copyright 2021 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#pragma once
+
+#include "common/parent_of_member.h"
+#include "common/tree.h"
+
+namespace Common {
+
+namespace impl {
+
+class IntrusiveRedBlackTreeImpl;
+
+}
+
+struct IntrusiveRedBlackTreeNode {
+public:
+    using EntryType = RBEntry<IntrusiveRedBlackTreeNode>;
+
+    constexpr IntrusiveRedBlackTreeNode() = default;
+
+    void SetEntry(const EntryType& new_entry) {
+        entry = new_entry;
+    }
+
+    [[nodiscard]] EntryType& GetEntry() {
+        return entry;
+    }
+
+    [[nodiscard]] const EntryType& GetEntry() const {
+        return entry;
+    }
+
+private:
+    EntryType entry{};
+
+    friend class impl::IntrusiveRedBlackTreeImpl;
+
+    template <class, class, class>
+    friend class IntrusiveRedBlackTree;
+};
+
+template <class T, class Traits, class Comparator>
+class IntrusiveRedBlackTree;
+
+namespace impl {
+
+class IntrusiveRedBlackTreeImpl {
+private:
+    template <class, class, class>
+    friend class ::Common::IntrusiveRedBlackTree;
+
+    using RootType = RBHead<IntrusiveRedBlackTreeNode>;
+    RootType root;
+
+public:
+    template <bool Const>
+    class Iterator;
+
+    using value_type = IntrusiveRedBlackTreeNode;
+    using size_type = size_t;
+    using difference_type = ptrdiff_t;
+    using pointer = value_type*;
+    using const_pointer = const value_type*;
+    using reference = value_type&;
+    using const_reference = const value_type&;
+    using iterator = Iterator<false>;
+    using const_iterator = Iterator<true>;
+
+    template <bool Const>
+    class Iterator {
+    public:
+        using iterator_category = std::bidirectional_iterator_tag;
+        using value_type = typename IntrusiveRedBlackTreeImpl::value_type;
+        using difference_type = typename IntrusiveRedBlackTreeImpl::difference_type;
+        using pointer = std::conditional_t<Const, IntrusiveRedBlackTreeImpl::const_pointer,
+                                           IntrusiveRedBlackTreeImpl::pointer>;
+        using reference = std::conditional_t<Const, IntrusiveRedBlackTreeImpl::const_reference,
+                                             IntrusiveRedBlackTreeImpl::reference>;
+
+    private:
+        pointer node;
+
+    public:
+        explicit Iterator(pointer n) : node(n) {}
+
+        bool operator==(const Iterator& rhs) const {
+            return this->node == rhs.node;
+        }
+
+        bool operator!=(const Iterator& rhs) const {
+            return !(*this == rhs);
+        }
+
+        pointer operator->() const {
+            return this->node;
+        }
+
+        reference operator*() const {
+            return *this->node;
+        }
+
+        Iterator& operator++() {
+            this->node = GetNext(this->node);
+            return *this;
+        }
+
+        Iterator& operator--() {
+            this->node = GetPrev(this->node);
+            return *this;
+        }
+
+        Iterator operator++(int) {
+            const Iterator it{*this};
+            ++(*this);
+            return it;
+        }
+
+        Iterator operator--(int) {
+            const Iterator it{*this};
+            --(*this);
+            return it;
+        }
+
+        operator Iterator<true>() const {
+            return Iterator<true>(this->node);
+        }
+    };
+
+private:
+    // Define accessors using RB_* functions.
+    bool EmptyImpl() const {
+        return root.IsEmpty();
+    }
+
+    IntrusiveRedBlackTreeNode* GetMinImpl() const {
+        return RB_MIN(const_cast<RootType*>(&root));
+    }
+
+    IntrusiveRedBlackTreeNode* GetMaxImpl() const {
+        return RB_MAX(const_cast<RootType*>(&root));
+    }
+
+    IntrusiveRedBlackTreeNode* RemoveImpl(IntrusiveRedBlackTreeNode* node) {
+        return RB_REMOVE(&root, node);
+    }
+
+public:
+    static IntrusiveRedBlackTreeNode* GetNext(IntrusiveRedBlackTreeNode* node) {
+        return RB_NEXT(node);
+    }
+
+    static IntrusiveRedBlackTreeNode* GetPrev(IntrusiveRedBlackTreeNode* node) {
+        return RB_PREV(node);
+    }
+
+    static const IntrusiveRedBlackTreeNode* GetNext(const IntrusiveRedBlackTreeNode* node) {
+        return static_cast<const IntrusiveRedBlackTreeNode*>(
+            GetNext(const_cast<IntrusiveRedBlackTreeNode*>(node)));
+    }
+
+    static const IntrusiveRedBlackTreeNode* GetPrev(const IntrusiveRedBlackTreeNode* node) {
+        return static_cast<const IntrusiveRedBlackTreeNode*>(
+            GetPrev(const_cast<IntrusiveRedBlackTreeNode*>(node)));
+    }
+
+public:
+    constexpr IntrusiveRedBlackTreeImpl() {}
+
+    // Iterator accessors.
+    iterator begin() {
+        return iterator(this->GetMinImpl());
+    }
+
+    const_iterator begin() const {
+        return const_iterator(this->GetMinImpl());
+    }
+
+    iterator end() {
+        return iterator(static_cast<IntrusiveRedBlackTreeNode*>(nullptr));
+    }
+
+    const_iterator end() const {
+        return const_iterator(static_cast<const IntrusiveRedBlackTreeNode*>(nullptr));
+    }
+
+    const_iterator cbegin() const {
+        return this->begin();
+    }
+
+    const_iterator cend() const {
+        return this->end();
+    }
+
+    iterator iterator_to(reference ref) {
+        return iterator(&ref);
+    }
+
+    const_iterator iterator_to(const_reference ref) const {
+        return const_iterator(&ref);
+    }
+
+    // Content management.
+    bool empty() const {
+        return this->EmptyImpl();
+    }
+
+    reference back() {
+        return *this->GetMaxImpl();
+    }
+
+    const_reference back() const {
+        return *this->GetMaxImpl();
+    }
+
+    reference front() {
+        return *this->GetMinImpl();
+    }
+
+    const_reference front() const {
+        return *this->GetMinImpl();
+    }
+
+    iterator erase(iterator it) {
+        auto cur = std::addressof(*it);
+        auto next = GetNext(cur);
+        this->RemoveImpl(cur);
+        return iterator(next);
+    }
+};
+
+} // namespace impl
+
+template <typename T>
+concept HasLightCompareType = requires {
+    { std::is_same<typename T::LightCompareType, void>::value }
+    ->std::convertible_to<bool>;
+};
+
+namespace impl {
+
+template <typename T, typename Default>
+consteval auto* GetLightCompareType() {
+    if constexpr (HasLightCompareType<T>) {
+        return static_cast<typename T::LightCompareType*>(nullptr);
+    } else {
+        return static_cast<Default*>(nullptr);
+    }
+}
+
+} // namespace impl
+
+template <typename T, typename Default>
+using LightCompareType = std::remove_pointer_t<decltype(impl::GetLightCompareType<T, Default>())>;
+
+template <class T, class Traits, class Comparator>
+class IntrusiveRedBlackTree {
+
+public:
+    using ImplType = impl::IntrusiveRedBlackTreeImpl;
+
+private:
+    ImplType impl{};
+
+public:
+    template <bool Const>
+    class Iterator;
+
+    using value_type = T;
+    using size_type = size_t;
+    using difference_type = ptrdiff_t;
+    using pointer = T*;
+    using const_pointer = const T*;
+    using reference = T&;
+    using const_reference = const T&;
+    using iterator = Iterator<false>;
+    using const_iterator = Iterator<true>;
+
+    using light_value_type = LightCompareType<Comparator, value_type>;
+    using const_light_pointer = const light_value_type*;
+    using const_light_reference = const light_value_type&;
+
+    template <bool Const>
+    class Iterator {
+    public:
+        friend class IntrusiveRedBlackTree<T, Traits, Comparator>;
+
+        using ImplIterator =
+            std::conditional_t<Const, ImplType::const_iterator, ImplType::iterator>;
+
+        using iterator_category = std::bidirectional_iterator_tag;
+        using value_type = typename IntrusiveRedBlackTree::value_type;
+        using difference_type = typename IntrusiveRedBlackTree::difference_type;
+        using pointer = std::conditional_t<Const, IntrusiveRedBlackTree::const_pointer,
+                                           IntrusiveRedBlackTree::pointer>;
+        using reference = std::conditional_t<Const, IntrusiveRedBlackTree::const_reference,
+                                             IntrusiveRedBlackTree::reference>;
+
+    private:
+        ImplIterator iterator;
+
+    private:
+        explicit Iterator(ImplIterator it) : iterator(it) {}
+
+        explicit Iterator(typename std::conditional<Const, ImplType::const_iterator,
+                                                    ImplType::iterator>::type::pointer ptr)
+            : iterator(ptr) {}
+
+        ImplIterator GetImplIterator() const {
+            return this->iterator;
+        }
+
+    public:
+        bool operator==(const Iterator& rhs) const {
+            return this->iterator == rhs.iterator;
+        }
+
+        bool operator!=(const Iterator& rhs) const {
+            return !(*this == rhs);
+        }
+
+        pointer operator->() const {
+            return Traits::GetParent(std::addressof(*this->iterator));
+        }
+
+        reference operator*() const {
+            return *Traits::GetParent(std::addressof(*this->iterator));
+        }
+
+        Iterator& operator++() {
+            ++this->iterator;
+            return *this;
+        }
+
+        Iterator& operator--() {
+            --this->iterator;
+            return *this;
+        }
+
+        Iterator operator++(int) {
+            const Iterator it{*this};
+            ++this->iterator;
+            return it;
+        }
+
+        Iterator operator--(int) {
+            const Iterator it{*this};
+            --this->iterator;
+            return it;
+        }
+
+        operator Iterator<true>() const {
+            return Iterator<true>(this->iterator);
+        }
+    };
+
+private:
+    static int CompareImpl(const IntrusiveRedBlackTreeNode* lhs,
+                           const IntrusiveRedBlackTreeNode* rhs) {
+        return Comparator::Compare(*Traits::GetParent(lhs), *Traits::GetParent(rhs));
+    }
+
+    static int LightCompareImpl(const void* elm, const IntrusiveRedBlackTreeNode* rhs) {
+        return Comparator::Compare(*static_cast<const_light_pointer>(elm), *Traits::GetParent(rhs));
+    }
+
+    // Define accessors using RB_* functions.
+    IntrusiveRedBlackTreeNode* InsertImpl(IntrusiveRedBlackTreeNode* node) {
+        return RB_INSERT(&impl.root, node, CompareImpl);
+    }
+
+    IntrusiveRedBlackTreeNode* FindImpl(const IntrusiveRedBlackTreeNode* node) const {
+        return RB_FIND(const_cast<ImplType::RootType*>(&impl.root),
+                       const_cast<IntrusiveRedBlackTreeNode*>(node), CompareImpl);
+    }
+
+    IntrusiveRedBlackTreeNode* NFindImpl(const IntrusiveRedBlackTreeNode* node) const {
+        return RB_NFIND(const_cast<ImplType::RootType*>(&impl.root),
+                        const_cast<IntrusiveRedBlackTreeNode*>(node), CompareImpl);
+    }
+
+    IntrusiveRedBlackTreeNode* FindLightImpl(const_light_pointer lelm) const {
+        return RB_FIND_LIGHT(const_cast<ImplType::RootType*>(&impl.root),
+                             static_cast<const void*>(lelm), LightCompareImpl);
+    }
+
+    IntrusiveRedBlackTreeNode* NFindLightImpl(const_light_pointer lelm) const {
+        return RB_NFIND_LIGHT(const_cast<ImplType::RootType*>(&impl.root),
+                              static_cast<const void*>(lelm), LightCompareImpl);
+    }
+
+public:
+    constexpr IntrusiveRedBlackTree() = default;
+
+    // Iterator accessors.
+    iterator begin() {
+        return iterator(this->impl.begin());
+    }
+
+    const_iterator begin() const {
+        return const_iterator(this->impl.begin());
+    }
+
+    iterator end() {
+        return iterator(this->impl.end());
+    }
+
+    const_iterator end() const {
+        return const_iterator(this->impl.end());
+    }
+
+    const_iterator cbegin() const {
+        return this->begin();
+    }
+
+    const_iterator cend() const {
+        return this->end();
+    }
+
+    iterator iterator_to(reference ref) {
+        return iterator(this->impl.iterator_to(*Traits::GetNode(std::addressof(ref))));
+    }
+
+    const_iterator iterator_to(const_reference ref) const {
+        return const_iterator(this->impl.iterator_to(*Traits::GetNode(std::addressof(ref))));
+    }
+
+    // Content management.
+    bool empty() const {
+        return this->impl.empty();
+    }
+
+    reference back() {
+        return *Traits::GetParent(std::addressof(this->impl.back()));
+    }
+
+    const_reference back() const {
+        return *Traits::GetParent(std::addressof(this->impl.back()));
+    }
+
+    reference front() {
+        return *Traits::GetParent(std::addressof(this->impl.front()));
+    }
+
+    const_reference front() const {
+        return *Traits::GetParent(std::addressof(this->impl.front()));
+    }
+
+    iterator erase(iterator it) {
+        return iterator(this->impl.erase(it.GetImplIterator()));
+    }
+
+    iterator insert(reference ref) {
+        ImplType::pointer node = Traits::GetNode(std::addressof(ref));
+        this->InsertImpl(node);
+        return iterator(node);
+    }
+
+    iterator find(const_reference ref) const {
+        return iterator(this->FindImpl(Traits::GetNode(std::addressof(ref))));
+    }
+
+    iterator nfind(const_reference ref) const {
+        return iterator(this->NFindImpl(Traits::GetNode(std::addressof(ref))));
+    }
+
+    iterator find_light(const_light_reference ref) const {
+        return iterator(this->FindLightImpl(std::addressof(ref)));
+    }
+
+    iterator nfind_light(const_light_reference ref) const {
+        return iterator(this->NFindLightImpl(std::addressof(ref)));
+    }
+};
+
+template <auto T, class Derived = impl::GetParentType<T>>
+class IntrusiveRedBlackTreeMemberTraits;
+
+template <class Parent, IntrusiveRedBlackTreeNode Parent::*Member, class Derived>
+class IntrusiveRedBlackTreeMemberTraits<Member, Derived> {
+public:
+    template <class Comparator>
+    using TreeType = IntrusiveRedBlackTree<Derived, IntrusiveRedBlackTreeMemberTraits, Comparator>;
+    using TreeTypeImpl = impl::IntrusiveRedBlackTreeImpl;
+
+private:
+    template <class, class, class>
+    friend class IntrusiveRedBlackTree;
+
+    friend class impl::IntrusiveRedBlackTreeImpl;
+
+    static constexpr IntrusiveRedBlackTreeNode* GetNode(Derived* parent) {
+        return std::addressof(parent->*Member);
+    }
+
+    static constexpr IntrusiveRedBlackTreeNode const* GetNode(Derived const* parent) {
+        return std::addressof(parent->*Member);
+    }
+
+    static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
+        return GetParentPointer<Member, Derived>(node);
+    }
+
+    static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) {
+        return GetParentPointer<Member, Derived>(node);
+    }
+
+private:
+    static constexpr TypedStorage<Derived> DerivedStorage = {};
+    static_assert(GetParent(GetNode(GetPointer(DerivedStorage))) == GetPointer(DerivedStorage));
+};
+
+template <auto T, class Derived = impl::GetParentType<T>>
+class IntrusiveRedBlackTreeMemberTraitsDeferredAssert;
+
+template <class Parent, IntrusiveRedBlackTreeNode Parent::*Member, class Derived>
+class IntrusiveRedBlackTreeMemberTraitsDeferredAssert<Member, Derived> {
+public:
+    template <class Comparator>
+    using TreeType =
+        IntrusiveRedBlackTree<Derived, IntrusiveRedBlackTreeMemberTraitsDeferredAssert, Comparator>;
+    using TreeTypeImpl = impl::IntrusiveRedBlackTreeImpl;
+
+    static constexpr bool IsValid() {
+        TypedStorage<Derived> DerivedStorage = {};
+        return GetParent(GetNode(GetPointer(DerivedStorage))) == GetPointer(DerivedStorage);
+    }
+
+private:
+    template <class, class, class>
+    friend class IntrusiveRedBlackTree;
+
+    friend class impl::IntrusiveRedBlackTreeImpl;
+
+    static constexpr IntrusiveRedBlackTreeNode* GetNode(Derived* parent) {
+        return std::addressof(parent->*Member);
+    }
+
+    static constexpr IntrusiveRedBlackTreeNode const* GetNode(Derived const* parent) {
+        return std::addressof(parent->*Member);
+    }
+
+    static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
+        return GetParentPointer<Member, Derived>(node);
+    }
+
+    static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) {
+        return GetParentPointer<Member, Derived>(node);
+    }
+};
+
+template <class Derived>
+class IntrusiveRedBlackTreeBaseNode : public IntrusiveRedBlackTreeNode {
+public:
+    constexpr Derived* GetPrev() {
+        return static_cast<Derived*>(impl::IntrusiveRedBlackTreeImpl::GetPrev(this));
+    }
+    constexpr const Derived* GetPrev() const {
+        return static_cast<const Derived*>(impl::IntrusiveRedBlackTreeImpl::GetPrev(this));
+    }
+
+    constexpr Derived* GetNext() {
+        return static_cast<Derived*>(impl::IntrusiveRedBlackTreeImpl::GetNext(this));
+    }
+    constexpr const Derived* GetNext() const {
+        return static_cast<const Derived*>(impl::IntrusiveRedBlackTreeImpl::GetNext(this));
+    }
+};
+
+template <class Derived>
+class IntrusiveRedBlackTreeBaseTraits {
+public:
+    template <class Comparator>
+    using TreeType = IntrusiveRedBlackTree<Derived, IntrusiveRedBlackTreeBaseTraits, Comparator>;
+    using TreeTypeImpl = impl::IntrusiveRedBlackTreeImpl;
+
+private:
+    template <class, class, class>
+    friend class IntrusiveRedBlackTree;
+
+    friend class impl::IntrusiveRedBlackTreeImpl;
+
+    static constexpr IntrusiveRedBlackTreeNode* GetNode(Derived* parent) {
+        return static_cast<IntrusiveRedBlackTreeNode*>(parent);
+    }
+
+    static constexpr IntrusiveRedBlackTreeNode const* GetNode(Derived const* parent) {
+        return static_cast<const IntrusiveRedBlackTreeNode*>(parent);
+    }
+
+    static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
+        return static_cast<Derived*>(node);
+    }
+
+    static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) {
+        return static_cast<const Derived*>(node);
+    }
+};
+
+} // namespace Common
diff --git a/src/common/logging/backend.cpp b/src/common/logging/backend.cpp
index 631f64d05..2d4d2e9e7 100644
--- a/src/common/logging/backend.cpp
+++ b/src/common/logging/backend.cpp
@@ -145,10 +145,18 @@ void ColorConsoleBackend::Write(const Entry& entry) {
     PrintColoredMessage(entry);
 }
 
-// _SH_DENYWR allows read only access to the file for other programs.
-// It is #defined to 0 on other platforms
-FileBackend::FileBackend(const std::string& filename)
-    : file(filename, "w", _SH_DENYWR), bytes_written(0) {}
+FileBackend::FileBackend(const std::string& filename) : bytes_written(0) {
+    if (Common::FS::Exists(filename + ".old.txt")) {
+        Common::FS::Delete(filename + ".old.txt");
+    }
+    if (Common::FS::Exists(filename)) {
+        Common::FS::Rename(filename, filename + ".old.txt");
+    }
+
+    // _SH_DENYWR allows read only access to the file for other programs.
+    // It is #defined to 0 on other platforms
+    file = Common::FS::IOFile(filename, "w", _SH_DENYWR);
+}
 
 void FileBackend::Write(const Entry& entry) {
     // prevent logs from going over the maximum size (in case its spamming and the user doesn't
diff --git a/src/common/parent_of_member.h b/src/common/parent_of_member.h
new file mode 100644
index 000000000..d9a14529d
--- /dev/null
+++ b/src/common/parent_of_member.h
@@ -0,0 +1,191 @@
+// Copyright 2021 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#pragma once
+
+#include <type_traits>
+
+#include "common/assert.h"
+#include "common/common_types.h"
+
+namespace Common {
+namespace detail {
+template <typename T, size_t Size, size_t Align>
+struct TypedStorageImpl {
+    std::aligned_storage_t<Size, Align> storage_;
+};
+} // namespace detail
+
+template <typename T>
+using TypedStorage = detail::TypedStorageImpl<T, sizeof(T), alignof(T)>;
+
+template <typename T>
+static constexpr T* GetPointer(TypedStorage<T>& ts) {
+    return static_cast<T*>(static_cast<void*>(std::addressof(ts.storage_)));
+}
+
+template <typename T>
+static constexpr const T* GetPointer(const TypedStorage<T>& ts) {
+    return static_cast<const T*>(static_cast<const void*>(std::addressof(ts.storage_)));
+}
+
+namespace impl {
+
+template <size_t MaxDepth>
+struct OffsetOfUnionHolder {
+    template <typename ParentType, typename MemberType, size_t Offset>
+    union UnionImpl {
+        using PaddingMember = char;
+        static constexpr size_t GetOffset() {
+            return Offset;
+        }
+
+#pragma pack(push, 1)
+        struct {
+            PaddingMember padding[Offset];
+            MemberType members[(sizeof(ParentType) / sizeof(MemberType)) + 1];
+        } data;
+#pragma pack(pop)
+        UnionImpl<ParentType, MemberType, Offset + 1> next_union;
+    };
+
+    template <typename ParentType, typename MemberType>
+    union UnionImpl<ParentType, MemberType, 0> {
+        static constexpr size_t GetOffset() {
+            return 0;
+        }
+
+        struct {
+            MemberType members[(sizeof(ParentType) / sizeof(MemberType)) + 1];
+        } data;
+        UnionImpl<ParentType, MemberType, 1> next_union;
+    };
+
+    template <typename ParentType, typename MemberType>
+    union UnionImpl<ParentType, MemberType, MaxDepth> {};
+};
+
+template <typename ParentType, typename MemberType>
+struct OffsetOfCalculator {
+    using UnionHolder =
+        typename OffsetOfUnionHolder<sizeof(MemberType)>::template UnionImpl<ParentType, MemberType,
+                                                                             0>;
+    union Union {
+        char c{};
+        UnionHolder first_union;
+        TypedStorage<ParentType> parent;
+
+        constexpr Union() : c() {}
+    };
+    static constexpr Union U = {};
+
+    static constexpr const MemberType* GetNextAddress(const MemberType* start,
+                                                      const MemberType* target) {
+        while (start < target) {
+            start++;
+        }
+        return start;
+    }
+
+    static constexpr std::ptrdiff_t GetDifference(const MemberType* start,
+                                                  const MemberType* target) {
+        return (target - start) * sizeof(MemberType);
+    }
+
+    template <typename CurUnion>
+    static constexpr std::ptrdiff_t OffsetOfImpl(MemberType ParentType::*member,
+                                                 CurUnion& cur_union) {
+        constexpr size_t Offset = CurUnion::GetOffset();
+        const auto target = std::addressof(GetPointer(U.parent)->*member);
+        const auto start = std::addressof(cur_union.data.members[0]);
+        const auto next = GetNextAddress(start, target);
+
+        if (next != target) {
+            if constexpr (Offset < sizeof(MemberType) - 1) {
+                return OffsetOfImpl(member, cur_union.next_union);
+            } else {
+                UNREACHABLE();
+            }
+        }
+
+        return (next - start) * sizeof(MemberType) + Offset;
+    }
+
+    static constexpr std::ptrdiff_t OffsetOf(MemberType ParentType::*member) {
+        return OffsetOfImpl(member, U.first_union);
+    }
+};
+
+template <typename T>
+struct GetMemberPointerTraits;
+
+template <typename P, typename M>
+struct GetMemberPointerTraits<M P::*> {
+    using Parent = P;
+    using Member = M;
+};
+
+template <auto MemberPtr>
+using GetParentType = typename GetMemberPointerTraits<decltype(MemberPtr)>::Parent;
+
+template <auto MemberPtr>
+using GetMemberType = typename GetMemberPointerTraits<decltype(MemberPtr)>::Member;
+
+template <auto MemberPtr, typename RealParentType = GetParentType<MemberPtr>>
+static inline std::ptrdiff_t OffsetOf = [] {
+    using DeducedParentType = GetParentType<MemberPtr>;
+    using MemberType = GetMemberType<MemberPtr>;
+    static_assert(std::is_base_of<DeducedParentType, RealParentType>::value ||
+                  std::is_same<RealParentType, DeducedParentType>::value);
+
+    return OffsetOfCalculator<RealParentType, MemberType>::OffsetOf(MemberPtr);
+}();
+
+} // namespace impl
+
+template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
+constexpr RealParentType& GetParentReference(impl::GetMemberType<MemberPtr>* member) {
+    std::ptrdiff_t Offset = impl::OffsetOf<MemberPtr, RealParentType>;
+    return *static_cast<RealParentType*>(
+        static_cast<void*>(static_cast<uint8_t*>(static_cast<void*>(member)) - Offset));
+}
+
+template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
+constexpr RealParentType const& GetParentReference(impl::GetMemberType<MemberPtr> const* member) {
+    std::ptrdiff_t Offset = impl::OffsetOf<MemberPtr, RealParentType>;
+    return *static_cast<const RealParentType*>(static_cast<const void*>(
+        static_cast<const uint8_t*>(static_cast<const void*>(member)) - Offset));
+}
+
+template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
+constexpr RealParentType* GetParentPointer(impl::GetMemberType<MemberPtr>* member) {
+    return std::addressof(GetParentReference<MemberPtr, RealParentType>(member));
+}
+
+template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
+constexpr RealParentType const* GetParentPointer(impl::GetMemberType<MemberPtr> const* member) {
+    return std::addressof(GetParentReference<MemberPtr, RealParentType>(member));
+}
+
+template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
+constexpr RealParentType& GetParentReference(impl::GetMemberType<MemberPtr>& member) {
+    return GetParentReference<MemberPtr, RealParentType>(std::addressof(member));
+}
+
+template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
+constexpr RealParentType const& GetParentReference(impl::GetMemberType<MemberPtr> const& member) {
+    return GetParentReference<MemberPtr, RealParentType>(std::addressof(member));
+}
+
+template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
+constexpr RealParentType* GetParentPointer(impl::GetMemberType<MemberPtr>& member) {
+    return std::addressof(GetParentReference<MemberPtr, RealParentType>(member));
+}
+
+template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
+constexpr RealParentType const* GetParentPointer(impl::GetMemberType<MemberPtr> const& member) {
+    return std::addressof(GetParentReference<MemberPtr, RealParentType>(member));
+}
+
+} // namespace Common
diff --git a/src/common/timer.cpp b/src/common/timer.cpp
deleted file mode 100644
index d17dc2a50..000000000
--- a/src/common/timer.cpp
+++ /dev/null
@@ -1,159 +0,0 @@
-// Copyright 2013 Dolphin Emulator Project / 2014 Citra Emulator Project
-// Licensed under GPLv2 or any later version
-// Refer to the license.txt file included.
-
-#include <ctime>
-#include <fmt/format.h>
-#include "common/common_types.h"
-#include "common/string_util.h"
-#include "common/timer.h"
-
-namespace Common {
-
-std::chrono::milliseconds Timer::GetTimeMs() {
-    return std::chrono::duration_cast<std::chrono::milliseconds>(
-        std::chrono::system_clock::now().time_since_epoch());
-}
-
-// --------------------------------------------
-// Initiate, Start, Stop, and Update the time
-// --------------------------------------------
-
-// Set initial values for the class
-Timer::Timer() : m_LastTime(0), m_StartTime(0), m_Running(false) {
-    Update();
-}
-
-// Write the starting time
-void Timer::Start() {
-    m_StartTime = GetTimeMs();
-    m_Running = true;
-}
-
-// Stop the timer
-void Timer::Stop() {
-    // Write the final time
-    m_LastTime = GetTimeMs();
-    m_Running = false;
-}
-
-// Update the last time variable
-void Timer::Update() {
-    m_LastTime = GetTimeMs();
-    // TODO(ector) - QPF
-}
-
-// -------------------------------------
-// Get time difference and elapsed time
-// -------------------------------------
-
-// Get the number of milliseconds since the last Update()
-std::chrono::milliseconds Timer::GetTimeDifference() {
-    return GetTimeMs() - m_LastTime;
-}
-
-// Add the time difference since the last Update() to the starting time.
-// This is used to compensate for a paused game.
-void Timer::AddTimeDifference() {
-    m_StartTime += GetTimeDifference();
-}
-
-// Get the time elapsed since the Start()
-std::chrono::milliseconds Timer::GetTimeElapsed() {
-    // If we have not started yet, return 1 (because then I don't
-    // have to change the FPS calculation in CoreRerecording.cpp .
-    if (m_StartTime.count() == 0)
-        return std::chrono::milliseconds(1);
-
-    // Return the final timer time if the timer is stopped
-    if (!m_Running)
-        return (m_LastTime - m_StartTime);
-
-    return (GetTimeMs() - m_StartTime);
-}
-
-// Get the formatted time elapsed since the Start()
-std::string Timer::GetTimeElapsedFormatted() const {
-    // If we have not started yet, return zero
-    if (m_StartTime.count() == 0)
-        return "00:00:00:000";
-
-    // The number of milliseconds since the start.
-    // Use a different value if the timer is stopped.
-    std::chrono::milliseconds Milliseconds;
-    if (m_Running)
-        Milliseconds = GetTimeMs() - m_StartTime;
-    else
-        Milliseconds = m_LastTime - m_StartTime;
-    // Seconds
-    std::chrono::seconds Seconds = std::chrono::duration_cast<std::chrono::seconds>(Milliseconds);
-    // Minutes
-    std::chrono::minutes Minutes = std::chrono::duration_cast<std::chrono::minutes>(Milliseconds);
-    // Hours
-    std::chrono::hours Hours = std::chrono::duration_cast<std::chrono::hours>(Milliseconds);
-
-    std::string TmpStr = fmt::format("{:02}:{:02}:{:02}:{:03}", Hours.count(), Minutes.count() % 60,
-                                     Seconds.count() % 60, Milliseconds.count() % 1000);
-    return TmpStr;
-}
-
-// Get the number of seconds since January 1 1970
-std::chrono::seconds Timer::GetTimeSinceJan1970() {
-    return std::chrono::duration_cast<std::chrono::seconds>(GetTimeMs());
-}
-
-std::chrono::seconds Timer::GetLocalTimeSinceJan1970() {
-    time_t sysTime, tzDiff, tzDST;
-    struct tm* gmTime;
-
-    time(&sysTime);
-
-    // Account for DST where needed
-    gmTime = localtime(&sysTime);
-    if (gmTime->tm_isdst == 1)
-        tzDST = 3600;
-    else
-        tzDST = 0;
-
-    // Lazy way to get local time in sec
-    gmTime = gmtime(&sysTime);
-    tzDiff = sysTime - mktime(gmTime);
-
-    return std::chrono::seconds(sysTime + tzDiff + tzDST);
-}
-
-// Return the current time formatted as Minutes:Seconds:Milliseconds
-// in the form 00:00:000.
-std::string Timer::GetTimeFormatted() {
-    time_t sysTime;
-    struct tm* gmTime;
-    char tmp[13];
-
-    time(&sysTime);
-    gmTime = localtime(&sysTime);
-
-    strftime(tmp, 6, "%M:%S", gmTime);
-
-    u64 milliseconds = static_cast<u64>(GetTimeMs().count()) % 1000;
-    return fmt::format("{}:{:03}", tmp, milliseconds);
-}
-
-// Returns a timestamp with decimals for precise time comparisons
-// ----------------
-double Timer::GetDoubleTime() {
-    // Get continuous timestamp
-    auto tmp_seconds = static_cast<u64>(GetTimeSinceJan1970().count());
-    const auto ms = static_cast<double>(static_cast<u64>(GetTimeMs().count()) % 1000);
-
-    // Remove a few years. We only really want enough seconds to make
-    // sure that we are detecting actual actions, perhaps 60 seconds is
-    // enough really, but I leave a year of seconds anyway, in case the
-    // user's clock is incorrect or something like that.
-    tmp_seconds = tmp_seconds - (38 * 365 * 24 * 60 * 60);
-
-    // Make a smaller integer that fits in the double
-    const auto seconds = static_cast<u32>(tmp_seconds);
-    return seconds + ms;
-}
-
-} // Namespace Common
diff --git a/src/common/timer.h b/src/common/timer.h
deleted file mode 100644
index 8894a143d..000000000
--- a/src/common/timer.h
+++ /dev/null
@@ -1,41 +0,0 @@
-// Copyright 2013 Dolphin Emulator Project / 2014 Citra Emulator Project
-// Licensed under GPLv2 or any later version
-// Refer to the license.txt file included.
-
-#pragma once
-
-#include <chrono>
-#include <string>
-#include "common/common_types.h"
-
-namespace Common {
-class Timer {
-public:
-    Timer();
-
-    void Start();
-    void Stop();
-    void Update();
-
-    // The time difference is always returned in milliseconds, regardless of alternative internal
-    // representation
-    [[nodiscard]] std::chrono::milliseconds GetTimeDifference();
-    void AddTimeDifference();
-
-    [[nodiscard]] static std::chrono::seconds GetTimeSinceJan1970();
-    [[nodiscard]] static std::chrono::seconds GetLocalTimeSinceJan1970();
-    [[nodiscard]] static double GetDoubleTime();
-
-    [[nodiscard]] static std::string GetTimeFormatted();
-    [[nodiscard]] std::string GetTimeElapsedFormatted() const;
-    [[nodiscard]] std::chrono::milliseconds GetTimeElapsed();
-
-    [[nodiscard]] static std::chrono::milliseconds GetTimeMs();
-
-private:
-    std::chrono::milliseconds m_LastTime;
-    std::chrono::milliseconds m_StartTime;
-    bool m_Running;
-};
-
-} // Namespace Common
diff --git a/src/common/tree.h b/src/common/tree.h
new file mode 100644
index 000000000..3da49e422
--- /dev/null
+++ b/src/common/tree.h
@@ -0,0 +1,674 @@
+/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */
+/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
+/* $FreeBSD$ */
+
+/*-
+ * Copyright 2002 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+/*
+ * This file defines data structures for red-black trees.
+ *
+ * A red-black tree is a binary search tree with the node color as an
+ * extra attribute.  It fulfills a set of conditions:
+ * - every search path from the root to a leaf consists of the
+ *   same number of black nodes,
+ * - each red node (except for the root) has a black parent,
+ * - each leaf node is black.
+ *
+ * Every operation on a red-black tree is bounded as O(lg n).
+ * The maximum height of a red-black tree is 2lg (n+1).
+ */
+
+namespace Common {
+template <typename T>
+class RBHead {
+public:
+    [[nodiscard]] T* Root() {
+        return rbh_root;
+    }
+
+    [[nodiscard]] const T* Root() const {
+        return rbh_root;
+    }
+
+    void SetRoot(T* root) {
+        rbh_root = root;
+    }
+
+    [[nodiscard]] bool IsEmpty() const {
+        return Root() == nullptr;
+    }
+
+private:
+    T* rbh_root = nullptr;
+};
+
+enum class EntryColor {
+    Black,
+    Red,
+};
+
+template <typename T>
+class RBEntry {
+public:
+    [[nodiscard]] T* Left() {
+        return rbe_left;
+    }
+
+    [[nodiscard]] const T* Left() const {
+        return rbe_left;
+    }
+
+    void SetLeft(T* left) {
+        rbe_left = left;
+    }
+
+    [[nodiscard]] T* Right() {
+        return rbe_right;
+    }
+
+    [[nodiscard]] const T* Right() const {
+        return rbe_right;
+    }
+
+    void SetRight(T* right) {
+        rbe_right = right;
+    }
+
+    [[nodiscard]] T* Parent() {
+        return rbe_parent;
+    }
+
+    [[nodiscard]] const T* Parent() const {
+        return rbe_parent;
+    }
+
+    void SetParent(T* parent) {
+        rbe_parent = parent;
+    }
+
+    [[nodiscard]] bool IsBlack() const {
+        return rbe_color == EntryColor::Black;
+    }
+
+    [[nodiscard]] bool IsRed() const {
+        return rbe_color == EntryColor::Red;
+    }
+
+    [[nodiscard]] EntryColor Color() const {
+        return rbe_color;
+    }
+
+    void SetColor(EntryColor color) {
+        rbe_color = color;
+    }
+
+private:
+    T* rbe_left = nullptr;
+    T* rbe_right = nullptr;
+    T* rbe_parent = nullptr;
+    EntryColor rbe_color{};
+};
+
+template <typename Node>
+[[nodiscard]] RBEntry<Node>& RB_ENTRY(Node* node) {
+    return node->GetEntry();
+}
+
+template <typename Node>
+[[nodiscard]] const RBEntry<Node>& RB_ENTRY(const Node* node) {
+    return node->GetEntry();
+}
+
+template <typename Node>
+[[nodiscard]] Node* RB_PARENT(Node* node) {
+    return RB_ENTRY(node).Parent();
+}
+
+template <typename Node>
+[[nodiscard]] const Node* RB_PARENT(const Node* node) {
+    return RB_ENTRY(node).Parent();
+}
+
+template <typename Node>
+void RB_SET_PARENT(Node* node, Node* parent) {
+    return RB_ENTRY(node).SetParent(parent);
+}
+
+template <typename Node>
+[[nodiscard]] Node* RB_LEFT(Node* node) {
+    return RB_ENTRY(node).Left();
+}
+
+template <typename Node>
+[[nodiscard]] const Node* RB_LEFT(const Node* node) {
+    return RB_ENTRY(node).Left();
+}
+
+template <typename Node>
+void RB_SET_LEFT(Node* node, Node* left) {
+    return RB_ENTRY(node).SetLeft(left);
+}
+
+template <typename Node>
+[[nodiscard]] Node* RB_RIGHT(Node* node) {
+    return RB_ENTRY(node).Right();
+}
+
+template <typename Node>
+[[nodiscard]] const Node* RB_RIGHT(const Node* node) {
+    return RB_ENTRY(node).Right();
+}
+
+template <typename Node>
+void RB_SET_RIGHT(Node* node, Node* right) {
+    return RB_ENTRY(node).SetRight(right);
+}
+
+template <typename Node>
+[[nodiscard]] bool RB_IS_BLACK(const Node* node) {
+    return RB_ENTRY(node).IsBlack();
+}
+
+template <typename Node>
+[[nodiscard]] bool RB_IS_RED(const Node* node) {
+    return RB_ENTRY(node).IsRed();
+}
+
+template <typename Node>
+[[nodiscard]] EntryColor RB_COLOR(const Node* node) {
+    return RB_ENTRY(node).Color();
+}
+
+template <typename Node>
+void RB_SET_COLOR(Node* node, EntryColor color) {
+    return RB_ENTRY(node).SetColor(color);
+}
+
+template <typename Node>
+void RB_SET(Node* node, Node* parent) {
+    auto& entry = RB_ENTRY(node);
+    entry.SetParent(parent);
+    entry.SetLeft(nullptr);
+    entry.SetRight(nullptr);
+    entry.SetColor(EntryColor::Red);
+}
+
+template <typename Node>
+void RB_SET_BLACKRED(Node* black, Node* red) {
+    RB_SET_COLOR(black, EntryColor::Black);
+    RB_SET_COLOR(red, EntryColor::Red);
+}
+
+template <typename Node>
+void RB_ROTATE_LEFT(RBHead<Node>* head, Node* elm, Node*& tmp) {
+    tmp = RB_RIGHT(elm);
+    RB_SET_RIGHT(elm, RB_LEFT(tmp));
+    if (RB_RIGHT(elm) != nullptr) {
+        RB_SET_PARENT(RB_LEFT(tmp), elm);
+    }
+
+    RB_SET_PARENT(tmp, RB_PARENT(elm));
+    if (RB_PARENT(tmp) != nullptr) {
+        if (elm == RB_LEFT(RB_PARENT(elm))) {
+            RB_SET_LEFT(RB_PARENT(elm), tmp);
+        } else {
+            RB_SET_RIGHT(RB_PARENT(elm), tmp);
+        }
+    } else {
+        head->SetRoot(tmp);
+    }
+
+    RB_SET_LEFT(tmp, elm);
+    RB_SET_PARENT(elm, tmp);
+}
+
+template <typename Node>
+void RB_ROTATE_RIGHT(RBHead<Node>* head, Node* elm, Node*& tmp) {
+    tmp = RB_LEFT(elm);
+    RB_SET_LEFT(elm, RB_RIGHT(tmp));
+    if (RB_LEFT(elm) != nullptr) {
+        RB_SET_PARENT(RB_RIGHT(tmp), elm);
+    }
+
+    RB_SET_PARENT(tmp, RB_PARENT(elm));
+    if (RB_PARENT(tmp) != nullptr) {
+        if (elm == RB_LEFT(RB_PARENT(elm))) {
+            RB_SET_LEFT(RB_PARENT(elm), tmp);
+        } else {
+            RB_SET_RIGHT(RB_PARENT(elm), tmp);
+        }
+    } else {
+        head->SetRoot(tmp);
+    }
+
+    RB_SET_RIGHT(tmp, elm);
+    RB_SET_PARENT(elm, tmp);
+}
+
+template <typename Node>
+void RB_INSERT_COLOR(RBHead<Node>* head, Node* elm) {
+    Node* parent = nullptr;
+    Node* tmp = nullptr;
+
+    while ((parent = RB_PARENT(elm)) != nullptr && RB_IS_RED(parent)) {
+        Node* gparent = RB_PARENT(parent);
+        if (parent == RB_LEFT(gparent)) {
+            tmp = RB_RIGHT(gparent);
+            if (tmp && RB_IS_RED(tmp)) {
+                RB_SET_COLOR(tmp, EntryColor::Black);
+                RB_SET_BLACKRED(parent, gparent);
+                elm = gparent;
+                continue;
+            }
+
+            if (RB_RIGHT(parent) == elm) {
+                RB_ROTATE_LEFT(head, parent, tmp);
+                tmp = parent;
+                parent = elm;
+                elm = tmp;
+            }
+
+            RB_SET_BLACKRED(parent, gparent);
+            RB_ROTATE_RIGHT(head, gparent, tmp);
+        } else {
+            tmp = RB_LEFT(gparent);
+            if (tmp && RB_IS_RED(tmp)) {
+                RB_SET_COLOR(tmp, EntryColor::Black);
+                RB_SET_BLACKRED(parent, gparent);
+                elm = gparent;
+                continue;
+            }
+
+            if (RB_LEFT(parent) == elm) {
+                RB_ROTATE_RIGHT(head, parent, tmp);
+                tmp = parent;
+                parent = elm;
+                elm = tmp;
+            }
+
+            RB_SET_BLACKRED(parent, gparent);
+            RB_ROTATE_LEFT(head, gparent, tmp);
+        }
+    }
+
+    RB_SET_COLOR(head->Root(), EntryColor::Black);
+}
+
+template <typename Node>
+void RB_REMOVE_COLOR(RBHead<Node>* head, Node* parent, Node* elm) {
+    Node* tmp;
+    while ((elm == nullptr || RB_IS_BLACK(elm)) && elm != head->Root()) {
+        if (RB_LEFT(parent) == elm) {
+            tmp = RB_RIGHT(parent);
+            if (RB_IS_RED(tmp)) {
+                RB_SET_BLACKRED(tmp, parent);
+                RB_ROTATE_LEFT(head, parent, tmp);
+                tmp = RB_RIGHT(parent);
+            }
+
+            if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) &&
+                (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) {
+                RB_SET_COLOR(tmp, EntryColor::Red);
+                elm = parent;
+                parent = RB_PARENT(elm);
+            } else {
+                if (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp))) {
+                    Node* oleft;
+                    if ((oleft = RB_LEFT(tmp)) != nullptr) {
+                        RB_SET_COLOR(oleft, EntryColor::Black);
+                    }
+
+                    RB_SET_COLOR(tmp, EntryColor::Red);
+                    RB_ROTATE_RIGHT(head, tmp, oleft);
+                    tmp = RB_RIGHT(parent);
+                }
+
+                RB_SET_COLOR(tmp, RB_COLOR(parent));
+                RB_SET_COLOR(parent, EntryColor::Black);
+                if (RB_RIGHT(tmp)) {
+                    RB_SET_COLOR(RB_RIGHT(tmp), EntryColor::Black);
+                }
+
+                RB_ROTATE_LEFT(head, parent, tmp);
+                elm = head->Root();
+                break;
+            }
+        } else {
+            tmp = RB_LEFT(parent);
+            if (RB_IS_RED(tmp)) {
+                RB_SET_BLACKRED(tmp, parent);
+                RB_ROTATE_RIGHT(head, parent, tmp);
+                tmp = RB_LEFT(parent);
+            }
+
+            if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) &&
+                (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) {
+                RB_SET_COLOR(tmp, EntryColor::Red);
+                elm = parent;
+                parent = RB_PARENT(elm);
+            } else {
+                if (RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) {
+                    Node* oright;
+                    if ((oright = RB_RIGHT(tmp)) != nullptr) {
+                        RB_SET_COLOR(oright, EntryColor::Black);
+                    }
+
+                    RB_SET_COLOR(tmp, EntryColor::Red);
+                    RB_ROTATE_LEFT(head, tmp, oright);
+                    tmp = RB_LEFT(parent);
+                }
+
+                RB_SET_COLOR(tmp, RB_COLOR(parent));
+                RB_SET_COLOR(parent, EntryColor::Black);
+
+                if (RB_LEFT(tmp)) {
+                    RB_SET_COLOR(RB_LEFT(tmp), EntryColor::Black);
+                }
+
+                RB_ROTATE_RIGHT(head, parent, tmp);
+                elm = head->Root();
+                break;
+            }
+        }
+    }
+
+    if (elm) {
+        RB_SET_COLOR(elm, EntryColor::Black);
+    }
+}
+
+template <typename Node>
+Node* RB_REMOVE(RBHead<Node>* head, Node* elm) {
+    Node* child = nullptr;
+    Node* parent = nullptr;
+    Node* old = elm;
+    EntryColor color{};
+
+    const auto finalize = [&] {
+        if (color == EntryColor::Black) {
+            RB_REMOVE_COLOR(head, parent, child);
+        }
+
+        return old;
+    };
+
+    if (RB_LEFT(elm) == nullptr) {
+        child = RB_RIGHT(elm);
+    } else if (RB_RIGHT(elm) == nullptr) {
+        child = RB_LEFT(elm);
+    } else {
+        Node* left;
+        elm = RB_RIGHT(elm);
+        while ((left = RB_LEFT(elm)) != nullptr) {
+            elm = left;
+        }
+
+        child = RB_RIGHT(elm);
+        parent = RB_PARENT(elm);
+        color = RB_COLOR(elm);
+
+        if (child) {
+            RB_SET_PARENT(child, parent);
+        }
+        if (parent) {
+            if (RB_LEFT(parent) == elm) {
+                RB_SET_LEFT(parent, child);
+            } else {
+                RB_SET_RIGHT(parent, child);
+            }
+        } else {
+            head->SetRoot(child);
+        }
+
+        if (RB_PARENT(elm) == old) {
+            parent = elm;
+        }
+
+        elm->SetEntry(old->GetEntry());
+
+        if (RB_PARENT(old)) {
+            if (RB_LEFT(RB_PARENT(old)) == old) {
+                RB_SET_LEFT(RB_PARENT(old), elm);
+            } else {
+                RB_SET_RIGHT(RB_PARENT(old), elm);
+            }
+        } else {
+            head->SetRoot(elm);
+        }
+        RB_SET_PARENT(RB_LEFT(old), elm);
+        if (RB_RIGHT(old)) {
+            RB_SET_PARENT(RB_RIGHT(old), elm);
+        }
+        if (parent) {
+            left = parent;
+        }
+
+        return finalize();
+    }
+
+    parent = RB_PARENT(elm);
+    color = RB_COLOR(elm);
+
+    if (child) {
+        RB_SET_PARENT(child, parent);
+    }
+    if (parent) {
+        if (RB_LEFT(parent) == elm) {
+            RB_SET_LEFT(parent, child);
+        } else {
+            RB_SET_RIGHT(parent, child);
+        }
+    } else {
+        head->SetRoot(child);
+    }
+
+    return finalize();
+}
+
+// Inserts a node into the RB tree
+template <typename Node, typename CompareFunction>
+Node* RB_INSERT(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
+    Node* parent = nullptr;
+    Node* tmp = head->Root();
+    int comp = 0;
+
+    while (tmp) {
+        parent = tmp;
+        comp = cmp(elm, parent);
+        if (comp < 0) {
+            tmp = RB_LEFT(tmp);
+        } else if (comp > 0) {
+            tmp = RB_RIGHT(tmp);
+        } else {
+            return tmp;
+        }
+    }
+
+    RB_SET(elm, parent);
+
+    if (parent != nullptr) {
+        if (comp < 0) {
+            RB_SET_LEFT(parent, elm);
+        } else {
+            RB_SET_RIGHT(parent, elm);
+        }
+    } else {
+        head->SetRoot(elm);
+    }
+
+    RB_INSERT_COLOR(head, elm);
+    return nullptr;
+}
+
+// Finds the node with the same key as elm
+template <typename Node, typename CompareFunction>
+Node* RB_FIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
+    Node* tmp = head->Root();
+
+    while (tmp) {
+        const int comp = cmp(elm, tmp);
+        if (comp < 0) {
+            tmp = RB_LEFT(tmp);
+        } else if (comp > 0) {
+            tmp = RB_RIGHT(tmp);
+        } else {
+            return tmp;
+        }
+    }
+
+    return nullptr;
+}
+
+// Finds the first node greater than or equal to the search key
+template <typename Node, typename CompareFunction>
+Node* RB_NFIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
+    Node* tmp = head->Root();
+    Node* res = nullptr;
+
+    while (tmp) {
+        const int comp = cmp(elm, tmp);
+        if (comp < 0) {
+            res = tmp;
+            tmp = RB_LEFT(tmp);
+        } else if (comp > 0) {
+            tmp = RB_RIGHT(tmp);
+        } else {
+            return tmp;
+        }
+    }
+
+    return res;
+}
+
+// Finds the node with the same key as lelm
+template <typename Node, typename CompareFunction>
+Node* RB_FIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) {
+    Node* tmp = head->Root();
+
+    while (tmp) {
+        const int comp = lcmp(lelm, tmp);
+        if (comp < 0) {
+            tmp = RB_LEFT(tmp);
+        } else if (comp > 0) {
+            tmp = RB_RIGHT(tmp);
+        } else {
+            return tmp;
+        }
+    }
+
+    return nullptr;
+}
+
+// Finds the first node greater than or equal to the search key
+template <typename Node, typename CompareFunction>
+Node* RB_NFIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) {
+    Node* tmp = head->Root();
+    Node* res = nullptr;
+
+    while (tmp) {
+        const int comp = lcmp(lelm, tmp);
+        if (comp < 0) {
+            res = tmp;
+            tmp = RB_LEFT(tmp);
+        } else if (comp > 0) {
+            tmp = RB_RIGHT(tmp);
+        } else {
+            return tmp;
+        }
+    }
+
+    return res;
+}
+
+template <typename Node>
+Node* RB_NEXT(Node* elm) {
+    if (RB_RIGHT(elm)) {
+        elm = RB_RIGHT(elm);
+        while (RB_LEFT(elm)) {
+            elm = RB_LEFT(elm);
+        }
+    } else {
+        if (RB_PARENT(elm) && (elm == RB_LEFT(RB_PARENT(elm)))) {
+            elm = RB_PARENT(elm);
+        } else {
+            while (RB_PARENT(elm) && (elm == RB_RIGHT(RB_PARENT(elm)))) {
+                elm = RB_PARENT(elm);
+            }
+            elm = RB_PARENT(elm);
+        }
+    }
+    return elm;
+}
+
+template <typename Node>
+Node* RB_PREV(Node* elm) {
+    if (RB_LEFT(elm)) {
+        elm = RB_LEFT(elm);
+        while (RB_RIGHT(elm)) {
+            elm = RB_RIGHT(elm);
+        }
+    } else {
+        if (RB_PARENT(elm) && (elm == RB_RIGHT(RB_PARENT(elm)))) {
+            elm = RB_PARENT(elm);
+        } else {
+            while (RB_PARENT(elm) && (elm == RB_LEFT(RB_PARENT(elm)))) {
+                elm = RB_PARENT(elm);
+            }
+            elm = RB_PARENT(elm);
+        }
+    }
+    return elm;
+}
+
+template <typename Node>
+Node* RB_MINMAX(RBHead<Node>* head, bool is_min) {
+    Node* tmp = head->Root();
+    Node* parent = nullptr;
+
+    while (tmp) {
+        parent = tmp;
+        if (is_min) {
+            tmp = RB_LEFT(tmp);
+        } else {
+            tmp = RB_RIGHT(tmp);
+        }
+    }
+
+    return parent;
+}
+
+template <typename Node>
+Node* RB_MIN(RBHead<Node>* head) {
+    return RB_MINMAX(head, true);
+}
+
+template <typename Node>
+Node* RB_MAX(RBHead<Node>* head) {
+    return RB_MINMAX(head, false);
+}
+} // namespace Common
diff --git a/src/common/uuid.h b/src/common/uuid.h
index 4ab9a25f0..2e7a18405 100644
--- a/src/common/uuid.h
+++ b/src/common/uuid.h
@@ -14,8 +14,8 @@ constexpr u128 INVALID_UUID{{0, 0}};
 
 struct UUID {
     // UUIDs which are 0 are considered invalid!
-    u128 uuid = INVALID_UUID;
-    constexpr UUID() = default;
+    u128 uuid;
+    UUID() = default;
     constexpr explicit UUID(const u128& id) : uuid{id} {}
     constexpr explicit UUID(const u64 lo, const u64 hi) : uuid{{lo, hi}} {}
 
diff --git a/src/common/x64/native_clock.cpp b/src/common/x64/native_clock.cpp
index eb8a7782f..a65f6b832 100644
--- a/src/common/x64/native_clock.cpp
+++ b/src/common/x64/native_clock.cpp
@@ -2,19 +2,74 @@
 // Licensed under GPLv2 or any later version
 // Refer to the license.txt file included.
 
+#include <array>
 #include <chrono>
+#include <limits>
 #include <mutex>
 #include <thread>
 
 #ifdef _MSC_VER
 #include <intrin.h>
+
+#pragma intrinsic(__umulh)
+#pragma intrinsic(_udiv128)
 #else
 #include <x86intrin.h>
 #endif
 
+#include "common/atomic_ops.h"
 #include "common/uint128.h"
 #include "common/x64/native_clock.h"
 
+namespace {
+
+[[nodiscard]] u64 GetFixedPoint64Factor(u64 numerator, u64 divisor) {
+#ifdef __SIZEOF_INT128__
+    const auto base = static_cast<unsigned __int128>(numerator) << 64ULL;
+    return static_cast<u64>(base / divisor);
+#elif defined(_M_X64) || defined(_M_ARM64)
+    std::array<u64, 2> r = {0, numerator};
+    u64 remainder;
+#if _MSC_VER < 1923
+    return udiv128(r[1], r[0], divisor, &remainder);
+#else
+    return _udiv128(r[1], r[0], divisor, &remainder);
+#endif
+#else
+    // This one is bit more inaccurate.
+    return MultiplyAndDivide64(std::numeric_limits<u64>::max(), numerator, divisor);
+#endif
+}
+
+[[nodiscard]] u64 MultiplyHigh(u64 a, u64 b) {
+#ifdef __SIZEOF_INT128__
+    return (static_cast<unsigned __int128>(a) * static_cast<unsigned __int128>(b)) >> 64;
+#elif defined(_M_X64) || defined(_M_ARM64)
+    return __umulh(a, b); // MSVC
+#else
+    // Generic fallback
+    const u64 a_lo = u32(a);
+    const u64 a_hi = a >> 32;
+    const u64 b_lo = u32(b);
+    const u64 b_hi = b >> 32;
+
+    const u64 a_x_b_hi = a_hi * b_hi;
+    const u64 a_x_b_mid = a_hi * b_lo;
+    const u64 b_x_a_mid = b_hi * a_lo;
+    const u64 a_x_b_lo = a_lo * b_lo;
+
+    const u64 carry_bit = (static_cast<u64>(static_cast<u32>(a_x_b_mid)) +
+                           static_cast<u64>(static_cast<u32>(b_x_a_mid)) + (a_x_b_lo >> 32)) >>
+                          32;
+
+    const u64 multhi = a_x_b_hi + (a_x_b_mid >> 32) + (b_x_a_mid >> 32) + carry_bit;
+
+    return multhi;
+#endif
+}
+
+} // namespace
+
 namespace Common {
 
 u64 EstimateRDTSCFrequency() {
@@ -48,54 +103,71 @@ NativeClock::NativeClock(u64 emulated_cpu_frequency_, u64 emulated_clock_frequen
     : WallClock(emulated_cpu_frequency_, emulated_clock_frequency_, true), rtsc_frequency{
                                                                                rtsc_frequency_} {
     _mm_mfence();
-    last_measure = __rdtsc();
-    accumulated_ticks = 0U;
+    time_point.inner.last_measure = __rdtsc();
+    time_point.inner.accumulated_ticks = 0U;
+    ns_rtsc_factor = GetFixedPoint64Factor(1000000000, rtsc_frequency);
+    us_rtsc_factor = GetFixedPoint64Factor(1000000, rtsc_frequency);
+    ms_rtsc_factor = GetFixedPoint64Factor(1000, rtsc_frequency);
+    clock_rtsc_factor = GetFixedPoint64Factor(emulated_clock_frequency, rtsc_frequency);
+    cpu_rtsc_factor = GetFixedPoint64Factor(emulated_cpu_frequency, rtsc_frequency);
 }
 
 u64 NativeClock::GetRTSC() {
-    std::scoped_lock scope{rtsc_serialize};
-    _mm_mfence();
-    const u64 current_measure = __rdtsc();
-    u64 diff = current_measure - last_measure;
-    diff = diff & ~static_cast<u64>(static_cast<s64>(diff) >> 63); // max(diff, 0)
-    if (current_measure > last_measure) {
-        last_measure = current_measure;
-    }
-    accumulated_ticks += diff;
+    TimePoint new_time_point{};
+    TimePoint current_time_point{};
+    do {
+        current_time_point.pack = time_point.pack;
+        _mm_mfence();
+        const u64 current_measure = __rdtsc();
+        u64 diff = current_measure - current_time_point.inner.last_measure;
+        diff = diff & ~static_cast<u64>(static_cast<s64>(diff) >> 63); // max(diff, 0)
+        new_time_point.inner.last_measure = current_measure > current_time_point.inner.last_measure
+                                                ? current_measure
+                                                : current_time_point.inner.last_measure;
+        new_time_point.inner.accumulated_ticks = current_time_point.inner.accumulated_ticks + diff;
+    } while (!Common::AtomicCompareAndSwap(time_point.pack.data(), new_time_point.pack,
+                                           current_time_point.pack));
     /// The clock cannot be more precise than the guest timer, remove the lower bits
-    return accumulated_ticks & inaccuracy_mask;
+    return new_time_point.inner.accumulated_ticks & inaccuracy_mask;
 }
 
 void NativeClock::Pause(bool is_paused) {
     if (!is_paused) {
-        _mm_mfence();
-        last_measure = __rdtsc();
+        TimePoint current_time_point{};
+        TimePoint new_time_point{};
+        do {
+            current_time_point.pack = time_point.pack;
+            new_time_point.pack = current_time_point.pack;
+            _mm_mfence();
+            new_time_point.inner.last_measure = __rdtsc();
+        } while (!Common::AtomicCompareAndSwap(time_point.pack.data(), new_time_point.pack,
+                                               current_time_point.pack));
     }
 }
 
 std::chrono::nanoseconds NativeClock::GetTimeNS() {
     const u64 rtsc_value = GetRTSC();
-    return std::chrono::nanoseconds{MultiplyAndDivide64(rtsc_value, 1000000000, rtsc_frequency)};
+    return std::chrono::nanoseconds{MultiplyHigh(rtsc_value, ns_rtsc_factor)};
 }
 
 std::chrono::microseconds NativeClock::GetTimeUS() {
     const u64 rtsc_value = GetRTSC();
-    return std::chrono::microseconds{MultiplyAndDivide64(rtsc_value, 1000000, rtsc_frequency)};
+    return std::chrono::microseconds{MultiplyHigh(rtsc_value, us_rtsc_factor)};
 }
 
 std::chrono::milliseconds NativeClock::GetTimeMS() {
     const u64 rtsc_value = GetRTSC();
-    return std::chrono::milliseconds{MultiplyAndDivide64(rtsc_value, 1000, rtsc_frequency)};
+    return std::chrono::milliseconds{MultiplyHigh(rtsc_value, ms_rtsc_factor)};
 }
 
 u64 NativeClock::GetClockCycles() {
     const u64 rtsc_value = GetRTSC();
-    return MultiplyAndDivide64(rtsc_value, emulated_clock_frequency, rtsc_frequency);
+    return MultiplyHigh(rtsc_value, clock_rtsc_factor);
 }
 
 u64 NativeClock::GetCPUCycles() {
     const u64 rtsc_value = GetRTSC();
-    return MultiplyAndDivide64(rtsc_value, emulated_cpu_frequency, rtsc_frequency);
+    return MultiplyHigh(rtsc_value, cpu_rtsc_factor);
 }
 
 } // namespace X64
diff --git a/src/common/x64/native_clock.h b/src/common/x64/native_clock.h
index 6d1e32ac8..7cbd400d2 100644
--- a/src/common/x64/native_clock.h
+++ b/src/common/x64/native_clock.h
@@ -6,7 +6,6 @@
 
 #include <optional>
 
-#include "common/spin_lock.h"
 #include "common/wall_clock.h"
 
 namespace Common {
@@ -32,14 +31,28 @@ public:
 private:
     u64 GetRTSC();
 
+    union alignas(16) TimePoint {
+        TimePoint() : pack{} {}
+        u128 pack{};
+        struct Inner {
+            u64 last_measure{};
+            u64 accumulated_ticks{};
+        } inner;
+    };
+
     /// value used to reduce the native clocks accuracy as some apss rely on
     /// undefined behavior where the level of accuracy in the clock shouldn't
     /// be higher.
     static constexpr u64 inaccuracy_mask = ~(UINT64_C(0x400) - 1);
 
-    SpinLock rtsc_serialize{};
-    u64 last_measure{};
-    u64 accumulated_ticks{};
+    TimePoint time_point;
+    // factors
+    u64 clock_rtsc_factor{};
+    u64 cpu_rtsc_factor{};
+    u64 ns_rtsc_factor{};
+    u64 us_rtsc_factor{};
+    u64 ms_rtsc_factor{};
+
     u64 rtsc_frequency;
 };
 } // namespace X64