Stroika Library 3.0d24
 
Loading...
Searching...
No Matches
SortedKeyedCollection_SkipList.inl
1/*
2 * Copyright(c) Sophist Solutions, Inc. 1990-2026. All rights reserved
3 */
4#include "Stroika/Foundation/Common/Concepts.h"
5#include "Stroika/Foundation/Containers/Private/IteratorImplHelper.h"
6#include "Stroika/Foundation/Debug/Cast.h"
7#include "Stroika/Foundation/Memory/BlockAllocated.h"
8
9namespace Stroika::Foundation::Containers::Concrete {
10
11 /*
12 ********************************************************************************
13 ********** SortedKeyedCollection_SkipList<T, KEY_TYPE, TRAITS>::Rep_ ***********
14 ********************************************************************************
15 */
16 template <typename T, typename KEY_TYPE, typename TRAITS>
17 template <qCompilerAndStdLib_ConstraintDiffersInTemplateRedeclaration_BWA (IThreeWayComparer<KEY_TYPE>) COMPARER>
18 class SortedKeyedCollection_SkipList<T, KEY_TYPE, TRAITS>::Rep_ : public Private::SkipListBasedContainerRepImpl<Rep_<COMPARER>, IImplRepBase_>,
19 public Memory::UseBlockAllocationIfAppropriate<Rep_<COMPARER>> {
20 public:
21 static_assert (not is_reference_v<COMPARER>);
22
23 private:
24 using inherited = Private::SkipListBasedContainerRepImpl<Rep_<COMPARER>, IImplRepBase_>;
25
26 private:
27 qStroika_ATTRIBUTE_NO_UNIQUE_ADDRESS const KeyExtractorType fKeyExtractor_;
28
29 public:
30 Rep_ (const KeyExtractorType& keyExtractor, const COMPARER& comparer)
31 : fKeyExtractor_{keyExtractor}
32 , fData_{SKIPLIST_ELT_COMPARER<COMPARER>{keyExtractor, comparer}}
33 {
34 }
35 Rep_ (const Rep_& from) = default;
36
37 public:
38 nonvirtual Rep_& operator= (const Rep_&) = delete;
39
40 // Iterable<T>::_IRep overrides
41 public:
42 virtual shared_ptr<typename Iterable<T>::_IRep> Clone () const override
43 {
44 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
45 return Memory::MakeSharedPtr<Rep_> (*this);
46 }
47 virtual Iterator<value_type> MakeIterator () const override
48 {
49 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
50 return Iterator<value_type>{make_unique<IteratorRep_> (&fData_, &fChangeCounts_)};
51 }
52 virtual size_t size () const override
53 {
54 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
55 return fData_.size ();
56 }
57 virtual bool empty () const override
58 {
59 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
60 return fData_.empty ();
61 }
62 virtual void Apply (const function<void (ArgByValueType<value_type> item)>& doToElement, [[maybe_unused]] Execution::SequencePolicy seq) const override
63 {
64 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
65 fData_.Apply ([&] (auto arg) { doToElement (arg.fKey); });
66 }
67 virtual Iterator<T> Find ([[maybe_unused]] bool findFirst, const function<bool (ArgByValueType<value_type> item)>& that,
68 [[maybe_unused]] Execution::SequencePolicy seq) const override
69 {
70 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
71 return Iterator<value_type>{make_unique<IteratorRep_> (&fChangeCounts_, fData_.Find ([&] (auto arg) { return that (arg.fKey); }))};
72 }
73 virtual Iterator<value_type> Find_equal_to (const ArgByValueType<value_type>& v, [[maybe_unused]] Execution::SequencePolicy seq) const override
74 {
75 // if doing a find by 'equals-to' - we already have this indexed
76 auto found = fData_.Find (v);
77#if 0
78 Ensure ((found == fData_.end () and this->inherited::Find_equal_to (v, seq) == Iterator<value_type>{nullptr}) or
79 (found == Debug::UncheckedDynamicCast<const IteratorRep_&> (this->inherited::Find_equal_to (v, seq).ConstGetRep ())
80 .fIterator.GetUnderlyingIteratorRep ()));
81#endif
82 return Iterator<value_type>{make_unique<IteratorRep_> (&fChangeCounts_, found)};
83 }
84
85 // KeyedCollection<T, KEY_TYPE, TRAITS>::_IRep overrides
86 public:
87 virtual KeyExtractorType GetKeyExtractor () const override
88 {
89 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
90 return fKeyExtractor_;
91 }
92 virtual KeyEqualityComparerType GetKeyEqualityComparer () const override
93 {
94 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
95 return Common::EqualsComparerAdapter<T, COMPARER>{fData_.key_comp ().fKeyComparer};
96 }
97 virtual shared_ptr<typename KeyedCollection<T, KEY_TYPE, TRAITS>::_IRep> CloneEmpty () const override
98 {
99 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
100 return Memory::MakeSharedPtr<Rep_> (this->fKeyExtractor_, fData_.key_comp ().fKeyComparer); // keep extractor/comparer but lose data in clone
101 }
102 virtual shared_ptr<typename KeyedCollection<T, KEY_TYPE, TRAITS>::_IRep> CloneAndPatchIterator (Iterator<value_type>* i) const override
103 {
104 RequireNotNull (i);
105 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
106 auto result = Memory::MakeSharedPtr<Rep_> (*this);
107 auto& mir = Debug::UncheckedDynamicCast<const IteratorRep_&> (i->ConstGetRep ());
108 result->fData_.MoveIteratorHereAfterClone (&mir.fIterator, &fData_);
109 i->Refresh (); // reflect updated rep
110 return result;
111 }
112 virtual bool Lookup (ArgByValueType<KeyType> key, optional<value_type>* item) const override
113 {
114 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
115 auto i = fData_.Find (key);
116 if (i == fData_.end ()) {
117 if (item != nullptr) {
118 *item = nullopt;
119 }
120 return false;
121 }
122 else {
123 if (item != nullptr) {
124 *item = i->fKey;
125 }
126 return true;
127 }
128 }
129 virtual bool Add (ArgByValueType<value_type> item) override
130 {
131 Debug::AssertExternallySynchronizedChecker::WriteContext declareContext{fData_};
132 size_t szBefore = fData_.size ();
133 fData_.Add (item); // note return value says if changed, doesn't report if added, so check size for that
134 fChangeCounts_.PerformedChange ();
135 return szBefore != fData_.size ();
136 }
137 virtual void Remove (const Iterator<value_type>& i, Iterator<value_type>* nextI) override
138 {
139 Require (not i.AtEnd ());
140 Debug::AssertExternallySynchronizedChecker::WriteContext declareContext{fData_};
141 auto& mir = Debug::UncheckedDynamicCast<const IteratorRep_&> (i.ConstGetRep ());
142 mir.fIterator.AssertDataMatches (&fData_);
143 auto nextIResult = fData_.erase (mir.fIterator);
144 fChangeCounts_.PerformedChange ();
145 if (nextI != nullptr) {
146 *nextI = Iterator<value_type>{make_unique<IteratorRep_> (&fChangeCounts_, nextIResult)};
147 }
148 }
149 virtual bool RemoveIf (ArgByValueType<KEY_TYPE> key) override
150 {
151 Debug::AssertExternallySynchronizedChecker::WriteContext declareContext{fData_};
152 auto i = fData_.Find (key);
153 if (i != fData_.end ()) {
154 fData_.Remove (i);
155 fChangeCounts_.PerformedChange ();
156 return true;
157 }
158 return false;
159 }
160
161 // SortedKeyedCollection<KEY_TYPE, MAPPED_VALUE_TYPE>::_IRep overrides
162 public:
163 virtual KeyThreeWayComparerType GetThreeWayKeyComparer () const override
164 {
165 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
166 return fData_.key_comp ().fKeyComparer;
167 }
168
169 private:
170 using DataStructureImplType_ = SKIPLIST<COMPARER>;
171 struct IterTraits_ : Private::IteratorImplHelper_DefaultTraits<value_type, DataStructureImplType_> {
172 static constexpr value_type ConvertDataStructureIterationResult2ContainerIteratorResult (const typename DataStructureImplType_::value_type& t)
173 {
174 return t.fKey;
175 }
176 };
177 using IteratorRep_ = Private::IteratorImplHelper_<value_type, DataStructureImplType_, IterTraits_>;
178
179 private:
180 DataStructureImplType_ fData_;
181 qStroika_ATTRIBUTE_NO_UNIQUE_ADDRESS_VCFORCE Private::ContainerDebugChangeCounts_ fChangeCounts_;
182
183 private:
184 friend inherited;
185 };
186
187 /*
188 ********************************************************************************
189 ********** SortedKeyedCollection_SkipList<KEY_TYPE,MAPPED_VALUE_TYPE> **********
190 ********************************************************************************
191 */
192 template <typename T, typename KEY_TYPE, typename TRAITS>
193 template <IThreeWayComparer<KEY_TYPE> COMPARER>
194 inline SortedKeyedCollection_SkipList<T, KEY_TYPE, TRAITS>::SortedKeyedCollection_SkipList (COMPARER&& keyComparer)
195 requires (IKeyedCollection_ExtractorCanBeDefaulted<T, KEY_TYPE, TRAITS>)
196 : SortedKeyedCollection_SkipList{KeyExtractorType{}, forward<COMPARER> (keyComparer)}
197 {
198 }
199 template <typename T, typename KEY_TYPE, typename TRAITS>
200 template <IThreeWayComparer<KEY_TYPE> COMPARER>
201 SortedKeyedCollection_SkipList<T, KEY_TYPE, TRAITS>::SortedKeyedCollection_SkipList (const KeyExtractorType& keyExtractor, COMPARER&& keyComparer)
202 : inherited{Memory::MakeSharedPtr<Rep_<remove_cvref_t<COMPARER>>> (keyExtractor, forward<COMPARER> (keyComparer))}
203 {
204 AssertRepValidType_ ();
205 }
206#if !qCompilerAndStdLib_RequiresNotMatchInlineOutOfLineForTemplateClassBeingDefined_Buggy
207 template <typename T, typename KEY_TYPE, typename TRAITS>
208 template <IIterableOfTo<T> ITERABLE_OF_ADDABLE, IThreeWayComparer<KEY_TYPE> COMPARER>
209 requires (IKeyedCollection_ExtractorCanBeDefaulted<T, KEY_TYPE, TRAITS> and
210 not derived_from<remove_cvref_t<ITERABLE_OF_ADDABLE>, SortedKeyedCollection_SkipList<T, KEY_TYPE, TRAITS>>)
211 inline SortedKeyedCollection_SkipList<T, KEY_TYPE, TRAITS>::SortedKeyedCollection_SkipList (ITERABLE_OF_ADDABLE&& src)
212 : SortedKeyedCollection_SkipList{KeyExtractorType{}, COMPARER{}}
213 {
214 this->AddAll (src);
215 AssertRepValidType_ ();
216 }
217#endif
218 template <typename T, typename KEY_TYPE, typename TRAITS>
219 template <IIterableOfTo<T> ITERABLE_OF_ADDABLE, IThreeWayComparer<KEY_TYPE> COMPARER>
220 inline SortedKeyedCollection_SkipList<T, KEY_TYPE, TRAITS>::SortedKeyedCollection_SkipList (COMPARER&& keyComparer, ITERABLE_OF_ADDABLE&& src)
221 requires (IKeyedCollection_ExtractorCanBeDefaulted<T, KEY_TYPE, TRAITS>)
222 {
223 this->AddAll (src);
224 AssertRepValidType_ ();
225 }
226 template <typename T, typename KEY_TYPE, typename TRAITS>
227 template <IThreeWayComparer<KEY_TYPE> COMPARER, IIterableOfTo<T> ITERABLE_OF_ADDABLE>
228 inline SortedKeyedCollection_SkipList<T, KEY_TYPE, TRAITS>::SortedKeyedCollection_SkipList (const KeyExtractorType& keyExtractor,
229 COMPARER&& keyComparer, ITERABLE_OF_ADDABLE&& src)
230 : SortedKeyedCollection_SkipList{keyExtractor, forward<COMPARER> (keyComparer)}
231 {
232 this->AddAll (src);
233 AssertRepValidType_ ();
234 }
235 template <typename T, typename KEY_TYPE, typename TRAITS>
236 template <IInputIterator<T> ITERATOR_OF_ADDABLE, IThreeWayComparer<KEY_TYPE> COMPARER>
237 inline SortedKeyedCollection_SkipList<T, KEY_TYPE, TRAITS>::SortedKeyedCollection_SkipList (ITERATOR_OF_ADDABLE&& start, ITERATOR_OF_ADDABLE&& end)
238 requires (IKeyedCollection_ExtractorCanBeDefaulted<T, KEY_TYPE, TRAITS>)
239 : SortedKeyedCollection_SkipList{KeyExtractorType{}, COMPARER{}}
240 {
241 this->AddAll (forward<ITERATOR_OF_ADDABLE> (start), forward<ITERATOR_OF_ADDABLE> (end));
242 AssertRepValidType_ ();
243 }
244 template <typename T, typename KEY_TYPE, typename TRAITS>
245 template <IInputIterator<T> ITERATOR_OF_ADDABLE, IThreeWayComparer<KEY_TYPE> COMPARER>
246 inline SortedKeyedCollection_SkipList<T, KEY_TYPE, TRAITS>::SortedKeyedCollection_SkipList (COMPARER&& keyComparer, ITERATOR_OF_ADDABLE&& start,
247 ITERATOR_OF_ADDABLE&& end)
248 requires (IKeyedCollection_ExtractorCanBeDefaulted<T, KEY_TYPE, TRAITS>)
249 : SortedKeyedCollection_SkipList{KeyExtractorType{}, forward<COMPARER> (keyComparer)}
250 {
251 this->AddAll (forward<ITERATOR_OF_ADDABLE> (start), forward<ITERATOR_OF_ADDABLE> (end));
252 AssertRepValidType_ ();
253 }
254 template <typename T, typename KEY_TYPE, typename TRAITS>
255 template <IThreeWayComparer<KEY_TYPE> COMPARER, IInputIterator<T> ITERATOR_OF_ADDABLE>
256 inline SortedKeyedCollection_SkipList<T, KEY_TYPE, TRAITS>::SortedKeyedCollection_SkipList (const KeyExtractorType& keyExtractor,
257 COMPARER&& keyComparer, ITERATOR_OF_ADDABLE&& start,
258 ITERATOR_OF_ADDABLE&& end)
259 : SortedKeyedCollection_SkipList{keyExtractor, forward<COMPARER> (keyComparer)}
260 {
261 this->AddAll (forward<ITERATOR_OF_ADDABLE> (start), forward<ITERATOR_OF_ADDABLE> (end));
262 AssertRepValidType_ ();
263 }
264 template <typename T, typename KEY_TYPE, typename TRAITS>
265 inline void SortedKeyedCollection_SkipList<T, KEY_TYPE, TRAITS>::AssertRepValidType_ () const
266 {
267 if constexpr (qStroika_Foundation_Debug_AssertionsChecked) {
268 typename inherited::template _SafeReadRepAccessor<IImplRepBase_> tmp{this}; // for side-effect of AssertMember
269 }
270 }
271
272}
qStroika_Foundation_Debug_AssertionsChecked
#define qStroika_Foundation_Debug_AssertionsChecked
The qStroika_Foundation_Debug_AssertionsChecked flag determines if assertions are checked and validat...
Definition Assertions.h:49
RequireNotNull
#define RequireNotNull(p)
Definition Assertions.h:348
Stroika::Foundation::Memory::MakeSharedPtr
auto MakeSharedPtr(ARGS_TYPE &&... args) -> shared_ptr< T >
same as make_shared, but if type T has block allocation, then use block allocation for the 'shared pa...
Definition BlockAllocated.inl:52
qStroika_ATTRIBUTE_NO_UNIQUE_ADDRESS
#define qStroika_ATTRIBUTE_NO_UNIQUE_ADDRESS
qStroika_ATTRIBUTE_NO_UNIQUE_ADDRESS - used for the attribute [[no_unique_address]]
Definition StdCompat.h:433
qStroika_ATTRIBUTE_NO_UNIQUE_ADDRESS_VCFORCE
#define qStroika_ATTRIBUTE_NO_UNIQUE_ADDRESS_VCFORCE
[[msvc::no_unique_address]] isn't always broken in MSVC. Annotate with this on things where its not b...
Definition StdCompat.h:443
Stroika::Foundation::Debug::AssertExternallySynchronizedChecker::WriteContext
unique_lock< AssertExternallySynchronizedChecker > WriteContext
Instantiate AssertExternallySynchronizedChecker::WriteContext to designate an area of code where prot...
Definition AssertExternallySynchronizedChecker.h:335
Stroika::Foundation::Debug::AssertExternallySynchronizedChecker::ReadContext
shared_lock< const AssertExternallySynchronizedChecker > ReadContext
Instantiate AssertExternallySynchronizedChecker::ReadContext to designate an area of code where prote...
Definition AssertExternallySynchronizedChecker.h:314
Stroika::Foundation::Execution::SequencePolicy
SequencePolicy
equivalent which of 4 types being used std::execution::sequenced_policy, parallel_policy,...
Definition Foundation/Execution/Common.h:46