From 01ba6cf610641f1937092b469843b14ebc2a5962 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Sun, 4 Feb 2024 14:44:17 +0100
Subject: Common: Introduce Range Sets

---
 src/common/range_sets.inc | 279 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 279 insertions(+)
 create mode 100644 src/common/range_sets.inc

(limited to 'src/common/range_sets.inc')

diff --git a/src/common/range_sets.inc b/src/common/range_sets.inc
new file mode 100644
index 000000000..fa55a68fb
--- /dev/null
+++ b/src/common/range_sets.inc
@@ -0,0 +1,279 @@
+// SPDX-FileCopyrightText: 2024 yuzu Emulator Project
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#pragma once
+
+#include <limits>
+#include <utility>
+
+#define BOOST_NO_MT
+#include <boost/pool/detail/mutex.hpp>
+#undef BOOST_NO_MT
+#include <boost/icl/interval.hpp>
+#include <boost/icl/interval_base_set.hpp>
+#include <boost/icl/interval_map.hpp>
+#include <boost/icl/interval_set.hpp>
+#include <boost/icl/split_interval_map.hpp>
+#include <boost/pool/pool.hpp>
+#include <boost/pool/pool_alloc.hpp>
+#include <boost/pool/poolfwd.hpp>
+
+#include "common/range_sets.h"
+
+namespace boost {
+template <typename T>
+class fast_pool_allocator<T, default_user_allocator_new_delete, details::pool::null_mutex, 4096, 0>;
+}
+
+namespace Common {
+
+template <typename AddressType>
+struct RangeSet<AddressType>::RangeSetImpl {
+    using IntervalSet = boost::icl::interval_set<
+        AddressType, std::less, ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, AddressType, std::less),
+        boost::fast_pool_allocator>;
+    using IntervalType = typename IntervalSet::interval_type;
+
+    RangeSetImpl() = default;
+    ~RangeSetImpl() = default;
+
+    void Add(AddressType base_address, size_t size) {
+        AddressType end_address = base_address + static_cast<AddressType>(size);
+        IntervalType interval{base_address, end_address};
+        m_ranges_set.add(interval);
+    }
+
+    void Subtract(AddressType base_address, size_t size) {
+        AddressType end_address = base_address + static_cast<AddressType>(size);
+        IntervalType interval{base_address, end_address};
+        m_ranges_set.subtract(interval);
+    }
+
+    IntervalSet m_ranges_set;
+};
+
+template <typename AddressType>
+struct SplitRangeSet<AddressType>::SplitRangeSetImpl {
+
+    using IntervalSet =
+        boost::icl::split_interval_map<AddressType, s32, boost::icl::partial_enricher, std::less,
+                                       boost::icl::inplace_plus, boost::icl::inter_section,
+                                       ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, AddressType,
+                                                             std::less),
+                                       boost::fast_pool_allocator>;
+    using IntervalType = typename IntervalSet::interval_type;
+
+    SplitRangeSetImpl() = default;
+    ~SplitRangeSetImpl() = default;
+
+    void Add(AddressType base_address, size_t size) {
+        AddressType end_address = base_address + static_cast<AddressType>(size);
+        IntervalType interval{base_address, end_address};
+        m_split_ranges_set += std::make_pair(interval, 1);
+    }
+
+    template <bool has_on_delete, typename Func>
+    void Subtract(AddressType base_address, size_t size, s32 amount,
+                  [[maybe_unused]] Func&& on_delete) {
+        AddressType end_address = base_address + static_cast<AddressType>(size);
+        IntervalType interval{base_address, end_address};
+        bool any_removals = false;
+        m_split_ranges_set += std::make_pair(interval, -amount);
+        do {
+            any_removals = false;
+            auto it = m_split_ranges_set.lower_bound(interval);
+            if (it == m_split_ranges_set.end()) {
+                return;
+            }
+            auto end_it = m_split_ranges_set.upper_bound(interval);
+            for (; it != end_it; it++) {
+                if (it->second <= 0) {
+                    if constexpr (has_on_delete) {
+                        if (it->second == 0) {
+                            on_delete(it->first.lower(), it->first.upper());
+                        }
+                    }
+                    any_removals = true;
+                    m_split_ranges_set.erase(it);
+                    break;
+                }
+            }
+        } while (any_removals);
+    }
+
+    IntervalSet m_split_ranges_set;
+};
+
+template <typename AddressType>
+RangeSet<AddressType>::RangeSet() {
+    m_impl = std::make_unique<RangeSet<AddressType>::RangeSetImpl>();
+}
+
+template <typename AddressType>
+RangeSet<AddressType>::~RangeSet() = default;
+
+template <typename AddressType>
+RangeSet<AddressType>::RangeSet(RangeSet&& other) {
+    m_impl = std::make_unique<RangeSet<AddressType>::RangeSetImpl>();
+    m_impl->m_ranges_set = std::move(other.m_impl->m_ranges_set);
+}
+
+template <typename AddressType>
+RangeSet<AddressType>& RangeSet<AddressType>::operator=(RangeSet&& other) {
+    m_impl->m_ranges_set = std::move(other.m_impl->m_ranges_set);
+}
+
+template <typename AddressType>
+void RangeSet<AddressType>::Add(AddressType base_address, size_t size) {
+    m_impl->Add(base_address, size);
+}
+
+template <typename AddressType>
+void RangeSet<AddressType>::Subtract(AddressType base_address, size_t size) {
+    m_impl->Subtract(base_address, size);
+}
+
+template <typename AddressType>
+void RangeSet<AddressType>::Clear() {
+    m_impl->m_ranges_set.clear();
+}
+
+template <typename AddressType>
+bool RangeSet<AddressType>::Empty() const {
+    return m_impl->m_ranges_set.empty();
+}
+
+template <typename AddressType>
+template <typename Func>
+void RangeSet<AddressType>::ForEach(Func&& func) const {
+    if (m_impl->m_ranges_set.empty()) {
+        return;
+    }
+    auto it = m_impl->m_ranges_set.begin();
+    auto end_it = m_impl->m_ranges_set.end();
+    for (; it != end_it; it++) {
+        const AddressType inter_addr_end = it->upper();
+        const AddressType inter_addr = it->lower();
+        func(inter_addr, inter_addr_end);
+    }
+}
+
+template <typename AddressType>
+template <typename Func>
+void RangeSet<AddressType>::ForEachInRange(AddressType base_addr, size_t size, Func&& func) const {
+    auto& range_set = m_impl->m_ranges_set;
+    const AddressType start_address = base_addr;
+    const AddressType end_address = start_address + size;
+    const RangeSetImpl::IntervalType search_interval{start_address, end_address};
+    auto it = range_set.lower_bound(search_interval);
+    if (it == range_set.end()) {
+        return;
+    }
+    auto end_it = range_set.upper_bound(search_interval);
+    for (; it != end_it; it++) {
+        AddressType inter_addr_end = it->upper();
+        AddressType inter_addr = it->lower();
+        if (inter_addr_end > end_address) {
+            inter_addr_end = end_address;
+        }
+        if (inter_addr < start_address) {
+            inter_addr = start_address;
+        }
+        func(inter_addr, inter_addr_end);
+    }
+}
+
+template <typename AddressType>
+SplitRangeSet<AddressType>::SplitRangeSet() {
+    m_impl = std::make_unique<SplitRangeSet<AddressType>::SplitRangeSetImpl>();
+}
+
+template <typename AddressType>
+SplitRangeSet<AddressType>::~SplitRangeSet() = default;
+
+template <typename AddressType>
+SplitRangeSet<AddressType>::SplitRangeSet(SplitRangeSet&& other) {
+    m_impl = std::make_unique<SplitRangeSet<AddressType>::SplitRangeSetImpl>();
+    m_impl->m_split_ranges_set = std::move(other.m_impl->m_split_ranges_set);
+}
+
+template <typename AddressType>
+SplitRangeSet<AddressType>& SplitRangeSet<AddressType>::operator=(SplitRangeSet&& other) {
+    m_impl->m_split_ranges_set = std::move(other.m_impl->m_split_ranges_set);
+}
+
+template <typename AddressType>
+void SplitRangeSet<AddressType>::Add(AddressType base_address, size_t size) {
+    m_impl->Add(base_address, size);
+}
+
+template <typename AddressType>
+void SplitRangeSet<AddressType>::Subtract(AddressType base_address, size_t size) {
+    m_impl->Subtract<false>(base_address, size, 1, [](AddressType, AddressType) {});
+}
+
+template <typename AddressType>
+template <typename Func>
+void SplitRangeSet<AddressType>::Subtract(AddressType base_address, size_t size, Func&& on_delete) {
+    m_impl->Subtract<true>(base_address, size, 1, on_delete);
+}
+
+template <typename AddressType>
+void SplitRangeSet<AddressType>::DeleteAll(AddressType base_address, size_t size) {
+    m_impl->Subtract<false>(base_address, size, std::numeric_limits<s32>::max(),
+                            [](AddressType, AddressType) {});
+}
+
+template <typename AddressType>
+void SplitRangeSet<AddressType>::Clear() {
+    m_impl->m_split_ranges_set.clear();
+}
+
+template <typename AddressType>
+bool SplitRangeSet<AddressType>::Empty() const {
+    return m_impl->m_split_ranges_set.empty();
+}
+
+template <typename AddressType>
+template <typename Func>
+void SplitRangeSet<AddressType>::ForEach(Func&& func) const {
+    if (m_impl->m_split_ranges_set.empty()) {
+        return;
+    }
+    auto it = m_impl->m_split_ranges_set.begin();
+    auto end_it = m_impl->m_split_ranges_set.end();
+    for (; it != end_it; it++) {
+        const AddressType inter_addr_end = it->first.upper();
+        const AddressType inter_addr = it->first.lower();
+        func(inter_addr, inter_addr_end, it->second);
+    }
+}
+
+template <typename AddressType>
+template <typename Func>
+void SplitRangeSet<AddressType>::ForEachInRange(AddressType base_address, size_t size,
+                                                Func&& func) const {
+    auto& range_set = m_impl->m_split_ranges_set;
+    const AddressType start_address = base_address;
+    const AddressType end_address = start_address + size;
+    const SplitRangeSetImpl::IntervalType search_interval{start_address, end_address};
+    auto it = range_set.lower_bound(search_interval);
+    if (it == range_set.end()) {
+        return;
+    }
+    auto end_it = range_set.upper_bound(search_interval);
+    for (; it != end_it; it++) {
+        auto& inter = it->first;
+        AddressType inter_addr_end = inter.upper();
+        AddressType inter_addr = inter.lower();
+        if (inter_addr_end > end_address) {
+            inter_addr_end = end_address;
+        }
+        if (inter_addr < start_address) {
+            inter_addr = start_address;
+        }
+        func(inter_addr, inter_addr_end, it->second);
+    }
+}
+
+} // namespace Common
\ No newline at end of file
-- 
cgit v1.2.3


