libstdc++
compare
Go to the documentation of this file.
1 // -*- C++ -*- operator<=> three-way comparison support.
2 
3 // Copyright (C) 2019-2022 Free Software Foundation, Inc.
4 //
5 // This file is part of GCC.
6 //
7 // GCC is free software; you can redistribute it and/or modify
8 // it under the terms of the GNU General Public License as published by
9 // the Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 //
12 // GCC is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 //
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /** @file compare
27  * This is a Standard C++ Library header.
28  */
29 
30 #ifndef _COMPARE
31 #define _COMPARE
32 
33 #pragma GCC system_header
34 
35 #if __cplusplus > 201703L && __cpp_impl_three_way_comparison >= 201907L
36 
37 #pragma GCC visibility push(default)
38 
39 #include <concepts>
40 
41 #if __cpp_lib_concepts
42 # define __cpp_lib_three_way_comparison 201907L
43 #endif
44 
45 namespace std
46 {
47  // [cmp.categories], comparison category types
48 
49  namespace __cmp_cat
50  {
51  using type = signed char;
52 
53  enum class _Ord : type { equivalent = 0, less = -1, greater = 1 };
54 
55  enum class _Ncmp : type { _Unordered = 2 };
56 
57  struct __unspec
58  {
59  constexpr __unspec(__unspec*) noexcept { }
60  };
61  }
62 
63  class partial_ordering
64  {
65  // less=0xff, equiv=0x00, greater=0x01, unordered=0x02
66  __cmp_cat::type _M_value;
67 
68  constexpr explicit
69  partial_ordering(__cmp_cat::_Ord __v) noexcept
70  : _M_value(__cmp_cat::type(__v))
71  { }
72 
73  constexpr explicit
74  partial_ordering(__cmp_cat::_Ncmp __v) noexcept
75  : _M_value(__cmp_cat::type(__v))
76  { }
77 
78  friend class weak_ordering;
79  friend class strong_ordering;
80 
81  public:
82  // valid values
83  static const partial_ordering less;
84  static const partial_ordering equivalent;
85  static const partial_ordering greater;
86  static const partial_ordering unordered;
87 
88  // comparisons
89  [[nodiscard]]
90  friend constexpr bool
91  operator==(partial_ordering __v, __cmp_cat::__unspec) noexcept
92  { return __v._M_value == 0; }
93 
94  [[nodiscard]]
95  friend constexpr bool
96  operator==(partial_ordering, partial_ordering) noexcept = default;
97 
98  [[nodiscard]]
99  friend constexpr bool
100  operator< (partial_ordering __v, __cmp_cat::__unspec) noexcept
101  { return __v._M_value == -1; }
102 
103  [[nodiscard]]
104  friend constexpr bool
105  operator> (partial_ordering __v, __cmp_cat::__unspec) noexcept
106  { return __v._M_value == 1; }
107 
108  [[nodiscard]]
109  friend constexpr bool
110  operator<=(partial_ordering __v, __cmp_cat::__unspec) noexcept
111  { return __v._M_value <= 0; }
112 
113  [[nodiscard]]
114  friend constexpr bool
115  operator>=(partial_ordering __v, __cmp_cat::__unspec) noexcept
116  { return __cmp_cat::type(__v._M_value & 1) == __v._M_value; }
117 
118  [[nodiscard]]
119  friend constexpr bool
120  operator< (__cmp_cat::__unspec, partial_ordering __v) noexcept
121  { return __v._M_value == 1; }
122 
123  [[nodiscard]]
124  friend constexpr bool
125  operator> (__cmp_cat::__unspec, partial_ordering __v) noexcept
126  { return __v._M_value == -1; }
127 
128  [[nodiscard]]
129  friend constexpr bool
130  operator<=(__cmp_cat::__unspec, partial_ordering __v) noexcept
131  { return __cmp_cat::type(__v._M_value & 1) == __v._M_value; }
132 
133  [[nodiscard]]
134  friend constexpr bool
135  operator>=(__cmp_cat::__unspec, partial_ordering __v) noexcept
136  { return 0 >= __v._M_value; }
137 
138  [[nodiscard]]
139  friend constexpr partial_ordering
140  operator<=>(partial_ordering __v, __cmp_cat::__unspec) noexcept
141  { return __v; }
142 
143  [[nodiscard]]
144  friend constexpr partial_ordering
145  operator<=>(__cmp_cat::__unspec, partial_ordering __v) noexcept
146  {
147  if (__v._M_value & 1)
148  return partial_ordering(__cmp_cat::_Ord(-__v._M_value));
149  else
150  return __v;
151  }
152  };
153 
154  // valid values' definitions
155  inline constexpr partial_ordering
156  partial_ordering::less(__cmp_cat::_Ord::less);
157 
158  inline constexpr partial_ordering
159  partial_ordering::equivalent(__cmp_cat::_Ord::equivalent);
160 
161  inline constexpr partial_ordering
162  partial_ordering::greater(__cmp_cat::_Ord::greater);
163 
164  inline constexpr partial_ordering
165  partial_ordering::unordered(__cmp_cat::_Ncmp::_Unordered);
166 
167  class weak_ordering
168  {
169  __cmp_cat::type _M_value;
170 
171  constexpr explicit
172  weak_ordering(__cmp_cat::_Ord __v) noexcept : _M_value(__cmp_cat::type(__v))
173  { }
174 
175  friend class strong_ordering;
176 
177  public:
178  // valid values
179  static const weak_ordering less;
180  static const weak_ordering equivalent;
181  static const weak_ordering greater;
182 
183  [[nodiscard]]
184  constexpr operator partial_ordering() const noexcept
185  { return partial_ordering(__cmp_cat::_Ord(_M_value)); }
186 
187  // comparisons
188  [[nodiscard]]
189  friend constexpr bool
190  operator==(weak_ordering __v, __cmp_cat::__unspec) noexcept
191  { return __v._M_value == 0; }
192 
193  [[nodiscard]]
194  friend constexpr bool
195  operator==(weak_ordering, weak_ordering) noexcept = default;
196 
197  [[nodiscard]]
198  friend constexpr bool
199  operator< (weak_ordering __v, __cmp_cat::__unspec) noexcept
200  { return __v._M_value < 0; }
201 
202  [[nodiscard]]
203  friend constexpr bool
204  operator> (weak_ordering __v, __cmp_cat::__unspec) noexcept
205  { return __v._M_value > 0; }
206 
207  [[nodiscard]]
208  friend constexpr bool
209  operator<=(weak_ordering __v, __cmp_cat::__unspec) noexcept
210  { return __v._M_value <= 0; }
211 
212  [[nodiscard]]
213  friend constexpr bool
214  operator>=(weak_ordering __v, __cmp_cat::__unspec) noexcept
215  { return __v._M_value >= 0; }
216 
217  [[nodiscard]]
218  friend constexpr bool
219  operator< (__cmp_cat::__unspec, weak_ordering __v) noexcept
220  { return 0 < __v._M_value; }
221 
222  [[nodiscard]]
223  friend constexpr bool
224  operator> (__cmp_cat::__unspec, weak_ordering __v) noexcept
225  { return 0 > __v._M_value; }
226 
227  [[nodiscard]]
228  friend constexpr bool
229  operator<=(__cmp_cat::__unspec, weak_ordering __v) noexcept
230  { return 0 <= __v._M_value; }
231 
232  [[nodiscard]]
233  friend constexpr bool
234  operator>=(__cmp_cat::__unspec, weak_ordering __v) noexcept
235  { return 0 >= __v._M_value; }
236 
237  [[nodiscard]]
238  friend constexpr weak_ordering
239  operator<=>(weak_ordering __v, __cmp_cat::__unspec) noexcept
240  { return __v; }
241 
242  [[nodiscard]]
243  friend constexpr weak_ordering
244  operator<=>(__cmp_cat::__unspec, weak_ordering __v) noexcept
245  { return weak_ordering(__cmp_cat::_Ord(-__v._M_value)); }
246  };
247 
248  // valid values' definitions
249  inline constexpr weak_ordering
250  weak_ordering::less(__cmp_cat::_Ord::less);
251 
252  inline constexpr weak_ordering
253  weak_ordering::equivalent(__cmp_cat::_Ord::equivalent);
254 
255  inline constexpr weak_ordering
256  weak_ordering::greater(__cmp_cat::_Ord::greater);
257 
258  class strong_ordering
259  {
260  __cmp_cat::type _M_value;
261 
262  constexpr explicit
263  strong_ordering(__cmp_cat::_Ord __v) noexcept
264  : _M_value(__cmp_cat::type(__v))
265  { }
266 
267  public:
268  // valid values
269  static const strong_ordering less;
270  static const strong_ordering equal;
271  static const strong_ordering equivalent;
272  static const strong_ordering greater;
273 
274  [[nodiscard]]
275  constexpr operator partial_ordering() const noexcept
276  { return partial_ordering(__cmp_cat::_Ord(_M_value)); }
277 
278  [[nodiscard]]
279  constexpr operator weak_ordering() const noexcept
280  { return weak_ordering(__cmp_cat::_Ord(_M_value)); }
281 
282  // comparisons
283  [[nodiscard]]
284  friend constexpr bool
285  operator==(strong_ordering __v, __cmp_cat::__unspec) noexcept
286  { return __v._M_value == 0; }
287 
288  [[nodiscard]]
289  friend constexpr bool
290  operator==(strong_ordering, strong_ordering) noexcept = default;
291 
292  [[nodiscard]]
293  friend constexpr bool
294  operator< (strong_ordering __v, __cmp_cat::__unspec) noexcept
295  { return __v._M_value < 0; }
296 
297  [[nodiscard]]
298  friend constexpr bool
299  operator> (strong_ordering __v, __cmp_cat::__unspec) noexcept
300  { return __v._M_value > 0; }
301 
302  [[nodiscard]]
303  friend constexpr bool
304  operator<=(strong_ordering __v, __cmp_cat::__unspec) noexcept
305  { return __v._M_value <= 0; }
306 
307  [[nodiscard]]
308  friend constexpr bool
309  operator>=(strong_ordering __v, __cmp_cat::__unspec) noexcept
310  { return __v._M_value >= 0; }
311 
312  [[nodiscard]]
313  friend constexpr bool
314  operator< (__cmp_cat::__unspec, strong_ordering __v) noexcept
315  { return 0 < __v._M_value; }
316 
317  [[nodiscard]]
318  friend constexpr bool
319  operator> (__cmp_cat::__unspec, strong_ordering __v) noexcept
320  { return 0 > __v._M_value; }
321 
322  [[nodiscard]]
323  friend constexpr bool
324  operator<=(__cmp_cat::__unspec, strong_ordering __v) noexcept
325  { return 0 <= __v._M_value; }
326 
327  [[nodiscard]]
328  friend constexpr bool
329  operator>=(__cmp_cat::__unspec, strong_ordering __v) noexcept
330  { return 0 >= __v._M_value; }
331 
332  [[nodiscard]]
333  friend constexpr strong_ordering
334  operator<=>(strong_ordering __v, __cmp_cat::__unspec) noexcept
335  { return __v; }
336 
337  [[nodiscard]]
338  friend constexpr strong_ordering
339  operator<=>(__cmp_cat::__unspec, strong_ordering __v) noexcept
340  { return strong_ordering(__cmp_cat::_Ord(-__v._M_value)); }
341  };
342 
343  // valid values' definitions
344  inline constexpr strong_ordering
345  strong_ordering::less(__cmp_cat::_Ord::less);
346 
347  inline constexpr strong_ordering
348  strong_ordering::equal(__cmp_cat::_Ord::equivalent);
349 
350  inline constexpr strong_ordering
351  strong_ordering::equivalent(__cmp_cat::_Ord::equivalent);
352 
353  inline constexpr strong_ordering
354  strong_ordering::greater(__cmp_cat::_Ord::greater);
355 
356 
357  // named comparison functions
358  [[nodiscard]]
359  constexpr bool
360  is_eq(partial_ordering __cmp) noexcept
361  { return __cmp == 0; }
362 
363  [[nodiscard]]
364  constexpr bool
365  is_neq(partial_ordering __cmp) noexcept
366  { return __cmp != 0; }
367 
368  [[nodiscard]]
369  constexpr bool
370  is_lt (partial_ordering __cmp) noexcept
371  { return __cmp < 0; }
372 
373  [[nodiscard]]
374  constexpr bool
375  is_lteq(partial_ordering __cmp) noexcept
376  { return __cmp <= 0; }
377 
378  [[nodiscard]]
379  constexpr bool
380  is_gt (partial_ordering __cmp) noexcept
381  { return __cmp > 0; }
382 
383  [[nodiscard]]
384  constexpr bool
385  is_gteq(partial_ordering __cmp) noexcept
386  { return __cmp >= 0; }
387 
388  namespace __detail
389  {
390  template<typename _Tp>
391  inline constexpr unsigned __cmp_cat_id = 1;
392  template<>
393  inline constexpr unsigned __cmp_cat_id<partial_ordering> = 2;
394  template<>
395  inline constexpr unsigned __cmp_cat_id<weak_ordering> = 4;
396  template<>
397  inline constexpr unsigned __cmp_cat_id<strong_ordering> = 8;
398 
399  template<typename... _Ts>
400  constexpr auto __common_cmp_cat()
401  {
402  constexpr unsigned __cats = (__cmp_cat_id<_Ts> | ...);
403  // If any Ti is not a comparison category type, U is void.
404  if constexpr (__cats & 1)
405  return;
406  // Otherwise, if at least one Ti is std::partial_ordering,
407  // U is std::partial_ordering.
408  else if constexpr (bool(__cats & __cmp_cat_id<partial_ordering>))
409  return partial_ordering::equivalent;
410  // Otherwise, if at least one Ti is std::weak_ordering,
411  // U is std::weak_ordering.
412  else if constexpr (bool(__cats & __cmp_cat_id<weak_ordering>))
413  return weak_ordering::equivalent;
414  // Otherwise, U is std::strong_ordering.
415  else
416  return strong_ordering::equivalent;
417  }
418  } // namespace __detail
419 
420  // [cmp.common], common comparison category type
421  template<typename... _Ts>
422  struct common_comparison_category
423  {
424  using type = decltype(__detail::__common_cmp_cat<_Ts...>());
425  };
426 
427  // Partial specializations for one and zero argument cases.
428 
429  template<typename _Tp>
430  struct common_comparison_category<_Tp>
431  { using type = void; };
432 
433  template<>
434  struct common_comparison_category<partial_ordering>
435  { using type = partial_ordering; };
436 
437  template<>
438  struct common_comparison_category<weak_ordering>
439  { using type = weak_ordering; };
440 
441  template<>
442  struct common_comparison_category<strong_ordering>
443  { using type = strong_ordering; };
444 
445  template<>
446  struct common_comparison_category<>
447  { using type = strong_ordering; };
448 
449  template<typename... _Ts>
450  using common_comparison_category_t
451  = typename common_comparison_category<_Ts...>::type;
452 
453 #if __cpp_lib_concepts
454  namespace __detail
455  {
456  template<typename _Tp, typename _Cat>
457  concept __compares_as
458  = same_as<common_comparison_category_t<_Tp, _Cat>, _Cat>;
459  } // namespace __detail
460 
461  // [cmp.concept], concept three_way_comparable
462  template<typename _Tp, typename _Cat = partial_ordering>
463  concept three_way_comparable
464  = __detail::__weakly_eq_cmp_with<_Tp, _Tp>
465  && __detail::__partially_ordered_with<_Tp, _Tp>
466  && requires(const remove_reference_t<_Tp>& __a,
467  const remove_reference_t<_Tp>& __b)
468  {
469  { __a <=> __b } -> __detail::__compares_as<_Cat>;
470  };
471 
472  template<typename _Tp, typename _Up, typename _Cat = partial_ordering>
473  concept three_way_comparable_with
474  = three_way_comparable<_Tp, _Cat>
475  && three_way_comparable<_Up, _Cat>
476  && common_reference_with<const remove_reference_t<_Tp>&,
477  const remove_reference_t<_Up>&>
478  && three_way_comparable<
479  common_reference_t<const remove_reference_t<_Tp>&,
480  const remove_reference_t<_Up>&>, _Cat>
481  && __detail::__weakly_eq_cmp_with<_Tp, _Up>
482  && __detail::__partially_ordered_with<_Tp, _Up>
483  && requires(const remove_reference_t<_Tp>& __t,
484  const remove_reference_t<_Up>& __u)
485  {
486  { __t <=> __u } -> __detail::__compares_as<_Cat>;
487  { __u <=> __t } -> __detail::__compares_as<_Cat>;
488  };
489 
490  namespace __detail
491  {
492  template<typename _Tp, typename _Up>
493  using __cmp3way_res_t
494  = decltype(std::declval<_Tp>() <=> std::declval<_Up>());
495 
496  // Implementation of std::compare_three_way_result.
497  // It is undefined for a program to add specializations of
498  // std::compare_three_way_result, so the std::compare_three_way_result_t
499  // alias ignores std::compare_three_way_result and uses
500  // __detail::__cmp3way_res_impl directly instead.
501  template<typename _Tp, typename _Up>
502  struct __cmp3way_res_impl
503  { };
504 
505  template<typename _Tp, typename _Up>
506  requires requires { typename __cmp3way_res_t<__cref<_Tp>, __cref<_Up>>; }
507  struct __cmp3way_res_impl<_Tp, _Up>
508  {
509  using type = __cmp3way_res_t<__cref<_Tp>, __cref<_Up>>;
510  };
511  } // namespace __detail
512 
513  /// [cmp.result], result of three-way comparison
514  template<typename _Tp, typename _Up = _Tp>
516  : __detail::__cmp3way_res_impl<_Tp, _Up>
517  { };
518 
519  /// [cmp.result], result of three-way comparison
520  template<typename _Tp, typename _Up = _Tp>
522  = typename __detail::__cmp3way_res_impl<_Tp, _Up>::type;
523 
524  namespace __detail
525  {
526  // BUILTIN-PTR-THREE-WAY(T, U)
527  // This determines whether t <=> u results in a call to a built-in
528  // operator<=> comparing pointers. It doesn't work for function pointers
529  // (PR 93628).
530  template<typename _Tp, typename _Up>
531  concept __3way_builtin_ptr_cmp
532  = requires(_Tp&& __t, _Up&& __u)
533  { static_cast<_Tp&&>(__t) <=> static_cast<_Up&&>(__u); }
534  && convertible_to<_Tp, const volatile void*>
535  && convertible_to<_Up, const volatile void*>
536  && ! requires(_Tp&& __t, _Up&& __u)
537  { operator<=>(static_cast<_Tp&&>(__t), static_cast<_Up&&>(__u)); }
538  && ! requires(_Tp&& __t, _Up&& __u)
539  { static_cast<_Tp&&>(__t).operator<=>(static_cast<_Up&&>(__u)); };
540  } // namespace __detail
541 
542  // _GLIBCXX_RESOLVE_LIB_DEFECTS
543  // 3530 BUILTIN-PTR-MEOW should not opt the type out of syntactic checks
544 
545  // [cmp.object], typename compare_three_way
546  struct compare_three_way
547  {
548  template<typename _Tp, typename _Up>
549  requires three_way_comparable_with<_Tp, _Up>
550  constexpr auto
551  operator() [[nodiscard]] (_Tp&& __t, _Up&& __u) const
552  noexcept(noexcept(std::declval<_Tp>() <=> std::declval<_Up>()))
553  {
554  if constexpr (__detail::__3way_builtin_ptr_cmp<_Tp, _Up>)
555  {
556  auto __pt = static_cast<const volatile void*>(__t);
557  auto __pu = static_cast<const volatile void*>(__u);
558  if (std::__is_constant_evaluated())
559  return __pt <=> __pu;
560  auto __it = reinterpret_cast<__UINTPTR_TYPE__>(__pt);
561  auto __iu = reinterpret_cast<__UINTPTR_TYPE__>(__pu);
562  return __it <=> __iu;
563  }
564  else
565  return static_cast<_Tp&&>(__t) <=> static_cast<_Up&&>(__u);
566  }
567 
568  using is_transparent = void;
569  };
570 
571  namespace __cmp_cust
572  {
573  template<floating_point _Tp>
574  constexpr weak_ordering
575  __fp_weak_ordering(_Tp __e, _Tp __f)
576  {
577  // Returns an integer with the same sign as the argument, and magnitude
578  // indicating the classification: zero=1 subnorm=2 norm=3 inf=4 nan=5
579  auto __cat = [](_Tp __fp) -> int {
580  const int __sign = __builtin_signbit(__fp) ? -1 : 1;
581  if (__builtin_isnormal(__fp))
582  return (__fp == 0 ? 1 : 3) * __sign;
583  if (__builtin_isnan(__fp))
584  return 5 * __sign;
585  if (int __inf = __builtin_isinf_sign(__fp))
586  return 4 * __inf;
587  return 2 * __sign;
588  };
589 
590  auto __po = __e <=> __f;
591  if (is_lt(__po))
592  return weak_ordering::less;
593  else if (is_gt(__po))
594  return weak_ordering::greater;
595  else if (__po == partial_ordering::equivalent)
596  return weak_ordering::equivalent;
597  else // unordered, at least one argument is NaN
598  {
599  // return -1 for negative nan, +1 for positive nan, 0 otherwise.
600  auto __isnan_sign = [](_Tp __fp) -> int {
601  return __builtin_isnan(__fp)
602  ? __builtin_signbit(__fp) ? -1 : 1
603  : 0;
604  };
605  auto __ord = __isnan_sign(__e) <=> __isnan_sign(__f);
606  if (is_eq(__ord))
607  return weak_ordering::equivalent;
608  else if (is_lt(__ord))
609  return weak_ordering::less;
610  else
611  return weak_ordering::greater;
612  }
613  }
614 
615  template<typename _Tp, typename _Up>
616  concept __adl_strong = requires(_Tp&& __t, _Up&& __u)
617  {
618  strong_ordering(strong_order(static_cast<_Tp&&>(__t),
619  static_cast<_Up&&>(__u)));
620  };
621 
622  template<typename _Tp, typename _Up>
623  concept __adl_weak = requires(_Tp&& __t, _Up&& __u)
624  {
625  weak_ordering(weak_order(static_cast<_Tp&&>(__t),
626  static_cast<_Up&&>(__u)));
627  };
628 
629  template<typename _Tp, typename _Up>
630  concept __adl_partial = requires(_Tp&& __t, _Up&& __u)
631  {
632  partial_ordering(partial_order(static_cast<_Tp&&>(__t),
633  static_cast<_Up&&>(__u)));
634  };
635 
636  template<typename _Ord, typename _Tp, typename _Up>
637  concept __cmp3way = requires(_Tp&& __t, _Up&& __u, compare_three_way __c)
638  {
639  _Ord(__c(static_cast<_Tp&&>(__t), static_cast<_Up&&>(__u)));
640  };
641 
642  template<typename _Tp, typename _Up>
643  concept __strongly_ordered
644  = __adl_strong<_Tp, _Up>
645  || floating_point<remove_reference_t<_Tp>>
646  || __cmp3way<strong_ordering, _Tp, _Up>;
647 
648  template<typename _Tp, typename _Up>
649  concept __decayed_same_as = same_as<decay_t<_Tp>, decay_t<_Up>>;
650 
651  class _Strong_order
652  {
653  template<typename _Tp, typename _Up>
654  static constexpr bool
655  _S_noexcept()
656  {
657  if constexpr (floating_point<decay_t<_Tp>>)
658  return true;
659  else if constexpr (__adl_strong<_Tp, _Up>)
660  return noexcept(strong_ordering(strong_order(std::declval<_Tp>(),
661  std::declval<_Up>())));
662  else if constexpr (__cmp3way<strong_ordering, _Tp, _Up>)
663  return noexcept(compare_three_way()(std::declval<_Tp>(),
664  std::declval<_Up>()));
665  }
666 
667  friend class _Weak_order;
668  friend class _Strong_fallback;
669 
670  // Names for the supported floating-point representations.
671  enum class _Fp_fmt
672  {
673  _Binary16, _Binary32, _Binary64, _Binary128, // IEEE
674  _X86_80bit, // x86 80-bit extended precision
675  _M68k_80bit, // m68k 80-bit extended precision
676  _Dbldbl, // IBM 128-bit double-double
677  // TODO: _Bfloat16,
678  };
679 
680  // Identify the format used by a floating-point type.
681  template<typename _Tp>
682  static consteval _Fp_fmt
683  _S_fp_fmt() noexcept
684  {
685  using enum _Fp_fmt;
686 
687  // Identify these formats first, then assume anything else is IEEE.
688  // N.B. ARM __fp16 alternative format can be handled as binary16.
689 
690 #ifdef __LONG_DOUBLE_IBM128__
691  if constexpr (__is_same(_Tp, long double))
692  return _Dbldbl;
693 #elif defined __LONG_DOUBLE_IEEE128__ && defined __SIZEOF_IBM128__
694  if constexpr (__is_same(_Tp, __ibm128))
695  return _Dbldbl;
696 #endif
697 
698 #if __LDBL_MANT_DIG__ == 64
699  if constexpr (__is_same(_Tp, long double))
700  return __LDBL_MIN_EXP__ == -16381 ? _X86_80bit : _M68k_80bit;
701 #endif
702 #ifdef __SIZEOF_FLOAT80__
703  if constexpr (__is_same(_Tp, __float80))
704  return _X86_80bit;
705 #endif
706 
707  constexpr int __width = sizeof(_Tp) * __CHAR_BIT__;
708 
709  if constexpr (__width == 16) // IEEE binary16 (or ARM fp16).
710  return _Binary16;
711  else if constexpr (__width == 32) // IEEE binary32
712  return _Binary32;
713  else if constexpr (__width == 64) // IEEE binary64
714  return _Binary64;
715  else if constexpr (__width == 128) // IEEE binary128
716  return _Binary128;
717  }
718 
719  // So we don't need to include <stdint.h> and pollute the namespace.
720  using int64_t = __INT64_TYPE__;
721  using int32_t = __INT32_TYPE__;
722  using int16_t = __INT16_TYPE__;
723  using uint64_t = __UINT64_TYPE__;
724  using uint16_t = __UINT16_TYPE__;
725 
726  // Used to unpack floating-point types that do not fit into an integer.
727  template<typename _Tp>
728  struct _Int
729  {
730 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
731  uint64_t _M_lo;
732  _Tp _M_hi;
733 #else
734  _Tp _M_hi;
735  uint64_t _M_lo;
736 #endif
737 
738  constexpr explicit
739  _Int(_Tp __hi, uint64_t __lo) noexcept : _M_hi(__hi)
740  { _M_lo = __lo; }
741 
742  constexpr explicit
743  _Int(uint64_t __lo) noexcept : _M_hi(0)
744  { _M_lo = __lo; }
745 
746  constexpr bool operator==(const _Int&) const = default;
747 
748 #if defined __hppa__ || (defined __mips__ && !defined __mips_nan2008)
749  consteval _Int
750  operator<<(int __n) const noexcept
751  {
752  // XXX this assumes n >= 64, which is true for the use below.
753  return _Int(static_cast<_Tp>(_M_lo << (__n - 64)), 0);
754  }
755 #endif
756 
757  constexpr _Int&
758  operator^=(const _Int& __rhs) noexcept
759  {
760  _M_hi ^= __rhs._M_hi;
761  _M_lo ^= __rhs._M_lo;
762  return *this;
763  }
764 
765  constexpr strong_ordering
766  operator<=>(const _Int& __rhs) const noexcept
767  {
768  strong_ordering __cmp = _M_hi <=> __rhs._M_hi;
769  if (__cmp != strong_ordering::equal)
770  return __cmp;
771  return _M_lo <=> __rhs._M_lo;
772  }
773  };
774 
775  template<typename _Tp>
776  static constexpr _Tp
777  _S_compl(_Tp __t) noexcept
778  {
779  constexpr int __width = sizeof(_Tp) * __CHAR_BIT__;
780  // Sign extend to get all ones or all zeros.
781  make_unsigned_t<_Tp> __sign = __t >> (__width - 1);
782  // If the sign bit was set, this flips all bits below it.
783  // This converts ones' complement to two's complement.
784  return __t ^ (__sign >> 1);
785  }
786 
787  // As above but works on both parts of _Int<T>.
788  template<typename _Tp>
789  static constexpr _Int<_Tp>
790  _S_compl(_Int<_Tp> __t) noexcept
791  {
792  constexpr int __width = sizeof(_Tp) * __CHAR_BIT__;
793  make_unsigned_t<_Tp> __sign = __t._M_hi >> (__width - 1);
794  __t._M_hi ^= (__sign >> 1 );
795  uint64_t __sign64 = (_Tp)__sign;
796  __t._M_lo ^= __sign64;
797  return __t;
798  }
799 
800  // Bit-cast a floating-point value to an unsigned integer.
801  template<typename _Tp>
802  constexpr static auto
803  _S_fp_bits(_Tp __val) noexcept
804  {
805  if constexpr (sizeof(_Tp) == sizeof(int64_t))
806  return __builtin_bit_cast(int64_t, __val);
807  else if constexpr (sizeof(_Tp) == sizeof(int32_t))
808  return __builtin_bit_cast(int32_t, __val);
809  else if constexpr (sizeof(_Tp) == sizeof(int16_t))
810  return __builtin_bit_cast(int16_t, __val);
811  else
812  {
813  using enum _Fp_fmt;
814  constexpr auto __fmt = _S_fp_fmt<_Tp>();
815  if constexpr (__fmt == _X86_80bit || __fmt == _M68k_80bit)
816  {
817  if constexpr (sizeof(_Tp) == 3 * sizeof(int32_t))
818  {
819  auto __ival = __builtin_bit_cast(_Int<int32_t>, __val);
820  return _Int<int16_t>(__ival._M_hi, __ival._M_lo);
821  }
822  else
823  {
824  auto __ival = __builtin_bit_cast(_Int<int64_t>, __val);
825  return _Int<int16_t>(__ival._M_hi, __ival._M_lo);
826  }
827  }
828  else if constexpr (sizeof(_Tp) == 2 * sizeof(int64_t))
829  {
830 #if __SIZEOF_INT128__
831  return __builtin_bit_cast(__int128, __val);
832 #else
833  return __builtin_bit_cast(_Int<int64_t>, __val);
834 #endif
835  }
836  else
837  static_assert(sizeof(_Tp) == sizeof(int64_t),
838  "unsupported floating-point type");
839  }
840  }
841 
842  template<typename _Tp>
843  static constexpr strong_ordering
844  _S_fp_cmp(_Tp __x, _Tp __y) noexcept
845  {
846 #ifdef __vax__
847  if (__builtin_isnan(__x) || __builtin_isnan(__y))
848  {
849  int __ix = (bool) __builtin_isnan(__x);
850  int __iy = (bool) __builtin_isnan(__y);
851  __ix *= __builtin_signbit(__x) ? -1 : 1;
852  __iy *= __builtin_signbit(__y) ? -1 : 1;
853  return __ix <=> __iy;
854  }
855  else
856  return __builtin_bit_cast(strong_ordering, __x <=> __y);
857 #endif
858 
859  auto __ix = _S_fp_bits(__x);
860  auto __iy = _S_fp_bits(__y);
861 
862  if (__ix == __iy)
863  return strong_ordering::equal; // All bits are equal, we're done.
864 
865  using enum _Fp_fmt;
866  constexpr auto __fmt = _S_fp_fmt<_Tp>();
867 
868  if constexpr (__fmt == _Dbldbl) // double-double
869  {
870  // Unpack the double-double into two parts.
871  // We never inspect the low double as a double, cast to integer.
872  struct _Unpacked { double _M_hi; int64_t _M_lo; };
873  auto __x2 = __builtin_bit_cast(_Unpacked, __x);
874  auto __y2 = __builtin_bit_cast(_Unpacked, __y);
875 
876  // Compare the high doubles first and use result if unequal.
877  auto __cmp = _S_fp_cmp(__x2._M_hi, __y2._M_hi);
878  if (__cmp != strong_ordering::equal)
879  return __cmp;
880 
881  // For NaN the low double is unused, so if the high doubles
882  // are the same NaN, we don't need to compare the low doubles.
883  if (__builtin_isnan(__x2._M_hi))
884  return strong_ordering::equal;
885  // Similarly, if the low doubles are +zero or -zero (which is
886  // true for all infinities and some other values), we're done.
887  if (((__x2._M_lo | __y2._M_lo) & 0x7fffffffffffffffULL) == 0)
888  return strong_ordering::equal;
889 
890  // Otherwise, compare the low parts.
891  return _S_compl(__x2._M_lo) <=> _S_compl(__y2._M_lo);
892  }
893  else
894  {
895  if constexpr (__fmt == _M68k_80bit)
896  {
897  // For m68k the MSB of the significand is ignored for the
898  // greatest exponent, so either 0 or 1 is valid there.
899  // Set it before comparing, so that we never have 0 there.
900  constexpr uint16_t __maxexp = 0x7fff;
901  if ((__ix._M_hi & __maxexp) == __maxexp)
902  __ix._M_lo |= 1ull << 63;
903  if ((__iy._M_hi & __maxexp) == __maxexp)
904  __iy._M_lo |= 1ull << 63;
905  }
906  else
907  {
908 #if defined __hppa__ || (defined __mips__ && !defined __mips_nan2008)
909  // IEEE 754-1985 allowed the meaning of the quiet/signaling
910  // bit to be reversed. Flip that to give desired ordering.
911  if (__builtin_isnan(__x) && __builtin_isnan(__y))
912  {
913  using _Int = decltype(__ix);
914 
915  constexpr int __nantype = __fmt == _Binary32 ? 22
916  : __fmt == _Binary64 ? 51
917  : __fmt == _Binary128 ? 111
918  : -1;
919  constexpr _Int __bit = _Int(1) << __nantype;
920  __ix ^= __bit;
921  __iy ^= __bit;
922  }
923 #endif
924  }
925  return _S_compl(__ix) <=> _S_compl(__iy);
926  }
927  }
928 
929  public:
930  template<typename _Tp, __decayed_same_as<_Tp> _Up>
931  requires __strongly_ordered<_Tp, _Up>
932  constexpr strong_ordering
933  operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
934  noexcept(_S_noexcept<_Tp, _Up>())
935  {
936  if constexpr (floating_point<decay_t<_Tp>>)
937  return _S_fp_cmp(__e, __f);
938  else if constexpr (__adl_strong<_Tp, _Up>)
939  return strong_ordering(strong_order(static_cast<_Tp&&>(__e),
940  static_cast<_Up&&>(__f)));
941  else if constexpr (__cmp3way<strong_ordering, _Tp, _Up>)
942  return compare_three_way()(static_cast<_Tp&&>(__e),
943  static_cast<_Up&&>(__f));
944  }
945  };
946 
947  template<typename _Tp, typename _Up>
948  concept __weakly_ordered
949  = floating_point<remove_reference_t<_Tp>>
950  || __adl_weak<_Tp, _Up>
951  || __cmp3way<weak_ordering, _Tp, _Up>
952  || __strongly_ordered<_Tp, _Up>;
953 
954  class _Weak_order
955  {
956  template<typename _Tp, typename _Up>
957  static constexpr bool
958  _S_noexcept()
959  {
960  if constexpr (floating_point<decay_t<_Tp>>)
961  return true;
962  else if constexpr (__adl_weak<_Tp, _Up>)
963  return noexcept(weak_ordering(weak_order(std::declval<_Tp>(),
964  std::declval<_Up>())));
965  else if constexpr (__cmp3way<weak_ordering, _Tp, _Up>)
966  return noexcept(compare_three_way()(std::declval<_Tp>(),
967  std::declval<_Up>()));
968  else if constexpr (__strongly_ordered<_Tp, _Up>)
969  return _Strong_order::_S_noexcept<_Tp, _Up>();
970  }
971 
972  friend class _Partial_order;
973  friend class _Weak_fallback;
974 
975  public:
976  template<typename _Tp, __decayed_same_as<_Tp> _Up>
977  requires __weakly_ordered<_Tp, _Up>
978  constexpr weak_ordering
979  operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
980  noexcept(_S_noexcept<_Tp, _Up>())
981  {
982  if constexpr (floating_point<decay_t<_Tp>>)
983  return __cmp_cust::__fp_weak_ordering(__e, __f);
984  else if constexpr (__adl_weak<_Tp, _Up>)
985  return weak_ordering(weak_order(static_cast<_Tp&&>(__e),
986  static_cast<_Up&&>(__f)));
987  else if constexpr (__cmp3way<weak_ordering, _Tp, _Up>)
988  return compare_three_way()(static_cast<_Tp&&>(__e),
989  static_cast<_Up&&>(__f));
990  else if constexpr (__strongly_ordered<_Tp, _Up>)
991  return _Strong_order{}(static_cast<_Tp&&>(__e),
992  static_cast<_Up&&>(__f));
993  }
994  };
995 
996  template<typename _Tp, typename _Up>
997  concept __partially_ordered
998  = __adl_partial<_Tp, _Up>
999  || __cmp3way<partial_ordering, _Tp, _Up>
1000  || __weakly_ordered<_Tp, _Up>;
1001 
1002  class _Partial_order
1003  {
1004  template<typename _Tp, typename _Up>
1005  static constexpr bool
1006  _S_noexcept()
1007  {
1008  if constexpr (__adl_partial<_Tp, _Up>)
1009  return noexcept(partial_ordering(partial_order(std::declval<_Tp>(),
1010  std::declval<_Up>())));
1011  else if constexpr (__cmp3way<partial_ordering, _Tp, _Up>)
1012  return noexcept(compare_three_way()(std::declval<_Tp>(),
1013  std::declval<_Up>()));
1014  else if constexpr (__weakly_ordered<_Tp, _Up>)
1015  return _Weak_order::_S_noexcept<_Tp, _Up>();
1016  }
1017 
1018  friend class _Partial_fallback;
1019 
1020  public:
1021  template<typename _Tp, __decayed_same_as<_Tp> _Up>
1022  requires __partially_ordered<_Tp, _Up>
1023  constexpr partial_ordering
1024  operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
1025  noexcept(_S_noexcept<_Tp, _Up>())
1026  {
1027  if constexpr (__adl_partial<_Tp, _Up>)
1028  return partial_ordering(partial_order(static_cast<_Tp&&>(__e),
1029  static_cast<_Up&&>(__f)));
1030  else if constexpr (__cmp3way<partial_ordering, _Tp, _Up>)
1031  return compare_three_way()(static_cast<_Tp&&>(__e),
1032  static_cast<_Up&&>(__f));
1033  else if constexpr (__weakly_ordered<_Tp, _Up>)
1034  return _Weak_order{}(static_cast<_Tp&&>(__e),
1035  static_cast<_Up&&>(__f));
1036  }
1037  };
1038 
1039  template<typename _Tp, typename _Up>
1040  concept __op_eq_lt = requires(_Tp&& __t, _Up&& __u)
1041  {
1042  { static_cast<_Tp&&>(__t) == static_cast<_Up&&>(__u) }
1043  -> convertible_to<bool>;
1044  { static_cast<_Tp&&>(__t) < static_cast<_Up&&>(__u) }
1045  -> convertible_to<bool>;
1046  };
1047 
1048  class _Strong_fallback
1049  {
1050  template<typename _Tp, typename _Up>
1051  static constexpr bool
1052  _S_noexcept()
1053  {
1054  if constexpr (__strongly_ordered<_Tp, _Up>)
1055  return _Strong_order::_S_noexcept<_Tp, _Up>();
1056  else
1057  return noexcept(bool(std::declval<_Tp>() == std::declval<_Up>()))
1058  && noexcept(bool(std::declval<_Tp>() < std::declval<_Up>()));
1059  }
1060 
1061  public:
1062  template<typename _Tp, __decayed_same_as<_Tp> _Up>
1063  requires __strongly_ordered<_Tp, _Up> || __op_eq_lt<_Tp, _Up>
1064  constexpr strong_ordering
1065  operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
1066  noexcept(_S_noexcept<_Tp, _Up>())
1067  {
1068  if constexpr (__strongly_ordered<_Tp, _Up>)
1069  return _Strong_order{}(static_cast<_Tp&&>(__e),
1070  static_cast<_Up&&>(__f));
1071  else // __op_eq_lt<_Tp, _Up>
1072  return static_cast<_Tp&&>(__e) == static_cast<_Up&&>(__f)
1073  ? strong_ordering::equal
1074  : static_cast<_Tp&&>(__e) < static_cast<_Up&&>(__f)
1075  ? strong_ordering::less
1076  : strong_ordering::greater;
1077  }
1078  };
1079 
1080  class _Weak_fallback
1081  {
1082  template<typename _Tp, typename _Up>
1083  static constexpr bool
1084  _S_noexcept()
1085  {
1086  if constexpr (__weakly_ordered<_Tp, _Up>)
1087  return _Weak_order::_S_noexcept<_Tp, _Up>();
1088  else
1089  return noexcept(bool(std::declval<_Tp>() == std::declval<_Up>()))
1090  && noexcept(bool(std::declval<_Tp>() < std::declval<_Up>()));
1091  }
1092 
1093  public:
1094  template<typename _Tp, __decayed_same_as<_Tp> _Up>
1095  requires __weakly_ordered<_Tp, _Up> || __op_eq_lt<_Tp, _Up>
1096  constexpr weak_ordering
1097  operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
1098  noexcept(_S_noexcept<_Tp, _Up>())
1099  {
1100  if constexpr (__weakly_ordered<_Tp, _Up>)
1101  return _Weak_order{}(static_cast<_Tp&&>(__e),
1102  static_cast<_Up&&>(__f));
1103  else // __op_eq_lt<_Tp, _Up>
1104  return static_cast<_Tp&&>(__e) == static_cast<_Up&&>(__f)
1105  ? weak_ordering::equivalent
1106  : static_cast<_Tp&&>(__e) < static_cast<_Up&&>(__f)
1107  ? weak_ordering::less
1108  : weak_ordering::greater;
1109  }
1110  };
1111 
1112  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1113  // 3465. compare_partial_order_fallback requires F < E
1114  template<typename _Tp, typename _Up>
1115  concept __op_eq_lt_lt = __op_eq_lt<_Tp, _Up>
1116  && requires(_Tp&& __t, _Up&& __u)
1117  {
1118  { static_cast<_Up&&>(__u) < static_cast<_Tp&&>(__t) }
1119  -> convertible_to<bool>;
1120  };
1121 
1122  class _Partial_fallback
1123  {
1124  template<typename _Tp, typename _Up>
1125  static constexpr bool
1126  _S_noexcept()
1127  {
1128  if constexpr (__partially_ordered<_Tp, _Up>)
1129  return _Partial_order::_S_noexcept<_Tp, _Up>();
1130  else
1131  return noexcept(bool(std::declval<_Tp>() == std::declval<_Up>()))
1132  && noexcept(bool(std::declval<_Tp>() < std::declval<_Up>()));
1133  }
1134 
1135  public:
1136  template<typename _Tp, __decayed_same_as<_Tp> _Up>
1137  requires __partially_ordered<_Tp, _Up> || __op_eq_lt_lt<_Tp, _Up>
1138  constexpr partial_ordering
1139  operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
1140  noexcept(_S_noexcept<_Tp, _Up>())
1141  {
1142  if constexpr (__partially_ordered<_Tp, _Up>)
1143  return _Partial_order{}(static_cast<_Tp&&>(__e),
1144  static_cast<_Up&&>(__f));
1145  else // __op_eq_lt_lt<_Tp, _Up>
1146  return static_cast<_Tp&&>(__e) == static_cast<_Up&&>(__f)
1147  ? partial_ordering::equivalent
1148  : static_cast<_Tp&&>(__e) < static_cast<_Up&&>(__f)
1149  ? partial_ordering::less
1150  : static_cast<_Up&&>(__f) < static_cast<_Tp&&>(__e)
1151  ? partial_ordering::greater
1152  : partial_ordering::unordered;
1153  }
1154  };
1155  } // namespace __cmp_cust
1156 
1157  // [cmp.alg], comparison algorithms
1158  inline namespace __cmp_alg
1159  {
1160  inline constexpr __cmp_cust::_Strong_order strong_order{};
1161 
1162  inline constexpr __cmp_cust::_Weak_order weak_order{};
1163 
1164  inline constexpr __cmp_cust::_Partial_order partial_order{};
1165 
1166  inline constexpr __cmp_cust::_Strong_fallback
1167  compare_strong_order_fallback{};
1168 
1169  inline constexpr __cmp_cust::_Weak_fallback
1170  compare_weak_order_fallback{};
1171 
1172  inline constexpr __cmp_cust::_Partial_fallback
1173  compare_partial_order_fallback{};
1174  }
1175 
1176  namespace __detail
1177  {
1178  // [expos.only.func] synth-three-way
1179  inline constexpr struct _Synth3way
1180  {
1181  template<typename _Tp, typename _Up>
1182  static constexpr bool
1183  _S_noexcept(const _Tp* __t = nullptr, const _Up* __u = nullptr)
1184  {
1185  if constexpr (three_way_comparable_with<_Tp, _Up>)
1186  return noexcept(*__t <=> *__u);
1187  else
1188  return noexcept(*__t < *__u) && noexcept(*__u < *__t);
1189  }
1190 
1191  template<typename _Tp, typename _Up>
1192  [[nodiscard]]
1193  constexpr auto
1194  operator()(const _Tp& __t, const _Up& __u) const
1195  noexcept(_S_noexcept<_Tp, _Up>())
1196  requires requires
1197  {
1198  { __t < __u } -> __boolean_testable;
1199  { __u < __t } -> __boolean_testable;
1200  }
1201  {
1202  if constexpr (three_way_comparable_with<_Tp, _Up>)
1203  return __t <=> __u;
1204  else
1205  {
1206  if (__t < __u)
1207  return weak_ordering::less;
1208  else if (__u < __t)
1209  return weak_ordering::greater;
1210  else
1211  return weak_ordering::equivalent;
1212  }
1213  }
1214  } __synth3way = {};
1215 
1216  // [expos.only.func] synth-three-way-result
1217  template<typename _Tp, typename _Up = _Tp>
1218  using __synth3way_t
1219  = decltype(__detail::__synth3way(std::declval<_Tp&>(),
1220  std::declval<_Up&>()));
1221  } // namespace __detail
1222 #endif // concepts
1223 } // namespace std
1224 
1225 #pragma GCC visibility pop
1226 
1227 #endif // C++20
1228 
1229 #endif // _COMPARE
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
Definition: type_traits:1670
auto declval() noexcept -> decltype(__declval< _Tp >(0))
Definition: type_traits:2393
ISO C++ entities toplevel namespace is std.
std::basic_ostream< _CharT, _Traits > & operator<<(std::basic_ostream< _CharT, _Traits > &__os, const bitset< _Nb > &__x)
Global I/O operators for bitsets.
Definition: bitset:1540
typename __detail::__cmp3way_res_impl< _Tp, _Up >::type compare_three_way_result_t
[cmp.result], result of three-way comparison
Definition: compare:522
[cmp.result], result of three-way comparison
Definition: compare:517