1#pragma once
2
3#include <cmath>
4#include <Columns/IColumn.h>
5#include <Columns/IColumnImpl.h>
6#include <Columns/ColumnVectorHelper.h>
7#include <common/unaligned.h>
8#include <Core/Field.h>
9
10
11namespace DB
12{
13
14/** Stuff for comparing numbers.
15 * Integer values are compared as usual.
16 * Floating-point numbers are compared this way that NaNs always end up at the end
17 * (if you don't do this, the sort would not work at all).
18 */
19template <typename T>
20struct CompareHelper
21{
22 static bool less(T a, T b, int /*nan_direction_hint*/) { return a < b; }
23 static bool greater(T a, T b, int /*nan_direction_hint*/) { return a > b; }
24
25 /** Compares two numbers. Returns a number less than zero, equal to zero, or greater than zero if a < b, a == b, a > b, respectively.
26 * If one of the values is NaN, then
27 * - if nan_direction_hint == -1 - NaN are considered less than all numbers;
28 * - if nan_direction_hint == 1 - NaN are considered to be larger than all numbers;
29 * Essentially: nan_direction_hint == -1 says that the comparison is for sorting in descending order.
30 */
31 static int compare(T a, T b, int /*nan_direction_hint*/)
32 {
33 return a > b ? 1 : (a < b ? -1 : 0);
34 }
35};
36
37template <typename T>
38struct FloatCompareHelper
39{
40 static bool less(T a, T b, int nan_direction_hint)
41 {
42 bool isnan_a = std::isnan(a);
43 bool isnan_b = std::isnan(b);
44
45 if (isnan_a && isnan_b)
46 return false;
47 if (isnan_a)
48 return nan_direction_hint < 0;
49 if (isnan_b)
50 return nan_direction_hint > 0;
51
52 return a < b;
53 }
54
55 static bool greater(T a, T b, int nan_direction_hint)
56 {
57 bool isnan_a = std::isnan(a);
58 bool isnan_b = std::isnan(b);
59
60 if (isnan_a && isnan_b)
61 return false;
62 if (isnan_a)
63 return nan_direction_hint > 0;
64 if (isnan_b)
65 return nan_direction_hint < 0;
66
67 return a > b;
68 }
69
70 static int compare(T a, T b, int nan_direction_hint)
71 {
72 bool isnan_a = std::isnan(a);
73 bool isnan_b = std::isnan(b);
74 if (unlikely(isnan_a || isnan_b))
75 {
76 if (isnan_a && isnan_b)
77 return 0;
78
79 return isnan_a
80 ? nan_direction_hint
81 : -nan_direction_hint;
82 }
83
84 return (T(0) < (a - b)) - ((a - b) < T(0));
85 }
86};
87
88template <> struct CompareHelper<Float32> : public FloatCompareHelper<Float32> {};
89template <> struct CompareHelper<Float64> : public FloatCompareHelper<Float64> {};
90
91
92/** A template for columns that use a simple array to store.
93 */
94template <typename T>
95class ColumnVector final : public COWHelper<ColumnVectorHelper, ColumnVector<T>>
96{
97 static_assert(!IsDecimalNumber<T>);
98
99private:
100 using Self = ColumnVector;
101 friend class COWHelper<ColumnVectorHelper, Self>;
102
103 struct less;
104 struct greater;
105
106public:
107 using ValueType = T;
108 using Container = PaddedPODArray<ValueType>;
109
110private:
111 ColumnVector() {}
112 ColumnVector(const size_t n) : data(n) {}
113 ColumnVector(const size_t n, const ValueType x) : data(n, x) {}
114 ColumnVector(const ColumnVector & src) : data(src.data.begin(), src.data.end()) {}
115
116 /// Sugar constructor.
117 ColumnVector(std::initializer_list<T> il) : data{il} {}
118
119public:
120 bool isNumeric() const override { return IsNumber<T>; }
121
122 size_t size() const override
123 {
124 return data.size();
125 }
126
127 StringRef getDataAt(size_t n) const override
128 {
129 return StringRef(reinterpret_cast<const char *>(&data[n]), sizeof(data[n]));
130 }
131
132 void insertFrom(const IColumn & src, size_t n) override
133 {
134 data.push_back(static_cast<const Self &>(src).getData()[n]);
135 }
136
137 void insertData(const char * pos, size_t /*length*/) override
138 {
139 data.push_back(unalignedLoad<T>(pos));
140 }
141
142 void insertDefault() override
143 {
144 data.push_back(T());
145 }
146
147 virtual void insertManyDefaults(size_t length) override
148 {
149 data.resize_fill(data.size() + length, T());
150 }
151
152 void popBack(size_t n) override
153 {
154 data.resize_assume_reserved(data.size() - n);
155 }
156
157 StringRef serializeValueIntoArena(size_t n, Arena & arena, char const *& begin) const override;
158
159 const char * deserializeAndInsertFromArena(const char * pos) override;
160
161 void updateHashWithValue(size_t n, SipHash & hash) const override;
162
163 size_t byteSize() const override
164 {
165 return data.size() * sizeof(data[0]);
166 }
167
168 size_t allocatedBytes() const override
169 {
170 return data.allocated_bytes();
171 }
172
173 void protect() override
174 {
175 data.protect();
176 }
177
178 void insertValue(const T value)
179 {
180 data.push_back(value);
181 }
182
183 /// This method implemented in header because it could be possibly devirtualized.
184 int compareAt(size_t n, size_t m, const IColumn & rhs_, int nan_direction_hint) const override
185 {
186 return CompareHelper<T>::compare(data[n], static_cast<const Self &>(rhs_).data[m], nan_direction_hint);
187 }
188
189 void getPermutation(bool reverse, size_t limit, int nan_direction_hint, IColumn::Permutation & res) const override;
190
191 void reserve(size_t n) override
192 {
193 data.reserve(n);
194 }
195
196 const char * getFamilyName() const override;
197
198 MutableColumnPtr cloneResized(size_t size) const override;
199
200 Field operator[](size_t n) const override
201 {
202 return data[n];
203 }
204
205 void get(size_t n, Field & res) const override
206 {
207 res = (*this)[n];
208 }
209
210 UInt64 get64(size_t n) const override;
211
212 Float64 getFloat64(size_t n) const override;
213 Float32 getFloat32(size_t n) const override;
214
215 /// Out of range conversion is permitted.
216 UInt64 NO_SANITIZE_UNDEFINED getUInt(size_t n) const override
217 {
218 return UInt64(data[n]);
219 }
220
221 /// Out of range conversion is permitted.
222 Int64 NO_SANITIZE_UNDEFINED getInt(size_t n) const override
223 {
224 return Int64(data[n]);
225 }
226
227 bool getBool(size_t n) const override
228 {
229 return bool(data[n]);
230 }
231
232 void insert(const Field & x) override
233 {
234 data.push_back(DB::get<NearestFieldType<T>>(x));
235 }
236
237 void insertRangeFrom(const IColumn & src, size_t start, size_t length) override;
238
239 ColumnPtr filter(const IColumn::Filter & filt, ssize_t result_size_hint) const override;
240
241 ColumnPtr permute(const IColumn::Permutation & perm, size_t limit) const override;
242
243 ColumnPtr index(const IColumn & indexes, size_t limit) const override;
244
245 template <typename Type>
246 ColumnPtr indexImpl(const PaddedPODArray<Type> & indexes, size_t limit) const;
247
248 ColumnPtr replicate(const IColumn::Offsets & offsets) const override;
249
250 void getExtremes(Field & min, Field & max) const override;
251
252 MutableColumns scatter(IColumn::ColumnIndex num_columns, const IColumn::Selector & selector) const override
253 {
254 return this->template scatterImpl<Self>(num_columns, selector);
255 }
256
257 void gather(ColumnGathererStream & gatherer_stream) override;
258
259
260 bool canBeInsideNullable() const override { return true; }
261
262 bool isFixedAndContiguous() const override { return true; }
263 size_t sizeOfValueIfFixed() const override { return sizeof(T); }
264 StringRef getRawData() const override { return StringRef(reinterpret_cast<const char*>(data.data()), data.size()); }
265
266
267 bool structureEquals(const IColumn & rhs) const override
268 {
269 return typeid(rhs) == typeid(ColumnVector<T>);
270 }
271
272 /** More efficient methods of manipulation - to manipulate with data directly. */
273 Container & getData()
274 {
275 return data;
276 }
277
278 const Container & getData() const
279 {
280 return data;
281 }
282
283 const T & getElement(size_t n) const
284 {
285 return data[n];
286 }
287
288 T & getElement(size_t n)
289 {
290 return data[n];
291 }
292
293protected:
294 Container data;
295};
296
297template <typename T>
298template <typename Type>
299ColumnPtr ColumnVector<T>::indexImpl(const PaddedPODArray<Type> & indexes, size_t limit) const
300{
301 size_t size = indexes.size();
302
303 if (limit == 0)
304 limit = size;
305 else
306 limit = std::min(size, limit);
307
308 auto res = this->create(limit);
309 typename Self::Container & res_data = res->getData();
310 for (size_t i = 0; i < limit; ++i)
311 res_data[i] = data[indexes[i]];
312
313 return res;
314}
315
316}
317