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