summaryrefslogtreecommitdiff
path: root/src/common
diff options
context:
space:
mode:
Diffstat (limited to 'src/common')
-rw-r--r--src/common/intrusive_red_black_tree.h391
-rw-r--r--src/common/tree.h625
2 files changed, 551 insertions, 465 deletions
diff --git a/src/common/intrusive_red_black_tree.h b/src/common/intrusive_red_black_tree.h
index 3173cc449..b296b639e 100644
--- a/src/common/intrusive_red_black_tree.h
+++ b/src/common/intrusive_red_black_tree.h
@@ -4,6 +4,8 @@
4 4
5#pragma once 5#pragma once
6 6
7#include "common/alignment.h"
8#include "common/common_funcs.h"
7#include "common/parent_of_member.h" 9#include "common/parent_of_member.h"
8#include "common/tree.h" 10#include "common/tree.h"
9 11
@@ -15,32 +17,33 @@ class IntrusiveRedBlackTreeImpl;
15 17
16} 18}
17 19
20#pragma pack(push, 4)
18struct IntrusiveRedBlackTreeNode { 21struct IntrusiveRedBlackTreeNode {
22 YUZU_NON_COPYABLE(IntrusiveRedBlackTreeNode);
23
19public: 24public:
20 using EntryType = RBEntry<IntrusiveRedBlackTreeNode>; 25 using RBEntry = freebsd::RBEntry<IntrusiveRedBlackTreeNode>;
21 26
22 constexpr IntrusiveRedBlackTreeNode() = default; 27private:
28 RBEntry m_entry;
23 29
24 void SetEntry(const EntryType& new_entry) { 30public:
25 entry = new_entry; 31 explicit IntrusiveRedBlackTreeNode() = default;
26 }
27 32
28 [[nodiscard]] EntryType& GetEntry() { 33 [[nodiscard]] constexpr RBEntry& GetRBEntry() {
29 return entry; 34 return m_entry;
30 } 35 }
31 36 [[nodiscard]] constexpr const RBEntry& GetRBEntry() const {
32 [[nodiscard]] const EntryType& GetEntry() const { 37 return m_entry;
33 return entry;
34 } 38 }
35 39
36private: 40 constexpr void SetRBEntry(const RBEntry& entry) {
37 EntryType entry{}; 41 m_entry = entry;
38 42 }
39 friend class impl::IntrusiveRedBlackTreeImpl;
40
41 template <class, class, class>
42 friend class IntrusiveRedBlackTree;
43}; 43};
44static_assert(sizeof(IntrusiveRedBlackTreeNode) ==
45 3 * sizeof(void*) + std::max<size_t>(sizeof(freebsd::RBColor), 4));
46#pragma pack(pop)
44 47
45template <class T, class Traits, class Comparator> 48template <class T, class Traits, class Comparator>
46class IntrusiveRedBlackTree; 49class IntrusiveRedBlackTree;
@@ -48,12 +51,17 @@ class IntrusiveRedBlackTree;
48namespace impl { 51namespace impl {
49 52
50class IntrusiveRedBlackTreeImpl { 53class IntrusiveRedBlackTreeImpl {
54 YUZU_NON_COPYABLE(IntrusiveRedBlackTreeImpl);
55
51private: 56private:
52 template <class, class, class> 57 template <class, class, class>
53 friend class ::Common::IntrusiveRedBlackTree; 58 friend class ::Common::IntrusiveRedBlackTree;
54 59
55 using RootType = RBHead<IntrusiveRedBlackTreeNode>; 60private:
56 RootType root; 61 using RootType = freebsd::RBHead<IntrusiveRedBlackTreeNode>;
62
63private:
64 RootType m_root;
57 65
58public: 66public:
59 template <bool Const> 67 template <bool Const>
@@ -81,149 +89,150 @@ public:
81 IntrusiveRedBlackTreeImpl::reference>; 89 IntrusiveRedBlackTreeImpl::reference>;
82 90
83 private: 91 private:
84 pointer node; 92 pointer m_node;
85 93
86 public: 94 public:
87 explicit Iterator(pointer n) : node(n) {} 95 constexpr explicit Iterator(pointer n) : m_node(n) {}
88 96
89 bool operator==(const Iterator& rhs) const { 97 constexpr bool operator==(const Iterator& rhs) const {
90 return this->node == rhs.node; 98 return m_node == rhs.m_node;
91 } 99 }
92 100
93 bool operator!=(const Iterator& rhs) const { 101 constexpr bool operator!=(const Iterator& rhs) const {
94 return !(*this == rhs); 102 return !(*this == rhs);
95 } 103 }
96 104
97 pointer operator->() const { 105 constexpr pointer operator->() const {
98 return this->node; 106 return m_node;
99 } 107 }
100 108
101 reference operator*() const { 109 constexpr reference operator*() const {
102 return *this->node; 110 return *m_node;
103 } 111 }
104 112
105 Iterator& operator++() { 113 constexpr Iterator& operator++() {
106 this->node = GetNext(this->node); 114 m_node = GetNext(m_node);
107 return *this; 115 return *this;
108 } 116 }
109 117
110 Iterator& operator--() { 118 constexpr Iterator& operator--() {
111 this->node = GetPrev(this->node); 119 m_node = GetPrev(m_node);
112 return *this; 120 return *this;
113 } 121 }
114 122
115 Iterator operator++(int) { 123 constexpr Iterator operator++(int) {
116 const Iterator it{*this}; 124 const Iterator it{*this};
117 ++(*this); 125 ++(*this);
118 return it; 126 return it;
119 } 127 }
120 128
121 Iterator operator--(int) { 129 constexpr Iterator operator--(int) {
122 const Iterator it{*this}; 130 const Iterator it{*this};
123 --(*this); 131 --(*this);
124 return it; 132 return it;
125 } 133 }
126 134
127 operator Iterator<true>() const { 135 constexpr operator Iterator<true>() const {
128 return Iterator<true>(this->node); 136 return Iterator<true>(m_node);
129 } 137 }
130 }; 138 };
131 139
132private: 140private:
133 // Define accessors using RB_* functions. 141 constexpr bool EmptyImpl() const {
134 bool EmptyImpl() const { 142 return m_root.IsEmpty();
135 return root.IsEmpty();
136 } 143 }
137 144
138 IntrusiveRedBlackTreeNode* GetMinImpl() const { 145 constexpr IntrusiveRedBlackTreeNode* GetMinImpl() const {
139 return RB_MIN(const_cast<RootType*>(&root)); 146 return freebsd::RB_MIN(const_cast<RootType&>(m_root));
140 } 147 }
141 148
142 IntrusiveRedBlackTreeNode* GetMaxImpl() const { 149 constexpr IntrusiveRedBlackTreeNode* GetMaxImpl() const {
143 return RB_MAX(const_cast<RootType*>(&root)); 150 return freebsd::RB_MAX(const_cast<RootType&>(m_root));
144 } 151 }
145 152
146 IntrusiveRedBlackTreeNode* RemoveImpl(IntrusiveRedBlackTreeNode* node) { 153 constexpr IntrusiveRedBlackTreeNode* RemoveImpl(IntrusiveRedBlackTreeNode* node) {
147 return RB_REMOVE(&root, node); 154 return freebsd::RB_REMOVE(m_root, node);
148 } 155 }
149 156
150public: 157public:
151 static IntrusiveRedBlackTreeNode* GetNext(IntrusiveRedBlackTreeNode* node) { 158 static constexpr IntrusiveRedBlackTreeNode* GetNext(IntrusiveRedBlackTreeNode* node) {
152 return RB_NEXT(node); 159 return freebsd::RB_NEXT(node);
153 } 160 }
154 161
155 static IntrusiveRedBlackTreeNode* GetPrev(IntrusiveRedBlackTreeNode* node) { 162 static constexpr IntrusiveRedBlackTreeNode* GetPrev(IntrusiveRedBlackTreeNode* node) {
156 return RB_PREV(node); 163 return freebsd::RB_PREV(node);
157 } 164 }
158 165
159 static const IntrusiveRedBlackTreeNode* GetNext(const IntrusiveRedBlackTreeNode* node) { 166 static constexpr IntrusiveRedBlackTreeNode const* GetNext(
167 IntrusiveRedBlackTreeNode const* node) {
160 return static_cast<const IntrusiveRedBlackTreeNode*>( 168 return static_cast<const IntrusiveRedBlackTreeNode*>(
161 GetNext(const_cast<IntrusiveRedBlackTreeNode*>(node))); 169 GetNext(const_cast<IntrusiveRedBlackTreeNode*>(node)));
162 } 170 }
163 171
164 static const IntrusiveRedBlackTreeNode* GetPrev(const IntrusiveRedBlackTreeNode* node) { 172 static constexpr IntrusiveRedBlackTreeNode const* GetPrev(
173 IntrusiveRedBlackTreeNode const* node) {
165 return static_cast<const IntrusiveRedBlackTreeNode*>( 174 return static_cast<const IntrusiveRedBlackTreeNode*>(
166 GetPrev(const_cast<IntrusiveRedBlackTreeNode*>(node))); 175 GetPrev(const_cast<IntrusiveRedBlackTreeNode*>(node)));
167 } 176 }
168 177
169public: 178public:
170 constexpr IntrusiveRedBlackTreeImpl() {} 179 constexpr IntrusiveRedBlackTreeImpl() = default;
171 180
172 // Iterator accessors. 181 // Iterator accessors.
173 iterator begin() { 182 constexpr iterator begin() {
174 return iterator(this->GetMinImpl()); 183 return iterator(this->GetMinImpl());
175 } 184 }
176 185
177 const_iterator begin() const { 186 constexpr const_iterator begin() const {
178 return const_iterator(this->GetMinImpl()); 187 return const_iterator(this->GetMinImpl());
179 } 188 }
180 189
181 iterator end() { 190 constexpr iterator end() {
182 return iterator(static_cast<IntrusiveRedBlackTreeNode*>(nullptr)); 191 return iterator(static_cast<IntrusiveRedBlackTreeNode*>(nullptr));
183 } 192 }
184 193
185 const_iterator end() const { 194 constexpr const_iterator end() const {
186 return const_iterator(static_cast<const IntrusiveRedBlackTreeNode*>(nullptr)); 195 return const_iterator(static_cast<const IntrusiveRedBlackTreeNode*>(nullptr));
187 } 196 }
188 197
189 const_iterator cbegin() const { 198 constexpr const_iterator cbegin() const {
190 return this->begin(); 199 return this->begin();
191 } 200 }
192 201
193 const_iterator cend() const { 202 constexpr const_iterator cend() const {
194 return this->end(); 203 return this->end();
195 } 204 }
196 205
197 iterator iterator_to(reference ref) { 206 constexpr iterator iterator_to(reference ref) {
198 return iterator(&ref); 207 return iterator(std::addressof(ref));
199 } 208 }
200 209
201 const_iterator iterator_to(const_reference ref) const { 210 constexpr const_iterator iterator_to(const_reference ref) const {
202 return const_iterator(&ref); 211 return const_iterator(std::addressof(ref));
203 } 212 }
204 213
205 // Content management. 214 // Content management.
206 bool empty() const { 215 constexpr bool empty() const {
207 return this->EmptyImpl(); 216 return this->EmptyImpl();
208 } 217 }
209 218
210 reference back() { 219 constexpr reference back() {
211 return *this->GetMaxImpl(); 220 return *this->GetMaxImpl();
212 } 221 }
213 222
214 const_reference back() const { 223 constexpr const_reference back() const {
215 return *this->GetMaxImpl(); 224 return *this->GetMaxImpl();
216 } 225 }
217 226
218 reference front() { 227 constexpr reference front() {
219 return *this->GetMinImpl(); 228 return *this->GetMinImpl();
220 } 229 }
221 230
222 const_reference front() const { 231 constexpr const_reference front() const {
223 return *this->GetMinImpl(); 232 return *this->GetMinImpl();
224 } 233 }
225 234
226 iterator erase(iterator it) { 235 constexpr iterator erase(iterator it) {
227 auto cur = std::addressof(*it); 236 auto cur = std::addressof(*it);
228 auto next = GetNext(cur); 237 auto next = GetNext(cur);
229 this->RemoveImpl(cur); 238 this->RemoveImpl(cur);
@@ -234,16 +243,16 @@ public:
234} // namespace impl 243} // namespace impl
235 244
236template <typename T> 245template <typename T>
237concept HasLightCompareType = requires { 246concept HasRedBlackKeyType = requires {
238 { std::is_same<typename T::LightCompareType, void>::value } -> std::convertible_to<bool>; 247 { std::is_same<typename T::RedBlackKeyType, void>::value } -> std::convertible_to<bool>;
239}; 248};
240 249
241namespace impl { 250namespace impl {
242 251
243 template <typename T, typename Default> 252 template <typename T, typename Default>
244 consteval auto* GetLightCompareType() { 253 consteval auto* GetRedBlackKeyType() {
245 if constexpr (HasLightCompareType<T>) { 254 if constexpr (HasRedBlackKeyType<T>) {
246 return static_cast<typename T::LightCompareType*>(nullptr); 255 return static_cast<typename T::RedBlackKeyType*>(nullptr);
247 } else { 256 } else {
248 return static_cast<Default*>(nullptr); 257 return static_cast<Default*>(nullptr);
249 } 258 }
@@ -252,16 +261,17 @@ namespace impl {
252} // namespace impl 261} // namespace impl
253 262
254template <typename T, typename Default> 263template <typename T, typename Default>
255using LightCompareType = std::remove_pointer_t<decltype(impl::GetLightCompareType<T, Default>())>; 264using RedBlackKeyType = std::remove_pointer_t<decltype(impl::GetRedBlackKeyType<T, Default>())>;
256 265
257template <class T, class Traits, class Comparator> 266template <class T, class Traits, class Comparator>
258class IntrusiveRedBlackTree { 267class IntrusiveRedBlackTree {
268 YUZU_NON_COPYABLE(IntrusiveRedBlackTree);
259 269
260public: 270public:
261 using ImplType = impl::IntrusiveRedBlackTreeImpl; 271 using ImplType = impl::IntrusiveRedBlackTreeImpl;
262 272
263private: 273private:
264 ImplType impl{}; 274 ImplType m_impl;
265 275
266public: 276public:
267 template <bool Const> 277 template <bool Const>
@@ -277,9 +287,9 @@ public:
277 using iterator = Iterator<false>; 287 using iterator = Iterator<false>;
278 using const_iterator = Iterator<true>; 288 using const_iterator = Iterator<true>;
279 289
280 using light_value_type = LightCompareType<Comparator, value_type>; 290 using key_type = RedBlackKeyType<Comparator, value_type>;
281 using const_light_pointer = const light_value_type*; 291 using const_key_pointer = const key_type*;
282 using const_light_reference = const light_value_type&; 292 using const_key_reference = const key_type&;
283 293
284 template <bool Const> 294 template <bool Const>
285 class Iterator { 295 class Iterator {
@@ -298,183 +308,201 @@ public:
298 IntrusiveRedBlackTree::reference>; 308 IntrusiveRedBlackTree::reference>;
299 309
300 private: 310 private:
301 ImplIterator iterator; 311 ImplIterator m_impl;
302 312
303 private: 313 private:
304 explicit Iterator(ImplIterator it) : iterator(it) {} 314 constexpr explicit Iterator(ImplIterator it) : m_impl(it) {}
305 315
306 explicit Iterator(typename std::conditional<Const, ImplType::const_iterator, 316 constexpr explicit Iterator(typename ImplIterator::pointer p) : m_impl(p) {}
307 ImplType::iterator>::type::pointer ptr)
308 : iterator(ptr) {}
309 317
310 ImplIterator GetImplIterator() const { 318 constexpr ImplIterator GetImplIterator() const {
311 return this->iterator; 319 return m_impl;
312 } 320 }
313 321
314 public: 322 public:
315 bool operator==(const Iterator& rhs) const { 323 constexpr bool operator==(const Iterator& rhs) const {
316 return this->iterator == rhs.iterator; 324 return m_impl == rhs.m_impl;
317 } 325 }
318 326
319 bool operator!=(const Iterator& rhs) const { 327 constexpr bool operator!=(const Iterator& rhs) const {
320 return !(*this == rhs); 328 return !(*this == rhs);
321 } 329 }
322 330
323 pointer operator->() const { 331 constexpr pointer operator->() const {
324 return Traits::GetParent(std::addressof(*this->iterator)); 332 return Traits::GetParent(std::addressof(*m_impl));
325 } 333 }
326 334
327 reference operator*() const { 335 constexpr reference operator*() const {
328 return *Traits::GetParent(std::addressof(*this->iterator)); 336 return *Traits::GetParent(std::addressof(*m_impl));
329 } 337 }
330 338
331 Iterator& operator++() { 339 constexpr Iterator& operator++() {
332 ++this->iterator; 340 ++m_impl;
333 return *this; 341 return *this;
334 } 342 }
335 343
336 Iterator& operator--() { 344 constexpr Iterator& operator--() {
337 --this->iterator; 345 --m_impl;
338 return *this; 346 return *this;
339 } 347 }
340 348
341 Iterator operator++(int) { 349 constexpr Iterator operator++(int) {
342 const Iterator it{*this}; 350 const Iterator it{*this};
343 ++this->iterator; 351 ++m_impl;
344 return it; 352 return it;
345 } 353 }
346 354
347 Iterator operator--(int) { 355 constexpr Iterator operator--(int) {
348 const Iterator it{*this}; 356 const Iterator it{*this};
349 --this->iterator; 357 --m_impl;
350 return it; 358 return it;
351 } 359 }
352 360
353 operator Iterator<true>() const { 361 constexpr operator Iterator<true>() const {
354 return Iterator<true>(this->iterator); 362 return Iterator<true>(m_impl);
355 } 363 }
356 }; 364 };
357 365
358private: 366private:
359 static int CompareImpl(const IntrusiveRedBlackTreeNode* lhs, 367 static constexpr int CompareImpl(const IntrusiveRedBlackTreeNode* lhs,
360 const IntrusiveRedBlackTreeNode* rhs) { 368 const IntrusiveRedBlackTreeNode* rhs) {
361 return Comparator::Compare(*Traits::GetParent(lhs), *Traits::GetParent(rhs)); 369 return Comparator::Compare(*Traits::GetParent(lhs), *Traits::GetParent(rhs));
362 } 370 }
363 371
364 static int LightCompareImpl(const void* elm, const IntrusiveRedBlackTreeNode* rhs) { 372 static constexpr int CompareKeyImpl(const_key_reference key,
365 return Comparator::Compare(*static_cast<const_light_pointer>(elm), *Traits::GetParent(rhs)); 373 const IntrusiveRedBlackTreeNode* rhs) {
374 return Comparator::Compare(key, *Traits::GetParent(rhs));
366 } 375 }
367 376
368 // Define accessors using RB_* functions. 377 // Define accessors using RB_* functions.
369 IntrusiveRedBlackTreeNode* InsertImpl(IntrusiveRedBlackTreeNode* node) { 378 constexpr IntrusiveRedBlackTreeNode* InsertImpl(IntrusiveRedBlackTreeNode* node) {
370 return RB_INSERT(&impl.root, node, CompareImpl); 379 return freebsd::RB_INSERT(m_impl.m_root, node, CompareImpl);
371 } 380 }
372 381
373 IntrusiveRedBlackTreeNode* FindImpl(const IntrusiveRedBlackTreeNode* node) const { 382 constexpr IntrusiveRedBlackTreeNode* FindImpl(IntrusiveRedBlackTreeNode const* node) const {
374 return RB_FIND(const_cast<ImplType::RootType*>(&impl.root), 383 return freebsd::RB_FIND(const_cast<ImplType::RootType&>(m_impl.m_root),
375 const_cast<IntrusiveRedBlackTreeNode*>(node), CompareImpl); 384 const_cast<IntrusiveRedBlackTreeNode*>(node), CompareImpl);
376 } 385 }
377 386
378 IntrusiveRedBlackTreeNode* NFindImpl(const IntrusiveRedBlackTreeNode* node) const { 387 constexpr IntrusiveRedBlackTreeNode* NFindImpl(IntrusiveRedBlackTreeNode const* node) const {
379 return RB_NFIND(const_cast<ImplType::RootType*>(&impl.root), 388 return freebsd::RB_NFIND(const_cast<ImplType::RootType&>(m_impl.m_root),
380 const_cast<IntrusiveRedBlackTreeNode*>(node), CompareImpl); 389 const_cast<IntrusiveRedBlackTreeNode*>(node), CompareImpl);
381 } 390 }
382 391
383 IntrusiveRedBlackTreeNode* FindLightImpl(const_light_pointer lelm) const { 392 constexpr IntrusiveRedBlackTreeNode* FindKeyImpl(const_key_reference key) const {
384 return RB_FIND_LIGHT(const_cast<ImplType::RootType*>(&impl.root), 393 return freebsd::RB_FIND_KEY(const_cast<ImplType::RootType&>(m_impl.m_root), key,
385 static_cast<const void*>(lelm), LightCompareImpl); 394 CompareKeyImpl);
386 } 395 }
387 396
388 IntrusiveRedBlackTreeNode* NFindLightImpl(const_light_pointer lelm) const { 397 constexpr IntrusiveRedBlackTreeNode* NFindKeyImpl(const_key_reference key) const {
389 return RB_NFIND_LIGHT(const_cast<ImplType::RootType*>(&impl.root), 398 return freebsd::RB_NFIND_KEY(const_cast<ImplType::RootType&>(m_impl.m_root), key,
390 static_cast<const void*>(lelm), LightCompareImpl); 399 CompareKeyImpl);
400 }
401
402 constexpr IntrusiveRedBlackTreeNode* FindExistingImpl(
403 IntrusiveRedBlackTreeNode const* node) const {
404 return freebsd::RB_FIND_EXISTING(const_cast<ImplType::RootType&>(m_impl.m_root),
405 const_cast<IntrusiveRedBlackTreeNode*>(node), CompareImpl);
406 }
407
408 constexpr IntrusiveRedBlackTreeNode* FindExistingKeyImpl(const_key_reference key) const {
409 return freebsd::RB_FIND_EXISTING_KEY(const_cast<ImplType::RootType&>(m_impl.m_root), key,
410 CompareKeyImpl);
391 } 411 }
392 412
393public: 413public:
394 constexpr IntrusiveRedBlackTree() = default; 414 constexpr IntrusiveRedBlackTree() = default;
395 415
396 // Iterator accessors. 416 // Iterator accessors.
397 iterator begin() { 417 constexpr iterator begin() {
398 return iterator(this->impl.begin()); 418 return iterator(m_impl.begin());
399 } 419 }
400 420
401 const_iterator begin() const { 421 constexpr const_iterator begin() const {
402 return const_iterator(this->impl.begin()); 422 return const_iterator(m_impl.begin());
403 } 423 }
404 424
405 iterator end() { 425 constexpr iterator end() {
406 return iterator(this->impl.end()); 426 return iterator(m_impl.end());
407 } 427 }
408 428
409 const_iterator end() const { 429 constexpr const_iterator end() const {
410 return const_iterator(this->impl.end()); 430 return const_iterator(m_impl.end());
411 } 431 }
412 432
413 const_iterator cbegin() const { 433 constexpr const_iterator cbegin() const {
414 return this->begin(); 434 return this->begin();
415 } 435 }
416 436
417 const_iterator cend() const { 437 constexpr const_iterator cend() const {
418 return this->end(); 438 return this->end();
419 } 439 }
420 440
421 iterator iterator_to(reference ref) { 441 constexpr iterator iterator_to(reference ref) {
422 return iterator(this->impl.iterator_to(*Traits::GetNode(std::addressof(ref)))); 442 return iterator(m_impl.iterator_to(*Traits::GetNode(std::addressof(ref))));
423 } 443 }
424 444
425 const_iterator iterator_to(const_reference ref) const { 445 constexpr const_iterator iterator_to(const_reference ref) const {
426 return const_iterator(this->impl.iterator_to(*Traits::GetNode(std::addressof(ref)))); 446 return const_iterator(m_impl.iterator_to(*Traits::GetNode(std::addressof(ref))));
427 } 447 }
428 448
429 // Content management. 449 // Content management.
430 bool empty() const { 450 constexpr bool empty() const {
431 return this->impl.empty(); 451 return m_impl.empty();
432 } 452 }
433 453
434 reference back() { 454 constexpr reference back() {
435 return *Traits::GetParent(std::addressof(this->impl.back())); 455 return *Traits::GetParent(std::addressof(m_impl.back()));
436 } 456 }
437 457
438 const_reference back() const { 458 constexpr const_reference back() const {
439 return *Traits::GetParent(std::addressof(this->impl.back())); 459 return *Traits::GetParent(std::addressof(m_impl.back()));
440 } 460 }
441 461
442 reference front() { 462 constexpr reference front() {
443 return *Traits::GetParent(std::addressof(this->impl.front())); 463 return *Traits::GetParent(std::addressof(m_impl.front()));
444 } 464 }
445 465
446 const_reference front() const { 466 constexpr const_reference front() const {
447 return *Traits::GetParent(std::addressof(this->impl.front())); 467 return *Traits::GetParent(std::addressof(m_impl.front()));
448 } 468 }
449 469
450 iterator erase(iterator it) { 470 constexpr iterator erase(iterator it) {
451 return iterator(this->impl.erase(it.GetImplIterator())); 471 return iterator(m_impl.erase(it.GetImplIterator()));
452 } 472 }
453 473
454 iterator insert(reference ref) { 474 constexpr iterator insert(reference ref) {
455 ImplType::pointer node = Traits::GetNode(std::addressof(ref)); 475 ImplType::pointer node = Traits::GetNode(std::addressof(ref));
456 this->InsertImpl(node); 476 this->InsertImpl(node);
457 return iterator(node); 477 return iterator(node);
458 } 478 }
459 479
460 iterator find(const_reference ref) const { 480 constexpr iterator find(const_reference ref) const {
461 return iterator(this->FindImpl(Traits::GetNode(std::addressof(ref)))); 481 return iterator(this->FindImpl(Traits::GetNode(std::addressof(ref))));
462 } 482 }
463 483
464 iterator nfind(const_reference ref) const { 484 constexpr iterator nfind(const_reference ref) const {
465 return iterator(this->NFindImpl(Traits::GetNode(std::addressof(ref)))); 485 return iterator(this->NFindImpl(Traits::GetNode(std::addressof(ref))));
466 } 486 }
467 487
468 iterator find_light(const_light_reference ref) const { 488 constexpr iterator find_key(const_key_reference ref) const {
469 return iterator(this->FindLightImpl(std::addressof(ref))); 489 return iterator(this->FindKeyImpl(ref));
490 }
491
492 constexpr iterator nfind_key(const_key_reference ref) const {
493 return iterator(this->NFindKeyImpl(ref));
494 }
495
496 constexpr iterator find_existing(const_reference ref) const {
497 return iterator(this->FindExistingImpl(Traits::GetNode(std::addressof(ref))));
470 } 498 }
471 499
472 iterator nfind_light(const_light_reference ref) const { 500 constexpr iterator find_existing_key(const_key_reference ref) const {
473 return iterator(this->NFindLightImpl(std::addressof(ref))); 501 return iterator(this->FindExistingKeyImpl(ref));
474 } 502 }
475}; 503};
476 504
477template <auto T, class Derived = impl::GetParentType<T>> 505template <auto T, class Derived = Common::impl::GetParentType<T>>
478class IntrusiveRedBlackTreeMemberTraits; 506class IntrusiveRedBlackTreeMemberTraits;
479 507
480template <class Parent, IntrusiveRedBlackTreeNode Parent::*Member, class Derived> 508template <class Parent, IntrusiveRedBlackTreeNode Parent::*Member, class Derived>
@@ -498,19 +526,16 @@ private:
498 return std::addressof(parent->*Member); 526 return std::addressof(parent->*Member);
499 } 527 }
500 528
501 static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) { 529 static Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
502 return GetParentPointer<Member, Derived>(node); 530 return Common::GetParentPointer<Member, Derived>(node);
503 } 531 }
504 532
505 static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) { 533 static Derived const* GetParent(IntrusiveRedBlackTreeNode const* node) {
506 return GetParentPointer<Member, Derived>(node); 534 return Common::GetParentPointer<Member, Derived>(node);
507 } 535 }
508
509private:
510 static constexpr TypedStorage<Derived> DerivedStorage = {};
511}; 536};
512 537
513template <auto T, class Derived = impl::GetParentType<T>> 538template <auto T, class Derived = Common::impl::GetParentType<T>>
514class IntrusiveRedBlackTreeMemberTraitsDeferredAssert; 539class IntrusiveRedBlackTreeMemberTraitsDeferredAssert;
515 540
516template <class Parent, IntrusiveRedBlackTreeNode Parent::*Member, class Derived> 541template <class Parent, IntrusiveRedBlackTreeNode Parent::*Member, class Derived>
@@ -521,11 +546,6 @@ public:
521 IntrusiveRedBlackTree<Derived, IntrusiveRedBlackTreeMemberTraitsDeferredAssert, Comparator>; 546 IntrusiveRedBlackTree<Derived, IntrusiveRedBlackTreeMemberTraitsDeferredAssert, Comparator>;
522 using TreeTypeImpl = impl::IntrusiveRedBlackTreeImpl; 547 using TreeTypeImpl = impl::IntrusiveRedBlackTreeImpl;
523 548
524 static constexpr bool IsValid() {
525 TypedStorage<Derived> DerivedStorage = {};
526 return GetParent(GetNode(GetPointer(DerivedStorage))) == GetPointer(DerivedStorage);
527 }
528
529private: 549private:
530 template <class, class, class> 550 template <class, class, class>
531 friend class IntrusiveRedBlackTree; 551 friend class IntrusiveRedBlackTree;
@@ -540,30 +560,36 @@ private:
540 return std::addressof(parent->*Member); 560 return std::addressof(parent->*Member);
541 } 561 }
542 562
543 static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) { 563 static Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
544 return GetParentPointer<Member, Derived>(node); 564 return Common::GetParentPointer<Member, Derived>(node);
545 } 565 }
546 566
547 static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) { 567 static Derived const* GetParent(IntrusiveRedBlackTreeNode const* node) {
548 return GetParentPointer<Member, Derived>(node); 568 return Common::GetParentPointer<Member, Derived>(node);
549 } 569 }
550}; 570};
551 571
552template <class Derived> 572template <class Derived>
553class IntrusiveRedBlackTreeBaseNode : public IntrusiveRedBlackTreeNode { 573class alignas(void*) IntrusiveRedBlackTreeBaseNode : public IntrusiveRedBlackTreeNode {
554public: 574public:
575 using IntrusiveRedBlackTreeNode::IntrusiveRedBlackTreeNode;
576
555 constexpr Derived* GetPrev() { 577 constexpr Derived* GetPrev() {
556 return static_cast<Derived*>(impl::IntrusiveRedBlackTreeImpl::GetPrev(this)); 578 return static_cast<Derived*>(static_cast<IntrusiveRedBlackTreeBaseNode*>(
579 impl::IntrusiveRedBlackTreeImpl::GetPrev(this)));
557 } 580 }
558 constexpr const Derived* GetPrev() const { 581 constexpr const Derived* GetPrev() const {
559 return static_cast<const Derived*>(impl::IntrusiveRedBlackTreeImpl::GetPrev(this)); 582 return static_cast<const Derived*>(static_cast<const IntrusiveRedBlackTreeBaseNode*>(
583 impl::IntrusiveRedBlackTreeImpl::GetPrev(this)));
560 } 584 }
561 585
562 constexpr Derived* GetNext() { 586 constexpr Derived* GetNext() {
563 return static_cast<Derived*>(impl::IntrusiveRedBlackTreeImpl::GetNext(this)); 587 return static_cast<Derived*>(static_cast<IntrusiveRedBlackTreeBaseNode*>(
588 impl::IntrusiveRedBlackTreeImpl::GetNext(this)));
564 } 589 }
565 constexpr const Derived* GetNext() const { 590 constexpr const Derived* GetNext() const {
566 return static_cast<const Derived*>(impl::IntrusiveRedBlackTreeImpl::GetNext(this)); 591 return static_cast<const Derived*>(static_cast<const IntrusiveRedBlackTreeBaseNode*>(
592 impl::IntrusiveRedBlackTreeImpl::GetNext(this)));
567 } 593 }
568}; 594};
569 595
@@ -581,19 +607,22 @@ private:
581 friend class impl::IntrusiveRedBlackTreeImpl; 607 friend class impl::IntrusiveRedBlackTreeImpl;
582 608
583 static constexpr IntrusiveRedBlackTreeNode* GetNode(Derived* parent) { 609 static constexpr IntrusiveRedBlackTreeNode* GetNode(Derived* parent) {
584 return static_cast<IntrusiveRedBlackTreeNode*>(parent); 610 return static_cast<IntrusiveRedBlackTreeNode*>(
611 static_cast<IntrusiveRedBlackTreeBaseNode<Derived>*>(parent));
585 } 612 }
586 613
587 static constexpr IntrusiveRedBlackTreeNode const* GetNode(Derived const* parent) { 614 static constexpr IntrusiveRedBlackTreeNode const* GetNode(Derived const* parent) {
588 return static_cast<const IntrusiveRedBlackTreeNode*>(parent); 615 return static_cast<const IntrusiveRedBlackTreeNode*>(
616 static_cast<const IntrusiveRedBlackTreeBaseNode<Derived>*>(parent));
589 } 617 }
590 618
591 static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) { 619 static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
592 return static_cast<Derived*>(node); 620 return static_cast<Derived*>(static_cast<IntrusiveRedBlackTreeBaseNode<Derived>*>(node));
593 } 621 }
594 622
595 static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) { 623 static constexpr Derived const* GetParent(IntrusiveRedBlackTreeNode const* node) {
596 return static_cast<const Derived*>(node); 624 return static_cast<const Derived*>(
625 static_cast<const IntrusiveRedBlackTreeBaseNode<Derived>*>(node));
597 } 626 }
598}; 627};
599 628
diff --git a/src/common/tree.h b/src/common/tree.h
index 18faa4a48..28370e343 100644
--- a/src/common/tree.h
+++ b/src/common/tree.h
@@ -43,294 +43,265 @@
43 * 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).
44 */ 44 */
45 45
46#include "common/assert.h" 46namespace Common::freebsd {
47 47
48namespace Common { 48enum class RBColor {
49 RB_BLACK = 0,
50 RB_RED = 1,
51};
52
53#pragma pack(push, 4)
49template <typename T> 54template <typename T>
50class RBHead { 55class RBEntry {
51public: 56public:
52 [[nodiscard]] T* Root() { 57 constexpr RBEntry() = default;
53 return rbh_root;
54 }
55 58
56 [[nodiscard]] const T* Root() const { 59 [[nodiscard]] constexpr T* Left() {
57 return rbh_root; 60 return m_rbe_left;
58 } 61 }
59 62 [[nodiscard]] constexpr const T* Left() const {
60 void SetRoot(T* root) { 63 return m_rbe_left;
61 rbh_root = root;
62 } 64 }
63 65
64 [[nodiscard]] bool IsEmpty() const { 66 constexpr void SetLeft(T* e) {
65 return Root() == nullptr; 67 m_rbe_left = e;
66 } 68 }
67 69
68private: 70 [[nodiscard]] constexpr T* Right() {
69 T* rbh_root = nullptr; 71 return m_rbe_right;
70};
71
72enum class EntryColor {
73 Black,
74 Red,
75};
76
77template <typename T>
78class RBEntry {
79public:
80 [[nodiscard]] T* Left() {
81 return rbe_left;
82 } 72 }
83 73 [[nodiscard]] constexpr const T* Right() const {
84 [[nodiscard]] const T* Left() const { 74 return m_rbe_right;
85 return rbe_left;
86 } 75 }
87 76
88 void SetLeft(T* left) { 77 constexpr void SetRight(T* e) {
89 rbe_left = left; 78 m_rbe_right = e;
90 } 79 }
91 80
92 [[nodiscard]] T* Right() { 81 [[nodiscard]] constexpr T* Parent() {
93 return rbe_right; 82 return m_rbe_parent;
94 } 83 }
95 84 [[nodiscard]] constexpr const T* Parent() const {
96 [[nodiscard]] const T* Right() const { 85 return m_rbe_parent;
97 return rbe_right;
98 } 86 }
99 87
100 void SetRight(T* right) { 88 constexpr void SetParent(T* e) {
101 rbe_right = right; 89 m_rbe_parent = e;
102 } 90 }
103 91
104 [[nodiscard]] T* Parent() { 92 [[nodiscard]] constexpr bool IsBlack() const {
105 return rbe_parent; 93 return m_rbe_color == RBColor::RB_BLACK;
106 } 94 }
107 95 [[nodiscard]] constexpr bool IsRed() const {
108 [[nodiscard]] const T* Parent() const { 96 return m_rbe_color == RBColor::RB_RED;
109 return rbe_parent;
110 } 97 }
111 98 [[nodiscard]] constexpr RBColor Color() const {
112 void SetParent(T* parent) { 99 return m_rbe_color;
113 rbe_parent = parent;
114 } 100 }
115 101
116 [[nodiscard]] bool IsBlack() const { 102 constexpr void SetColor(RBColor c) {
117 return rbe_color == EntryColor::Black; 103 m_rbe_color = c;
118 } 104 }
119 105
120 [[nodiscard]] bool IsRed() const { 106private:
121 return rbe_color == EntryColor::Red; 107 T* m_rbe_left{};
122 } 108 T* m_rbe_right{};
109 T* m_rbe_parent{};
110 RBColor m_rbe_color{RBColor::RB_BLACK};
111};
112#pragma pack(pop)
123 113
124 [[nodiscard]] EntryColor Color() const { 114template <typename T>
125 return rbe_color; 115struct CheckRBEntry {
126 } 116 static constexpr bool value = false;
117};
118template <typename T>
119struct CheckRBEntry<RBEntry<T>> {
120 static constexpr bool value = true;
121};
127 122
128 void SetColor(EntryColor color) { 123template <typename T>
129 rbe_color = color; 124concept IsRBEntry = CheckRBEntry<T>::value;
130 }
131 125
126template <typename T>
127concept HasRBEntry = requires(T& t, const T& ct) {
128 { t.GetRBEntry() } -> std::same_as<RBEntry<T>&>;
129 { ct.GetRBEntry() } -> std::same_as<const RBEntry<T>&>;
130};
131
132template <typename T>
133requires HasRBEntry<T>
134class RBHead {
132private: 135private:
133 T* rbe_left = nullptr; 136 T* m_rbh_root = nullptr;
134 T* rbe_right = nullptr; 137
135 T* rbe_parent = nullptr; 138public:
136 EntryColor rbe_color{}; 139 [[nodiscard]] constexpr T* Root() {
140 return m_rbh_root;
141 }
142 [[nodiscard]] constexpr const T* Root() const {
143 return m_rbh_root;
144 }
145 constexpr void SetRoot(T* root) {
146 m_rbh_root = root;
147 }
148
149 [[nodiscard]] constexpr bool IsEmpty() const {
150 return this->Root() == nullptr;
151 }
137}; 152};
138 153
139template <typename Node> 154template <typename T>
140[[nodiscard]] RBEntry<Node>& RB_ENTRY(Node* node) { 155requires HasRBEntry<T>
141 return node->GetEntry(); 156[[nodiscard]] constexpr RBEntry<T>& RB_ENTRY(T* t) {
157 return t->GetRBEntry();
142} 158}
143 159template <typename T>
144template <typename Node> 160requires HasRBEntry<T>
145[[nodiscard]] const RBEntry<Node>& RB_ENTRY(const Node* node) { 161[[nodiscard]] constexpr const RBEntry<T>& RB_ENTRY(const T* t) {
146 return node->GetEntry(); 162 return t->GetRBEntry();
147} 163}
148 164
149template <typename Node> 165template <typename T>
150[[nodiscard]] Node* RB_PARENT(Node* node) { 166requires HasRBEntry<T>
151 return RB_ENTRY(node).Parent(); 167[[nodiscard]] constexpr T* RB_LEFT(T* t) {
168 return RB_ENTRY(t).Left();
152} 169}
153 170template <typename T>
154template <typename Node> 171requires HasRBEntry<T>
155[[nodiscard]] const Node* RB_PARENT(const Node* node) { 172[[nodiscard]] constexpr const T* RB_LEFT(const T* t) {
156 return RB_ENTRY(node).Parent(); 173 return RB_ENTRY(t).Left();
157} 174}
158 175
159template <typename Node> 176template <typename T>
160void RB_SET_PARENT(Node* node, Node* parent) { 177requires HasRBEntry<T>
161 return RB_ENTRY(node).SetParent(parent); 178[[nodiscard]] constexpr T* RB_RIGHT(T* t) {
179 return RB_ENTRY(t).Right();
162} 180}
163 181template <typename T>
164template <typename Node> 182requires HasRBEntry<T>
165[[nodiscard]] Node* RB_LEFT(Node* node) { 183[[nodiscard]] constexpr const T* RB_RIGHT(const T* t) {
166 return RB_ENTRY(node).Left(); 184 return RB_ENTRY(t).Right();
167} 185}
168 186
169template <typename Node> 187template <typename T>
170[[nodiscard]] const Node* RB_LEFT(const Node* node) { 188requires HasRBEntry<T>
171 return RB_ENTRY(node).Left(); 189[[nodiscard]] constexpr T* RB_PARENT(T* t) {
190 return RB_ENTRY(t).Parent();
172} 191}
173 192template <typename T>
174template <typename Node> 193requires HasRBEntry<T>
175void RB_SET_LEFT(Node* node, Node* left) { 194[[nodiscard]] constexpr const T* RB_PARENT(const T* t) {
176 return RB_ENTRY(node).SetLeft(left); 195 return RB_ENTRY(t).Parent();
177} 196}
178 197
179template <typename Node> 198template <typename T>
180[[nodiscard]] Node* RB_RIGHT(Node* node) { 199requires HasRBEntry<T>
181 return RB_ENTRY(node).Right(); 200constexpr void RB_SET_LEFT(T* t, T* e) {
201 RB_ENTRY(t).SetLeft(e);
182} 202}
183 203template <typename T>
184template <typename Node> 204requires HasRBEntry<T>
185[[nodiscard]] const Node* RB_RIGHT(const Node* node) { 205constexpr void RB_SET_RIGHT(T* t, T* e) {
186 return RB_ENTRY(node).Right(); 206 RB_ENTRY(t).SetRight(e);
187} 207}
188 208template <typename T>
189template <typename Node> 209requires HasRBEntry<T>
190void RB_SET_RIGHT(Node* node, Node* right) { 210constexpr void RB_SET_PARENT(T* t, T* e) {
191 return RB_ENTRY(node).SetRight(right); 211 RB_ENTRY(t).SetParent(e);
192} 212}
193 213
194template <typename Node> 214template <typename T>
195[[nodiscard]] bool RB_IS_BLACK(const Node* node) { 215requires HasRBEntry<T>
196 return RB_ENTRY(node).IsBlack(); 216[[nodiscard]] constexpr bool RB_IS_BLACK(const T* t) {
217 return RB_ENTRY(t).IsBlack();
197} 218}
198 219template <typename T>
199template <typename Node> 220requires HasRBEntry<T>
200[[nodiscard]] bool RB_IS_RED(const Node* node) { 221[[nodiscard]] constexpr bool RB_IS_RED(const T* t) {
201 return RB_ENTRY(node).IsRed(); 222 return RB_ENTRY(t).IsRed();
202} 223}
203 224
204template <typename Node> 225template <typename T>
205[[nodiscard]] EntryColor RB_COLOR(const Node* node) { 226requires HasRBEntry<T>
206 return RB_ENTRY(node).Color(); 227[[nodiscard]] constexpr RBColor RB_COLOR(const T* t) {
228 return RB_ENTRY(t).Color();
207} 229}
208 230
209template <typename Node> 231template <typename T>
210void RB_SET_COLOR(Node* node, EntryColor color) { 232requires HasRBEntry<T>
211 return RB_ENTRY(node).SetColor(color); 233constexpr void RB_SET_COLOR(T* t, RBColor c) {
234 RB_ENTRY(t).SetColor(c);
212} 235}
213 236
214template <typename Node> 237template <typename T>
215void RB_SET(Node* node, Node* parent) { 238requires HasRBEntry<T>
216 auto& entry = RB_ENTRY(node); 239constexpr void RB_SET(T* elm, T* parent) {
217 entry.SetParent(parent); 240 auto& rb_entry = RB_ENTRY(elm);
218 entry.SetLeft(nullptr); 241 rb_entry.SetParent(parent);
219 entry.SetRight(nullptr); 242 rb_entry.SetLeft(nullptr);
220 entry.SetColor(EntryColor::Red); 243 rb_entry.SetRight(nullptr);
244 rb_entry.SetColor(RBColor::RB_RED);
221} 245}
222 246
223template <typename Node> 247template <typename T>
224void RB_SET_BLACKRED(Node* black, Node* red) { 248requires HasRBEntry<T>
225 RB_SET_COLOR(black, EntryColor::Black); 249constexpr void RB_SET_BLACKRED(T* black, T* red) {
226 RB_SET_COLOR(red, EntryColor::Red); 250 RB_SET_COLOR(black, RBColor::RB_BLACK);
251 RB_SET_COLOR(red, RBColor::RB_RED);
227} 252}
228 253
229template <typename Node> 254template <typename T>
230void RB_ROTATE_LEFT(RBHead<Node>* head, Node* elm, Node*& tmp) { 255requires HasRBEntry<T>
256constexpr void RB_ROTATE_LEFT(RBHead<T>& head, T* elm, T*& tmp) {
231 tmp = RB_RIGHT(elm); 257 tmp = RB_RIGHT(elm);
232 RB_SET_RIGHT(elm, RB_LEFT(tmp)); 258 if (RB_SET_RIGHT(elm, RB_LEFT(tmp)); RB_RIGHT(elm) != nullptr) {
233 if (RB_RIGHT(elm) != nullptr) {
234 RB_SET_PARENT(RB_LEFT(tmp), elm); 259 RB_SET_PARENT(RB_LEFT(tmp), elm);
235 } 260 }
236 261
237 RB_SET_PARENT(tmp, RB_PARENT(elm)); 262 if (RB_SET_PARENT(tmp, RB_PARENT(elm)); RB_PARENT(tmp) != nullptr) {
238 if (RB_PARENT(tmp) != nullptr) {
239 if (elm == RB_LEFT(RB_PARENT(elm))) { 263 if (elm == RB_LEFT(RB_PARENT(elm))) {
240 RB_SET_LEFT(RB_PARENT(elm), tmp); 264 RB_SET_LEFT(RB_PARENT(elm), tmp);
241 } else { 265 } else {
242 RB_SET_RIGHT(RB_PARENT(elm), tmp); 266 RB_SET_RIGHT(RB_PARENT(elm), tmp);
243 } 267 }
244 } else { 268 } else {
245 head->SetRoot(tmp); 269 head.SetRoot(tmp);
246 } 270 }
247 271
248 RB_SET_LEFT(tmp, elm); 272 RB_SET_LEFT(tmp, elm);
249 RB_SET_PARENT(elm, tmp); 273 RB_SET_PARENT(elm, tmp);
250} 274}
251 275
252template <typename Node> 276template <typename T>
253void RB_ROTATE_RIGHT(RBHead<Node>* head, Node* elm, Node*& tmp) { 277requires HasRBEntry<T>
278constexpr void RB_ROTATE_RIGHT(RBHead<T>& head, T* elm, T*& tmp) {
254 tmp = RB_LEFT(elm); 279 tmp = RB_LEFT(elm);
255 RB_SET_LEFT(elm, RB_RIGHT(tmp)); 280 if (RB_SET_LEFT(elm, RB_RIGHT(tmp)); RB_LEFT(elm) != nullptr) {
256 if (RB_LEFT(elm) != nullptr) {
257 RB_SET_PARENT(RB_RIGHT(tmp), elm); 281 RB_SET_PARENT(RB_RIGHT(tmp), elm);
258 } 282 }
259 283
260 RB_SET_PARENT(tmp, RB_PARENT(elm)); 284 if (RB_SET_PARENT(tmp, RB_PARENT(elm)); RB_PARENT(tmp) != nullptr) {
261 if (RB_PARENT(tmp) != nullptr) {
262 if (elm == RB_LEFT(RB_PARENT(elm))) { 285 if (elm == RB_LEFT(RB_PARENT(elm))) {
263 RB_SET_LEFT(RB_PARENT(elm), tmp); 286 RB_SET_LEFT(RB_PARENT(elm), tmp);
264 } else { 287 } else {
265 RB_SET_RIGHT(RB_PARENT(elm), tmp); 288 RB_SET_RIGHT(RB_PARENT(elm), tmp);
266 } 289 }
267 } else { 290 } else {
268 head->SetRoot(tmp); 291 head.SetRoot(tmp);
269 } 292 }
270 293
271 RB_SET_RIGHT(tmp, elm); 294 RB_SET_RIGHT(tmp, elm);
272 RB_SET_PARENT(elm, tmp); 295 RB_SET_PARENT(elm, tmp);
273} 296}
274 297
275template <typename Node> 298template <typename T>
276void RB_INSERT_COLOR(RBHead<Node>* head, Node* elm) { 299requires HasRBEntry<T>
277 Node* parent = nullptr; 300constexpr void RB_REMOVE_COLOR(RBHead<T>& head, T* parent, T* elm) {
278 Node* tmp = nullptr; 301 T* tmp;
279 302 while ((elm == nullptr || RB_IS_BLACK(elm)) && elm != head.Root()) {
280 while ((parent = RB_PARENT(elm)) != nullptr && RB_IS_RED(parent)) {
281 Node* gparent = RB_PARENT(parent);
282 if (parent == RB_LEFT(gparent)) {
283 tmp = RB_RIGHT(gparent);
284 if (tmp && RB_IS_RED(tmp)) {
285 RB_SET_COLOR(tmp, EntryColor::Black);
286 RB_SET_BLACKRED(parent, gparent);
287 elm = gparent;
288 continue;
289 }
290
291 if (RB_RIGHT(parent) == elm) {
292 RB_ROTATE_LEFT(head, parent, tmp);
293 tmp = parent;
294 parent = elm;
295 elm = tmp;
296 }
297
298 RB_SET_BLACKRED(parent, gparent);
299 RB_ROTATE_RIGHT(head, gparent, tmp);
300 } else {
301 tmp = RB_LEFT(gparent);
302 if (tmp && RB_IS_RED(tmp)) {
303 RB_SET_COLOR(tmp, EntryColor::Black);
304 RB_SET_BLACKRED(parent, gparent);
305 elm = gparent;
306 continue;
307 }
308
309 if (RB_LEFT(parent) == elm) {
310 RB_ROTATE_RIGHT(head, parent, tmp);
311 tmp = parent;
312 parent = elm;
313 elm = tmp;
314 }
315
316 RB_SET_BLACKRED(parent, gparent);
317 RB_ROTATE_LEFT(head, gparent, tmp);
318 }
319 }
320
321 RB_SET_COLOR(head->Root(), EntryColor::Black);
322}
323
324template <typename Node>
325void RB_REMOVE_COLOR(RBHead<Node>* head, Node* parent, Node* elm) {
326 Node* tmp;
327 while ((elm == nullptr || RB_IS_BLACK(elm)) && elm != head->Root() && parent != nullptr) {
328 if (RB_LEFT(parent) == elm) { 303 if (RB_LEFT(parent) == elm) {
329 tmp = RB_RIGHT(parent); 304 tmp = RB_RIGHT(parent);
330 if (!tmp) {
331 ASSERT_MSG(false, "tmp is invalid!");
332 break;
333 }
334 if (RB_IS_RED(tmp)) { 305 if (RB_IS_RED(tmp)) {
335 RB_SET_BLACKRED(tmp, parent); 306 RB_SET_BLACKRED(tmp, parent);
336 RB_ROTATE_LEFT(head, parent, tmp); 307 RB_ROTATE_LEFT(head, parent, tmp);
@@ -339,29 +310,29 @@ void RB_REMOVE_COLOR(RBHead<Node>* head, Node* parent, Node* elm) {
339 310
340 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) && 311 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) &&
341 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) { 312 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) {
342 RB_SET_COLOR(tmp, EntryColor::Red); 313 RB_SET_COLOR(tmp, RBColor::RB_RED);
343 elm = parent; 314 elm = parent;
344 parent = RB_PARENT(elm); 315 parent = RB_PARENT(elm);
345 } else { 316 } else {
346 if (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp))) { 317 if (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp))) {
347 Node* oleft; 318 T* oleft;
348 if ((oleft = RB_LEFT(tmp)) != nullptr) { 319 if ((oleft = RB_LEFT(tmp)) != nullptr) {
349 RB_SET_COLOR(oleft, EntryColor::Black); 320 RB_SET_COLOR(oleft, RBColor::RB_BLACK);
350 } 321 }
351 322
352 RB_SET_COLOR(tmp, EntryColor::Red); 323 RB_SET_COLOR(tmp, RBColor::RB_RED);
353 RB_ROTATE_RIGHT(head, tmp, oleft); 324 RB_ROTATE_RIGHT(head, tmp, oleft);
354 tmp = RB_RIGHT(parent); 325 tmp = RB_RIGHT(parent);
355 } 326 }
356 327
357 RB_SET_COLOR(tmp, RB_COLOR(parent)); 328 RB_SET_COLOR(tmp, RB_COLOR(parent));
358 RB_SET_COLOR(parent, EntryColor::Black); 329 RB_SET_COLOR(parent, RBColor::RB_BLACK);
359 if (RB_RIGHT(tmp)) { 330 if (RB_RIGHT(tmp)) {
360 RB_SET_COLOR(RB_RIGHT(tmp), EntryColor::Black); 331 RB_SET_COLOR(RB_RIGHT(tmp), RBColor::RB_BLACK);
361 } 332 }
362 333
363 RB_ROTATE_LEFT(head, parent, tmp); 334 RB_ROTATE_LEFT(head, parent, tmp);
364 elm = head->Root(); 335 elm = head.Root();
365 break; 336 break;
366 } 337 }
367 } else { 338 } else {
@@ -372,68 +343,56 @@ void RB_REMOVE_COLOR(RBHead<Node>* head, Node* parent, Node* elm) {
372 tmp = RB_LEFT(parent); 343 tmp = RB_LEFT(parent);
373 } 344 }
374 345
375 if (!tmp) {
376 ASSERT_MSG(false, "tmp is invalid!");
377 break;
378 }
379
380 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) && 346 if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) &&
381 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) { 347 (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) {
382 RB_SET_COLOR(tmp, EntryColor::Red); 348 RB_SET_COLOR(tmp, RBColor::RB_RED);
383 elm = parent; 349 elm = parent;
384 parent = RB_PARENT(elm); 350 parent = RB_PARENT(elm);
385 } else { 351 } else {
386 if (RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) { 352 if (RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) {
387 Node* oright; 353 T* oright;
388 if ((oright = RB_RIGHT(tmp)) != nullptr) { 354 if ((oright = RB_RIGHT(tmp)) != nullptr) {
389 RB_SET_COLOR(oright, EntryColor::Black); 355 RB_SET_COLOR(oright, RBColor::RB_BLACK);
390 } 356 }
391 357
392 RB_SET_COLOR(tmp, EntryColor::Red); 358 RB_SET_COLOR(tmp, RBColor::RB_RED);
393 RB_ROTATE_LEFT(head, tmp, oright); 359 RB_ROTATE_LEFT(head, tmp, oright);
394 tmp = RB_LEFT(parent); 360 tmp = RB_LEFT(parent);
395 } 361 }
396 362
397 RB_SET_COLOR(tmp, RB_COLOR(parent)); 363 RB_SET_COLOR(tmp, RB_COLOR(parent));
398 RB_SET_COLOR(parent, EntryColor::Black); 364 RB_SET_COLOR(parent, RBColor::RB_BLACK);
399 365
400 if (RB_LEFT(tmp)) { 366 if (RB_LEFT(tmp)) {
401 RB_SET_COLOR(RB_LEFT(tmp), EntryColor::Black); 367 RB_SET_COLOR(RB_LEFT(tmp), RBColor::RB_BLACK);
402 } 368 }
403 369
404 RB_ROTATE_RIGHT(head, parent, tmp); 370 RB_ROTATE_RIGHT(head, parent, tmp);
405 elm = head->Root(); 371 elm = head.Root();
406 break; 372 break;
407 } 373 }
408 } 374 }
409 } 375 }
410 376
411 if (elm) { 377 if (elm) {
412 RB_SET_COLOR(elm, EntryColor::Black); 378 RB_SET_COLOR(elm, RBColor::RB_BLACK);
413 } 379 }
414} 380}
415 381
416template <typename Node> 382template <typename T>
417Node* RB_REMOVE(RBHead<Node>* head, Node* elm) { 383requires HasRBEntry<T>
418 Node* child = nullptr; 384constexpr T* RB_REMOVE(RBHead<T>& head, T* elm) {
419 Node* parent = nullptr; 385 T* child = nullptr;
420 Node* old = elm; 386 T* parent = nullptr;
421 EntryColor color{}; 387 T* old = elm;
422 388 RBColor color = RBColor::RB_BLACK;
423 const auto finalize = [&] {
424 if (color == EntryColor::Black) {
425 RB_REMOVE_COLOR(head, parent, child);
426 }
427
428 return old;
429 };
430 389
431 if (RB_LEFT(elm) == nullptr) { 390 if (RB_LEFT(elm) == nullptr) {
432 child = RB_RIGHT(elm); 391 child = RB_RIGHT(elm);
433 } else if (RB_RIGHT(elm) == nullptr) { 392 } else if (RB_RIGHT(elm) == nullptr) {
434 child = RB_LEFT(elm); 393 child = RB_LEFT(elm);
435 } else { 394 } else {
436 Node* left; 395 T* left;
437 elm = RB_RIGHT(elm); 396 elm = RB_RIGHT(elm);
438 while ((left = RB_LEFT(elm)) != nullptr) { 397 while ((left = RB_LEFT(elm)) != nullptr) {
439 elm = left; 398 elm = left;
@@ -446,6 +405,7 @@ Node* RB_REMOVE(RBHead<Node>* head, Node* elm) {
446 if (child) { 405 if (child) {
447 RB_SET_PARENT(child, parent); 406 RB_SET_PARENT(child, parent);
448 } 407 }
408
449 if (parent) { 409 if (parent) {
450 if (RB_LEFT(parent) == elm) { 410 if (RB_LEFT(parent) == elm) {
451 RB_SET_LEFT(parent, child); 411 RB_SET_LEFT(parent, child);
@@ -453,14 +413,14 @@ Node* RB_REMOVE(RBHead<Node>* head, Node* elm) {
453 RB_SET_RIGHT(parent, child); 413 RB_SET_RIGHT(parent, child);
454 } 414 }
455 } else { 415 } else {
456 head->SetRoot(child); 416 head.SetRoot(child);
457 } 417 }
458 418
459 if (RB_PARENT(elm) == old) { 419 if (RB_PARENT(elm) == old) {
460 parent = elm; 420 parent = elm;
461 } 421 }
462 422
463 elm->SetEntry(old->GetEntry()); 423 elm->SetRBEntry(old->GetRBEntry());
464 424
465 if (RB_PARENT(old)) { 425 if (RB_PARENT(old)) {
466 if (RB_LEFT(RB_PARENT(old)) == old) { 426 if (RB_LEFT(RB_PARENT(old)) == old) {
@@ -469,17 +429,24 @@ Node* RB_REMOVE(RBHead<Node>* head, Node* elm) {
469 RB_SET_RIGHT(RB_PARENT(old), elm); 429 RB_SET_RIGHT(RB_PARENT(old), elm);
470 } 430 }
471 } else { 431 } else {
472 head->SetRoot(elm); 432 head.SetRoot(elm);
473 } 433 }
434
474 RB_SET_PARENT(RB_LEFT(old), elm); 435 RB_SET_PARENT(RB_LEFT(old), elm);
436
475 if (RB_RIGHT(old)) { 437 if (RB_RIGHT(old)) {
476 RB_SET_PARENT(RB_RIGHT(old), elm); 438 RB_SET_PARENT(RB_RIGHT(old), elm);
477 } 439 }
440
478 if (parent) { 441 if (parent) {
479 left = parent; 442 left = parent;
480 } 443 }
481 444
482 return finalize(); 445 if (color == RBColor::RB_BLACK) {
446 RB_REMOVE_COLOR(head, parent, child);
447 }
448
449 return old;
483 } 450 }
484 451
485 parent = RB_PARENT(elm); 452 parent = RB_PARENT(elm);
@@ -495,17 +462,69 @@ Node* RB_REMOVE(RBHead<Node>* head, Node* elm) {
495 RB_SET_RIGHT(parent, child); 462 RB_SET_RIGHT(parent, child);
496 } 463 }
497 } else { 464 } else {
498 head->SetRoot(child); 465 head.SetRoot(child);
466 }
467
468 if (color == RBColor::RB_BLACK) {
469 RB_REMOVE_COLOR(head, parent, child);
470 }
471
472 return old;
473}
474
475template <typename T>
476requires HasRBEntry<T>
477constexpr void RB_INSERT_COLOR(RBHead<T>& head, T* elm) {
478 T *parent = nullptr, *tmp = nullptr;
479 while ((parent = RB_PARENT(elm)) != nullptr && RB_IS_RED(parent)) {
480 T* gparent = RB_PARENT(parent);
481 if (parent == RB_LEFT(gparent)) {
482 tmp = RB_RIGHT(gparent);
483 if (tmp && RB_IS_RED(tmp)) {
484 RB_SET_COLOR(tmp, RBColor::RB_BLACK);
485 RB_SET_BLACKRED(parent, gparent);
486 elm = gparent;
487 continue;
488 }
489
490 if (RB_RIGHT(parent) == elm) {
491 RB_ROTATE_LEFT(head, parent, tmp);
492 tmp = parent;
493 parent = elm;
494 elm = tmp;
495 }
496
497 RB_SET_BLACKRED(parent, gparent);
498 RB_ROTATE_RIGHT(head, gparent, tmp);
499 } else {
500 tmp = RB_LEFT(gparent);
501 if (tmp && RB_IS_RED(tmp)) {
502 RB_SET_COLOR(tmp, RBColor::RB_BLACK);
503 RB_SET_BLACKRED(parent, gparent);
504 elm = gparent;
505 continue;
506 }
507
508 if (RB_LEFT(parent) == elm) {
509 RB_ROTATE_RIGHT(head, parent, tmp);
510 tmp = parent;
511 parent = elm;
512 elm = tmp;
513 }
514
515 RB_SET_BLACKRED(parent, gparent);
516 RB_ROTATE_LEFT(head, gparent, tmp);
517 }
499 } 518 }
500 519
501 return finalize(); 520 RB_SET_COLOR(head.Root(), RBColor::RB_BLACK);
502} 521}
503 522
504// Inserts a node into the RB tree 523template <typename T, typename Compare>
505template <typename Node, typename CompareFunction> 524requires HasRBEntry<T>
506Node* RB_INSERT(RBHead<Node>* head, Node* elm, CompareFunction cmp) { 525constexpr T* RB_INSERT(RBHead<T>& head, T* elm, Compare cmp) {
507 Node* parent = nullptr; 526 T* parent = nullptr;
508 Node* tmp = head->Root(); 527 T* tmp = head.Root();
509 int comp = 0; 528 int comp = 0;
510 529
511 while (tmp) { 530 while (tmp) {
@@ -529,17 +548,17 @@ Node* RB_INSERT(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
529 RB_SET_RIGHT(parent, elm); 548 RB_SET_RIGHT(parent, elm);
530 } 549 }
531 } else { 550 } else {
532 head->SetRoot(elm); 551 head.SetRoot(elm);
533 } 552 }
534 553
535 RB_INSERT_COLOR(head, elm); 554 RB_INSERT_COLOR(head, elm);
536 return nullptr; 555 return nullptr;
537} 556}
538 557
539// Finds the node with the same key as elm 558template <typename T, typename Compare>
540template <typename Node, typename CompareFunction> 559requires HasRBEntry<T>
541Node* RB_FIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) { 560constexpr T* RB_FIND(RBHead<T>& head, T* elm, Compare cmp) {
542 Node* tmp = head->Root(); 561 T* tmp = head.Root();
543 562
544 while (tmp) { 563 while (tmp) {
545 const int comp = cmp(elm, tmp); 564 const int comp = cmp(elm, tmp);
@@ -555,11 +574,11 @@ Node* RB_FIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
555 return nullptr; 574 return nullptr;
556} 575}
557 576
558// Finds the first node greater than or equal to the search key 577template <typename T, typename Compare>
559template <typename Node, typename CompareFunction> 578requires HasRBEntry<T>
560Node* RB_NFIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) { 579constexpr T* RB_NFIND(RBHead<T>& head, T* elm, Compare cmp) {
561 Node* tmp = head->Root(); 580 T* tmp = head.Root();
562 Node* res = nullptr; 581 T* res = nullptr;
563 582
564 while (tmp) { 583 while (tmp) {
565 const int comp = cmp(elm, tmp); 584 const int comp = cmp(elm, tmp);
@@ -576,13 +595,13 @@ Node* RB_NFIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) {
576 return res; 595 return res;
577} 596}
578 597
579// Finds the node with the same key as lelm 598template <typename T, typename U, typename Compare>
580template <typename Node, typename CompareFunction> 599requires HasRBEntry<T>
581Node* RB_FIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) { 600constexpr T* RB_FIND_KEY(RBHead<T>& head, const U& key, Compare cmp) {
582 Node* tmp = head->Root(); 601 T* tmp = head.Root();
583 602
584 while (tmp) { 603 while (tmp) {
585 const int comp = lcmp(lelm, tmp); 604 const int comp = cmp(key, tmp);
586 if (comp < 0) { 605 if (comp < 0) {
587 tmp = RB_LEFT(tmp); 606 tmp = RB_LEFT(tmp);
588 } else if (comp > 0) { 607 } else if (comp > 0) {
@@ -595,14 +614,14 @@ Node* RB_FIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp)
595 return nullptr; 614 return nullptr;
596} 615}
597 616
598// Finds the first node greater than or equal to the search key 617template <typename T, typename U, typename Compare>
599template <typename Node, typename CompareFunction> 618requires HasRBEntry<T>
600Node* RB_NFIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) { 619constexpr T* RB_NFIND_KEY(RBHead<T>& head, const U& key, Compare cmp) {
601 Node* tmp = head->Root(); 620 T* tmp = head.Root();
602 Node* res = nullptr; 621 T* res = nullptr;
603 622
604 while (tmp) { 623 while (tmp) {
605 const int comp = lcmp(lelm, tmp); 624 const int comp = cmp(key, tmp);
606 if (comp < 0) { 625 if (comp < 0) {
607 res = tmp; 626 res = tmp;
608 tmp = RB_LEFT(tmp); 627 tmp = RB_LEFT(tmp);
@@ -616,8 +635,43 @@ Node* RB_NFIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp)
616 return res; 635 return res;
617} 636}
618 637
619template <typename Node> 638template <typename T, typename Compare>
620Node* RB_NEXT(Node* elm) { 639requires HasRBEntry<T>
640constexpr T* RB_FIND_EXISTING(RBHead<T>& head, T* elm, Compare cmp) {
641 T* tmp = head.Root();
642
643 while (true) {
644 const int comp = cmp(elm, tmp);
645 if (comp < 0) {
646 tmp = RB_LEFT(tmp);
647 } else if (comp > 0) {
648 tmp = RB_RIGHT(tmp);
649 } else {
650 return tmp;
651 }
652 }
653}
654
655template <typename T, typename U, typename Compare>
656requires HasRBEntry<T>
657constexpr T* RB_FIND_EXISTING_KEY(RBHead<T>& head, const U& key, Compare cmp) {
658 T* tmp = head.Root();
659
660 while (true) {
661 const int comp = cmp(key, tmp);
662 if (comp < 0) {
663 tmp = RB_LEFT(tmp);
664 } else if (comp > 0) {
665 tmp = RB_RIGHT(tmp);
666 } else {
667 return tmp;
668 }
669 }
670}
671
672template <typename T>
673requires HasRBEntry<T>
674constexpr T* RB_NEXT(T* elm) {
621 if (RB_RIGHT(elm)) { 675 if (RB_RIGHT(elm)) {
622 elm = RB_RIGHT(elm); 676 elm = RB_RIGHT(elm);
623 while (RB_LEFT(elm)) { 677 while (RB_LEFT(elm)) {
@@ -636,8 +690,9 @@ Node* RB_NEXT(Node* elm) {
636 return elm; 690 return elm;
637} 691}
638 692
639template <typename Node> 693template <typename T>
640Node* RB_PREV(Node* elm) { 694requires HasRBEntry<T>
695constexpr T* RB_PREV(T* elm) {
641 if (RB_LEFT(elm)) { 696 if (RB_LEFT(elm)) {
642 elm = RB_LEFT(elm); 697 elm = RB_LEFT(elm);
643 while (RB_RIGHT(elm)) { 698 while (RB_RIGHT(elm)) {
@@ -656,30 +711,32 @@ Node* RB_PREV(Node* elm) {
656 return elm; 711 return elm;
657} 712}
658 713
659template <typename Node> 714template <typename T>
660Node* RB_MINMAX(RBHead<Node>* head, bool is_min) { 715requires HasRBEntry<T>
661 Node* tmp = head->Root(); 716constexpr T* RB_MIN(RBHead<T>& head) {
662 Node* parent = nullptr; 717 T* tmp = head.Root();
718 T* parent = nullptr;
663 719
664 while (tmp) { 720 while (tmp) {
665 parent = tmp; 721 parent = tmp;
666 if (is_min) { 722 tmp = RB_LEFT(tmp);
667 tmp = RB_LEFT(tmp);
668 } else {
669 tmp = RB_RIGHT(tmp);
670 }
671 } 723 }
672 724
673 return parent; 725 return parent;
674} 726}
675 727
676template <typename Node> 728template <typename T>
677Node* RB_MIN(RBHead<Node>* head) { 729requires HasRBEntry<T>
678 return RB_MINMAX(head, true); 730constexpr T* RB_MAX(RBHead<T>& head) {
679} 731 T* tmp = head.Root();
732 T* parent = nullptr;
680 733
681template <typename Node> 734 while (tmp) {
682Node* RB_MAX(RBHead<Node>* head) { 735 parent = tmp;
683 return RB_MINMAX(head, false); 736 tmp = RB_RIGHT(tmp);
737 }
738
739 return parent;
684} 740}
685} // namespace Common 741
742} // namespace Common::freebsd
HIC SVNT DRACONES