summaryrefslogtreecommitdiff
path: root/src/common
diff options
context:
space:
mode:
Diffstat (limited to 'src/common')
-rw-r--r--src/common/CMakeLists.txt6
-rw-r--r--src/common/alignment.h29
-rw-r--r--src/common/bit_util.h76
-rw-r--r--src/common/color.h271
-rw-r--r--src/common/common_funcs.h16
-rw-r--r--src/common/div_ceil.h10
-rw-r--r--src/common/intrusive_red_black_tree.h602
-rw-r--r--src/common/logging/backend.cpp16
-rw-r--r--src/common/page_table.h2
-rw-r--r--src/common/parent_of_member.h191
-rw-r--r--src/common/swap.h4
-rw-r--r--src/common/timer.cpp159
-rw-r--r--src/common/timer.h41
-rw-r--r--src/common/tree.h674
14 files changed, 1514 insertions, 583 deletions
diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt
index abe62543e..f77575a00 100644
--- a/src/common/CMakeLists.txt
+++ b/src/common/CMakeLists.txt
@@ -107,7 +107,6 @@ add_library(common STATIC
107 bit_util.h 107 bit_util.h
108 cityhash.cpp 108 cityhash.cpp
109 cityhash.h 109 cityhash.h
110 color.h
111 common_funcs.h 110 common_funcs.h
112 common_paths.h 111 common_paths.h
113 common_types.h 112 common_types.h
@@ -122,6 +121,7 @@ add_library(common STATIC
122 hash.h 121 hash.h
123 hex_util.cpp 122 hex_util.cpp
124 hex_util.h 123 hex_util.h
124 intrusive_red_black_tree.h
125 logging/backend.cpp 125 logging/backend.cpp
126 logging/backend.h 126 logging/backend.h
127 logging/filter.cpp 127 logging/filter.cpp
@@ -142,6 +142,7 @@ add_library(common STATIC
142 page_table.h 142 page_table.h
143 param_package.cpp 143 param_package.cpp
144 param_package.h 144 param_package.h
145 parent_of_member.h
145 quaternion.h 146 quaternion.h
146 ring_buffer.h 147 ring_buffer.h
147 scm_rev.cpp 148 scm_rev.cpp
@@ -164,8 +165,7 @@ add_library(common STATIC
164 threadsafe_queue.h 165 threadsafe_queue.h
165 time_zone.cpp 166 time_zone.cpp
166 time_zone.h 167 time_zone.h
167 timer.cpp 168 tree.h
168 timer.h
169 uint128.cpp 169 uint128.cpp
170 uint128.h 170 uint128.h
171 uuid.cpp 171 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 @@
9namespace Common { 9namespace Common {
10 10
11template <typename T> 11template <typename T>
12[[nodiscard]] constexpr T AlignUp(T value, std::size_t size) { 12requires std::is_unsigned_v<T>[[nodiscard]] constexpr T AlignUp(T value, size_t size) {
13 static_assert(std::is_unsigned_v<T>, "T must be an unsigned value.");
14 auto mod{static_cast<T>(value % size)}; 13 auto mod{static_cast<T>(value % size)};
15 value -= mod; 14 value -= mod;
16 return static_cast<T>(mod == T{0} ? value : value + size); 15 return static_cast<T>(mod == T{0} ? value : value + size);
17} 16}
18 17
19template <typename T> 18template <typename T>
20[[nodiscard]] constexpr T AlignDown(T value, std::size_t size) { 19requires std::is_unsigned_v<T>[[nodiscard]] constexpr T AlignUpLog2(T value, size_t align_log2) {
21 static_assert(std::is_unsigned_v<T>, "T must be an unsigned value."); 20 return static_cast<T>((value + ((1ULL << align_log2) - 1)) >> align_log2 << align_log2);
22 return static_cast<T>(value - value % size);
23} 21}
24 22
25template <typename T> 23template <typename T>
26[[nodiscard]] constexpr T AlignBits(T value, std::size_t align) { 24requires std::is_unsigned_v<T>[[nodiscard]] constexpr T AlignDown(T value, size_t size) {
27 static_assert(std::is_unsigned_v<T>, "T must be an unsigned value."); 25 return static_cast<T>(value - value % size);
28 return static_cast<T>((value + ((1ULL << align) - 1)) >> align << align);
29} 26}
30 27
31template <typename T> 28template <typename T>
32[[nodiscard]] constexpr bool Is4KBAligned(T value) { 29requires std::is_unsigned_v<T>[[nodiscard]] constexpr bool Is4KBAligned(T value) {
33 static_assert(std::is_unsigned_v<T>, "T must be an unsigned value.");
34 return (value & 0xFFF) == 0; 30 return (value & 0xFFF) == 0;
35} 31}
36 32
37template <typename T> 33template <typename T>
38[[nodiscard]] constexpr bool IsWordAligned(T value) { 34requires std::is_unsigned_v<T>[[nodiscard]] constexpr bool IsWordAligned(T value) {
39 static_assert(std::is_unsigned_v<T>, "T must be an unsigned value.");
40 return (value & 0b11) == 0; 35 return (value & 0b11) == 0;
41} 36}
42 37
43template <typename T> 38template <typename T>
44[[nodiscard]] constexpr bool IsAligned(T value, std::size_t alignment) { 39requires std::is_integral_v<T>[[nodiscard]] constexpr bool IsAligned(T value, size_t alignment) {
45 using U = typename std::make_unsigned<T>::type; 40 using U = typename std::make_unsigned_t<T>;
46 const U mask = static_cast<U>(alignment - 1); 41 const U mask = static_cast<U>(alignment - 1);
47 return (value & mask) == 0; 42 return (value & mask) == 0;
48} 43}
49 44
50template <typename T, std::size_t Align = 16> 45template <typename T, size_t Align = 16>
51class AlignmentAllocator { 46class AlignmentAllocator {
52public: 47public:
53 using value_type = T; 48 using value_type = T;
54 using size_type = std::size_t; 49 using size_type = size_t;
55 using difference_type = std::ptrdiff_t; 50 using difference_type = ptrdiff_t;
56 51
57 using propagate_on_container_copy_assignment = std::true_type; 52 using propagate_on_container_copy_assignment = std::true_type;
58 using propagate_on_container_move_assignment = std::true_type; 53 using propagate_on_container_move_assignment = std::true_type;
diff --git a/src/common/bit_util.h b/src/common/bit_util.h
index 29f59a9a3..685e7fc9b 100644
--- a/src/common/bit_util.h
+++ b/src/common/bit_util.h
@@ -22,82 +22,6 @@ template <typename T>
22} 22}
23 23
24#ifdef _MSC_VER 24#ifdef _MSC_VER
25[[nodiscard]] inline u32 CountLeadingZeroes32(u32 value) {
26 unsigned long leading_zero = 0;
27
28 if (_BitScanReverse(&leading_zero, value) != 0) {
29 return 31 - leading_zero;
30 }
31
32 return 32;
33}
34
35[[nodiscard]] inline u32 CountLeadingZeroes64(u64 value) {
36 unsigned long leading_zero = 0;
37
38 if (_BitScanReverse64(&leading_zero, value) != 0) {
39 return 63 - leading_zero;
40 }
41
42 return 64;
43}
44#else
45[[nodiscard]] inline u32 CountLeadingZeroes32(u32 value) {
46 if (value == 0) {
47 return 32;
48 }
49
50 return static_cast<u32>(__builtin_clz(value));
51}
52
53[[nodiscard]] inline u32 CountLeadingZeroes64(u64 value) {
54 if (value == 0) {
55 return 64;
56 }
57
58 return static_cast<u32>(__builtin_clzll(value));
59}
60#endif
61
62#ifdef _MSC_VER
63[[nodiscard]] inline u32 CountTrailingZeroes32(u32 value) {
64 unsigned long trailing_zero = 0;
65
66 if (_BitScanForward(&trailing_zero, value) != 0) {
67 return trailing_zero;
68 }
69
70 return 32;
71}
72
73[[nodiscard]] inline u32 CountTrailingZeroes64(u64 value) {
74 unsigned long trailing_zero = 0;
75
76 if (_BitScanForward64(&trailing_zero, value) != 0) {
77 return trailing_zero;
78 }
79
80 return 64;
81}
82#else
83[[nodiscard]] inline u32 CountTrailingZeroes32(u32 value) {
84 if (value == 0) {
85 return 32;
86 }
87
88 return static_cast<u32>(__builtin_ctz(value));
89}
90
91[[nodiscard]] inline u32 CountTrailingZeroes64(u64 value) {
92 if (value == 0) {
93 return 64;
94 }
95
96 return static_cast<u32>(__builtin_ctzll(value));
97}
98#endif
99
100#ifdef _MSC_VER
101 25
102[[nodiscard]] inline u32 MostSignificantBit32(const u32 value) { 26[[nodiscard]] inline u32 MostSignificantBit32(const u32 value) {
103 unsigned long result; 27 unsigned long result;
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 @@
1// Copyright 2014 Citra Emulator Project
2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included.
4
5#pragma once
6
7#include <cstring>
8
9#include "common/common_types.h"
10#include "common/swap.h"
11#include "common/vector_math.h"
12
13namespace Common::Color {
14
15/// Convert a 1-bit color component to 8 bit
16[[nodiscard]] constexpr u8 Convert1To8(u8 value) {
17 return value * 255;
18}
19
20/// Convert a 4-bit color component to 8 bit
21[[nodiscard]] constexpr u8 Convert4To8(u8 value) {
22 return (value << 4) | value;
23}
24
25/// Convert a 5-bit color component to 8 bit
26[[nodiscard]] constexpr u8 Convert5To8(u8 value) {
27 return (value << 3) | (value >> 2);
28}
29
30/// Convert a 6-bit color component to 8 bit
31[[nodiscard]] constexpr u8 Convert6To8(u8 value) {
32 return (value << 2) | (value >> 4);
33}
34
35/// Convert a 8-bit color component to 1 bit
36[[nodiscard]] constexpr u8 Convert8To1(u8 value) {
37 return value >> 7;
38}
39
40/// Convert a 8-bit color component to 4 bit
41[[nodiscard]] constexpr u8 Convert8To4(u8 value) {
42 return value >> 4;
43}
44
45/// Convert a 8-bit color component to 5 bit
46[[nodiscard]] constexpr u8 Convert8To5(u8 value) {
47 return value >> 3;
48}
49
50/// Convert a 8-bit color component to 6 bit
51[[nodiscard]] constexpr u8 Convert8To6(u8 value) {
52 return value >> 2;
53}
54
55/**
56 * Decode a color stored in RGBA8 format
57 * @param bytes Pointer to encoded source color
58 * @return Result color decoded as Common::Vec4<u8>
59 */
60[[nodiscard]] inline Common::Vec4<u8> DecodeRGBA8(const u8* bytes) {
61 return {bytes[3], bytes[2], bytes[1], bytes[0]};
62}
63
64/**
65 * Decode a color stored in RGB8 format
66 * @param bytes Pointer to encoded source color
67 * @return Result color decoded as Common::Vec4<u8>
68 */
69[[nodiscard]] inline Common::Vec4<u8> DecodeRGB8(const u8* bytes) {
70 return {bytes[2], bytes[1], bytes[0], 255};
71}
72
73/**
74 * Decode a color stored in RG8 (aka HILO8) format
75 * @param bytes Pointer to encoded source color
76 * @return Result color decoded as Common::Vec4<u8>
77 */
78[[nodiscard]] inline Common::Vec4<u8> DecodeRG8(const u8* bytes) {
79 return {bytes[1], bytes[0], 0, 255};
80}
81
82/**
83 * Decode a color stored in RGB565 format
84 * @param bytes Pointer to encoded source color
85 * @return Result color decoded as Common::Vec4<u8>
86 */
87[[nodiscard]] inline Common::Vec4<u8> DecodeRGB565(const u8* bytes) {
88 u16_le pixel;
89 std::memcpy(&pixel, bytes, sizeof(pixel));
90 return {Convert5To8((pixel >> 11) & 0x1F), Convert6To8((pixel >> 5) & 0x3F),
91 Convert5To8(pixel & 0x1F), 255};
92}
93
94/**
95 * Decode a color stored in RGB5A1 format
96 * @param bytes Pointer to encoded source color
97 * @return Result color decoded as Common::Vec4<u8>
98 */
99[[nodiscard]] inline Common::Vec4<u8> DecodeRGB5A1(const u8* bytes) {
100 u16_le pixel;
101 std::memcpy(&pixel, bytes, sizeof(pixel));
102 return {Convert5To8((pixel >> 11) & 0x1F), Convert5To8((pixel >> 6) & 0x1F),
103 Convert5To8((pixel >> 1) & 0x1F), Convert1To8(pixel & 0x1)};
104}
105
106/**
107 * Decode a color stored in RGBA4 format
108 * @param bytes Pointer to encoded source color
109 * @return Result color decoded as Common::Vec4<u8>
110 */
111[[nodiscard]] inline Common::Vec4<u8> DecodeRGBA4(const u8* bytes) {
112 u16_le pixel;
113 std::memcpy(&pixel, bytes, sizeof(pixel));
114 return {Convert4To8((pixel >> 12) & 0xF), Convert4To8((pixel >> 8) & 0xF),
115 Convert4To8((pixel >> 4) & 0xF), Convert4To8(pixel & 0xF)};
116}
117
118/**
119 * Decode a depth value stored in D16 format
120 * @param bytes Pointer to encoded source value
121 * @return Depth value as an u32
122 */
123[[nodiscard]] inline u32 DecodeD16(const u8* bytes) {
124 u16_le data;
125 std::memcpy(&data, bytes, sizeof(data));
126 return data;
127}
128
129/**
130 * Decode a depth value stored in D24 format
131 * @param bytes Pointer to encoded source value
132 * @return Depth value as an u32
133 */
134[[nodiscard]] inline u32 DecodeD24(const u8* bytes) {
135 return (bytes[2] << 16) | (bytes[1] << 8) | bytes[0];
136}
137
138/**
139 * Decode a depth value and a stencil value stored in D24S8 format
140 * @param bytes Pointer to encoded source values
141 * @return Resulting values stored as a Common::Vec2
142 */
143[[nodiscard]] inline Common::Vec2<u32> DecodeD24S8(const u8* bytes) {
144 return {static_cast<u32>((bytes[2] << 16) | (bytes[1] << 8) | bytes[0]), bytes[3]};
145}
146
147/**
148 * Encode a color as RGBA8 format
149 * @param color Source color to encode
150 * @param bytes Destination pointer to store encoded color
151 */
152inline void EncodeRGBA8(const Common::Vec4<u8>& color, u8* bytes) {
153 bytes[3] = color.r();
154 bytes[2] = color.g();
155 bytes[1] = color.b();
156 bytes[0] = color.a();
157}
158
159/**
160 * Encode a color as RGB8 format
161 * @param color Source color to encode
162 * @param bytes Destination pointer to store encoded color
163 */
164inline void EncodeRGB8(const Common::Vec4<u8>& color, u8* bytes) {
165 bytes[2] = color.r();
166 bytes[1] = color.g();
167 bytes[0] = color.b();
168}
169
170/**
171 * Encode a color as RG8 (aka HILO8) format
172 * @param color Source color to encode
173 * @param bytes Destination pointer to store encoded color
174 */
175inline void EncodeRG8(const Common::Vec4<u8>& color, u8* bytes) {
176 bytes[1] = color.r();
177 bytes[0] = color.g();
178}
179/**
180 * Encode a color as RGB565 format
181 * @param color Source color to encode
182 * @param bytes Destination pointer to store encoded color
183 */
184inline void EncodeRGB565(const Common::Vec4<u8>& color, u8* bytes) {
185 const u16_le data =
186 (Convert8To5(color.r()) << 11) | (Convert8To6(color.g()) << 5) | Convert8To5(color.b());
187
188 std::memcpy(bytes, &data, sizeof(data));
189}
190
191/**
192 * Encode a color as RGB5A1 format
193 * @param color Source color to encode
194 * @param bytes Destination pointer to store encoded color
195 */
196inline void EncodeRGB5A1(const Common::Vec4<u8>& color, u8* bytes) {
197 const u16_le data = (Convert8To5(color.r()) << 11) | (Convert8To5(color.g()) << 6) |
198 (Convert8To5(color.b()) << 1) | Convert8To1(color.a());
199
200 std::memcpy(bytes, &data, sizeof(data));
201}
202
203/**
204 * Encode a color as RGBA4 format
205 * @param color Source color to encode
206 * @param bytes Destination pointer to store encoded color
207 */
208inline void EncodeRGBA4(const Common::Vec4<u8>& color, u8* bytes) {
209 const u16 data = (Convert8To4(color.r()) << 12) | (Convert8To4(color.g()) << 8) |
210 (Convert8To4(color.b()) << 4) | Convert8To4(color.a());
211
212 std::memcpy(bytes, &data, sizeof(data));
213}
214
215/**
216 * Encode a 16 bit depth value as D16 format
217 * @param value 16 bit source depth value to encode
218 * @param bytes Pointer where to store the encoded value
219 */
220inline void EncodeD16(u32 value, u8* bytes) {
221 const u16_le data = static_cast<u16>(value);
222 std::memcpy(bytes, &data, sizeof(data));
223}
224
225/**
226 * Encode a 24 bit depth value as D24 format
227 * @param value 24 bit source depth value to encode
228 * @param bytes Pointer where to store the encoded value
229 */
230inline void EncodeD24(u32 value, u8* bytes) {
231 bytes[0] = value & 0xFF;
232 bytes[1] = (value >> 8) & 0xFF;
233 bytes[2] = (value >> 16) & 0xFF;
234}
235
236/**
237 * Encode a 24 bit depth and 8 bit stencil values as D24S8 format
238 * @param depth 24 bit source depth value to encode
239 * @param stencil 8 bit source stencil value to encode
240 * @param bytes Pointer where to store the encoded value
241 */
242inline void EncodeD24S8(u32 depth, u8 stencil, u8* bytes) {
243 bytes[0] = depth & 0xFF;
244 bytes[1] = (depth >> 8) & 0xFF;
245 bytes[2] = (depth >> 16) & 0xFF;
246 bytes[3] = stencil;
247}
248
249/**
250 * Encode a 24 bit depth value as D24X8 format (32 bits per pixel with 8 bits unused)
251 * @param depth 24 bit source depth value to encode
252 * @param bytes Pointer where to store the encoded value
253 * @note unused bits will not be modified
254 */
255inline void EncodeD24X8(u32 depth, u8* bytes) {
256 bytes[0] = depth & 0xFF;
257 bytes[1] = (depth >> 8) & 0xFF;
258 bytes[2] = (depth >> 16) & 0xFF;
259}
260
261/**
262 * Encode an 8 bit stencil value as X24S8 format (32 bits per pixel with 24 bits unused)
263 * @param stencil 8 bit source stencil value to encode
264 * @param bytes Pointer where to store the encoded value
265 * @note unused bits will not be modified
266 */
267inline void EncodeX24S8(u8 stencil, u8* bytes) {
268 bytes[3] = stencil;
269}
270
271} // 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 @@
24#define INSERT_PADDING_WORDS(num_words) \ 24#define INSERT_PADDING_WORDS(num_words) \
25 std::array<u32, num_words> CONCAT2(pad, __LINE__) {} 25 std::array<u32, num_words> CONCAT2(pad, __LINE__) {}
26 26
27/// These are similar to the INSERT_PADDING_* macros, but are needed for padding unions. This is 27/// These are similar to the INSERT_PADDING_* macros but do not zero-initialize the contents.
28/// because unions can only be initialized by one member. 28/// This keeps the structure trivial to construct.
29#define INSERT_UNION_PADDING_BYTES(num_bytes) std::array<u8, num_bytes> CONCAT2(pad, __LINE__) 29#define INSERT_PADDING_BYTES_NOINIT(num_bytes) std::array<u8, num_bytes> CONCAT2(pad, __LINE__)
30#define INSERT_UNION_PADDING_WORDS(num_words) std::array<u32, num_words> CONCAT2(pad, __LINE__) 30#define INSERT_PADDING_WORDS_NOINIT(num_words) std::array<u32, num_words> CONCAT2(pad, __LINE__)
31 31
32#ifndef _MSC_VER 32#ifndef _MSC_VER
33 33
@@ -93,6 +93,14 @@ __declspec(dllimport) void __stdcall DebugBreak(void);
93 return static_cast<T>(key) == 0; \ 93 return static_cast<T>(key) == 0; \
94 } 94 }
95 95
96/// Evaluates a boolean expression, and returns a result unless that expression is true.
97#define R_UNLESS(expr, res) \
98 { \
99 if (!(expr)) { \
100 return res; \
101 } \
102 }
103
96namespace Common { 104namespace Common {
97 105
98[[nodiscard]] constexpr u32 MakeMagic(char a, char b, char c, char d) { 106[[nodiscard]] constexpr u32 MakeMagic(char a, char b, char c, char d) {
diff --git a/src/common/div_ceil.h b/src/common/div_ceil.h
index 6b2c48f91..95e1489a9 100644
--- a/src/common/div_ceil.h
+++ b/src/common/div_ceil.h
@@ -11,16 +11,16 @@ namespace Common {
11 11
12/// Ceiled integer division. 12/// Ceiled integer division.
13template <typename N, typename D> 13template <typename N, typename D>
14requires std::is_integral_v<N>&& std::is_unsigned_v<D>[[nodiscard]] constexpr auto DivCeil( 14requires std::is_integral_v<N>&& std::is_unsigned_v<D>[[nodiscard]] constexpr N DivCeil(N number,
15 N number, D divisor) { 15 D divisor) {
16 return (static_cast<D>(number) + divisor - 1) / divisor; 16 return static_cast<N>((static_cast<D>(number) + divisor - 1) / divisor);
17} 17}
18 18
19/// Ceiled integer division with logarithmic divisor in base 2 19/// Ceiled integer division with logarithmic divisor in base 2
20template <typename N, typename D> 20template <typename N, typename D>
21requires std::is_integral_v<N>&& std::is_unsigned_v<D>[[nodiscard]] constexpr auto DivCeilLog2( 21requires std::is_integral_v<N>&& std::is_unsigned_v<D>[[nodiscard]] constexpr N DivCeilLog2(
22 N value, D alignment_log2) { 22 N value, D alignment_log2) {
23 return (static_cast<D>(value) + (D(1) << alignment_log2) - 1) >> alignment_log2; 23 return static_cast<N>((static_cast<D>(value) + (D(1) << alignment_log2) - 1) >> alignment_log2);
24} 24}
25 25
26} // namespace Common 26} // namespace Common
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 @@
1// Copyright 2021 yuzu Emulator Project
2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included.
4
5#pragma once
6
7#include "common/parent_of_member.h"
8#include "common/tree.h"
9
10namespace Common {
11
12namespace impl {
13
14class IntrusiveRedBlackTreeImpl;
15
16}
17
18struct IntrusiveRedBlackTreeNode {
19public:
20 using EntryType = RBEntry<IntrusiveRedBlackTreeNode>;
21
22 constexpr IntrusiveRedBlackTreeNode() = default;
23
24 void SetEntry(const EntryType& new_entry) {
25 entry = new_entry;
26 }
27
28 [[nodiscard]] EntryType& GetEntry() {
29 return entry;
30 }
31
32 [[nodiscard]] const EntryType& GetEntry() const {
33 return entry;
34 }
35
36private:
37 EntryType entry{};
38
39 friend class impl::IntrusiveRedBlackTreeImpl;
40
41 template <class, class, class>
42 friend class IntrusiveRedBlackTree;
43};
44
45template <class T, class Traits, class Comparator>
46class IntrusiveRedBlackTree;
47
48namespace impl {
49
50class IntrusiveRedBlackTreeImpl {
51private:
52 template <class, class, class>
53 friend class ::Common::IntrusiveRedBlackTree;
54
55 using RootType = RBHead<IntrusiveRedBlackTreeNode>;
56 RootType root;
57
58public:
59 template <bool Const>
60 class Iterator;
61
62 using value_type = IntrusiveRedBlackTreeNode;
63 using size_type = size_t;
64 using difference_type = ptrdiff_t;
65 using pointer = value_type*;
66 using const_pointer = const value_type*;
67 using reference = value_type&;
68 using const_reference = const value_type&;
69 using iterator = Iterator<false>;
70 using const_iterator = Iterator<true>;
71
72 template <bool Const>
73 class Iterator {
74 public:
75 using iterator_category = std::bidirectional_iterator_tag;
76 using value_type = typename IntrusiveRedBlackTreeImpl::value_type;
77 using difference_type = typename IntrusiveRedBlackTreeImpl::difference_type;
78 using pointer = std::conditional_t<Const, IntrusiveRedBlackTreeImpl::const_pointer,
79 IntrusiveRedBlackTreeImpl::pointer>;
80 using reference = std::conditional_t<Const, IntrusiveRedBlackTreeImpl::const_reference,
81 IntrusiveRedBlackTreeImpl::reference>;
82
83 private:
84 pointer node;
85
86 public:
87 explicit Iterator(pointer n) : node(n) {}
88
89 bool operator==(const Iterator& rhs) const {
90 return this->node == rhs.node;
91 }
92
93 bool operator!=(const Iterator& rhs) const {
94 return !(*this == rhs);
95 }
96
97 pointer operator->() const {
98 return this->node;
99 }
100
101 reference operator*() const {
102 return *this->node;
103 }
104
105 Iterator& operator++() {
106 this->node = GetNext(this->node);
107 return *this;
108 }
109
110 Iterator& operator--() {
111 this->node = GetPrev(this->node);
112 return *this;
113 }
114
115 Iterator operator++(int) {
116 const Iterator it{*this};
117 ++(*this);
118 return it;
119 }
120
121 Iterator operator--(int) {
122 const Iterator it{*this};
123 --(*this);
124 return it;
125 }
126
127 operator Iterator<true>() const {
128 return Iterator<true>(this->node);
129 }
130 };
131
132private:
133 // Define accessors using RB_* functions.
134 bool EmptyImpl() const {
135 return root.IsEmpty();
136 }
137
138 IntrusiveRedBlackTreeNode* GetMinImpl() const {
139 return RB_MIN(const_cast<RootType*>(&root));
140 }
141
142 IntrusiveRedBlackTreeNode* GetMaxImpl() const {
143 return RB_MAX(const_cast<RootType*>(&root));
144 }
145
146 IntrusiveRedBlackTreeNode* RemoveImpl(IntrusiveRedBlackTreeNode* node) {
147 return RB_REMOVE(&root, node);
148 }
149
150public:
151 static IntrusiveRedBlackTreeNode* GetNext(IntrusiveRedBlackTreeNode* node) {
152 return RB_NEXT(node);
153 }
154
155 static IntrusiveRedBlackTreeNode* GetPrev(IntrusiveRedBlackTreeNode* node) {
156 return RB_PREV(node);
157 }
158
159 static const IntrusiveRedBlackTreeNode* GetNext(const IntrusiveRedBlackTreeNode* node) {
160 return static_cast<const IntrusiveRedBlackTreeNode*>(
161 GetNext(const_cast<IntrusiveRedBlackTreeNode*>(node)));
162 }
163
164 static const IntrusiveRedBlackTreeNode* GetPrev(const IntrusiveRedBlackTreeNode* node) {
165 return static_cast<const IntrusiveRedBlackTreeNode*>(
166 GetPrev(const_cast<IntrusiveRedBlackTreeNode*>(node)));
167 }
168
169public:
170 constexpr IntrusiveRedBlackTreeImpl() {}
171
172 // Iterator accessors.
173 iterator begin() {
174 return iterator(this->GetMinImpl());
175 }
176
177 const_iterator begin() const {
178 return const_iterator(this->GetMinImpl());
179 }
180
181 iterator end() {
182 return iterator(static_cast<IntrusiveRedBlackTreeNode*>(nullptr));
183 }
184
185 const_iterator end() const {
186 return const_iterator(static_cast<const IntrusiveRedBlackTreeNode*>(nullptr));
187 }
188
189 const_iterator cbegin() const {
190 return this->begin();
191 }
192
193 const_iterator cend() const {
194 return this->end();
195 }
196
197 iterator iterator_to(reference ref) {
198 return iterator(&ref);
199 }
200
201 const_iterator iterator_to(const_reference ref) const {
202 return const_iterator(&ref);
203 }
204
205 // Content management.
206 bool empty() const {
207 return this->EmptyImpl();
208 }
209
210 reference back() {
211 return *this->GetMaxImpl();
212 }
213
214 const_reference back() const {
215 return *this->GetMaxImpl();
216 }
217
218 reference front() {
219 return *this->GetMinImpl();
220 }
221
222 const_reference front() const {
223 return *this->GetMinImpl();
224 }
225
226 iterator erase(iterator it) {
227 auto cur = std::addressof(*it);
228 auto next = GetNext(cur);
229 this->RemoveImpl(cur);
230 return iterator(next);
231 }
232};
233
234} // namespace impl
235
236template <typename T>
237concept HasLightCompareType = requires {
238 { std::is_same<typename T::LightCompareType, void>::value }
239 ->std::convertible_to<bool>;
240};
241
242namespace impl {
243
244template <typename T, typename Default>
245consteval auto* GetLightCompareType() {
246 if constexpr (HasLightCompareType<T>) {
247 return static_cast<typename T::LightCompareType*>(nullptr);
248 } else {
249 return static_cast<Default*>(nullptr);
250 }
251}
252
253} // namespace impl
254
255template <typename T, typename Default>
256using LightCompareType = std::remove_pointer_t<decltype(impl::GetLightCompareType<T, Default>())>;
257
258template <class T, class Traits, class Comparator>
259class IntrusiveRedBlackTree {
260
261public:
262 using ImplType = impl::IntrusiveRedBlackTreeImpl;
263
264private:
265 ImplType impl{};
266
267public:
268 template <bool Const>
269 class Iterator;
270
271 using value_type = T;
272 using size_type = size_t;
273 using difference_type = ptrdiff_t;
274 using pointer = T*;
275 using const_pointer = const T*;
276 using reference = T&;
277 using const_reference = const T&;
278 using iterator = Iterator<false>;
279 using const_iterator = Iterator<true>;
280
281 using light_value_type = LightCompareType<Comparator, value_type>;
282 using const_light_pointer = const light_value_type*;
283 using const_light_reference = const light_value_type&;
284
285 template <bool Const>
286 class Iterator {
287 public:
288 friend class IntrusiveRedBlackTree<T, Traits, Comparator>;
289
290 using ImplIterator =
291 std::conditional_t<Const, ImplType::const_iterator, ImplType::iterator>;
292
293 using iterator_category = std::bidirectional_iterator_tag;
294 using value_type = typename IntrusiveRedBlackTree::value_type;
295 using difference_type = typename IntrusiveRedBlackTree::difference_type;
296 using pointer = std::conditional_t<Const, IntrusiveRedBlackTree::const_pointer,
297 IntrusiveRedBlackTree::pointer>;
298 using reference = std::conditional_t<Const, IntrusiveRedBlackTree::const_reference,
299 IntrusiveRedBlackTree::reference>;
300
301 private:
302 ImplIterator iterator;
303
304 private:
305 explicit Iterator(ImplIterator it) : iterator(it) {}
306
307 explicit Iterator(typename std::conditional<Const, ImplType::const_iterator,
308 ImplType::iterator>::type::pointer ptr)
309 : iterator(ptr) {}
310
311 ImplIterator GetImplIterator() const {
312 return this->iterator;
313 }
314
315 public:
316 bool operator==(const Iterator& rhs) const {
317 return this->iterator == rhs.iterator;
318 }
319
320 bool operator!=(const Iterator& rhs) const {
321 return !(*this == rhs);
322 }
323
324 pointer operator->() const {
325 return Traits::GetParent(std::addressof(*this->iterator));
326 }
327
328 reference operator*() const {
329 return *Traits::GetParent(std::addressof(*this->iterator));
330 }
331
332 Iterator& operator++() {
333 ++this->iterator;
334 return *this;
335 }
336
337 Iterator& operator--() {
338 --this->iterator;
339 return *this;
340 }
341
342 Iterator operator++(int) {
343 const Iterator it{*this};
344 ++this->iterator;
345 return it;
346 }
347
348 Iterator operator--(int) {
349 const Iterator it{*this};
350 --this->iterator;
351 return it;
352 }
353
354 operator Iterator<true>() const {
355 return Iterator<true>(this->iterator);
356 }
357 };
358
359private:
360 static int CompareImpl(const IntrusiveRedBlackTreeNode* lhs,
361 const IntrusiveRedBlackTreeNode* rhs) {
362 return Comparator::Compare(*Traits::GetParent(lhs), *Traits::GetParent(rhs));
363 }
364
365 static int LightCompareImpl(const void* elm, const IntrusiveRedBlackTreeNode* rhs) {
366 return Comparator::Compare(*static_cast<const_light_pointer>(elm), *Traits::GetParent(rhs));
367 }
368
369 // Define accessors using RB_* functions.
370 IntrusiveRedBlackTreeNode* InsertImpl(IntrusiveRedBlackTreeNode* node) {
371 return RB_INSERT(&impl.root, node, CompareImpl);
372 }
373
374 IntrusiveRedBlackTreeNode* FindImpl(const IntrusiveRedBlackTreeNode* node) const {
375 return RB_FIND(const_cast<ImplType::RootType*>(&impl.root),
376 const_cast<IntrusiveRedBlackTreeNode*>(node), CompareImpl);
377 }
378
379 IntrusiveRedBlackTreeNode* NFindImpl(const IntrusiveRedBlackTreeNode* node) const {
380 return RB_NFIND(const_cast<ImplType::RootType*>(&impl.root),
381 const_cast<IntrusiveRedBlackTreeNode*>(node), CompareImpl);
382 }
383
384 IntrusiveRedBlackTreeNode* FindLightImpl(const_light_pointer lelm) const {
385 return RB_FIND_LIGHT(const_cast<ImplType::RootType*>(&impl.root),
386 static_cast<const void*>(lelm), LightCompareImpl);
387 }
388
389 IntrusiveRedBlackTreeNode* NFindLightImpl(const_light_pointer lelm) const {
390 return RB_NFIND_LIGHT(const_cast<ImplType::RootType*>(&impl.root),
391 static_cast<const void*>(lelm), LightCompareImpl);
392 }
393
394public:
395 constexpr IntrusiveRedBlackTree() = default;
396
397 // Iterator accessors.
398 iterator begin() {
399 return iterator(this->impl.begin());
400 }
401
402 const_iterator begin() const {
403 return const_iterator(this->impl.begin());
404 }
405
406 iterator end() {
407 return iterator(this->impl.end());
408 }
409
410 const_iterator end() const {
411 return const_iterator(this->impl.end());
412 }
413
414 const_iterator cbegin() const {
415 return this->begin();
416 }
417
418 const_iterator cend() const {
419 return this->end();
420 }
421
422 iterator iterator_to(reference ref) {
423 return iterator(this->impl.iterator_to(*Traits::GetNode(std::addressof(ref))));
424 }
425
426 const_iterator iterator_to(const_reference ref) const {
427 return const_iterator(this->impl.iterator_to(*Traits::GetNode(std::addressof(ref))));
428 }
429
430 // Content management.
431 bool empty() const {
432 return this->impl.empty();
433 }
434
435 reference back() {
436 return *Traits::GetParent(std::addressof(this->impl.back()));
437 }
438
439 const_reference back() const {
440 return *Traits::GetParent(std::addressof(this->impl.back()));
441 }
442
443 reference front() {
444 return *Traits::GetParent(std::addressof(this->impl.front()));
445 }
446
447 const_reference front() const {
448 return *Traits::GetParent(std::addressof(this->impl.front()));
449 }
450
451 iterator erase(iterator it) {
452 return iterator(this->impl.erase(it.GetImplIterator()));
453 }
454
455 iterator insert(reference ref) {
456 ImplType::pointer node = Traits::GetNode(std::addressof(ref));
457 this->InsertImpl(node);
458 return iterator(node);
459 }
460
461 iterator find(const_reference ref) const {
462 return iterator(this->FindImpl(Traits::GetNode(std::addressof(ref))));
463 }
464
465 iterator nfind(const_reference ref) const {
466 return iterator(this->NFindImpl(Traits::GetNode(std::addressof(ref))));
467 }
468
469 iterator find_light(const_light_reference ref) const {
470 return iterator(this->FindLightImpl(std::addressof(ref)));
471 }
472
473 iterator nfind_light(const_light_reference ref) const {
474 return iterator(this->NFindLightImpl(std::addressof(ref)));
475 }
476};
477
478template <auto T, class Derived = impl::GetParentType<T>>
479class IntrusiveRedBlackTreeMemberTraits;
480
481template <class Parent, IntrusiveRedBlackTreeNode Parent::*Member, class Derived>
482class IntrusiveRedBlackTreeMemberTraits<Member, Derived> {
483public:
484 template <class Comparator>
485 using TreeType = IntrusiveRedBlackTree<Derived, IntrusiveRedBlackTreeMemberTraits, Comparator>;
486 using TreeTypeImpl = impl::IntrusiveRedBlackTreeImpl;
487
488private:
489 template <class, class, class>
490 friend class IntrusiveRedBlackTree;
491
492 friend class impl::IntrusiveRedBlackTreeImpl;
493
494 static constexpr IntrusiveRedBlackTreeNode* GetNode(Derived* parent) {
495 return std::addressof(parent->*Member);
496 }
497
498 static constexpr IntrusiveRedBlackTreeNode const* GetNode(Derived const* parent) {
499 return std::addressof(parent->*Member);
500 }
501
502 static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
503 return GetParentPointer<Member, Derived>(node);
504 }
505
506 static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) {
507 return GetParentPointer<Member, Derived>(node);
508 }
509
510private:
511 static constexpr TypedStorage<Derived> DerivedStorage = {};
512 static_assert(GetParent(GetNode(GetPointer(DerivedStorage))) == GetPointer(DerivedStorage));
513};
514
515template <auto T, class Derived = impl::GetParentType<T>>
516class IntrusiveRedBlackTreeMemberTraitsDeferredAssert;
517
518template <class Parent, IntrusiveRedBlackTreeNode Parent::*Member, class Derived>
519class IntrusiveRedBlackTreeMemberTraitsDeferredAssert<Member, Derived> {
520public:
521 template <class Comparator>
522 using TreeType =
523 IntrusiveRedBlackTree<Derived, IntrusiveRedBlackTreeMemberTraitsDeferredAssert, Comparator>;
524 using TreeTypeImpl = impl::IntrusiveRedBlackTreeImpl;
525
526 static constexpr bool IsValid() {
527 TypedStorage<Derived> DerivedStorage = {};
528 return GetParent(GetNode(GetPointer(DerivedStorage))) == GetPointer(DerivedStorage);
529 }
530
531private:
532 template <class, class, class>
533 friend class IntrusiveRedBlackTree;
534
535 friend class impl::IntrusiveRedBlackTreeImpl;
536
537 static constexpr IntrusiveRedBlackTreeNode* GetNode(Derived* parent) {
538 return std::addressof(parent->*Member);
539 }
540
541 static constexpr IntrusiveRedBlackTreeNode const* GetNode(Derived const* parent) {
542 return std::addressof(parent->*Member);
543 }
544
545 static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
546 return GetParentPointer<Member, Derived>(node);
547 }
548
549 static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) {
550 return GetParentPointer<Member, Derived>(node);
551 }
552};
553
554template <class Derived>
555class IntrusiveRedBlackTreeBaseNode : public IntrusiveRedBlackTreeNode {
556public:
557 constexpr Derived* GetPrev() {
558 return static_cast<Derived*>(impl::IntrusiveRedBlackTreeImpl::GetPrev(this));
559 }
560 constexpr const Derived* GetPrev() const {
561 return static_cast<const Derived*>(impl::IntrusiveRedBlackTreeImpl::GetPrev(this));
562 }
563
564 constexpr Derived* GetNext() {
565 return static_cast<Derived*>(impl::IntrusiveRedBlackTreeImpl::GetNext(this));
566 }
567 constexpr const Derived* GetNext() const {
568 return static_cast<const Derived*>(impl::IntrusiveRedBlackTreeImpl::GetNext(this));
569 }
570};
571
572template <class Derived>
573class IntrusiveRedBlackTreeBaseTraits {
574public:
575 template <class Comparator>
576 using TreeType = IntrusiveRedBlackTree<Derived, IntrusiveRedBlackTreeBaseTraits, Comparator>;
577 using TreeTypeImpl = impl::IntrusiveRedBlackTreeImpl;
578
579private:
580 template <class, class, class>
581 friend class IntrusiveRedBlackTree;
582
583 friend class impl::IntrusiveRedBlackTreeImpl;
584
585 static constexpr IntrusiveRedBlackTreeNode* GetNode(Derived* parent) {
586 return static_cast<IntrusiveRedBlackTreeNode*>(parent);
587 }
588
589 static constexpr IntrusiveRedBlackTreeNode const* GetNode(Derived const* parent) {
590 return static_cast<const IntrusiveRedBlackTreeNode*>(parent);
591 }
592
593 static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
594 return static_cast<Derived*>(node);
595 }
596
597 static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) {
598 return static_cast<const Derived*>(node);
599 }
600};
601
602} // 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) {
145 PrintColoredMessage(entry); 145 PrintColoredMessage(entry);
146} 146}
147 147
148// _SH_DENYWR allows read only access to the file for other programs. 148FileBackend::FileBackend(const std::string& filename) : bytes_written(0) {
149// It is #defined to 0 on other platforms 149 if (Common::FS::Exists(filename + ".old.txt")) {
150FileBackend::FileBackend(const std::string& filename) 150 Common::FS::Delete(filename + ".old.txt");
151 : file(filename, "w", _SH_DENYWR), bytes_written(0) {} 151 }
152 if (Common::FS::Exists(filename)) {
153 Common::FS::Rename(filename, filename + ".old.txt");
154 }
155
156 // _SH_DENYWR allows read only access to the file for other programs.
157 // It is #defined to 0 on other platforms
158 file = Common::FS::IOFile(filename, "w", _SH_DENYWR);
159}
152 160
153void FileBackend::Write(const Entry& entry) { 161void FileBackend::Write(const Entry& entry) {
154 // prevent logs from going over the maximum size (in case its spamming and the user doesn't 162 // prevent logs from going over the maximum size (in case its spamming and the user doesn't
diff --git a/src/common/page_table.h b/src/common/page_table.h
index 0c14e6433..61c5552e0 100644
--- a/src/common/page_table.h
+++ b/src/common/page_table.h
@@ -90,7 +90,7 @@ struct PageTable {
90 PageTable& operator=(PageTable&&) noexcept = default; 90 PageTable& operator=(PageTable&&) noexcept = default;
91 91
92 /** 92 /**
93 * Resizes the page table to be able to accomodate enough pages within 93 * Resizes the page table to be able to accommodate enough pages within
94 * a given address space. 94 * a given address space.
95 * 95 *
96 * @param address_space_width_in_bits The address size width in bits. 96 * @param address_space_width_in_bits The address size width in bits.
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 @@
1// Copyright 2021 yuzu Emulator Project
2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included.
4
5#pragma once
6
7#include <type_traits>
8
9#include "common/assert.h"
10#include "common/common_types.h"
11
12namespace Common {
13namespace detail {
14template <typename T, size_t Size, size_t Align>
15struct TypedStorageImpl {
16 std::aligned_storage_t<Size, Align> storage_;
17};
18} // namespace detail
19
20template <typename T>
21using TypedStorage = detail::TypedStorageImpl<T, sizeof(T), alignof(T)>;
22
23template <typename T>
24static constexpr T* GetPointer(TypedStorage<T>& ts) {
25 return static_cast<T*>(static_cast<void*>(std::addressof(ts.storage_)));
26}
27
28template <typename T>
29static constexpr const T* GetPointer(const TypedStorage<T>& ts) {
30 return static_cast<const T*>(static_cast<const void*>(std::addressof(ts.storage_)));
31}
32
33namespace impl {
34
35template <size_t MaxDepth>
36struct OffsetOfUnionHolder {
37 template <typename ParentType, typename MemberType, size_t Offset>
38 union UnionImpl {
39 using PaddingMember = char;
40 static constexpr size_t GetOffset() {
41 return Offset;
42 }
43
44#pragma pack(push, 1)
45 struct {
46 PaddingMember padding[Offset];
47 MemberType members[(sizeof(ParentType) / sizeof(MemberType)) + 1];
48 } data;
49#pragma pack(pop)
50 UnionImpl<ParentType, MemberType, Offset + 1> next_union;
51 };
52
53 template <typename ParentType, typename MemberType>
54 union UnionImpl<ParentType, MemberType, 0> {
55 static constexpr size_t GetOffset() {
56 return 0;
57 }
58
59 struct {
60 MemberType members[(sizeof(ParentType) / sizeof(MemberType)) + 1];
61 } data;
62 UnionImpl<ParentType, MemberType, 1> next_union;
63 };
64
65 template <typename ParentType, typename MemberType>
66 union UnionImpl<ParentType, MemberType, MaxDepth> {};
67};
68
69template <typename ParentType, typename MemberType>
70struct OffsetOfCalculator {
71 using UnionHolder =
72 typename OffsetOfUnionHolder<sizeof(MemberType)>::template UnionImpl<ParentType, MemberType,
73 0>;
74 union Union {
75 char c{};
76 UnionHolder first_union;
77 TypedStorage<ParentType> parent;
78
79 constexpr Union() : c() {}
80 };
81 static constexpr Union U = {};
82
83 static constexpr const MemberType* GetNextAddress(const MemberType* start,
84 const MemberType* target) {
85 while (start < target) {
86 start++;
87 }
88 return start;
89 }
90
91 static constexpr std::ptrdiff_t GetDifference(const MemberType* start,
92 const MemberType* target) {
93 return (target - start) * sizeof(MemberType);
94 }
95
96 template <typename CurUnion>
97 static constexpr std::ptrdiff_t OffsetOfImpl(MemberType ParentType::*member,
98 CurUnion& cur_union) {
99 constexpr size_t Offset = CurUnion::GetOffset();
100 const auto target = std::addressof(GetPointer(U.parent)->*member);
101 const auto start = std::addressof(cur_union.data.members[0]);
102 const auto next = GetNextAddress(start, target);
103
104 if (next != target) {
105 if constexpr (Offset < sizeof(MemberType) - 1) {
106 return OffsetOfImpl(member, cur_union.next_union);
107 } else {
108 UNREACHABLE();
109 }
110 }
111
112 return (next - start) * sizeof(MemberType) + Offset;
113 }
114
115 static constexpr std::ptrdiff_t OffsetOf(MemberType ParentType::*member) {
116 return OffsetOfImpl(member, U.first_union);
117 }
118};
119
120template <typename T>
121struct GetMemberPointerTraits;
122
123template <typename P, typename M>
124struct GetMemberPointerTraits<M P::*> {
125 using Parent = P;
126 using Member = M;
127};
128
129template <auto MemberPtr>
130using GetParentType = typename GetMemberPointerTraits<decltype(MemberPtr)>::Parent;
131
132template <auto MemberPtr>
133using GetMemberType = typename GetMemberPointerTraits<decltype(MemberPtr)>::Member;
134
135template <auto MemberPtr, typename RealParentType = GetParentType<MemberPtr>>
136static inline std::ptrdiff_t OffsetOf = [] {
137 using DeducedParentType = GetParentType<MemberPtr>;
138 using MemberType = GetMemberType<MemberPtr>;
139 static_assert(std::is_base_of<DeducedParentType, RealParentType>::value ||
140 std::is_same<RealParentType, DeducedParentType>::value);
141
142 return OffsetOfCalculator<RealParentType, MemberType>::OffsetOf(MemberPtr);
143}();
144
145} // namespace impl
146
147template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
148constexpr RealParentType& GetParentReference(impl::GetMemberType<MemberPtr>* member) {
149 std::ptrdiff_t Offset = impl::OffsetOf<MemberPtr, RealParentType>;
150 return *static_cast<RealParentType*>(
151 static_cast<void*>(static_cast<uint8_t*>(static_cast<void*>(member)) - Offset));
152}
153
154template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
155constexpr RealParentType const& GetParentReference(impl::GetMemberType<MemberPtr> const* member) {
156 std::ptrdiff_t Offset = impl::OffsetOf<MemberPtr, RealParentType>;
157 return *static_cast<const RealParentType*>(static_cast<const void*>(
158 static_cast<const uint8_t*>(static_cast<const void*>(member)) - Offset));
159}
160
161template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
162constexpr RealParentType* GetParentPointer(impl::GetMemberType<MemberPtr>* member) {
163 return std::addressof(GetParentReference<MemberPtr, RealParentType>(member));
164}
165
166template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
167constexpr RealParentType const* GetParentPointer(impl::GetMemberType<MemberPtr> const* member) {
168 return std::addressof(GetParentReference<MemberPtr, RealParentType>(member));
169}
170
171template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
172constexpr RealParentType& GetParentReference(impl::GetMemberType<MemberPtr>& member) {
173 return GetParentReference<MemberPtr, RealParentType>(std::addressof(member));
174}
175
176template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
177constexpr RealParentType const& GetParentReference(impl::GetMemberType<MemberPtr> const& member) {
178 return GetParentReference<MemberPtr, RealParentType>(std::addressof(member));
179}
180
181template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
182constexpr RealParentType* GetParentPointer(impl::GetMemberType<MemberPtr>& member) {
183 return std::addressof(GetParentReference<MemberPtr, RealParentType>(member));
184}
185
186template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
187constexpr RealParentType const* GetParentPointer(impl::GetMemberType<MemberPtr> const& member) {
188 return std::addressof(GetParentReference<MemberPtr, RealParentType>(member));
189}
190
191} // namespace Common
diff --git a/src/common/swap.h b/src/common/swap.h
index 7665942a2..a80e191dc 100644
--- a/src/common/swap.h
+++ b/src/common/swap.h
@@ -394,7 +394,7 @@ public:
394 template <typename S, typename T2, typename F2> 394 template <typename S, typename T2, typename F2>
395 friend S operator%(const S& p, const swapped_t v); 395 friend S operator%(const S& p, const swapped_t v);
396 396
397 // Arithmetics + assignements 397 // Arithmetics + assignments
398 template <typename S, typename T2, typename F2> 398 template <typename S, typename T2, typename F2>
399 friend S operator+=(const S& p, const swapped_t v); 399 friend S operator+=(const S& p, const swapped_t v);
400 400
@@ -451,7 +451,7 @@ S operator%(const S& i, const swap_struct_t<T, F> v) {
451 return i % v.swap(); 451 return i % v.swap();
452} 452}
453 453
454// Arithmetics + assignements 454// Arithmetics + assignments
455template <typename S, typename T, typename F> 455template <typename S, typename T, typename F>
456S& operator+=(S& i, const swap_struct_t<T, F> v) { 456S& operator+=(S& i, const swap_struct_t<T, F> v) {
457 i += v.swap(); 457 i += v.swap();
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 @@
1// Copyright 2013 Dolphin Emulator Project / 2014 Citra Emulator Project
2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included.
4
5#include <ctime>
6#include <fmt/format.h>
7#include "common/common_types.h"
8#include "common/string_util.h"
9#include "common/timer.h"
10
11namespace Common {
12
13std::chrono::milliseconds Timer::GetTimeMs() {
14 return std::chrono::duration_cast<std::chrono::milliseconds>(
15 std::chrono::system_clock::now().time_since_epoch());
16}
17
18// --------------------------------------------
19// Initiate, Start, Stop, and Update the time
20// --------------------------------------------
21
22// Set initial values for the class
23Timer::Timer() : m_LastTime(0), m_StartTime(0), m_Running(false) {
24 Update();
25}
26
27// Write the starting time
28void Timer::Start() {
29 m_StartTime = GetTimeMs();
30 m_Running = true;
31}
32
33// Stop the timer
34void Timer::Stop() {
35 // Write the final time
36 m_LastTime = GetTimeMs();
37 m_Running = false;
38}
39
40// Update the last time variable
41void Timer::Update() {
42 m_LastTime = GetTimeMs();
43 // TODO(ector) - QPF
44}
45
46// -------------------------------------
47// Get time difference and elapsed time
48// -------------------------------------
49
50// Get the number of milliseconds since the last Update()
51std::chrono::milliseconds Timer::GetTimeDifference() {
52 return GetTimeMs() - m_LastTime;
53}
54
55// Add the time difference since the last Update() to the starting time.
56// This is used to compensate for a paused game.
57void Timer::AddTimeDifference() {
58 m_StartTime += GetTimeDifference();
59}
60
61// Get the time elapsed since the Start()
62std::chrono::milliseconds Timer::GetTimeElapsed() {
63 // If we have not started yet, return 1 (because then I don't
64 // have to change the FPS calculation in CoreRerecording.cpp .
65 if (m_StartTime.count() == 0)
66 return std::chrono::milliseconds(1);
67
68 // Return the final timer time if the timer is stopped
69 if (!m_Running)
70 return (m_LastTime - m_StartTime);
71
72 return (GetTimeMs() - m_StartTime);
73}
74
75// Get the formatted time elapsed since the Start()
76std::string Timer::GetTimeElapsedFormatted() const {
77 // If we have not started yet, return zero
78 if (m_StartTime.count() == 0)
79 return "00:00:00:000";
80
81 // The number of milliseconds since the start.
82 // Use a different value if the timer is stopped.
83 std::chrono::milliseconds Milliseconds;
84 if (m_Running)
85 Milliseconds = GetTimeMs() - m_StartTime;
86 else
87 Milliseconds = m_LastTime - m_StartTime;
88 // Seconds
89 std::chrono::seconds Seconds = std::chrono::duration_cast<std::chrono::seconds>(Milliseconds);
90 // Minutes
91 std::chrono::minutes Minutes = std::chrono::duration_cast<std::chrono::minutes>(Milliseconds);
92 // Hours
93 std::chrono::hours Hours = std::chrono::duration_cast<std::chrono::hours>(Milliseconds);
94
95 std::string TmpStr = fmt::format("{:02}:{:02}:{:02}:{:03}", Hours.count(), Minutes.count() % 60,
96 Seconds.count() % 60, Milliseconds.count() % 1000);
97 return TmpStr;
98}
99
100// Get the number of seconds since January 1 1970
101std::chrono::seconds Timer::GetTimeSinceJan1970() {
102 return std::chrono::duration_cast<std::chrono::seconds>(GetTimeMs());
103}
104
105std::chrono::seconds Timer::GetLocalTimeSinceJan1970() {
106 time_t sysTime, tzDiff, tzDST;
107 struct tm* gmTime;
108
109 time(&sysTime);
110
111 // Account for DST where needed
112 gmTime = localtime(&sysTime);
113 if (gmTime->tm_isdst == 1)
114 tzDST = 3600;
115 else
116 tzDST = 0;
117
118 // Lazy way to get local time in sec
119 gmTime = gmtime(&sysTime);
120 tzDiff = sysTime - mktime(gmTime);
121
122 return std::chrono::seconds(sysTime + tzDiff + tzDST);
123}
124
125// Return the current time formatted as Minutes:Seconds:Milliseconds
126// in the form 00:00:000.
127std::string Timer::GetTimeFormatted() {
128 time_t sysTime;
129 struct tm* gmTime;
130 char tmp[13];
131
132 time(&sysTime);
133 gmTime = localtime(&sysTime);
134
135 strftime(tmp, 6, "%M:%S", gmTime);
136
137 u64 milliseconds = static_cast<u64>(GetTimeMs().count()) % 1000;
138 return fmt::format("{}:{:03}", tmp, milliseconds);
139}
140
141// Returns a timestamp with decimals for precise time comparisons
142// ----------------
143double Timer::GetDoubleTime() {
144 // Get continuous timestamp
145 auto tmp_seconds = static_cast<u64>(GetTimeSinceJan1970().count());
146 const auto ms = static_cast<double>(static_cast<u64>(GetTimeMs().count()) % 1000);
147
148 // Remove a few years. We only really want enough seconds to make
149 // sure that we are detecting actual actions, perhaps 60 seconds is
150 // enough really, but I leave a year of seconds anyway, in case the
151 // user's clock is incorrect or something like that.
152 tmp_seconds = tmp_seconds - (38 * 365 * 24 * 60 * 60);
153
154 // Make a smaller integer that fits in the double
155 const auto seconds = static_cast<u32>(tmp_seconds);
156 return seconds + ms;
157}
158
159} // 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 @@
1// Copyright 2013 Dolphin Emulator Project / 2014 Citra Emulator Project
2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included.
4
5#pragma once
6
7#include <chrono>
8#include <string>
9#include "common/common_types.h"
10
11namespace Common {
12class Timer {
13public:
14 Timer();
15
16 void Start();
17 void Stop();
18 void Update();
19
20 // The time difference is always returned in milliseconds, regardless of alternative internal
21 // representation
22 [[nodiscard]] std::chrono::milliseconds GetTimeDifference();
23 void AddTimeDifference();
24
25 [[nodiscard]] static std::chrono::seconds GetTimeSinceJan1970();
26 [[nodiscard]] static std::chrono::seconds GetLocalTimeSinceJan1970();
27 [[nodiscard]] static double GetDoubleTime();
28
29 [[nodiscard]] static std::string GetTimeFormatted();
30 [[nodiscard]] std::string GetTimeElapsedFormatted() const;
31 [[nodiscard]] std::chrono::milliseconds GetTimeElapsed();
32
33 [[nodiscard]] static std::chrono::milliseconds GetTimeMs();
34
35private:
36 std::chrono::milliseconds m_LastTime;
37 std::chrono::milliseconds m_StartTime;
38 bool m_Running;
39};
40
41} // 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 @@
1/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */
2/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
3/* $FreeBSD$ */
4
5/*-
6 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30#pragma once
31
32/*
33 * This file defines data structures for red-black trees.
34 *
35 * A red-black tree is a binary search tree with the node color as an
36 * extra attribute. It fulfills a set of conditions:
37 * - every search path from the root to a leaf consists of the
38 * same number of black nodes,
39 * - each red node (except for the root) has a black parent,
40 * - each leaf node is black.
41 *
42 * Every operation on a red-black tree is bounded as O(lg n).
43 * The maximum height of a red-black tree is 2lg (n+1).
44 */
45
46namespace Common {
47template <typename T>
48class RBHead {
49public:
50 [[nodiscard]] T* Root() {
51 return rbh_root;
52 }
53
54 [[nodiscard]] const T* Root() const {
55 return rbh_root;
56 }
57
58 void SetRoot(T* root) {
59 rbh_root = root;
60 }
61
62 [[nodiscard]] bool IsEmpty() const {
63 return Root() == nullptr;
64 }
65
66private:
67 T* rbh_root = nullptr;
68};
69
70enum class EntryColor {
71 Black,
72 Red,
73};
74
75template <typename T>
76class RBEntry {
77public:
78 [[nodiscard]] T* Left() {
79 return rbe_left;
80 }
81
82 [[nodiscard]] const T* Left() const {
83 return rbe_left;
84 }
85
86 void SetLeft(T* left) {
87 rbe_left = left;
88 }
89
90 [[nodiscard]] T* Right() {
91 return rbe_right;
92 }
93
94 [[nodiscard]] const T* Right() const {
95 return rbe_right;
96 }
97
98 void SetRight(T* right) {
99 rbe_right = right;
100 }
101
102 [[nodiscard]] T* Parent() {
103 return rbe_parent;
104 }
105
106 [[nodiscard]] const T* Parent() const {
107 return rbe_parent;
108 }
109
110 void SetParent(T* parent) {
111 rbe_parent = parent;
112 }
113
114 [[nodiscard]] bool IsBlack() const {
115 return rbe_color == EntryColor::Black;
116 }
117
118 [[nodiscard]] bool IsRed() const {
119 return rbe_color == EntryColor::Red;
120 }
121
122 [[nodiscard]] EntryColor Color() const {
123 return rbe_color;
124 }
125
126 void SetColor(EntryColor color) {
127 rbe_color = color;
128 }
129
130private:
131 T* rbe_left = nullptr;
132 T* rbe_right = nullptr;
133 T* rbe_parent = nullptr;
134 EntryColor rbe_color{};
135};
136
137template <typename Node>
138[[nodiscard]] RBEntry<Node>& RB_ENTRY(Node* node) {
139 return node->GetEntry();
140}
141
142template <typename Node>
143[[nodiscard]] const RBEntry<Node>& RB_ENTRY(const Node* node) {
144 return node->GetEntry();
145}
146
147template <typename Node>
148[[nodiscard]] Node* RB_PARENT(Node* node) {
149 return RB_ENTRY(node).Parent();
150}
151
152template <typename Node>
153[[nodiscard]] const Node* RB_PARENT(const Node* node) {
154 return RB_ENTRY(node).Parent();
155}
156
157template <typename Node>
158void RB_SET_PARENT(Node* node, Node* parent) {
159 return RB_ENTRY(node).SetParent(parent);
160}
161
162template <typename Node>
163[[nodiscard]] Node* RB_LEFT(Node* node) {
164 return RB_ENTRY(node).Left();
165}
166
167template <typename Node>
168[[nodiscard]] const Node* RB_LEFT(const Node* node) {
169 return RB_ENTRY(node).Left();
170}
171
172template <typename Node>
173void RB_SET_LEFT(Node* node, Node* left) {
174 return RB_ENTRY(node).SetLeft(left);
175}
176
177template <typename Node>
178[[nodiscard]] Node* RB_RIGHT(Node* node) {
179 return RB_ENTRY(node).Right();
180}
181
182template <typename Node>
183[[nodiscard]] const Node* RB_RIGHT(const Node* node) {
184 return RB_ENTRY(node).Right();
185}
186
187template <typename Node>
188void RB_SET_RIGHT(Node* node, Node* right) {
189 return RB_ENTRY(node).SetRight(right);
190}
191
192template <typename Node>
193[[nodiscard]] bool RB_IS_BLACK(const Node* node) {
194 return RB_ENTRY(node).IsBlack();
195}
196
197template <typename Node>
198[[nodiscard]] bool RB_IS_RED(const Node* node) {
199 return RB_ENTRY(node).IsRed();
200}
201
202template <typename Node>
203[[nodiscard]] EntryColor RB_COLOR(const Node* node) {
204 return RB_ENTRY(node).Color();
205}
206
207template <typename Node>
208void RB_SET_COLOR(Node* node, EntryColor color) {
209 return RB_ENTRY(node).SetColor(color);
210}
211
212template <typename Node>
213void RB_SET(Node* node, Node* parent) {
214 auto& entry = RB_ENTRY(node);
215 entry.SetParent(parent);
216 entry.SetLeft(nullptr);
217 entry.SetRight(nullptr);
218 entry.SetColor(EntryColor::Red);
219}
220
221template <typename Node>
222void RB_SET_BLACKRED(Node* black, Node* red) {
223 RB_SET_COLOR(black, EntryColor::Black);
224 RB_SET_COLOR(red, EntryColor::Red);
225}
226
227template <typename Node>
228void RB_ROTATE_LEFT(RBHead<Node>* head, Node* elm, Node*& tmp) {
229 tmp = RB_RIGHT(elm);
230 RB_SET_RIGHT(elm, RB_LEFT(tmp));
231 if (RB_RIGHT(elm) != nullptr) {
232 RB_SET_PARENT(RB_LEFT(tmp), elm);
233 }
234
235 RB_SET_PARENT(tmp, RB_PARENT(elm));
236 if (RB_PARENT(tmp) != nullptr) {
237 if (elm == RB_LEFT(RB_PARENT(elm))) {
238 RB_SET_LEFT(RB_PARENT(elm), tmp);
239 } else {
240 RB_SET_RIGHT(RB_PARENT(elm), tmp);
241 }
242 } else {
243 head->SetRoot(tmp);
244 }
245
246 RB_SET_LEFT(tmp, elm);
247 RB_SET_PARENT(elm, tmp);
248}
249
250template <typename Node>
251void RB_ROTATE_RIGHT(RBHead<Node>* head, Node* elm, Node*& tmp) {
252 tmp = RB_LEFT(elm);
253 RB_SET_LEFT(elm, RB_RIGHT(tmp));
254 if (RB_LEFT(elm) != nullptr) {
255 RB_SET_PARENT(RB_RIGHT(tmp), elm);
256 }
257
258 RB_SET_PARENT(tmp, RB_PARENT(elm));
259 if (RB_PARENT(tmp) != nullptr) {
260 if (elm == RB_LEFT(RB_PARENT(elm))) {
261 RB_SET_LEFT(RB_PARENT(elm), tmp);
262 } else {
263 RB_SET_RIGHT(RB_PARENT(elm), tmp);
264 }
265 } else {
266 head->SetRoot(tmp);
267 }
268
269 RB_SET_RIGHT(tmp, elm);
270 RB_SET_PARENT(elm, tmp);
271}
272
273template <typename Node>
274void RB_INSERT_COLOR(RBHead<Node>* head, Node* elm) {
275 Node* parent = nullptr;
276 Node* tmp = nullptr;
277
278 while ((parent = RB_PARENT(elm)) != nullptr && RB_IS_RED(parent)) {
279 Node* gparent = RB_PARENT(parent);
280 if (parent == RB_LEFT(gparent)) {
281 tmp = RB_RIGHT(gparent);
282 if (tmp && RB_IS_RED(tmp)) {
283 RB_SET_COLOR(tmp, EntryColor::Black);
284 RB_SET_BLACKRED(parent, gparent);
285 elm = gparent;
286 continue;
287 }
288
289 if (RB_RIGHT(parent) == elm) {
290 RB_ROTATE_LEFT(head, parent, tmp);
291 tmp = parent;
292 parent = elm;
293 elm = tmp;
294 }
295
296 RB_SET_BLACKRED(parent, gparent);
297 RB_ROTATE_RIGHT(head, gparent, tmp);
298 } else {
299 tmp = RB_LEFT(gparent);
300 if (tmp && RB_IS_RED(tmp)) {
301 RB_SET_COLOR(tmp, EntryColor::Black);
302 RB_SET_BLACKRED(parent, gparent);
303 elm = gparent;
304 continue;
305 }
306
307 if (RB_LEFT(parent) == elm) {
308 RB_ROTATE_RIGHT(head, parent, tmp);
309 tmp = parent;
310 parent = elm;
311 elm = tmp;
312 }
313
314 RB_SET_BLACKRED(parent, gparent);
315 RB_ROTATE_LEFT(head, gparent, tmp);
316 }
317 }
318
319 RB_SET_COLOR(head->Root(), EntryColor::Black);
320}
321
322template <typename Node>
323void RB_REMOVE_COLOR(RBHead<Node>* head, Node* parent, Node* elm) {
324 Node* tmp;
325 while ((elm == nullptr || RB_IS_BLACK(elm)) && elm != head->Root()) {
326 if (RB_LEFT(parent) == elm) {
327 tmp = RB_RIGHT(parent);
328 if (RB_IS_RED(tmp)) {
329 RB_SET_BLACKRED(tmp, parent);
330 RB_ROTATE_LEFT(head, parent, tmp);
331 tmp = RB_RIGHT(parent);
332 }
333
334 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) &&
335 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) {
336 RB_SET_COLOR(tmp, EntryColor::Red);
337 elm = parent;
338 parent = RB_PARENT(elm);
339 } else {
340 if (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp))) {
341 Node* oleft;
342 if ((oleft = RB_LEFT(tmp)) != nullptr) {
343 RB_SET_COLOR(oleft, EntryColor::Black);
344 }
345
346 RB_SET_COLOR(tmp, EntryColor::Red);
347 RB_ROTATE_RIGHT(head, tmp, oleft);
348 tmp = RB_RIGHT(parent);
349 }
350
351 RB_SET_COLOR(tmp, RB_COLOR(parent));
352 RB_SET_COLOR(parent, EntryColor::Black);
353 if (RB_RIGHT(tmp)) {
354 RB_SET_COLOR(RB_RIGHT(tmp), EntryColor::Black);
355 }
356
357 RB_ROTATE_LEFT(head, parent, tmp);
358 elm = head->Root();
359 break;
360 }
361 } else {
362 tmp = RB_LEFT(parent);
363 if (RB_IS_RED(tmp)) {
364 RB_SET_BLACKRED(tmp, parent);
365 RB_ROTATE_RIGHT(head, parent, tmp);
366 tmp = RB_LEFT(parent);
367 }
368
369 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) &&
370 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) {
371 RB_SET_COLOR(tmp, EntryColor::Red);
372 elm = parent;
373 parent = RB_PARENT(elm);
374 } else {
375 if (RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) {
376 Node* oright;
377 if ((oright = RB_RIGHT(tmp)) != nullptr) {
378 RB_SET_COLOR(oright, EntryColor::Black);
379 }
380
381 RB_SET_COLOR(tmp, EntryColor::Red);
382 RB_ROTATE_LEFT(head, tmp, oright);
383 tmp = RB_LEFT(parent);
384 }
385
386 RB_SET_COLOR(tmp, RB_COLOR(parent));
387 RB_SET_COLOR(parent, EntryColor::Black);
388
389 if (RB_LEFT(tmp)) {
390 RB_SET_COLOR(RB_LEFT(tmp), EntryColor::Black);
391 }
392
393 RB_ROTATE_RIGHT(head, parent, tmp);
394 elm = head->Root();
395 break;
396 }
397 }
398 }
399
400 if (elm) {
401 RB_SET_COLOR(elm, EntryColor::Black);
402 }
403}
404
405template <typename Node>
406Node* RB_REMOVE(RBHead<Node>* head, Node* elm) {
407 Node* child = nullptr;
408 Node* parent = nullptr;
409 Node* old = elm;
410 EntryColor color{};
411
412 const auto finalize = [&] {
413 if (color == EntryColor::Black) {
414 RB_REMOVE_COLOR(head, parent, child);
415 }
416
417 return old;
418 };
419
420 if (RB_LEFT(elm) == nullptr) {
421 child = RB_RIGHT(elm);
422 } else if (RB_RIGHT(elm) == nullptr) {
423 child = RB_LEFT(elm);
424 } else {
425 Node* left;
426 elm = RB_RIGHT(elm);
427 while ((left = RB_LEFT(elm)) != nullptr) {
428 elm = left;
429 }
430
431 child = RB_RIGHT(elm);
432 parent = RB_PARENT(elm);
433 color = RB_COLOR(elm);
434
435 if (child) {
436 RB_SET_PARENT(child, parent);
437 }
438 if (parent) {
439 if (RB_LEFT(parent) == elm) {
440 RB_SET_LEFT(parent, child);
441 } else {
442 RB_SET_RIGHT(parent, child);
443 }
444 } else {
445 head->SetRoot(child);
446 }
447
448 if (RB_PARENT(elm) == old) {
449 parent = elm;
450 }
451
452 elm->SetEntry(old->GetEntry());
453
454 if (RB_PARENT(old)) {
455 if (RB_LEFT(RB_PARENT(old)) == old) {
456 RB_SET_LEFT(RB_PARENT(old), elm);
457 } else {
458 RB_SET_RIGHT(RB_PARENT(old), elm);
459 }
460 } else {
461 head->SetRoot(elm);
462 }
463 RB_SET_PARENT(RB_LEFT(old), elm);
464 if (RB_RIGHT(old)) {
465 RB_SET_PARENT(RB_RIGHT(old), elm);
466 }
467 if (parent) {
468 left = parent;
469 }
470
471 return finalize();
472 }
473
474 parent = RB_PARENT(elm);
475 color = RB_COLOR(elm);
476
477 if (child) {
478 RB_SET_PARENT(child, parent);
479 }
480 if (parent) {
481 if (RB_LEFT(parent) == elm) {
482 RB_SET_LEFT(parent, child);
483 } else {
484 RB_SET_RIGHT(parent, child);
485 }
486 } else {
487 head->SetRoot(child);
488 }
489
490 return finalize();
491}
492
493// Inserts a node into the RB tree
494template <typename Node, typename CompareFunction>
495Node* RB_INSERT(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
496 Node* parent = nullptr;
497 Node* tmp = head->Root();
498 int comp = 0;
499
500 while (tmp) {
501 parent = tmp;
502 comp = cmp(elm, parent);
503 if (comp < 0) {
504 tmp = RB_LEFT(tmp);
505 } else if (comp > 0) {
506 tmp = RB_RIGHT(tmp);
507 } else {
508 return tmp;
509 }
510 }
511
512 RB_SET(elm, parent);
513
514 if (parent != nullptr) {
515 if (comp < 0) {
516 RB_SET_LEFT(parent, elm);
517 } else {
518 RB_SET_RIGHT(parent, elm);
519 }
520 } else {
521 head->SetRoot(elm);
522 }
523
524 RB_INSERT_COLOR(head, elm);
525 return nullptr;
526}
527
528// Finds the node with the same key as elm
529template <typename Node, typename CompareFunction>
530Node* RB_FIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
531 Node* tmp = head->Root();
532
533 while (tmp) {
534 const int comp = cmp(elm, tmp);
535 if (comp < 0) {
536 tmp = RB_LEFT(tmp);
537 } else if (comp > 0) {
538 tmp = RB_RIGHT(tmp);
539 } else {
540 return tmp;
541 }
542 }
543
544 return nullptr;
545}
546
547// Finds the first node greater than or equal to the search key
548template <typename Node, typename CompareFunction>
549Node* RB_NFIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
550 Node* tmp = head->Root();
551 Node* res = nullptr;
552
553 while (tmp) {
554 const int comp = cmp(elm, tmp);
555 if (comp < 0) {
556 res = tmp;
557 tmp = RB_LEFT(tmp);
558 } else if (comp > 0) {
559 tmp = RB_RIGHT(tmp);
560 } else {
561 return tmp;
562 }
563 }
564
565 return res;
566}
567
568// Finds the node with the same key as lelm
569template <typename Node, typename CompareFunction>
570Node* RB_FIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) {
571 Node* tmp = head->Root();
572
573 while (tmp) {
574 const int comp = lcmp(lelm, tmp);
575 if (comp < 0) {
576 tmp = RB_LEFT(tmp);
577 } else if (comp > 0) {
578 tmp = RB_RIGHT(tmp);
579 } else {
580 return tmp;
581 }
582 }
583
584 return nullptr;
585}
586
587// Finds the first node greater than or equal to the search key
588template <typename Node, typename CompareFunction>
589Node* RB_NFIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) {
590 Node* tmp = head->Root();
591 Node* res = nullptr;
592
593 while (tmp) {
594 const int comp = lcmp(lelm, tmp);
595 if (comp < 0) {
596 res = tmp;
597 tmp = RB_LEFT(tmp);
598 } else if (comp > 0) {
599 tmp = RB_RIGHT(tmp);
600 } else {
601 return tmp;
602 }
603 }
604
605 return res;
606}
607
608template <typename Node>
609Node* RB_NEXT(Node* elm) {
610 if (RB_RIGHT(elm)) {
611 elm = RB_RIGHT(elm);
612 while (RB_LEFT(elm)) {
613 elm = RB_LEFT(elm);
614 }
615 } else {
616 if (RB_PARENT(elm) && (elm == RB_LEFT(RB_PARENT(elm)))) {
617 elm = RB_PARENT(elm);
618 } else {
619 while (RB_PARENT(elm) && (elm == RB_RIGHT(RB_PARENT(elm)))) {
620 elm = RB_PARENT(elm);
621 }
622 elm = RB_PARENT(elm);
623 }
624 }
625 return elm;
626}
627
628template <typename Node>
629Node* RB_PREV(Node* elm) {
630 if (RB_LEFT(elm)) {
631 elm = RB_LEFT(elm);
632 while (RB_RIGHT(elm)) {
633 elm = RB_RIGHT(elm);
634 }
635 } else {
636 if (RB_PARENT(elm) && (elm == RB_RIGHT(RB_PARENT(elm)))) {
637 elm = RB_PARENT(elm);
638 } else {
639 while (RB_PARENT(elm) && (elm == RB_LEFT(RB_PARENT(elm)))) {
640 elm = RB_PARENT(elm);
641 }
642 elm = RB_PARENT(elm);
643 }
644 }
645 return elm;
646}
647
648template <typename Node>
649Node* RB_MINMAX(RBHead<Node>* head, bool is_min) {
650 Node* tmp = head->Root();
651 Node* parent = nullptr;
652
653 while (tmp) {
654 parent = tmp;
655 if (is_min) {
656 tmp = RB_LEFT(tmp);
657 } else {
658 tmp = RB_RIGHT(tmp);
659 }
660 }
661
662 return parent;
663}
664
665template <typename Node>
666Node* RB_MIN(RBHead<Node>* head) {
667 return RB_MINMAX(head, true);
668}
669
670template <typename Node>
671Node* RB_MAX(RBHead<Node>* head) {
672 return RB_MINMAX(head, false);
673}
674} // namespace Common
HIC SVNT DRACONES