-
Notifications
You must be signed in to change notification settings - Fork 27
/
Copy pathlibfork.hpp
10306 lines (8489 loc) · 316 KB
/
libfork.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
//---------------------------------------------------------------//
// This is a machine generated file DO NOT EDIT IT //
//---------------------------------------------------------------//
#ifndef EDCA974A_808F_4B62_95D5_4D84E31B8911
#define EDCA974A_808F_4B62_95D5_4D84E31B8911
// Copyright © Conor Williams <[email protected]>
// SPDX-License-Identifier: MPL-2.0
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.
#ifndef A6BE090F_9077_40E8_9B57_9BAFD9620469
#define A6BE090F_9077_40E8_9B57_9BAFD9620469
// Copyright © Conor Williams <[email protected]>
// SPDX-License-Identifier: MPL-2.0
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.
#ifndef A951FB73_0FCF_4B7C_A997_42B7E87D21CB
#define A951FB73_0FCF_4B7C_A997_42B7E87D21CB
// Copyright © Conor Williams <[email protected]>
// SPDX-License-Identifier: MPL-2.0
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.
#include <array> // for tuple_element, tuple_size
#include <concepts> // for default_initializable
#include <cstddef> // for size_t
#include <memory> // for destroy
#include <span> // for span
#include <type_traits> // for integral_constant, type_identity
#ifndef CF97E524_27A6_4CD9_8967_39F1B1BE97B6
#define CF97E524_27A6_4CD9_8967_39F1B1BE97B6
// Copyright © Conor Williams <[email protected]>
// SPDX-License-Identifier: MPL-2.0
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.
#include <stdexcept> // for runtime_error
#include <utility> // for move
#ifndef D66BBECE_E467_4EB6_B74A_AAA2E7256E02
#define D66BBECE_E467_4EB6_B74A_AAA2E7256E02
// Copyright © Conor Williams <[email protected]>
// SPDX-License-Identifier: MPL-2.0
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.
#include <functional> // for function
#include <utility> // for move
#include <version> // for __cpp_lib_move_only_function
#ifndef C9703881_3D9C_41A5_A7A2_44615C4CFA6A
#define C9703881_3D9C_41A5_A7A2_44615C4CFA6A
// Copyright © Conor Williams <[email protected]>
// SPDX-License-Identifier: MPL-2.0
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.
#include <algorithm> // for max
#include <atomic> // for atomic, atomic_thread_fence, memory_order, memo...
#include <bit> // for has_single_bit
#include <concepts> // for convertible_to, invocable, default_initializable
#include <cstddef> // for ptrdiff_t, size_t
#include <functional> // for invoke
#include <memory> // for unique_ptr, make_unique
#include <optional> // for optional
#include <type_traits> // for invoke_result_t
#include <utility> // for addressof, forward, exchange
#include <vector> // for vector
#include <version> // for ptrdiff_t
#ifndef F70CC480_E6E6_43C1_A7D6_3EEB74F05088
#define F70CC480_E6E6_43C1_A7D6_3EEB74F05088
// Copyright © 2024 Conor Williams <[email protected]>
// Copyright © 2020 Andrey Semashev
// SPDX-License-Identifier: BSL-1.0
// Distributed under the Boost Software License, Version 1.0.
// Permission is hereby granted, free of charge, to any person or organization
// obtaining a copy of the software and accompanying documentation covered by
// this license (the "Software") to use, reproduce, display, distribute,
// execute, and transmit the Software, and to prepare derivative works of the
// Software, and to permit third-parties to whom the Software is furnished to
// do so, all subject to the following:
//
// The copyright notices in the Software and this entire statement, including
// the above license grant, this restriction and the following disclaimer,
// must be included in all copies of the Software, in whole or in part, and
// all derivative works of the Software, unless such copies or derivative
// works are solely in the form of machine-executable object code generated by
// a source language processor.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.
#include <atomic>
#ifndef C5DCA647_8269_46C2_B76F_5FA68738AEDA
#define C5DCA647_8269_46C2_B76F_5FA68738AEDA
// Copyright © Conor Williams <[email protected]>
// SPDX-License-Identifier: MPL-2.0
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.
#include <cassert> // for assert
#include <version> // for __cpp_lib_unreachable, ...
/**
* @file macro.hpp
*
* @brief A collection of internal/public macros.
*
* These are exhaustively documented due to macros nasty visibility rules however, only
* macros that are marked as __[public]__ should be consumed.
*/
// NOLINTBEGIN Sometime macros are the only way to do things...
/**
* @brief __[public]__ The major version of libfork.
*
* Increments with incompatible API changes.
*/
#define LF_VERSION_MAJOR 3
/**
* @brief __[public]__ The minor version of libfork.
*
* Increments when functionality is added in an API backward compatible manner.
*/
#define LF_VERSION_MINOR 8
/**
* @brief __[public]__ The patch version of libfork.
*
* Increments when bug fixes are made in an API backward compatible manner.
*/
#define LF_VERSION_PATCH 0
/**
* @brief Use to conditionally decorate lambdas and ``operator()`` (alongside ``LF_STATIC_CONST``) with
* ``static``.
*/
#ifdef __cpp_static_call_operator
#define LF_STATIC_CALL static
#else
#define LF_STATIC_CALL
#endif
/**
* @brief Use with ``LF_STATIC_CALL`` to conditionally decorate ``operator()`` with ``const``.
*/
#ifdef __cpp_static_call_operator
#define LF_STATIC_CONST
#else
#define LF_STATIC_CONST const
#endif
// clang-format off
/**
* @brief Use like `BOOST_HOF_RETURNS` to define a function/lambda with all the noexcept/requires/decltype specifiers.
*
* This macro is not truly variadic but the ``...`` allows commas in the macro argument.
*/
#define LF_HOF_RETURNS(...) noexcept(noexcept(__VA_ARGS__)) -> decltype(__VA_ARGS__) requires requires { __VA_ARGS__; } { return __VA_ARGS__;}
// clang-format on
/**
* @brief __[public]__ Detects if the compiler has exceptions enabled.
*
* Overridable by defining ``LF_COMPILER_EXCEPTIONS``.
*/
#ifndef LF_COMPILER_EXCEPTIONS
#if defined(__cpp_exceptions) || (defined(_MSC_VER) && defined(_CPPUNWIND)) || defined(__EXCEPTIONS)
#define LF_COMPILER_EXCEPTIONS 1
#else
#define LF_COMPILER_EXCEPTIONS 0
#endif
#endif
#if LF_COMPILER_EXCEPTIONS || defined(LF_DOXYGEN_SHOULD_SKIP_THIS)
/**
* @brief Expands to ``try`` if exceptions are enabled, otherwise expands to ``if constexpr (true)``.
*/
#define LF_TRY try
/**
* @brief Expands to ``catch (...)`` if exceptions are enabled, otherwise expands to ``if constexpr
* (false)``.
*/
#define LF_CATCH_ALL catch (...)
/**
* @brief Expands to ``throw X`` if exceptions are enabled, otherwise terminates the program.
*/
#define LF_THROW(X) throw X
/**
* @brief Expands to ``throw`` if exceptions are enabled, otherwise terminates the program.
*/
#define LF_RETHROW throw
#else
#include <exception>
#define LF_TRY if constexpr (true)
#define LF_CATCH_ALL if constexpr (false)
#ifndef NDEBUG
#define LF_THROW(X) assert(false && "Tried to throw: " #X)
#else
#define LF_THROW(X) std::terminate()
#endif
#ifndef NDEBUG
#define LF_RETHROW assert(false && "Tried to rethrow without compiler exceptions")
#else
#define LF_RETHROW std::terminate()
#endif
#endif
#ifdef __cpp_lib_unreachable
#include <utility>
#endif
namespace lf::impl {
#ifdef __cpp_lib_unreachable
using std::unreachable;
#else
/**
* @brief A homebrew version of `std::unreachable`, see https://en.cppreference.com/w/cpp/utility/unreachable
*/
[[noreturn]] inline void unreachable() {
// Uses compiler specific extensions if possible.
#if defined(_MSC_VER) && !defined(__clang__) // MSVC
__assume(false);
#else // GCC, Clang
__builtin_unreachable();
#endif
// Even if no extension is used, undefined behavior is still raised by infinite loop.
for (;;) {
}
}
#endif
} // namespace lf::impl
/**
* @brief Invokes undefined behavior if ``expr`` evaluates to `false`.
*
* \rst
*
* .. warning::
*
* This has different semantics than ``[[assume(expr)]]`` as it WILL evaluate the
* expression at runtime. Hence you should conservatively only use this macro
* if ``expr`` is side-effect free and cheap to evaluate.
*
* \endrst
*/
#define LF_ASSUME(expr) \
do { \
if (!(expr)) { \
::lf::impl::unreachable(); \
} \
} while (false)
/**
* @brief If ``NDEBUG`` is defined then ``LF_ASSERT(expr)`` is `` `` otherwise ``assert(expr)``.
*
* This is for expressions with side-effects.
*/
#ifndef NDEBUG
#define LF_ASSERT_NO_ASSUME(expr) assert(expr)
#else
#define LF_ASSERT_NO_ASSUME(expr) \
do { \
} while (false)
#endif
/**
* @brief If ``NDEBUG`` is defined then ``LF_ASSERT(expr)`` is ``LF_ASSUME(expr)`` otherwise
* ``assert(expr)``.
*/
#ifndef NDEBUG
#define LF_ASSERT(expr) assert(expr)
#else
#define LF_ASSERT(expr) LF_ASSUME(expr)
#endif
/**
* @brief Macro to prevent a function to be inlined.
*/
#if !defined(LF_NOINLINE)
#if defined(_MSC_VER) && !defined(__clang__)
#define LF_NOINLINE __declspec(noinline)
#elif defined(__GNUC__) && __GNUC__ > 3
// Clang also defines __GNUC__ (as 4)
#if defined(__CUDACC__)
// nvcc doesn't always parse __noinline__, see: https://svn.boost.org/trac/boost/ticket/9392
#define LF_NOINLINE __attribute__((noinline))
#elif defined(__HIP__)
// See https://github.com/boostorg/config/issues/392
#define LF_NOINLINE __attribute__((noinline))
#else
#define LF_NOINLINE __attribute__((__noinline__))
#endif
#else
#define LF_NOINLINE
#endif
#endif
/**
* @brief Force no-inline for clang, works-around https://github.com/llvm/llvm-project/issues/63022.
*
* TODO: Check __apple_build_version__ when xcode 16 is released.
*/
#if defined(__clang__)
#if defined(__apple_build_version__) || __clang_major__ <= 16
#define LF_CLANG_TLS_NOINLINE LF_NOINLINE
#else
#define LF_CLANG_TLS_NOINLINE
#endif
#else
#define LF_CLANG_TLS_NOINLINE
#endif
/**
* @brief Macro to use next to 'inline' to force a function to be inlined.
*
* \rst
*
* .. note::
*
* This does not imply the c++'s `inline` keyword which also has an effect on linkage.
*
* \endrst
*/
#if !defined(LF_FORCEINLINE)
#if defined(_MSC_VER) && !defined(__clang__)
#define LF_FORCEINLINE __forceinline
#elif defined(__GNUC__) && __GNUC__ > 3
// Clang also defines __GNUC__ (as 4)
#define LF_FORCEINLINE __attribute__((__always_inline__))
#else
#define LF_FORCEINLINE
#endif
#endif
#if defined(__clang__) && defined(__has_attribute)
/**
* @brief Compiler specific attribute.
*/
#if __has_attribute(coro_return_type)
#define LF_CORO_RETURN_TYPE [[clang::coro_return_type]]
#else
#define LF_CORO_RETURN_TYPE
#endif
/**
* @brief Compiler specific attribute.
*/
#if __has_attribute(coro_only_destroy_when_complete)
#define LF_CORO_ONLY_DESTROY_WHEN_COMPLETE [[clang::coro_only_destroy_when_complete]]
#else
#define LF_CORO_ONLY_DESTROY_WHEN_COMPLETE
#endif
/**
* @brief Compiler specific attributes libfork uses for its coroutine types.
*/
#define LF_CORO_ATTRIBUTES LF_CORO_RETURN_TYPE LF_CORO_ONLY_DESTROY_WHEN_COMPLETE
#else
/**
* @brief Compiler specific attributes libfork uses for its coroutine types.
*/
#define LF_CORO_ATTRIBUTES
#endif
/**
* @brief Compiler specific attributes libfork uses for its coroutine types.
*/
#if defined(__clang__) && defined(__has_attribute)
#if __has_attribute(coro_wrapper)
#define LF_CORO_WRAPPER [[clang::coro_wrapper]]
#else
#define LF_CORO_WRAPPER
#endif
#else
#define LF_CORO_WRAPPER
#endif
/**
* @brief __[public]__ A customizable logging macro.
*
* By default this is a no-op. Defining ``LF_DEFAULT_LOGGING`` will enable a default
* logging implementation which prints to ``std::cout``. Overridable by defining your
* own ``LF_LOG`` macro with an API like ``std::format()``.
*/
#ifndef LF_LOG
#ifdef LF_DEFAULT_LOGGING
#include <iostream>
#include <thread>
#include <type_traits>
#ifdef __cpp_lib_format
#include <format>
#define LF_FORMAT(message, ...) std::format((message)__VA_OPT__(, ) __VA_ARGS__)
#else
#define LF_FORMAT(message, ...) (message)
#endif
#ifdef __cpp_lib_syncbuf
#include <syncstream>
#define LF_SYNC_COUT std::osyncstream(std::cout) << std::this_thread::get_id()
#else
#define LF_SYNC_COUT std::cout << std::this_thread::get_id()
#endif
#define LF_LOG(message, ...) \
do { \
if (!std::is_constant_evaluated()) { \
LF_SYNC_COUT << ": " << LF_FORMAT(message __VA_OPT__(, ) __VA_ARGS__) << '\n'; \
} \
} while (false)
#else
#define LF_LOG(head, ...)
#endif
#endif
/**
* @brief Concatenation macro
*/
#define LF_CONCAT_OUTER(a, b) LF_CONCAT_INNER(a, b)
/**
* @brief Internal concatenation macro (use LF_CONCAT_OUTER)
*/
#define LF_CONCAT_INNER(a, b) a##b
/**
* @brief Depreciate operator() in favor of operator[] if multidimensional subscript is available.
*/
#if defined(__cpp_multidimensional_subscript) && __cpp_multidimensional_subscript >= 202211L
#define LF_DEPRECATE_CALL [[deprecated("Use operator[] instead of operator()")]]
#else
#define LF_DEPRECATE_CALL
#endif
/**
* @brief Expands to ``_Pragma(#x)``.
*/
#define LF_AS_PRAGMA(x) _Pragma(#x)
/**
* @brief Expands to `#pragma unroll n` or equivalent if the compiler supports it.
*/
#ifdef __clang__
#define LF_PRAGMA_UNROLL(n) LF_AS_PRAGMA(unroll n)
#elif defined(__GNUC__)
#define LF_PRAGMA_UNROLL(n) LF_AS_PRAGMA(GCC unroll n)
#else
#define LF_PRAGMA_UNROLL(n)
#endif
// NOLINTEND
#endif /* C5DCA647_8269_46C2_B76F_5FA68738AEDA */
/**
* @file atomics.hpp
*
* @brief A port of part of boost::atomic_thread_fence(seq_cst) to work around clang's bad codegen.
*/
namespace lf::impl {
/**
* This is a workaround for clang generating bad codegen for ``std::atomic_thread_fence``.
*
* See: https://github.com/llvm/llvm-project/issues/91731
* https://www.reddit.com/r/cpp_questions/comments/16uer2g/how_do_i_stop_clang_generating_mfence/
* https://github.com/boostorg/atomic/issues/36
*
* This is a port of part of boost::atomic_thread_fence(seq_qst), see:
*
* https://github.com/boostorg/atomic/blob/5bbcce0f6e855dc4009e2e6977c62e0520c39573/include/boost/atomic/detail/fence_arch_ops_gcc_x86.hpp
* https://github.com/boostorg/atomic/blob/5bbcce0f6e855dc4009e2e6977c62e0520c39573/include/boost/atomic/detail/platform.hpp
*
*/
LF_FORCEINLINE inline void thread_fence_seq_cst() {
#if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__)) && defined(__clang__)
/**
* We could generate mfence for a seq_cst fence here, but a dummy lock-prefixed instruction is enough and is
* faster than mfence on most modern x86 CPUs (as of 2020). Note that we want to apply the atomic operation
* on any location so that:
* - It is not shared with other threads. A variable on the stack suits this well.
* - It is likely in cache. Being close to the top of the stack fits this well.
* - It does not alias existing data on the stack, so that we don't introduce a false data dependency.
* See some performance data here: https://shipilev.net/blog/2014/on-the-fence-with-dependencies/
* Unfortunately, to make tools like valgrind happy, we have to initialize the dummy, which is otherwise
* not needed.
*/
unsigned char dummy = 0u;
__asm__ __volatile__("lock; notb %0" : "+m"(dummy) : : "memory");
#else
std::atomic_thread_fence(std::memory_order_seq_cst);
#endif
}
} // namespace lf::impl
#endif /* F70CC480_E6E6_43C1_A7D6_3EEB74F05088 */
// for thread_fence_seq_cst
#ifndef DF63D333_F8C0_4BBA_97E1_32A78466B8B7
#define DF63D333_F8C0_4BBA_97E1_32A78466B8B7
// Copyright © Conor Williams <[email protected]>
// SPDX-License-Identifier: MPL-2.0
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.
#include <bit> // for bit_cast, has_single_bit
#include <concepts> // for same_as, integral, convertible_to
#include <cstddef> // for byte, size_t
#include <cstdint> // for uint16_t
#include <cstdio> // for fprintf, stderr
#include <exception> // for terminate
#include <functional> // for invoke
#include <limits> // for numeric_limits
#include <new> // for std::hardware_destructive_interference_size
#include <source_location> // for source_location
#include <stdexcept>
#include <type_traits> // for invoke_result_t, remove_cvref_t, type_identity, condit...
#include <utility> // for cmp_greater, cmp_less, forward
#include <vector> // for vector
#include <version> // for __cpp_lib_hardware_interference_size
// for LF_ASSERT, LF_HOF_RETURNS
/**
* @file utility.hpp
*
* @brief A collection of internal utilities.
*/
/**
* @brief The ``libfork`` namespace.
*
* Everything in ``libfork`` is contained within this namespace.
*/
namespace lf {
/**
* @brief An inline namespace that wraps core functionality.
*
* This is the namespace that contains the minimal user-facing API of ``libfork``, notably
* this excludes schedulers and algorithms.
*/
inline namespace core {}
/**
* @brief An inline namespace that wraps extension functionality.
*
* This namespace is part of ``libfork``s public API but is intended for advanced users
* writing schedulers, It exposes the scheduler/context API's alongside some implementation
* details (such as lock-free dequeues, a `hwloc` abstraction, and synchronization primitives)
* that could be useful when implementing custom schedulers.
*/
inline namespace ext {}
/**
* @brief An internal namespace that wraps implementation details.
*
* \rst
*
* .. warning::
*
* This is exposed as internal documentation only it is not part of the public facing API.
*
* \endrst
*/
namespace impl {}
} // namespace lf
namespace lf::impl {
// ---------------- Constants ---------------- //
/**
* @brief The cache line size (bytes) of the current architecture.
*/
#ifdef __cpp_lib_hardware_interference_size
inline constexpr std::size_t k_cache_line = std::hardware_destructive_interference_size;
#else
inline constexpr std::size_t k_cache_line = 64;
#endif
/**
* @brief The default alignment of `operator new`, a power of two.
*/
inline constexpr std::size_t k_new_align = __STDCPP_DEFAULT_NEW_ALIGNMENT__;
static_assert(std::has_single_bit(k_new_align));
/**
* @brief Shorthand for `std::numeric_limits<std::unt32_t>::max()`.
*/
static constexpr std::uint16_t k_u16_max = std::numeric_limits<std::uint16_t>::max();
/**
* @brief A dependent value to emulate `static_assert(false)` pre c++26.
*/
template <typename...>
inline constexpr bool always_false = false;
// ---------------- Utility classes ---------------- //
/**
* @brief An empty type.
*/
template <std::size_t = 0>
struct empty_t {};
/**
* If `Cond` is `true` then `T` otherwise an empty type.
*/
template <bool Cond, typename T, std::size_t N = 0>
using else_empty_t = std::conditional_t<Cond, T, empty_t<N>>;
// -------------------------------- //
/**
* @brief An empty base class that is not copyable or movable.
*
* The template parameter prevents multiple empty bases when inheriting multiple classes.
*/
template <typename CRTP>
struct immovable {
immovable() = default;
immovable(const immovable &) = delete;
immovable(immovable &&) = delete;
auto operator=(const immovable &) -> immovable & = delete;
auto operator=(immovable &&) -> immovable & = delete;
~immovable() = default;
};
static_assert(std::is_empty_v<immovable<void>>);
// ---------------- Meta programming ---------------- //
/**
* @brief Check is a type is not ``void``.
*/
template <typename T>
concept non_void = !std::is_void_v<T>;
namespace detail {
template <typename From, typename To>
struct forward_cv : std::type_identity<To> {};
template <typename From, typename To>
struct forward_cv<From const, To> : std::type_identity<To const> {};
template <typename From, typename To>
struct forward_cv<From volatile, To> : std::type_identity<To volatile> {};
template <typename From, typename To>
struct forward_cv<From const volatile, To> : std::type_identity<To const volatile> {};
} // namespace detail
/**
* @brief Copy the ``const``/``volatile`` qualifiers from ``From`` to ``To``.
*/
template <typename From, typename To>
requires (!std::is_reference_v<From> && std::same_as<std::remove_cvref_t<To>, To>)
using forward_cv_t = typename detail::forward_cv<From, To>::type;
/**
* @brief Test if the `T` has no `const`, `volatile` or reference qualifiers.
*/
template <typename T>
concept unqualified = std::same_as<std::remove_cvref_t<T>, T>;
/**
* @brief True if the unqualified ``T`` and ``U`` refer to different types.
*
* This is useful for preventing ''T &&'' constructor/assignment from replacing the defaults.
*/
template <typename T, typename U>
concept different_from = !std::same_as<std::remove_cvref_t<U>, std::remove_cvref_t<T>>;
// ---------------- Small functions ---------------- //
/**
* @brief Safe integral cast, will terminate if the cast would overflow in debug.
*/
template <std::integral To, std::integral From>
auto checked_cast(From val) noexcept -> To {
constexpr auto to_min = std::numeric_limits<To>::min();
constexpr auto to_max = std::numeric_limits<To>::max();
constexpr auto from_min = std::numeric_limits<From>::min();
constexpr auto from_max = std::numeric_limits<From>::max();
/**
* [ from ]
* [ to ]
*/
if constexpr (std::cmp_greater(to_min, from_min)) {
LF_ASSERT(val >= static_cast<From>(to_min) && "Underflow");
}
if constexpr (std::cmp_less(to_max, from_max)) {
LF_ASSERT(val <= static_cast<From>(to_max) && "Overflow");
}
return static_cast<To>(val);
}
/**
* @brief Transform `[a, b, c] -> [f(a), f(b), f(c)]`.
*/
template <typename T, typename F>
auto map(std::vector<T> const &from, F &&func) -> std::vector<std::invoke_result_t<F &, T const &>> {
std::vector<std::invoke_result_t<F &, T const &>> out;
out.reserve(from.size());
for (auto &&item : from) {
out.emplace_back(std::invoke(func, item));
}
return out;
}
/**
* @brief Transform `[a, b, c] -> [f(a), f(b), f(c)]`.
*/
template <typename T, typename F>
auto map(std::vector<T> &&from, F &&func) -> std::vector<std::invoke_result_t<F &, T>> {
std::vector<std::invoke_result_t<F &, T>> out;
out.reserve(from.size());
for (auto &&item : from) {
out.emplace_back(std::invoke(func, std::move(item)));
}
return out;
}
// -------------------------------- //
/**
* @brief Returns ``ptr`` and asserts it is non-null in debug builds.
*/
template <typename T>
requires requires (T &&ptr) {
{ ptr == nullptr } -> std::convertible_to<bool>;
}
constexpr auto
non_null(T &&val,
[[maybe_unused]] std::source_location loc = std::source_location::current()) noexcept -> T && {
#ifndef NDEBUG
if (val == nullptr) {
// NOLINTNEXTLINE
std::fprintf(stderr,
"%s:%u: Null check failed: %s\n",
loc.file_name(),
checked_cast<unsigned>(loc.line()),
loc.function_name());
std::terminate();
}
#endif
return std::forward<T>(val);
}
// -------------------------------- //
/**
* @brief Cast a pointer to a byte pointer.
*/
template <typename T>
auto byte_cast(T *ptr) LF_HOF_RETURNS(std::bit_cast<forward_cv_t<T, std::byte> *>(ptr))
} // namespace lf::impl
#endif /* DF63D333_F8C0_4BBA_97E1_32A78466B8B7 */
// for k_cache_line, immovable // for LF_ASSERT, LF_STATIC_CALL, LF_STATIC_CONST
/**
* @file deque.hpp
*
* @brief A production-quality implementation of the Chase-Lev lock-free SPMC deque.
*/
namespace lf {
inline namespace ext {
/**
* @brief Verify a type is suitable for use with `std::atomic`
*
* This requires a `TriviallyCopyable` type satisfying both `CopyConstructible` and `CopyAssignable`.
*/
template <typename T>
concept atomicable = std::is_trivially_copyable_v<T> && //
std::is_copy_constructible_v<T> && //
std::is_move_constructible_v<T> && //
std::is_copy_assignable_v<T> && //
std::is_move_assignable_v<T>; //
/**
* @brief A concept that verifies a type is lock-free when used with `std::atomic`.
*/
template <typename T>
concept lock_free = atomicable<T> && std::atomic<T>::is_always_lock_free;
/**
* @brief Test is a type is suitable for use with `lf::deque`.
*
* This requires it to be `lf::ext::lock_free` and `std::default_initializable`.
*/
template <typename T>
concept dequeable = lock_free<T> && std::default_initializable<T>;
} // namespace ext
namespace impl {
/**
* @brief A basic wrapper around a c-style array that provides modulo load/stores.
*
* This class is designed for internal use only. It provides a c-style API that is
* used efficiently by deque for low level atomic operations.
*
* @tparam T The type of the elements in the array.
*/
template <dequeable T>
struct atomic_ring_buf {
/**
* @brief Construct a new ring buff object
*
* @param cap The capacity of the buffer, MUST be a power of 2.
*/
constexpr explicit atomic_ring_buf(std::ptrdiff_t cap) : m_cap{cap}, m_mask{cap - 1} {
LF_ASSERT(cap > 0 && std::has_single_bit(static_cast<std::size_t>(cap)));
}
/**
* @brief Get the capacity of the buffer.
*/
[[nodiscard]] constexpr auto capacity() const noexcept -> std::ptrdiff_t { return m_cap; }
/**
* @brief Store ``val`` at ``index % this->capacity()``.
*/
constexpr auto store(std::ptrdiff_t index, T const &val) noexcept -> void {
LF_ASSERT(index >= 0);
(m_buf.get() + (index & m_mask))->store(val, std::memory_order_relaxed); // NOLINT Avoid cast.
}
/**
* @brief Load value at ``index % this->capacity()``.
*/
[[nodiscard]] constexpr auto load(std::ptrdiff_t index) const noexcept -> T {
LF_ASSERT(index >= 0);
return (m_buf.get() + (index & m_mask))->load(std::memory_order_relaxed); // NOLINT Avoid cast.
}
/**
* @brief Copies elements in range ``[bottom, top)`` into a new ring buffer.
*
* This function allocates a new buffer and returns a pointer to it.
* The caller is responsible for deallocating the memory.
*
* @param bot The bottom of the range to copy from (inclusive).
* @param top The top of the range to copy from (exclusive).
*/
[[nodiscard]] constexpr auto resize(std::ptrdiff_t bot, std::ptrdiff_t top) const -> atomic_ring_buf<T> * {
auto *ptr = new atomic_ring_buf{2 * m_cap}; // NOLINT
for (std::ptrdiff_t i = top; i != bot; ++i) {
ptr->store(i, load(i));
}
return ptr;
}
private:
/**
* @brief An array of atomic elements.
*/
using array_t = std::atomic<T>[]; // NOLINT
/**
* @brief Capacity of the buffer.
*/
std::ptrdiff_t m_cap;
/**
* @brief Bit mask to perform modulo capacity operations.
*/
std::ptrdiff_t m_mask;
#ifdef __cpp_lib_smart_ptr_for_overwrite
std::unique_ptr<array_t> m_buf = std::make_unique_for_overwrite<array_t>(static_cast<std::size_t>(m_cap));
#else
std::unique_ptr<array_t> m_buf = std::make_unique<array_t>(static_cast<std::size_t>(m_cap));
#endif
};
} // namespace impl
inline namespace ext {
/**
* @brief Error codes for ``deque`` 's ``steal()`` operation.
*/
enum class err : int {
/**
* @brief The ``steal()`` operation succeeded.
*/
none = 0,
/**
* @brief Lost the ``steal()`` race hence, the ``steal()`` operation failed.
*/
lost,
/**
* @brief The deque is empty and hence, the ``steal()`` operation failed.
*/
empty,
};
/**
* @brief The return type of a `lf::deque` `steal()` operation.
*
* This type is suitable for structured bindings. We return a custom type instead of a
* `std::optional` to allow for more information to be returned as to why a steal may fail.
*/
template <typename T>
struct steal_t {
/**
* @brief Check if the operation succeeded.
*/
[[nodiscard]] constexpr explicit operator bool() const noexcept { return code == err::none; }
/**
* @brief Get the value like ``std::optional``.
*
* Requires ``code == err::none`` .
*/