17#if defined(HIGHWAY_HWY_CONTRIB_SORT_TRAITS_TOGGLE) == \
18 defined(HWY_TARGET_TOGGLE)
19#ifdef HIGHWAY_HWY_CONTRIB_SORT_TRAITS_TOGGLE
20#undef HIGHWAY_HWY_CONTRIB_SORT_TRAITS_TOGGLE
22#define HIGHWAY_HWY_CONTRIB_SORT_TRAITS_TOGGLE
37#if VQSORT_ENABLED || HWY_IDE
44 static constexpr bool Is128() {
return false; }
47 static constexpr bool IsKV() {
return false; }
68 template <
class V,
class M>
69 HWY_INLINE V CompressKeys(V keys, M mask)
const {
80 HWY_INLINE Mask<D> EqualKeys(D , Vec<D> a, Vec<D> b)
const {
85 HWY_INLINE Mask<D> NotEqualKeys(D , Vec<D> a, Vec<D> b)
const {
91 HWY_INLINE bool NoKeyDifference(D , Vec<D> diff)
const {
93 const RebindToUnsigned<D> du;
97 HWY_INLINE bool Equal1(
const T* a,
const T* b)
const {
return *a == *b; }
122 return ReverseKeys(
d,
v);
126 HWY_INLINE V OddEvenKeys(
const V odd,
const V even)
const {
130 template <
class D, HWY_IF_LANE_SIZE_D(D, 2)>
131 HWY_INLINE Vec<D> SwapAdjacentPairs(D
d,
const Vec<D>
v)
const {
132 const Repartition<uint32_t, D> du32;
135 template <
class D, HWY_IF_LANE_SIZE_D(D, 4)>
136 HWY_INLINE Vec<D> SwapAdjacentPairs(D ,
const Vec<D>
v)
const {
139 template <
class D, HWY_IF_LANE_SIZE_D(D, 8)>
140 HWY_INLINE Vec<D> SwapAdjacentPairs(D ,
const Vec<D>
v)
const {
144 template <
class D, HWY_IF_NOT_LANE_SIZE_D(D, 8)>
145 HWY_INLINE Vec<D> SwapAdjacentQuads(D
d,
const Vec<D>
v)
const {
147 const RepartitionToWide<D> dw;
149 const RepartitionToWide<RebindToUnsigned<D> > dw;
153 template <
class D, HWY_IF_LANE_SIZE_D(D, 8)>
154 HWY_INLINE Vec<D> SwapAdjacentQuads(D
d,
const Vec<D>
v)
const {
159 template <
class D, HWY_IF_NOT_LANE_SIZE_D(D, 8)>
160 HWY_INLINE Vec<D> OddEvenPairs(D
d,
const Vec<D> odd,
161 const Vec<D> even)
const {
163 const RepartitionToWide<D> dw;
165 const RepartitionToWide<RebindToUnsigned<D> > dw;
169 template <
class D, HWY_IF_LANE_SIZE_D(D, 8)>
170 HWY_INLINE Vec<D> OddEvenPairs(D , Vec<D> odd, Vec<D> even)
const {
174 template <
class D, HWY_IF_NOT_LANE_SIZE_D(D, 8)>
175 HWY_INLINE Vec<D> OddEvenQuads(D
d, Vec<D> odd, Vec<D> even)
const {
177 const RepartitionToWide<D> dw;
179 const RepartitionToWide<RebindToUnsigned<D> > dw;
183 template <
class D, HWY_IF_LANE_SIZE_D(D, 8)>
184 HWY_INLINE Vec<D> OddEvenQuads(D
d, Vec<D> odd, Vec<D> even)
const {
197struct OrderAscending :
public KeyLane<T> {
198 using Order = SortAscending;
209 HWY_INLINE Vec<D> First(D ,
const Vec<D> a,
const Vec<D> b)
const {
214 HWY_INLINE Vec<D> Last(D ,
const Vec<D> a,
const Vec<D> b)
const {
232 return Set(
d, hwy::LowestValue<T>());
237 return Set(
d, hwy::HighestValue<T>());
242 return Sub(
v,
Set(
d, hwy::Epsilon<T>()));
247struct OrderDescending :
public KeyLane<T> {
248 using Order = SortDescending;
258 HWY_INLINE Vec<D> First(D ,
const Vec<D> a,
const Vec<D> b)
const {
263 HWY_INLINE Vec<D> Last(D ,
const Vec<D> a,
const Vec<D> b)
const {
281 return Set(
d, hwy::HighestValue<T>());
286 return Set(
d, hwy::LowestValue<T>());
291 return Add(
v,
Set(
d, hwy::Epsilon<T>()));
295struct KeyValue64 :
public KeyLane<uint64_t> {
298 static constexpr bool IsKV() {
return true; }
301 HWY_INLINE Mask<D> EqualKeys(D , Vec<D> a, Vec<D> b)
const {
302 return Eq(ShiftRight<32>(a), ShiftRight<32>(b));
306 HWY_INLINE Mask<D> NotEqualKeys(D , Vec<D> a, Vec<D> b)
const {
307 return Ne(ShiftRight<32>(a), ShiftRight<32>(b));
310 HWY_INLINE bool Equal1(
const uint64_t* a,
const uint64_t* b)
const {
311 return (*a >> 32) == (*b >> 32);
316 HWY_INLINE bool NoKeyDifference(D , Vec<D> diff)
const {
318 const RebindToUnsigned<D> du;
319 const Vec<
decltype(du)> zero =
Zero(du);
320 const Vec<
decltype(du)> keys = ShiftRight<32>(diff);
325struct OrderAscendingKV64 :
public KeyValue64 {
326 using Order = SortAscending;
328 HWY_INLINE bool Compare1(
const LaneType* a,
const LaneType* b) {
329 return (*a >> 32) < (*b >> 32);
333 HWY_INLINE Mask<D> Compare(D , Vec<D> a, Vec<D> b)
const {
334 return Lt(ShiftRight<32>(a), ShiftRight<32>(b));
340 HWY_INLINE Vec<D> First(D ,
const Vec<D> a,
const Vec<D> b)
const {
345 HWY_INLINE Vec<D> Last(D ,
const Vec<D> a,
const Vec<D> b)
const {
373 HWY_INLINE Vec<D> PrevValue(D d, Vec<D> v)
const {
374 return Sub(v,
Set(d, uint64_t{1}));
378struct OrderDescendingKV64 :
public KeyValue64 {
379 using Order = SortDescending;
381 HWY_INLINE bool Compare1(
const LaneType* a,
const LaneType* b) {
382 return (*b >> 32) < (*a >> 32);
386 HWY_INLINE Mask<D> Compare(D , Vec<D> a, Vec<D> b)
const {
387 return Lt(ShiftRight<32>(b), ShiftRight<32>(a));
393 HWY_INLINE Vec<D> First(D ,
const Vec<D> a,
const Vec<D> b)
const {
398 HWY_INLINE Vec<D> Last(D ,
const Vec<D> a,
const Vec<D> b)
const {
425 HWY_INLINE Vec<D> PrevValue(D d, Vec<D> v)
const {
426 return Add(v,
Set(d, uint64_t{1}));
432struct TraitsLane :
public Base {
438 HWY_INLINE void Sort2(D
d, Vec<D>& a, Vec<D>& b)
const {
439 const Base* base =
static_cast<const Base*
>(
this);
441 const Vec<D> a_copy = a;
444#if HWY_AVX3 < HWY_TARGET && HWY_TARGET <= HWY_SSSE3
445 if (
sizeof(TFromD<D>) == 8) {
446 const Mask<D> cmp = base->Compare(
d, a, b);
452 a = base->First(
d, a, b);
453 b = base->Last(
d, a_copy, b);
457 template <
class D, HWY_IF_LANE_SIZE_D(D, 8)>
458 HWY_INLINE Vec<D> SortPairsDistance1(D
d, Vec<D>
v)
const {
459 const Base* base =
static_cast<const Base*
>(
this);
460 Vec<D> swapped = base->ReverseKeys2(
d,
v);
463#if HWY_AVX3 < HWY_TARGET && HWY_TARGET <= HWY_SSSE3
467 Sort2(
d,
v, swapped);
468 return base->OddEvenKeys(swapped,
v);
473 template <
class D, HWY_IF_NOT_LANE_SIZE_D(D, 8)>
474 HWY_INLINE Vec<D> SortPairsDistance1(D
d, Vec<D>
v)
const {
475 const Base* base =
static_cast<const Base*
>(
this);
476 Vec<D> swapped = base->ReverseKeys2(
d,
v);
477 Sort2(
d,
v, swapped);
478 return base->OddEvenKeys(swapped,
v);
483 HWY_INLINE Vec<D> SortPairsReverse4(D
d, Vec<D>
v)
const {
484 const Base* base =
static_cast<const Base*
>(
this);
485 Vec<D> swapped = base->ReverseKeys4(
d,
v);
486 Sort2(
d,
v, swapped);
487 return base->OddEvenPairs(
d, swapped,
v);
492 HWY_INLINE Vec<D> SortPairsDistance4(D
d, Vec<D>
v)
const {
493 const Base* base =
static_cast<const Base*
>(
this);
494 Vec<D> swapped = base->SwapAdjacentQuads(
d,
v);
497 Sort2(
d,
v, swapped);
498 return base->OddEvenQuads(
d, swapped,
v);
507 constexpr bool Is128()
const {
return false; }
544template <
class Order>
547 template <
typename T>
#define HWY_RESTRICT
Definition base.h:64
#define HWY_INLINE
Definition base.h:70
HWY_API Vec128< T, N > Shuffle2301(const Vec128< T, N > a, const Vec128< T, N > b)
Definition wasm_128-inl.h:2413
HWY_INLINE bool AllTrue(hwy::SizeTag< 1 >, const Mask128< T > m)
Definition wasm_128-inl.h:3661
HWY_INLINE Vec128< T, N > Add(hwy::NonFloatTag, Vec128< T, N > a, Vec128< T, N > b)
Definition emu128-inl.h:535
HWY_INLINE Vec128< T, N > OddEven(hwy::SizeTag< 1 >, const Vec128< T, N > a, const Vec128< T, N > b)
Definition wasm_128-inl.h:3023
HWY_INLINE Vec128< T, N > Min(hwy::NonFloatTag, Vec128< T, N > a, const Vec128< T, N > b)
Definition emu128-inl.h:663
HWY_INLINE Vec128< T, 1 > MinOfLanes(hwy::SizeTag< sizeof(T)>, const Vec128< T, 1 > v)
Definition arm_neon-inl.h:5063
HWY_INLINE Vec128< T, N > CompressNot(Vec128< T, N > v, const uint64_t mask_bits)
Definition arm_neon-inl.h:6162
HWY_INLINE Vec128< T, N > Sub(hwy::NonFloatTag, Vec128< T, N > a, Vec128< T, N > b)
Definition emu128-inl.h:545
HWY_INLINE Vec128< T, N > Max(hwy::NonFloatTag, Vec128< T, N > a, const Vec128< T, N > b)
Definition emu128-inl.h:671
HWY_INLINE Vec128< T, N > IfThenElse(hwy::SizeTag< 1 >, Mask128< T, N > mask, Vec128< T, N > yes, Vec128< T, N > no)
Definition x86_128-inl.h:670
HWY_INLINE Vec128< T, 1 > MaxOfLanes(hwy::SizeTag< sizeof(T)>, const Vec128< T, 1 > v)
Definition arm_neon-inl.h:5068
d
Definition rvv-inl.h:1998
HWY_API Vec128< T, N > OddEvenBlocks(Vec128< T, N >, Vec128< T, N > even)
Definition arm_neon-inl.h:4697
HWY_API Vec128< T, N > DupOdd(Vec128< T, N > v)
Definition arm_neon-inl.h:4662
HWY_API bool AllTrue(const Full128< T > d, const Mask128< T > m)
Definition arm_neon-inl.h:5716
HWY_API Vec128< T > Shuffle1032(const Vec128< T > v)
Definition arm_neon-inl.h:4131
HWY_API Vec128< uint64_t, N > Min(const Vec128< uint64_t, N > a, const Vec128< uint64_t, N > b)
Definition arm_neon-inl.h:2517
HWY_API Vec128< uint64_t, N > Max(const Vec128< uint64_t, N > a, const Vec128< uint64_t, N > b)
Definition arm_neon-inl.h:2555
HWY_API Vec128< T, N > ConcatLowerUpper(const Simd< T, N, 0 > d, Vec128< T, N > hi, Vec128< T, N > lo)
Definition arm_neon-inl.h:4544
HWY_API Vec128< T, N > IfVecThenElse(Vec128< T, N > mask, Vec128< T, N > yes, Vec128< T, N > no)
Definition arm_neon-inl.h:2047
HWY_API Vec128< T, N > VecFromMask(Simd< T, N, 0 > d, const Mask128< T, N > v)
Definition arm_neon-inl.h:2223
HWY_API Vec128< T, N > SwapAdjacentBlocks(Vec128< T, N > v)
Definition arm_neon-inl.h:4704
HWY_API Vec128< T, N > Reverse2(Simd< T, N, 0 > d, const Vec128< T, N > v)
Definition arm_neon-inl.h:4061
svuint16_t Set(Simd< bfloat16_t, N, kPow2 > d, bfloat16_t arg)
Definition arm_sve-inl.h:322
HWY_API Vec128< T, N > Reverse8(Simd< T, N, 0 > d, const Vec128< T, N > v)
Definition arm_neon-inl.h:4113
HWY_API Vec128< T, N > ConcatUpperLower(Simd< T, N, 0 > d, Vec128< T, N > hi, Vec128< T, N > lo)
Definition arm_neon-inl.h:4570
HWY_API Vec128< T, N > BitCast(Simd< T, N, 0 > d, Vec128< FromT, N *sizeof(T)/sizeof(FromT)> v)
Definition arm_neon-inl.h:997
HWY_API Vec128< T, N > Zero(Simd< T, N, 0 > d)
Definition arm_neon-inl.h:1020
decltype(MaskFromVec(Zero(D()))) Mask
Definition generic_ops-inl.h:46
HWY_API Vec128< T, N > Reverse4(Simd< T, N, 0 > d, const Vec128< T, N > v)
Definition arm_neon-inl.h:4090
HWY_API Vec128< T, 1 > Reverse(Simd< T, 1, 0 >, const Vec128< T, 1 > v)
Definition arm_neon-inl.h:4030
const vfloat64m1_t v
Definition rvv-inl.h:1998
typename D::T TFromD
Definition ops/shared-inl.h:203
decltype(Zero(D())) Vec
Definition generic_ops-inl.h:40
HWY_DLLEXPORT void TypeName(const TypeInfo &info, size_t N, char *string100)
Definition aligned_allocator.h:27
HWY_API constexpr T HighestValue()
Definition base.h:684
HWY_API constexpr T LowestValue()
Definition base.h:671
#define HWY_NAMESPACE
Definition set_macros-inl.h:82
Definition traits-inl.h:506
T LaneType
Definition traits-inl.h:510
constexpr size_t LanesPerKey() const
Definition traits-inl.h:508
T KeyType
Definition traits-inl.h:511
constexpr bool Is128() const
Definition traits-inl.h:507
std::string KeyString() const
Definition traits-inl.h:513
Definition traits-inl.h:521
HWY_INLINE bool Compare1(const T *a, const T *b)
Definition traits-inl.h:524
HWY_INLINE Mask< D > Compare(D, Vec< D > a, Vec< D > b)
Definition traits-inl.h:527
SortAscending Order
Definition traits-inl.h:522
Definition traits-inl.h:533
HWY_INLINE bool Compare1(const T *a, const T *b)
Definition traits-inl.h:536
HWY_INLINE Mask< D > Compare(D, Vec< D > a, Vec< D > b)
Definition traits-inl.h:539
SortDescending Order
Definition traits-inl.h:534
Definition traits-inl.h:545
HWY_INLINE void Swap(T *a, T *b) const
Definition traits-inl.h:548
HWY_INLINE Vec< D > SetKey(D d, const TFromD< D > *key) const
Definition traits-inl.h:555
static constexpr size_t kMaxCols
Definition contrib/sort/shared-inl.h:34