From 0d5a3abeaefd3a1682c48a59c5a9170cfb0a39d0 Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Sun, 4 Feb 2024 19:16:07 +0100
Subject: Buffer Cache: Refactor to use Range sets instead

---
 src/common/range_sets.inc | 184 ++++++++++++++++++++++++++--------------------
 1 file changed, 103 insertions(+), 81 deletions(-)

(limited to 'src/common/range_sets.inc')

diff --git a/src/common/range_sets.inc b/src/common/range_sets.inc
index fa55a68fb..705ebd4a1 100644
--- a/src/common/range_sets.inc
+++ b/src/common/range_sets.inc
@@ -6,9 +6,6 @@
 #include <limits>
 #include <utility>
 
-#define BOOST_NO_MT
-#include <boost/pool/detail/mutex.hpp>
-#undef BOOST_NO_MT
 #include <boost/icl/interval.hpp>
 #include <boost/icl/interval_base_set.hpp>
 #include <boost/icl/interval_map.hpp>
@@ -20,18 +17,16 @@
 
 #include "common/range_sets.h"
 
-namespace boost {
-template <typename T>
-class fast_pool_allocator<T, default_user_allocator_new_delete, details::pool::null_mutex, 4096, 0>;
-}
-
 namespace Common {
 
 template <typename AddressType>
 struct RangeSet<AddressType>::RangeSetImpl {
+    template <class T>
+    using MyAllocator = boost::fast_pool_allocator<T, boost::default_user_allocator_new_delete,
+                                                   boost::details::pool::default_mutex, 1024, 2048>;
     using IntervalSet = boost::icl::interval_set<
         AddressType, std::less, ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, AddressType, std::less),
-        boost::fast_pool_allocator>;
+        MyAllocator>;
     using IntervalType = typename IntervalSet::interval_type;
 
     RangeSetImpl() = default;
@@ -49,18 +44,58 @@ struct RangeSet<AddressType>::RangeSetImpl {
         m_ranges_set.subtract(interval);
     }
 
+    template <typename Func>
+    void ForEach(Func&& func) const {
+        if (m_ranges_set.empty()) {
+            return;
+        }
+        auto it = m_ranges_set.begin();
+        auto end_it = m_ranges_set.end();
+        for (; it != end_it; it++) {
+            const AddressType inter_addr_end = it->upper();
+            const AddressType inter_addr = it->lower();
+            func(inter_addr, inter_addr_end);
+        }
+    }
+
+    template <typename Func>
+    void ForEachInRange(AddressType base_addr, size_t size, Func&& func) const {
+        if (m_ranges_set.empty()) {
+            return;
+        }
+        const AddressType start_address = base_addr;
+        const AddressType end_address = start_address + size;
+        const RangeSetImpl::IntervalType search_interval{start_address, end_address};
+        auto it = m_ranges_set.lower_bound(search_interval);
+        if (it == m_ranges_set.end()) {
+            return;
+        }
+        auto end_it = m_ranges_set.upper_bound(search_interval);
+        for (; it != end_it; it++) {
+            AddressType inter_addr_end = it->upper();
+            AddressType inter_addr = it->lower();
+            if (inter_addr_end > end_address) {
+                inter_addr_end = end_address;
+            }
+            if (inter_addr < start_address) {
+                inter_addr = start_address;
+            }
+            func(inter_addr, inter_addr_end);
+        }
+    }
+
     IntervalSet m_ranges_set;
 };
 
 template <typename AddressType>
 struct SplitRangeSet<AddressType>::SplitRangeSetImpl {
-
-    using IntervalSet =
-        boost::icl::split_interval_map<AddressType, s32, boost::icl::partial_enricher, std::less,
-                                       boost::icl::inplace_plus, boost::icl::inter_section,
-                                       ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, AddressType,
-                                                             std::less),
-                                       boost::fast_pool_allocator>;
+    template <class T>
+    using MyAllocator = boost::fast_pool_allocator<T, boost::default_user_allocator_new_delete,
+                                                   boost::details::pool::default_mutex, 1024, 2048>;
+    using IntervalSet = boost::icl::split_interval_map<
+        AddressType, s32, boost::icl::partial_enricher, std::less, boost::icl::inplace_plus,
+        boost::icl::inter_section,
+        ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, AddressType, std::less), MyAllocator>;
     using IntervalType = typename IntervalSet::interval_type;
 
     SplitRangeSetImpl() = default;
