-
Notifications
You must be signed in to change notification settings - Fork 2
/
HandyDeque.hpp
2068 lines (1704 loc) · 71.8 KB
/
HandyDeque.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/// ================================================================================
/// Microsoft's implementation of std::deque, but with different tuning values
/// Downloaded on: 9/18/2019
/// https://github.com/microsoft/STL/blob/master/stl/inc/deque
///
/// LICENSE - Apache-2.0 WITH LLVM-exception
///
/// Copyright (c) Microsoft Corporation.
///
/// Licensed under the Apache License, Version 2.0 (the "License");
/// you may not use this file except in compliance with the License.
/// You may obtain a copy of the License at
///
/// http://www.apache.org/licenses/LICENSE-2.0
///
/// Unless required by applicable law or agreed to in writing, software
/// distributed under the License is distributed on an "AS IS" BASIS,
/// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
/// See the License for the specific language governing permissions and
/// limitations under the License.
///
/// As an exception, if, as a result of your compiling your source code,
/// portions of this Software are embedded into an Object form of such
/// source code, you may redistribute such embedded portions in such Object
/// form without complying with the conditions of Sections 4(a), 4(b) and
/// 4(d) of the License.
///
/// In addition, if you combine or link compiled forms of this Software with
/// software that is licensed under the GPLv2 ("Combined Software") and if a
/// court of competent jurisdiction determines that the patent provision
/// (Section 3), the indemnity provision (Section 9) or other Section of the
/// License conflicts with the conditions of the GPLv2, you may retroactively
/// and prospectively choose to deem waived or otherwise exclude such
/// Section(s) of the License, but only in their entirety and only with respect
/// to the Combined Software.
/// ================================================================================
#pragma once
#include "HandyBase.hpp"
#if defined IS_WINDOWS
#include <stdexcept>
#include <stdio.h>
#include <string.h>
#include <algorithm>
/// DEQUE PARAMETERS --- THESE MUST BE POWERS OF TWO:
/// ORIGINAL MSSTL VERSION:
//#define HTD_DEQUEMAPSIZE 8 // minimum map size, at least 1
/*#define HTD_DEQUESIZE \
( sizeof(value_type) <= 1 ? 16 \
: sizeof(value_type) <= 2 ? 8 \
: sizeof(value_type) <= 4 ? 4 \
: sizeof(value_type) <= 8 ? 2 : 1) // elements per block (a power of 2)
*/
/// LIBC++ VALUES:
#define HTD_DEQUEMAPSIZE 8 // minimum map size, at least 1
#define HTD_DEQUESIZE (sizeof(value_type) < 256 ? 4096 / sizeof(value_type) : 16) // elements per block (a power of 2)
#define HTD_ITERATOR_DEBUG_LEVEL 0
#define HTD_HAS_CXX17 1
// Enforcement of matching allocator value_types
#ifndef HTD_ENFORCE_MATCHING_ALLOCATORS
#define HTD_ENFORCE_MATCHING_ALLOCATORS HTD_HAS_CXX17
#endif /* HTD_ENFORCE_MATCHING_ALLOCATORS */
#define HTD_MISMATCHED_ALLOCATOR_MESSAGE(_CONTAINER, _VALUE_TYPE) \
_CONTAINER " requires that Allocator's value_type match " _VALUE_TYPE \
" (See N4659 26.2.1 [container.requirements.general]/16 allocator_type)" \
" Either fix the allocator value_type or define _ENFORCE_MATCHING_ALLOCATORS=0" \
" to suppress this diagnostic."
// warning: constexpr if is a C++17 extension [-Wc++17-extensions]
// warning: user-defined literal suffixes not starting with '_' are reserved [-Wuser-defined-literals]
// warning: unknown pragma ignored [-Wunknown-pragmas]
#ifndef HTD_STL_DISABLE_CLANG_WARNINGS
#ifdef __clang__
#define HTD_STL_DISABLE_CLANG_WARNINGS _Pragma("clang diagnostic push") \
_Pragma("clang diagnostic ignored \"-Wc++17-extensions\"") \
_Pragma("clang diagnostic ignored \"-Wuser-defined-literals\"") \
_Pragma("clang diagnostic ignored \"-Wunknown-pragmas\"")
#else /* __clang__ */
#define HTD_STL_DISABLE_CLANG_WARNINGS
#endif /* __clang__ */
#endif /* HTD_STL_DISABLE_CLANG_WARNINGS */
#ifndef HTD_STL_RESTORE_CLANG_WARNINGS
#ifdef __clang__
#define HTD_STL_RESTORE_CLANG_WARNINGS _Pragma("clang diagnostic pop")
#else /* __clang__ */
#define HTD_STL_RESTORE_CLANG_WARNINGS
#endif /* __clang__ */
#endif /* HTD_STL_RESTORE_CLANG_WARNINGS */
namespace htd {
template<class _Ptrty> inline auto Unfancy(_Ptrty _Ptr) { return (std::addressof(*_Ptr)); } // converts from a fancy pointer to a plain pointer
template<class _Ty> inline _Ty * Unfancy(_Ty * _Ptr) { return (_Ptr); } // do nothing for plain pointers
template <class _Ty, class... _Types>
void Construct_in_place(_Ty& _Obj, _Types&&... _Args) noexcept(std::is_nothrow_constructible_v<_Ty, _Types...>)
{
::new (const_cast<void*>(static_cast<const volatile void*>(std::addressof(_Obj)))) _Ty(std::forward<_Types>(_Args)...);
}
template<class _Ty>
constexpr const _Ty& Min_value(const _Ty& _Left, const _Ty& _Right) noexcept(noexcept(_Right < _Left))
{ // return smaller of _Left and _Right
return (_Right < _Left ? _Right : _Left);
}
template<class _Ty>
constexpr const _Ty& Max_value(const _Ty& _Left, const _Ty& _Right) noexcept(noexcept(_Left < _Right))
{ // return larger of _Left and _Right
return (_Left < _Right ? _Right : _Left);
}
template <class _Ty, class = void> struct Is_allocator : std::false_type {}; // selected when _Ty can't possibly be an allocator
template <class _Ty> struct Is_allocator
<_Ty, std::void_t<typename _Ty::value_type, decltype(std::declval<_Ty&>().deallocate(std::declval<_Ty&>().allocate(size_t{1}), size_t{1}))>>
: std::true_type { }; // selected when _Ty resembles an allocator, N4687 26.2.1 [container.requirements.general]/17
template <class _Alloc> // tests if allocator has simple addressing
inline constexpr bool Is_simple_alloc_v =
std::is_same_v<typename std::allocator_traits<_Alloc>::size_type, size_t>&&
std::is_same_v<typename std::allocator_traits<_Alloc>::difference_type, ptrdiff_t>&&
std::is_same_v<typename std::allocator_traits<_Alloc>::pointer, typename _Alloc::value_type*>&&
std::is_same_v<typename std::allocator_traits<_Alloc>::const_pointer, const typename _Alloc::value_type*>;
template <class _Alloc> using Alloc_ptr_t = typename std::allocator_traits<_Alloc>::pointer;
template <class _Alloc, class _Value_type> using Rebind_alloc_t = typename std::allocator_traits<_Alloc>::template rebind_alloc<_Value_type>;
template <class _Iter> using Iter_ref_t = typename std::iterator_traits<_Iter>::reference;
template <class _Iter> using Iter_value_t = typename std::iterator_traits<_Iter>::value_type;
template <class _Iter> using Iter_cat_t = typename std::iterator_traits<_Iter>::iterator_category;
template <class _Ty, class = void> inline constexpr bool Is_iterator_v = false;
template <class _Ty> inline constexpr bool Is_iterator_v<_Ty, std::void_t<Iter_cat_t<_Ty>>> = true;
template <class _Ty> struct Is_iterator : std::bool_constant<Is_iterator_v<_Ty>> {};
struct Equal_allocators {}; // usually allows contents to be stolen (e.g. with swap)
using Propagate_allocators = std::true_type; // usually allows the allocator to be propagated, and then contents stolen
using No_propagate_allocators = std::false_type; // usually turns moves into copies
// Choose_pocca returns whether an attempt to propagate allocators is necessary in copy assignment operations.
// Note that even when false_type, callers should call _Pocca as we want to assign allocators even when equal.
template <class _Alloc>
using Choose_pocca = std::bool_constant<std::allocator_traits<_Alloc>::propagate_on_container_copy_assignment::value
&& !std::allocator_traits<_Alloc>::is_always_equal::value>;
template <class _Alloc>
using Choose_pocma = std::conditional_t<std::allocator_traits<_Alloc>::is_always_equal::value, Equal_allocators,
typename std::allocator_traits<_Alloc>::propagate_on_container_move_assignment::type>;
template <class NoThrowFwdIt>
inline constexpr bool Use_memset_value_construct_v = std::conjunction_v<std::is_pointer<NoThrowFwdIt>,
std::is_scalar<Iter_value_t<NoThrowFwdIt>>, std::negation<std::is_volatile<std::remove_reference_t<Iter_ref_t<NoThrowFwdIt>>>>,
std::negation<std::is_member_pointer<Iter_value_t<NoThrowFwdIt>>>>;
template <class _Ptr>
_Ptr Zero_range(const _Ptr _First, const _Ptr _Last) // fill [_First, _Last) with zeroes
{
char* const _First_ch = reinterpret_cast<char*>(_First);
char* const _Last_ch = reinterpret_cast<char*>(_Last);
memset(_First_ch, 0, static_cast<size_t>(_Last_ch - _First_ch));
return _Last;
}
template <class NoThrowFwdIt>
struct Uninitialized_backout // struct to undo partially constructed ranges in _Uninitialized_xxx algorithms
{
NoThrowFwdIt _First;
NoThrowFwdIt _Last;
explicit Uninitialized_backout(NoThrowFwdIt _Dest) : _First(_Dest), _Last(_Dest) {}
Uninitialized_backout(NoThrowFwdIt _First_, NoThrowFwdIt _Last_) : _First(_First_), _Last(_Last_) {}
Uninitialized_backout(const Uninitialized_backout&) = delete;
Uninitialized_backout& operator=(const Uninitialized_backout&) = delete;
~Uninitialized_backout() { Destroy_range(_First, _Last); }
template <class... _Types>
void _Emplace_back(_Types&&... _Vals)
{ // construct a new element at *_Last and increment
Construct_in_place(*_Last, std::forward<_Types>(_Vals)...);
++_Last;
}
NoThrowFwdIt _Release()
{ // suppress any exception handling backout and return _Last
_First = _Last;
return _Last;
}
};
template <class NoThrowFwdIt, class _Diff>
NoThrowFwdIt Uninitialized_value_construct_n_unchecked1(NoThrowFwdIt _UFirst, _Diff _Count)
{
// value-initialize all elements in [_UFirst, _UFirst + _Count_raw)
if constexpr (Use_memset_value_construct_v<NoThrowFwdIt>)
{
return Zero_range(_UFirst, _UFirst + _Count);
}
else
{
Uninitialized_backout<NoThrowFwdIt> _Backout{ _UFirst };
for (; 0 < _Count; --_Count)
{
_Backout._Emplace_back();
}
return _Backout._Release();
}
}
template <class _Ty>
void Destroy_in_place(_Ty& _Obj) noexcept
{
_Obj.~_Ty();
}
template <class _NoThrowFwdIt>
void Destroy_range(_NoThrowFwdIt _First, const _NoThrowFwdIt _Last) noexcept
{
// note that this is an optimization for debug mode codegen; in release mode the BE removes all of this
if constexpr(std::is_trivially_destructible_v<Iter_value_t<_NoThrowFwdIt>>)
{
(void) _First;
(void) _Last;
}
else
{
for (; _First != _Last; ++_First)
{
Destroy_in_place(*_First);
}
}
}
template <class _Iter, class _Sentinel>
constexpr void Adl_verify_range(const _Iter& _First, const _Sentinel& _Last) {
// check that [_First, _Last) forms an iterator range
//if constexpr (_Range_verifiable_v<_Iter, _Sentinel>)
//{
// _Verify_range(_First, _Last);
//}
//else
{
(void) _First; // TRANSITION, VSO#486357
(void) _Last; // TRANSITION, VSO#486357
}
}
template <class _Alloc>
void Deallocate_plain(_Alloc& _Al, typename _Alloc::value_type* const _Ptr) noexcept
{
// deallocate a plain pointer using an allocator
using _Alloc_traits = std::allocator_traits<_Alloc>;
if constexpr (std::is_same_v<Alloc_ptr_t<_Alloc>, typename _Alloc::value_type*>)
{
_Alloc_traits::deallocate(_Al, _Ptr, 1);
}
else
{
using _Ptr_traits = std::pointer_traits<Alloc_ptr_t<_Alloc>>;
_Alloc_traits::deallocate(_Al, _Ptr_traits::pointer_to(*_Ptr), 1);
}
}
template <class _Alloc>
void Delete_plain_internal(_Alloc& _Al, typename _Alloc::value_type* const _Ptr) noexcept {
// destroy *_Ptr in place, then deallocate _Ptr using _Al; used for internal container types the user didn't name
using _Ty = typename _Alloc::value_type;
_Ptr->~_Ty();
Deallocate_plain(_Al, _Ptr);
}
template <class _Ty> struct Wrap { _Ty _Value; }; // workaround for "T^ is not allowed in a union"
template <class _Alloc>
struct Alloc_temporary
{
using value_type = typename _Alloc::value_type;
using _Traits = std::allocator_traits<_Alloc>;
_Alloc& _Al;
union
{
Wrap<value_type> _Storage;
};
template <class... _Args>
explicit Alloc_temporary(_Alloc& _Al_, _Args&&... _Vals) noexcept(
noexcept(_Traits::construct(_Al_, std::addressof(_Storage._Value), std::forward<_Args>(_Vals)...)))
: _Al(_Al_) {
_Traits::construct(_Al, std::addressof(_Storage._Value), std::forward<_Args>(_Vals)...);
}
Alloc_temporary(const Alloc_temporary&) = delete;
Alloc_temporary& operator=(const Alloc_temporary&) = delete;
~Alloc_temporary()
{
_Traits::destroy(_Al, std::addressof(_Storage._Value));
}
};
template <class _Iter, class = void>
struct Allow_inheriting_unwrap : std::true_type {};
template <class _Iter>
struct Allow_inheriting_unwrap<_Iter, std::enable_if_t<!std::is_same_v<_Iter, typename _Iter::_Prevent_inheriting_unwrap>>>
: std::false_type {};
template <class _Iter, class = void> struct Unwrappable : std::false_type {};
template <class _Iter> struct Unwrappable<_Iter, std::void_t<decltype(std::declval<_Iter&>()._Seek_to(std::declval<const _Iter&>()._Unwrapped()))>>
: Allow_inheriting_unwrap<_Iter>::type {};
template <class _Iter> inline constexpr bool Unwrappable_v = Unwrappable<_Iter>::value;
template <class _Iter, std::enable_if_t<Unwrappable_v<_Iter>, int> = 0>
[[nodiscard]] constexpr auto Get_unwrapped(const _Iter& _It) { return _It._Unwrapped(); } // unwrap an iterator previously subjected to Adl_verify_range or otherwise validated
template <class _Iter, std::enable_if_t<!Unwrappable_v<_Iter>, int> = 0>
[[nodiscard]] constexpr const _Iter& Get_unwrapped(const _Iter& _It) { return _It; } // (don't) unwrap an iterator previously subjected to Adl_verify_range or otherwise validated
template <class _Iter, std::enable_if_t<!Unwrappable_v<_Iter>, int> = 0>
[[nodiscard]] constexpr const _Iter&& Get_unwrapped(const _Iter&& _It) { return static_cast<const _Iter&&>(_It); } // (don't) unwrap an iterator previously subjected to Adl_verify_range or otherwise validated
template <class _Ty>
[[nodiscard]] constexpr _Ty* Get_unwrapped(_Ty* const _Ptr) { return _Ptr; } // special case already-unwrapped pointers
template <class _Ty>
void Swap_adl(_Ty& _Left, _Ty& _Right) noexcept(std::is_nothrow_swappable<_Ty>::value) { std::swap(_Left, _Right); }
struct Container_base12;
struct Iterator_base12;
struct Container_proxy // store head of iterator chain and back pointer
{
Container_proxy() noexcept : _Mycont(nullptr), _Myfirstiter(nullptr) {}
Container_proxy(Container_base12* _Mycont_) noexcept : _Mycont(_Mycont_), _Myfirstiter(nullptr) {}
const Container_base12* _Mycont;
Iterator_base12* _Myfirstiter;
};
struct Container_base12
{
public:
Container_base12() noexcept : _Myproxy(nullptr) {}
Container_base12(const Container_base12&) = delete;
Container_base12& operator=(const Container_base12&) = delete;
void _Orphan_all() noexcept;
void _Swap_proxy_and_iterators(Container_base12&) noexcept;
template <class _Alloc>
void _Alloc_proxy(_Alloc&& _Al)
{
Container_proxy* const _New_proxy = Unfancy(_Al.allocate(1));
Construct_in_place(*_New_proxy, this);
_Myproxy = _New_proxy;
_New_proxy->_Mycont = this;
}
template <class _Alloc>
void _Reload_proxy(_Alloc&& _Old_alloc, _Alloc&& _New_alloc)
{
// pre: no iterators refer to the existing proxy
Container_proxy* const _New_proxy = Unfancy(_New_alloc.allocate(1));
Construct_in_place(*_New_proxy, this);
_New_proxy->_Mycont = this;
Delete_plain_internal(_Old_alloc, std::exchange(_Myproxy, _New_proxy));
}
Container_proxy* _Myproxy;
};
struct BasicContainer_proxy_ptr12 // smart pointer components for a Container_proxy * that don't depend on the allocator
{
Container_proxy* _Ptr;
void _Release() noexcept { // disengage this BasicContainer_proxy_ptr12
_Ptr = nullptr;
}
protected:
BasicContainer_proxy_ptr12() = default;
BasicContainer_proxy_ptr12(const BasicContainer_proxy_ptr12&) = delete;
BasicContainer_proxy_ptr12(BasicContainer_proxy_ptr12&&) = delete;
};
struct Leave_proxy_unbound {}; // tag to indicate that a proxy is being allocated before it is safe to bind to a
// _Container_base12
template <class _Alloc>
struct Container_proxy_ptr12 : BasicContainer_proxy_ptr12
{
// smart pointer components for a Container_proxy * for an allocator family
_Alloc& _Al;
Container_proxy_ptr12(_Alloc& _Al_, Leave_proxy_unbound) : _Al(_Al_) // create a new unbound Container_proxy
{
_Ptr = Unfancy(_Al_.allocate(1));
Construct_in_place(*_Ptr);
}
Container_proxy_ptr12(_Alloc& _Al_, Container_base12& _Mycont) // create a new Container_proxy pointing at _Mycont
: _Al(_Al_)
{
_Ptr = Unfancy(_Al_.allocate(1));
Construct_in_place(*_Ptr, std::addressof(_Mycont));
_Mycont._Myproxy = _Ptr;
}
void _Bind(_Alloc& _Old_alloc, Container_base12* _Mycont) noexcept
{
// Attach the proxy stored in *this to _Mycont, and destroy _Mycont's existing proxy
// with _Old_alloc. Requires that no iterators are alive referring to _Mycont.
_Ptr->_Mycont = _Mycont;
Delete_plain_internal(_Old_alloc, std::exchange(_Mycont->_Myproxy, std::exchange(_Ptr, nullptr)));
}
~Container_proxy_ptr12()
{
if (_Ptr)
Delete_plain_internal(_Al, _Ptr);
}
};
struct Iterator_base12 // store links to container proxy, next iterator
{
Iterator_base12() noexcept : _Myproxy(nullptr), _Mynextiter(nullptr) {} // construct orphaned iterator
Iterator_base12(const Iterator_base12& _Right) noexcept : _Myproxy(nullptr), _Mynextiter(nullptr) {
*this = _Right;
}
Iterator_base12& operator=(const Iterator_base12& _Right) noexcept
{
if (_Myproxy != _Right._Myproxy)
{
if (_Right._Myproxy)
{
_Adopt(_Right._Myproxy->_Mycont);
}
else { // becoming invalid, disown current parent
#if HTD_ITERATOR_DEBUG_LEVEL == 2
_Lockit _Lock(_LOCK_DEBUG);
_Orphan_me();
#else // HTD_ITERATOR_DEBUG_LEVEL == 2
_Myproxy = nullptr;
#endif // HTD_ITERATOR_DEBUG_LEVEL == 2
}
}
return *this;
}
~Iterator_base12() noexcept
{
#if HTD_ITERATOR_DEBUG_LEVEL == 2
_Lockit _Lock(_LOCK_DEBUG);
_Orphan_me();
#endif // HTD_ITERATOR_DEBUG_LEVEL == 2
}
void _Adopt(const Container_base12* _Parent) noexcept
{
if (_Parent)
{// have a parent, do adoption
Container_proxy* _Parent_proxy = _Parent->_Myproxy;
#if HTD_ITERATOR_DEBUG_LEVEL == 2
if (_Myproxy != _Parent_proxy)
{ // change parentage
_Lockit _Lock(_LOCK_DEBUG);
_Orphan_me();
_Mynextiter = _Parent_proxy->_Myfirstiter;
_Parent_proxy->_Myfirstiter = this;
_Myproxy = _Parent_proxy;
}
#else // HTD_ITERATOR_DEBUG_LEVEL == 2
_Myproxy = _Parent_proxy;
#endif // HTD_ITERATOR_DEBUG_LEVEL == 2
}
else
{// no future parent, just disown current parent
#if HTD_ITERATOR_DEBUG_LEVEL == 2
_Lockit _Lock(_LOCK_DEBUG);
_Orphan_me();
#else // HTD_ITERATOR_DEBUG_LEVEL == 2
_Myproxy = nullptr;
#endif // HTD_ITERATOR_DEBUG_LEVEL == 2
}
}
const Container_base12* _Getcont() const noexcept { return _Myproxy ? _Myproxy->_Mycont : nullptr; }
#if HTD_ITERATOR_DEBUG_LEVEL == 2
void _Orphan_me() noexcept
{
if (_Myproxy) { // adopted, remove self from list
Iterator_base12** _Pnext = &_Myproxy->_Myfirstiter;
while (*_Pnext && *_Pnext != this) {
_Pnext = &(*_Pnext)->_Mynextiter;
}
_STL_VERIFY(*_Pnext, "ITERATOR LIST CORRUPTED!");
*_Pnext = _Mynextiter;
_Myproxy = nullptr;
}
}
#endif // HTD_ITERATOR_DEBUG_LEVEL == 2
static constexpr bool _Unwrap_when_unverified = HTD_ITERATOR_DEBUG_LEVEL == 0;
Container_proxy* _Myproxy;
Iterator_base12* _Mynextiter;
};
// MEMBER FUNCTIONS FOR Container_base12
inline void Container_base12::_Orphan_all() noexcept
{
#if HTD_ITERATOR_DEBUG_LEVEL == 2
if (_Myproxy) { // proxy allocated, drain it
_Lockit _Lock(_LOCK_DEBUG);
for (auto _Pnext = &_Myproxy->_Myfirstiter; *_Pnext; *_Pnext = (*_Pnext)->_Mynextiter) {
(*_Pnext)->_Myproxy = nullptr;
}
_Myproxy->_Myfirstiter = nullptr;
}
#endif // HTD_ITERATOR_DEBUG_LEVEL == 2
}
inline void Container_base12::_Swap_proxy_and_iterators(Container_base12& _Right) noexcept
{
#if HTD_ITERATOR_DEBUG_LEVEL == 2
_Lockit _Lock(_LOCK_DEBUG);
#endif // HTD_ITERATOR_DEBUG_LEVEL == 2
Container_proxy* _Temp = _Myproxy;
_Myproxy = _Right._Myproxy;
_Right._Myproxy = _Temp;
if (_Myproxy)
_Myproxy->_Mycont = this;
if (_Right._Myproxy)
_Right._Myproxy->_Mycont = &_Right;
}
struct Zero_then_variadic_args_t {}; // tag type for value-initializing first, constructing second from remaining args
struct One_then_variadic_args_t {}; // tag type for constructing first from one arg, constructing second from remaining args
template <class _Ty1, class _Ty2, bool = std::is_empty_v<_Ty1> && !std::is_final_v<_Ty1>>
class Compressed_pair final : private _Ty1 { // store a pair of values, deriving from empty first
public:
_Ty2 _Myval2;
using _Mybase = _Ty1; // for visualization
template <class... _Other2>
constexpr explicit Compressed_pair(Zero_then_variadic_args_t, _Other2&&... _Val2) noexcept(
std::conjunction_v<std::is_nothrow_default_constructible<_Ty1>, std::is_nothrow_constructible<_Ty2, _Other2...>>)
: _Ty1(), _Myval2(std::forward<_Other2>(_Val2)...) { }
template <class _Other1, class... _Other2>
Compressed_pair(One_then_variadic_args_t, _Other1&& _Val1, _Other2&&... _Val2) noexcept(
std::conjunction_v<std::is_nothrow_constructible<_Ty1, _Other1>, std::is_nothrow_constructible<_Ty2, _Other2...>>)
: _Ty1(std::forward<_Other1>(_Val1)), _Myval2(std::forward<_Other2>(_Val2)...) { }
_Ty1& _Get_first() noexcept { return *this; }
const _Ty1& _Get_first() const noexcept { return *this; }
};
template <class _Ty1, class _Ty2>
class Compressed_pair<_Ty1, _Ty2, false> final { // store a pair of values, not deriving from first
public:
_Ty1 _Myval1;
_Ty2 _Myval2;
template <class... _Other2>
constexpr explicit Compressed_pair(Zero_then_variadic_args_t, _Other2&&... _Val2) noexcept(
std::conjunction_v<std::is_nothrow_default_constructible<_Ty1>, std::is_nothrow_constructible<_Ty2, _Other2...>>)
: _Myval1(), _Myval2(std::forward<_Other2>(_Val2)...) {}
template <class _Other1, class... _Other2>
Compressed_pair(One_then_variadic_args_t, _Other1&& _Val1, _Other2&&... _Val2) noexcept(
std::conjunction_v<std::is_nothrow_constructible<_Ty1, _Other1>, std::is_nothrow_constructible<_Ty2, _Other2...>>)
: _Myval1(std::forward<_Other1>(_Val1)), _Myval2(std::forward<_Other2>(_Val2)...) {}
_Ty1& _Get_first() noexcept {
return _Myval1;
}
const _Ty1& _Get_first() const noexcept {
return _Myval1;
}
};
template <class _Ty>
struct Tidy_guard
{ // class with destructor that calls _Tidy
_Ty* _Target;
~Tidy_guard()
{
if (_Target)
_Target->_Tidy();
}
};
}
#pragma pack(push, _CRT_PACKING)
#pragma warning(push, _STL_WARNING_LEVEL)
#pragma warning(disable : _STL_DISABLED_WARNINGS)
HTD_STL_DISABLE_CLANG_WARNINGS
#pragma push_macro("new")
#undef new
namespace htd {
// CLASS TEMPLATE DequeUnchecked_const_iterator
template <class _Mydeque>
class DequeUnchecked_const_iterator
{
private:
using _Size_type = typename _Mydeque::size_type;
public:
using iterator_category = std::random_access_iterator_tag;
using value_type = typename _Mydeque::value_type;
using difference_type = typename _Mydeque::difference_type;
using pointer = typename _Mydeque::const_pointer;
using reference = const value_type&;
DequeUnchecked_const_iterator() noexcept : _Mycont(), _Myoff(0) {}
DequeUnchecked_const_iterator(_Size_type _Off, const Container_base12* _Pdeque) noexcept
: _Mycont(static_cast<const _Mydeque*>(_Pdeque)), _Myoff(_Off) {}
[[nodiscard]] reference operator*() const
{
_Size_type _Block = _Mycont->_Getblock(_Myoff);
_Size_type _Off = _Myoff % HTD_DEQUESIZE;
return _Mycont->_Map[_Block][_Off];
}
[[nodiscard]] pointer operator->() const { return std::pointer_traits<pointer>::pointer_to(**this); }
DequeUnchecked_const_iterator& operator++() { ++_Myoff; return *this; }
DequeUnchecked_const_iterator& operator--() { --_Myoff; return *this; }
DequeUnchecked_const_iterator operator++(int) { DequeUnchecked_const_iterator _Tmp = *this; ++_Myoff; return _Tmp; }
DequeUnchecked_const_iterator operator--(int) { DequeUnchecked_const_iterator _Tmp = *this; --_Myoff; return _Tmp; }
DequeUnchecked_const_iterator& operator+=(const difference_type _Off) { _Myoff += _Off; return *this; }
DequeUnchecked_const_iterator& operator-=(const difference_type _Off) { _Myoff -= _Off; return *this; }
[[nodiscard]] DequeUnchecked_const_iterator operator+(const difference_type _Off) const { DequeUnchecked_const_iterator _Tmp = *this; return _Tmp += _Off; }
[[nodiscard]] DequeUnchecked_const_iterator operator-(const difference_type _Off) const { DequeUnchecked_const_iterator _Tmp = *this; return _Tmp -= _Off; }
[[nodiscard]] difference_type operator-(const DequeUnchecked_const_iterator& _Right) const { return static_cast<difference_type>(_Myoff - _Right._Myoff); }
[[nodiscard]] reference operator[](const difference_type _Off) const { return *(*this + _Off); }
[[nodiscard]] bool operator==(const DequeUnchecked_const_iterator& _Right) const { return _Myoff == _Right._Myoff; }
[[nodiscard]] bool operator!=(const DequeUnchecked_const_iterator& _Right) const { return !(*this == _Right); }
[[nodiscard]] bool operator< (const DequeUnchecked_const_iterator& _Right) const { return _Myoff < _Right._Myoff; }
[[nodiscard]] bool operator> (const DequeUnchecked_const_iterator& _Right) const { return _Right < *this; }
[[nodiscard]] bool operator<=(const DequeUnchecked_const_iterator& _Right) const { return !(_Right < *this); }
[[nodiscard]] bool operator>=(const DequeUnchecked_const_iterator& _Right) const { return !(*this < _Right); }
const Container_base12* _Getcont() const { return _Mycont; } // get container pointer
const _Mydeque * _Mycont;
_Size_type _Myoff; // offset of element in deque
};
template <class _Mydeque>
[[nodiscard]] DequeUnchecked_const_iterator<_Mydeque> operator+(
typename DequeUnchecked_const_iterator<_Mydeque>::difference_type _Off,
DequeUnchecked_const_iterator<_Mydeque> _Next) {
return _Next += _Off;
}
// CLASS TEMPLATE DequeUnchecked_iterator
template <class _Mydeque>
class DequeUnchecked_iterator : public DequeUnchecked_const_iterator<_Mydeque> {
private:
using _Size_type = typename _Mydeque::size_type;
using _Mybase = DequeUnchecked_const_iterator<_Mydeque>;
public:
using iterator_category = std::random_access_iterator_tag;
using value_type = typename _Mydeque::value_type;
using difference_type = typename _Mydeque::difference_type;
using pointer = typename _Mydeque::pointer;
using reference = value_type&;
using _Mybase::_Mybase;
[[nodiscard]] reference operator*() const { return const_cast<reference>(_Mybase::operator*()); }
[[nodiscard]] pointer operator->() const { return std::pointer_traits<pointer>::pointer_to(**this); }
DequeUnchecked_iterator& operator++() { _Mybase::operator++(); return *this; }
DequeUnchecked_iterator& operator--() { _Mybase::operator--(); return *this; }
DequeUnchecked_iterator operator++(int) { DequeUnchecked_iterator _Tmp = *this; _Mybase::operator++(); return _Tmp; }
DequeUnchecked_iterator operator--(int) { DequeUnchecked_iterator _Tmp = *this; _Mybase::operator--(); return _Tmp; }
DequeUnchecked_iterator& operator+=(const difference_type _Off) { _Mybase::operator+=(_Off); return *this; }
DequeUnchecked_iterator& operator-=(const difference_type _Off) { _Mybase::operator-=(_Off); return *this; }
[[nodiscard]] DequeUnchecked_iterator operator+(const difference_type _Off) const { DequeUnchecked_iterator _Tmp = *this; return _Tmp += _Off; }
[[nodiscard]] DequeUnchecked_iterator operator-(const difference_type _Off) const { DequeUnchecked_iterator _Tmp = *this; return _Tmp -= _Off; }
[[nodiscard]] difference_type operator-(const _Mybase& _Right) const { return _Mybase::operator-(_Right); }
[[nodiscard]] reference operator[](const difference_type _Off) const { return const_cast<reference>(_Mybase::operator[](_Off)); }
};
template <class _Mydeque>
[[nodiscard]] DequeUnchecked_iterator<_Mydeque> operator+(typename DequeUnchecked_iterator<_Mydeque>::difference_type _Off, DequeUnchecked_iterator<_Mydeque> _Next)
{
return _Next += _Off;
}
// CLASS TEMPLATE Deque_const_iterator
template <class _Mydeque>
class Deque_const_iterator : public Iterator_base12
{
private:
using _Size_type = typename _Mydeque::size_type;
public:
using iterator_category = std::random_access_iterator_tag;
using value_type = typename _Mydeque::value_type;
using difference_type = typename _Mydeque::difference_type;
using pointer = typename _Mydeque::const_pointer;
using reference = const value_type&;
using _Mydeque_t = _Mydeque; // helper for expression evaluator
enum { _EEN_DS = HTD_DEQUESIZE }; // helper for expression evaluator
Deque_const_iterator() noexcept : _Myoff(0) {
_Setcont(nullptr);
}
Deque_const_iterator(_Size_type _Off, const Container_base12* _Pdeque) noexcept : _Myoff(_Off)
{
_Setcont(static_cast<const _Mydeque*>(_Pdeque));
}
[[nodiscard]] reference operator*() const
{
const auto _Mycont = static_cast<const _Mydeque*>(this->_Getcont());
#if HTD_ITERATOR_DEBUG_LEVEL != 0
_STL_VERIFY(_Mycont, "cannot dereference value-initialized deque iterator");
_STL_VERIFY(_Mycont->_Myoff <= this->_Myoff && this->_Myoff < _Mycont->_Myoff + _Mycont->_Mysize,
"cannot deference out of range deque iterator");
#endif // HTD_ITERATOR_DEBUG_LEVEL != 0
_Size_type _Block = _Mycont->_Getblock(_Myoff);
_Size_type _Off = _Myoff % HTD_DEQUESIZE;
return _Mycont->_Map[_Block][_Off];
}
[[nodiscard]] pointer operator->() const { return std::pointer_traits<pointer>::pointer_to(**this); }
Deque_const_iterator& operator++()
{
#if HTD_ITERATOR_DEBUG_LEVEL != 0
const auto _Mycont = static_cast<const _Mydeque*>(this->_Getcont());
_STL_VERIFY(_Mycont, "cannot increment value-initialized deque iterator");
_STL_VERIFY(this->_Myoff < _Mycont->_Myoff + _Mycont->_Mysize, "cannot increment deque iterator past end");
#endif // HTD_ITERATOR_DEBUG_LEVEL != 0
++_Myoff;
return *this;
}
Deque_const_iterator operator++(int)
{
Deque_const_iterator _Tmp = *this;
++*this;
return _Tmp;
}
Deque_const_iterator& operator--()
{
#if HTD_ITERATOR_DEBUG_LEVEL != 0
const auto _Mycont = static_cast<const _Mydeque*>(this->_Getcont());
_STL_VERIFY(_Mycont, "cannot decrement value-initialized deque iterator");
_STL_VERIFY(_Mycont->_Myoff < this->_Myoff, "cannot decrement deque iterator before begin");
#endif // HTD_ITERATOR_DEBUG_LEVEL != 0
--_Myoff;
return *this;
}
Deque_const_iterator operator--(int)
{
Deque_const_iterator _Tmp = *this;
--*this;
return _Tmp;
}
Deque_const_iterator& operator+=(const difference_type _Off)
{
#if HTD_ITERATOR_DEBUG_LEVEL != 0
if (_Off != 0) {
const auto _Mycont = static_cast<const _Mydeque*>(this->_Getcont());
_STL_VERIFY(_Mycont, "cannot seek value-initialized deque iterator");
_STL_VERIFY(
_Mycont->_Myoff <= this->_Myoff + _Off && this->_Myoff + _Off <= _Mycont->_Myoff + _Mycont->_Mysize,
"cannot seek deque iterator out of range");
}
#endif // HTD_ITERATOR_DEBUG_LEVEL != 0
_Myoff += _Off;
return *this;
}
void _Compat(const Deque_const_iterator& _Right) const
{ // test for compatible iterator pair
#if HTD_ITERATOR_DEBUG_LEVEL == 0
(void) _Right;
#else // HTD_ITERATOR_DEBUG_LEVEL == 0
_STL_VERIFY(this->_Getcont() == _Right._Getcont(), "deque iterators incompatible");
#endif // HTD_ITERATOR_DEBUG_LEVEL == 0
}
[[nodiscard]] Deque_const_iterator operator+(const difference_type _Off) const { Deque_const_iterator _Tmp = *this; return _Tmp += _Off; }
Deque_const_iterator& operator-=(const difference_type _Off) { return *this += -_Off; }
[[nodiscard]] Deque_const_iterator operator-(const difference_type _Off) const { Deque_const_iterator _Tmp = *this; return _Tmp -= _Off; }
[[nodiscard]] difference_type operator-(const Deque_const_iterator& _Right) const { _Compat(_Right); return static_cast<difference_type>(this->_Myoff - _Right._Myoff); }
[[nodiscard]] reference operator[](const difference_type _Off) const { return *(*this + _Off); }
[[nodiscard]] bool operator==(const Deque_const_iterator& _Right) const { _Compat(_Right); return this->_Myoff == _Right._Myoff; }
[[nodiscard]] bool operator!=(const Deque_const_iterator& _Right) const { return !(*this == _Right); }
[[nodiscard]] bool operator< (const Deque_const_iterator& _Right) const { _Compat(_Right); return this->_Myoff < _Right._Myoff; }
[[nodiscard]] bool operator> (const Deque_const_iterator& _Right) const { return _Right < *this; }
[[nodiscard]] bool operator<=(const Deque_const_iterator& _Right) const { return !(_Right < *this); }
[[nodiscard]] bool operator>=(const Deque_const_iterator& _Right) const { return !(*this < _Right); }
// set container pointer
void _Setcont(const _Mydeque* _Pdeque) { this->_Adopt(_Pdeque); }
using _Prevent_inheriting_unwrap = Deque_const_iterator;
[[nodiscard]] DequeUnchecked_const_iterator<_Mydeque> _Unwrapped() const { return {this->_Myoff, this->_Getcont()}; }
void _Verify_offset(const difference_type _Off) const noexcept {
#if HTD_ITERATOR_DEBUG_LEVEL == 0
(void) _Off;
#else // ^^^ HTD_ITERATOR_DEBUG_LEVEL == 0 ^^^ // vvv HTD_ITERATOR_DEBUG_LEVEL != 0 vvv
if (_Off != 0) {
const auto _Mycont = static_cast<const _Mydeque*>(this->_Getcont());
_STL_VERIFY(_Mycont, "cannot use value-initialized deque iterator");
_STL_VERIFY(
_Mycont->_Myoff <= this->_Myoff + _Off && this->_Myoff + _Off <= _Mycont->_Myoff + _Mycont->_Mysize,
"cannot seek deque iterator out of range");
}
#endif // HTD_ITERATOR_DEBUG_LEVEL == 0
}
#if HTD_ITERATOR_DEBUG_LEVEL != 0
friend void _Verify_range(const Deque_const_iterator& _First, const Deque_const_iterator& _Last) {
// note _Compat check inside operator<=
_STL_VERIFY(_First <= _Last, "deque iterators transposed");
}
#endif // HTD_ITERATOR_DEBUG_LEVEL != 0
void _Seek_to(const DequeUnchecked_const_iterator<_Mydeque>& _UIt) { _Myoff = _UIt._Myoff; }
_Size_type _Myoff; // offset of element in deque
};
template <class _Mydeque>
[[nodiscard]] Deque_const_iterator<_Mydeque> operator+(
typename Deque_const_iterator<_Mydeque>::difference_type _Off, Deque_const_iterator<_Mydeque> _Next) {
return _Next += _Off;
}
// CLASS TEMPLATE Deque_iterator
template <class _Mydeque>
class Deque_iterator : public Deque_const_iterator<_Mydeque> {
private:
using _Size_type = typename _Mydeque::size_type;
using _Mybase = Deque_const_iterator<_Mydeque>;
public:
using _Deque_unchecked_type = DequeUnchecked_iterator<_Mydeque>;
using iterator_category = std::random_access_iterator_tag;
using value_type = typename _Mydeque::value_type;
using difference_type = typename _Mydeque::difference_type;
using pointer = typename _Mydeque::pointer;
using reference = value_type&;
using _Mybase::_Mybase;
[[nodiscard]] reference operator*() const { return const_cast<reference>(_Mybase::operator*()); }
[[nodiscard]] pointer operator->() const { return std::pointer_traits<pointer>::pointer_to(**this); }
Deque_iterator& operator++() { _Mybase::operator++(); return *this; }
Deque_iterator& operator--() { _Mybase::operator--(); return *this; }
Deque_iterator operator++(int) { Deque_iterator _Tmp = *this; _Mybase::operator++(); return _Tmp; }
Deque_iterator operator--(int) { Deque_iterator _Tmp = *this; _Mybase::operator--(); return _Tmp; }
Deque_iterator& operator+=(const difference_type _Off) { _Mybase::operator+=(_Off); return *this; }
Deque_iterator& operator-=(const difference_type _Off) { _Mybase::operator-=(_Off); return *this; }
using _Mybase::operator-;
[[nodiscard]] Deque_iterator operator+(const difference_type _Off) const { Deque_iterator _Tmp = *this; return _Tmp += _Off; }
[[nodiscard]] Deque_iterator operator-(const difference_type _Off) const { Deque_iterator _Tmp = *this; return _Tmp -= _Off; }
[[nodiscard]] reference operator[](const difference_type _Off) const { return const_cast<reference>(_Mybase::operator[](_Off)); }
using _Prevent_inheriting_unwrap = Deque_iterator;
[[nodiscard]] DequeUnchecked_iterator<_Mydeque> _Unwrapped() const {
return {this->_Myoff, this->_Getcont()};
}
};
template <class _Mydeque>
[[nodiscard]] Deque_iterator<_Mydeque> operator+(typename Deque_iterator<_Mydeque>::difference_type _Off, Deque_iterator<_Mydeque> _Next)
{
return _Next += _Off;
}
// deque TYPE WRAPPERS
template <class _Value_type, class _Size_type, class _Difference_type, class _Pointer, class _Const_pointer,
class _Reference, class _Const_reference, class _Mapptr_type>
struct Deque_iter_types
{
using value_type = _Value_type;
using size_type = _Size_type;
using difference_type = _Difference_type;
using pointer = _Pointer;
using const_pointer = _Const_pointer;
using _Mapptr = _Mapptr_type;
};
template <class _Ty>
struct Deque_simple_types
{
using value_type = _Ty;
using size_type = size_t;
using difference_type = ptrdiff_t;
using pointer = value_type*;
using const_pointer = const value_type*;
using _Mapptr = _Ty**;
};
// CLASS TEMPLATE Deque_val
template <class _Val_types>
class Deque_val : public Container_base12
{
public:
using value_type = typename _Val_types::value_type;
using size_type = typename _Val_types::size_type;
using difference_type = typename _Val_types::difference_type;
using pointer = typename _Val_types::pointer;
using const_pointer = typename _Val_types::const_pointer;
using reference = value_type&;
using const_reference = const value_type&;
using _Mapptr = typename _Val_types::_Mapptr;
Deque_val() noexcept : _Map(), _Mapsize(0), _Myoff(0), _Mysize(0) {}
// NB: _Mapsize and HTD_DEQUESIZE are guaranteed to be powers of 2
size_type _Getblock(size_type _Off) const noexcept { return (_Off / HTD_DEQUESIZE) & (_Mapsize - 1); }
_Mapptr _Map; // pointer to array of pointers to blocks
size_type _Mapsize; // size of map array, zero or 2^N