/Users/deen/code/yugabyte-db/src/yb/util/slice.h
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
2 | | // Use of this source code is governed by a BSD-style license that can be |
3 | | // found in the LICENSE file. See the AUTHORS file for names of contributors. |
4 | | // |
5 | | // The following only applies to changes made to this file as part of YugaByte development. |
6 | | // |
7 | | // Portions Copyright (c) YugaByte, Inc. |
8 | | // |
9 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
10 | | // in compliance with the License. You may obtain a copy of the License at |
11 | | // |
12 | | // http://www.apache.org/licenses/LICENSE-2.0 |
13 | | // |
14 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
15 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
16 | | // or implied. See the License for the specific language governing permissions and limitations |
17 | | // under the License. |
18 | | // |
19 | | // Slice is a simple structure containing a pointer into some external |
20 | | // storage and a size. The user of a Slice must ensure that the slice |
21 | | // is not used after the corresponding external storage has been |
22 | | // deallocated. |
23 | | // |
24 | | // Multiple threads can invoke const methods on a Slice without |
25 | | // external synchronization, but if any of the threads may call a |
26 | | // non-const method, all threads accessing the same Slice must use |
27 | | // external synchronization. |
28 | | // |
29 | | // Slices can be built around faststrings and GStringPieces using constructors |
30 | | // with implicit casts. Both GStringPieces and faststrings depend on a great |
31 | | // deal of gutil code, so these constructors are conditionalized on |
32 | | // YB_HEADERS_USE_RICH_SLICE. Likewise, YB_HEADERS_USE_RICH_SLICE controls |
33 | | // whether to use gutil-based memeq/memcmp substitutes; if it is unset, Slice |
34 | | // will fall back to standard memcmp. |
35 | | |
36 | | #ifndef YB_UTIL_SLICE_H_ |
37 | | #define YB_UTIL_SLICE_H_ |
38 | | |
39 | | #include <string> |
40 | | |
41 | | #include "yb/gutil/strings/fastmem.h" |
42 | | #include "yb/gutil/strings/stringpiece.h" |
43 | | |
44 | | #include "yb/util/cast.h" |
45 | | #include "yb/util/faststring.h" |
46 | | #include "yb/util/status_fwd.h" |
47 | | |
48 | | namespace yb { |
49 | | |
50 | | struct SliceParts; |
51 | | |
52 | | class Slice { |
53 | | public: |
54 | | // Create an empty slice. |
55 | 5.54G | Slice() : begin_(to_uchar_ptr("")), end_(begin_) { } |
56 | | |
57 | | // Create a slice that refers to d[0,n-1]. |
58 | 147G | Slice(const uint8_t* d, size_t n) : begin_(d), end_(d + n) {} |
59 | | // Create a slice that refers to d[0,n-1]. |
60 | 80.6G | Slice(const char* d, size_t n) : Slice(to_uchar_ptr(d), n) {} Unexecuted instantiation: yb::Slice::Slice(char const*, unsigned long) yb::Slice::Slice(char const*, unsigned long) Line | Count | Source | 60 | 80.6G | Slice(const char* d, size_t n) : Slice(to_uchar_ptr(d), n) {} |
|
61 | | |
62 | | // Create a slice that refers to [begin, end). |
63 | 1.45G | Slice(const uint8_t* begin, const uint8_t* end) : begin_(begin), end_(end) {} |
64 | | |
65 | | template<size_t N> |
66 | 451 | explicit Slice(const std::array<char, N>& arr) : Slice(arr.data(), N) {} yb::Slice::Slice<18ul>(std::__1::array<char, 18ul> const&) Line | Count | Source | 66 | 28 | explicit Slice(const std::array<char, N>& arr) : Slice(arr.data(), N) {} |
yb::Slice::Slice<1ul>(std::__1::array<char, 1ul> const&) Line | Count | Source | 66 | 423 | explicit Slice(const std::array<char, N>& arr) : Slice(arr.data(), N) {} |
|
67 | | |
68 | | template<size_t N> |
69 | 11.6k | explicit Slice(const std::array<unsigned char, N>& arr) : Slice(arr.data(), N) {} |
70 | | |
71 | | Slice(const char* begin, const char* end) |
72 | 1.16G | : Slice(to_uchar_ptr(begin), to_uchar_ptr(end)) {} Unexecuted instantiation: yb::Slice::Slice(char const*, char const*) yb::Slice::Slice(char const*, char const*) Line | Count | Source | 72 | 1.16G | : Slice(to_uchar_ptr(begin), to_uchar_ptr(end)) {} |
|
73 | | |
74 | | // Create a slice that refers to the contents of "s" |
75 | | template <class CharTraits, class Allocator> |
76 | | Slice(const std::basic_string<char, CharTraits, Allocator>& s) // NOLINT(runtime/explicit) |
77 | 3.73G | : Slice(to_uchar_ptr(s.data()), s.size()) {} yb::Slice::Slice<std::__1::char_traits<char>, std::__1::allocator<char> >(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&) Line | Count | Source | 77 | 3.72G | : Slice(to_uchar_ptr(s.data()), s.size()) {} |
yb::Slice::Slice<std::__1::char_traits<char>, yb::internal::ArenaAllocatorBase<char, yb::internal::ArenaTraits> >(std::__1::basic_string<char, std::__1::char_traits<char>, yb::internal::ArenaAllocatorBase<char, yb::internal::ArenaTraits> > const&) Line | Count | Source | 77 | 7.48M | : Slice(to_uchar_ptr(s.data()), s.size()) {} |
|
78 | | |
79 | | // Create a slice that refers to s[0,strlen(s)-1] |
80 | | Slice(const char* s) // NOLINT(runtime/explicit) |
81 | 4.23G | : Slice(to_uchar_ptr(s), strlen(s)) {} Unexecuted instantiation: yb::Slice::Slice(char const*) yb::Slice::Slice(char const*) Line | Count | Source | 81 | 4.23G | : Slice(to_uchar_ptr(s), strlen(s)) {} |
|
82 | | |
83 | | // Create a slice that refers to the contents of the faststring. |
84 | | // Note that further appends to the faststring may invalidate this slice. |
85 | | Slice(const faststring &s) // NOLINT(runtime/explicit) |
86 | 48.0M | : Slice(s.data(), s.size()) {} Unexecuted instantiation: yb::Slice::Slice(yb::faststring const&) yb::Slice::Slice(yb::faststring const&) Line | Count | Source | 86 | 48.0M | : Slice(s.data(), s.size()) {} |
|
87 | | |
88 | | Slice(const GStringPiece& s) // NOLINT(runtime/explicit) |
89 | 1.01k | : Slice(to_uchar_ptr(s.data()), s.size()) {} Unexecuted instantiation: yb::Slice::Slice(GStringPiece const&) yb::Slice::Slice(GStringPiece const&) Line | Count | Source | 89 | 1.01k | : Slice(to_uchar_ptr(s.data()), s.size()) {} |
|
90 | | |
91 | | // Create a single slice from SliceParts using buf as storage. |
92 | | // buf must exist as long as the returned Slice exists. |
93 | | Slice(const SliceParts& parts, std::string* buf); |
94 | | |
95 | 11.4G | const char* cdata() const { return to_char_ptr(begin_); } |
96 | | |
97 | | // Return a pointer to the beginning of the referenced data |
98 | 86.5G | const uint8_t* data() const { return begin_; } |
99 | | |
100 | | // Return a mutable pointer to the beginning of the referenced data. |
101 | 358k | uint8_t *mutable_data() { return const_cast<uint8_t*>(begin_); } |
102 | | |
103 | 4.68G | const uint8_t* end() const { return end_; } |
104 | | |
105 | 2.54G | const char* cend() const { return to_char_ptr(end_); } |
106 | | |
107 | | // Return the length (in bytes) of the referenced data |
108 | 241G | size_t size() const { return end_ - begin_; } |
109 | | |
110 | | // Return true iff the length of the referenced data is zero |
111 | 27.8G | bool empty() const { return begin_ == end_; } |
112 | | |
113 | | template <class... Args> |
114 | 242 | bool GreaterOrEqual(const Slice& arg0, Args&&... args) const { |
115 | 242 | return !Less(arg0, std::forward<Args>(args)...); |
116 | 242 | } bool yb::Slice::GreaterOrEqual<>(yb::Slice const&) const Line | Count | Source | 114 | 242 | bool GreaterOrEqual(const Slice& arg0, Args&&... args) const { | 115 | 242 | return !Less(arg0, std::forward<Args>(args)...); | 116 | 242 | } |
Unexecuted instantiation: bool yb::Slice::GreaterOrEqual<yb::Slice const&>(yb::Slice const&, yb::Slice const&) const |
117 | | |
118 | | template <class... Args> |
119 | 3.06M | bool Less(const Slice& arg0, Args&&... args) const { |
120 | 3.06M | return DoLess(arg0, std::forward<Args>(args)...); |
121 | 3.06M | } bool yb::Slice::Less<>(yb::Slice const&) const Line | Count | Source | 119 | 3.06M | bool Less(const Slice& arg0, Args&&... args) const { | 120 | 3.06M | return DoLess(arg0, std::forward<Args>(args)...); | 121 | 3.06M | } |
Unexecuted instantiation: bool yb::Slice::Less<yb::Slice const&>(yb::Slice const&, yb::Slice const&) const |
122 | | |
123 | | // Return the ith byte in the referenced data. |
124 | | // REQUIRES: n < size() |
125 | | uint8_t operator[](size_t n) const; |
126 | | |
127 | | // Change this slice to refer to an empty array |
128 | 43.2M | void clear() { |
129 | 43.2M | begin_ = to_uchar_ptr(""); |
130 | 43.2M | end_ = begin_; |
131 | 43.2M | } |
132 | | |
133 | | // Drop the first "n" bytes from this slice. |
134 | | void remove_prefix(size_t n); |
135 | | |
136 | | Slice Prefix(size_t n) const; |
137 | | |
138 | | Slice WithoutPrefix(size_t n) const; |
139 | | |
140 | | // Drop the last "n" bytes from this slice. |
141 | | void remove_suffix(size_t n); |
142 | | |
143 | | Slice Suffix(size_t n) const; |
144 | | |
145 | | Slice WithoutSuffix(size_t n) const; |
146 | | |
147 | 56.2M | void CopyTo(void* buffer) const { |
148 | 56.2M | memcpy(buffer, begin_, size()); |
149 | 56.2M | } |
150 | | |
151 | | // Truncate the slice to "n" bytes |
152 | | void truncate(size_t n); |
153 | | |
154 | | char consume_byte(); |
155 | | |
156 | 5.17G | bool TryConsumeByte(char c) { |
157 | 5.17G | if (empty()5.17G || *begin_ != c) { |
158 | 4.62G | return false; |
159 | 4.62G | } |
160 | 545M | ++begin_; |
161 | 545M | return true; |
162 | 5.17G | } |
163 | | |
164 | 1.86M | char FirstByteOr(char def) { |
165 | 1.86M | return !empty() ? *begin_ : def0 ; |
166 | 1.86M | } |
167 | | |
168 | | MUST_USE_RESULT Status consume_byte(char c); |
169 | | |
170 | | // Checks that this slice has size() = 'expected_size' and returns |
171 | | // STATUS(Corruption, ) otherwise. |
172 | | Status check_size(size_t expected_size) const; |
173 | | |
174 | | // Compare two slices and returns the offset of the first byte where they differ. |
175 | | size_t difference_offset(const Slice& b) const; |
176 | | |
177 | | void CopyToBuffer(std::string* buffer) const; |
178 | | |
179 | | // Return a string that contains the copy of the referenced data. |
180 | | std::string ToBuffer() const; |
181 | | |
182 | 155M | std::string ToString() const __attribute__ ((deprecated)) { return ToBuffer(); } |
183 | | std::string ToString(bool hex) const __attribute__ ((deprecated)); |
184 | | |
185 | | std::string ToDebugString(size_t max_len = 0) const; |
186 | | std::string ToDebugHexString() const; |
187 | | |
188 | | // Three-way comparison. Returns value: |
189 | | // < 0 iff "*this" < "b", |
190 | | // == 0 iff "*this" == "b", |
191 | | // > 0 iff "*this" > "b" |
192 | | int compare(const Slice& b) const; |
193 | | int compare_prefix(const Slice& b) const; |
194 | | |
195 | | size_t hash() const noexcept; |
196 | | |
197 | | // Return true iff "x" is a prefix of "*this" |
198 | 1.58G | bool starts_with(const Slice& x) const { |
199 | 1.58G | return starts_with(x.data(), x.size()); |
200 | 1.58G | } |
201 | | |
202 | 1.58G | bool starts_with(const uint8_t* data, size_t size) const { |
203 | 1.58G | return (this->size() >= size) && MemEqual(begin_, data, size)1.55G ; |
204 | 1.58G | } |
205 | | |
206 | 609k | bool starts_with(const char* data, size_t size) const { |
207 | 609k | return (this->size() >= size) && MemEqual(begin_, data, size)609k ; |
208 | 609k | } |
209 | | |
210 | 125M | bool starts_with(char c) const { |
211 | 125M | return (size() >= 1) && (*begin_ == c)125M ; |
212 | 125M | } |
213 | | |
214 | 4.99M | bool ends_with(const Slice& x) const { |
215 | 4.99M | size_t xsize = x.size(); |
216 | 4.99M | return (size() >= xsize) && MemEqual(end_ - xsize, x.begin_, xsize)4.99M ; |
217 | 4.99M | } |
218 | | |
219 | 846M | bool ends_with(char c) const { |
220 | 846M | return (size() >= 1) && *(end_ - 1) == c846M ; |
221 | 846M | } |
222 | | |
223 | | // Comparator struct, useful for ordered collections (like STL maps). |
224 | | struct Comparator { |
225 | 45.9k | bool operator()(const Slice& a, const Slice& b) const { |
226 | 45.9k | return a.compare(b) < 0; |
227 | 45.9k | } |
228 | | }; |
229 | | |
230 | | struct Hash { |
231 | 1.74M | size_t operator()(const Slice& a) const noexcept { |
232 | 1.74M | return a.hash(); |
233 | 1.74M | } |
234 | | }; |
235 | | |
236 | | // Relocates this slice's data into 'd' provided this isn't already the |
237 | | // case. It is assumed that 'd' is large enough to fit the data. |
238 | 7 | void relocate(uint8_t* d) { |
239 | 7 | if (begin_ != d) { |
240 | 6 | size_t size = end_ - begin_; |
241 | 6 | memcpy(d, begin_, size); |
242 | 6 | begin_ = d; |
243 | 6 | end_ = d + size; |
244 | 6 | } |
245 | 7 | } |
246 | | |
247 | 757k | size_t DynamicMemoryUsage() const { return 0; } |
248 | | |
249 | | // Return a Slice representing bytes for any type which is laid out contiguously in memory. |
250 | | template<class T, class = typename std::enable_if<std::is_pod<T>::value, void>::type> |
251 | 64.6M | static Slice FromPod(const T* data) { |
252 | 64.6M | return Slice(pointer_cast<const char*>(data), sizeof(*data)); |
253 | 64.6M | } |
254 | | |
255 | | private: |
256 | | friend bool operator==(const Slice& x, const Slice& y); |
257 | | |
258 | 1.24k | bool DoLess() const { |
259 | 1.24k | return !empty(); |
260 | 1.24k | } |
261 | | |
262 | | template <class... Args> |
263 | 3.05M | bool DoLess(const Slice& arg0, Args&&... args) const { |
264 | 3.05M | auto arg0_size = arg0.size(); |
265 | 3.05M | if (size() < arg0_size) { |
266 | 3.05M | return compare(arg0) < 0; |
267 | 3.05M | } |
268 | | |
269 | 1.01k | int cmp = Slice(begin_, arg0_size).compare(arg0); |
270 | 1.56k | if (cmp != 01.01k ) { |
271 | 1.56k | return cmp < 0; |
272 | 1.56k | } |
273 | | |
274 | 18.4E | return Slice(begin_ + arg0_size, end_).DoLess(std::forward<Args>(args)...); |
275 | 1.01k | } bool yb::Slice::DoLess<>(yb::Slice const&) const Line | Count | Source | 263 | 3.05M | bool DoLess(const Slice& arg0, Args&&... args) const { | 264 | 3.05M | auto arg0_size = arg0.size(); | 265 | 3.05M | if (size() < arg0_size) { | 266 | 3.05M | return compare(arg0) < 0; | 267 | 3.05M | } | 268 | | | 269 | 1.01k | int cmp = Slice(begin_, arg0_size).compare(arg0); | 270 | 1.56k | if (cmp != 01.01k ) { | 271 | 1.56k | return cmp < 0; | 272 | 1.56k | } | 273 | | | 274 | 18.4E | return Slice(begin_ + arg0_size, end_).DoLess(std::forward<Args>(args)...); | 275 | 1.01k | } |
Unexecuted instantiation: bool yb::Slice::DoLess<yb::Slice const&>(yb::Slice const&, yb::Slice const&) const |
276 | | |
277 | 3.25G | static bool MemEqual(const void* a, const void* b, size_t n) { |
278 | 3.25G | return strings::memeq(a, b, n); |
279 | 3.25G | } |
280 | | |
281 | 36.2G | static int MemCompare(const void* a, const void* b, size_t n) { |
282 | 36.2G | return strings::fastmemcmp_inlined(a, b, n); |
283 | 36.2G | } |
284 | | |
285 | | const uint8_t* begin_; |
286 | | const uint8_t* end_; |
287 | | |
288 | | // Intentionally copyable |
289 | | }; |
290 | | |
291 | | struct SliceParts { |
292 | | SliceParts(const Slice* _parts, int _num_parts) : |
293 | 383M | parts(_parts), num_parts(_num_parts) { } |
294 | 9.90M | SliceParts() : parts(nullptr), num_parts(0) {} |
295 | | |
296 | | template<size_t N> |
297 | | SliceParts(const std::array<Slice, N>& input) // NOLINT |
298 | 406M | : parts(input.data()), num_parts(N) { |
299 | 406M | } yb::SliceParts::SliceParts<5ul>(std::__1::array<yb::Slice, 5ul> const&) Line | Count | Source | 298 | 243 | : parts(input.data()), num_parts(N) { | 299 | 243 | } |
Unexecuted instantiation: yb::SliceParts::SliceParts<4ul>(std::__1::array<yb::Slice, 4ul> const&) Unexecuted instantiation: yb::SliceParts::SliceParts<6ul>(std::__1::array<yb::Slice, 6ul> const&) yb::SliceParts::SliceParts<2ul>(std::__1::array<yb::Slice, 2ul> const&) Line | Count | Source | 298 | 254M | : parts(input.data()), num_parts(N) { | 299 | 254M | } |
yb::SliceParts::SliceParts<1ul>(std::__1::array<yb::Slice, 1ul> const&) Line | Count | Source | 298 | 1.29k | : parts(input.data()), num_parts(N) { | 299 | 1.29k | } |
Unexecuted instantiation: yb::SliceParts::SliceParts<11ul>(std::__1::array<yb::Slice, 11ul> const&) yb::SliceParts::SliceParts<3ul>(std::__1::array<yb::Slice, 3ul> const&) Line | Count | Source | 298 | 86.6M | : parts(input.data()), num_parts(N) { | 299 | 86.6M | } |
yb::SliceParts::SliceParts<7ul>(std::__1::array<yb::Slice, 7ul> const&) Line | Count | Source | 298 | 64.6M | : parts(input.data()), num_parts(N) { | 299 | 64.6M | } |
Unexecuted instantiation: yb::SliceParts::SliceParts<10ul>(std::__1::array<yb::Slice, 10ul> const&) |
300 | | |
301 | | std::string ToDebugHexString() const; |
302 | | |
303 | | // Sum of sizes of all slices. |
304 | | size_t SumSizes() const; |
305 | | |
306 | | // Copy content of all slice to specified buffer. |
307 | 0 | void* CopyAllTo(void* out) const { |
308 | 0 | return CopyAllTo(static_cast<char*>(out)); |
309 | 0 | } |
310 | | |
311 | | char* CopyAllTo(char* out) const; |
312 | | |
313 | | Slice TheOnlyPart() const; |
314 | | |
315 | | const Slice* parts; |
316 | | int num_parts; |
317 | | }; |
318 | | |
319 | 1.96G | inline bool operator==(const Slice& x, const Slice& y) { |
320 | 1.96G | return ((x.size() == y.size()) && |
321 | 1.96G | (Slice::MemEqual(x.data(), y.data(), x.size()))1.70G ); |
322 | 1.96G | } |
323 | | |
324 | 182M | inline bool operator!=(const Slice& x, const Slice& y) { |
325 | 182M | return !(x == y); |
326 | 182M | } |
327 | | |
328 | 14 | inline std::ostream& operator<<(std::ostream& o, const Slice& s) { |
329 | 14 | return o << s.ToDebugString(16); // should be enough for anyone... |
330 | 14 | } |
331 | | |
332 | 36.0G | inline int Slice::compare(const Slice& b) const { |
333 | 36.0G | auto my_size = size(); |
334 | 36.0G | auto b_size = b.size(); |
335 | 36.0G | const size_t min_len = std::min(my_size, b_size); |
336 | 36.0G | int r = MemCompare(begin_, b.begin_, min_len); |
337 | 36.0G | if (r == 0) { |
338 | 1.02G | if (my_size < b_size) { return -1; }56.0M |
339 | 967M | if (my_size > b_size) { return 1; }93.8M |
340 | 967M | } |
341 | 35.8G | return r; |
342 | 36.0G | } |
343 | | |
344 | 8.22M | inline int Slice::compare_prefix(const Slice& b) const { |
345 | 8.22M | return Slice(begin_, std::min(size(), b.size())).compare(b); |
346 | 8.22M | } |
347 | | |
348 | 392M | inline size_t Slice::hash() const noexcept { |
349 | 392M | constexpr uint64_t kFnvOffset = 14695981039346656037ULL; |
350 | 392M | constexpr uint64_t kFnvPrime = 1099511628211ULL; |
351 | 392M | size_t result = kFnvOffset; |
352 | 392M | const uint8_t* e = end(); |
353 | 12.6G | for (const uint8_t* i = begin_; i != e; ++i12.2G ) { |
354 | 12.2G | result = (result * kFnvPrime) ^ *i; |
355 | 12.2G | } |
356 | 392M | return result; |
357 | 392M | } |
358 | | |
359 | 93.1M | inline size_t hash_value(const Slice& slice) { |
360 | 93.1M | return slice.hash(); |
361 | 93.1M | } |
362 | | |
363 | | inline size_t Slice::difference_offset(const Slice& b) const { |
364 | | size_t off = 0; |
365 | | const size_t len = std::min(size(), b.size()); |
366 | | for (; off < len; off++) { |
367 | | if (begin_[off] != b.begin_[off]) break; |
368 | | } |
369 | | return off; |
370 | | } |
371 | | |
372 | | // Can be used with source implicitly convertible to Slice, for example std::string. |
373 | 81.9k | inline void CopyToBuffer(const Slice& source, std::string* dest) { |
374 | | // operator= or assign(const std::string&) will shrink the capacity on at least CentOS gcc |
375 | | // build, so we have to use assign(const char*, size_t) to preserve buffer capacity and avoid |
376 | | // unnecessary memory reallocations. |
377 | 81.9k | source.CopyToBuffer(dest); |
378 | 81.9k | } |
379 | | |
380 | | } // namespace yb |
381 | | |
382 | | namespace rocksdb { |
383 | | |
384 | | typedef yb::Slice Slice; |
385 | | typedef yb::SliceParts SliceParts; |
386 | | |
387 | | } // namespace rocksdb |
388 | | |
389 | | #endif // YB_UTIL_SLICE_H_ |