@@ -75,6 +110,9 @@ struct SplitRangeSet<AddressType>::SplitRangeSetImpl {
     template <bool has_on_delete, typename Func>
     void Subtract(AddressType base_address, size_t size, s32 amount,
                   [[maybe_unused]] Func&& on_delete) {
+        if (m_split_ranges_set.empty()) {
+            return;
+        }
         AddressType end_address = base_address + static_cast<AddressType>(size);
         IntervalType interval{base_address, end_address};
         bool any_removals = false;
@@ -101,6 +139,47 @@ struct SplitRangeSet<AddressType>::SplitRangeSetImpl {
         } while (any_removals);
     }
 
+    template <typename Func>
+    void ForEach(Func&& func) const {
+        if (m_split_ranges_set.empty()) {
+            return;
+        }
+        auto it = m_split_ranges_set.begin();
+        auto end_it = m_split_ranges_set.end();
+        for (; it != end_it; it++) {
+            const AddressType inter_addr_end = it->first.upper();
+            const AddressType inter_addr = it->first.lower();
+            func(inter_addr, inter_addr_end, it->second);
+        }
+    }
+
+    template <typename Func>
+    void ForEachInRange(AddressType base_address, size_t size, Func&& func) const {
+        if (m_split_ranges_set.empty()) {
+            return;
+        }
+        const AddressType start_address = base_address;
+        const AddressType end_address = start_address + size;
+        const SplitRangeSetImpl::IntervalType search_interval{start_address, end_address};
+        auto it = m_split_ranges_set.lower_bound(search_interval);
+        if (it == m_split_ranges_set.end()) {
+            return;
+        }
+        auto end_it = m_split_ranges_set.upper_bound(search_interval);
+        for (; it != end_it; it++) {
+            auto& inter = it->first;
+            AddressType inter_addr_end = inter.upper();
+            AddressType inter_addr = inter.lower();
+            if (inter_addr_end > end_address) {
+                inter_addr_end = end_address;
+            }
+            if (inter_addr < start_address) {
+                inter_addr = start_address;
+            }
+            func(inter_addr, inter_addr_end, it->second);
+        }
+    }
+
     IntervalSet m_split_ranges_set;
 };
 
