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>
515  struct compare_three_way_result
516  : __detail::__cmp3way_res_impl<_Tp, _Up>
517  { };
518 
519  /// [cmp.result], result of three-way comparison
520  template<typename _Tp, typename _Up = _Tp>
521  using compare_three_way_result_t
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  auto __ix = _S_fp_bits(__x);
847  auto __iy = _S_fp_bits(__y);
848 
849  if (__ix == __iy)
850  return strong_ordering::equal; // All bits are equal, we're done.
851 
852  using enum _Fp_fmt;
853  constexpr auto __fmt = _S_fp_fmt<_Tp>();
854 
855  if constexpr (__fmt == _Dbldbl) // double-double
856  {
857  // Unpack the double-double into two parts.
858  // We never inspect the low double as a double, cast to integer.
859  struct _Unpacked { double _M_hi; int64_t _M_lo; };
860  auto __x2 = __builtin_bit_cast(_Unpacked, __x);
861  auto __y2 = __builtin_bit_cast(_Unpacked, __y);
862 
863  // Compare the high doubles first and use result if unequal.
864  auto __cmp = _S_fp_cmp(__x2._M_hi, __y2._M_hi);
865  if (__cmp != strong_ordering::equal)
866  return __cmp;
867 
868  // For NaN the low double is unused, so if the high doubles
869  // are the same NaN, we don't need to compare the low doubles.
870  if (__builtin_isnan(__x2._M_hi))
871  return strong_ordering::equal;
872  // Similarly, if the low doubles are +zero or -zero (which is
873  // true for all infinities and some other values), we're done.
874  if (((__x2._M_lo | __y2._M_lo) & 0x7fffffffffffffffULL) == 0)
875  return strong_ordering::equal;
876 
877  // Otherwise, compare the low parts.
878  return _S_compl(__x2._M_lo) <=> _S_compl(__y2._M_lo);
879  }
880  else
881  {
882  if constexpr (__fmt == _M68k_80bit)
883  {
884  // For m68k the MSB of the significand is ignored for the
885  // greatest exponent, so either 0 or 1 is valid there.
886  // Set it before comparing, so that we never have 0 there.
887  constexpr uint16_t __maxexp = 0x7fff;
888  if ((__ix._M_hi & __maxexp) == __maxexp)
889  __ix._M_lo |= 1ull << 63;
890  if ((__iy._M_hi & __maxexp) == __maxexp)
891  __iy._M_lo |= 1ull << 63;
892  }
893  else
894  {
895 #if defined __hppa__ || (defined __mips__ && !defined __mips_nan2008)
896  // IEEE 754-1985 allowed the meaning of the quiet/signaling
897  // bit to be reversed. Flip that to give desired ordering.
898  if (__builtin_isnan(__x) && __builtin_isnan(__y))
899  {
900  using _Int = decltype(__ix);
901 
902  constexpr int __nantype = __fmt == _Binary32 ? 22
903  : __fmt == _Binary64 ? 51
904  : __fmt == _Binary128 ? 111
905  : -1;
906  constexpr _Int __bit = _Int(1) << __nantype;
907  __ix ^= __bit;
908  __iy ^= __bit;
909  }
910 #endif
911  }
912  return _S_compl(__ix) <=> _S_compl(__iy);
913  }
914  }
915 
916  public:
917  template<typename _Tp, __decayed_same_as<_Tp> _Up>
918  requires __strongly_ordered<_Tp, _Up>
919  constexpr strong_ordering
920  operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
921  noexcept(_S_noexcept<_Tp, _Up>())
922  {
923  if constexpr (floating_point<decay_t<_Tp>>)
924  return _S_fp_cmp(__e, __f);
925  else if constexpr (__adl_strong<_Tp, _Up>)
926  return strong_ordering(strong_order(static_cast<_Tp&&>(__e),
927  static_cast<_Up&&>(__f)));
928  else if constexpr (__cmp3way<strong_ordering, _Tp, _Up>)
929  return compare_three_way()(static_cast<_Tp&&>(__e),
930  static_cast<_Up&&>(__f));
931  }
932  };
933 
934  template<typename _Tp, typename _Up>
935  concept __weakly_ordered
936  = floating_point<remove_reference_t<_Tp>>
937  || __adl_weak<_Tp, _Up>
938  || __cmp3way<weak_ordering, _Tp, _Up>
939  || __strongly_ordered<_Tp, _Up>;
940 
941  class _Weak_order
942  {
943  template<typename _Tp, typename _Up>
944  static constexpr bool
945  _S_noexcept()
946  {
947  if constexpr (floating_point<decay_t<_Tp>>)
948  return true;
949  else if constexpr (__adl_weak<_Tp, _Up>)
950  return noexcept(weak_ordering(weak_order(std::declval<_Tp>(),
951  std::declval<_Up>())));
952  else if constexpr (__cmp3way<weak_ordering, _Tp, _Up>)
953  return noexcept(compare_three_way()(std::declval<_Tp>(),
954  std::declval<_Up>()));
955  else if constexpr (__strongly_ordered<_Tp, _Up>)
956  return _Strong_order::_S_noexcept<_Tp, _Up>();
957  }
958 
959  friend class _Partial_order;
960  friend class _Weak_fallback;
961 
962  public:
963  template<typename _Tp, __decayed_same_as<_Tp> _Up>
964  requires __weakly_ordered<_Tp, _Up>
965  constexpr weak_ordering
966  operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
967  noexcept(_S_noexcept<_Tp, _Up>())
968  {
969  if constexpr (floating_point<decay_t<_Tp>>)
970  return __cmp_cust::__fp_weak_ordering(__e, __f);
971  else if constexpr (__adl_weak<_Tp, _Up>)
972  return weak_ordering(weak_order(static_cast<_Tp&&>(__e),
973  static_cast<_Up&&>(__f)));
974  else if constexpr (__cmp3way<weak_ordering, _Tp, _Up>)
975  return compare_three_way()(static_cast<_Tp&&>(__e),
976  static_cast<_Up&&>(__f));
977  else if constexpr (__strongly_ordered<_Tp, _Up>)
978  return _Strong_order{}(static_cast<_Tp&&>(__e),
979  static_cast<_Up&&>(__f));
980  }
981  };
982 
983  template<typename _Tp, typename _Up>
984  concept __partially_ordered
985  = __adl_partial<_Tp, _Up>
986  || __cmp3way<partial_ordering, _Tp, _Up>
987  || __weakly_ordered<_Tp, _Up>;
988 
989  class _Partial_order
990  {
991  template<typename _Tp, typename _Up>
992  static constexpr bool
993  _S_noexcept()
994  {
995  if constexpr (__adl_partial<_Tp, _Up>)
996  return noexcept(partial_ordering(partial_order(std::declval<_Tp>(),
997  std::declval<_Up>())));
998  else if constexpr (__cmp3way<partial_ordering, _Tp, _Up>)
999  return noexcept(compare_three_way()(std::declval<_Tp>(),
1000  std::declval<_Up>()));
1001  else if constexpr (__weakly_ordered<_Tp, _Up>)
1002  return _Weak_order::_S_noexcept<_Tp, _Up>();
1003  }
1004 
1005  friend class _Partial_fallback;
1006 
1007  public:
1008  template<typename _Tp, __decayed_same_as<_Tp> _Up>
1009  requires __partially_ordered<_Tp, _Up>
1010  constexpr partial_ordering
1011  operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
1012  noexcept(_S_noexcept<_Tp, _Up>())
1013  {
1014  if constexpr (__adl_partial<_Tp, _Up>)
1015  return partial_ordering(partial_order(static_cast<_Tp&&>(__e),
1016  static_cast<_Up&&>(__f)));
1017  else if constexpr (__cmp3way<partial_ordering, _Tp, _Up>)
1018  return compare_three_way()(static_cast<_Tp&&>(__e),
1019  static_cast<_Up&&>(__f));
1020  else if constexpr (__weakly_ordered<_Tp, _Up>)
1021  return _Weak_order{}(static_cast<_Tp&&>(__e),
1022  static_cast<_Up&&>(__f));
1023  }
1024  };
1025 
1026  template<typename _Tp, typename _Up>
1027  concept __op_eq_lt = requires(_Tp&& __t, _Up&& __u)
1028  {
1029  { static_cast<_Tp&&>(__t) == static_cast<_Up&&>(__u) }
1030  -> convertible_to<bool>;
1031  { static_cast<_Tp&&>(__t) < static_cast<_Up&&>(__u) }
1032  -> convertible_to<bool>;
1033  };
1034 
1035  class _Strong_fallback
1036  {
1037  template<typename _Tp, typename _Up>
1038  static constexpr bool
1039  _S_noexcept()
1040  {
1041  if constexpr (__strongly_ordered<_Tp, _Up>)
1042  return _Strong_order::_S_noexcept<_Tp, _Up>();
1043  else
1044  return noexcept(bool(std::declval<_Tp>() == std::declval<_Up>()))
1045  && noexcept(bool(std::declval<_Tp>() < std::declval<_Up>()));
1046  }
1047 
1048  public:
1049  template<typename _Tp, __decayed_same_as<_Tp> _Up>
1050  requires __strongly_ordered<_Tp, _Up> || __op_eq_lt<_Tp, _Up>
1051  constexpr strong_ordering
1052  operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
1053  noexcept(_S_noexcept<_Tp, _Up>())
1054  {
1055  if constexpr (__strongly_ordered<_Tp, _Up>)
1056  return _Strong_order{}(static_cast<_Tp&&>(__e),
1057  static_cast<_Up&&>(__f));
1058  else // __op_eq_lt<_Tp, _Up>
1059  return static_cast<_Tp&&>(__e) == static_cast<_Up&&>(__f)
1060  ? strong_ordering::equal
1061  : static_cast<_Tp&&>(__e) < static_cast<_Up&&>(__f)
1062  ? strong_ordering::less
1063  : strong_ordering::greater;
1064  }
1065  };
1066 
1067  class _Weak_fallback
1068  {
1069  template<typename _Tp, typename _Up>
1070  static constexpr bool
1071  _S_noexcept()
1072  {
1073  if constexpr (__weakly_ordered<_Tp, _Up>)
1074  return _Weak_order::_S_noexcept<_Tp, _Up>();
1075  else
1076  return noexcept(bool(std::declval<_Tp>() == std::declval<_Up>()))
1077  && noexcept(bool(std::declval<_Tp>() < std::declval<_Up>()));
1078  }
1079 
1080  public:
1081  template<typename _Tp, __decayed_same_as<_Tp> _Up>
1082  requires __weakly_ordered<_Tp, _Up> || __op_eq_lt<_Tp, _Up>
1083  constexpr weak_ordering
1084  operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
1085  noexcept(_S_noexcept<_Tp, _Up>())
1086  {
1087  if constexpr (__weakly_ordered<_Tp, _Up>)
1088  return _Weak_order{}(static_cast<_Tp&&>(__e),
1089  static_cast<_Up&&>(__f));
1090  else // __op_eq_lt<_Tp, _Up>
1091  return static_cast<_Tp&&>(__e) == static_cast<_Up&&>(__f)
1092  ? weak_ordering::equivalent
1093  : static_cast<_Tp&&>(__e) < static_cast<_Up&&>(__f)
1094  ? weak_ordering::less
1095  : weak_ordering::greater;
1096  }
1097  };
1098 
1099  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1100  // 3465. compare_partial_order_fallback requires F < E
1101  template<typename _Tp, typename _Up>
1102  concept __op_eq_lt_lt = __op_eq_lt<_Tp, _Up>
1103  && requires(_Tp&& __t, _Up&& __u)
1104  {
1105  { static_cast<_Up&&>(__u) < static_cast<_Tp&&>(__t) }
1106  -> convertible_to<bool>;
1107  };
1108 
1109  class _Partial_fallback
1110  {
1111  template<typename _Tp, typename _Up>
1112  static constexpr bool
1113  _S_noexcept()
1114  {
1115  if constexpr (__partially_ordered<_Tp, _Up>)
1116  return _Partial_order::_S_noexcept<_Tp, _Up>();
1117  else
1118  return noexcept(bool(std::declval<_Tp>() == std::declval<_Up>()))
1119  && noexcept(bool(std::declval<_Tp>() < std::declval<_Up>()));
1120  }
1121 
1122  public:
1123  template<typename _Tp, __decayed_same_as<_Tp> _Up>
1124  requires __partially_ordered<_Tp, _Up> || __op_eq_lt_lt<_Tp, _Up>
1125  constexpr partial_ordering
1126  operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
1127  noexcept(_S_noexcept<_Tp, _Up>())
1128  {
1129  if constexpr (__partially_ordered<_Tp, _Up>)
1130  return _Partial_order{}(static_cast<_Tp&&>(__e),
1131  static_cast<_Up&&>(__f));
1132  else // __op_eq_lt_lt<_Tp, _Up>
1133  return static_cast<_Tp&&>(__e) == static_cast<_Up&&>(__f)
1134  ? partial_ordering::equivalent
1135  : static_cast<_Tp&&>(__e) < static_cast<_Up&&>(__f)
1136  ? partial_ordering::less
1137  : static_cast<_Up&&>(__f) < static_cast<_Tp&&>(__e)
1138  ? partial_ordering::greater
1139  : partial_ordering::unordered;
1140  }
1141  };
1142  } // namespace __cmp_cust
1143 
1144  // [cmp.alg], comparison algorithms
1145  inline namespace __cmp_alg
1146  {
1147  inline constexpr __cmp_cust::_Strong_order strong_order{};
1148 
1149  inline constexpr __cmp_cust::_Weak_order weak_order{};
1150 
1151  inline constexpr __cmp_cust::_Partial_order partial_order{};
1152 
1153  inline constexpr __cmp_cust::_Strong_fallback
1154  compare_strong_order_fallback{};
1155 
1156  inline constexpr __cmp_cust::_Weak_fallback
1157  compare_weak_order_fallback{};
1158 
1159  inline constexpr __cmp_cust::_Partial_fallback
1160  compare_partial_order_fallback{};
1161  }
1162 
1163  namespace __detail
1164  {
1165  // [expos.only.func] synth-three-way
1166  inline constexpr struct _Synth3way
1167  {
1168  template<typename _Tp, typename _Up>
1169  static constexpr bool
1170  _S_noexcept(const _Tp* __t = nullptr, const _Up* __u = nullptr)
1171  {
1172  if constexpr (three_way_comparable_with<_Tp, _Up>)
1173  return noexcept(*__t <=> *__u);
1174  else
1175  return noexcept(*__t < *__u) && noexcept(*__u < *__t);
1176  }
1177 
1178  template<typename _Tp, typename _Up>
1179  [[nodiscard]]
1180  constexpr auto
1181  operator()(const _Tp& __t, const _Up& __u) const
1182  noexcept(_S_noexcept<_Tp, _Up>())
1183  requires requires
1184  {
1185  { __t < __u } -> __boolean_testable;
1186  { __u < __t } -> __boolean_testable;
1187  }
1188  {
1189  if constexpr (three_way_comparable_with<_Tp, _Up>)
1190  return __t <=> __u;
1191  else
1192  {
1193  if (__t < __u)
1194  return weak_ordering::less;
1195  else if (__u < __t)
1196  return weak_ordering::greater;
1197  else
1198  return weak_ordering::equivalent;
1199  }
1200  }
1201  } __synth3way = {};
1202 
1203  // [expos.only.func] synth-three-way-result
1204  template<typename _Tp, typename _Up = _Tp>
1205  using __synth3way_t
1206  = decltype(__detail::__synth3way(std::declval<_Tp&>(),
1207  std::declval<_Up&>()));
1208  } // namespace __detail
1209 #endif // concepts
1210 } // namespace std
1211 
1212 #pragma GCC visibility pop
1213 
1214 #endif // C++20
1215 
1216 #endif // _COMPARE