summaryrefslogtreecommitdiff
path: root/src/common
diff options
context:
space:
mode:
Diffstat (limited to 'src/common')
-rw-r--r--src/common/CMakeLists.txt3
-rw-r--r--src/common/atomic_ops.cpp75
-rw-r--r--src/common/atomic_ops.h71
-rw-r--r--src/common/common_funcs.h8
-rw-r--r--src/common/intrusive_red_black_tree.h99
-rw-r--r--src/common/timer.cpp159
-rw-r--r--src/common/timer.h41
-rw-r--r--src/common/tree.h1410
-rw-r--r--src/common/uuid.h4
-rw-r--r--src/common/x64/native_clock.cpp110
-rw-r--r--src/common/x64/native_clock.h21
11 files changed, 848 insertions, 1153 deletions
diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt
index aeaf8e81f..f77575a00 100644
--- a/src/common/CMakeLists.txt
+++ b/src/common/CMakeLists.txt
@@ -98,7 +98,6 @@ add_library(common STATIC
98 algorithm.h 98 algorithm.h
99 alignment.h 99 alignment.h
100 assert.h 100 assert.h
101 atomic_ops.cpp
102 atomic_ops.h 101 atomic_ops.h
103 detached_tasks.cpp 102 detached_tasks.cpp
104 detached_tasks.h 103 detached_tasks.h
@@ -166,8 +165,6 @@ add_library(common STATIC
166 threadsafe_queue.h 165 threadsafe_queue.h
167 time_zone.cpp 166 time_zone.cpp
168 time_zone.h 167 time_zone.h
169 timer.cpp
170 timer.h
171 tree.h 168 tree.h
172 uint128.cpp 169 uint128.cpp
173 uint128.h 170 uint128.h
diff --git a/src/common/atomic_ops.cpp b/src/common/atomic_ops.cpp
deleted file mode 100644
index 1612d0e67..000000000
--- a/src/common/atomic_ops.cpp
+++ /dev/null
@@ -1,75 +0,0 @@
1// Copyright 2020 yuzu Emulator Project
2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included.
4
5#include <cstring>
6
7#include "common/atomic_ops.h"
8
9#if _MSC_VER
10#include <intrin.h>
11#endif
12
13namespace Common {
14
15#if _MSC_VER
16
17bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected) {
18 const u8 result =
19 _InterlockedCompareExchange8(reinterpret_cast<volatile char*>(pointer), value, expected);
20 return result == expected;
21}
22
23bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected) {
24 const u16 result =
25 _InterlockedCompareExchange16(reinterpret_cast<volatile short*>(pointer), value, expected);
26 return result == expected;
27}
28
29bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected) {
30 const u32 result =
31 _InterlockedCompareExchange(reinterpret_cast<volatile long*>(pointer), value, expected);
32 return result == expected;
33}
34
35bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected) {
36 const u64 result = _InterlockedCompareExchange64(reinterpret_cast<volatile __int64*>(pointer),
37 value, expected);
38 return result == expected;
39}
40
41bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected) {
42 return _InterlockedCompareExchange128(reinterpret_cast<volatile __int64*>(pointer), value[1],
43 value[0],
44 reinterpret_cast<__int64*>(expected.data())) != 0;
45}
46
47#else
48
49bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected) {
50 return __sync_bool_compare_and_swap(pointer, expected, value);
51}
52
53bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected) {
54 return __sync_bool_compare_and_swap(pointer, expected, value);
55}
56
57bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected) {
58 return __sync_bool_compare_and_swap(pointer, expected, value);
59}
60
61bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected) {
62 return __sync_bool_compare_and_swap(pointer, expected, value);
63}
64
65bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected) {
66 unsigned __int128 value_a;
67 unsigned __int128 expected_a;
68 std::memcpy(&value_a, value.data(), sizeof(u128));
69 std::memcpy(&expected_a, expected.data(), sizeof(u128));
70 return __sync_bool_compare_and_swap((unsigned __int128*)pointer, expected_a, value_a);
71}
72
73#endif
74
75} // namespace Common
diff --git a/src/common/atomic_ops.h b/src/common/atomic_ops.h
index b46888589..2b1f515e8 100644
--- a/src/common/atomic_ops.h
+++ b/src/common/atomic_ops.h
@@ -4,14 +4,75 @@
4 4
5#pragma once 5#pragma once
6 6
7#include <cstring>
8#include <memory>
9
7#include "common/common_types.h" 10#include "common/common_types.h"
8 11
12#if _MSC_VER
13#include <intrin.h>
14#endif
15
9namespace Common { 16namespace Common {
10 17
11[[nodiscard]] bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected); 18#if _MSC_VER
12[[nodiscard]] bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected); 19
13[[nodiscard]] bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected); 20[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected) {
14[[nodiscard]] bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected); 21 const u8 result =
15[[nodiscard]] bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected); 22 _InterlockedCompareExchange8(reinterpret_cast<volatile char*>(pointer), value, expected);
23 return result == expected;
24}
25
26[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected) {
27 const u16 result =
28 _InterlockedCompareExchange16(reinterpret_cast<volatile short*>(pointer), value, expected);
29 return result == expected;
30}
31
32[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected) {
33 const u32 result =
34 _InterlockedCompareExchange(reinterpret_cast<volatile long*>(pointer), value, expected);
35 return result == expected;
36}
37
38[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected) {
39 const u64 result = _InterlockedCompareExchange64(reinterpret_cast<volatile __int64*>(pointer),
40 value, expected);
41 return result == expected;
42}
43
44[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected) {
45 return _InterlockedCompareExchange128(reinterpret_cast<volatile __int64*>(pointer), value[1],
46 value[0],
47 reinterpret_cast<__int64*>(expected.data())) != 0;
48}
49
50#else
51
52[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected) {
53 return __sync_bool_compare_and_swap(pointer, expected, value);
54}
55
56[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected) {
57 return __sync_bool_compare_and_swap(pointer, expected, value);
58}
59
60[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected) {
61 return __sync_bool_compare_and_swap(pointer, expected, value);
62}
63
64[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected) {
65 return __sync_bool_compare_and_swap(pointer, expected, value);
66}
67
68[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected) {
69 unsigned __int128 value_a;
70 unsigned __int128 expected_a;
71 std::memcpy(&value_a, value.data(), sizeof(u128));
72 std::memcpy(&expected_a, expected.data(), sizeof(u128));
73 return __sync_bool_compare_and_swap((unsigned __int128*)pointer, expected_a, value_a);
74}
75
76#endif
16 77
17} // namespace Common 78} // namespace Common
diff --git a/src/common/common_funcs.h b/src/common/common_funcs.h
index c90978f9c..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
diff --git a/src/common/intrusive_red_black_tree.h b/src/common/intrusive_red_black_tree.h
index fb55de94e..c0bbcd457 100644
--- a/src/common/intrusive_red_black_tree.h
+++ b/src/common/intrusive_red_black_tree.h
@@ -16,17 +16,30 @@ class IntrusiveRedBlackTreeImpl;
16} 16}
17 17
18struct IntrusiveRedBlackTreeNode { 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 }
19 35
20private: 36private:
21 RB_ENTRY(IntrusiveRedBlackTreeNode) entry{}; 37 EntryType entry{};
22 38
23 friend class impl::IntrusiveRedBlackTreeImpl; 39 friend class impl::IntrusiveRedBlackTreeImpl;
24 40
25 template <class, class, class> 41 template <class, class, class>
26 friend class IntrusiveRedBlackTree; 42 friend class IntrusiveRedBlackTree;
27
28public:
29 constexpr IntrusiveRedBlackTreeNode() = default;
30}; 43};
31 44
32template <class T, class Traits, class Comparator> 45template <class T, class Traits, class Comparator>
@@ -35,17 +48,12 @@ class IntrusiveRedBlackTree;
35namespace impl { 48namespace impl {
36 49
37class IntrusiveRedBlackTreeImpl { 50class IntrusiveRedBlackTreeImpl {
38
39private: 51private:
40 template <class, class, class> 52 template <class, class, class>
41 friend class ::Common::IntrusiveRedBlackTree; 53 friend class ::Common::IntrusiveRedBlackTree;
42 54
43private: 55 using RootType = RBHead<IntrusiveRedBlackTreeNode>;
44 RB_HEAD(IntrusiveRedBlackTreeRoot, IntrusiveRedBlackTreeNode); 56 RootType root;
45 using RootType = IntrusiveRedBlackTreeRoot;
46
47private:
48 IntrusiveRedBlackTreeRoot root;
49 57
50public: 58public:
51 template <bool Const> 59 template <bool Const>
@@ -121,57 +129,45 @@ public:
121 } 129 }
122 }; 130 };
123 131
124protected:
125 // Generate static implementations for non-comparison operations for IntrusiveRedBlackTreeRoot.
126 RB_GENERATE_WITHOUT_COMPARE_STATIC(IntrusiveRedBlackTreeRoot, IntrusiveRedBlackTreeNode, entry);
127
128private: 132private:
129 // Define accessors using RB_* functions. 133 // Define accessors using RB_* functions.
130 constexpr void InitializeImpl() {
131 RB_INIT(&this->root);
132 }
133
134 bool EmptyImpl() const { 134 bool EmptyImpl() const {
135 return RB_EMPTY(&this->root); 135 return root.IsEmpty();
136 } 136 }
137 137
138 IntrusiveRedBlackTreeNode* GetMinImpl() const { 138 IntrusiveRedBlackTreeNode* GetMinImpl() const {
139 return RB_MIN(IntrusiveRedBlackTreeRoot, 139 return RB_MIN(const_cast<RootType*>(&root));
140 const_cast<IntrusiveRedBlackTreeRoot*>(&this->root));
141 } 140 }
142 141
143 IntrusiveRedBlackTreeNode* GetMaxImpl() const { 142 IntrusiveRedBlackTreeNode* GetMaxImpl() const {
144 return RB_MAX(IntrusiveRedBlackTreeRoot, 143 return RB_MAX(const_cast<RootType*>(&root));
145 const_cast<IntrusiveRedBlackTreeRoot*>(&this->root));
146 } 144 }
147 145
148 IntrusiveRedBlackTreeNode* RemoveImpl(IntrusiveRedBlackTreeNode* node) { 146 IntrusiveRedBlackTreeNode* RemoveImpl(IntrusiveRedBlackTreeNode* node) {
149 return RB_REMOVE(IntrusiveRedBlackTreeRoot, &this->root, node); 147 return RB_REMOVE(&root, node);
150 } 148 }
151 149
152public: 150public:
153 static IntrusiveRedBlackTreeNode* GetNext(IntrusiveRedBlackTreeNode* node) { 151 static IntrusiveRedBlackTreeNode* GetNext(IntrusiveRedBlackTreeNode* node) {
154 return RB_NEXT(IntrusiveRedBlackTreeRoot, nullptr, node); 152 return RB_NEXT(node);
155 } 153 }
156 154
157 static IntrusiveRedBlackTreeNode* GetPrev(IntrusiveRedBlackTreeNode* node) { 155 static IntrusiveRedBlackTreeNode* GetPrev(IntrusiveRedBlackTreeNode* node) {
158 return RB_PREV(IntrusiveRedBlackTreeRoot, nullptr, node); 156 return RB_PREV(node);
159 } 157 }
160 158
161 static IntrusiveRedBlackTreeNode const* GetNext(const IntrusiveRedBlackTreeNode* node) { 159 static const IntrusiveRedBlackTreeNode* GetNext(const IntrusiveRedBlackTreeNode* node) {
162 return static_cast<const IntrusiveRedBlackTreeNode*>( 160 return static_cast<const IntrusiveRedBlackTreeNode*>(
163 GetNext(const_cast<IntrusiveRedBlackTreeNode*>(node))); 161 GetNext(const_cast<IntrusiveRedBlackTreeNode*>(node)));
164 } 162 }
165 163
166 static IntrusiveRedBlackTreeNode const* GetPrev(const IntrusiveRedBlackTreeNode* node) { 164 static const IntrusiveRedBlackTreeNode* GetPrev(const IntrusiveRedBlackTreeNode* node) {
167 return static_cast<const IntrusiveRedBlackTreeNode*>( 165 return static_cast<const IntrusiveRedBlackTreeNode*>(
168 GetPrev(const_cast<IntrusiveRedBlackTreeNode*>(node))); 166 GetPrev(const_cast<IntrusiveRedBlackTreeNode*>(node)));
169 } 167 }
170 168
171public: 169public:
172 constexpr IntrusiveRedBlackTreeImpl() : root() { 170 constexpr IntrusiveRedBlackTreeImpl() {}
173 this->InitializeImpl();
174 }
175 171
176 // Iterator accessors. 172 // Iterator accessors.
177 iterator begin() { 173 iterator begin() {
@@ -269,8 +265,6 @@ private:
269 ImplType impl{}; 265 ImplType impl{};
270 266
271public: 267public:
272 struct IntrusiveRedBlackTreeRootWithCompare : ImplType::IntrusiveRedBlackTreeRoot {};
273
274 template <bool Const> 268 template <bool Const>
275 class Iterator; 269 class Iterator;
276 270
@@ -363,11 +357,6 @@ public:
363 }; 357 };
364 358
365private: 359private:
366 // Generate static implementations for comparison operations for IntrusiveRedBlackTreeRoot.
367 RB_GENERATE_WITH_COMPARE_STATIC(IntrusiveRedBlackTreeRootWithCompare, IntrusiveRedBlackTreeNode,
368 entry, CompareImpl, LightCompareImpl);
369
370private:
371 static int CompareImpl(const IntrusiveRedBlackTreeNode* lhs, 360 static int CompareImpl(const IntrusiveRedBlackTreeNode* lhs,
372 const IntrusiveRedBlackTreeNode* rhs) { 361 const IntrusiveRedBlackTreeNode* rhs) {
373 return Comparator::Compare(*Traits::GetParent(lhs), *Traits::GetParent(rhs)); 362 return Comparator::Compare(*Traits::GetParent(lhs), *Traits::GetParent(rhs));
@@ -379,41 +368,27 @@ private:
379 368
380 // Define accessors using RB_* functions. 369 // Define accessors using RB_* functions.
381 IntrusiveRedBlackTreeNode* InsertImpl(IntrusiveRedBlackTreeNode* node) { 370 IntrusiveRedBlackTreeNode* InsertImpl(IntrusiveRedBlackTreeNode* node) {
382 return RB_INSERT(IntrusiveRedBlackTreeRootWithCompare, 371 return RB_INSERT(&impl.root, node, CompareImpl);
383 static_cast<IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root),
384 node);
385 } 372 }
386 373
387 IntrusiveRedBlackTreeNode* FindImpl(const IntrusiveRedBlackTreeNode* node) const { 374 IntrusiveRedBlackTreeNode* FindImpl(const IntrusiveRedBlackTreeNode* node) const {
388 return RB_FIND( 375 return RB_FIND(const_cast<ImplType::RootType*>(&impl.root),
389 IntrusiveRedBlackTreeRootWithCompare, 376 const_cast<IntrusiveRedBlackTreeNode*>(node), CompareImpl);
390 const_cast<IntrusiveRedBlackTreeRootWithCompare*>(
391 static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)),
392 const_cast<IntrusiveRedBlackTreeNode*>(node));
393 } 377 }
394 378
395 IntrusiveRedBlackTreeNode* NFindImpl(const IntrusiveRedBlackTreeNode* node) const { 379 IntrusiveRedBlackTreeNode* NFindImpl(const IntrusiveRedBlackTreeNode* node) const {
396 return RB_NFIND( 380 return RB_NFIND(const_cast<ImplType::RootType*>(&impl.root),
397 IntrusiveRedBlackTreeRootWithCompare, 381 const_cast<IntrusiveRedBlackTreeNode*>(node), CompareImpl);
398 const_cast<IntrusiveRedBlackTreeRootWithCompare*>(
399 static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)),
400 const_cast<IntrusiveRedBlackTreeNode*>(node));
401 } 382 }
402 383
403 IntrusiveRedBlackTreeNode* FindLightImpl(const_light_pointer lelm) const { 384 IntrusiveRedBlackTreeNode* FindLightImpl(const_light_pointer lelm) const {
404 return RB_FIND_LIGHT( 385 return RB_FIND_LIGHT(const_cast<ImplType::RootType*>(&impl.root),
405 IntrusiveRedBlackTreeRootWithCompare, 386 static_cast<const void*>(lelm), LightCompareImpl);
406 const_cast<IntrusiveRedBlackTreeRootWithCompare*>(
407 static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)),
408 static_cast<const void*>(lelm));
409 } 387 }
410 388
411 IntrusiveRedBlackTreeNode* NFindLightImpl(const_light_pointer lelm) const { 389 IntrusiveRedBlackTreeNode* NFindLightImpl(const_light_pointer lelm) const {
412 return RB_NFIND_LIGHT( 390 return RB_NFIND_LIGHT(const_cast<ImplType::RootType*>(&impl.root),
413 IntrusiveRedBlackTreeRootWithCompare, 391 static_cast<const void*>(lelm), LightCompareImpl);
414 const_cast<IntrusiveRedBlackTreeRootWithCompare*>(
415 static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)),
416 static_cast<const void*>(lelm));
417 } 392 }
418 393
419public: 394public:
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
index a6b636646..3da49e422 100644
--- a/src/common/tree.h
+++ b/src/common/tree.h
@@ -27,33 +27,10 @@
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */ 28 */
29 29
30#ifndef _SYS_TREE_H_ 30#pragma once
31#define _SYS_TREE_H_
32
33/* FreeBSD <sys/cdefs.h> has a lot of defines we don't really want. */
34/* tree.h only actually uses __inline and __unused, so we'll just define those. */
35
36/* #include <sys/cdefs.h> */
37
38#ifndef __inline
39#define __inline inline
40#endif
41 31
42/* 32/*
43 * This file defines data structures for different types of trees: 33 * This file defines data structures for red-black trees.
44 * splay trees and red-black trees.
45 *
46 * A splay tree is a self-organizing data structure. Every operation
47 * on the tree causes a splay to happen. The splay moves the requested
48 * node to the root of the tree and partly rebalances it.
49 *
50 * This has the benefit that request locality causes faster lookups as
51 * the requested nodes move to the top of the tree. On the other hand,
52 * every lookup causes memory writes.
53 *
54 * The Balance Theorem bounds the total access time for m operations
55 * and n inserts on an initially empty tree as O((m + n)lg n). The
56 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
57 * 34 *
58 * A red-black tree is a binary search tree with the node color as an 35 * A red-black tree is a binary search tree with the node color as an
59 * extra attribute. It fulfills a set of conditions: 36 * extra attribute. It fulfills a set of conditions:
@@ -66,757 +43,632 @@
66 * The maximum height of a red-black tree is 2lg (n+1). 43 * The maximum height of a red-black tree is 2lg (n+1).
67 */ 44 */
68 45
69#define SPLAY_HEAD(name, type) \ 46namespace Common {
70 struct name { \ 47template <typename T>
71 struct type* sph_root; /* root of the tree */ \ 48class RBHead {
72 } 49public:
73 50 [[nodiscard]] T* Root() {
74#define SPLAY_INITIALIZER(root) \ 51 return rbh_root;
75 { NULL } 52 }
76 53
77#define SPLAY_INIT(root) \ 54 [[nodiscard]] const T* Root() const {
78 do { \ 55 return rbh_root;
79 (root)->sph_root = NULL; \ 56 }
80 } while (/*CONSTCOND*/ 0) 57
81 58 void SetRoot(T* root) {
82#define SPLAY_ENTRY(type) \ 59 rbh_root = root;
83 struct { \ 60 }
84 struct type* spe_left; /* left element */ \ 61
85 struct type* spe_right; /* right element */ \ 62 [[nodiscard]] bool IsEmpty() const {
86 } 63 return Root() == nullptr;
87 64 }
88#define SPLAY_LEFT(elm, field) (elm)->field.spe_left 65
89#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 66private:
90#define SPLAY_ROOT(head) (head)->sph_root 67 T* rbh_root = nullptr;
91#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 68};
92 69
93/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 70enum class EntryColor {
94#define SPLAY_ROTATE_RIGHT(head, tmp, field) \ 71 Black,
95 do { \ 72 Red,
96 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 73};
97 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 74
98 (head)->sph_root = tmp; \ 75template <typename T>
99 } while (/*CONSTCOND*/ 0) 76class RBEntry {
100 77public:
101#define SPLAY_ROTATE_LEFT(head, tmp, field) \ 78 [[nodiscard]] T* Left() {
102 do { \ 79 return rbe_left;
103 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 80 }
104 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 81
105 (head)->sph_root = tmp; \ 82 [[nodiscard]] const T* Left() const {
106 } while (/*CONSTCOND*/ 0) 83 return rbe_left;
107 84 }
108#define SPLAY_LINKLEFT(head, tmp, field) \ 85
109 do { \ 86 void SetLeft(T* left) {
110 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 87 rbe_left = left;
111 tmp = (head)->sph_root; \ 88 }
112 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 89
113 } while (/*CONSTCOND*/ 0) 90 [[nodiscard]] T* Right() {
114 91 return rbe_right;
115#define SPLAY_LINKRIGHT(head, tmp, field) \ 92 }
116 do { \ 93
117 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 94 [[nodiscard]] const T* Right() const {
118 tmp = (head)->sph_root; \ 95 return rbe_right;
119 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 96 }
120 } while (/*CONSTCOND*/ 0) 97
121 98 void SetRight(T* right) {
122#define SPLAY_ASSEMBLE(head, node, left, right, field) \ 99 rbe_right = right;
123 do { \ 100 }
124 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 101
125 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field); \ 102 [[nodiscard]] T* Parent() {
126 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 103 return rbe_parent;
127 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 104 }
128 } while (/*CONSTCOND*/ 0) 105
129 106 [[nodiscard]] const T* Parent() const {
130/* Generates prototypes and inline functions */ 107 return rbe_parent;
131 108 }
132#define SPLAY_PROTOTYPE(name, type, field, cmp) \ 109
133 void name##_SPLAY(struct name*, struct type*); \ 110 void SetParent(T* parent) {
134 void name##_SPLAY_MINMAX(struct name*, int); \ 111 rbe_parent = parent;
135 struct type* name##_SPLAY_INSERT(struct name*, struct type*); \ 112 }
136 struct type* name##_SPLAY_REMOVE(struct name*, struct type*); \ 113
137 \ 114 [[nodiscard]] bool IsBlack() const {
138 /* Finds the node with the same key as elm */ \ 115 return rbe_color == EntryColor::Black;
139 static __inline struct type* name##_SPLAY_FIND(struct name* head, struct type* elm) { \ 116 }
140 if (SPLAY_EMPTY(head)) \ 117
141 return (NULL); \ 118 [[nodiscard]] bool IsRed() const {
142 name##_SPLAY(head, elm); \ 119 return rbe_color == EntryColor::Red;
143 if ((cmp)(elm, (head)->sph_root) == 0) \ 120 }
144 return (head->sph_root); \ 121
145 return (NULL); \ 122 [[nodiscard]] EntryColor Color() const {
146 } \ 123 return rbe_color;
147 \ 124 }
148 static __inline struct type* name##_SPLAY_NEXT(struct name* head, struct type* elm) { \ 125
149 name##_SPLAY(head, elm); \ 126 void SetColor(EntryColor color) {
150 if (SPLAY_RIGHT(elm, field) != NULL) { \ 127 rbe_color = color;
151 elm = SPLAY_RIGHT(elm, field); \ 128 }
152 while (SPLAY_LEFT(elm, field) != NULL) { \ 129
153 elm = SPLAY_LEFT(elm, field); \ 130private:
154 } \ 131 T* rbe_left = nullptr;
155 } else \ 132 T* rbe_right = nullptr;
156 elm = NULL; \ 133 T* rbe_parent = nullptr;
157 return (elm); \ 134 EntryColor rbe_color{};
158 } \ 135};
159 \ 136
160 static __inline struct type* name##_SPLAY_MIN_MAX(struct name* head, int val) { \ 137template <typename Node>
161 name##_SPLAY_MINMAX(head, val); \ 138[[nodiscard]] RBEntry<Node>& RB_ENTRY(Node* node) {
162 return (SPLAY_ROOT(head)); \ 139 return node->GetEntry();
163 } 140}
164 141
165/* Main splay operation. 142template <typename Node>
166 * Moves node close to the key of elm to top 143[[nodiscard]] const RBEntry<Node>& RB_ENTRY(const Node* node) {
167 */ 144 return node->GetEntry();
168#define SPLAY_GENERATE(name, type, field, cmp) \ 145}
169 struct type* name##_SPLAY_INSERT(struct name* head, struct type* elm) { \ 146
170 if (SPLAY_EMPTY(head)) { \ 147template <typename Node>
171 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 148[[nodiscard]] Node* RB_PARENT(Node* node) {
172 } else { \ 149 return RB_ENTRY(node).Parent();
173 int __comp; \ 150}
174 name##_SPLAY(head, elm); \ 151
175 __comp = (cmp)(elm, (head)->sph_root); \ 152template <typename Node>
176 if (__comp < 0) { \ 153[[nodiscard]] const Node* RB_PARENT(const Node* node) {
177 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field); \ 154 return RB_ENTRY(node).Parent();
178 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 155}
179 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 156
180 } else if (__comp > 0) { \ 157template <typename Node>
181 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field); \ 158void RB_SET_PARENT(Node* node, Node* parent) {
182 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 159 return RB_ENTRY(node).SetParent(parent);
183 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 160}
184 } else \ 161
185 return ((head)->sph_root); \ 162template <typename Node>
186 } \ 163[[nodiscard]] Node* RB_LEFT(Node* node) {
187 (head)->sph_root = (elm); \ 164 return RB_ENTRY(node).Left();
188 return (NULL); \ 165}
189 } \ 166
190 \ 167template <typename Node>
191 struct type* name##_SPLAY_REMOVE(struct name* head, struct type* elm) { \ 168[[nodiscard]] const Node* RB_LEFT(const Node* node) {
192 struct type* __tmp; \ 169 return RB_ENTRY(node).Left();
193 if (SPLAY_EMPTY(head)) \ 170}
194 return (NULL); \ 171
195 name##_SPLAY(head, elm); \ 172template <typename Node>
196 if ((cmp)(elm, (head)->sph_root) == 0) { \ 173void RB_SET_LEFT(Node* node, Node* left) {
197 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 174 return RB_ENTRY(node).SetLeft(left);
198 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 175}
199 } else { \ 176
200 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 177template <typename Node>
201 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 178[[nodiscard]] Node* RB_RIGHT(Node* node) {
202 name##_SPLAY(head, elm); \ 179 return RB_ENTRY(node).Right();
203 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 180}
204 } \ 181
205 return (elm); \ 182template <typename Node>
206 } \ 183[[nodiscard]] const Node* RB_RIGHT(const Node* node) {
207 return (NULL); \ 184 return RB_ENTRY(node).Right();
208 } \ 185}
209 \ 186
210 void name##_SPLAY(struct name* head, struct type* elm) { \ 187template <typename Node>
211 struct type __node, *__left, *__right, *__tmp; \ 188void RB_SET_RIGHT(Node* node, Node* right) {
212 int __comp; \ 189 return RB_ENTRY(node).SetRight(right);
213 \ 190}
214 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ 191
215 __left = __right = &__node; \ 192template <typename Node>
216 \ 193[[nodiscard]] bool RB_IS_BLACK(const Node* node) {
217 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 194 return RB_ENTRY(node).IsBlack();
218 if (__comp < 0) { \ 195}
219 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 196
220 if (__tmp == NULL) \ 197template <typename Node>
221 break; \ 198[[nodiscard]] bool RB_IS_RED(const Node* node) {
222 if ((cmp)(elm, __tmp) < 0) { \ 199 return RB_ENTRY(node).IsRed();
223 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 200}
224 if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ 201
225 break; \ 202template <typename Node>
226 } \ 203[[nodiscard]] EntryColor RB_COLOR(const Node* node) {
227 SPLAY_LINKLEFT(head, __right, field); \ 204 return RB_ENTRY(node).Color();
228 } else if (__comp > 0) { \ 205}
229 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 206
230 if (__tmp == NULL) \ 207template <typename Node>
231 break; \ 208void RB_SET_COLOR(Node* node, EntryColor color) {
232 if ((cmp)(elm, __tmp) > 0) { \ 209 return RB_ENTRY(node).SetColor(color);
233 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 210}
234 if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ 211
235 break; \ 212template <typename Node>
236 } \ 213void RB_SET(Node* node, Node* parent) {
237 SPLAY_LINKRIGHT(head, __left, field); \ 214 auto& entry = RB_ENTRY(node);
238 } \ 215 entry.SetParent(parent);
239 } \ 216 entry.SetLeft(nullptr);
240 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 217 entry.SetRight(nullptr);
241 } \ 218 entry.SetColor(EntryColor::Red);
242 \ 219}
243 /* Splay with either the minimum or the maximum element \ 220
244 * Used to find minimum or maximum element in tree. \ 221template <typename Node>
245 */ \ 222void RB_SET_BLACKRED(Node* black, Node* red) {
246 void name##_SPLAY_MINMAX(struct name* head, int __comp) { \ 223 RB_SET_COLOR(black, EntryColor::Black);
247 struct type __node, *__left, *__right, *__tmp; \ 224 RB_SET_COLOR(red, EntryColor::Red);
248 \ 225}
249 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ 226
250 __left = __right = &__node; \ 227template <typename Node>
251 \ 228void RB_ROTATE_LEFT(RBHead<Node>* head, Node* elm, Node*& tmp) {
252 while (1) { \ 229 tmp = RB_RIGHT(elm);
253 if (__comp < 0) { \ 230 RB_SET_RIGHT(elm, RB_LEFT(tmp));
254 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 231 if (RB_RIGHT(elm) != nullptr) {
255 if (__tmp == NULL) \ 232 RB_SET_PARENT(RB_LEFT(tmp), elm);
256 break; \ 233 }
257 if (__comp < 0) { \ 234
258 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 235 RB_SET_PARENT(tmp, RB_PARENT(elm));
259 if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ 236 if (RB_PARENT(tmp) != nullptr) {
260 break; \ 237 if (elm == RB_LEFT(RB_PARENT(elm))) {
261 } \ 238 RB_SET_LEFT(RB_PARENT(elm), tmp);
262 SPLAY_LINKLEFT(head, __right, field); \ 239 } else {
263 } else if (__comp > 0) { \ 240 RB_SET_RIGHT(RB_PARENT(elm), tmp);
264 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 241 }
265 if (__tmp == NULL) \ 242 } else {
266 break; \ 243 head->SetRoot(tmp);
267 if (__comp > 0) { \ 244 }
268 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 245
269 if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ 246 RB_SET_LEFT(tmp, elm);
270 break; \ 247 RB_SET_PARENT(elm, tmp);
271 } \ 248}
272 SPLAY_LINKRIGHT(head, __left, field); \ 249
273 } \ 250template <typename Node>
274 } \ 251void RB_ROTATE_RIGHT(RBHead<Node>* head, Node* elm, Node*& tmp) {
275 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 252 tmp = RB_LEFT(elm);
276 } 253 RB_SET_LEFT(elm, RB_RIGHT(tmp));
277 254 if (RB_LEFT(elm) != nullptr) {
278#define SPLAY_NEGINF -1 255 RB_SET_PARENT(RB_RIGHT(tmp), elm);
279#define SPLAY_INF 1 256 }
280 257
281#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 258 RB_SET_PARENT(tmp, RB_PARENT(elm));
282#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 259 if (RB_PARENT(tmp) != nullptr) {
283#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 260 if (elm == RB_LEFT(RB_PARENT(elm))) {
284#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 261 RB_SET_LEFT(RB_PARENT(elm), tmp);
285#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 262 } else {
286#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 263 RB_SET_RIGHT(RB_PARENT(elm), tmp);
287 264 }
288#define SPLAY_FOREACH(x, name, head) \ 265 } else {
289 for ((x) = SPLAY_MIN(name, head); (x) != NULL; (x) = SPLAY_NEXT(name, head, x)) 266 head->SetRoot(tmp);
290 267 }
291/* Macros that define a red-black tree */ 268
292#define RB_HEAD(name, type) \ 269 RB_SET_RIGHT(tmp, elm);
293 struct name { \ 270 RB_SET_PARENT(elm, tmp);
294 struct type* rbh_root; /* root of the tree */ \ 271}
295 } 272
296 273template <typename Node>
297#define RB_INITIALIZER(root) \ 274void RB_INSERT_COLOR(RBHead<Node>* head, Node* elm) {
298 { NULL } 275 Node* parent = nullptr;
299 276 Node* tmp = nullptr;
300#define RB_INIT(root) \ 277
301 do { \ 278 while ((parent = RB_PARENT(elm)) != nullptr && RB_IS_RED(parent)) {
302 (root)->rbh_root = NULL; \ 279 Node* gparent = RB_PARENT(parent);
303 } while (/*CONSTCOND*/ 0) 280 if (parent == RB_LEFT(gparent)) {
304 281 tmp = RB_RIGHT(gparent);
305#define RB_BLACK 0 282 if (tmp && RB_IS_RED(tmp)) {
306#define RB_RED 1 283 RB_SET_COLOR(tmp, EntryColor::Black);
307#define RB_ENTRY(type) \ 284 RB_SET_BLACKRED(parent, gparent);
308 struct { \ 285 elm = gparent;
309 struct type* rbe_left; /* left element */ \ 286 continue;
310 struct type* rbe_right; /* right element */ \ 287 }
311 struct type* rbe_parent; /* parent element */ \ 288
312 int rbe_color; /* node color */ \ 289 if (RB_RIGHT(parent) == elm) {
313 } 290 RB_ROTATE_LEFT(head, parent, tmp);
314 291 tmp = parent;
315#define RB_LEFT(elm, field) (elm)->field.rbe_left 292 parent = elm;
316#define RB_RIGHT(elm, field) (elm)->field.rbe_right 293 elm = tmp;
317#define RB_PARENT(elm, field) (elm)->field.rbe_parent 294 }
318#define RB_COLOR(elm, field) (elm)->field.rbe_color 295
319#define RB_ROOT(head) (head)->rbh_root 296 RB_SET_BLACKRED(parent, gparent);
320#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 297 RB_ROTATE_RIGHT(head, gparent, tmp);
321 298 } else {
322#define RB_SET(elm, parent, field) \ 299 tmp = RB_LEFT(gparent);
323 do { \ 300 if (tmp && RB_IS_RED(tmp)) {
324 RB_PARENT(elm, field) = parent; \ 301 RB_SET_COLOR(tmp, EntryColor::Black);
325 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 302 RB_SET_BLACKRED(parent, gparent);
326 RB_COLOR(elm, field) = RB_RED; \ 303 elm = gparent;
327 } while (/*CONSTCOND*/ 0) 304 continue;
328 305 }
329#define RB_SET_BLACKRED(black, red, field) \ 306
330 do { \ 307 if (RB_LEFT(parent) == elm) {
331 RB_COLOR(black, field) = RB_BLACK; \ 308 RB_ROTATE_RIGHT(head, parent, tmp);
332 RB_COLOR(red, field) = RB_RED; \ 309 tmp = parent;
333 } while (/*CONSTCOND*/ 0) 310 parent = elm;
334 311 elm = tmp;
335#ifndef RB_AUGMENT 312 }
336#define RB_AUGMENT(x) \ 313
337 do { \ 314 RB_SET_BLACKRED(parent, gparent);
338 } while (0) 315 RB_ROTATE_LEFT(head, gparent, tmp);
339#endif 316 }
340 317 }
341#define RB_ROTATE_LEFT(head, elm, tmp, field) \ 318
342 do { \ 319 RB_SET_COLOR(head->Root(), EntryColor::Black);
343 (tmp) = RB_RIGHT(elm, field); \ 320}
344 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 321
345 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 322template <typename Node>
346 } \ 323void RB_REMOVE_COLOR(RBHead<Node>* head, Node* parent, Node* elm) {
347 RB_AUGMENT(elm); \ 324 Node* tmp;
348 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 325 while ((elm == nullptr || RB_IS_BLACK(elm)) && elm != head->Root()) {
349 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 326 if (RB_LEFT(parent) == elm) {
350 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 327 tmp = RB_RIGHT(parent);
351 else \ 328 if (RB_IS_RED(tmp)) {
352 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 329 RB_SET_BLACKRED(tmp, parent);
353 } else \ 330 RB_ROTATE_LEFT(head, parent, tmp);
354 (head)->rbh_root = (tmp); \ 331 tmp = RB_RIGHT(parent);
355 RB_LEFT(tmp, field) = (elm); \ 332 }
356 RB_PARENT(elm, field) = (tmp); \ 333
357 RB_AUGMENT(tmp); \ 334 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) &&
358 if ((RB_PARENT(tmp, field))) \ 335 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) {
359 RB_AUGMENT(RB_PARENT(tmp, field)); \ 336 RB_SET_COLOR(tmp, EntryColor::Red);
360 } while (/*CONSTCOND*/ 0) 337 elm = parent;
361 338 parent = RB_PARENT(elm);
362#define RB_ROTATE_RIGHT(head, elm, tmp, field) \ 339 } else {
363 do { \ 340 if (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp))) {
364 (tmp) = RB_LEFT(elm, field); \ 341 Node* oleft;
365 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 342 if ((oleft = RB_LEFT(tmp)) != nullptr) {
366 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 343 RB_SET_COLOR(oleft, EntryColor::Black);
367 } \ 344 }
368 RB_AUGMENT(elm); \ 345
369 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 346 RB_SET_COLOR(tmp, EntryColor::Red);
370 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 347 RB_ROTATE_RIGHT(head, tmp, oleft);
371 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 348 tmp = RB_RIGHT(parent);
372 else \ 349 }
373 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 350
374 } else \ 351 RB_SET_COLOR(tmp, RB_COLOR(parent));
375 (head)->rbh_root = (tmp); \ 352 RB_SET_COLOR(parent, EntryColor::Black);
376 RB_RIGHT(tmp, field) = (elm); \ 353 if (RB_RIGHT(tmp)) {
377 RB_PARENT(elm, field) = (tmp); \ 354 RB_SET_COLOR(RB_RIGHT(tmp), EntryColor::Black);
378 RB_AUGMENT(tmp); \ 355 }
379 if ((RB_PARENT(tmp, field))) \ 356
380 RB_AUGMENT(RB_PARENT(tmp, field)); \ 357 RB_ROTATE_LEFT(head, parent, tmp);
381 } while (/*CONSTCOND*/ 0) 358 elm = head->Root();
382 359 break;
383/* Generates prototypes and inline functions */ 360 }
384#define RB_PROTOTYPE(name, type, field, cmp) RB_PROTOTYPE_INTERNAL(name, type, field, cmp, ) 361 } else {
385#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 362 tmp = RB_LEFT(parent);
386 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, static) 363 if (RB_IS_RED(tmp)) {
387#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 364 RB_SET_BLACKRED(tmp, parent);
388 RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ 365 RB_ROTATE_RIGHT(head, parent, tmp);
389 RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ 366 tmp = RB_LEFT(parent);
390 RB_PROTOTYPE_INSERT(name, type, attr); \ 367 }
391 RB_PROTOTYPE_REMOVE(name, type, attr); \ 368
392 RB_PROTOTYPE_FIND(name, type, attr); \ 369 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) &&
393 RB_PROTOTYPE_NFIND(name, type, attr); \ 370 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) {
394 RB_PROTOTYPE_FIND_LIGHT(name, type, attr); \ 371 RB_SET_COLOR(tmp, EntryColor::Red);
395 RB_PROTOTYPE_NFIND_LIGHT(name, type, attr); \ 372 elm = parent;
396 RB_PROTOTYPE_NEXT(name, type, attr); \ 373 parent = RB_PARENT(elm);
397 RB_PROTOTYPE_PREV(name, type, attr); \ 374 } else {
398 RB_PROTOTYPE_MINMAX(name, type, attr); 375 if (RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) {
399#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ 376 Node* oright;
400 attr void name##_RB_INSERT_COLOR(struct name*, struct type*) 377 if ((oright = RB_RIGHT(tmp)) != nullptr) {
401#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ 378 RB_SET_COLOR(oright, EntryColor::Black);
402 attr void name##_RB_REMOVE_COLOR(struct name*, struct type*, struct type*) 379 }
403#define RB_PROTOTYPE_REMOVE(name, type, attr) \ 380
404 attr struct type* name##_RB_REMOVE(struct name*, struct type*) 381 RB_SET_COLOR(tmp, EntryColor::Red);
405#define RB_PROTOTYPE_INSERT(name, type, attr) \ 382 RB_ROTATE_LEFT(head, tmp, oright);
406 attr struct type* name##_RB_INSERT(struct name*, struct type*) 383 tmp = RB_LEFT(parent);
407#define RB_PROTOTYPE_FIND(name, type, attr) \ 384 }
408 attr struct type* name##_RB_FIND(struct name*, struct type*) 385
409#define RB_PROTOTYPE_NFIND(name, type, attr) \ 386 RB_SET_COLOR(tmp, RB_COLOR(parent));
410 attr struct type* name##_RB_NFIND(struct name*, struct type*) 387 RB_SET_COLOR(parent, EntryColor::Black);
411#define RB_PROTOTYPE_FIND_LIGHT(name, type, attr) \ 388
412 attr struct type* name##_RB_FIND_LIGHT(struct name*, const void*) 389 if (RB_LEFT(tmp)) {
413#define RB_PROTOTYPE_NFIND_LIGHT(name, type, attr) \ 390 RB_SET_COLOR(RB_LEFT(tmp), EntryColor::Black);
414 attr struct type* name##_RB_NFIND_LIGHT(struct name*, const void*) 391 }
415#define RB_PROTOTYPE_NEXT(name, type, attr) attr struct type* name##_RB_NEXT(struct type*) 392
416#define RB_PROTOTYPE_PREV(name, type, attr) attr struct type* name##_RB_PREV(struct type*) 393 RB_ROTATE_RIGHT(head, parent, tmp);
417#define RB_PROTOTYPE_MINMAX(name, type, attr) attr struct type* name##_RB_MINMAX(struct name*, int) 394 elm = head->Root();
418 395 break;
419/* Main rb operation. 396 }
420 * Moves node close to the key of elm to top 397 }
421 */ 398 }
422#define RB_GENERATE_WITHOUT_COMPARE(name, type, field) \ 399
423 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, ) 400 if (elm) {
424#define RB_GENERATE_WITHOUT_COMPARE_STATIC(name, type, field) \ 401 RB_SET_COLOR(elm, EntryColor::Black);
425 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, static) 402 }
426#define RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, attr) \ 403}
427 RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 404
428 RB_GENERATE_REMOVE(name, type, field, attr) \ 405template <typename Node>
429 RB_GENERATE_NEXT(name, type, field, attr) \ 406Node* RB_REMOVE(RBHead<Node>* head, Node* elm) {
430 RB_GENERATE_PREV(name, type, field, attr) \ 407 Node* child = nullptr;
431 RB_GENERATE_MINMAX(name, type, field, attr) 408 Node* parent = nullptr;
432 409 Node* old = elm;
433#define RB_GENERATE_WITH_COMPARE(name, type, field, cmp, lcmp) \ 410 EntryColor color{};
434 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, ) 411
435#define RB_GENERATE_WITH_COMPARE_STATIC(name, type, field, cmp, lcmp) \ 412 const auto finalize = [&] {
436 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, static) 413 if (color == EntryColor::Black) {
437#define RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, attr) \ 414 RB_REMOVE_COLOR(head, parent, child);
438 RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 415 }
439 RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 416
440 RB_GENERATE_FIND(name, type, field, cmp, attr) \ 417 return old;
441 RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 418 };
442 RB_GENERATE_FIND_LIGHT(name, type, field, lcmp, attr) \ 419
443 RB_GENERATE_NFIND_LIGHT(name, type, field, lcmp, attr) 420 if (RB_LEFT(elm) == nullptr) {
444 421 child = RB_RIGHT(elm);
445#define RB_GENERATE_ALL(name, type, field, cmp) RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, ) 422 } else if (RB_RIGHT(elm) == nullptr) {
446#define RB_GENERATE_ALL_STATIC(name, type, field, cmp) \ 423 child = RB_LEFT(elm);
447 RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, static) 424 } else {
448#define RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, attr) \ 425 Node* left;
449 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, attr) \ 426 elm = RB_RIGHT(elm);
450 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, attr) 427 while ((left = RB_LEFT(elm)) != nullptr) {
451 428 elm = left;
452#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 429 }
453 attr void name##_RB_INSERT_COLOR(struct name* head, struct type* elm) { \ 430
454 struct type *parent, *gparent, *tmp; \ 431 child = RB_RIGHT(elm);
455 while ((parent = RB_PARENT(elm, field)) != NULL && RB_COLOR(parent, field) == RB_RED) { \ 432 parent = RB_PARENT(elm);
456 gparent = RB_PARENT(parent, field); \ 433 color = RB_COLOR(elm);
457 if (parent == RB_LEFT(gparent, field)) { \ 434
458 tmp = RB_RIGHT(gparent, field); \ 435 if (child) {
459 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 436 RB_SET_PARENT(child, parent);
460 RB_COLOR(tmp, field) = RB_BLACK; \ 437 }
461 RB_SET_BLACKRED(parent, gparent, field); \ 438 if (parent) {
462 elm = gparent; \ 439 if (RB_LEFT(parent) == elm) {
463 continue; \ 440 RB_SET_LEFT(parent, child);
464 } \ 441 } else {
465 if (RB_RIGHT(parent, field) == elm) { \ 442 RB_SET_RIGHT(parent, child);
466 RB_ROTATE_LEFT(head, parent, tmp, field); \ 443 }
467 tmp = parent; \ 444 } else {
468 parent = elm; \ 445 head->SetRoot(child);
469 elm = tmp; \ 446 }
470 } \ 447
471 RB_SET_BLACKRED(parent, gparent, field); \ 448 if (RB_PARENT(elm) == old) {
472 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 449 parent = elm;
473 } else { \ 450 }
474 tmp = RB_LEFT(gparent, field); \ 451
475 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 452 elm->SetEntry(old->GetEntry());
476 RB_COLOR(tmp, field) = RB_BLACK; \ 453
477 RB_SET_BLACKRED(parent, gparent, field); \ 454 if (RB_PARENT(old)) {
478 elm = gparent; \ 455 if (RB_LEFT(RB_PARENT(old)) == old) {
479 continue; \ 456 RB_SET_LEFT(RB_PARENT(old), elm);
480 } \ 457 } else {
481 if (RB_LEFT(parent, field) == elm) { \ 458 RB_SET_RIGHT(RB_PARENT(old), elm);
482 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 459 }
483 tmp = parent; \ 460 } else {
484 parent = elm; \ 461 head->SetRoot(elm);
485 elm = tmp; \ 462 }
486 } \ 463 RB_SET_PARENT(RB_LEFT(old), elm);
487 RB_SET_BLACKRED(parent, gparent, field); \ 464 if (RB_RIGHT(old)) {
488 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 465 RB_SET_PARENT(RB_RIGHT(old), elm);
489 } \ 466 }
490 } \ 467 if (parent) {
491 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 468 left = parent;
492 } 469 }
493 470
494#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 471 return finalize();
495 attr void name##_RB_REMOVE_COLOR(struct name* head, struct type* parent, struct type* elm) { \ 472 }
496 struct type* tmp; \ 473
497 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && elm != RB_ROOT(head)) { \ 474 parent = RB_PARENT(elm);
498 if (RB_LEFT(parent, field) == elm) { \ 475 color = RB_COLOR(elm);
499 tmp = RB_RIGHT(parent, field); \ 476
500 if (RB_COLOR(tmp, field) == RB_RED) { \ 477 if (child) {
501 RB_SET_BLACKRED(tmp, parent, field); \ 478 RB_SET_PARENT(child, parent);
502 RB_ROTATE_LEFT(head, parent, tmp, field); \ 479 }
503 tmp = RB_RIGHT(parent, field); \ 480 if (parent) {
504 } \ 481 if (RB_LEFT(parent) == elm) {
505 if ((RB_LEFT(tmp, field) == NULL || \ 482 RB_SET_LEFT(parent, child);
506 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 483 } else {
507 (RB_RIGHT(tmp, field) == NULL || \ 484 RB_SET_RIGHT(parent, child);
508 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 485 }
509 RB_COLOR(tmp, field) = RB_RED; \ 486 } else {
510 elm = parent; \ 487 head->SetRoot(child);
511 parent = RB_PARENT(elm, field); \ 488 }
512 } else { \ 489
513 if (RB_RIGHT(tmp, field) == NULL || \ 490 return finalize();
514 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \ 491}
515 struct type* oleft; \ 492
516 if ((oleft = RB_LEFT(tmp, field)) != NULL) \ 493// Inserts a node into the RB tree
517 RB_COLOR(oleft, field) = RB_BLACK; \ 494template <typename Node, typename CompareFunction>
518 RB_COLOR(tmp, field) = RB_RED; \ 495Node* RB_INSERT(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
519 RB_ROTATE_RIGHT(head, tmp, oleft, field); \ 496 Node* parent = nullptr;
520 tmp = RB_RIGHT(parent, field); \ 497 Node* tmp = head->Root();
521 } \ 498 int comp = 0;
522 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 499
523 RB_COLOR(parent, field) = RB_BLACK; \ 500 while (tmp) {
524 if (RB_RIGHT(tmp, field)) \ 501 parent = tmp;
525 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ 502 comp = cmp(elm, parent);
526 RB_ROTATE_LEFT(head, parent, tmp, field); \ 503 if (comp < 0) {
527 elm = RB_ROOT(head); \ 504 tmp = RB_LEFT(tmp);
528 break; \ 505 } else if (comp > 0) {
529 } \ 506 tmp = RB_RIGHT(tmp);
530 } else { \ 507 } else {
531 tmp = RB_LEFT(parent, field); \ 508 return tmp;
532 if (RB_COLOR(tmp, field) == RB_RED) { \ 509 }
533 RB_SET_BLACKRED(tmp, parent, field); \ 510 }
534 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 511
535 tmp = RB_LEFT(parent, field); \ 512 RB_SET(elm, parent);
536 } \ 513
537 if ((RB_LEFT(tmp, field) == NULL || \ 514 if (parent != nullptr) {
538 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 515 if (comp < 0) {
539 (RB_RIGHT(tmp, field) == NULL || \ 516 RB_SET_LEFT(parent, elm);
540 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 517 } else {
541 RB_COLOR(tmp, field) = RB_RED; \ 518 RB_SET_RIGHT(parent, elm);
542 elm = parent; \ 519 }
543 parent = RB_PARENT(elm, field); \ 520 } else {
544 } else { \ 521 head->SetRoot(elm);
545 if (RB_LEFT(tmp, field) == NULL || \ 522 }
546 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \ 523
547 struct type* oright; \ 524 RB_INSERT_COLOR(head, elm);
548 if ((oright = RB_RIGHT(tmp, field)) != NULL) \ 525 return nullptr;
549 RB_COLOR(oright, field) = RB_BLACK; \ 526}
550 RB_COLOR(tmp, field) = RB_RED; \ 527
551 RB_ROTATE_LEFT(head, tmp, oright, field); \ 528// Finds the node with the same key as elm
552 tmp = RB_LEFT(parent, field); \ 529template <typename Node, typename CompareFunction>
553 } \ 530Node* RB_FIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
554 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 531 Node* tmp = head->Root();
555 RB_COLOR(parent, field) = RB_BLACK; \ 532
556 if (RB_LEFT(tmp, field)) \ 533 while (tmp) {
557 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ 534 const int comp = cmp(elm, tmp);
558 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 535 if (comp < 0) {
559 elm = RB_ROOT(head); \ 536 tmp = RB_LEFT(tmp);
560 break; \ 537 } else if (comp > 0) {
561 } \ 538 tmp = RB_RIGHT(tmp);
562 } \ 539 } else {
563 } \ 540 return tmp;
564 if (elm) \ 541 }
565 RB_COLOR(elm, field) = RB_BLACK; \ 542 }
566 } 543
567 544 return nullptr;
568#define RB_GENERATE_REMOVE(name, type, field, attr) \ 545}
569 attr struct type* name##_RB_REMOVE(struct name* head, struct type* elm) { \ 546
570 struct type *child, *parent, *old = elm; \ 547// Finds the first node greater than or equal to the search key
571 int color; \ 548template <typename Node, typename CompareFunction>
572 if (RB_LEFT(elm, field) == NULL) \ 549Node* RB_NFIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
573 child = RB_RIGHT(elm, field); \ 550 Node* tmp = head->Root();
574 else if (RB_RIGHT(elm, field) == NULL) \ 551 Node* res = nullptr;
575 child = RB_LEFT(elm, field); \ 552
576 else { \ 553 while (tmp) {
577 struct type* left; \ 554 const int comp = cmp(elm, tmp);
578 elm = RB_RIGHT(elm, field); \ 555 if (comp < 0) {
579 while ((left = RB_LEFT(elm, field)) != NULL) \ 556 res = tmp;
580 elm = left; \ 557 tmp = RB_LEFT(tmp);
581 child = RB_RIGHT(elm, field); \ 558 } else if (comp > 0) {
582 parent = RB_PARENT(elm, field); \ 559 tmp = RB_RIGHT(tmp);
583 color = RB_COLOR(elm, field); \ 560 } else {
584 if (child) \ 561 return tmp;
585 RB_PARENT(child, field) = parent; \ 562 }
586 if (parent) { \ 563 }
587 if (RB_LEFT(parent, field) == elm) \ 564
588 RB_LEFT(parent, field) = child; \ 565 return res;
589 else \ 566}
590 RB_RIGHT(parent, field) = child; \ 567
591 RB_AUGMENT(parent); \ 568// Finds the node with the same key as lelm
592 } else \ 569template <typename Node, typename CompareFunction>
593 RB_ROOT(head) = child; \ 570Node* RB_FIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) {
594 if (RB_PARENT(elm, field) == old) \ 571 Node* tmp = head->Root();
595 parent = elm; \ 572
596 (elm)->field = (old)->field; \ 573 while (tmp) {
597 if (RB_PARENT(old, field)) { \ 574 const int comp = lcmp(lelm, tmp);
598 if (RB_LEFT(RB_PARENT(old, field), field) == old) \ 575 if (comp < 0) {
599 RB_LEFT(RB_PARENT(old, field), field) = elm; \ 576 tmp = RB_LEFT(tmp);
600 else \ 577 } else if (comp > 0) {
601 RB_RIGHT(RB_PARENT(old, field), field) = elm; \ 578 tmp = RB_RIGHT(tmp);
602 RB_AUGMENT(RB_PARENT(old, field)); \ 579 } else {
603 } else \ 580 return tmp;
604 RB_ROOT(head) = elm; \ 581 }
605 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 582 }
606 if (RB_RIGHT(old, field)) \ 583
607 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 584 return nullptr;
608 if (parent) { \ 585}
609 left = parent; \ 586
610 do { \ 587// Finds the first node greater than or equal to the search key
611 RB_AUGMENT(left); \ 588template <typename Node, typename CompareFunction>
612 } while ((left = RB_PARENT(left, field)) != NULL); \ 589Node* RB_NFIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) {
613 } \ 590 Node* tmp = head->Root();
614 goto color; \ 591 Node* res = nullptr;
615 } \ 592
616 parent = RB_PARENT(elm, field); \ 593 while (tmp) {
617 color = RB_COLOR(elm, field); \ 594 const int comp = lcmp(lelm, tmp);
618 if (child) \ 595 if (comp < 0) {
619 RB_PARENT(child, field) = parent; \ 596 res = tmp;
620 if (parent) { \ 597 tmp = RB_LEFT(tmp);
621 if (RB_LEFT(parent, field) == elm) \ 598 } else if (comp > 0) {
622 RB_LEFT(parent, field) = child; \ 599 tmp = RB_RIGHT(tmp);
623 else \ 600 } else {
624 RB_RIGHT(parent, field) = child; \ 601 return tmp;
625 RB_AUGMENT(parent); \ 602 }
626 } else \ 603 }
627 RB_ROOT(head) = child; \ 604
628 color: \ 605 return res;
629 if (color == RB_BLACK) \ 606}
630 name##_RB_REMOVE_COLOR(head, parent, child); \ 607
631 return (old); \ 608template <typename Node>
632 } 609Node* RB_NEXT(Node* elm) {
633 610 if (RB_RIGHT(elm)) {
634#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 611 elm = RB_RIGHT(elm);
635 /* Inserts a node into the RB tree */ \ 612 while (RB_LEFT(elm)) {
636 attr struct type* name##_RB_INSERT(struct name* head, struct type* elm) { \ 613 elm = RB_LEFT(elm);
637 struct type* tmp; \ 614 }
638 struct type* parent = NULL; \ 615 } else {
639 int comp = 0; \ 616 if (RB_PARENT(elm) && (elm == RB_LEFT(RB_PARENT(elm)))) {
640 tmp = RB_ROOT(head); \ 617 elm = RB_PARENT(elm);
641 while (tmp) { \ 618 } else {
642 parent = tmp; \ 619 while (RB_PARENT(elm) && (elm == RB_RIGHT(RB_PARENT(elm)))) {
643 comp = (cmp)(elm, parent); \ 620 elm = RB_PARENT(elm);
644 if (comp < 0) \ 621 }
645 tmp = RB_LEFT(tmp, field); \ 622 elm = RB_PARENT(elm);
646 else if (comp > 0) \ 623 }
647 tmp = RB_RIGHT(tmp, field); \ 624 }
648 else \ 625 return elm;
649 return (tmp); \ 626}
650 } \ 627
651 RB_SET(elm, parent, field); \ 628template <typename Node>
652 if (parent != NULL) { \ 629Node* RB_PREV(Node* elm) {
653 if (comp < 0) \ 630 if (RB_LEFT(elm)) {
654 RB_LEFT(parent, field) = elm; \ 631 elm = RB_LEFT(elm);
655 else \ 632 while (RB_RIGHT(elm)) {
656 RB_RIGHT(parent, field) = elm; \ 633 elm = RB_RIGHT(elm);
657 RB_AUGMENT(parent); \ 634 }
658 } else \ 635 } else {
659 RB_ROOT(head) = elm; \ 636 if (RB_PARENT(elm) && (elm == RB_RIGHT(RB_PARENT(elm)))) {
660 name##_RB_INSERT_COLOR(head, elm); \ 637 elm = RB_PARENT(elm);
661 return (NULL); \ 638 } else {
662 } 639 while (RB_PARENT(elm) && (elm == RB_LEFT(RB_PARENT(elm)))) {
663 640 elm = RB_PARENT(elm);
664#define RB_GENERATE_FIND(name, type, field, cmp, attr) \ 641 }
665 /* Finds the node with the same key as elm */ \ 642 elm = RB_PARENT(elm);
666 attr struct type* name##_RB_FIND(struct name* head, struct type* elm) { \ 643 }
667 struct type* tmp = RB_ROOT(head); \ 644 }
668 int comp; \ 645 return elm;
669 while (tmp) { \ 646}
670 comp = cmp(elm, tmp); \ 647
671 if (comp < 0) \ 648template <typename Node>
672 tmp = RB_LEFT(tmp, field); \ 649Node* RB_MINMAX(RBHead<Node>* head, bool is_min) {
673 else if (comp > 0) \ 650 Node* tmp = head->Root();
674 tmp = RB_RIGHT(tmp, field); \ 651 Node* parent = nullptr;
675 else \ 652
676 return (tmp); \ 653 while (tmp) {
677 } \ 654 parent = tmp;
678 return (NULL); \ 655 if (is_min) {
679 } 656 tmp = RB_LEFT(tmp);
680 657 } else {
681#define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 658 tmp = RB_RIGHT(tmp);
682 /* Finds the first node greater than or equal to the search key */ \ 659 }
683 attr struct type* name##_RB_NFIND(struct name* head, struct type* elm) { \ 660 }
684 struct type* tmp = RB_ROOT(head); \ 661
685 struct type* res = NULL; \ 662 return parent;
686 int comp; \ 663}
687 while (tmp) { \ 664
688 comp = cmp(elm, tmp); \ 665template <typename Node>
689 if (comp < 0) { \ 666Node* RB_MIN(RBHead<Node>* head) {
690 res = tmp; \ 667 return RB_MINMAX(head, true);
691 tmp = RB_LEFT(tmp, field); \ 668}
692 } else if (comp > 0) \ 669
693 tmp = RB_RIGHT(tmp, field); \ 670template <typename Node>
694 else \ 671Node* RB_MAX(RBHead<Node>* head) {
695 return (tmp); \ 672 return RB_MINMAX(head, false);
696 } \ 673}
697 return (res); \ 674} // namespace Common
698 }
699
700#define RB_GENERATE_FIND_LIGHT(name, type, field, lcmp, attr) \
701 /* Finds the node with the same key as elm */ \
702 attr struct type* name##_RB_FIND_LIGHT(struct name* head, const void* lelm) { \
703 struct type* tmp = RB_ROOT(head); \
704 int comp; \
705 while (tmp) { \
706 comp = lcmp(lelm, tmp); \
707 if (comp < 0) \
708 tmp = RB_LEFT(tmp, field); \
709 else if (comp > 0) \
710 tmp = RB_RIGHT(tmp, field); \
711 else \
712 return (tmp); \
713 } \
714 return (NULL); \
715 }
716
717#define RB_GENERATE_NFIND_LIGHT(name, type, field, lcmp, attr) \
718 /* Finds the first node greater than or equal to the search key */ \
719 attr struct type* name##_RB_NFIND_LIGHT(struct name* head, const void* lelm) { \
720 struct type* tmp = RB_ROOT(head); \
721 struct type* res = NULL; \
722 int comp; \
723 while (tmp) { \
724 comp = lcmp(lelm, tmp); \
725 if (comp < 0) { \
726 res = tmp; \
727 tmp = RB_LEFT(tmp, field); \
728 } else if (comp > 0) \
729 tmp = RB_RIGHT(tmp, field); \
730 else \
731 return (tmp); \
732 } \
733 return (res); \
734 }
735
736#define RB_GENERATE_NEXT(name, type, field, attr) \
737 /* ARGSUSED */ \
738 attr struct type* name##_RB_NEXT(struct type* elm) { \
739 if (RB_RIGHT(elm, field)) { \
740 elm = RB_RIGHT(elm, field); \
741 while (RB_LEFT(elm, field)) \
742 elm = RB_LEFT(elm, field); \
743 } else { \
744 if (RB_PARENT(elm, field) && (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
745 elm = RB_PARENT(elm, field); \
746 else { \
747 while (RB_PARENT(elm, field) && (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
748 elm = RB_PARENT(elm, field); \
749 elm = RB_PARENT(elm, field); \
750 } \
751 } \
752 return (elm); \
753 }
754
755#define RB_GENERATE_PREV(name, type, field, attr) \
756 /* ARGSUSED */ \
757 attr struct type* name##_RB_PREV(struct type* elm) { \
758 if (RB_LEFT(elm, field)) { \
759 elm = RB_LEFT(elm, field); \
760 while (RB_RIGHT(elm, field)) \
761 elm = RB_RIGHT(elm, field); \
762 } else { \
763 if (RB_PARENT(elm, field) && (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
764 elm = RB_PARENT(elm, field); \
765 else { \
766 while (RB_PARENT(elm, field) && (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
767 elm = RB_PARENT(elm, field); \
768 elm = RB_PARENT(elm, field); \
769 } \
770 } \
771 return (elm); \
772 }
773
774#define RB_GENERATE_MINMAX(name, type, field, attr) \
775 attr struct type* name##_RB_MINMAX(struct name* head, int val) { \
776 struct type* tmp = RB_ROOT(head); \
777 struct type* parent = NULL; \
778 while (tmp) { \
779 parent = tmp; \
780 if (val < 0) \
781 tmp = RB_LEFT(tmp, field); \
782 else \
783 tmp = RB_RIGHT(tmp, field); \
784 } \
785 return (parent); \
786 }
787
788#define RB_NEGINF -1
789#define RB_INF 1
790
791#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
792#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
793#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
794#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
795#define RB_FIND_LIGHT(name, x, y) name##_RB_FIND_LIGHT(x, y)
796#define RB_NFIND_LIGHT(name, x, y) name##_RB_NFIND_LIGHT(x, y)
797#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
798#define RB_PREV(name, x, y) name##_RB_PREV(y)
799#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
800#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
801
802#define RB_FOREACH(x, name, head) \
803 for ((x) = RB_MIN(name, head); (x) != NULL; (x) = name##_RB_NEXT(x))
804
805#define RB_FOREACH_FROM(x, name, y) \
806 for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); (x) = (y))
807
808#define RB_FOREACH_SAFE(x, name, head, y) \
809 for ((x) = RB_MIN(name, head); ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
810 (x) = (y))
811
812#define RB_FOREACH_REVERSE(x, name, head) \
813 for ((x) = RB_MAX(name, head); (x) != NULL; (x) = name##_RB_PREV(x))
814
815#define RB_FOREACH_REVERSE_FROM(x, name, y) \
816 for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); (x) = (y))
817
818#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
819 for ((x) = RB_MAX(name, head); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
820 (x) = (y))
821
822#endif /* _SYS_TREE_H_ */
diff --git a/src/common/uuid.h b/src/common/uuid.h
index 4ab9a25f0..2e7a18405 100644
--- a/src/common/uuid.h
+++ b/src/common/uuid.h
@@ -14,8 +14,8 @@ constexpr u128 INVALID_UUID{{0, 0}};
14 14
15struct UUID { 15struct UUID {
16 // UUIDs which are 0 are considered invalid! 16 // UUIDs which are 0 are considered invalid!
17 u128 uuid = INVALID_UUID; 17 u128 uuid;
18 constexpr UUID() = default; 18 UUID() = default;
19 constexpr explicit UUID(const u128& id) : uuid{id} {} 19 constexpr explicit UUID(const u128& id) : uuid{id} {}
20 constexpr explicit UUID(const u64 lo, const u64 hi) : uuid{{lo, hi}} {} 20 constexpr explicit UUID(const u64 lo, const u64 hi) : uuid{{lo, hi}} {}
21 21
diff --git a/src/common/x64/native_clock.cpp b/src/common/x64/native_clock.cpp
index eb8a7782f..a65f6b832 100644
--- a/src/common/x64/native_clock.cpp
+++ b/src/common/x64/native_clock.cpp
@@ -2,19 +2,74 @@
2// Licensed under GPLv2 or any later version 2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included. 3// Refer to the license.txt file included.
4 4
5#include <array>
5#include <chrono> 6#include <chrono>
7#include <limits>
6#include <mutex> 8#include <mutex>
7#include <thread> 9#include <thread>
8 10
9#ifdef _MSC_VER 11#ifdef _MSC_VER
10#include <intrin.h> 12#include <intrin.h>
13
14#pragma intrinsic(__umulh)
15#pragma intrinsic(_udiv128)
11#else 16#else
12#include <x86intrin.h> 17#include <x86intrin.h>
13#endif 18#endif
14 19
20#include "common/atomic_ops.h"
15#include "common/uint128.h" 21#include "common/uint128.h"
16#include "common/x64/native_clock.h" 22#include "common/x64/native_clock.h"
17 23
24namespace {
25
26[[nodiscard]] u64 GetFixedPoint64Factor(u64 numerator, u64 divisor) {
27#ifdef __SIZEOF_INT128__
28 const auto base = static_cast<unsigned __int128>(numerator) << 64ULL;
29 return static_cast<u64>(base / divisor);
30#elif defined(_M_X64) || defined(_M_ARM64)
31 std::array<u64, 2> r = {0, numerator};
32 u64 remainder;
33#if _MSC_VER < 1923
34 return udiv128(r[1], r[0], divisor, &remainder);
35#else
36 return _udiv128(r[1], r[0], divisor, &remainder);
37#endif
38#else
39 // This one is bit more inaccurate.
40 return MultiplyAndDivide64(std::numeric_limits<u64>::max(), numerator, divisor);
41#endif
42}
43
44[[nodiscard]] u64 MultiplyHigh(u64 a, u64 b) {
45#ifdef __SIZEOF_INT128__
46 return (static_cast<unsigned __int128>(a) * static_cast<unsigned __int128>(b)) >> 64;
47#elif defined(_M_X64) || defined(_M_ARM64)
48 return __umulh(a, b); // MSVC
49#else
50 // Generic fallback
51 const u64 a_lo = u32(a);
52 const u64 a_hi = a >> 32;
53 const u64 b_lo = u32(b);
54 const u64 b_hi = b >> 32;
55
56 const u64 a_x_b_hi = a_hi * b_hi;
57 const u64 a_x_b_mid = a_hi * b_lo;
58 const u64 b_x_a_mid = b_hi * a_lo;
59 const u64 a_x_b_lo = a_lo * b_lo;
60
61 const u64 carry_bit = (static_cast<u64>(static_cast<u32>(a_x_b_mid)) +
62 static_cast<u64>(static_cast<u32>(b_x_a_mid)) + (a_x_b_lo >> 32)) >>
63 32;
64
65 const u64 multhi = a_x_b_hi + (a_x_b_mid >> 32) + (b_x_a_mid >> 32) + carry_bit;
66
67 return multhi;
68#endif
69}
70
71} // namespace
72
18namespace Common { 73namespace Common {
19 74
20u64 EstimateRDTSCFrequency() { 75u64 EstimateRDTSCFrequency() {
@@ -48,54 +103,71 @@ NativeClock::NativeClock(u64 emulated_cpu_frequency_, u64 emulated_clock_frequen
48 : WallClock(emulated_cpu_frequency_, emulated_clock_frequency_, true), rtsc_frequency{ 103 : WallClock(emulated_cpu_frequency_, emulated_clock_frequency_, true), rtsc_frequency{
49 rtsc_frequency_} { 104 rtsc_frequency_} {
50 _mm_mfence(); 105 _mm_mfence();
51 last_measure = __rdtsc(); 106 time_point.inner.last_measure = __rdtsc();
52 accumulated_ticks = 0U; 107 time_point.inner.accumulated_ticks = 0U;
108 ns_rtsc_factor = GetFixedPoint64Factor(1000000000, rtsc_frequency);
109 us_rtsc_factor = GetFixedPoint64Factor(1000000, rtsc_frequency);
110 ms_rtsc_factor = GetFixedPoint64Factor(1000, rtsc_frequency);
111 clock_rtsc_factor = GetFixedPoint64Factor(emulated_clock_frequency, rtsc_frequency);
112 cpu_rtsc_factor = GetFixedPoint64Factor(emulated_cpu_frequency, rtsc_frequency);
53} 113}
54 114
55u64 NativeClock::GetRTSC() { 115u64 NativeClock::GetRTSC() {
56 std::scoped_lock scope{rtsc_serialize}; 116 TimePoint new_time_point{};
57 _mm_mfence(); 117 TimePoint current_time_point{};
58 const u64 current_measure = __rdtsc(); 118 do {
59 u64 diff = current_measure - last_measure; 119 current_time_point.pack = time_point.pack;
60 diff = diff & ~static_cast<u64>(static_cast<s64>(diff) >> 63); // max(diff, 0) 120 _mm_mfence();
61 if (current_measure > last_measure) { 121 const u64 current_measure = __rdtsc();
62 last_measure = current_measure; 122 u64 diff = current_measure - current_time_point.inner.last_measure;
63 } 123 diff = diff & ~static_cast<u64>(static_cast<s64>(diff) >> 63); // max(diff, 0)
64 accumulated_ticks += diff; 124 new_time_point.inner.last_measure = current_measure > current_time_point.inner.last_measure
125 ? current_measure
126 : current_time_point.inner.last_measure;
127 new_time_point.inner.accumulated_ticks = current_time_point.inner.accumulated_ticks + diff;
128 } while (!Common::AtomicCompareAndSwap(time_point.pack.data(), new_time_point.pack,
129 current_time_point.pack));
65 /// The clock cannot be more precise than the guest timer, remove the lower bits 130 /// The clock cannot be more precise than the guest timer, remove the lower bits
66 return accumulated_ticks & inaccuracy_mask; 131 return new_time_point.inner.accumulated_ticks & inaccuracy_mask;
67} 132}
68 133
69void NativeClock::Pause(bool is_paused) { 134void NativeClock::Pause(bool is_paused) {
70 if (!is_paused) { 135 if (!is_paused) {
71 _mm_mfence(); 136 TimePoint current_time_point{};
72 last_measure = __rdtsc(); 137 TimePoint new_time_point{};
138 do {
139 current_time_point.pack = time_point.pack;
140 new_time_point.pack = current_time_point.pack;
141 _mm_mfence();
142 new_time_point.inner.last_measure = __rdtsc();
143 } while (!Common::AtomicCompareAndSwap(time_point.pack.data(), new_time_point.pack,
144 current_time_point.pack));
73 } 145 }
74} 146}
75 147
76std::chrono::nanoseconds NativeClock::GetTimeNS() { 148std::chrono::nanoseconds NativeClock::GetTimeNS() {
77 const u64 rtsc_value = GetRTSC(); 149 const u64 rtsc_value = GetRTSC();
78 return std::chrono::nanoseconds{MultiplyAndDivide64(rtsc_value, 1000000000, rtsc_frequency)}; 150 return std::chrono::nanoseconds{MultiplyHigh(rtsc_value, ns_rtsc_factor)};
79} 151}
80 152
81std::chrono::microseconds NativeClock::GetTimeUS() { 153std::chrono::microseconds NativeClock::GetTimeUS() {
82 const u64 rtsc_value = GetRTSC(); 154 const u64 rtsc_value = GetRTSC();
83 return std::chrono::microseconds{MultiplyAndDivide64(rtsc_value, 1000000, rtsc_frequency)}; 155 return std::chrono::microseconds{MultiplyHigh(rtsc_value, us_rtsc_factor)};
84} 156}
85 157
86std::chrono::milliseconds NativeClock::GetTimeMS() { 158std::chrono::milliseconds NativeClock::GetTimeMS() {
87 const u64 rtsc_value = GetRTSC(); 159 const u64 rtsc_value = GetRTSC();
88 return std::chrono::milliseconds{MultiplyAndDivide64(rtsc_value, 1000, rtsc_frequency)}; 160 return std::chrono::milliseconds{MultiplyHigh(rtsc_value, ms_rtsc_factor)};
89} 161}
90 162
91u64 NativeClock::GetClockCycles() { 163u64 NativeClock::GetClockCycles() {
92 const u64 rtsc_value = GetRTSC(); 164 const u64 rtsc_value = GetRTSC();
93 return MultiplyAndDivide64(rtsc_value, emulated_clock_frequency, rtsc_frequency); 165 return MultiplyHigh(rtsc_value, clock_rtsc_factor);
94} 166}
95 167
96u64 NativeClock::GetCPUCycles() { 168u64 NativeClock::GetCPUCycles() {
97 const u64 rtsc_value = GetRTSC(); 169 const u64 rtsc_value = GetRTSC();
98 return MultiplyAndDivide64(rtsc_value, emulated_cpu_frequency, rtsc_frequency); 170 return MultiplyHigh(rtsc_value, cpu_rtsc_factor);
99} 171}
100 172
101} // namespace X64 173} // namespace X64
diff --git a/src/common/x64/native_clock.h b/src/common/x64/native_clock.h
index 6d1e32ac8..7cbd400d2 100644
--- a/src/common/x64/native_clock.h
+++ b/src/common/x64/native_clock.h
@@ -6,7 +6,6 @@
6 6
7#include <optional> 7#include <optional>
8 8
9#include "common/spin_lock.h"
10#include "common/wall_clock.h" 9#include "common/wall_clock.h"
11 10
12namespace Common { 11namespace Common {
@@ -32,14 +31,28 @@ public:
32private: 31private:
33 u64 GetRTSC(); 32 u64 GetRTSC();
34 33
34 union alignas(16) TimePoint {
35 TimePoint() : pack{} {}
36 u128 pack{};
37 struct Inner {
38 u64 last_measure{};
39 u64 accumulated_ticks{};
40 } inner;
41 };
42
35 /// value used to reduce the native clocks accuracy as some apss rely on 43 /// value used to reduce the native clocks accuracy as some apss rely on
36 /// undefined behavior where the level of accuracy in the clock shouldn't 44 /// undefined behavior where the level of accuracy in the clock shouldn't
37 /// be higher. 45 /// be higher.
38 static constexpr u64 inaccuracy_mask = ~(UINT64_C(0x400) - 1); 46 static constexpr u64 inaccuracy_mask = ~(UINT64_C(0x400) - 1);
39 47
40 SpinLock rtsc_serialize{}; 48 TimePoint time_point;
41 u64 last_measure{}; 49 // factors
42 u64 accumulated_ticks{}; 50 u64 clock_rtsc_factor{};
51 u64 cpu_rtsc_factor{};
52 u64 ns_rtsc_factor{};
53 u64 us_rtsc_factor{};
54 u64 ms_rtsc_factor{};
55
43 u64 rtsc_frequency; 56 u64 rtsc_frequency;
44}; 57};
45} // namespace X64 58} // namespace X64
HIC SVNT DRACONES