1#include <cfloat>
2#include <limits.h>
3#include <cstring> // strlen() on Solaris
4
5#include "duckdb/execution/index/art/art_key.hpp"
6#include "duckdb/execution/index/art/art.hpp"
7
8using namespace duckdb;
9
10//! these are optimized and assume a particular byte order
11#define BSWAP16(x) ((uint16_t)((((uint16_t)(x)&0xff00) >> 8) | (((uint16_t)(x)&0x00ff) << 8)))
12
13#define BSWAP32(x) \
14 ((uint32_t)((((uint32_t)(x)&0xff000000) >> 24) | (((uint32_t)(x)&0x00ff0000) >> 8) | \
15 (((uint32_t)(x)&0x0000ff00) << 8) | (((uint32_t)(x)&0x000000ff) << 24)))
16
17#define BSWAP64(x) \
18 ((uint64_t)((((uint64_t)(x)&0xff00000000000000ull) >> 56) | (((uint64_t)(x)&0x00ff000000000000ull) >> 40) | \
19 (((uint64_t)(x)&0x0000ff0000000000ull) >> 24) | (((uint64_t)(x)&0x000000ff00000000ull) >> 8) | \
20 (((uint64_t)(x)&0x00000000ff000000ull) << 8) | (((uint64_t)(x)&0x0000000000ff0000ull) << 24) | \
21 (((uint64_t)(x)&0x000000000000ff00ull) << 40) | (((uint64_t)(x)&0x00000000000000ffull) << 56)))
22
23static uint8_t FlipSign(uint8_t key_byte) {
24 return key_byte ^ 128;
25}
26
27uint32_t Key::EncodeFloat(float x) {
28 unsigned long buff;
29
30 //! zero
31 if (x == 0) {
32 buff = 0;
33 buff |= (1u << 31);
34 return buff;
35 }
36 //! infinity
37 if (x > FLT_MAX) {
38 return UINT_MAX;
39 }
40 //! -infinity
41 if (x < -FLT_MAX) {
42 return 0;
43 }
44 buff = reinterpret_cast<uint32_t *>(&x)[0];
45 if ((buff & (1u << 31)) == 0) { //! +0 and positive numbers
46 buff |= (1u << 31);
47 } else { //! negative numbers
48 buff = ~buff; //! complement 1
49 }
50
51 return buff;
52}
53
54uint64_t Key::EncodeDouble(double x) {
55 uint64_t buff;
56 //! zero
57 if (x == 0) {
58 buff = 0;
59 buff += (1ull << 63);
60 return buff;
61 }
62 //! infinity
63 if (x > DBL_MAX) {
64 return ULLONG_MAX;
65 }
66 //! -infinity
67 if (x < -DBL_MAX) {
68 return 0;
69 }
70 buff = reinterpret_cast<uint64_t *>(&x)[0];
71 if (buff < (1ull << 63)) { //! +0 and positive numbers
72 buff += (1ull << 63);
73 } else { //! negative numbers
74 buff = ~buff; //! complement 1
75 }
76 return buff;
77}
78
79Key::Key(unique_ptr<data_t[]> data, idx_t len) : len(len), data(move(data)) {
80}
81
82template <> unique_ptr<data_t[]> Key::CreateData(bool value, bool is_little_endian) {
83 auto data = unique_ptr<data_t[]>(new data_t[sizeof(value)]);
84 data[0] = value ? 1 : 0;
85 return data;
86}
87
88template <> unique_ptr<data_t[]> Key::CreateData(int8_t value, bool is_little_endian) {
89 auto data = unique_ptr<data_t[]>(new data_t[sizeof(value)]);
90 reinterpret_cast<uint8_t *>(data.get())[0] = value;
91 data[0] = FlipSign(data[0]);
92 return data;
93}
94
95template <> unique_ptr<data_t[]> Key::CreateData(int16_t value, bool is_little_endian) {
96 auto data = unique_ptr<data_t[]>(new data_t[sizeof(value)]);
97 reinterpret_cast<uint16_t *>(data.get())[0] = is_little_endian ? BSWAP16(value) : value;
98 data[0] = FlipSign(data[0]);
99 return data;
100}
101
102template <> unique_ptr<data_t[]> Key::CreateData(int32_t value, bool is_little_endian) {
103 auto data = unique_ptr<data_t[]>(new data_t[sizeof(value)]);
104 reinterpret_cast<uint32_t *>(data.get())[0] = is_little_endian ? BSWAP32(value) : value;
105 data[0] = FlipSign(data[0]);
106 return data;
107}
108
109template <> unique_ptr<data_t[]> Key::CreateData(int64_t value, bool is_little_endian) {
110 auto data = unique_ptr<data_t[]>(new data_t[sizeof(value)]);
111 reinterpret_cast<uint64_t *>(data.get())[0] = is_little_endian ? BSWAP64(value) : value;
112 data[0] = FlipSign(data[0]);
113 return data;
114}
115
116template <> unique_ptr<data_t[]> Key::CreateData(float value, bool is_little_endian) {
117 uint32_t converted_value = EncodeFloat(value);
118 auto data = unique_ptr<data_t[]>(new data_t[sizeof(converted_value)]);
119 reinterpret_cast<uint32_t *>(data.get())[0] = is_little_endian ? BSWAP32(converted_value) : converted_value;
120 return data;
121}
122template <> unique_ptr<data_t[]> Key::CreateData(double value, bool is_little_endian) {
123 uint64_t converted_value = EncodeDouble(value);
124 auto data = unique_ptr<data_t[]>(new data_t[sizeof(converted_value)]);
125 reinterpret_cast<uint64_t *>(data.get())[0] = is_little_endian ? BSWAP64(converted_value) : converted_value;
126 return data;
127}
128
129template <> unique_ptr<Key> Key::CreateKey(string_t value, bool is_little_endian) {
130 idx_t len = value.GetSize() + 1;
131 auto data = unique_ptr<data_t[]>(new data_t[len]);
132 memcpy(data.get(), value.GetData(), len);
133 return make_unique<Key>(move(data), len);
134}
135
136template <> unique_ptr<Key> Key::CreateKey(const char *value, bool is_little_endian) {
137 return Key::CreateKey(string_t(value, strlen(value)), is_little_endian);
138}
139
140bool Key::operator>(const Key &k) const {
141 for (idx_t i = 0; i < std::min(len, k.len); i++) {
142 if (data[i] > k.data[i]) {
143 return true;
144 } else if (data[i] < k.data[i]) {
145 return false;
146 }
147 }
148 return len > k.len;
149}
150
151bool Key::operator<(const Key &k) const {
152 for (idx_t i = 0; i < std::min(len, k.len); i++) {
153 if (data[i] < k.data[i]) {
154 return true;
155 } else if (data[i] > k.data[i]) {
156 return false;
157 }
158 }
159 return len < k.len;
160}
161
162bool Key::operator>=(const Key &k) const {
163 for (idx_t i = 0; i < std::min(len, k.len); i++) {
164 if (data[i] > k.data[i]) {
165 return true;
166 } else if (data[i] < k.data[i]) {
167 return false;
168 }
169 }
170 return len >= k.len;
171}
172
173bool Key::operator==(const Key &k) const {
174 if (len != k.len) {
175 return false;
176 }
177 for (idx_t i = 0; i < len; i++) {
178 if (data[i] != k.data[i]) {
179 return false;
180 }
181 }
182 return true;
183}
184