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