Stroika Library 3.0d16
 
Loading...
Searching...
No Matches
SkipList.inl
1/*
2 * Copyright(c) Sophist Solutions, Inc. 1990-2025. 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, SkipList_Support::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, SkipList_Support::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, SkipList_Support::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, SkipList_Support::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, SkipList_Support::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, SkipList_Support::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, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
116 SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>& SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::operator= (const SkipList& t)
117 {
118 RemoveAll ();
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, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
144 inline SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::~SkipList ()
145 {
146 RemoveAll ();
147 }
148 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::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, SkipList_Support::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, SkipList_Support::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, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
164 inline size_t SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::size () const
165 {
166 AssertExternallySynchronizedMutex::ReadContext declareContext{*this};
167 return fLength_;
168 }
169 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
170 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::empty () const
171 {
172 AssertExternallySynchronizedMutex::ReadContext declareContext{*this};
173 return fLength_ == 0;
174 }
175 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
176 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::begin () const -> ForwardIterator
177 {
178 AssertExternallySynchronizedMutex::ReadContext declareContext{*this};
179 return ForwardIterator{this};
180 }
181 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::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, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
187 inline void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::MoveIteratorHereAfterClone (ForwardIterator* pi, const SkipList* movedFrom) const
188 {
189 Debug::AssertExternallySynchronizedMutex::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, SkipList_Support::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 AssertExternallySynchronizedMutex::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<SkipList_Support::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, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
252 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Find (ArgByValueType<key_type> key) const -> ForwardIterator
253 {
254 return ForwardIterator{this, FindLink_ (key)};
255 }
256 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
257 template <typename ARG_T>
258 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Find (ARG_T key) const -> ForwardIterator
259 requires (not same_as<typename TRAITS::AlternateFindType, void> and same_as<remove_cvref_t<ARG_T>, typename TRAITS::AlternateFindType>)
260 {
261 return ForwardIterator{this, FindLink_ (key)};
262 }
263#if !qCompilerAndStdLib_RequiresNotMatchInlineOutOfLineForTemplateClassBeingDefined_Buggy
264 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
265 template <predicate<typename SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::value_type> FUNCTION>
266 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Find (FUNCTION&& firstThat) const -> ForwardIterator
267 {
268 for (auto i = begin (); i; ++i) {
269 if (firstThat (*i)) {
270 return i;
271 }
272 }
273 return end ();
274 }
275#endif
276 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
277 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::First (ArgByValueType<key_type> key) const -> optional<mapped_type>
278 {
279 if (auto o = FindLink_ (key)) {
280 return o->fEntry.fValue;
281 }
282 return nullopt;
283 }
284 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
285 template <qCompilerAndStdLib_RequiresNotMatchXXXDefined_1_BWA (predicate<typename SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::value_type>) FUNCTION>
286 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::First (FUNCTION&& firstThat) const -> optional<mapped_type>
287 {
288 for (auto i : *this) {
289 if (firstThat (*i)) {
290 return i->fValue;
291 }
292 }
293 return nullopt;
294 }
295 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
296 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::contains (ArgByValueType<key_type> key) const
297 {
298 AssertExternallySynchronizedMutex::ReadContext declareContext{*this};
299 return FindLink_ (key) != nullptr;
300 }
301 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
302#if qCompilerAndStdLib_RequiresNotMatchInlineOutOfLineForTemplateClassBeingDefined_Buggy
303 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Add1_ (ArgByValueType<key_type> key, ForwardIterator* oAddedI)
304#else
305 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Add (ArgByValueType<key_type> key, ForwardIterator* oAddedI)
306 requires (same_as<mapped_type, void>)
307#endif
308 {
309 AssertExternallySynchronizedMutex::WriteContext declareContext{*this};
310 if constexpr (TRAITS::kCostlyInvariants) {
311 Invariant ();
312 }
313 LinkAndInfoAboutBackPointers keyLinkInfo = FindNearest_ (key);
314 Link_* n = keyLinkInfo.fLink;
315 if (n == nullptr) {
316 Link_* newLink = new Link_{key};
317 AddLink_ (newLink, keyLinkInfo.fLinksPointingToReturnedLink);
318 if constexpr (TRAITS::kCostlyInvariants) {
319 Invariant ();
320 }
321 if (oAddedI != nullptr) [[unlikely]] {
322 *oAddedI = ForwardIterator{this, newLink};
323 }
324 return true;
325 }
326 else {
327 switch (TRAITS::kAddOrExtendOrReplaceMode) {
328 case AddOrExtendOrReplaceMode::eAddIfMissing:
329 return false;
330 case AddOrExtendOrReplaceMode::eAddReplaces:
331 n->fEntry.fKey = key; // two 'different' objects can compare equal, and this updates the value (e.g. stroika set)
332 if constexpr (TRAITS::kCostlyInvariants) {
333 Invariant ();
334 }
335 if (oAddedI != nullptr) [[unlikely]] {
336 *oAddedI = ForwardIterator{this, n};
337 }
338 return true;
339 case AddOrExtendOrReplaceMode::eAddExtras: {
340 Link_* newLink = new Link_{key};
341 AddLink_ (newLink, keyLinkInfo.fLinksPointingToReturnedLink);
342 if constexpr (TRAITS::kCostlyInvariants) {
343 Invariant ();
344 }
345 if (oAddedI != nullptr) [[unlikely]] {
346 *oAddedI = ForwardIterator{this, newLink};
347 }
348 return true;
349 }
350 case AddOrExtendOrReplaceMode::eDuplicatesRejected:
351 static const auto kExcept_ = Execution::RuntimeErrorException<logic_error>{"Duplicates not allowed"sv};
352 Execution::Throw (kExcept_);
353 }
354 AssertNotReached ();
355 return false;
356 }
357 }
358 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
359#if qCompilerAndStdLib_RequiresNotMatchInlineOutOfLineForTemplateClassBeingDefined_Buggy
360 template <typename CHECK_T>
361 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Add2_ (ArgByValueType<key_type> key, ArgByValueType<CHECK_T> val, ForwardIterator* oAddedI)
362#else
363 template <typename CHECK_T>
364 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Add (ArgByValueType<key_type> key, ArgByValueType<CHECK_T> val, ForwardIterator* oAddedI)
365 requires (not same_as<mapped_type, void>)
366#endif
367 {
368 AssertExternallySynchronizedMutex::WriteContext declareContext{*this};
369 if constexpr (TRAITS::kCostlyInvariants) {
370 Invariant ();
371 }
372 LinkAndInfoAboutBackPointers keyLinkInfo = FindNearest_ (key);
373 Link_* n = keyLinkInfo.fLink;
374 if (keyLinkInfo.fLink == nullptr) {
375 Link_* newLink = new Link_{key, val};
376 AddLink_ (newLink, keyLinkInfo.fLinksPointingToReturnedLink);
377 if constexpr (TRAITS::kCostlyInvariants) {
378 Invariant ();
379 }
380 if (oAddedI != nullptr) [[unlikely]] {
381 *oAddedI = ForwardIterator{this, newLink};
382 }
383 return true;
384 }
385 else {
386 switch (TRAITS::kAddOrExtendOrReplaceMode) {
387 case AddOrExtendOrReplaceMode::eAddIfMissing:
388 return false;
389 case AddOrExtendOrReplaceMode::eAddReplaces:
390 n->fEntry.fKey = key; // two 'different' objects can compare equal, and this updates the value (e.g. stroika set)
391 n->fEntry.fValue = val;
392 if constexpr (TRAITS::kCostlyInvariants) {
393 Invariant ();
394 }
395 if (oAddedI != nullptr) [[unlikely]] {
396 *oAddedI = ForwardIterator{this, n};
397 }
398 return true;
399 case AddOrExtendOrReplaceMode::eAddExtras: {
400
401 Link_* newLink = new Link_{key, val};
402 AddLink_ (newLink, keyLinkInfo.fLinksPointingToReturnedLink);
403 if constexpr (TRAITS::kCostlyInvariants) {
404 Invariant ();
405 }
406 if (oAddedI != nullptr) [[unlikely]] {
407 *oAddedI = ForwardIterator{this, newLink};
408 }
409 return true;
410 }
411 case AddOrExtendOrReplaceMode::eDuplicatesRejected:
412 static const auto kExcept_ = Execution::RuntimeErrorException<logic_error>{"Duplicates not allowed"sv};
413 Execution::Throw (kExcept_);
414 }
415 AssertNotReached ();
416 return false;
417 }
418 }
419 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
420 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Add (const value_type& v, ForwardIterator* oAddedI)
421 {
422 return Add (v.fKey, v.fValue, oAddedI);
423 }
424 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
425 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::AddLink_ (Link_* link, const LinkVector_& links)
426 {
427 AssertExternallySynchronizedMutex::WriteContext declareContext{*this};
428 RequireNotNull (link);
429 size_t newLinkHeight = DetermineLinkHeight_ ();
430 link->fNext.resize (newLinkHeight);
431 size_t linksToPatch = min (fHead_.size (), newLinkHeight);
432 for (size_t i = 0; i < linksToPatch; ++i) {
433 Link_* nextL = nullptr;
434 if (links[i] == nullptr) {
435 nextL = fHead_[i];
436 fHead_[i] = link;
437 }
438 else {
439 if constexpr (same_as<SkipList_Support::Stats_Basic, StatsType>) {
440 ++fStats_.fRotations;
441 }
442 Link_* oldLink = links[i];
443 AssertNotNull (oldLink);
444 nextL = oldLink->fNext[i];
445 oldLink->fNext[i] = link;
446 }
447 link->fNext[i] = nextL;
448 }
449 GrowHeadLinksIfNeeded_ (newLinkHeight, link);
450 ++fLength_;
451 }
452 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
453 inline void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Remove (ArgByValueType<key_type> key)
454 {
455 Verify (RemoveIf (key));
456 }
457 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
458 inline void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Remove (const ForwardIterator& it)
459 {
460 // we need the links to reset, so have to re-find (cannot Link_* n = const_cast<Link_*> (it.fCurrent_))
461 LinkAndInfoAboutBackPointers keyLinkInfo = FindNearest_ (it);
462 RequireNotNull (keyLinkInfo.fLink);
463 RemoveLink_ (keyLinkInfo.fLink, keyLinkInfo.fLinksPointingToReturnedLink);
464 if constexpr (TRAITS::kCostlyInvariants) {
465 Invariant ();
466 }
467 }
468 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
469 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::erase (const ForwardIterator& i) -> ForwardIterator
470 {
471 // we need the links to reset, so have to re-find
472 // Link_* n = const_cast<Link_*> (it.fCurrent_);
473 LinkAndInfoAboutBackPointers keyLinkInfo = FindNearest_ (i);
474 RequireNotNull (keyLinkInfo.fLink);
475 Link_* after = keyLinkInfo.fLink->fNext[0]; // result returned
476 RemoveLink_ (keyLinkInfo.fLink, keyLinkInfo.fLinksPointingToReturnedLink);
477 if constexpr (TRAITS::kCostlyInvariants) {
478 Invariant ();
479 }
480 return after == nullptr ? end () : ForwardIterator{this, after};
481 }
482 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
483 inline bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::RemoveIf (ArgByValueType<key_type> key)
484 {
485 AssertExternallySynchronizedMutex::WriteContext declareContext{*this};
486 if constexpr (TRAITS::kCostlyInvariants) {
487 Invariant ();
488 }
489 LinkAndInfoAboutBackPointers keyLinkInfo = FindNearest_ (key);
490 if (keyLinkInfo.fLink != nullptr) {
491 RemoveLink_ (keyLinkInfo.fLink, keyLinkInfo.fLinksPointingToReturnedLink);
492 if constexpr (TRAITS::kCostlyInvariants) {
493 Invariant ();
494 }
495 return true;
496 }
497 else {
498 return false;
499 }
500 }
501 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
502 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::RemoveLink_ (Link_* n, const LinkVector_& links)
503 {
504 AssertExternallySynchronizedMutex::WriteContext declareContext{*this};
505 for (auto it = links.begin (); it != links.end (); ++it) {
506 size_t index = it - links.begin ();
507 Link_** patchLink = (*it == nullptr) ? &fHead_[index] : &(*it)->fNext[index];
508 if (*patchLink == n) {
509 if constexpr (same_as<SkipList_Support::Stats_Basic, StatsType>) {
510 ++fStats_.fRotations;
511 }
512 *patchLink = n->fNext[index];
513 }
514 else {
515 break; //? @todo document why we can stop here???
516 }
517 }
518 if (n->fNext.size () == fHead_.size ()) {
519 ShrinkHeadLinksIfNeeded_ ();
520 }
521 delete n;
522 --fLength_;
523 }
524 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
525 size_t SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::DetermineLinkHeight_ () const
526 {
527 constexpr size_t kMaxNewGrowth = 1;
528 size_t linkHeight = 1;
529 size_t maxHeight = min (fHead_.size () + kMaxNewGrowth, size_t (kMaxLinkHeight_));
530 while ((linkHeight < maxHeight) and (Private_::RandomSize_t (1, 100) <= GetLinkHeightProbability ())) {
531 ++linkHeight;
532 }
533 return linkHeight;
534 }
535 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
536 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::GrowHeadLinksIfNeeded_ (size_t newSize, Link_* linkToPointTo)
537 {
538 if (newSize > fHead_.size ()) {
539 fHead_.resize (newSize, linkToPointTo);
540 Assert (fHead_[newSize - 1] == linkToPointTo);
541 }
542 }
543 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
544 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ShrinkHeadLinksIfNeeded_ ()
545 {
546 Require (fHead_.size () >= 1);
547 for (size_t i = fHead_.size () - 1; i >= 1; --i) {
548 if (fHead_[i] == nullptr) {
549 fHead_.pop_back ();
550 }
551 }
552 Ensure (fHead_.size () >= 1);
553 }
554 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
555 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::RemoveAll ()
556 {
557 AssertExternallySynchronizedMutex::WriteContext declareContext{*this};
558 Link_* link = (fHead_.size () == 0) ? nullptr : fHead_[0];
559 while (link != nullptr) {
560 Link_* nextLink = link->fNext[0];
561 delete link;
562 link = nextLink;
563 }
564 fHead_.resize (1);
565 fHead_[0] = nullptr;
566 fLength_ = 0;
567 Ensure (size () == 0);
568 }
569 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
570 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::FindNearest_ (const variant<key_type, ForwardIterator>& keyOrI) const -> LinkAndInfoAboutBackPointers
571 {
572 LinkVector_ linksPointingToReturnedLink;
573 key_type key = std::get_if<key_type> (&keyOrI) ? std::get<key_type> (keyOrI) : get<ForwardIterator> (keyOrI).fCurrent_->fEntry.fKey;
574 using Common::ToInt;
575 Assert (fHead_.size () > 0);
576 linksPointingToReturnedLink = fHead_;
577 Link_* newOverShotLink = nullptr;
578 Link_* foundLink = nullptr;
579 Assert (not linksPointingToReturnedLink.empty ()); // now
580 size_t linkIndex = linksPointingToReturnedLink.size () - 1;
581 do {
582 Link_* n = linksPointingToReturnedLink[linkIndex];
583 // tweak to use pointer comparisons rather than key field compares. We know any link higher than the current link being
584 // tested must point past the key we are looking for, so we can compare our current link with that one and skip the
585 // test if they are the same. In practice, seems to avoid 3-10% of all compares
586 Link_* overShotLink = newOverShotLink;
587 Assert (n == nullptr or overShotLink == nullptr or
588 (fKeyThreeWayComparer_ (n->fEntry.fKey, overShotLink->fEntry.fKey) != strong_ordering::greater));
589
590 linksPointingToReturnedLink[linkIndex] = nullptr;
591 while (n != overShotLink) {
592 if constexpr (same_as<SkipList_Support::Stats_Basic, StatsType>) {
593 ++fStats_.fCompares;
594 }
595 switch (ToInt (fKeyThreeWayComparer_ (n->fEntry.fKey, key))) {
596 case ToInt (strong_ordering::equal):
597 if (std::get_if<key_type> (&keyOrI) or n == get<ForwardIterator> (keyOrI).fCurrent_) {
598 foundLink = n;
599 newOverShotLink = foundLink;
600 goto finished;
601 }
602 else {
603 linksPointingToReturnedLink[linkIndex] = n;
604 n = n->fNext[linkIndex];
605 newOverShotLink = n;
606 }
607 break;
608 case ToInt (strong_ordering::less):
609 linksPointingToReturnedLink[linkIndex] = n;
610 n = n->fNext[linkIndex];
611 //newOverShotLink = n;
612 break;
613 case ToInt (strong_ordering::greater):
614 newOverShotLink = n;
615 // NB: sterl changed this from less case to greater case cuz he thinks will perform better, but untested -- SSW 2024-09-13
616 goto finished;
617 }
618 }
619 finished:
620 /*
621 * Before fixing the next lowest link pointers, reset the start link to the last link linking to our target
622 * This gives us log(n) behavior rather than n^2
623 */
624 if (linkIndex > 0 and linksPointingToReturnedLink[linkIndex] != nullptr) {
625 linksPointingToReturnedLink[linkIndex - 1] = linksPointingToReturnedLink[linkIndex];
626 }
627 } while (linkIndex-- != 0);
628
629 Ensure (foundLink == nullptr or fKeyThreeWayComparer_ (foundLink->fEntry.fKey, key) == strong_ordering::equal);
630
631 //@todo ASK STERL - WHAT IS PROMISED HERE ABOUT linksPointingToReturnedLink. What do NULL values mean? Why do we allow them? Does this promise to return
632 // ALL links pointer key, and ONLY links pointing to key?
633 // --LGP 2024-09-12
634 return LinkAndInfoAboutBackPointers{foundLink, move (linksPointingToReturnedLink)};
635 }
636
637 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
638 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::GetFirst_ () const -> Link_*
639 {
640 Require (fHead_.size () >= 1);
641 return fHead_[0];
642 }
643 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
644 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::GetLast_ () const -> Link_*
645 {
646 Require (fHead_.size () >= 1);
647 size_t linkIndex = fHead_.size () - 1;
648 Link_* n = fHead_[linkIndex];
649 if (n != nullptr) {
650 Link_* prev = n;
651 while (true) {
652 while (n != nullptr) {
653 prev = n;
654 n = n->fNext[linkIndex];
655 }
656 n = prev;
657 if (linkIndex == 0) {
658 break;
659 }
660 --linkIndex;
661 }
662 }
663 return n;
664 }
665 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
666 template <qCompilerAndStdLib_RequiresNotMatchXXXDefined_1_BWA (invocable<typename SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::value_type>) FUNCTION>
667 inline void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Apply (FUNCTION&& doToElement) const
668 {
669 Debug::AssertExternallySynchronizedMutex::ReadContext declareContext{*this};
670 std::for_each (begin (), end (), forward<FUNCTION> (doToElement));
671 }
672 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
673 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Prioritize (ArgByValueType<key_type> key)
674 {
675 LinkAndInfoAboutBackPointers keyLinkInfo = FindNearest_ (key);
676 if (keyLinkInfo.fLink != nullptr and keyLinkInfo.fLink->fNext.size () <= fHead_.size ()) {
677 if (keyLinkInfo.fLink->fNext.size () == fHead_.size ()) {
678 GrowHeadLinksIfNeeded_ (fHead_.size () + 1, keyLinkInfo.fLink);
679 keyLinkInfo.fLinksPointingToReturnedLink.resize (fHead_.size (), keyLinkInfo.fLink);
680 }
681 size_t oldLinkHeight = keyLinkInfo.fLink->fNext.size ();
682 keyLinkInfo.fLink->fNext.resize (fHead_.size (), nullptr);
683 size_t newLinkHeight = keyLinkInfo.fLink->fNext.size ();
684 Assert (oldLinkHeight < newLinkHeight);
685 for (size_t i = oldLinkHeight; i <= newLinkHeight - 1; ++i) {
686 if (keyLinkInfo.fLinksPointingToReturnedLink[i] == nullptr) {
687 fHead_[i] = keyLinkInfo.fLink;
688 }
689 else if (keyLinkInfo.fLinksPointingToReturnedLink[i] == keyLinkInfo.fLink) {
690 break;
691 }
692 else {
693 if constexpr (same_as<SkipList_Support::Stats_Basic, StatsType>) {
694 ++fStats_.fRotations;
695 }
696 Link_* oldLink = keyLinkInfo.fLinksPointingToReturnedLink[i];
697 AssertNotNull (oldLink);
698 Assert (oldLink->fNext.size () > i);
699 Link_* nextL = oldLink->fNext[i];
700 oldLink->fNext[i] = keyLinkInfo.fLink;
701 keyLinkInfo.fLink->fNext[i] = nextL;
702 }
703 }
704 }
705 }
706 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
707 template <typename CHECKED_T>
708 inline void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Update (const ForwardIterator& it, ArgByValueType<CHECKED_T> newValue)
709 requires (not same_as<MAPPED_TYPE, void>)
710 {
711 const_cast<ForwardIterator&> (it).UpdateValue (newValue);
712 }
713 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
714 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ReBalance ()
715 {
716 if (empty ()) [[unlikely]] {
717 return;
718 }
719 // precompute table of indices height
720 // idea is to have a link for every log power of the probability at a particular index
721 // for example, for a 1/2 chance, have heights start as 1 2 1 3 1 2 1 4
722 double indexBase = (GetLinkHeightProbability () == 0) ? 0 : 1 / (GetLinkHeightProbability () / 100.0);
723 size_t height[kMaxLinkHeight_];
724 size_t lastValidHeight = 0;
725 for (size_t i = 0; i < sizeof (height) / sizeof (size_t); ++i) {
726 height[i] = size_t (pow (indexBase, double (i)));
727 if (height[i] == 0 or height[i] > size ()) {
728 Assert (i > 0); // else have no valid heights
729 break;
730 }
731 lastValidHeight = i;
732 }
733 // wipe out everything, keeping only a link to the first item in list
734 Link_* link = fHead_[0];
735 fHead_.clear ();
736 fHead_.resize (kMaxLinkHeight_);
737
738 Link_** patchLinks[kMaxLinkHeight_];
739 for (size_t i = 0; i < sizeof (patchLinks) / sizeof (size_t); ++i) {
740 patchLinks[i] = &fHead_[i];
741 }
742
743 size_t index = 1;
744 while (link != nullptr) {
745 Link_* next = link->fNext[0];
746 link->fNext.clear ();
747#if qStroika_Foundation_Debug_AssertionsChecked
748 bool patched = false;
749#endif
750 for (size_t hIndex = lastValidHeight + 1; hIndex-- > 0;) {
751 if (index >= height[hIndex] and (index % height[hIndex] == 0)) {
752 link->fNext.resize (hIndex + 1, nullptr);
753 for (size_t patchIndex = link->fNext.size (); patchIndex-- > 0;) {
754 *patchLinks[patchIndex] = link;
755 patchLinks[patchIndex] = &link->fNext[patchIndex];
756 }
757#if qStroika_Foundation_Debug_AssertionsChecked
758 patched = true;
759#endif
760 break;
761 }
762 }
763#if qStroika_Foundation_Debug_AssertionsChecked
764 Assert (patched);
765#endif
766
767 ++index;
768 link = next;
769 }
770 Assert (index == size () + 1);
771 ShrinkHeadLinksIfNeeded_ ();
772 }
773 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
774 size_t SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::CalcHeight (size_t* totalHeight) const
775 {
776 if (totalHeight != nullptr) {
777 *totalHeight = 0;
778 size_t maxLinkHeight = 0;
779 Link_* n = fHead_[0];
780 while (n != nullptr) {
781 maxLinkHeight = max (maxLinkHeight, n->fNext.size ());
782 *totalHeight += n->fNext.size ();
783 n = n->fNext[0];
784 }
785 Assert (maxLinkHeight == fHead_.size ());
786 }
787 return fHead_.size ();
788 }
789 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
790 constexpr void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Invariant () const noexcept
791 {
792#if qStroika_Foundation_Debug_AssertionsChecked
793 Invariant_ ();
794#endif
795 }
796#if qStroika_Foundation_Debug_AssertionsChecked
797 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
798 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::Invariant_ () const noexcept
799 {
800 size_t sz{0};
801 const Link_* n = fHead_[0];
802 while (n != nullptr) {
803 ++sz;
804 KEY_TYPE oldKey = n->fEntry.fKey;
805 for (size_t i = 1; i < n->fNext.size (); ++i) {
806 const Link_* newN = n->fNext[i];
807 if (n == nullptr) {
808 Assert (newN == nullptr);
809 }
810 else {
811 Assert (newN != n);
812 Assert (newN == nullptr or fKeyThreeWayComparer_ (oldKey, newN->fEntry.fKey) != strong_ordering::greater);
813 }
814 }
815 Assert (not n->fNext.empty ());
816 n = n->fNext[0];
817 Assert (n == nullptr or fKeyThreeWayComparer_ (n->fEntry.fKey, oldKey) != strong_ordering::less);
818 }
819 Assert (sz == this->fLength_);
820 }
821#endif
822
823 /*
824 ********************************************************************************
825 *********** SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator ***********
826 ********************************************************************************
827 */
828 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
829 constexpr SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::ForwardIterator (const SkipList* data, UnderlyingIteratorRep startAt) noexcept
830 : fCurrent_{startAt}
831#if qStroika_Foundation_Debug_AssertionsChecked
832 , fData_{data}
833#endif
834 {
835 RequireNotNull (data);
836 // startAt may be nullptr (end)
837 }
838 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
839 constexpr SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::ForwardIterator (const SkipList* data) noexcept
840 : ForwardIterator{data, (RequireExpression (data != nullptr), data->fHead_[0])}
841 {
842 }
843#if qStroika_Foundation_Debug_AssertionsChecked
844 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
845 SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::~ForwardIterator ()
846 {
847 Invariant ();
848 }
849#endif
850 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
851 inline SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::operator bool () const
852 {
853 return not Done ();
854 }
855 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
856 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::Done () const noexcept -> bool
857 {
858 return fCurrent_ == nullptr;
859 }
860 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
861 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::operator* () const -> const value_type&
862 {
863 RequireNotNull (fCurrent_);
864 return fCurrent_->fEntry;
865 }
866 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
867 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::operator->() const -> const value_type*
868 {
869 RequireNotNull (fCurrent_);
870 return &fCurrent_->fEntry;
871 }
872 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
873 inline auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::CurrentIndex (const SkipList* data) const -> size_t
874 {
875 Require (not Done ());
876#if qStroika_Foundation_Debug_AssertionsChecked
877 RequireNotNull (fData_);
878 Require (fData_ == data);
879#endif
880 RequireNotNull (this->fCurrent_);
881 size_t i = 0;
882 for (const Link_* l = data->fHead_;; l = l->fNext[0], ++i) {
883 AssertNotNull (l);
884 if (l == fCurrent_) [[unlikely]] {
885 return i;
886 }
887 }
888 AssertNotReached ();
889 return i;
890 }
891 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
892 inline constexpr bool SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::operator== (const ForwardIterator& rhs) const
893 {
894#if qStroika_Foundation_Debug_AssertionsChecked
895 Require (fData_ == nullptr or rhs.fData_ == nullptr or fData_ == rhs.fData_); // fData_==null for end sentinel case
896#endif
897 return fCurrent_ == rhs.fCurrent_;
898 }
899 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
900 constexpr auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::GetUnderlyingIteratorRep () const -> UnderlyingIteratorRep
901 {
902 return fCurrent_;
903 }
904 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
905 inline void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::SetUnderlyingIteratorRep (const UnderlyingIteratorRep l)
906 {
907 fCurrent_ = l;
908 }
909 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
910 constexpr void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::AssertDataMatches ([[maybe_unused]] const SkipList* data) const
911 {
912#if qStroika_Foundation_Debug_AssertionsChecked
913 Require (data == fData_);
914#endif
915 }
916 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
917 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::operator++ () -> ForwardIterator&
918 {
919 fCurrent_ = fCurrent_->fNext[0];
920 return *this;
921 }
922 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
923 auto SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::operator++ (int) -> ForwardIterator
924 {
925 ForwardIterator result = *this;
926 this->operator++ ();
927 return result;
928 }
929 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
930 template <typename CHECKED_T>
931 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::UpdateValue (ArgByValueType<CHECKED_T> newValue)
932 requires (not same_as<MAPPED_TYPE, void>)
933 {
934 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
935 link2Update->fEntry.fValue = newValue;
936 }
937 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
938 constexpr void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::Invariant () const noexcept
939 {
940#if qStroika_Foundation_Debug_AssertionsChecked
941 Invariant_ ();
942#endif
943 }
944#if qStroika_Foundation_Debug_AssertionsChecked
945 template <typename KEY_TYPE, typename MAPPED_TYPE, SkipList_Support::IValidTraits<KEY_TYPE> TRAITS>
946 void SkipList<KEY_TYPE, MAPPED_TYPE, TRAITS>::ForwardIterator::Invariant_ () const noexcept
947 {
948 // fData_ not always present - for end () iterators
949 Require (Done () or fData_ != nullptr);
950 if (fData_ != nullptr) {
951 fData_->Invariant (); // @todo verify fCurrent_ == nullptr or somewhere inside fData_....
952 }
953 }
954#endif
955
956}
AssertNotNull
#define AssertNotNull(p)
Definition Assertions.h:333
RequireNotNull
#define RequireNotNull(p)
Definition Assertions.h:347
RequireExpression
#define RequireExpression(c)
Definition Assertions.h:267
AssertNotReached
#define AssertNotReached()
Definition Assertions.h:355
Verify
#define Verify(c)
Definition Assertions.h:419
Stroika::Foundation::Containers::DataStructures::SkipList::StatsType
SkipList_Support::StatsType< KEY_TYPE, TRAITS > StatsType
Definition SkipList.h:176
std
STL namespace.