1 // Copyright 2022 Google LLC 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 // Interface to vectorized quicksort with dynamic dispatch. 16 17 #ifndef HIGHWAY_HWY_CONTRIB_SORT_VQSORT_H_ 18 #define HIGHWAY_HWY_CONTRIB_SORT_VQSORT_H_ 19 20 #include "hwy/base.h" 21 22 namespace hwy { 23 24 // Aligned 128-bit type. Cannot use __int128 because clang doesn't yet align it: 25 // https://reviews.llvm.org/D86310 26 #pragma pack(push, 1) 27 struct alignas(16) uint128_t { 28 uint64_t lo; // little-endian layout 29 uint64_t hi; 30 }; 31 #pragma pack(pop) 32 33 // Tag arguments that determine the sort order. 34 struct SortAscending { IsAscendingSortAscending35 constexpr bool IsAscending() const { return true; } 36 }; 37 struct SortDescending { IsAscendingSortDescending38 constexpr bool IsAscending() const { return false; } 39 }; 40 41 // Allocates O(1) space. Type-erased RAII wrapper over hwy/aligned_allocator.h. 42 // This allows amortizing the allocation over multiple sorts. 43 class HWY_CONTRIB_DLLEXPORT Sorter { 44 public: 45 Sorter(); ~Sorter()46 ~Sorter() { Delete(); } 47 48 // Move-only 49 Sorter(const Sorter&) = delete; 50 Sorter& operator=(const Sorter&) = delete; Sorter(Sorter && other)51 Sorter(Sorter&& other) { 52 Delete(); 53 ptr_ = other.ptr_; 54 other.ptr_ = nullptr; 55 } 56 Sorter& operator=(Sorter&& other) { 57 Delete(); 58 ptr_ = other.ptr_; 59 other.ptr_ = nullptr; 60 return *this; 61 } 62 63 // Sorts keys[0, n). Dispatches to the best available instruction set, 64 // and does not allocate memory. 65 void operator()(uint16_t* HWY_RESTRICT keys, size_t n, SortAscending) const; 66 void operator()(uint16_t* HWY_RESTRICT keys, size_t n, SortDescending) const; 67 void operator()(uint32_t* HWY_RESTRICT keys, size_t n, SortAscending) const; 68 void operator()(uint32_t* HWY_RESTRICT keys, size_t n, SortDescending) const; 69 void operator()(uint64_t* HWY_RESTRICT keys, size_t n, SortAscending) const; 70 void operator()(uint64_t* HWY_RESTRICT keys, size_t n, SortDescending) const; 71 72 void operator()(int16_t* HWY_RESTRICT keys, size_t n, SortAscending) const; 73 void operator()(int16_t* HWY_RESTRICT keys, size_t n, SortDescending) const; 74 void operator()(int32_t* HWY_RESTRICT keys, size_t n, SortAscending) const; 75 void operator()(int32_t* HWY_RESTRICT keys, size_t n, SortDescending) const; 76 void operator()(int64_t* HWY_RESTRICT keys, size_t n, SortAscending) const; 77 void operator()(int64_t* HWY_RESTRICT keys, size_t n, SortDescending) const; 78 79 void operator()(float* HWY_RESTRICT keys, size_t n, SortAscending) const; 80 void operator()(float* HWY_RESTRICT keys, size_t n, SortDescending) const; 81 void operator()(double* HWY_RESTRICT keys, size_t n, SortAscending) const; 82 void operator()(double* HWY_RESTRICT keys, size_t n, SortDescending) const; 83 84 void operator()(uint128_t* HWY_RESTRICT keys, size_t n, SortAscending) const; 85 void operator()(uint128_t* HWY_RESTRICT keys, size_t n, SortDescending) const; 86 87 // For internal use only 88 static void Fill24Bytes(const void* seed_heap, size_t seed_num, void* bytes); 89 static bool HaveFloat64(); 90 91 private: 92 void Delete(); 93 94 template <typename T> Get()95 T* Get() const { 96 return static_cast<T*>(ptr_); 97 } 98 99 void* ptr_ = nullptr; 100 }; 101 102 } // namespace hwy 103 104 #endif // HIGHWAY_HWY_CONTRIB_SORT_VQSORT_H_ 105