@@ -146,41 +225,13 @@ bool RangeSet<AddressType>::Empty() const {
 template <typename AddressType>
 template <typename Func>
 void RangeSet<AddressType>::ForEach(Func&& func) const {
-    if (m_impl->m_ranges_set.empty()) {
-        return;
-    }
-    auto it = m_impl->m_ranges_set.begin();
-    auto end_it = m_impl->m_ranges_set.end();
-    for (; it != end_it; it++) {
-        const AddressType inter_addr_end = it->upper();
-        const AddressType inter_addr = it->lower();
-        func(inter_addr, inter_addr_end);
-    }
+    m_impl->ForEach(std::move(func));
 }
 
 template <typename AddressType>
 template <typename Func>
-void RangeSet<AddressType>::ForEachInRange(AddressType base_addr, size_t size, Func&& func) const {
-    auto& range_set = m_impl->m_ranges_set;
-    const AddressType start_address = base_addr;
-    const AddressType end_address = start_address + size;
-    const RangeSetImpl::IntervalType search_interval{start_address, end_address};
-    auto it = range_set.lower_bound(search_interval);
-    if (it == range_set.end()) {
-        return;
-    }
-    auto end_it = range_set.upper_bound(search_interval);
-    for (; it != end_it; it++) {
-        AddressType inter_addr_end = it->upper();
-        AddressType inter_addr = it->lower();
-        if (inter_addr_end > end_address) {
-            inter_addr_end = end_address;
-        }
-        if (inter_addr < start_address) {
-            inter_addr = start_address;
-        }
-        func(inter_addr, inter_addr_end);
-    }
+void RangeSet<AddressType>::ForEachInRange(AddressType base_address, size_t size, Func&& func) const {
+    m_impl->ForEachInRange(base_address, size, std::move(func));
 }
 
 template <typename AddressType>
@@ -209,18 +260,18 @@ void SplitRangeSet<AddressType>::Add(AddressType base_address, size_t size) {
 
 template <typename AddressType>
 void SplitRangeSet<AddressType>::Subtract(AddressType base_address, size_t size) {
-    m_impl->Subtract<false>(base_address, size, 1, [](AddressType, AddressType) {});
+    m_impl->template Subtract<false>(base_address, size, 1, [](AddressType, AddressType) {});
 }
 
 template <typename AddressType>
 template <typename Func>
 void SplitRangeSet<AddressType>::Subtract(AddressType base_address, size_t size, Func&& on_delete) {
-    m_impl->Subtract<true>(base_address, size, 1, on_delete);
+    m_impl->template Subtract<true, Func>(base_address, size, 1, std::move(on_delete));
 }
 
 template <typename AddressType>
 void SplitRangeSet<AddressType>::DeleteAll(AddressType base_address, size_t size) {
-    m_impl->Subtract<false>(base_address, size, std::numeric_limits<s32>::max(),
+    m_impl->template Subtract<false>(base_address, size, std::numeric_limits<s32>::max(),
                             [](AddressType, AddressType) {});
 }
 
@@ -237,43 +288,14 @@ bool SplitRangeSet<AddressType>::Empty() const {
 template <typename AddressType>
 template <typename Func>
 void SplitRangeSet<AddressType>::ForEach(Func&& func) const {
-    if (m_impl->m_split_ranges_set.empty()) {
-        return;
-    }
-    auto it = m_impl->m_split_ranges_set.begin();
-    auto end_it = m_impl->m_split_ranges_set.end();
-    for (; it != end_it; it++) {
-        const AddressType inter_addr_end = it->first.upper();
-        const AddressType inter_addr = it->first.lower();
-        func(inter_addr, inter_addr_end, it->second);
-    }
+    m_impl->ForEach(func);
 }
 
 template <typename AddressType>
 template <typename Func>
 void SplitRangeSet<AddressType>::ForEachInRange(AddressType base_address, size_t size,
                                                 Func&& func) const {
-    auto& range_set = m_impl->m_split_ranges_set;
-    const AddressType start_address = base_address;
-    const AddressType end_address = start_address + size;
-    const SplitRangeSetImpl::IntervalType search_interval{start_address, end_address};
-    auto it = range_set.lower_bound(search_interval);
-    if (it == range_set.end()) {
-        return;
-    }
-    auto end_it = range_set.upper_bound(search_interval);
-    for (; it != end_it; it++) {
-        auto& inter = it->first;
-        AddressType inter_addr_end = inter.upper();
-        AddressType inter_addr = inter.lower();
-        if (inter_addr_end > end_address) {
-            inter_addr_end = end_address;
-        }
-        if (inter_addr < start_address) {
-            inter_addr = start_address;
-        }
-        func(inter_addr, inter_addr_end, it->second);
-    }
+    m_impl->ForEachInRange(base_address, size, std::move(func));
 }
 
 } // namespace Common
\ No newline at end of file
-- 
cgit v1.2.3


From fa47ac1c9f8b117d556c7c18ac9dcb062af5cefc Mon Sep 17 00:00:00 2001
From: Fernando Sahmkow <fsahmkow27@gmail.com>
Date: Mon, 5 Feb 2024 12:46:49 +0100
Subject: Common: Rename SplitRangeSet to OverlapRangeSet

---
 src/common/range_sets.inc | 63 +++++++++++++++++++++++++----------------------
 1 file changed, 33 insertions(+), 30 deletions(-)

(limited to 'src/common/range_sets.inc')

diff --git a/src/common/range_sets.inc b/src/common/range_sets.inc
index 705ebd4a1..b83eceb7b 100644
--- a/src/common/range_sets.inc
+++ b/src/common/range_sets.inc
@@ -19,14 +19,18 @@
 
 namespace Common {
 
+namespace {
+template <class T>
+using RangeSetsAllocator =
+    boost::fast_pool_allocator<T, boost::default_user_allocator_new_delete,
+                               boost::details::pool::default_mutex, 1024, 2048>;
+}
+
 template <typename AddressType>
 struct RangeSet<AddressType>::RangeSetImpl {
-    template <class T>
-    using MyAllocator = boost::fast_pool_allocator<T, boost::default_user_allocator_new_delete,
-                                                   boost::details::pool::default_mutex, 1024, 2048>;
     using IntervalSet = boost::icl::interval_set<
         AddressType, std::less, ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, AddressType, std::less),
-        MyAllocator>;
+        RangeSetsAllocator>;
     using IntervalType = typename IntervalSet::interval_type;
 
     RangeSetImpl() = default;
@@ -88,18 +92,15 @@ struct RangeSet<AddressType>::RangeSetImpl {
 };
 
 template <typename AddressType>
-struct SplitRangeSet<AddressType>::SplitRangeSetImpl {
-    template <class T>
-    using MyAllocator = boost::fast_pool_allocator<T, boost::default_user_allocator_new_delete,
-                                                   boost::details::pool::default_mutex, 1024, 2048>;
+struct OverlapRangeSet<AddressType>::OverlapRangeSetImpl {
     using IntervalSet = boost::icl::split_interval_map<
         AddressType, s32, boost::icl::partial_enricher, std::less, boost::icl::inplace_plus,
         boost::icl::inter_section,
-        ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, AddressType, std::less), MyAllocator>;
+        ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, AddressType, std::less), RangeSetsAllocator>;
     using IntervalType = typename IntervalSet::interval_type;
 
-    SplitRangeSetImpl() = default;
-    ~SplitRangeSetImpl() = default;
+    OverlapRangeSetImpl() = default;
+    ~OverlapRangeSetImpl() = default;
 
     void Add(AddressType base_address, size_t size) {
         AddressType end_address = base_address + static_cast<AddressType>(size);
@@ -160,7 +161,7 @@ struct SplitRangeSet<AddressType>::SplitRangeSetImpl {
         }
         const AddressType start_address = base_address;
         const AddressType end_address = start_address + size;
-        const SplitRangeSetImpl::IntervalType search_interval{start_address, end_address};
+        const OverlapRangeSetImpl::IntervalType search_interval{start_address, end_address};
         auto it = m_split_ranges_set.lower_bound(search_interval);
         if (it == m_split_ranges_set.end()) {
             return;
@@ -230,72 +231,74 @@ void RangeSet<AddressType>::ForEach(Func&& func) const {
 
 template <typename AddressType>
 template <typename Func>
-void RangeSet<AddressType>::ForEachInRange(AddressType base_address, size_t size, Func&& func) const {
+void RangeSet<AddressType>::ForEachInRange(AddressType base_address, size_t size,
+                                           Func&& func) const {
     m_impl->ForEachInRange(base_address, size, std::move(func));
 }
 
 template <typename AddressType>
-SplitRangeSet<AddressType>::SplitRangeSet() {
-    m_impl = std::make_unique<SplitRangeSet<AddressType>::SplitRangeSetImpl>();
+OverlapRangeSet<AddressType>::OverlapRangeSet() {
+    m_impl = std::make_unique<OverlapRangeSet<AddressType>::OverlapRangeSetImpl>();
 }
 
 template <typename AddressType>
-SplitRangeSet<AddressType>::~SplitRangeSet() = default;
+OverlapRangeSet<AddressType>::~OverlapRangeSet() = default;
 
 template <typename AddressType>
-SplitRangeSet<AddressType>::SplitRangeSet(SplitRangeSet&& other) {
-    m_impl = std::make_unique<SplitRangeSet<AddressType>::SplitRangeSetImpl>();
+OverlapRangeSet<AddressType>::OverlapRangeSet(OverlapRangeSet&& other) {
+    m_impl = std::make_unique<OverlapRangeSet<AddressType>::OverlapRangeSetImpl>();
     m_impl->m_split_ranges_set = std::move(other.m_impl->m_split_ranges_set);
 }
 
 template <typename AddressType>
-SplitRangeSet<AddressType>& SplitRangeSet<AddressType>::operator=(SplitRangeSet&& other) {
+OverlapRangeSet<AddressType>& OverlapRangeSet<AddressType>::operator=(OverlapRangeSet&& other) {
     m_impl->m_split_ranges_set = std::move(other.m_impl->m_split_ranges_set);
 }
 
 template <typename AddressType>
-void SplitRangeSet<AddressType>::Add(AddressType base_address, size_t size) {
+void OverlapRangeSet<AddressType>::Add(AddressType base_address, size_t size) {
     m_impl->Add(base_address, size);
 }
 
 template <typename AddressType>
-void SplitRangeSet<AddressType>::Subtract(AddressType base_address, size_t size) {
+void OverlapRangeSet<AddressType>::Subtract(AddressType base_address, size_t size) {
     m_impl->template Subtract<false>(base_address, size, 1, [](AddressType, AddressType) {});
 }
 
 template <typename AddressType>
 template <typename Func>
-void SplitRangeSet<AddressType>::Subtract(AddressType base_address, size_t size, Func&& on_delete) {
+void OverlapRangeSet<AddressType>::Subtract(AddressType base_address, size_t size,
+                                            Func&& on_delete) {
     m_impl->template Subtract<true, Func>(base_address, size, 1, std::move(on_delete));
 }
 
 template <typename AddressType>
-void SplitRangeSet<AddressType>::DeleteAll(AddressType base_address, size_t size) {
+void OverlapRangeSet<AddressType>::DeleteAll(AddressType base_address, size_t size) {
     m_impl->template Subtract<false>(base_address, size, std::numeric_limits<s32>::max(),
-                            [](AddressType, AddressType) {});
+                                     [](AddressType, AddressType) {});
 }
 
 template <typename AddressType>
-void SplitRangeSet<AddressType>::Clear() {
+void OverlapRangeSet<AddressType>::Clear() {
     m_impl->m_split_ranges_set.clear();
 }
 
 template <typename AddressType>
-bool SplitRangeSet<AddressType>::Empty() const {
+bool OverlapRangeSet<AddressType>::Empty() const {
     return m_impl->m_split_ranges_set.empty();
 }
 
 template <typename AddressType>
 template <typename Func>
-void SplitRangeSet<AddressType>::ForEach(Func&& func) const {
+void OverlapRangeSet<AddressType>::ForEach(Func&& func) const {
     m_impl->ForEach(func);
 }
 
 template <typename AddressType>
 template <typename Func>
-void SplitRangeSet<AddressType>::ForEachInRange(AddressType base_address, size_t size,
-                                                Func&& func) const {
+void OverlapRangeSet<AddressType>::ForEachInRange(AddressType base_address, size_t size,
+                                                  Func&& func) const {
     m_impl->ForEachInRange(base_address, size, std::move(func));
 }
 
-} // namespace Common
\ No newline at end of file
+} // namespace Common
-- 
cgit v1.2.3