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