Stroika Library 3.0d24
 
Loading...
Searching...
No Matches
SkipList.inl
1/*
2 * Copyright(c) Sophist Solutions, Inc. 1990-2026. All rights reserved
3 */
4#include <random>
5
6#include "Stroika/Foundation/Debug/Assertions.h"
7#include "Stroika/Foundation/Execution/Exceptions.h"
8
9namespace Stroika::Foundation::Containers::DataStructures {
10
11 namespace Private_ {
12
13 static thread_local std::mt19937 sRng_{[] () {
14 auto seed = std::random_device{}();
15 return std::mt19937{seed};
16 }()};
17
18 /**
19 * Sometimes, the random nature of the data structure makes it difficult to debug, so capturing a bad seed
20 * and re-using can occasionally help
21 * Hack for debugging/some regression tests
22 */
23 inline void SetRandomNumberGenerator (const std::mt19937& use)
24 {
25 sRng_ = use;
26 }
27 inline size_t RandomSize_t (size_t first, size_t last)
28 {
29 Assert (sRng_.min () <= first);
30 // Assert (eng.max () >= last); // g++ has 8 byte size_t in 64 bit??
31 std::uniform_int_distribution<size_t> unif{first, last};
32 size_t result = unif (sRng_);
33 Ensure (result >= first);
34 Ensure (result <= last);
35 return result;
36 }
37
38 }
39
40 /*
41 ********************************************************************************
42 ************** SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Link_ ******************
43 ********************************************************************************
44 */
45#if !qCompilerAndStdLib_RequiresNotMatchInlineOutOfLineForTemplateClassBeingDefined_Buggy
46 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
47 template <typename MAPPED_TYPE2>
48 constexpr SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Link_::Link_ (ArgByValueType<key_type> key, ArgByValueType<MAPPED_TYPE2> val)
49 requires (not same_as<MAPPED_TYPE2, void>)
50 : fEntry{key, val}
51 {
52 }
53 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
54 constexpr SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Link_::Link_ (ArgByValueType<key_type> key)
55 requires (same_as<MAPPED_TYPE, void>)
56 : fEntry{key}
57 {
58 }
59#endif
60 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
61 constexpr SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Link_::Link_ (ArgByValueType<value_type> v)
62 : fEntry{v}
63 {
64 }
65
66 /*
67 ********************************************************************************
68 ******************* SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS> ********************
69 ********************************************************************************
70 */
71 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
72 inline SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::SkipList (const KeyComparerType& keyComparer)
73 : fKeyThreeWayComparer_{keyComparer}
74 {
75 GrowHeadLinksIfNeeded_ (1, nullptr);
76 }
77 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
78 SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::SkipList (const SkipList& src)
79 : fKeyThreeWayComparer_{src.fKeyThreeWayComparer_}
80 {
81 GrowHeadLinksIfNeeded_ (1, nullptr);
82 Link_* prev = nullptr;
83 Link_* n = src.fHead_[0];
84 while (n != nullptr) {
85 Link_* newLink = new Link_{n->fEntry};
86 if (prev == nullptr) {
87 Assert (fHead_.size () == 1);
88 Assert (fHead_[0] == nullptr);
89 fHead_[0] = newLink;
90 }
91 else {
92 prev->fNext.push_back (newLink);
93 }
94 prev = newLink;
95 n = n->fNext[0];
96 }
97 // AssertNotNull (prev);
98 if (prev != nullptr) {
99 Assert (prev->fNext.size () == 0);
100 prev->fNext.push_back (nullptr);
101 }
102 fLength_ = src.fLength_;
103 ReBalance (); // this will give us a proper link structure
104 }
105 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
106 inline SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::SkipList (SkipList&& src) noexcept
107 : fKeyThreeWayComparer_{src.fKeyThreeWayComparer_}
108 , fHead_{move (src.fHead_)}
109 , fLength_{src.fLength_}
110 {
111 src.fHead_.resize (1); // cannot throw cuz always shrinking or no change
112 src.fHead_[0] = 0;
113 src.fLength_ = 0;
114 }
115 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
116 SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>& SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::operator= (const SkipList& t)
117 {
118 clear ();
119 if (t.size () != 0) {
120 Link_* prev = nullptr;
121 Link_* n = t.fHead_[0];
122 while (n != nullptr) {
123 Link_* newLink = new Link_{n->fEntry};
124 if (prev == nullptr) {
125 Assert (fHead_.size () == 1);
126 Assert (fHead_[0] == nullptr);
127 fHead_[0] = newLink;
128 }
129 else {
130 prev->fNext.push_back (newLink);
131 }
132 prev = newLink;
133 n = n->fNext[0];
134 }
135 AssertNotNull (prev);
136 Assert (prev->fNext.size () == 0);
137 prev->fNext.push_back (nullptr);
138 fLength_ = t.fLength_;
139 ReBalance (); // this will give us a proper link structure
140 }
141 return *this;
142 }
143 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
144 inline SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::~SkipList ()
145 {
146 clear ();
147 }
148 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
149 constexpr auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::key_comp () const -> KeyComparerType
150 {
151 return fKeyThreeWayComparer_;
152 }
153 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
154 inline size_t SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::GetLinkHeightProbability ()
155 {
156 return 25;
157 }
158 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
159 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::GetStats () const -> StatsType
160 {
161 return fStats_;
162 }
163 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
164 inline size_t SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::size () const
165 {
166 AssertExternallySynchronizedChecker::ReadContext declareContext{*this};
167 return fLength_;
168 }
169 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
170 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::empty () const
171 {
172 AssertExternallySynchronizedChecker::ReadContext declareContext{*this};
173 return fLength_ == 0;
174 }
175 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
176 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::begin () const -> ForwardIterator
177 {
178 AssertExternallySynchronizedChecker::ReadContext declareContext{*this};
179 return ForwardIterator{this};
180 }
181 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
182 constexpr auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::end () const noexcept -> ForwardIterator
183 {
184 return ForwardIterator{};
185 }
186 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
187 inline void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::MoveIteratorHereAfterClone (ForwardIterator* pi, const SkipList* movedFrom) const
188 {
189 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{*this};
190 RequireNotNull (pi);
191 RequireNotNull (movedFrom);
192#if qStroika_Foundation_Debug_AssertionsChecked
193 Require (pi->fData_ == movedFrom);
194#endif
195 // TRICKY TODO - BUT MUST DO - MUST MOVE FROM OLD ITER TO NEW
196 // only way
197 //
198 // For STL containers, not sure how to find an equiv new iterator for an old one, but my best guess is to iterate through
199 // old for old, and when I match, stop on new
200 Link_* newI = this->fHead_[0];
201 [[maybe_unused]] Link_* newE = nullptr;
202 Link_* oldI = movedFrom->fHead_[0];
203 [[maybe_unused]] Link_* oldE = nullptr;
204 while (oldI != pi->fCurrent_) {
205 Assert (newI != newE);
206 Assert (oldI != oldE);
207 newI = newI->fNext[0];
208 oldI = oldI->fNext[0];
209 Assert (newI != newE);
210 Assert (oldI != oldE);
211 }
212 Assert (oldI == pi->fCurrent_);
213 pi->fCurrent_ = newI;
214#if qStroika_Foundation_Debug_AssertionsChecked
215 pi->fData_ = this;
216#endif
217 }
218 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
219 template <Common::IAnyOf<KEY_TYPE, typename TRAITS::AlternateFindType> KEYISH_T>
220 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::FindLink_ (const KEYISH_T& key) const -> Link_*
221 {
222 using Common::ToInt;
223 AssertExternallySynchronizedChecker::ReadContext declareContext{*this};
224 Assert (fHead_.size () > 0);
225 LinkVector_ const* startV = &fHead_;
226 for (size_t linkHeight = fHead_.size (); linkHeight > 0; --linkHeight) {
227 Link_* n = (*startV)[linkHeight - 1];
228 // tweak to use pointer comparisons rather than key field compares. We know any link higher than the current link being
229 // tested must point past the key we are looking for, so we can compare our current link with that one and skip the
230 // test if they are the same. In practice, seems to avoid 3-10% of all compares
231 Link_* overShotLink = (startV->size () <= linkHeight) ? nullptr : (*startV)[linkHeight];
232 while (n != overShotLink) {
233 if constexpr (same_as<Support::SkipList::Stats_Basic, StatsType>) {
234 ++fStats_.fCompares;
235 }
236 switch (ToInt (fKeyThreeWayComparer_ (n->fEntry.fKey, key))) {
237 case ToInt (strong_ordering::equal):
238 return n;
239 case ToInt (strong_ordering::less):
240 startV = &n->fNext;
241 n = n->fNext[linkHeight - 1];
242 break;
243 case ToInt (strong_ordering::greater):
244 goto overshoot;
245 }
246 }
247 overshoot:;
248 }
249 return nullptr;
250 }
251 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
252 template <Common::IAnyOf<KEY_TYPE, typename TRAITS::AlternateFindType> KEYISH_T>
253 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::FindFirstLink_ (const KEYISH_T& key) const -> Link_*
254 {
255 AssertExternallySynchronizedChecker::ReadContext declareContext{*this};
256 Assert (fHead_.size () > 0);
257 LinkVector_ const* startV = &fHead_;
258 Link_* candidate = nullptr;
259 for (size_t linkHeight = fHead_.size (); linkHeight > 0; --linkHeight) {
260 Link_* n = (*startV)[linkHeight - 1];
261 Link_* overShotLink = (startV->size () <= linkHeight) ? nullptr : (*startV)[linkHeight];
262 // Unlike FindLink_ (), NEVER stop early just because we hit an 'equal' key - only stop advancing
263 // (dropping down a level instead) once the current link is NOT strictly less than key. This
264 // guarantees we land on the leftmost (first, in sorted/iteration order) link with an equal key,
265 // instead of potentially shortcutting via a higher-level link into the middle of a run of equal keys.
266 while (n != overShotLink) {
267 if constexpr (same_as<Support::SkipList::Stats_Basic, StatsType>) {
268 ++fStats_.fCompares;
269 }
270 if (fKeyThreeWayComparer_ (n->fEntry.fKey, key) != strong_ordering::less) {
271 break;
272 }
273 startV = &n->fNext;
274 n = n->fNext[linkHeight - 1];
275 }
276 candidate = n;
277 }
278 return (candidate != nullptr and fKeyThreeWayComparer_ (candidate->fEntry.fKey, key) == strong_ordering::equal) ? candidate : nullptr;
279 }
280 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
281 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Find (ArgByValueType<key_type> key) const -> ForwardIterator
282 {
283 return ForwardIterator{this, FindLink_ (key)};
284 }
285 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
286 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::FindFirst (ArgByValueType<key_type> key) const -> ForwardIterator
287 {
288 return ForwardIterator{this, FindFirstLink_ (key)};
289 }
290 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
291 template <typename ARG_T>
292 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Find (ARG_T key) const -> ForwardIterator
293 requires (not same_as<typename TRAITS::AlternateFindType, void> and same_as<remove_cvref_t<ARG_T>, typename TRAITS::AlternateFindType>)
294 {
295 return ForwardIterator{this, FindLink_ (key)};
296 }
297#if !qCompilerAndStdLib_RequiresNotMatchInlineOutOfLineForTemplateClassBeingDefined_Buggy
298 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
299 template <predicate<typename SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::value_type> FUNCTION>
300 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Find (FUNCTION&& firstThat) const -> ForwardIterator
301 {
302 for (auto i = begin (); i; ++i) {
303 if (firstThat (*i)) {
304 return i;
305 }
306 }
307 return end ();
308 }
309#endif
310 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
311 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::First (ArgByValueType<key_type> key) const -> optional<mapped_type>
312 {
313 if (auto o = FindLink_ (key)) {
314 return o->fEntry.fValue;
315 }
316 return nullopt;
317 }
318 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
319 template <qCompilerAndStdLib_RequiresNotMatchXXXDefined_1_BWA (predicate<typename SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::value_type>) FUNCTION>
320 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::First (FUNCTION&& firstThat) const -> optional<mapped_type>
321 {
322 for (auto i : *this) {
323 if (firstThat (*i)) {
324 return i->fValue;
325 }
326 }
327 return nullopt;
328 }
329 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
330 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::contains (ArgByValueType<key_type> key) const
331 {
332 AssertExternallySynchronizedChecker::ReadContext declareContext{*this};
333 return FindLink_ (key) != nullptr;
334 }
335 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
336#if qCompilerAndStdLib_RequiresNotMatchInlineOutOfLineForTemplateClassBeingDefined_Buggy
337 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Add1_ (ArgByValueType<key_type> key, ForwardIterator* oAddedI)
338#else
339 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Add (ArgByValueType<key_type> key, ForwardIterator* oAddedI)
340 requires (same_as<mapped_type, void>)
341#endif
342 {
343 AssertExternallySynchronizedChecker::WriteContext declareContext{*this};
344 if constexpr (TRAITS::kCostlyInvariants) {
345 Invariant ();
346 }
347 LinkAndInfoAboutBackPointers_ keyLinkInfo = FindNearest_ (key);
348 Link_* n = keyLinkInfo.fLink;
349 if (n == nullptr) {
350 Link_* newLink = new Link_{key};
351 AddLink_ (newLink, keyLinkInfo.fLinksPointingToReturnedLink);
352 if constexpr (TRAITS::kCostlyInvariants) {
353 Invariant ();
354 }
355 if (oAddedI != nullptr) [[unlikely]] {
356 *oAddedI = ForwardIterator{this, newLink};
357 }
358 return true;
359 }
360 else {
361 switch (TRAITS::kAddOrExtendOrReplaceMode) {
362 case AddOrExtendOrReplaceMode::eAddIfMissing:
363 return false;
364 case AddOrExtendOrReplaceMode::eAddReplaces:
365 n->fEntry.fKey = key; // two 'different' objects can compare equal, and this updates the value (e.g. stroika set)
366 if constexpr (TRAITS::kCostlyInvariants) {
367 Invariant ();
368 }
369 if (oAddedI != nullptr) [[unlikely]] {
370 *oAddedI = ForwardIterator{this, n};
371 }
372 return true;
373 case AddOrExtendOrReplaceMode::eAddExtras: {
374 Link_* newLink = new Link_{key};
375 AddLink_ (newLink, keyLinkInfo.fLinksPointingToReturnedLink);
376 if constexpr (TRAITS::kCostlyInvariants) {
377 Invariant ();
378 }
379 if (oAddedI != nullptr) [[unlikely]] {
380 *oAddedI = ForwardIterator{this, newLink};
381 }
382 return true;
383 }
384 case AddOrExtendOrReplaceMode::eDuplicatesRejected:
385 static const auto kExcept_ = Execution::RuntimeErrorException<logic_error>{"Duplicates not allowed"sv};
386 Execution::Throw (kExcept_);
387 }
388 AssertNotReached ();
389 return false;
390 }
391 }
392 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
393#if qCompilerAndStdLib_RequiresNotMatchInlineOutOfLineForTemplateClassBeingDefined_Buggy
394 template <typename CHECK_T>
395 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Add2_ (ArgByValueType<key_type> key, ArgByValueType<CHECK_T> val, ForwardIterator* oAddedI)
396#else
397 template <typename CHECK_T>
398 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Add (ArgByValueType<key_type> key, ArgByValueType<CHECK_T> val, ForwardIterator* oAddedI)
399 requires (not same_as<mapped_type, void>)
400#endif
401 {
402 AssertExternallySynchronizedChecker::WriteContext declareContext{*this};
403 if constexpr (TRAITS::kCostlyInvariants) {
404 Invariant ();
405 }
406 LinkAndInfoAboutBackPointers_ keyLinkInfo = FindNearest_ (key);
407 Link_* n = keyLinkInfo.fLink;
408 if (keyLinkInfo.fLink == nullptr) {
409 Link_* newLink = new Link_{key, val};
410 AddLink_ (newLink, keyLinkInfo.fLinksPointingToReturnedLink);
411 if constexpr (TRAITS::kCostlyInvariants) {
412 Invariant ();
413 }
414 if (oAddedI != nullptr) [[unlikely]] {
415 *oAddedI = ForwardIterator{this, newLink};
416 }
417 return true;
418 }
419 else {
420 switch (TRAITS::kAddOrExtendOrReplaceMode) {
421 case AddOrExtendOrReplaceMode::eAddIfMissing:
422 return false;
423 case AddOrExtendOrReplaceMode::eAddReplaces:
424 n->fEntry.fKey = key; // two 'different' objects can compare equal, and this updates the value (e.g. stroika set)
425 n->fEntry.fValue = val;
426 if constexpr (TRAITS::kCostlyInvariants) {
427 Invariant ();
428 }
429 if (oAddedI != nullptr) [[unlikely]] {
430 *oAddedI = ForwardIterator{this, n};
431 }
432 return true;
433 case AddOrExtendOrReplaceMode::eAddExtras: {
434
435 Link_* newLink = new Link_{key, val};
436 AddLink_ (newLink, keyLinkInfo.fLinksPointingToReturnedLink);
437 if constexpr (TRAITS::kCostlyInvariants) {
438 Invariant ();
439 }
440 if (oAddedI != nullptr) [[unlikely]] {
441 *oAddedI = ForwardIterator{this, newLink};
442 }
443 return true;
444 }
445 case AddOrExtendOrReplaceMode::eDuplicatesRejected:
446 static const auto kExcept_ = Execution::RuntimeErrorException<logic_error>{"Duplicates not allowed"sv};
447 Execution::Throw (kExcept_);
448 }
449 AssertNotReached ();
450 return false;
451 }
452 }
453 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
454 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Add (const value_type& v, ForwardIterator* oAddedI)
455 {
456 return Add (v.fKey, v.fValue, oAddedI);
457 }
458 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
459 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::AddLink_ (Link_* link, const LinkVector_& links)
460 {
461 AssertExternallySynchronizedChecker::WriteContext declareContext{*this};
462 RequireNotNull (link);
463 size_t newLinkHeight = DetermineLinkHeight_ ();
464 link->fNext.resize (newLinkHeight);
465 size_t linksToPatch = min (fHead_.size (), newLinkHeight);
466 for (size_t i = 0; i < linksToPatch; ++i) {
467 Link_* nextL = nullptr;
468 if (links[i] == nullptr) {
469 nextL = fHead_[i];
470 fHead_[i] = link;
471 }
472 else {
473 if constexpr (same_as<Support::SkipList::Stats_Basic, StatsType>) {
474 ++fStats_.fRotations;
475 }
476 Link_* oldLink = links[i];
477 AssertNotNull (oldLink);
478 nextL = oldLink->fNext[i];
479 oldLink->fNext[i] = link;
480 }
481 link->fNext[i] = nextL;
482 }
483 GrowHeadLinksIfNeeded_ (newLinkHeight, link);
484 ++fLength_;
485 }
486 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
487 inline void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Remove (ArgByValueType<key_type> key)
488 {
489 Verify (RemoveIf (key));
490 }
491 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
492 inline void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Remove (const ForwardIterator& it)
493 {
494 // we need the links to reset, so have to re-find (cannot Link_* n = const_cast<Link_*> (it.fCurrent_))
495 LinkAndInfoAboutBackPointers_ keyLinkInfo = FindNearest_ (it);
496 RequireNotNull (keyLinkInfo.fLink);
497 RemoveLink_ (keyLinkInfo.fLink, keyLinkInfo.fLinksPointingToReturnedLink);
498 if constexpr (TRAITS::kCostlyInvariants) {
499 Invariant ();
500 }
501 }
502 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
503 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::erase (const ForwardIterator& i) -> ForwardIterator
504 {
505 // we need the links to reset, so have to re-find
506 // Link_* n = const_cast<Link_*> (it.fCurrent_);
507 LinkAndInfoAboutBackPointers_ keyLinkInfo = FindNearest_ (i);
508 RequireNotNull (keyLinkInfo.fLink);
509 Link_* after = keyLinkInfo.fLink->fNext[0]; // result returned
510 RemoveLink_ (keyLinkInfo.fLink, keyLinkInfo.fLinksPointingToReturnedLink);
511 if constexpr (TRAITS::kCostlyInvariants) {
512 Invariant ();
513 }
514 return after == nullptr ? end () : ForwardIterator{this, after};
515 }
516 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
517 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::RemoveIf (ArgByValueType<key_type> key)
518 {
519 AssertExternallySynchronizedChecker::WriteContext declareContext{*this};
520 if constexpr (TRAITS::kCostlyInvariants) {
521 Invariant ();
522 }
523 LinkAndInfoAboutBackPointers_ keyLinkInfo = FindNearest_ (key);
524 if (keyLinkInfo.fLink != nullptr) {
525 RemoveLink_ (keyLinkInfo.fLink, keyLinkInfo.fLinksPointingToReturnedLink);
526 if constexpr (TRAITS::kCostlyInvariants) {
527 Invariant ();
528 }
529 return true;
530 }
531 else {
532 return false;
533 }
534 }
535 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
536 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::RemoveLink_ (Link_* n, const LinkVector_& links)
537 {
538 AssertExternallySynchronizedChecker::WriteContext declareContext{*this};
539 for (auto it = links.begin (); it != links.end (); ++it) {
540 size_t index = it - links.begin ();
541 Link_** patchLink = (*it == nullptr) ? &fHead_[index] : &(*it)->fNext[index];
542 if (*patchLink == n) {
543 if constexpr (same_as<Support::SkipList::Stats_Basic, StatsType>) {
544 ++fStats_.fRotations;
545 }
546 *patchLink = n->fNext[index];
547 }
548 else {
549 break; //? @todo document why we can stop here???
550 }
551 }
552 if (n->fNext.size () == fHead_.size ()) {
553 ShrinkHeadLinksIfNeeded_ ();
554 }
555 delete n;
556 --fLength_;
557 }
558 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
559 size_t SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::DetermineLinkHeight_ () const
560 {
561 constexpr size_t kMaxNewGrowth = 1;
562 size_t linkHeight = 1;
563 size_t maxHeight = min (fHead_.size () + kMaxNewGrowth, size_t (kMaxLinkHeight_));
564 while ((linkHeight < maxHeight) and (Private_::RandomSize_t (1, 100) <= GetLinkHeightProbability ())) {
565 ++linkHeight;
566 }
567 return linkHeight;
568 }
569 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
570 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::GrowHeadLinksIfNeeded_ (size_t newSize, Link_* linkToPointTo)
571 {
572 if (newSize > fHead_.size ()) {
573 fHead_.resize (newSize, linkToPointTo);
574 Assert (fHead_[newSize - 1] == linkToPointTo);
575 }
576 }
577 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
578 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ShrinkHeadLinksIfNeeded_ ()
579 {
580 Require (fHead_.size () >= 1);
581 for (size_t i = fHead_.size () - 1; i >= 1; --i) {
582 if (fHead_[i] == nullptr) {
583 fHead_.pop_back ();
584 }
585 }
586 Ensure (fHead_.size () >= 1);
587 }
588 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
589 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::clear ()
590 {
591 AssertExternallySynchronizedChecker::WriteContext declareContext{*this};
592 Link_* link = (fHead_.size () == 0) ? nullptr : fHead_[0];
593 while (link != nullptr) {
594 Link_* nextLink = link->fNext[0];
595 delete link;
596 link = nextLink;
597 }
598 fHead_.resize (1);
599 fHead_[0] = nullptr;
600 fLength_ = 0;
601 Ensure (size () == 0);
602 }
603 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
604 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::FindNearest_ (const variant<key_type, ForwardIterator>& keyOrI) const -> LinkAndInfoAboutBackPointers_
605 {
606 LinkVector_ linksPointingToReturnedLink;
607 key_type key = std::get_if<key_type> (&keyOrI) ? std::get<key_type> (keyOrI) : get<ForwardIterator> (keyOrI).fCurrent_->fEntry.fKey;
608 using Common::ToInt;
609 Assert (fHead_.size () > 0);
610 linksPointingToReturnedLink = fHead_;
611 Link_* newOverShotLink = nullptr;
612 Link_* foundLink = nullptr;
613 Assert (not linksPointingToReturnedLink.empty ()); // now
614 size_t linkIndex = linksPointingToReturnedLink.size () - 1;
615 do {
616 Link_* n = linksPointingToReturnedLink[linkIndex];
617 // tweak to use pointer comparisons rather than key field compares. We know any link higher than the current link being
618 // tested must point past the key we are looking for, so we can compare our current link with that one and skip the
619 // test if they are the same. In practice, seems to avoid 3-10% of all compares
620 Link_* overShotLink = newOverShotLink;
621 Assert (n == nullptr or overShotLink == nullptr or
622 (fKeyThreeWayComparer_ (n->fEntry.fKey, overShotLink->fEntry.fKey) != strong_ordering::greater));
623
624 linksPointingToReturnedLink[linkIndex] = nullptr;
625 while (n != overShotLink) {
626 if constexpr (same_as<Support::SkipList::Stats_Basic, StatsType>) {
627 ++fStats_.fCompares;
628 }
629 switch (ToInt (fKeyThreeWayComparer_ (n->fEntry.fKey, key))) {
630 case ToInt (strong_ordering::equal):
631 if (std::get_if<key_type> (&keyOrI) or n == get<ForwardIterator> (keyOrI).fCurrent_) {
632 foundLink = n;
633 newOverShotLink = foundLink;
634 goto finished;
635 }
636 else {
637 linksPointingToReturnedLink[linkIndex] = n;
638 n = n->fNext[linkIndex];
639 newOverShotLink = n;
640 }
641 break;
642 case ToInt (strong_ordering::less):
643 linksPointingToReturnedLink[linkIndex] = n;
644 n = n->fNext[linkIndex];
645 //newOverShotLink = n;
646 break;
647 case ToInt (strong_ordering::greater):
648 newOverShotLink = n;
649 // NB: sterl changed this from less case to greater case cuz he thinks will perform better, but untested -- SSW 2024-09-13
650 goto finished;
651 }
652 }
653 finished:
654 /*
655 * Before fixing the next lowest link pointers, reset the start link to the last link linking to our target
656 * This gives us log(n) behavior rather than n^2
657 */
658 if (linkIndex > 0 and linksPointingToReturnedLink[linkIndex] != nullptr) {
659 linksPointingToReturnedLink[linkIndex - 1] = linksPointingToReturnedLink[linkIndex];
660 }
661 } while (linkIndex-- != 0);
662
663 Ensure (foundLink == nullptr or fKeyThreeWayComparer_ (foundLink->fEntry.fKey, key) == strong_ordering::equal);
664
665 //@todo ASK STERL - WHAT IS PROMISED HERE ABOUT linksPointingToReturnedLink. What do NULL values mean? Why do we allow them? Does this promise to return
666 // ALL links pointer key, and ONLY links pointing to key?
667 // --LGP 2024-09-12
668 return LinkAndInfoAboutBackPointers_{foundLink, move (linksPointingToReturnedLink)};
669 }
670
671 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
672 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::GetFirst_ () const -> Link_*
673 {
674 Require (fHead_.size () >= 1);
675 return fHead_[0];
676 }
677 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
678 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::GetLast_ () const -> Link_*
679 {
680 Require (fHead_.size () >= 1);
681 size_t linkIndex = fHead_.size () - 1;
682 Link_* n = fHead_[linkIndex];
683 if (n != nullptr) {
684 Link_* prev = n;
685 while (true) {
686 while (n != nullptr) {
687 prev = n;
688 n = n->fNext[linkIndex];
689 }
690 n = prev;
691 if (linkIndex == 0) {
692 break;
693 }
694 --linkIndex;
695 }
696 }
697 return n;
698 }
699 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
700 template <qCompilerAndStdLib_RequiresNotMatchXXXDefined_1_BWA (invocable<typename SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::value_type>) FUNCTION>
701 inline void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Apply (FUNCTION&& doToElement) const
702 {
703 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{*this};
704 std::for_each (begin (), end (), forward<FUNCTION> (doToElement));
705 }
706 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
707 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Prioritize (ArgByValueType<key_type> key)
708 {
709 LinkAndInfoAboutBackPointers_ keyLinkInfo = FindNearest_ (key);
710 if (keyLinkInfo.fLink != nullptr and keyLinkInfo.fLink->fNext.size () <= fHead_.size ()) {
711 if (keyLinkInfo.fLink->fNext.size () == fHead_.size ()) {
712 GrowHeadLinksIfNeeded_ (fHead_.size () + 1, keyLinkInfo.fLink);
713 keyLinkInfo.fLinksPointingToReturnedLink.resize (fHead_.size (), keyLinkInfo.fLink);
714 }
715 size_t oldLinkHeight = keyLinkInfo.fLink->fNext.size ();
716 keyLinkInfo.fLink->fNext.resize (fHead_.size (), nullptr);
717 size_t newLinkHeight = keyLinkInfo.fLink->fNext.size ();
718 Assert (oldLinkHeight < newLinkHeight);
719 for (size_t i = oldLinkHeight; i <= newLinkHeight - 1; ++i) {
720 if (keyLinkInfo.fLinksPointingToReturnedLink[i] == nullptr) {
721 fHead_[i] = keyLinkInfo.fLink;
722 }
723 else if (keyLinkInfo.fLinksPointingToReturnedLink[i] == keyLinkInfo.fLink) {
724 break;
725 }
726 else {
727 if constexpr (same_as<Support::SkipList::Stats_Basic, StatsType>) {
728 ++fStats_.fRotations;
729 }
730 Link_* oldLink = keyLinkInfo.fLinksPointingToReturnedLink[i];
731 AssertNotNull (oldLink);
732 Assert (oldLink->fNext.size () > i);
733 Link_* nextL = oldLink->fNext[i];
734 oldLink->fNext[i] = keyLinkInfo.fLink;
735 keyLinkInfo.fLink->fNext[i] = nextL;
736 }
737 }
738 }
739 }
740 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
741 template <typename CHECKED_T>
742 inline void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Update (const ForwardIterator& it, ArgByValueType<CHECKED_T> newValue)
743 requires (not same_as<MAPPED_TYPE, void>)
744 {
745 const_cast<ForwardIterator&> (it).UpdateValue (newValue);
746 }
747 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
748 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ReBalance ()
749 {
750 if (empty ()) [[unlikely]] {
751 return;
752 }
753 // precompute table of indices height
754 // idea is to have a link for every log power of the probability at a particular index
755 // for example, for a 1/2 chance, have heights start as 1 2 1 3 1 2 1 4
756 double indexBase = (GetLinkHeightProbability () == 0) ? 0 : 1 / (GetLinkHeightProbability () / 100.0);
757 size_t height[kMaxLinkHeight_];
758 size_t lastValidHeight = 0;
759 for (size_t i = 0; i < sizeof (height) / sizeof (size_t); ++i) {
760 height[i] = size_t (pow (indexBase, double (i)));
761 if (height[i] == 0 or height[i] > size ()) {
762 Assert (i > 0); // else have no valid heights
763 break;
764 }
765 lastValidHeight = i;
766 }
767 // wipe out everything, keeping only a link to the first item in list
768 Link_* link = fHead_[0];
769 fHead_.clear ();
770 fHead_.resize (kMaxLinkHeight_);
771
772 Link_** patchLinks[kMaxLinkHeight_];
773 for (size_t i = 0; i < sizeof (patchLinks) / sizeof (size_t); ++i) {
774 patchLinks[i] = &fHead_[i];
775 }
776
777 size_t index = 1;
778 while (link != nullptr) {
779 Link_* next = link->fNext[0];
780 link->fNext.clear ();
781#if qStroika_Foundation_Debug_AssertionsChecked
782 bool patched = false;
783#endif
784 for (size_t hIndex = lastValidHeight + 1; hIndex-- > 0;) {
785 if (index >= height[hIndex] and (index % height[hIndex] == 0)) {
786 link->fNext.resize (hIndex + 1, nullptr);
787 for (size_t patchIndex = link->fNext.size (); patchIndex-- > 0;) {
788 *patchLinks[patchIndex] = link;
789 patchLinks[patchIndex] = &link->fNext[patchIndex];
790 }
791#if qStroika_Foundation_Debug_AssertionsChecked
792 patched = true;
793#endif
794 break;
795 }
796 }
797#if qStroika_Foundation_Debug_AssertionsChecked
798 Assert (patched);
799#endif
800
801 ++index;
802 link = next;
803 }
804 Assert (index == size () + 1);
805 ShrinkHeadLinksIfNeeded_ ();
806 }
807 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
808 size_t SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::CalcHeight (size_t* totalHeight) const
809 {
810 if (totalHeight != nullptr) {
811 *totalHeight = 0;
812 size_t maxLinkHeight = 0;
813 Link_* n = fHead_[0];
814 while (n != nullptr) {
815 maxLinkHeight = max (maxLinkHeight, n->fNext.size ());
816 *totalHeight += n->fNext.size ();
817 n = n->fNext[0];
818 }
819 Assert (maxLinkHeight == fHead_.size ());
820 }
821 return fHead_.size ();
822 }
823 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
824 constexpr void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Invariant () const noexcept
825 {
826#if qStroika_Foundation_Debug_AssertionsChecked
827 Invariant_ ();
828#endif
829 }
830#if qStroika_Foundation_Debug_AssertionsChecked
831 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
832 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Invariant_ () const noexcept
833 {
834 size_t sz{0};
835 const Link_* n = fHead_[0];
836 while (n != nullptr) {
837 ++sz;
838 KEY_TYPE oldKey = n->fEntry.fKey;
839 for (size_t i = 1; i < n->fNext.size (); ++i) {
840 const Link_* newN = n->fNext[i];
841 if (n == nullptr) {
842 Assert (newN == nullptr);
843 }
844 else {
845 Assert (newN != n);
846 Assert (newN == nullptr or fKeyThreeWayComparer_ (oldKey, newN->fEntry.fKey) != strong_ordering::greater);
847 }
848 }
849 Assert (not n->fNext.empty ());
850 n = n->fNext[0];
851 Assert (n == nullptr or fKeyThreeWayComparer_ (n->fEntry.fKey, oldKey) != strong_ordering::less);
852 }
853 Assert (sz == this->fLength_);
854 }
855#endif
856
857 /*
858 ********************************************************************************
859 *********** SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator ***********
860 ********************************************************************************
861 */
862 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
863 constexpr SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::ForwardIterator (const SkipList* data, UnderlyingIteratorRep startAt) noexcept
864 : fCurrent_{startAt}
865#if qStroika_Foundation_Debug_AssertionsChecked
866 , fData_{data}
867#endif
868 {
869 RequireNotNull (data);
870 // startAt may be nullptr (end)
871 }
872 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
873 constexpr SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::ForwardIterator (const SkipList* data) noexcept
874 : ForwardIterator{data, (RequireExpression (data != nullptr), data->fHead_[0])}
875 {
876 }
877#if qStroika_Foundation_Debug_AssertionsChecked
878 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
879 SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::~ForwardIterator ()
880 {
881 Invariant ();
882 }
883#endif
884 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
885 inline SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::operator bool () const
886 {
887 return not AtEnd ();
888 }
889 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
890 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::AtEnd () const noexcept -> bool
891 {
892 return fCurrent_ == nullptr;
893 }
894 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
895 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::operator* () const -> const value_type&
896 {
897 RequireNotNull (fCurrent_);
898 return fCurrent_->fEntry;
899 }
900 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
901 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::operator->() const -> const value_type*
902 {
903 RequireNotNull (fCurrent_);
904 return &fCurrent_->fEntry;
905 }
906 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
907 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::CurrentIndex (const SkipList* data) const -> size_t
908 {
909 Require (not AtEnd ());
910#if qStroika_Foundation_Debug_AssertionsChecked
911 RequireNotNull (fData_);
912 Require (fData_ == data);
913#endif
914 RequireNotNull (this->fCurrent_);
915 size_t i = 0;
916 for (const Link_* l = data->fHead_;; l = l->fNext[0], ++i) {
917 AssertNotNull (l);
918 if (l == fCurrent_) [[unlikely]] {
919 return i;
920 }
921 }
922 AssertNotReached ();
923 return i;
924 }
925 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
926 inline constexpr bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::operator== (const ForwardIterator& rhs) const
927 {
928#if qStroika_Foundation_Debug_AssertionsChecked
929 Require (fData_ == nullptr or rhs.fData_ == nullptr or fData_ == rhs.fData_); // fData_==null for end sentinel case
930#endif
931 return fCurrent_ == rhs.fCurrent_;
932 }
933 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
934 constexpr auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::GetUnderlyingIteratorRep () const -> UnderlyingIteratorRep
935 {
936 return fCurrent_;
937 }
938 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
939 inline void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::SetUnderlyingIteratorRep (const UnderlyingIteratorRep l)
940 {
941 fCurrent_ = l;
942 }
943 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
944 constexpr void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::AssertDataMatches ([[maybe_unused]] const SkipList* data) const
945 {
946#if qStroika_Foundation_Debug_AssertionsChecked
947 Require (data == fData_);
948#endif
949 }
950 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
951 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::operator++ () -> ForwardIterator&
952 {
953 fCurrent_ = fCurrent_->fNext[0];
954 return *this;
955 }
956 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
957 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::operator++ (int) -> ForwardIterator
958 {
959 ForwardIterator result = *this;
960 this->operator++ ();
961 return result;
962 }
963 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
964 template <typename CHECKED_T>
965 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::UpdateValue (ArgByValueType<CHECKED_T> newValue)
966 requires (not same_as<MAPPED_TYPE, void>)
967 {
968 Link_* link2Update = const_cast<Link_*> (fCurrent_); // logically we could walk from the head of the list without a const_cast, but this is obviously safe and more efficient
969 link2Update->fEntry.fValue = newValue;
970 }
971 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
972 constexpr void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::Invariant () const noexcept
973 {
974#if qStroika_Foundation_Debug_AssertionsChecked
975 Invariant_ ();
976#endif
977 }
978#if qStroika_Foundation_Debug_AssertionsChecked
979 template <typename KEY_TYPE, typename MAPPED_TYPE, Support::SkipList::IValidTraits<KEY_TYPE> TRAITS>
980 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::Invariant_ () const noexcept
981 {
982 // fData_ not always present - for end () iterators
983 Require (AtEnd () or fData_ != nullptr);
984 if (fData_ != nullptr) {
985 fData_->Invariant (); // @todo verify fCurrent_ == nullptr or somewhere inside fData_....
986 }
987 }
988#endif
989
990}
AssertNotNull
#define AssertNotNull(p)
Definition Assertions.h:334
RequireNotNull
#define RequireNotNull(p)
Definition Assertions.h:348
RequireExpression
#define RequireExpression(c)
Definition Assertions.h:268
AssertNotReached
#define AssertNotReached()
Definition Assertions.h:356
Verify
#define Verify(c)
Definition Assertions.h:420
Stroika::Foundation::Containers::DataStructures::SkipList::StatsType
Support::SkipList::StatsType< KEY_TYPE, TRAITS > StatsType
Definition SkipList.h:176
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
std
STL namespace.