summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGravatar bunnei2020-12-27 01:58:16 -0800
committerGravatar bunnei2021-01-11 14:23:16 -0800
commitfb43b8efd22eaf0eaccf0c9ddc70cf2e06deafeb (patch)
tree021d00f3bcdca20b1e573d9ce91cfbbe9e06b562
parentcore: hle: kernel: Update KSynchronizationObject. (diff)
downloadyuzu-fb43b8efd22eaf0eaccf0c9ddc70cf2e06deafeb.tar.gz
yuzu-fb43b8efd22eaf0eaccf0c9ddc70cf2e06deafeb.tar.xz
yuzu-fb43b8efd22eaf0eaccf0c9ddc70cf2e06deafeb.zip
common: Introduce useful tree structures.
Diffstat
-rw-r--r--src/common/CMakeLists.txt3
-rw-r--r--src/common/intrusive_red_black_tree.h627
-rw-r--r--src/common/parent_of_member.h189
-rw-r--r--src/common/tree.h822
4 files changed, 1641 insertions, 0 deletions
diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt
index 2c2bd2ee8..5d781cd77 100644
--- a/src/common/CMakeLists.txt
+++ b/src/common/CMakeLists.txt
@@ -123,6 +123,7 @@ add_library(common STATIC
123 hash.h 123 hash.h
124 hex_util.cpp 124 hex_util.cpp
125 hex_util.h 125 hex_util.h
126 intrusive_red_black_tree.h
126 logging/backend.cpp 127 logging/backend.cpp
127 logging/backend.h 128 logging/backend.h
128 logging/filter.cpp 129 logging/filter.cpp
@@ -143,6 +144,7 @@ add_library(common STATIC
143 page_table.h 144 page_table.h
144 param_package.cpp 145 param_package.cpp
145 param_package.h 146 param_package.h
147 parent_of_member.h
146 quaternion.h 148 quaternion.h
147 ring_buffer.h 149 ring_buffer.h
148 scm_rev.cpp 150 scm_rev.cpp
@@ -167,6 +169,7 @@ add_library(common STATIC
167 time_zone.h 169 time_zone.h
168 timer.cpp 170 timer.cpp
169 timer.h 171 timer.h
172 tree.h
170 uint128.cpp 173 uint128.cpp
171 uint128.h 174 uint128.h
172 uuid.cpp 175 uuid.cpp
diff --git a/src/common/intrusive_red_black_tree.h b/src/common/intrusive_red_black_tree.h
new file mode 100644
index 000000000..929b5497e
--- /dev/null
+++ b/src/common/intrusive_red_black_tree.h
@@ -0,0 +1,627 @@
1// Copyright 2021 yuzu Emulator Project
2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included.
4
5#pragma once
6
7#include "common/parent_of_member.h"
8#include "common/tree.h"
9
10namespace Common {
11
12namespace impl {
13
14class IntrusiveRedBlackTreeImpl;
15
16}
17
18struct IntrusiveRedBlackTreeNode {
19
20private:
21 RB_ENTRY(IntrusiveRedBlackTreeNode) entry{};
22
23 friend class impl::IntrusiveRedBlackTreeImpl;
24
25 template <class, class, class>
26 friend class IntrusiveRedBlackTree;
27
28public:
29 constexpr IntrusiveRedBlackTreeNode() = default;
30};
31
32template <class T, class Traits, class Comparator>
33class IntrusiveRedBlackTree;
34
35namespace impl {
36
37class IntrusiveRedBlackTreeImpl {
38
39private:
40 template <class, class, class>
41 friend class ::Common::IntrusiveRedBlackTree;
42
43private:
44 RB_HEAD(IntrusiveRedBlackTreeRoot, IntrusiveRedBlackTreeNode);
45 using RootType = IntrusiveRedBlackTreeRoot;
46
47private:
48 IntrusiveRedBlackTreeRoot root;
49
50public:
51 template <bool Const>
52 class Iterator;
53
54 using value_type = IntrusiveRedBlackTreeNode;
55 using size_type = size_t;
56 using difference_type = ptrdiff_t;
57 using pointer = value_type*;
58 using const_pointer = const value_type*;
59 using reference = value_type&;
60 using const_reference = const value_type&;
61 using iterator = Iterator<false>;
62 using const_iterator = Iterator<true>;
63
64 template <bool Const>
65 class Iterator {
66 public:
67 using iterator_category = std::bidirectional_iterator_tag;
68 using value_type = typename IntrusiveRedBlackTreeImpl::value_type;
69 using difference_type = typename IntrusiveRedBlackTreeImpl::difference_type;
70 using pointer = std::conditional_t<Const, IntrusiveRedBlackTreeImpl::const_pointer,
71 IntrusiveRedBlackTreeImpl::pointer>;
72 using reference = std::conditional_t<Const, IntrusiveRedBlackTreeImpl::const_reference,
73 IntrusiveRedBlackTreeImpl::reference>;
74
75 private:
76 pointer node;
77
78 public:
79 explicit Iterator(pointer n) : node(n) {}
80
81 bool operator==(const Iterator& rhs) const {
82 return this->node == rhs.node;
83 }
84
85 bool operator!=(const Iterator& rhs) const {
86 return !(*this == rhs);
87 }
88
89 pointer operator->() const {
90 return this->node;
91 }
92
93 reference operator*() const {
94 return *this->node;
95 }
96
97 Iterator& operator++() {
98 this->node = GetNext(this->node);
99 return *this;
100 }
101
102 Iterator& operator--() {
103 this->node = GetPrev(this->node);
104 return *this;
105 }
106
107 Iterator operator++(int) {
108 const Iterator it{*this};
109 ++(*this);
110 return it;
111 }
112
113 Iterator operator--(int) {
114 const Iterator it{*this};
115 --(*this);
116 return it;
117 }
118
119 operator Iterator<true>() const {
120 return Iterator<true>(this->node);
121 }
122 };
123
124protected:
125 // Generate static implementations for non-comparison operations for IntrusiveRedBlackTreeRoot.
126 RB_GENERATE_WITHOUT_COMPARE_STATIC(IntrusiveRedBlackTreeRoot, IntrusiveRedBlackTreeNode, entry);
127
128private:
129 // Define accessors using RB_* functions.
130 constexpr void InitializeImpl() {
131 RB_INIT(&this->root);
132 }
133
134 bool EmptyImpl() const {
135 return RB_EMPTY(&this->root);
136 }
137
138 IntrusiveRedBlackTreeNode* GetMinImpl() const {
139 return RB_MIN(IntrusiveRedBlackTreeRoot,
140 const_cast<IntrusiveRedBlackTreeRoot*>(&this->root));
141 }
142
143 IntrusiveRedBlackTreeNode* GetMaxImpl() const {
144 return RB_MAX(IntrusiveRedBlackTreeRoot,
145 const_cast<IntrusiveRedBlackTreeRoot*>(&this->root));
146 }
147
148 IntrusiveRedBlackTreeNode* RemoveImpl(IntrusiveRedBlackTreeNode* node) {
149 return RB_REMOVE(IntrusiveRedBlackTreeRoot, &this->root, node);
150 }
151
152public:
153 static IntrusiveRedBlackTreeNode* GetNext(IntrusiveRedBlackTreeNode* node) {
154 return RB_NEXT(IntrusiveRedBlackTreeRoot, nullptr, node);
155 }
156
157 static IntrusiveRedBlackTreeNode* GetPrev(IntrusiveRedBlackTreeNode* node) {
158 return RB_PREV(IntrusiveRedBlackTreeRoot, nullptr, node);
159 }
160
161 static IntrusiveRedBlackTreeNode const* GetNext(const IntrusiveRedBlackTreeNode* node) {
162 return static_cast<const IntrusiveRedBlackTreeNode*>(
163 GetNext(const_cast<IntrusiveRedBlackTreeNode*>(node)));
164 }
165
166 static IntrusiveRedBlackTreeNode const* GetPrev(const IntrusiveRedBlackTreeNode* node) {
167 return static_cast<const IntrusiveRedBlackTreeNode*>(
168 GetPrev(const_cast<IntrusiveRedBlackTreeNode*>(node)));
169 }
170
171public:
172 constexpr IntrusiveRedBlackTreeImpl() : root() {
173 this->InitializeImpl();
174 }
175
176 // Iterator accessors.
177 iterator begin() {
178 return iterator(this->GetMinImpl());
179 }
180
181 const_iterator begin() const {
182 return const_iterator(this->GetMinImpl());
183 }
184
185 iterator end() {
186 return iterator(static_cast<IntrusiveRedBlackTreeNode*>(nullptr));
187 }
188
189 const_iterator end() const {
190 return const_iterator(static_cast<const IntrusiveRedBlackTreeNode*>(nullptr));
191 }
192
193 const_iterator cbegin() const {
194 return this->begin();
195 }
196
197 const_iterator cend() const {
198 return this->end();
199 }
200
201 iterator iterator_to(reference ref) {
202 return iterator(&ref);
203 }
204
205 const_iterator iterator_to(const_reference ref) const {
206 return const_iterator(&ref);
207 }
208
209 // Content management.
210 bool empty() const {
211 return this->EmptyImpl();
212 }
213
214 reference back() {
215 return *this->GetMaxImpl();
216 }
217
218 const_reference back() const {
219 return *this->GetMaxImpl();
220 }
221
222 reference front() {
223 return *this->GetMinImpl();
224 }
225
226 const_reference front() const {
227 return *this->GetMinImpl();
228 }
229
230 iterator erase(iterator it) {
231 auto cur = std::addressof(*it);
232 auto next = GetNext(cur);
233 this->RemoveImpl(cur);
234 return iterator(next);
235 }
236};
237
238} // namespace impl
239
240template <typename T>
241concept HasLightCompareType = requires {
242 { std::is_same<typename T::LightCompareType, void>::value }
243 ->std::convertible_to<bool>;
244};
245
246namespace impl {
247
248template <typename T, typename Default>
249consteval auto* GetLightCompareType() {
250 if constexpr (HasLightCompareType<T>) {
251 return static_cast<typename T::LightCompareType*>(nullptr);
252 } else {
253 return static_cast<Default*>(nullptr);
254 }
255}
256
257} // namespace impl
258
259template <typename T, typename Default>
260using LightCompareType = std::remove_pointer_t<decltype(impl::GetLightCompareType<T, Default>())>;
261
262template <class T, class Traits, class Comparator>
263class IntrusiveRedBlackTree {
264
265public:
266 using ImplType = impl::IntrusiveRedBlackTreeImpl;
267
268private:
269 ImplType impl{};
270
271public:
272 struct IntrusiveRedBlackTreeRootWithCompare : ImplType::IntrusiveRedBlackTreeRoot {};
273
274 template <bool Const>
275 class Iterator;
276
277 using value_type = T;
278 using size_type = size_t;
279 using difference_type = ptrdiff_t;
280 using pointer = T*;
281 using const_pointer = const T*;
282 using reference = T&;
283 using const_reference = const T&;
284 using iterator = Iterator<false>;
285 using const_iterator = Iterator<true>;
286
287 using light_value_type = LightCompareType<Comparator, value_type>;
288 using const_light_pointer = const light_value_type*;
289 using const_light_reference = const light_value_type&;
290
291 template <bool Const>
292 class Iterator {
293 public:
294 friend class IntrusiveRedBlackTree<T, Traits, Comparator>;
295
296 using ImplIterator =
297 std::conditional_t<Const, ImplType::const_iterator, ImplType::iterator>;
298
299 using iterator_category = std::bidirectional_iterator_tag;
300 using value_type = typename IntrusiveRedBlackTree::value_type;
301 using difference_type = typename IntrusiveRedBlackTree::difference_type;
302 using pointer = std::conditional_t<Const, IntrusiveRedBlackTree::const_pointer,
303 IntrusiveRedBlackTree::pointer>;
304 using reference = std::conditional_t<Const, IntrusiveRedBlackTree::const_reference,
305 IntrusiveRedBlackTree::reference>;
306
307 private:
308 ImplIterator iterator;
309
310 private:
311 explicit Iterator(ImplIterator it) : iterator(it) {}
312
313 explicit Iterator(typename std::conditional<Const, ImplType::const_iterator,
314 ImplType::iterator>::type::pointer ptr)
315 : iterator(ptr) {}
316
317 ImplIterator GetImplIterator() const {
318 return this->iterator;
319 }
320
321 public:
322 bool operator==(const Iterator& rhs) const {
323 return this->iterator == rhs.iterator;
324 }
325
326 bool operator!=(const Iterator& rhs) const {
327 return !(*this == rhs);
328 }
329
330 pointer operator->() const {
331 return Traits::GetParent(std::addressof(*this->iterator));
332 }
333
334 reference operator*() const {
335 return *Traits::GetParent(std::addressof(*this->iterator));
336 }
337
338 Iterator& operator++() {
339 ++this->iterator;
340 return *this;
341 }
342
343 Iterator& operator--() {
344 --this->iterator;
345 return *this;
346 }
347
348 Iterator operator++(int) {
349 const Iterator it{*this};
350 ++this->iterator;
351 return it;
352 }
353
354 Iterator operator--(int) {
355 const Iterator it{*this};
356 --this->iterator;
357 return it;
358 }
359
360 operator Iterator<true>() const {
361 return Iterator<true>(this->iterator);
362 }
363 };
364
365private:
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,
372 const IntrusiveRedBlackTreeNode* rhs) {
373 return Comparator::Compare(*Traits::GetParent(lhs), *Traits::GetParent(rhs));
374 }
375
376 static int LightCompareImpl(const void* elm, const IntrusiveRedBlackTreeNode* rhs) {
377 return Comparator::Compare(*static_cast<const_light_pointer>(elm), *Traits::GetParent(rhs));
378 }
379
380 // Define accessors using RB_* functions.
381 IntrusiveRedBlackTreeNode* InsertImpl(IntrusiveRedBlackTreeNode* node) {
382 return RB_INSERT(IntrusiveRedBlackTreeRootWithCompare,
383 static_cast<IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root),
384 node);
385 }
386
387 IntrusiveRedBlackTreeNode* FindImpl(const IntrusiveRedBlackTreeNode* node) const {
388 return RB_FIND(
389 IntrusiveRedBlackTreeRootWithCompare,
390 const_cast<IntrusiveRedBlackTreeRootWithCompare*>(
391 static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)),
392 const_cast<IntrusiveRedBlackTreeNode*>(node));
393 }
394
395 IntrusiveRedBlackTreeNode* NFindImpl(const IntrusiveRedBlackTreeNode* node) const {
396 return RB_NFIND(
397 IntrusiveRedBlackTreeRootWithCompare,
398 const_cast<IntrusiveRedBlackTreeRootWithCompare*>(
399 static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)),
400 const_cast<IntrusiveRedBlackTreeNode*>(node));
401 }
402
403 IntrusiveRedBlackTreeNode* FindLightImpl(const_light_pointer lelm) const {
404 return RB_FIND_LIGHT(
405 IntrusiveRedBlackTreeRootWithCompare,
406 const_cast<IntrusiveRedBlackTreeRootWithCompare*>(
407 static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)),
408 static_cast<const void*>(lelm));
409 }
410
411 IntrusiveRedBlackTreeNode* NFindLightImpl(const_light_pointer lelm) const {
412 return RB_NFIND_LIGHT(
413 IntrusiveRedBlackTreeRootWithCompare,
414 const_cast<IntrusiveRedBlackTreeRootWithCompare*>(
415 static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)),
416 static_cast<const void*>(lelm));
417 }
418
419public:
420 constexpr IntrusiveRedBlackTree() = default;
421
422 // Iterator accessors.
423 iterator begin() {
424 return iterator(this->impl.begin());
425 }
426
427 const_iterator begin() const {
428 return const_iterator(this->impl.begin());
429 }
430
431 iterator end() {
432 return iterator(this->impl.end());
433 }
434
435 const_iterator end() const {
436 return const_iterator(this->impl.end());
437 }
438
439 const_iterator cbegin() const {
440 return this->begin();
441 }
442
443 const_iterator cend() const {
444 return this->end();
445 }
446
447 iterator iterator_to(reference ref) {
448 return iterator(this->impl.iterator_to(*Traits::GetNode(std::addressof(ref))));
449 }
450
451 const_iterator iterator_to(const_reference ref) const {
452 return const_iterator(this->impl.iterator_to(*Traits::GetNode(std::addressof(ref))));
453 }
454
455 // Content management.
456 bool empty() const {
457 return this->impl.empty();
458 }
459
460 reference back() {
461 return *Traits::GetParent(std::addressof(this->impl.back()));
462 }
463
464 const_reference back() const {
465 return *Traits::GetParent(std::addressof(this->impl.back()));
466 }
467
468 reference front() {
469 return *Traits::GetParent(std::addressof(this->impl.front()));
470 }
471
472 const_reference front() const {
473 return *Traits::GetParent(std::addressof(this->impl.front()));
474 }
475
476 iterator erase(iterator it) {
477 return iterator(this->impl.erase(it.GetImplIterator()));
478 }
479
480 iterator insert(reference ref) {
481 ImplType::pointer node = Traits::GetNode(std::addressof(ref));
482 this->InsertImpl(node);
483 return iterator(node);
484 }
485
486 iterator find(const_reference ref) const {
487 return iterator(this->FindImpl(Traits::GetNode(std::addressof(ref))));
488 }
489
490 iterator nfind(const_reference ref) const {
491 return iterator(this->NFindImpl(Traits::GetNode(std::addressof(ref))));
492 }
493
494 iterator find_light(const_light_reference ref) const {
495 return iterator(this->FindLightImpl(std::addressof(ref)));
496 }
497
498 iterator nfind_light(const_light_reference ref) const {
499 return iterator(this->NFindLightImpl(std::addressof(ref)));
500 }
501};
502
503template <auto T, class Derived = impl::GetParentType<T>>
504class IntrusiveRedBlackTreeMemberTraits;
505
506template <class Parent, IntrusiveRedBlackTreeNode Parent::*Member, class Derived>
507class IntrusiveRedBlackTreeMemberTraits<Member, Derived> {
508public:
509 template <class Comparator>
510 using TreeType = IntrusiveRedBlackTree<Derived, IntrusiveRedBlackTreeMemberTraits, Comparator>;
511 using TreeTypeImpl = impl::IntrusiveRedBlackTreeImpl;
512
513private:
514 template <class, class, class>
515 friend class IntrusiveRedBlackTree;
516
517 friend class impl::IntrusiveRedBlackTreeImpl;
518
519 static constexpr IntrusiveRedBlackTreeNode* GetNode(Derived* parent) {
520 return std::addressof(parent->*Member);
521 }
522
523 static constexpr IntrusiveRedBlackTreeNode const* GetNode(Derived const* parent) {
524 return std::addressof(parent->*Member);
525 }
526
527 static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
528 return GetParentPointer<Member, Derived>(node);
529 }
530
531 static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) {
532 return GetParentPointer<Member, Derived>(node);
533 }
534
535private:
536 static constexpr TYPED_STORAGE(Derived) DerivedStorage = {};
537 static_assert(GetParent(GetNode(GetPointer(DerivedStorage))) == GetPointer(DerivedStorage));
538};
539
540template <auto T, class Derived = impl::GetParentType<T>>
541class IntrusiveRedBlackTreeMemberTraitsDeferredAssert;
542
543template <class Parent, IntrusiveRedBlackTreeNode Parent::*Member, class Derived>
544class IntrusiveRedBlackTreeMemberTraitsDeferredAssert<Member, Derived> {
545public:
546 template <class Comparator>
547 using TreeType =
548 IntrusiveRedBlackTree<Derived, IntrusiveRedBlackTreeMemberTraitsDeferredAssert, Comparator>;
549 using TreeTypeImpl = impl::IntrusiveRedBlackTreeImpl;
550
551 static constexpr bool IsValid() {
552 TYPED_STORAGE(Derived) DerivedStorage = {};
553 return GetParent(GetNode(GetPointer(DerivedStorage))) == GetPointer(DerivedStorage);
554 }
555
556private:
557 template <class, class, class>
558 friend class IntrusiveRedBlackTree;
559
560 friend class impl::IntrusiveRedBlackTreeImpl;
561
562 static constexpr IntrusiveRedBlackTreeNode* GetNode(Derived* parent) {
563 return std::addressof(parent->*Member);
564 }
565
566 static constexpr IntrusiveRedBlackTreeNode const* GetNode(Derived const* parent) {
567 return std::addressof(parent->*Member);
568 }
569
570 static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
571 return GetParentPointer<Member, Derived>(node);
572 }
573
574 static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) {
575 return GetParentPointer<Member, Derived>(node);
576 }
577};
578
579template <class Derived>
580class IntrusiveRedBlackTreeBaseNode : public IntrusiveRedBlackTreeNode {
581public:
582 constexpr Derived* GetPrev() {
583 return static_cast<Derived*>(impl::IntrusiveRedBlackTreeImpl::GetPrev(this));
584 }
585 constexpr const Derived* GetPrev() const {
586 return static_cast<const Derived*>(impl::IntrusiveRedBlackTreeImpl::GetPrev(this));
587 }
588
589 constexpr Derived* GetNext() {
590 return static_cast<Derived*>(impl::IntrusiveRedBlackTreeImpl::GetNext(this));
591 }
592 constexpr const Derived* GetNext() const {
593 return static_cast<const Derived*>(impl::IntrusiveRedBlackTreeImpl::GetNext(this));
594 }
595};
596
597template <class Derived>
598class IntrusiveRedBlackTreeBaseTraits {
599public:
600 template <class Comparator>
601 using TreeType = IntrusiveRedBlackTree<Derived, IntrusiveRedBlackTreeBaseTraits, Comparator>;
602 using TreeTypeImpl = impl::IntrusiveRedBlackTreeImpl;
603
604private:
605 template <class, class, class>
606 friend class IntrusiveRedBlackTree;
607
608 friend class impl::IntrusiveRedBlackTreeImpl;
609
610 static constexpr IntrusiveRedBlackTreeNode* GetNode(Derived* parent) {
611 return static_cast<IntrusiveRedBlackTreeNode*>(parent);
612 }
613
614 static constexpr IntrusiveRedBlackTreeNode const* GetNode(Derived const* parent) {
615 return static_cast<const IntrusiveRedBlackTreeNode*>(parent);
616 }
617
618 static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
619 return static_cast<Derived*>(node);
620 }
621
622 static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) {
623 return static_cast<const Derived*>(node);
624 }
625};
626
627} // namespace Common
diff --git a/src/common/parent_of_member.h b/src/common/parent_of_member.h
new file mode 100644
index 000000000..1af31ee44
--- /dev/null
+++ b/src/common/parent_of_member.h
@@ -0,0 +1,189 @@
1// Copyright 2021 yuzu Emulator Project
2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included.
4
5#pragma once
6
7#include <type_traits>
8
9#include "common/assert.h"
10#include "common/common_types.h"
11
12namespace Common {
13
14template <typename T, size_t Size, size_t Align>
15struct TypedStorage {
16 std::aligned_storage_t<Size, Align> storage_;
17};
18
19#define TYPED_STORAGE(...) TypedStorage<__VA_ARGS__, sizeof(__VA_ARGS__), alignof(__VA_ARGS__)>
20
21template <typename T>
22static constexpr T* GetPointer(TYPED_STORAGE(T) & ts) {
23 return static_cast<T*>(static_cast<void*>(std::addressof(ts.storage_)));
24}
25
26template <typename T>
27static constexpr const T* GetPointer(const TYPED_STORAGE(T) & ts) {
28 return static_cast<const T*>(static_cast<const void*>(std::addressof(ts.storage_)));
29}
30
31namespace impl {
32
33template <size_t MaxDepth>
34struct OffsetOfUnionHolder {
35 template <typename ParentType, typename MemberType, size_t Offset>
36 union UnionImpl {
37 using PaddingMember = char;
38 static constexpr size_t GetOffset() {
39 return Offset;
40 }
41
42#pragma pack(push, 1)
43 struct {
44 PaddingMember padding[Offset];
45 MemberType members[(sizeof(ParentType) / sizeof(MemberType)) + 1];
46 } data;
47#pragma pack(pop)
48 UnionImpl<ParentType, MemberType, Offset + 1> next_union;
49 };
50
51 template <typename ParentType, typename MemberType>
52 union UnionImpl<ParentType, MemberType, 0> {
53 static constexpr size_t GetOffset() {
54 return 0;
55 }
56
57 struct {
58 MemberType members[(sizeof(ParentType) / sizeof(MemberType)) + 1];
59 } data;
60 UnionImpl<ParentType, MemberType, 1> next_union;
61 };
62
63 template <typename ParentType, typename MemberType>
64 union UnionImpl<ParentType, MemberType, MaxDepth> {};
65};
66
67template <typename ParentType, typename MemberType>
68struct OffsetOfCalculator {
69 using UnionHolder =
70 typename OffsetOfUnionHolder<sizeof(MemberType)>::template UnionImpl<ParentType, MemberType,
71 0>;
72 union Union {
73 char c{};
74 UnionHolder first_union;
75 TYPED_STORAGE(ParentType) parent;
76
77 constexpr Union() : c() {}
78 };
79 static constexpr Union U = {};
80
81 static constexpr const MemberType* GetNextAddress(const MemberType* start,
82 const MemberType* target) {
83 while (start < target) {
84 start++;
85 }
86 return start;
87 }
88
89 static constexpr std::ptrdiff_t GetDifference(const MemberType* start,
90 const MemberType* target) {
91 return (target - start) * sizeof(MemberType);
92 }
93
94 template <typename CurUnion>
95 static constexpr std::ptrdiff_t OffsetOfImpl(MemberType ParentType::*member,
96 CurUnion& cur_union) {
97 constexpr size_t Offset = CurUnion::GetOffset();
98 const auto target = std::addressof(GetPointer(U.parent)->*member);
99 const auto start = std::addressof(cur_union.data.members[0]);
100 const auto next = GetNextAddress(start, target);
101
102 if (next != target) {
103 if constexpr (Offset < sizeof(MemberType) - 1) {
104 return OffsetOfImpl(member, cur_union.next_union);
105 } else {
106 UNREACHABLE();
107 }
108 }
109
110 return (next - start) * sizeof(MemberType) + Offset;
111 }
112
113 static constexpr std::ptrdiff_t OffsetOf(MemberType ParentType::*member) {
114 return OffsetOfImpl(member, U.first_union);
115 }
116};
117
118template <typename T>
119struct GetMemberPointerTraits;
120
121template <typename P, typename M>
122struct GetMemberPointerTraits<M P::*> {
123 using Parent = P;
124 using Member = M;
125};
126
127template <auto MemberPtr>
128using GetParentType = typename GetMemberPointerTraits<decltype(MemberPtr)>::Parent;
129
130template <auto MemberPtr>
131using GetMemberType = typename GetMemberPointerTraits<decltype(MemberPtr)>::Member;
132
133template <auto MemberPtr, typename RealParentType = GetParentType<MemberPtr>>
134static inline std::ptrdiff_t OffsetOf = [] {
135 using DeducedParentType = GetParentType<MemberPtr>;
136 using MemberType = GetMemberType<MemberPtr>;
137 static_assert(std::is_base_of<DeducedParentType, RealParentType>::value ||
138 std::is_same<RealParentType, DeducedParentType>::value);
139
140 return OffsetOfCalculator<RealParentType, MemberType>::OffsetOf(MemberPtr);
141}();
142
143} // namespace impl
144
145template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
146constexpr RealParentType& GetParentReference(impl::GetMemberType<MemberPtr>* member) {
147 std::ptrdiff_t Offset = impl::OffsetOf<MemberPtr, RealParentType>;
148 return *static_cast<RealParentType*>(
149 static_cast<void*>(static_cast<uint8_t*>(static_cast<void*>(member)) - Offset));
150}
151
152template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
153constexpr RealParentType const& GetParentReference(impl::GetMemberType<MemberPtr> const* member) {
154 std::ptrdiff_t Offset = impl::OffsetOf<MemberPtr, RealParentType>;
155 return *static_cast<const RealParentType*>(static_cast<const void*>(
156 static_cast<const uint8_t*>(static_cast<const void*>(member)) - Offset));
157}
158
159template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
160constexpr RealParentType* GetParentPointer(impl::GetMemberType<MemberPtr>* member) {
161 return std::addressof(GetParentReference<MemberPtr, RealParentType>(member));
162}
163
164template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
165constexpr RealParentType const* GetParentPointer(impl::GetMemberType<MemberPtr> const* member) {
166 return std::addressof(GetParentReference<MemberPtr, RealParentType>(member));
167}
168
169template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
170constexpr RealParentType& GetParentReference(impl::GetMemberType<MemberPtr>& member) {
171 return GetParentReference<MemberPtr, RealParentType>(std::addressof(member));
172}
173
174template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
175constexpr RealParentType const& GetParentReference(impl::GetMemberType<MemberPtr> const& member) {
176 return GetParentReference<MemberPtr, RealParentType>(std::addressof(member));
177}
178
179template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
180constexpr RealParentType* GetParentPointer(impl::GetMemberType<MemberPtr>& member) {
181 return std::addressof(GetParentReference<MemberPtr, RealParentType>(member));
182}
183
184template <auto MemberPtr, typename RealParentType = impl::GetParentType<MemberPtr>>
185constexpr RealParentType const* GetParentPointer(impl::GetMemberType<MemberPtr> const& member) {
186 return std::addressof(GetParentReference<MemberPtr, RealParentType>(member));
187}
188
189} // namespace Common
diff --git a/src/common/tree.h b/src/common/tree.h
new file mode 100644
index 000000000..a6b636646
--- /dev/null
+++ b/src/common/tree.h
@@ -0,0 +1,822 @@
1/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */
2/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
3/* $FreeBSD$ */
4
5/*-
6 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30#ifndef _SYS_TREE_H_
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
42/*
43 * This file defines data structures for different types of 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 *
58 * A red-black tree is a binary search tree with the node color as an
59 * extra attribute. It fulfills a set of conditions:
60 * - every search path from the root to a leaf consists of the
61 * same number of black nodes,
62 * - each red node (except for the root) has a black parent,
63 * - each leaf node is black.
64 *
65 * Every operation on a red-black tree is bounded as O(lg n).
66 * The maximum height of a red-black tree is 2lg (n+1).
67 */
68
69#define SPLAY_HEAD(name, type) \
70 struct name { \
71 struct type* sph_root; /* root of the tree */ \
72 }
73
74#define SPLAY_INITIALIZER(root) \
75 { NULL }
76
77#define SPLAY_INIT(root) \
78 do { \
79 (root)->sph_root = NULL; \
80 } while (/*CONSTCOND*/ 0)
81
82#define SPLAY_ENTRY(type) \
83 struct { \
84 struct type* spe_left; /* left element */ \
85 struct type* spe_right; /* right element */ \
86 }
87
88#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
89#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
90#define SPLAY_ROOT(head) (head)->sph_root
91#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
92
93/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
94#define SPLAY_ROTATE_RIGHT(head, tmp, field) \
95 do { \
96 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
97 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
98 (head)->sph_root = tmp; \
99 } while (/*CONSTCOND*/ 0)
100
101#define SPLAY_ROTATE_LEFT(head, tmp, field) \
102 do { \
103 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
104 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
105 (head)->sph_root = tmp; \
106 } while (/*CONSTCOND*/ 0)
107
108#define SPLAY_LINKLEFT(head, tmp, field) \
109 do { \
110 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
111 tmp = (head)->sph_root; \
112 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
113 } while (/*CONSTCOND*/ 0)
114
115#define SPLAY_LINKRIGHT(head, tmp, field) \
116 do { \
117 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
118 tmp = (head)->sph_root; \
119 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
120 } while (/*CONSTCOND*/ 0)
121
122#define SPLAY_ASSEMBLE(head, node, left, right, field) \
123 do { \
124 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
125 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field); \
126 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
127 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
128 } while (/*CONSTCOND*/ 0)
129
130/* Generates prototypes and inline functions */
131
132#define SPLAY_PROTOTYPE(name, type, field, cmp) \
133 void name##_SPLAY(struct name*, struct type*); \
134 void name##_SPLAY_MINMAX(struct name*, int); \
135 struct type* name##_SPLAY_INSERT(struct name*, struct type*); \
136 struct type* name##_SPLAY_REMOVE(struct name*, struct type*); \
137 \
138 /* Finds the node with the same key as elm */ \
139 static __inline struct type* name##_SPLAY_FIND(struct name* head, struct type* elm) { \
140 if (SPLAY_EMPTY(head)) \
141 return (NULL); \
142 name##_SPLAY(head, elm); \
143 if ((cmp)(elm, (head)->sph_root) == 0) \
144 return (head->sph_root); \
145 return (NULL); \
146 } \
147 \
148 static __inline struct type* name##_SPLAY_NEXT(struct name* head, struct type* elm) { \
149 name##_SPLAY(head, elm); \
150 if (SPLAY_RIGHT(elm, field) != NULL) { \
151 elm = SPLAY_RIGHT(elm, field); \
152 while (SPLAY_LEFT(elm, field) != NULL) { \
153 elm = SPLAY_LEFT(elm, field); \
154 } \
155 } else \
156 elm = NULL; \
157 return (elm); \
158 } \
159 \
160 static __inline struct type* name##_SPLAY_MIN_MAX(struct name* head, int val) { \
161 name##_SPLAY_MINMAX(head, val); \
162 return (SPLAY_ROOT(head)); \
163 }
164
165/* Main splay operation.
166 * Moves node close to the key of elm to top
167 */
168#define SPLAY_GENERATE(name, type, field, cmp) \
169 struct type* name##_SPLAY_INSERT(struct name* head, struct type* elm) { \
170 if (SPLAY_EMPTY(head)) { \
171 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
172 } else { \
173 int __comp; \
174 name##_SPLAY(head, elm); \
175 __comp = (cmp)(elm, (head)->sph_root); \
176 if (__comp < 0) { \
177 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field); \
178 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
179 SPLAY_LEFT((head)->sph_root, field) = NULL; \
180 } else if (__comp > 0) { \
181 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field); \
182 SPLAY_LEFT(elm, field) = (head)->sph_root; \
183 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
184 } else \
185 return ((head)->sph_root); \
186 } \
187 (head)->sph_root = (elm); \
188 return (NULL); \
189 } \
190 \
191 struct type* name##_SPLAY_REMOVE(struct name* head, struct type* elm) { \
192 struct type* __tmp; \
193 if (SPLAY_EMPTY(head)) \
194 return (NULL); \
195 name##_SPLAY(head, elm); \
196 if ((cmp)(elm, (head)->sph_root) == 0) { \
197 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
198 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
199 } else { \
200 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
201 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
202 name##_SPLAY(head, elm); \
203 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
204 } \
205 return (elm); \
206 } \
207 return (NULL); \
208 } \
209 \
210 void name##_SPLAY(struct name* head, struct type* elm) { \
211 struct type __node, *__left, *__right, *__tmp; \
212 int __comp; \
213 \
214 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \
215 __left = __right = &__node; \
216 \
217 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \
218 if (__comp < 0) { \
219 __tmp = SPLAY_LEFT((head)->sph_root, field); \
220 if (__tmp == NULL) \
221 break; \
222 if ((cmp)(elm, __tmp) < 0) { \
223 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
224 if (SPLAY_LEFT((head)->sph_root, field) == NULL) \
225 break; \
226 } \
227 SPLAY_LINKLEFT(head, __right, field); \
228 } else if (__comp > 0) { \
229 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
230 if (__tmp == NULL) \
231 break; \
232 if ((cmp)(elm, __tmp) > 0) { \
233 SPLAY_ROTATE_LEFT(head, __tmp, field); \
234 if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \
235 break; \
236 } \
237 SPLAY_LINKRIGHT(head, __left, field); \
238 } \
239 } \
240 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
241 } \
242 \
243 /* Splay with either the minimum or the maximum element \
244 * Used to find minimum or maximum element in tree. \
245 */ \
246 void name##_SPLAY_MINMAX(struct name* head, int __comp) { \
247 struct type __node, *__left, *__right, *__tmp; \
248 \
249 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \
250 __left = __right = &__node; \
251 \
252 while (1) { \
253 if (__comp < 0) { \
254 __tmp = SPLAY_LEFT((head)->sph_root, field); \
255 if (__tmp == NULL) \
256 break; \
257 if (__comp < 0) { \
258 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
259 if (SPLAY_LEFT((head)->sph_root, field) == NULL) \
260 break; \
261 } \
262 SPLAY_LINKLEFT(head, __right, field); \
263 } else if (__comp > 0) { \
264 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
265 if (__tmp == NULL) \
266 break; \
267 if (__comp > 0) { \
268 SPLAY_ROTATE_LEFT(head, __tmp, field); \
269 if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \
270 break; \
271 } \
272 SPLAY_LINKRIGHT(head, __left, field); \
273 } \
274 } \
275 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
276 }
277
278#define SPLAY_NEGINF -1
279#define SPLAY_INF 1
280
281#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
282#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
283#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
284#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
285#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
286#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
287
288#define SPLAY_FOREACH(x, name, head) \
289 for ((x) = SPLAY_MIN(name, head); (x) != NULL; (x) = SPLAY_NEXT(name, head, x))
290
291/* Macros that define a red-black tree */
292#define RB_HEAD(name, type) \
293 struct name { \
294 struct type* rbh_root; /* root of the tree */ \
295 }
296
297#define RB_INITIALIZER(root) \
298 { NULL }
299
300#define RB_INIT(root) \
301 do { \
302 (root)->rbh_root = NULL; \
303 } while (/*CONSTCOND*/ 0)
304
305#define RB_BLACK 0
306#define RB_RED 1
307#define RB_ENTRY(type) \
308 struct { \
309 struct type* rbe_left; /* left element */ \
310 struct type* rbe_right; /* right element */ \
311 struct type* rbe_parent; /* parent element */ \
312 int rbe_color; /* node color */ \
313 }
314
315#define RB_LEFT(elm, field) (elm)->field.rbe_left
316#define RB_RIGHT(elm, field) (elm)->field.rbe_right
317#define RB_PARENT(elm, field) (elm)->field.rbe_parent
318#define RB_COLOR(elm, field) (elm)->field.rbe_color
319#define RB_ROOT(head) (head)->rbh_root
320#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
321
322#define RB_SET(elm, parent, field) \
323 do { \
324 RB_PARENT(elm, field) = parent; \
325 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
326 RB_COLOR(elm, field) = RB_RED; \
327 } while (/*CONSTCOND*/ 0)
328
329#define RB_SET_BLACKRED(black, red, field) \
330 do { \
331 RB_COLOR(black, field) = RB_BLACK; \
332 RB_COLOR(red, field) = RB_RED; \
333 } while (/*CONSTCOND*/ 0)
334
335#ifndef RB_AUGMENT
336#define RB_AUGMENT(x) \
337 do { \
338 } while (0)
339#endif
340
341#define RB_ROTATE_LEFT(head, elm, tmp, field) \
342 do { \
343 (tmp) = RB_RIGHT(elm, field); \
344 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
345 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
346 } \
347 RB_AUGMENT(elm); \
348 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
349 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
350 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
351 else \
352 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
353 } else \
354 (head)->rbh_root = (tmp); \
355 RB_LEFT(tmp, field) = (elm); \
356 RB_PARENT(elm, field) = (tmp); \
357 RB_AUGMENT(tmp); \
358 if ((RB_PARENT(tmp, field))) \
359 RB_AUGMENT(RB_PARENT(tmp, field)); \
360 } while (/*CONSTCOND*/ 0)
361
362#define RB_ROTATE_RIGHT(head, elm, tmp, field) \
363 do { \
364 (tmp) = RB_LEFT(elm, field); \
365 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
366 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
367 } \
368 RB_AUGMENT(elm); \
369 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
370 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
371 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
372 else \
373 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
374 } else \
375 (head)->rbh_root = (tmp); \
376 RB_RIGHT(tmp, field) = (elm); \
377 RB_PARENT(elm, field) = (tmp); \
378 RB_AUGMENT(tmp); \
379 if ((RB_PARENT(tmp, field))) \
380 RB_AUGMENT(RB_PARENT(tmp, field)); \
381 } while (/*CONSTCOND*/ 0)
382
383/* Generates prototypes and inline functions */
384#define RB_PROTOTYPE(name, type, field, cmp) RB_PROTOTYPE_INTERNAL(name, type, field, cmp, )
385#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
386 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, static)
387#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
388 RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
389 RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
390 RB_PROTOTYPE_INSERT(name, type, attr); \
391 RB_PROTOTYPE_REMOVE(name, type, attr); \
392 RB_PROTOTYPE_FIND(name, type, attr); \
393 RB_PROTOTYPE_NFIND(name, type, attr); \
394 RB_PROTOTYPE_FIND_LIGHT(name, type, attr); \
395 RB_PROTOTYPE_NFIND_LIGHT(name, type, attr); \
396 RB_PROTOTYPE_NEXT(name, type, attr); \
397 RB_PROTOTYPE_PREV(name, type, attr); \
398 RB_PROTOTYPE_MINMAX(name, type, attr);
399#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
400 attr void name##_RB_INSERT_COLOR(struct name*, struct type*)
401#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
402 attr void name##_RB_REMOVE_COLOR(struct name*, struct type*, struct type*)
403#define RB_PROTOTYPE_REMOVE(name, type, attr) \
404 attr struct type* name##_RB_REMOVE(struct name*, struct type*)
405#define RB_PROTOTYPE_INSERT(name, type, attr) \
406 attr struct type* name##_RB_INSERT(struct name*, struct type*)
407#define RB_PROTOTYPE_FIND(name, type, attr) \
408 attr struct type* name##_RB_FIND(struct name*, struct type*)
409#define RB_PROTOTYPE_NFIND(name, type, attr) \
410 attr struct type* name##_RB_NFIND(struct name*, struct type*)
411#define RB_PROTOTYPE_FIND_LIGHT(name, type, attr) \
412 attr struct type* name##_RB_FIND_LIGHT(struct name*, const void*)
413#define RB_PROTOTYPE_NFIND_LIGHT(name, type, attr) \
414 attr struct type* name##_RB_NFIND_LIGHT(struct name*, const void*)
415#define RB_PROTOTYPE_NEXT(name, type, attr) attr struct type* name##_RB_NEXT(struct type*)
416#define RB_PROTOTYPE_PREV(name, type, attr) attr struct type* name##_RB_PREV(struct type*)
417#define RB_PROTOTYPE_MINMAX(name, type, attr) attr struct type* name##_RB_MINMAX(struct name*, int)
418
419/* Main rb operation.
420 * Moves node close to the key of elm to top
421 */
422#define RB_GENERATE_WITHOUT_COMPARE(name, type, field) \
423 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, )
424#define RB_GENERATE_WITHOUT_COMPARE_STATIC(name, type, field) \
425 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, static)
426#define RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, attr) \
427 RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
428 RB_GENERATE_REMOVE(name, type, field, attr) \
429 RB_GENERATE_NEXT(name, type, field, attr) \
430 RB_GENERATE_PREV(name, type, field, attr) \
431 RB_GENERATE_MINMAX(name, type, field, attr)
432
433#define RB_GENERATE_WITH_COMPARE(name, type, field, cmp, lcmp) \
434 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, )
435#define RB_GENERATE_WITH_COMPARE_STATIC(name, type, field, cmp, lcmp) \
436 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, static)
437#define RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, attr) \
438 RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
439 RB_GENERATE_INSERT(name, type, field, cmp, attr) \
440 RB_GENERATE_FIND(name, type, field, cmp, attr) \
441 RB_GENERATE_NFIND(name, type, field, cmp, attr) \
442 RB_GENERATE_FIND_LIGHT(name, type, field, lcmp, attr) \
443 RB_GENERATE_NFIND_LIGHT(name, type, field, lcmp, attr)
444
445#define RB_GENERATE_ALL(name, type, field, cmp) RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, )
446#define RB_GENERATE_ALL_STATIC(name, type, field, cmp) \
447 RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, static)
448#define RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, attr) \
449 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, attr) \
450 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, attr)
451
452#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
453 attr void name##_RB_INSERT_COLOR(struct name* head, struct type* elm) { \
454 struct type *parent, *gparent, *tmp; \
455 while ((parent = RB_PARENT(elm, field)) != NULL && RB_COLOR(parent, field) == RB_RED) { \
456 gparent = RB_PARENT(parent, field); \
457 if (parent == RB_LEFT(gparent, field)) { \
458 tmp = RB_RIGHT(gparent, field); \
459 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
460 RB_COLOR(tmp, field) = RB_BLACK; \
461 RB_SET_BLACKRED(parent, gparent, field); \
462 elm = gparent; \
463 continue; \
464 } \
465 if (RB_RIGHT(parent, field) == elm) { \
466 RB_ROTATE_LEFT(head, parent, tmp, field); \
467 tmp = parent; \
468 parent = elm; \
469 elm = tmp; \
470 } \
471 RB_SET_BLACKRED(parent, gparent, field); \
472 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
473 } else { \
474 tmp = RB_LEFT(gparent, field); \
475 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
476 RB_COLOR(tmp, field) = RB_BLACK; \
477 RB_SET_BLACKRED(parent, gparent, field); \
478 elm = gparent; \
479 continue; \
480 } \
481 if (RB_LEFT(parent, field) == elm) { \
482 RB_ROTATE_RIGHT(head, parent, tmp, field); \
483 tmp = parent; \
484 parent = elm; \
485 elm = tmp; \
486 } \
487 RB_SET_BLACKRED(parent, gparent, field); \
488 RB_ROTATE_LEFT(head, gparent, tmp, field); \
489 } \
490 } \
491 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
492 }
493
494#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
495 attr void name##_RB_REMOVE_COLOR(struct name* head, struct type* parent, struct type* elm) { \
496 struct type* tmp; \
497 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && elm != RB_ROOT(head)) { \
498 if (RB_LEFT(parent, field) == elm) { \
499 tmp = RB_RIGHT(parent, field); \
500 if (RB_COLOR(tmp, field) == RB_RED) { \
501 RB_SET_BLACKRED(tmp, parent, field); \
502 RB_ROTATE_LEFT(head, parent, tmp, field); \
503 tmp = RB_RIGHT(parent, field); \
504 } \
505 if ((RB_LEFT(tmp, field) == NULL || \
506 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \
507 (RB_RIGHT(tmp, field) == NULL || \
508 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \
509 RB_COLOR(tmp, field) = RB_RED; \
510 elm = parent; \
511 parent = RB_PARENT(elm, field); \
512 } else { \
513 if (RB_RIGHT(tmp, field) == NULL || \
514 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \
515 struct type* oleft; \
516 if ((oleft = RB_LEFT(tmp, field)) != NULL) \
517 RB_COLOR(oleft, field) = RB_BLACK; \
518 RB_COLOR(tmp, field) = RB_RED; \
519 RB_ROTATE_RIGHT(head, tmp, oleft, field); \
520 tmp = RB_RIGHT(parent, field); \
521 } \
522 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
523 RB_COLOR(parent, field) = RB_BLACK; \
524 if (RB_RIGHT(tmp, field)) \
525 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \
526 RB_ROTATE_LEFT(head, parent, tmp, field); \
527 elm = RB_ROOT(head); \
528 break; \
529 } \
530 } else { \
531 tmp = RB_LEFT(parent, field); \
532 if (RB_COLOR(tmp, field) == RB_RED) { \
533 RB_SET_BLACKRED(tmp, parent, field); \
534 RB_ROTATE_RIGHT(head, parent, tmp, field); \
535 tmp = RB_LEFT(parent, field); \
536 } \
537 if ((RB_LEFT(tmp, field) == NULL || \
538 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \
539 (RB_RIGHT(tmp, field) == NULL || \
540 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \
541 RB_COLOR(tmp, field) = RB_RED; \
542 elm = parent; \
543 parent = RB_PARENT(elm, field); \
544 } else { \
545 if (RB_LEFT(tmp, field) == NULL || \
546 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \
547 struct type* oright; \
548 if ((oright = RB_RIGHT(tmp, field)) != NULL) \
549 RB_COLOR(oright, field) = RB_BLACK; \
550 RB_COLOR(tmp, field) = RB_RED; \
551 RB_ROTATE_LEFT(head, tmp, oright, field); \
552 tmp = RB_LEFT(parent, field); \
553 } \
554 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
555 RB_COLOR(parent, field) = RB_BLACK; \
556 if (RB_LEFT(tmp, field)) \
557 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \
558 RB_ROTATE_RIGHT(head, parent, tmp, field); \
559 elm = RB_ROOT(head); \
560 break; \
561 } \
562 } \
563 } \
564 if (elm) \
565 RB_COLOR(elm, field) = RB_BLACK; \
566 }
567
568#define RB_GENERATE_REMOVE(name, type, field, attr) \
569 attr struct type* name##_RB_REMOVE(struct name* head, struct type* elm) { \
570 struct type *child, *parent, *old = elm; \
571 int color; \
572 if (RB_LEFT(elm, field) == NULL) \
573 child = RB_RIGHT(elm, field); \
574 else if (RB_RIGHT(elm, field) == NULL) \
575 child = RB_LEFT(elm, field); \
576 else { \
577 struct type* left; \
578 elm = RB_RIGHT(elm, field); \
579 while ((left = RB_LEFT(elm, field)) != NULL) \
580 elm = left; \
581 child = RB_RIGHT(elm, field); \
582 parent = RB_PARENT(elm, field); \
583 color = RB_COLOR(elm, field); \
584 if (child) \
585 RB_PARENT(child, field) = parent; \
586 if (parent) { \
587 if (RB_LEFT(parent, field) == elm) \
588 RB_LEFT(parent, field) = child; \
589 else \
590 RB_RIGHT(parent, field) = child; \
591 RB_AUGMENT(parent); \
592 } else \
593 RB_ROOT(head) = child; \
594 if (RB_PARENT(elm, field) == old) \
595 parent = elm; \
596 (elm)->field = (old)->field; \
597 if (RB_PARENT(old, field)) { \
598 if (RB_LEFT(RB_PARENT(old, field), field) == old) \
599 RB_LEFT(RB_PARENT(old, field), field) = elm; \
600 else \
601 RB_RIGHT(RB_PARENT(old, field), field) = elm; \
602 RB_AUGMENT(RB_PARENT(old, field)); \
603 } else \
604 RB_ROOT(head) = elm; \
605 RB_PARENT(RB_LEFT(old, field), field) = elm; \
606 if (RB_RIGHT(old, field)) \
607 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
608 if (parent) { \
609 left = parent; \
610 do { \
611 RB_AUGMENT(left); \
612 } while ((left = RB_PARENT(left, field)) != NULL); \
613 } \
614 goto color; \
615 } \
616 parent = RB_PARENT(elm, field); \
617 color = RB_COLOR(elm, field); \
618 if (child) \
619 RB_PARENT(child, field) = parent; \
620 if (parent) { \
621 if (RB_LEFT(parent, field) == elm) \
622 RB_LEFT(parent, field) = child; \
623 else \
624 RB_RIGHT(parent, field) = child; \
625 RB_AUGMENT(parent); \
626 } else \
627 RB_ROOT(head) = child; \
628 color: \
629 if (color == RB_BLACK) \
630 name##_RB_REMOVE_COLOR(head, parent, child); \
631 return (old); \
632 }
633
634#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \
635 /* Inserts a node into the RB tree */ \
636 attr struct type* name##_RB_INSERT(struct name* head, struct type* elm) { \
637 struct type* tmp; \
638 struct type* parent = NULL; \
639 int comp = 0; \
640 tmp = RB_ROOT(head); \
641 while (tmp) { \
642 parent = tmp; \
643 comp = (cmp)(elm, parent); \
644 if (comp < 0) \
645 tmp = RB_LEFT(tmp, field); \
646 else if (comp > 0) \
647 tmp = RB_RIGHT(tmp, field); \
648 else \
649 return (tmp); \
650 } \
651 RB_SET(elm, parent, field); \
652 if (parent != NULL) { \
653 if (comp < 0) \
654 RB_LEFT(parent, field) = elm; \
655 else \
656 RB_RIGHT(parent, field) = elm; \
657 RB_AUGMENT(parent); \
658 } else \
659 RB_ROOT(head) = elm; \
660 name##_RB_INSERT_COLOR(head, elm); \
661 return (NULL); \
662 }
663
664#define RB_GENERATE_FIND(name, type, field, cmp, attr) \
665 /* Finds the node with the same key as elm */ \
666 attr struct type* name##_RB_FIND(struct name* head, struct type* elm) { \
667 struct type* tmp = RB_ROOT(head); \
668 int comp; \
669 while (tmp) { \
670 comp = cmp(elm, tmp); \
671 if (comp < 0) \
672 tmp = RB_LEFT(tmp, field); \
673 else if (comp > 0) \
674 tmp = RB_RIGHT(tmp, field); \
675 else \
676 return (tmp); \
677 } \
678 return (NULL); \
679 }
680
681#define RB_GENERATE_NFIND(name, type, field, cmp, attr) \
682 /* Finds the first node greater than or equal to the search key */ \
683 attr struct type* name##_RB_NFIND(struct name* head, struct type* elm) { \
684 struct type* tmp = RB_ROOT(head); \
685 struct type* res = NULL; \
686 int comp; \
687 while (tmp) { \
688 comp = cmp(elm, tmp); \
689 if (comp < 0) { \
690 res = tmp; \
691 tmp = RB_LEFT(tmp, field); \
692 } else if (comp > 0) \
693 tmp = RB_RIGHT(tmp, field); \
694 else \
695 return (tmp); \
696 } \
697 return (res); \
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_ */
HIC SVNT DRACONES