1 | /* |
2 | * Copyright (c) Facebook, Inc. and its affiliates. |
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 | |
17 | // @author: Andrei Alexandrescu (aalexandre) |
18 | // String type. |
19 | |
20 | #pragma once |
21 | |
22 | #include <atomic> |
23 | #include <cstddef> |
24 | #include <iosfwd> |
25 | #include <limits> |
26 | #include <stdexcept> |
27 | #include <type_traits> |
28 | |
29 | #if FOLLY_HAS_STRING_VIEW |
30 | #include <string_view> |
31 | #endif |
32 | |
33 | #include <folly/CPortability.h> |
34 | #include <folly/CppAttributes.h> |
35 | #include <folly/Likely.h> |
36 | #include <folly/Portability.h> |
37 | |
38 | #include <algorithm> |
39 | #include <cassert> |
40 | #include <cstring> |
41 | #include <string> |
42 | #include <utility> |
43 | |
44 | #include <folly/Traits.h> |
45 | #include <folly/hash/Hash.h> |
46 | #include <folly/lang/Assume.h> |
47 | #include <folly/lang/Exception.h> |
48 | #include <folly/memory/Malloc.h> |
49 | |
50 | FOLLY_PUSH_WARNING |
51 | // Ignore shadowing warnings within this file, so includers can use -Wshadow. |
52 | FOLLY_GNU_DISABLE_WARNING("-Wshadow" ) |
53 | |
54 | namespace folly { |
55 | |
56 | // When compiling with ASan, always heap-allocate the string even if |
57 | // it would fit in-situ, so that ASan can detect access to the string |
58 | // buffer after it has been invalidated (destroyed, resized, etc.). |
59 | // Note that this flag doesn't remove support for in-situ strings, as |
60 | // that would break ABI-compatibility and wouldn't allow linking code |
61 | // compiled with this flag with code compiled without. |
62 | #ifdef FOLLY_SANITIZE_ADDRESS |
63 | #define FBSTRING_DISABLE_SSO true |
64 | #else |
65 | #define FBSTRING_DISABLE_SSO false |
66 | #endif |
67 | |
68 | namespace fbstring_detail { |
69 | |
70 | template <class InIt, class OutIt> |
71 | inline std::pair<InIt, OutIt> copy_n( |
72 | InIt b, |
73 | typename std::iterator_traits<InIt>::difference_type n, |
74 | OutIt d) { |
75 | for (; n != 0; --n, ++b, ++d) { |
76 | *d = *b; |
77 | } |
78 | return std::make_pair(b, d); |
79 | } |
80 | |
81 | template <class Pod, class T> |
82 | inline void podFill(Pod* b, Pod* e, T c) { |
83 | assert(b && e && b <= e); |
84 | constexpr auto kUseMemset = sizeof(T) == 1; |
85 | if /* constexpr */ (kUseMemset) { |
86 | memset(b, c, size_t(e - b)); |
87 | } else { |
88 | auto const ee = b + ((e - b) & ~7u); |
89 | for (; b != ee; b += 8) { |
90 | b[0] = c; |
91 | b[1] = c; |
92 | b[2] = c; |
93 | b[3] = c; |
94 | b[4] = c; |
95 | b[5] = c; |
96 | b[6] = c; |
97 | b[7] = c; |
98 | } |
99 | // Leftovers |
100 | for (; b != e; ++b) { |
101 | *b = c; |
102 | } |
103 | } |
104 | } |
105 | |
106 | /* |
107 | * Lightly structured memcpy, simplifies copying PODs and introduces |
108 | * some asserts. Unfortunately using this function may cause |
109 | * measurable overhead (presumably because it adjusts from a begin/end |
110 | * convention to a pointer/size convention, so it does some extra |
111 | * arithmetic even though the caller might have done the inverse |
112 | * adaptation outside). |
113 | */ |
114 | template <class Pod> |
115 | inline void podCopy(const Pod* b, const Pod* e, Pod* d) { |
116 | assert(b != nullptr); |
117 | assert(e != nullptr); |
118 | assert(d != nullptr); |
119 | assert(e >= b); |
120 | assert(d >= e || d + (e - b) <= b); |
121 | memcpy(d, b, (e - b) * sizeof(Pod)); |
122 | } |
123 | |
124 | /* |
125 | * Lightly structured memmove, simplifies copying PODs and introduces |
126 | * some asserts |
127 | */ |
128 | template <class Pod> |
129 | inline void podMove(const Pod* b, const Pod* e, Pod* d) { |
130 | assert(e >= b); |
131 | memmove(d, b, (e - b) * sizeof(*b)); |
132 | } |
133 | } // namespace fbstring_detail |
134 | |
135 | /** |
136 | * Defines a special acquisition method for constructing fbstring |
137 | * objects. AcquireMallocatedString means that the user passes a |
138 | * pointer to a malloc-allocated string that the fbstring object will |
139 | * take into custody. |
140 | */ |
141 | enum class AcquireMallocatedString {}; |
142 | |
143 | /* |
144 | * fbstring_core_model is a mock-up type that defines all required |
145 | * signatures of a fbstring core. The fbstring class itself uses such |
146 | * a core object to implement all of the numerous member functions |
147 | * required by the standard. |
148 | * |
149 | * If you want to define a new core, copy the definition below and |
150 | * implement the primitives. Then plug the core into basic_fbstring as |
151 | * a template argument. |
152 | |
153 | template <class Char> |
154 | class fbstring_core_model { |
155 | public: |
156 | fbstring_core_model(); |
157 | fbstring_core_model(const fbstring_core_model &); |
158 | fbstring_core_model& operator=(const fbstring_core_model &) = delete; |
159 | ~fbstring_core_model(); |
160 | // Returns a pointer to string's buffer (currently only contiguous |
161 | // strings are supported). The pointer is guaranteed to be valid |
162 | // until the next call to a non-const member function. |
163 | const Char * data() const; |
164 | // Much like data(), except the string is prepared to support |
165 | // character-level changes. This call is a signal for |
166 | // e.g. reference-counted implementation to fork the data. The |
167 | // pointer is guaranteed to be valid until the next call to a |
168 | // non-const member function. |
169 | Char* mutableData(); |
170 | // Returns a pointer to string's buffer and guarantees that a |
171 | // readable '\0' lies right after the buffer. The pointer is |
172 | // guaranteed to be valid until the next call to a non-const member |
173 | // function. |
174 | const Char * c_str() const; |
175 | // Shrinks the string by delta characters. Asserts that delta <= |
176 | // size(). |
177 | void shrink(size_t delta); |
178 | // Expands the string by delta characters (i.e. after this call |
179 | // size() will report the old size() plus delta) but without |
180 | // initializing the expanded region. The expanded region is |
181 | // zero-terminated. Returns a pointer to the memory to be |
182 | // initialized (the beginning of the expanded portion). The caller |
183 | // is expected to fill the expanded area appropriately. |
184 | // If expGrowth is true, exponential growth is guaranteed. |
185 | // It is not guaranteed not to reallocate even if size() + delta < |
186 | // capacity(), so all references to the buffer are invalidated. |
187 | Char* expandNoinit(size_t delta, bool expGrowth); |
188 | // Expands the string by one character and sets the last character |
189 | // to c. |
190 | void push_back(Char c); |
191 | // Returns the string's size. |
192 | size_t size() const; |
193 | // Returns the string's capacity, i.e. maximum size that the string |
194 | // can grow to without reallocation. Note that for reference counted |
195 | // strings that's technically a lie - even assigning characters |
196 | // within the existing size would cause a reallocation. |
197 | size_t capacity() const; |
198 | // Returns true if the data underlying the string is actually shared |
199 | // across multiple strings (in a refcounted fashion). |
200 | bool isShared() const; |
201 | // Makes sure that at least minCapacity characters are available for |
202 | // the string without reallocation. For reference-counted strings, |
203 | // it should fork the data even if minCapacity < size(). |
204 | void reserve(size_t minCapacity); |
205 | }; |
206 | */ |
207 | |
208 | /** |
209 | * This is the core of the string. The code should work on 32- and |
210 | * 64-bit and both big- and little-endianan architectures with any |
211 | * Char size. |
212 | * |
213 | * The storage is selected as follows (assuming we store one-byte |
214 | * characters on a 64-bit machine): (a) "small" strings between 0 and |
215 | * 23 chars are stored in-situ without allocation (the rightmost byte |
216 | * stores the size); (b) "medium" strings from 24 through 254 chars |
217 | * are stored in malloc-allocated memory that is copied eagerly; (c) |
218 | * "large" strings of 255 chars and above are stored in a similar |
219 | * structure as medium arrays, except that the string is |
220 | * reference-counted and copied lazily. the reference count is |
221 | * allocated right before the character array. |
222 | * |
223 | * The discriminator between these three strategies sits in two |
224 | * bits of the rightmost char of the storage: |
225 | * - If neither is set, then the string is small. Its length is represented by |
226 | * the lower-order bits on little-endian or the high-order bits on big-endian |
227 | * of that rightmost character. The value of these six bits is |
228 | * `maxSmallSize - size`, so this quantity must be subtracted from |
229 | * `maxSmallSize` to compute the `size` of the string (see `smallSize()`). |
230 | * This scheme ensures that when `size == `maxSmallSize`, the last byte in the |
231 | * storage is \0. This way, storage will be a null-terminated sequence of |
232 | * bytes, even if all 23 bytes of data are used on a 64-bit architecture. |
233 | * This enables `c_str()` and `data()` to simply return a pointer to the |
234 | * storage. |
235 | * |
236 | * - If the MSb is set, the string is medium width. |
237 | * |
238 | * - If the second MSb is set, then the string is large. On little-endian, |
239 | * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on |
240 | * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian |
241 | * and big-endian fbstring_core equivalent with merely different ops used |
242 | * to extract capacity/category. |
243 | */ |
244 | template <class Char> |
245 | class fbstring_core { |
246 | public: |
247 | fbstring_core() noexcept { |
248 | reset(); |
249 | } |
250 | |
251 | fbstring_core(const fbstring_core& rhs) { |
252 | assert(&rhs != this); |
253 | switch (rhs.category()) { |
254 | case Category::isSmall: |
255 | copySmall(rhs); |
256 | break; |
257 | case Category::isMedium: |
258 | copyMedium(rhs); |
259 | break; |
260 | case Category::isLarge: |
261 | copyLarge(rhs); |
262 | break; |
263 | default: |
264 | folly::assume_unreachable(); |
265 | } |
266 | assert(size() == rhs.size()); |
267 | assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0); |
268 | } |
269 | |
270 | fbstring_core& operator=(const fbstring_core& rhs) = delete; |
271 | |
272 | fbstring_core(fbstring_core&& goner) noexcept { |
273 | // Take goner's guts |
274 | ml_ = goner.ml_; |
275 | // Clean goner's carcass |
276 | goner.reset(); |
277 | } |
278 | |
279 | fbstring_core( |
280 | const Char* const data, |
281 | const size_t size, |
282 | bool disableSSO = FBSTRING_DISABLE_SSO) { |
283 | if (!disableSSO && size <= maxSmallSize) { |
284 | initSmall(data, size); |
285 | } else if (size <= maxMediumSize) { |
286 | initMedium(data, size); |
287 | } else { |
288 | initLarge(data, size); |
289 | } |
290 | assert(this->size() == size); |
291 | assert(size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0); |
292 | } |
293 | |
294 | ~fbstring_core() noexcept { |
295 | if (category() == Category::isSmall) { |
296 | return; |
297 | } |
298 | destroyMediumLarge(); |
299 | } |
300 | |
301 | // Snatches a previously mallocated string. The parameter "size" |
302 | // is the size of the string, and the parameter "allocatedSize" |
303 | // is the size of the mallocated block. The string must be |
304 | // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'. |
305 | // |
306 | // So if you want a 2-character string, pass malloc(3) as "data", |
307 | // pass 2 as "size", and pass 3 as "allocatedSize". |
308 | fbstring_core( |
309 | Char* const data, |
310 | const size_t size, |
311 | const size_t allocatedSize, |
312 | AcquireMallocatedString) { |
313 | if (size > 0) { |
314 | assert(allocatedSize >= size + 1); |
315 | assert(data[size] == '\0'); |
316 | // Use the medium string storage |
317 | ml_.data_ = data; |
318 | ml_.size_ = size; |
319 | // Don't forget about null terminator |
320 | ml_.setCapacity(allocatedSize - 1, Category::isMedium); |
321 | } else { |
322 | // No need for the memory |
323 | free(data); |
324 | reset(); |
325 | } |
326 | } |
327 | |
328 | // swap below doesn't test whether &rhs == this (and instead |
329 | // potentially does extra work) on the premise that the rarity of |
330 | // that situation actually makes the check more expensive than is |
331 | // worth. |
332 | void swap(fbstring_core& rhs) { |
333 | auto const t = ml_; |
334 | ml_ = rhs.ml_; |
335 | rhs.ml_ = t; |
336 | } |
337 | |
338 | // In C++11 data() and c_str() are 100% equivalent. |
339 | const Char* data() const { |
340 | return c_str(); |
341 | } |
342 | |
343 | Char* data() { |
344 | return c_str(); |
345 | } |
346 | |
347 | Char* mutableData() { |
348 | switch (category()) { |
349 | case Category::isSmall: |
350 | return small_; |
351 | case Category::isMedium: |
352 | return ml_.data_; |
353 | case Category::isLarge: |
354 | return mutableDataLarge(); |
355 | } |
356 | folly::assume_unreachable(); |
357 | } |
358 | |
359 | const Char* c_str() const { |
360 | const Char* ptr = ml_.data_; |
361 | // With this syntax, GCC and Clang generate a CMOV instead of a branch. |
362 | ptr = (category() == Category::isSmall) ? small_ : ptr; |
363 | return ptr; |
364 | } |
365 | |
366 | void shrink(const size_t delta) { |
367 | if (category() == Category::isSmall) { |
368 | shrinkSmall(delta); |
369 | } else if ( |
370 | category() == Category::isMedium || RefCounted::refs(ml_.data_) == 1) { |
371 | shrinkMedium(delta); |
372 | } else { |
373 | shrinkLarge(delta); |
374 | } |
375 | } |
376 | |
377 | FOLLY_NOINLINE |
378 | void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) { |
379 | switch (category()) { |
380 | case Category::isSmall: |
381 | reserveSmall(minCapacity, disableSSO); |
382 | break; |
383 | case Category::isMedium: |
384 | reserveMedium(minCapacity); |
385 | break; |
386 | case Category::isLarge: |
387 | reserveLarge(minCapacity); |
388 | break; |
389 | default: |
390 | folly::assume_unreachable(); |
391 | } |
392 | assert(capacity() >= minCapacity); |
393 | } |
394 | |
395 | Char* expandNoinit( |
396 | const size_t delta, |
397 | bool expGrowth = false, |
398 | bool disableSSO = FBSTRING_DISABLE_SSO); |
399 | |
400 | void push_back(Char c) { |
401 | *expandNoinit(1, /* expGrowth = */ true) = c; |
402 | } |
403 | |
404 | size_t size() const { |
405 | size_t ret = ml_.size_; |
406 | if /* constexpr */ (kIsLittleEndian) { |
407 | // We can save a couple instructions, because the category is |
408 | // small iff the last char, as unsigned, is <= maxSmallSize. |
409 | typedef typename std::make_unsigned<Char>::type UChar; |
410 | auto maybeSmallSize = size_t(maxSmallSize) - |
411 | size_t(static_cast<UChar>(small_[maxSmallSize])); |
412 | // With this syntax, GCC and Clang generate a CMOV instead of a branch. |
413 | ret = (static_cast<ssize_t>(maybeSmallSize) >= 0) ? maybeSmallSize : ret; |
414 | } else { |
415 | ret = (category() == Category::isSmall) ? smallSize() : ret; |
416 | } |
417 | return ret; |
418 | } |
419 | |
420 | size_t capacity() const { |
421 | switch (category()) { |
422 | case Category::isSmall: |
423 | return maxSmallSize; |
424 | case Category::isLarge: |
425 | // For large-sized strings, a multi-referenced chunk has no |
426 | // available capacity. This is because any attempt to append |
427 | // data would trigger a new allocation. |
428 | if (RefCounted::refs(ml_.data_) > 1) { |
429 | return ml_.size_; |
430 | } |
431 | break; |
432 | case Category::isMedium: |
433 | default: |
434 | break; |
435 | } |
436 | return ml_.capacity(); |
437 | } |
438 | |
439 | bool isShared() const { |
440 | return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1; |
441 | } |
442 | |
443 | private: |
444 | Char* c_str() { |
445 | Char* ptr = ml_.data_; |
446 | // With this syntax, GCC and Clang generate a CMOV instead of a branch. |
447 | ptr = (category() == Category::isSmall) ? small_ : ptr; |
448 | return ptr; |
449 | } |
450 | |
451 | void reset() { |
452 | setSmallSize(0); |
453 | } |
454 | |
455 | FOLLY_NOINLINE void destroyMediumLarge() noexcept { |
456 | auto const c = category(); |
457 | assert(c != Category::isSmall); |
458 | if (c == Category::isMedium) { |
459 | free(ml_.data_); |
460 | } else { |
461 | RefCounted::decrementRefs(ml_.data_); |
462 | } |
463 | } |
464 | |
465 | struct RefCounted { |
466 | std::atomic<size_t> refCount_; |
467 | Char data_[1]; |
468 | |
469 | constexpr static size_t getDataOffset() { |
470 | return offsetof(RefCounted, data_); |
471 | } |
472 | |
473 | static RefCounted* fromData(Char* p) { |
474 | return static_cast<RefCounted*>(static_cast<void*>( |
475 | static_cast<unsigned char*>(static_cast<void*>(p)) - |
476 | getDataOffset())); |
477 | } |
478 | |
479 | static size_t refs(Char* p) { |
480 | return fromData(p)->refCount_.load(std::memory_order_acquire); |
481 | } |
482 | |
483 | static void incrementRefs(Char* p) { |
484 | fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel); |
485 | } |
486 | |
487 | static void decrementRefs(Char* p) { |
488 | auto const dis = fromData(p); |
489 | size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel); |
490 | assert(oldcnt > 0); |
491 | if (oldcnt == 1) { |
492 | free(dis); |
493 | } |
494 | } |
495 | |
496 | static RefCounted* create(size_t* size) { |
497 | const size_t allocSize = |
498 | goodMallocSize(getDataOffset() + (*size + 1) * sizeof(Char)); |
499 | auto result = static_cast<RefCounted*>(checkedMalloc(allocSize)); |
500 | result->refCount_.store(1, std::memory_order_release); |
501 | *size = (allocSize - getDataOffset()) / sizeof(Char) - 1; |
502 | return result; |
503 | } |
504 | |
505 | static RefCounted* create(const Char* data, size_t* size) { |
506 | const size_t effectiveSize = *size; |
507 | auto result = create(size); |
508 | if (FOLLY_LIKELY(effectiveSize > 0)) { |
509 | fbstring_detail::podCopy(data, data + effectiveSize, result->data_); |
510 | } |
511 | return result; |
512 | } |
513 | |
514 | static RefCounted* reallocate( |
515 | Char* const data, |
516 | const size_t currentSize, |
517 | const size_t currentCapacity, |
518 | size_t* newCapacity) { |
519 | assert(*newCapacity > 0 && *newCapacity > currentSize); |
520 | const size_t allocNewCapacity = |
521 | goodMallocSize(getDataOffset() + (*newCapacity + 1) * sizeof(Char)); |
522 | auto const dis = fromData(data); |
523 | assert(dis->refCount_.load(std::memory_order_acquire) == 1); |
524 | auto result = static_cast<RefCounted*>(smartRealloc( |
525 | dis, |
526 | getDataOffset() + (currentSize + 1) * sizeof(Char), |
527 | getDataOffset() + (currentCapacity + 1) * sizeof(Char), |
528 | allocNewCapacity)); |
529 | assert(result->refCount_.load(std::memory_order_acquire) == 1); |
530 | *newCapacity = (allocNewCapacity - getDataOffset()) / sizeof(Char) - 1; |
531 | return result; |
532 | } |
533 | }; |
534 | |
535 | typedef uint8_t category_type; |
536 | |
537 | enum class Category : category_type { |
538 | isSmall = 0, |
539 | isMedium = kIsLittleEndian ? 0x80 : 0x2, |
540 | isLarge = kIsLittleEndian ? 0x40 : 0x1, |
541 | }; |
542 | |
543 | Category category() const { |
544 | // works for both big-endian and little-endian |
545 | return static_cast<Category>(bytes_[lastChar] & categoryExtractMask); |
546 | } |
547 | |
548 | struct MediumLarge { |
549 | Char* data_; |
550 | size_t size_; |
551 | size_t capacity_; |
552 | |
553 | size_t capacity() const { |
554 | return kIsLittleEndian ? capacity_ & capacityExtractMask : capacity_ >> 2; |
555 | } |
556 | |
557 | void setCapacity(size_t cap, Category cat) { |
558 | capacity_ = kIsLittleEndian |
559 | ? cap | (static_cast<size_t>(cat) << kCategoryShift) |
560 | : (cap << 2) | static_cast<size_t>(cat); |
561 | } |
562 | }; |
563 | |
564 | union { |
565 | uint8_t bytes_[sizeof(MediumLarge)]; // For accessing the last byte. |
566 | Char small_[sizeof(MediumLarge) / sizeof(Char)]; |
567 | MediumLarge ml_; |
568 | }; |
569 | |
570 | constexpr static size_t lastChar = sizeof(MediumLarge) - 1; |
571 | constexpr static size_t maxSmallSize = lastChar / sizeof(Char); |
572 | constexpr static size_t maxMediumSize = 254 / sizeof(Char); |
573 | constexpr static uint8_t = kIsLittleEndian ? 0xC0 : 0x3; |
574 | constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8; |
575 | constexpr static size_t = kIsLittleEndian |
576 | ? ~(size_t(categoryExtractMask) << kCategoryShift) |
577 | : 0x0 /* unused */; |
578 | |
579 | static_assert( |
580 | !(sizeof(MediumLarge) % sizeof(Char)), |
581 | "Corrupt memory layout for fbstring." ); |
582 | |
583 | size_t smallSize() const { |
584 | assert(category() == Category::isSmall); |
585 | constexpr auto shift = kIsLittleEndian ? 0 : 2; |
586 | auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift; |
587 | assert(static_cast<size_t>(maxSmallSize) >= smallShifted); |
588 | return static_cast<size_t>(maxSmallSize) - smallShifted; |
589 | } |
590 | |
591 | void setSmallSize(size_t s) { |
592 | // Warning: this should work with uninitialized strings too, |
593 | // so don't assume anything about the previous value of |
594 | // small_[maxSmallSize]. |
595 | assert(s <= maxSmallSize); |
596 | constexpr auto shift = kIsLittleEndian ? 0 : 2; |
597 | small_[maxSmallSize] = char((maxSmallSize - s) << shift); |
598 | small_[s] = '\0'; |
599 | assert(category() == Category::isSmall && size() == s); |
600 | } |
601 | |
602 | void copySmall(const fbstring_core&); |
603 | void copyMedium(const fbstring_core&); |
604 | void copyLarge(const fbstring_core&); |
605 | |
606 | void initSmall(const Char* data, size_t size); |
607 | void initMedium(const Char* data, size_t size); |
608 | void initLarge(const Char* data, size_t size); |
609 | |
610 | void reserveSmall(size_t minCapacity, bool disableSSO); |
611 | void reserveMedium(size_t minCapacity); |
612 | void reserveLarge(size_t minCapacity); |
613 | |
614 | void shrinkSmall(size_t delta); |
615 | void shrinkMedium(size_t delta); |
616 | void shrinkLarge(size_t delta); |
617 | |
618 | void unshare(size_t minCapacity = 0); |
619 | Char* mutableDataLarge(); |
620 | }; |
621 | |
622 | template <class Char> |
623 | inline void fbstring_core<Char>::copySmall(const fbstring_core& rhs) { |
624 | static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure" ); |
625 | static_assert( |
626 | offsetof(MediumLarge, size_) == sizeof(ml_.data_), |
627 | "fbstring layout failure" ); |
628 | static_assert( |
629 | offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_), |
630 | "fbstring layout failure" ); |
631 | // Just write the whole thing, don't look at details. In |
632 | // particular we need to copy capacity anyway because we want |
633 | // to set the size (don't forget that the last character, |
634 | // which stores a short string's length, is shared with the |
635 | // ml_.capacity field). |
636 | ml_ = rhs.ml_; |
637 | assert(category() == Category::isSmall && this->size() == rhs.size()); |
638 | } |
639 | |
640 | template <class Char> |
641 | FOLLY_NOINLINE inline void fbstring_core<Char>::copyMedium( |
642 | const fbstring_core& rhs) { |
643 | // Medium strings are copied eagerly. Don't forget to allocate |
644 | // one extra Char for the null terminator. |
645 | auto const allocSize = goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char)); |
646 | ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize)); |
647 | // Also copies terminator. |
648 | fbstring_detail::podCopy( |
649 | rhs.ml_.data_, rhs.ml_.data_ + rhs.ml_.size_ + 1, ml_.data_); |
650 | ml_.size_ = rhs.ml_.size_; |
651 | ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium); |
652 | assert(category() == Category::isMedium); |
653 | } |
654 | |
655 | template <class Char> |
656 | FOLLY_NOINLINE inline void fbstring_core<Char>::copyLarge( |
657 | const fbstring_core& rhs) { |
658 | // Large strings are just refcounted |
659 | ml_ = rhs.ml_; |
660 | RefCounted::incrementRefs(ml_.data_); |
661 | assert(category() == Category::isLarge && size() == rhs.size()); |
662 | } |
663 | |
664 | // Small strings are bitblitted |
665 | template <class Char> |
666 | inline void fbstring_core<Char>::initSmall( |
667 | const Char* const data, |
668 | const size_t size) { |
669 | // Layout is: Char* data_, size_t size_, size_t capacity_ |
670 | static_assert( |
671 | sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t), |
672 | "fbstring has unexpected size" ); |
673 | static_assert( |
674 | sizeof(Char*) == sizeof(size_t), "fbstring size assumption violation" ); |
675 | // sizeof(size_t) must be a power of 2 |
676 | static_assert( |
677 | (sizeof(size_t) & (sizeof(size_t) - 1)) == 0, |
678 | "fbstring size assumption violation" ); |
679 | |
680 | // If data is aligned, use fast word-wise copying. Otherwise, |
681 | // use conservative memcpy. |
682 | // The word-wise path reads bytes which are outside the range of |
683 | // the string, and makes ASan unhappy, so we disable it when |
684 | // compiling with ASan. |
685 | #ifndef FOLLY_SANITIZE_ADDRESS |
686 | if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) { |
687 | const size_t byteSize = size * sizeof(Char); |
688 | constexpr size_t wordWidth = sizeof(size_t); |
689 | switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words. |
690 | case 3: |
691 | ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2]; |
692 | FOLLY_FALLTHROUGH; |
693 | case 2: |
694 | ml_.size_ = reinterpret_cast<const size_t*>(data)[1]; |
695 | FOLLY_FALLTHROUGH; |
696 | case 1: |
697 | ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data)); |
698 | FOLLY_FALLTHROUGH; |
699 | case 0: |
700 | break; |
701 | } |
702 | } else |
703 | #endif |
704 | { |
705 | if (size != 0) { |
706 | fbstring_detail::podCopy(data, data + size, small_); |
707 | } |
708 | } |
709 | setSmallSize(size); |
710 | } |
711 | |
712 | template <class Char> |
713 | FOLLY_NOINLINE inline void fbstring_core<Char>::initMedium( |
714 | const Char* const data, |
715 | const size_t size) { |
716 | // Medium strings are allocated normally. Don't forget to |
717 | // allocate one extra Char for the terminating null. |
718 | auto const allocSize = goodMallocSize((1 + size) * sizeof(Char)); |
719 | ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize)); |
720 | if (FOLLY_LIKELY(size > 0)) { |
721 | fbstring_detail::podCopy(data, data + size, ml_.data_); |
722 | } |
723 | ml_.size_ = size; |
724 | ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium); |
725 | ml_.data_[size] = '\0'; |
726 | } |
727 | |
728 | template <class Char> |
729 | FOLLY_NOINLINE inline void fbstring_core<Char>::initLarge( |
730 | const Char* const data, |
731 | const size_t size) { |
732 | // Large strings are allocated differently |
733 | size_t effectiveCapacity = size; |
734 | auto const newRC = RefCounted::create(data, &effectiveCapacity); |
735 | ml_.data_ = newRC->data_; |
736 | ml_.size_ = size; |
737 | ml_.setCapacity(effectiveCapacity, Category::isLarge); |
738 | ml_.data_[size] = '\0'; |
739 | } |
740 | |
741 | template <class Char> |
742 | FOLLY_NOINLINE inline void fbstring_core<Char>::unshare(size_t minCapacity) { |
743 | assert(category() == Category::isLarge); |
744 | size_t effectiveCapacity = std::max(minCapacity, ml_.capacity()); |
745 | auto const newRC = RefCounted::create(&effectiveCapacity); |
746 | // If this fails, someone placed the wrong capacity in an |
747 | // fbstring. |
748 | assert(effectiveCapacity >= ml_.capacity()); |
749 | // Also copies terminator. |
750 | fbstring_detail::podCopy(ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_); |
751 | RefCounted::decrementRefs(ml_.data_); |
752 | ml_.data_ = newRC->data_; |
753 | ml_.setCapacity(effectiveCapacity, Category::isLarge); |
754 | // size_ remains unchanged. |
755 | } |
756 | |
757 | template <class Char> |
758 | inline Char* fbstring_core<Char>::mutableDataLarge() { |
759 | assert(category() == Category::isLarge); |
760 | if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique. |
761 | unshare(); |
762 | } |
763 | return ml_.data_; |
764 | } |
765 | |
766 | template <class Char> |
767 | FOLLY_NOINLINE inline void fbstring_core<Char>::reserveLarge( |
768 | size_t minCapacity) { |
769 | assert(category() == Category::isLarge); |
770 | if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique |
771 | // We must make it unique regardless; in-place reallocation is |
772 | // useless if the string is shared. In order to not surprise |
773 | // people, reserve the new block at current capacity or |
774 | // more. That way, a string's capacity never shrinks after a |
775 | // call to reserve. |
776 | unshare(minCapacity); |
777 | } else { |
778 | // String is not shared, so let's try to realloc (if needed) |
779 | if (minCapacity > ml_.capacity()) { |
780 | // Asking for more memory |
781 | auto const newRC = RefCounted::reallocate( |
782 | ml_.data_, ml_.size_, ml_.capacity(), &minCapacity); |
783 | ml_.data_ = newRC->data_; |
784 | ml_.setCapacity(minCapacity, Category::isLarge); |
785 | } |
786 | assert(capacity() >= minCapacity); |
787 | } |
788 | } |
789 | |
790 | template <class Char> |
791 | FOLLY_NOINLINE inline void fbstring_core<Char>::reserveMedium( |
792 | const size_t minCapacity) { |
793 | assert(category() == Category::isMedium); |
794 | // String is not shared |
795 | if (minCapacity <= ml_.capacity()) { |
796 | return; // nothing to do, there's enough room |
797 | } |
798 | if (minCapacity <= maxMediumSize) { |
799 | // Keep the string at medium size. Don't forget to allocate |
800 | // one extra Char for the terminating null. |
801 | size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char)); |
802 | // Also copies terminator. |
803 | ml_.data_ = static_cast<Char*>(smartRealloc( |
804 | ml_.data_, |
805 | (ml_.size_ + 1) * sizeof(Char), |
806 | (ml_.capacity() + 1) * sizeof(Char), |
807 | capacityBytes)); |
808 | ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium); |
809 | } else { |
810 | // Conversion from medium to large string |
811 | fbstring_core nascent; |
812 | // Will recurse to another branch of this function |
813 | nascent.reserve(minCapacity); |
814 | nascent.ml_.size_ = ml_.size_; |
815 | // Also copies terminator. |
816 | fbstring_detail::podCopy( |
817 | ml_.data_, ml_.data_ + ml_.size_ + 1, nascent.ml_.data_); |
818 | nascent.swap(*this); |
819 | assert(capacity() >= minCapacity); |
820 | } |
821 | } |
822 | |
823 | template <class Char> |
824 | FOLLY_NOINLINE inline void fbstring_core<Char>::reserveSmall( |
825 | size_t minCapacity, |
826 | const bool disableSSO) { |
827 | assert(category() == Category::isSmall); |
828 | if (!disableSSO && minCapacity <= maxSmallSize) { |
829 | // small |
830 | // Nothing to do, everything stays put |
831 | } else if (minCapacity <= maxMediumSize) { |
832 | // medium |
833 | // Don't forget to allocate one extra Char for the terminating null |
834 | auto const allocSizeBytes = |
835 | goodMallocSize((1 + minCapacity) * sizeof(Char)); |
836 | auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes)); |
837 | auto const size = smallSize(); |
838 | // Also copies terminator. |
839 | fbstring_detail::podCopy(small_, small_ + size + 1, pData); |
840 | ml_.data_ = pData; |
841 | ml_.size_ = size; |
842 | ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium); |
843 | } else { |
844 | // large |
845 | auto const newRC = RefCounted::create(&minCapacity); |
846 | auto const size = smallSize(); |
847 | // Also copies terminator. |
848 | fbstring_detail::podCopy(small_, small_ + size + 1, newRC->data_); |
849 | ml_.data_ = newRC->data_; |
850 | ml_.size_ = size; |
851 | ml_.setCapacity(minCapacity, Category::isLarge); |
852 | assert(capacity() >= minCapacity); |
853 | } |
854 | } |
855 | |
856 | template <class Char> |
857 | inline Char* fbstring_core<Char>::expandNoinit( |
858 | const size_t delta, |
859 | bool expGrowth, /* = false */ |
860 | bool disableSSO /* = FBSTRING_DISABLE_SSO */) { |
861 | // Strategy is simple: make room, then change size |
862 | assert(capacity() >= size()); |
863 | size_t sz, newSz; |
864 | if (category() == Category::isSmall) { |
865 | sz = smallSize(); |
866 | newSz = sz + delta; |
867 | if (!disableSSO && FOLLY_LIKELY(newSz <= maxSmallSize)) { |
868 | setSmallSize(newSz); |
869 | return small_ + sz; |
870 | } |
871 | reserveSmall( |
872 | expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz, disableSSO); |
873 | } else { |
874 | sz = ml_.size_; |
875 | newSz = sz + delta; |
876 | if (FOLLY_UNLIKELY(newSz > capacity())) { |
877 | // ensures not shared |
878 | reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz); |
879 | } |
880 | } |
881 | assert(capacity() >= newSz); |
882 | // Category can't be small - we took care of that above |
883 | assert(category() == Category::isMedium || category() == Category::isLarge); |
884 | ml_.size_ = newSz; |
885 | ml_.data_[newSz] = '\0'; |
886 | assert(size() == newSz); |
887 | return ml_.data_ + sz; |
888 | } |
889 | |
890 | template <class Char> |
891 | inline void fbstring_core<Char>::shrinkSmall(const size_t delta) { |
892 | // Check for underflow |
893 | assert(delta <= smallSize()); |
894 | setSmallSize(smallSize() - delta); |
895 | } |
896 | |
897 | template <class Char> |
898 | inline void fbstring_core<Char>::shrinkMedium(const size_t delta) { |
899 | // Medium strings and unique large strings need no special |
900 | // handling. |
901 | assert(ml_.size_ >= delta); |
902 | ml_.size_ -= delta; |
903 | ml_.data_[ml_.size_] = '\0'; |
904 | } |
905 | |
906 | template <class Char> |
907 | inline void fbstring_core<Char>::shrinkLarge(const size_t delta) { |
908 | assert(ml_.size_ >= delta); |
909 | // Shared large string, must make unique. This is because of the |
910 | // durn terminator must be written, which may trample the shared |
911 | // data. |
912 | if (delta) { |
913 | fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this); |
914 | } |
915 | // No need to write the terminator. |
916 | } |
917 | |
918 | /** |
919 | * Dummy fbstring core that uses an actual std::string. This doesn't |
920 | * make any sense - it's just for testing purposes. |
921 | */ |
922 | template <class Char> |
923 | class dummy_fbstring_core { |
924 | public: |
925 | dummy_fbstring_core() {} |
926 | dummy_fbstring_core(const dummy_fbstring_core& another) |
927 | : backend_(another.backend_) {} |
928 | dummy_fbstring_core(const Char* s, size_t n) : backend_(s, n) {} |
929 | void swap(dummy_fbstring_core& rhs) { |
930 | backend_.swap(rhs.backend_); |
931 | } |
932 | const Char* data() const { |
933 | return backend_.data(); |
934 | } |
935 | Char* mutableData() { |
936 | return const_cast<Char*>(backend_.data()); |
937 | } |
938 | void shrink(size_t delta) { |
939 | assert(delta <= size()); |
940 | backend_.resize(size() - delta); |
941 | } |
942 | Char* expandNoinit(size_t delta) { |
943 | auto const sz = size(); |
944 | backend_.resize(size() + delta); |
945 | return backend_.data() + sz; |
946 | } |
947 | void push_back(Char c) { |
948 | backend_.push_back(c); |
949 | } |
950 | size_t size() const { |
951 | return backend_.size(); |
952 | } |
953 | size_t capacity() const { |
954 | return backend_.capacity(); |
955 | } |
956 | bool isShared() const { |
957 | return false; |
958 | } |
959 | void reserve(size_t minCapacity) { |
960 | backend_.reserve(minCapacity); |
961 | } |
962 | |
963 | private: |
964 | std::basic_string<Char> backend_; |
965 | }; |
966 | |
967 | /** |
968 | * This is the basic_string replacement. For conformity, |
969 | * basic_fbstring takes the same template parameters, plus the last |
970 | * one which is the core. |
971 | */ |
972 | template < |
973 | typename E, |
974 | class T = std::char_traits<E>, |
975 | class A = std::allocator<E>, |
976 | class Storage = fbstring_core<E>> |
977 | class basic_fbstring { |
978 | template <typename Ex, typename... Args> |
979 | FOLLY_ALWAYS_INLINE static void enforce(bool condition, Args&&... args) { |
980 | if (!condition) { |
981 | throw_exception<Ex>(static_cast<Args&&>(args)...); |
982 | } |
983 | } |
984 | |
985 | bool isSane() const { |
986 | return begin() <= end() && empty() == (size() == 0) && |
987 | empty() == (begin() == end()) && size() <= max_size() && |
988 | capacity() <= max_size() && size() <= capacity() && |
989 | begin()[size()] == '\0'; |
990 | } |
991 | |
992 | struct Invariant { |
993 | Invariant& operator=(const Invariant&) = delete; |
994 | explicit Invariant(const basic_fbstring& s) noexcept : s_(s) { |
995 | assert(s_.isSane()); |
996 | } |
997 | ~Invariant() noexcept { |
998 | assert(s_.isSane()); |
999 | } |
1000 | |
1001 | private: |
1002 | const basic_fbstring& s_; |
1003 | }; |
1004 | |
1005 | public: |
1006 | // types |
1007 | typedef T traits_type; |
1008 | typedef typename traits_type::char_type value_type; |
1009 | typedef A allocator_type; |
1010 | typedef typename A::size_type size_type; |
1011 | typedef typename A::difference_type difference_type; |
1012 | |
1013 | typedef typename A::reference reference; |
1014 | typedef typename A::const_reference const_reference; |
1015 | typedef typename A::pointer pointer; |
1016 | typedef typename A::const_pointer const_pointer; |
1017 | |
1018 | typedef E* iterator; |
1019 | typedef const E* const_iterator; |
1020 | typedef std::reverse_iterator<iterator> reverse_iterator; |
1021 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
1022 | |
1023 | static constexpr size_type npos = size_type(-1); |
1024 | typedef std::true_type IsRelocatable; |
1025 | |
1026 | private: |
1027 | static void procrustes(size_type& n, size_type nmax) { |
1028 | if (n > nmax) { |
1029 | n = nmax; |
1030 | } |
1031 | } |
1032 | |
1033 | static size_type traitsLength(const value_type* s); |
1034 | |
1035 | public: |
1036 | // C++11 21.4.2 construct/copy/destroy |
1037 | |
1038 | // Note: while the following two constructors can be (and previously were) |
1039 | // collapsed into one constructor written this way: |
1040 | // |
1041 | // explicit basic_fbstring(const A& a = A()) noexcept { } |
1042 | // |
1043 | // This can cause Clang (at least version 3.7) to fail with the error: |
1044 | // "chosen constructor is explicit in copy-initialization ... |
1045 | // in implicit initialization of field '(x)' with omitted initializer" |
1046 | // |
1047 | // if used in a struct which is default-initialized. Hence the split into |
1048 | // these two separate constructors. |
1049 | |
1050 | basic_fbstring() noexcept : basic_fbstring(A()) {} |
1051 | |
1052 | explicit basic_fbstring(const A&) noexcept {} |
1053 | |
1054 | basic_fbstring(const basic_fbstring& str) : store_(str.store_) {} |
1055 | |
1056 | // Move constructor |
1057 | basic_fbstring(basic_fbstring&& goner) noexcept |
1058 | : store_(std::move(goner.store_)) {} |
1059 | |
1060 | // This is defined for compatibility with std::string |
1061 | template <typename A2> |
1062 | /* implicit */ basic_fbstring(const std::basic_string<E, T, A2>& str) |
1063 | : store_(str.data(), str.size()) {} |
1064 | |
1065 | basic_fbstring( |
1066 | const basic_fbstring& str, |
1067 | size_type pos, |
1068 | size_type n = npos, |
1069 | const A& /* a */ = A()) { |
1070 | assign(str, pos, n); |
1071 | } |
1072 | |
1073 | FOLLY_NOINLINE |
1074 | /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A()) |
1075 | : store_(s, traitsLength(s)) {} |
1076 | |
1077 | FOLLY_NOINLINE |
1078 | basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A()) |
1079 | : store_(s, n) {} |
1080 | |
1081 | FOLLY_NOINLINE |
1082 | basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) { |
1083 | auto const pData = store_.expandNoinit(n); |
1084 | fbstring_detail::podFill(pData, pData + n, c); |
1085 | } |
1086 | |
1087 | template <class InIt> |
1088 | FOLLY_NOINLINE basic_fbstring( |
1089 | InIt begin, |
1090 | InIt end, |
1091 | typename std::enable_if< |
1092 | !std::is_same<InIt, value_type*>::value, |
1093 | const A>::type& /*a*/ |
1094 | = A()) { |
1095 | assign(begin, end); |
1096 | } |
1097 | |
1098 | // Specialization for const char*, const char* |
1099 | FOLLY_NOINLINE |
1100 | basic_fbstring(const value_type* b, const value_type* e, const A& /*a*/ = A()) |
1101 | : store_(b, size_type(e - b)) {} |
1102 | |
1103 | // Nonstandard constructor |
1104 | basic_fbstring( |
1105 | value_type* s, |
1106 | size_type n, |
1107 | size_type c, |
1108 | AcquireMallocatedString a) |
1109 | : store_(s, n, c, a) {} |
1110 | |
1111 | // Construction from initialization list |
1112 | FOLLY_NOINLINE |
1113 | basic_fbstring(std::initializer_list<value_type> il) { |
1114 | assign(il.begin(), il.end()); |
1115 | } |
1116 | |
1117 | ~basic_fbstring() noexcept {} |
1118 | |
1119 | basic_fbstring& operator=(const basic_fbstring& lhs); |
1120 | |
1121 | // Move assignment |
1122 | basic_fbstring& operator=(basic_fbstring&& goner) noexcept; |
1123 | |
1124 | // Compatibility with std::string |
1125 | template <typename A2> |
1126 | basic_fbstring& operator=(const std::basic_string<E, T, A2>& rhs) { |
1127 | return assign(rhs.data(), rhs.size()); |
1128 | } |
1129 | |
1130 | // Compatibility with std::string |
1131 | std::basic_string<E, T, A> toStdString() const { |
1132 | return std::basic_string<E, T, A>(data(), size()); |
1133 | } |
1134 | |
1135 | basic_fbstring& operator=(const value_type* s) { |
1136 | return assign(s); |
1137 | } |
1138 | |
1139 | basic_fbstring& operator=(value_type c); |
1140 | |
1141 | // This actually goes directly against the C++ spec, but the |
1142 | // value_type overload is dangerous, so we're explicitly deleting |
1143 | // any overloads of operator= that could implicitly convert to |
1144 | // value_type. |
1145 | // Note that we do need to explicitly specify the template types because |
1146 | // otherwise MSVC 2017 will aggressively pre-resolve value_type to |
1147 | // traits_type::char_type, which won't compare as equal when determining |
1148 | // which overload the implementation is referring to. |
1149 | template <typename TP> |
1150 | typename std::enable_if< |
1151 | std::is_convertible< |
1152 | TP, |
1153 | typename basic_fbstring<E, T, A, Storage>::value_type>::value && |
1154 | !std::is_same< |
1155 | typename std::decay<TP>::type, |
1156 | typename basic_fbstring<E, T, A, Storage>::value_type>::value, |
1157 | basic_fbstring<E, T, A, Storage>&>::type |
1158 | operator=(TP c) = delete; |
1159 | |
1160 | basic_fbstring& operator=(std::initializer_list<value_type> il) { |
1161 | return assign(il.begin(), il.end()); |
1162 | } |
1163 | |
1164 | #if FOLLY_HAS_STRING_VIEW |
1165 | operator std::basic_string_view<value_type, traits_type>() const noexcept { |
1166 | return {data(), size()}; |
1167 | } |
1168 | #endif |
1169 | |
1170 | // C++11 21.4.3 iterators: |
1171 | iterator begin() { |
1172 | return store_.mutableData(); |
1173 | } |
1174 | |
1175 | const_iterator begin() const { |
1176 | return store_.data(); |
1177 | } |
1178 | |
1179 | const_iterator cbegin() const { |
1180 | return begin(); |
1181 | } |
1182 | |
1183 | iterator end() { |
1184 | return store_.mutableData() + store_.size(); |
1185 | } |
1186 | |
1187 | const_iterator end() const { |
1188 | return store_.data() + store_.size(); |
1189 | } |
1190 | |
1191 | const_iterator cend() const { |
1192 | return end(); |
1193 | } |
1194 | |
1195 | reverse_iterator rbegin() { |
1196 | return reverse_iterator(end()); |
1197 | } |
1198 | |
1199 | const_reverse_iterator rbegin() const { |
1200 | return const_reverse_iterator(end()); |
1201 | } |
1202 | |
1203 | const_reverse_iterator crbegin() const { |
1204 | return rbegin(); |
1205 | } |
1206 | |
1207 | reverse_iterator rend() { |
1208 | return reverse_iterator(begin()); |
1209 | } |
1210 | |
1211 | const_reverse_iterator rend() const { |
1212 | return const_reverse_iterator(begin()); |
1213 | } |
1214 | |
1215 | const_reverse_iterator crend() const { |
1216 | return rend(); |
1217 | } |
1218 | |
1219 | // Added by C++11 |
1220 | // C++11 21.4.5, element access: |
1221 | const value_type& front() const { |
1222 | return *begin(); |
1223 | } |
1224 | const value_type& back() const { |
1225 | assert(!empty()); |
1226 | // Should be begin()[size() - 1], but that branches twice |
1227 | return *(end() - 1); |
1228 | } |
1229 | value_type& front() { |
1230 | return *begin(); |
1231 | } |
1232 | value_type& back() { |
1233 | assert(!empty()); |
1234 | // Should be begin()[size() - 1], but that branches twice |
1235 | return *(end() - 1); |
1236 | } |
1237 | void pop_back() { |
1238 | assert(!empty()); |
1239 | store_.shrink(1); |
1240 | } |
1241 | |
1242 | // C++11 21.4.4 capacity: |
1243 | size_type size() const { |
1244 | return store_.size(); |
1245 | } |
1246 | |
1247 | size_type length() const { |
1248 | return size(); |
1249 | } |
1250 | |
1251 | size_type max_size() const { |
1252 | return std::numeric_limits<size_type>::max(); |
1253 | } |
1254 | |
1255 | void resize(size_type n, value_type c = value_type()); |
1256 | |
1257 | size_type capacity() const { |
1258 | return store_.capacity(); |
1259 | } |
1260 | |
1261 | void reserve(size_type res_arg = 0) { |
1262 | enforce<std::length_error>(res_arg <= max_size(), "" ); |
1263 | store_.reserve(res_arg); |
1264 | } |
1265 | |
1266 | void shrink_to_fit() { |
1267 | // Shrink only if slack memory is sufficiently large |
1268 | if (capacity() < size() * 3 / 2) { |
1269 | return; |
1270 | } |
1271 | basic_fbstring(cbegin(), cend()).swap(*this); |
1272 | } |
1273 | |
1274 | void clear() { |
1275 | resize(0); |
1276 | } |
1277 | |
1278 | bool empty() const { |
1279 | return size() == 0; |
1280 | } |
1281 | |
1282 | // C++11 21.4.5 element access: |
1283 | const_reference operator[](size_type pos) const { |
1284 | return *(begin() + pos); |
1285 | } |
1286 | |
1287 | reference operator[](size_type pos) { |
1288 | return *(begin() + pos); |
1289 | } |
1290 | |
1291 | const_reference at(size_type n) const { |
1292 | enforce<std::out_of_range>(n < size(), "" ); |
1293 | return (*this)[n]; |
1294 | } |
1295 | |
1296 | reference at(size_type n) { |
1297 | enforce<std::out_of_range>(n < size(), "" ); |
1298 | return (*this)[n]; |
1299 | } |
1300 | |
1301 | // C++11 21.4.6 modifiers: |
1302 | basic_fbstring& operator+=(const basic_fbstring& str) { |
1303 | return append(str); |
1304 | } |
1305 | |
1306 | basic_fbstring& operator+=(const value_type* s) { |
1307 | return append(s); |
1308 | } |
1309 | |
1310 | basic_fbstring& operator+=(const value_type c) { |
1311 | push_back(c); |
1312 | return *this; |
1313 | } |
1314 | |
1315 | basic_fbstring& operator+=(std::initializer_list<value_type> il) { |
1316 | append(il); |
1317 | return *this; |
1318 | } |
1319 | |
1320 | basic_fbstring& append(const basic_fbstring& str); |
1321 | |
1322 | basic_fbstring& |
1323 | append(const basic_fbstring& str, const size_type pos, size_type n); |
1324 | |
1325 | basic_fbstring& append(const value_type* s, size_type n); |
1326 | |
1327 | basic_fbstring& append(const value_type* s) { |
1328 | return append(s, traitsLength(s)); |
1329 | } |
1330 | |
1331 | basic_fbstring& append(size_type n, value_type c); |
1332 | |
1333 | template <class InputIterator> |
1334 | basic_fbstring& append(InputIterator first, InputIterator last) { |
1335 | insert(end(), first, last); |
1336 | return *this; |
1337 | } |
1338 | |
1339 | basic_fbstring& append(std::initializer_list<value_type> il) { |
1340 | return append(il.begin(), il.end()); |
1341 | } |
1342 | |
1343 | void push_back(const value_type c) { // primitive |
1344 | store_.push_back(c); |
1345 | } |
1346 | |
1347 | basic_fbstring& assign(const basic_fbstring& str) { |
1348 | if (&str == this) { |
1349 | return *this; |
1350 | } |
1351 | return assign(str.data(), str.size()); |
1352 | } |
1353 | |
1354 | basic_fbstring& assign(basic_fbstring&& str) { |
1355 | return *this = std::move(str); |
1356 | } |
1357 | |
1358 | basic_fbstring& |
1359 | assign(const basic_fbstring& str, const size_type pos, size_type n); |
1360 | |
1361 | basic_fbstring& assign(const value_type* s, const size_type n); |
1362 | |
1363 | basic_fbstring& assign(const value_type* s) { |
1364 | return assign(s, traitsLength(s)); |
1365 | } |
1366 | |
1367 | basic_fbstring& assign(std::initializer_list<value_type> il) { |
1368 | return assign(il.begin(), il.end()); |
1369 | } |
1370 | |
1371 | template <class ItOrLength, class ItOrChar> |
1372 | basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) { |
1373 | return replace(begin(), end(), first_or_n, last_or_c); |
1374 | } |
1375 | |
1376 | basic_fbstring& insert(size_type pos1, const basic_fbstring& str) { |
1377 | return insert(pos1, str.data(), str.size()); |
1378 | } |
1379 | |
1380 | basic_fbstring& insert( |
1381 | size_type pos1, |
1382 | const basic_fbstring& str, |
1383 | size_type pos2, |
1384 | size_type n) { |
1385 | enforce<std::out_of_range>(pos2 <= str.length(), "" ); |
1386 | procrustes(n, str.length() - pos2); |
1387 | return insert(pos1, str.data() + pos2, n); |
1388 | } |
1389 | |
1390 | basic_fbstring& insert(size_type pos, const value_type* s, size_type n) { |
1391 | enforce<std::out_of_range>(pos <= length(), "" ); |
1392 | insert(begin() + pos, s, s + n); |
1393 | return *this; |
1394 | } |
1395 | |
1396 | basic_fbstring& insert(size_type pos, const value_type* s) { |
1397 | return insert(pos, s, traitsLength(s)); |
1398 | } |
1399 | |
1400 | basic_fbstring& insert(size_type pos, size_type n, value_type c) { |
1401 | enforce<std::out_of_range>(pos <= length(), "" ); |
1402 | insert(begin() + pos, n, c); |
1403 | return *this; |
1404 | } |
1405 | |
1406 | iterator insert(const_iterator p, const value_type c) { |
1407 | const size_type pos = p - cbegin(); |
1408 | insert(p, 1, c); |
1409 | return begin() + pos; |
1410 | } |
1411 | |
1412 | private: |
1413 | typedef std::basic_istream<value_type, traits_type> istream_type; |
1414 | istream_type& getlineImpl(istream_type& is, value_type delim); |
1415 | |
1416 | public: |
1417 | friend inline istream_type& |
1418 | getline(istream_type& is, basic_fbstring& str, value_type delim) { |
1419 | return str.getlineImpl(is, delim); |
1420 | } |
1421 | |
1422 | friend inline istream_type& getline(istream_type& is, basic_fbstring& str) { |
1423 | return getline(is, str, '\n'); |
1424 | } |
1425 | |
1426 | private: |
1427 | iterator |
1428 | insertImplDiscr(const_iterator i, size_type n, value_type c, std::true_type); |
1429 | |
1430 | template <class InputIter> |
1431 | iterator |
1432 | insertImplDiscr(const_iterator i, InputIter b, InputIter e, std::false_type); |
1433 | |
1434 | template <class FwdIterator> |
1435 | iterator insertImpl( |
1436 | const_iterator i, |
1437 | FwdIterator s1, |
1438 | FwdIterator s2, |
1439 | std::forward_iterator_tag); |
1440 | |
1441 | template <class InputIterator> |
1442 | iterator insertImpl( |
1443 | const_iterator i, |
1444 | InputIterator b, |
1445 | InputIterator e, |
1446 | std::input_iterator_tag); |
1447 | |
1448 | public: |
1449 | template <class ItOrLength, class ItOrChar> |
1450 | iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) { |
1451 | using Sel = bool_constant<std::numeric_limits<ItOrLength>::is_specialized>; |
1452 | return insertImplDiscr(p, first_or_n, last_or_c, Sel()); |
1453 | } |
1454 | |
1455 | iterator insert(const_iterator p, std::initializer_list<value_type> il) { |
1456 | return insert(p, il.begin(), il.end()); |
1457 | } |
1458 | |
1459 | basic_fbstring& erase(size_type pos = 0, size_type n = npos) { |
1460 | Invariant checker(*this); |
1461 | |
1462 | enforce<std::out_of_range>(pos <= length(), "" ); |
1463 | procrustes(n, length() - pos); |
1464 | std::copy(begin() + pos + n, end(), begin() + pos); |
1465 | resize(length() - n); |
1466 | return *this; |
1467 | } |
1468 | |
1469 | iterator erase(iterator position) { |
1470 | const size_type pos(position - begin()); |
1471 | enforce<std::out_of_range>(pos <= size(), "" ); |
1472 | erase(pos, 1); |
1473 | return begin() + pos; |
1474 | } |
1475 | |
1476 | iterator erase(iterator first, iterator last) { |
1477 | const size_type pos(first - begin()); |
1478 | erase(pos, last - first); |
1479 | return begin() + pos; |
1480 | } |
1481 | |
1482 | // Replaces at most n1 chars of *this, starting with pos1 with the |
1483 | // content of str |
1484 | basic_fbstring& |
1485 | replace(size_type pos1, size_type n1, const basic_fbstring& str) { |
1486 | return replace(pos1, n1, str.data(), str.size()); |
1487 | } |
1488 | |
1489 | // Replaces at most n1 chars of *this, starting with pos1, |
1490 | // with at most n2 chars of str starting with pos2 |
1491 | basic_fbstring& replace( |
1492 | size_type pos1, |
1493 | size_type n1, |
1494 | const basic_fbstring& str, |
1495 | size_type pos2, |
1496 | size_type n2) { |
1497 | enforce<std::out_of_range>(pos2 <= str.length(), "" ); |
1498 | return replace( |
1499 | pos1, n1, str.data() + pos2, std::min(n2, str.size() - pos2)); |
1500 | } |
1501 | |
1502 | // Replaces at most n1 chars of *this, starting with pos, with chars from s |
1503 | basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) { |
1504 | return replace(pos, n1, s, traitsLength(s)); |
1505 | } |
1506 | |
1507 | // Replaces at most n1 chars of *this, starting with pos, with n2 |
1508 | // occurrences of c |
1509 | // |
1510 | // consolidated with |
1511 | // |
1512 | // Replaces at most n1 chars of *this, starting with pos, with at |
1513 | // most n2 chars of str. str must have at least n2 chars. |
1514 | template <class StrOrLength, class NumOrChar> |
1515 | basic_fbstring& |
1516 | replace(size_type pos, size_type n1, StrOrLength s_or_n2, NumOrChar n_or_c) { |
1517 | Invariant checker(*this); |
1518 | |
1519 | enforce<std::out_of_range>(pos <= size(), "" ); |
1520 | procrustes(n1, length() - pos); |
1521 | const iterator b = begin() + pos; |
1522 | return replace(b, b + n1, s_or_n2, n_or_c); |
1523 | } |
1524 | |
1525 | basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) { |
1526 | return replace(i1, i2, str.data(), str.length()); |
1527 | } |
1528 | |
1529 | basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) { |
1530 | return replace(i1, i2, s, traitsLength(s)); |
1531 | } |
1532 | |
1533 | private: |
1534 | basic_fbstring& replaceImplDiscr( |
1535 | iterator i1, |
1536 | iterator i2, |
1537 | const value_type* s, |
1538 | size_type n, |
1539 | std::integral_constant<int, 2>); |
1540 | |
1541 | basic_fbstring& replaceImplDiscr( |
1542 | iterator i1, |
1543 | iterator i2, |
1544 | size_type n2, |
1545 | value_type c, |
1546 | std::integral_constant<int, 1>); |
1547 | |
1548 | template <class InputIter> |
1549 | basic_fbstring& replaceImplDiscr( |
1550 | iterator i1, |
1551 | iterator i2, |
1552 | InputIter b, |
1553 | InputIter e, |
1554 | std::integral_constant<int, 0>); |
1555 | |
1556 | private: |
1557 | template <class FwdIterator> |
1558 | bool replaceAliased( |
1559 | iterator /* i1 */, |
1560 | iterator /* i2 */, |
1561 | FwdIterator /* s1 */, |
1562 | FwdIterator /* s2 */, |
1563 | std::false_type) { |
1564 | return false; |
1565 | } |
1566 | |
1567 | template <class FwdIterator> |
1568 | bool replaceAliased( |
1569 | iterator i1, |
1570 | iterator i2, |
1571 | FwdIterator s1, |
1572 | FwdIterator s2, |
1573 | std::true_type); |
1574 | |
1575 | template <class FwdIterator> |
1576 | void replaceImpl( |
1577 | iterator i1, |
1578 | iterator i2, |
1579 | FwdIterator s1, |
1580 | FwdIterator s2, |
1581 | std::forward_iterator_tag); |
1582 | |
1583 | template <class InputIterator> |
1584 | void replaceImpl( |
1585 | iterator i1, |
1586 | iterator i2, |
1587 | InputIterator b, |
1588 | InputIterator e, |
1589 | std::input_iterator_tag); |
1590 | |
1591 | public: |
1592 | template <class T1, class T2> |
1593 | basic_fbstring& |
1594 | replace(iterator i1, iterator i2, T1 first_or_n_or_s, T2 last_or_c_or_n) { |
1595 | constexpr bool num1 = std::numeric_limits<T1>::is_specialized, |
1596 | num2 = std::numeric_limits<T2>::is_specialized; |
1597 | using Sel = |
1598 | std::integral_constant<int, num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>; |
1599 | return replaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n, Sel()); |
1600 | } |
1601 | |
1602 | size_type copy(value_type* s, size_type n, size_type pos = 0) const { |
1603 | enforce<std::out_of_range>(pos <= size(), "" ); |
1604 | procrustes(n, size() - pos); |
1605 | |
1606 | if (n != 0) { |
1607 | fbstring_detail::podCopy(data() + pos, data() + pos + n, s); |
1608 | } |
1609 | return n; |
1610 | } |
1611 | |
1612 | void swap(basic_fbstring& rhs) { |
1613 | store_.swap(rhs.store_); |
1614 | } |
1615 | |
1616 | const value_type* c_str() const { |
1617 | return store_.c_str(); |
1618 | } |
1619 | |
1620 | const value_type* data() const { |
1621 | return c_str(); |
1622 | } |
1623 | |
1624 | value_type* data() { |
1625 | return store_.data(); |
1626 | } |
1627 | |
1628 | allocator_type get_allocator() const { |
1629 | return allocator_type(); |
1630 | } |
1631 | |
1632 | size_type find(const basic_fbstring& str, size_type pos = 0) const { |
1633 | return find(str.data(), pos, str.length()); |
1634 | } |
1635 | |
1636 | size_type find(const value_type* needle, size_type pos, size_type nsize) |
1637 | const; |
1638 | |
1639 | size_type find(const value_type* s, size_type pos = 0) const { |
1640 | return find(s, pos, traitsLength(s)); |
1641 | } |
1642 | |
1643 | size_type find(value_type c, size_type pos = 0) const { |
1644 | return find(&c, pos, 1); |
1645 | } |
1646 | |
1647 | size_type rfind(const basic_fbstring& str, size_type pos = npos) const { |
1648 | return rfind(str.data(), pos, str.length()); |
1649 | } |
1650 | |
1651 | size_type rfind(const value_type* s, size_type pos, size_type n) const; |
1652 | |
1653 | size_type rfind(const value_type* s, size_type pos = npos) const { |
1654 | return rfind(s, pos, traitsLength(s)); |
1655 | } |
1656 | |
1657 | size_type rfind(value_type c, size_type pos = npos) const { |
1658 | return rfind(&c, pos, 1); |
1659 | } |
1660 | |
1661 | size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const { |
1662 | return find_first_of(str.data(), pos, str.length()); |
1663 | } |
1664 | |
1665 | size_type find_first_of(const value_type* s, size_type pos, size_type n) |
1666 | const; |
1667 | |
1668 | size_type find_first_of(const value_type* s, size_type pos = 0) const { |
1669 | return find_first_of(s, pos, traitsLength(s)); |
1670 | } |
1671 | |
1672 | size_type find_first_of(value_type c, size_type pos = 0) const { |
1673 | return find_first_of(&c, pos, 1); |
1674 | } |
1675 | |
1676 | size_type find_last_of(const basic_fbstring& str, size_type pos = npos) |
1677 | const { |
1678 | return find_last_of(str.data(), pos, str.length()); |
1679 | } |
1680 | |
1681 | size_type find_last_of(const value_type* s, size_type pos, size_type n) const; |
1682 | |
1683 | size_type find_last_of(const value_type* s, size_type pos = npos) const { |
1684 | return find_last_of(s, pos, traitsLength(s)); |
1685 | } |
1686 | |
1687 | size_type find_last_of(value_type c, size_type pos = npos) const { |
1688 | return find_last_of(&c, pos, 1); |
1689 | } |
1690 | |
1691 | size_type find_first_not_of(const basic_fbstring& str, size_type pos = 0) |
1692 | const { |
1693 | return find_first_not_of(str.data(), pos, str.size()); |
1694 | } |
1695 | |
1696 | size_type find_first_not_of(const value_type* s, size_type pos, size_type n) |
1697 | const; |
1698 | |
1699 | size_type find_first_not_of(const value_type* s, size_type pos = 0) const { |
1700 | return find_first_not_of(s, pos, traitsLength(s)); |
1701 | } |
1702 | |
1703 | size_type find_first_not_of(value_type c, size_type pos = 0) const { |
1704 | return find_first_not_of(&c, pos, 1); |
1705 | } |
1706 | |
1707 | size_type find_last_not_of(const basic_fbstring& str, size_type pos = npos) |
1708 | const { |
1709 | return find_last_not_of(str.data(), pos, str.length()); |
1710 | } |
1711 | |
1712 | size_type find_last_not_of(const value_type* s, size_type pos, size_type n) |
1713 | const; |
1714 | |
1715 | size_type find_last_not_of(const value_type* s, size_type pos = npos) const { |
1716 | return find_last_not_of(s, pos, traitsLength(s)); |
1717 | } |
1718 | |
1719 | size_type find_last_not_of(value_type c, size_type pos = npos) const { |
1720 | return find_last_not_of(&c, pos, 1); |
1721 | } |
1722 | |
1723 | basic_fbstring substr(size_type pos = 0, size_type n = npos) const& { |
1724 | enforce<std::out_of_range>(pos <= size(), "" ); |
1725 | return basic_fbstring(data() + pos, std::min(n, size() - pos)); |
1726 | } |
1727 | |
1728 | basic_fbstring substr(size_type pos = 0, size_type n = npos) && { |
1729 | enforce<std::out_of_range>(pos <= size(), "" ); |
1730 | erase(0, pos); |
1731 | if (n < size()) { |
1732 | resize(n); |
1733 | } |
1734 | return std::move(*this); |
1735 | } |
1736 | |
1737 | int compare(const basic_fbstring& str) const { |
1738 | // FIX due to Goncalo N M de Carvalho July 18, 2005 |
1739 | return compare(0, size(), str); |
1740 | } |
1741 | |
1742 | int compare(size_type pos1, size_type n1, const basic_fbstring& str) const { |
1743 | return compare(pos1, n1, str.data(), str.size()); |
1744 | } |
1745 | |
1746 | int compare(size_type pos1, size_type n1, const value_type* s) const { |
1747 | return compare(pos1, n1, s, traitsLength(s)); |
1748 | } |
1749 | |
1750 | int compare(size_type pos1, size_type n1, const value_type* s, size_type n2) |
1751 | const { |
1752 | enforce<std::out_of_range>(pos1 <= size(), "" ); |
1753 | procrustes(n1, size() - pos1); |
1754 | // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks! |
1755 | const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2)); |
1756 | return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0; |
1757 | } |
1758 | |
1759 | int compare( |
1760 | size_type pos1, |
1761 | size_type n1, |
1762 | const basic_fbstring& str, |
1763 | size_type pos2, |
1764 | size_type n2) const { |
1765 | enforce<std::out_of_range>(pos2 <= str.size(), "" ); |
1766 | return compare( |
1767 | pos1, n1, str.data() + pos2, std::min(n2, str.size() - pos2)); |
1768 | } |
1769 | |
1770 | // Code from Jean-Francois Bastien (03/26/2007) |
1771 | int compare(const value_type* s) const { |
1772 | // Could forward to compare(0, size(), s, traitsLength(s)) |
1773 | // but that does two extra checks |
1774 | const size_type n1(size()), n2(traitsLength(s)); |
1775 | const int r = traits_type::compare(data(), s, std::min(n1, n2)); |
1776 | return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0; |
1777 | } |
1778 | |
1779 | private: |
1780 | // Data |
1781 | Storage store_; |
1782 | }; |
1783 | |
1784 | template <typename E, class T, class A, class S> |
1785 | FOLLY_NOINLINE inline typename basic_fbstring<E, T, A, S>::size_type |
1786 | basic_fbstring<E, T, A, S>::traitsLength(const value_type* s) { |
1787 | return s ? traits_type::length(s) |
1788 | : (throw_exception<std::logic_error>( |
1789 | "basic_fbstring: null pointer initializer not valid" ), |
1790 | 0); |
1791 | } |
1792 | |
1793 | template <typename E, class T, class A, class S> |
1794 | inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=( |
1795 | const basic_fbstring& lhs) { |
1796 | Invariant checker(*this); |
1797 | |
1798 | if (FOLLY_UNLIKELY(&lhs == this)) { |
1799 | return *this; |
1800 | } |
1801 | |
1802 | return assign(lhs.data(), lhs.size()); |
1803 | } |
1804 | |
1805 | // Move assignment |
1806 | template <typename E, class T, class A, class S> |
1807 | inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=( |
1808 | basic_fbstring&& goner) noexcept { |
1809 | if (FOLLY_UNLIKELY(&goner == this)) { |
1810 | // Compatibility with std::basic_string<>, |
1811 | // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support. |
1812 | return *this; |
1813 | } |
1814 | // No need of this anymore |
1815 | this->~basic_fbstring(); |
1816 | // Move the goner into this |
1817 | new (&store_) S(std::move(goner.store_)); |
1818 | return *this; |
1819 | } |
1820 | |
1821 | template <typename E, class T, class A, class S> |
1822 | inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=( |
1823 | value_type c) { |
1824 | Invariant checker(*this); |
1825 | |
1826 | if (empty()) { |
1827 | store_.expandNoinit(1); |
1828 | } else if (store_.isShared()) { |
1829 | basic_fbstring(1, c).swap(*this); |
1830 | return *this; |
1831 | } else { |
1832 | store_.shrink(size() - 1); |
1833 | } |
1834 | front() = c; |
1835 | return *this; |
1836 | } |
1837 | |
1838 | template <typename E, class T, class A, class S> |
1839 | inline void basic_fbstring<E, T, A, S>::resize( |
1840 | const size_type n, |
1841 | const value_type c /*= value_type()*/) { |
1842 | Invariant checker(*this); |
1843 | |
1844 | auto size = this->size(); |
1845 | if (n <= size) { |
1846 | store_.shrink(size - n); |
1847 | } else { |
1848 | auto const delta = n - size; |
1849 | auto pData = store_.expandNoinit(delta); |
1850 | fbstring_detail::podFill(pData, pData + delta, c); |
1851 | } |
1852 | assert(this->size() == n); |
1853 | } |
1854 | |
1855 | template <typename E, class T, class A, class S> |
1856 | inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append( |
1857 | const basic_fbstring& str) { |
1858 | #ifndef NDEBUG |
1859 | auto desiredSize = size() + str.size(); |
1860 | #endif |
1861 | append(str.data(), str.size()); |
1862 | assert(size() == desiredSize); |
1863 | return *this; |
1864 | } |
1865 | |
1866 | template <typename E, class T, class A, class S> |
1867 | inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append( |
1868 | const basic_fbstring& str, |
1869 | const size_type pos, |
1870 | size_type n) { |
1871 | const size_type sz = str.size(); |
1872 | enforce<std::out_of_range>(pos <= sz, "" ); |
1873 | procrustes(n, sz - pos); |
1874 | return append(str.data() + pos, n); |
1875 | } |
1876 | |
1877 | template <typename E, class T, class A, class S> |
1878 | FOLLY_NOINLINE inline basic_fbstring<E, T, A, S>& |
1879 | basic_fbstring<E, T, A, S>::append(const value_type* s, size_type n) { |
1880 | Invariant checker(*this); |
1881 | |
1882 | if (FOLLY_UNLIKELY(!n)) { |
1883 | // Unlikely but must be done |
1884 | return *this; |
1885 | } |
1886 | auto const oldSize = size(); |
1887 | auto const oldData = data(); |
1888 | auto pData = store_.expandNoinit(n, /* expGrowth = */ true); |
1889 | |
1890 | // Check for aliasing (rare). We could use "<=" here but in theory |
1891 | // those do not work for pointers unless the pointers point to |
1892 | // elements in the same array. For that reason we use |
1893 | // std::less_equal, which is guaranteed to offer a total order |
1894 | // over pointers. See discussion at http://goo.gl/Cy2ya for more |
1895 | // info. |
1896 | std::less_equal<const value_type*> le; |
1897 | if (FOLLY_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) { |
1898 | assert(le(s + n, oldData + oldSize)); |
1899 | // expandNoinit() could have moved the storage, restore the source. |
1900 | s = data() + (s - oldData); |
1901 | fbstring_detail::podMove(s, s + n, pData); |
1902 | } else { |
1903 | fbstring_detail::podCopy(s, s + n, pData); |
1904 | } |
1905 | |
1906 | assert(size() == oldSize + n); |
1907 | return *this; |
1908 | } |
1909 | |
1910 | template <typename E, class T, class A, class S> |
1911 | inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append( |
1912 | size_type n, |
1913 | value_type c) { |
1914 | Invariant checker(*this); |
1915 | auto pData = store_.expandNoinit(n, /* expGrowth = */ true); |
1916 | fbstring_detail::podFill(pData, pData + n, c); |
1917 | return *this; |
1918 | } |
1919 | |
1920 | template <typename E, class T, class A, class S> |
1921 | inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign( |
1922 | const basic_fbstring& str, |
1923 | const size_type pos, |
1924 | size_type n) { |
1925 | const size_type sz = str.size(); |
1926 | enforce<std::out_of_range>(pos <= sz, "" ); |
1927 | procrustes(n, sz - pos); |
1928 | return assign(str.data() + pos, n); |
1929 | } |
1930 | |
1931 | template <typename E, class T, class A, class S> |
1932 | FOLLY_NOINLINE inline basic_fbstring<E, T, A, S>& |
1933 | basic_fbstring<E, T, A, S>::assign(const value_type* s, const size_type n) { |
1934 | Invariant checker(*this); |
1935 | |
1936 | if (n == 0) { |
1937 | resize(0); |
1938 | } else if (size() >= n) { |
1939 | // s can alias this, we need to use podMove. |
1940 | fbstring_detail::podMove(s, s + n, store_.mutableData()); |
1941 | store_.shrink(size() - n); |
1942 | assert(size() == n); |
1943 | } else { |
1944 | // If n is larger than size(), s cannot alias this string's |
1945 | // storage. |
1946 | resize(0); |
1947 | // Do not use exponential growth here: assign() should be tight, |
1948 | // to mirror the behavior of the equivalent constructor. |
1949 | fbstring_detail::podCopy(s, s + n, store_.expandNoinit(n)); |
1950 | } |
1951 | |
1952 | assert(size() == n); |
1953 | return *this; |
1954 | } |
1955 | |
1956 | template <typename E, class T, class A, class S> |
1957 | inline typename basic_fbstring<E, T, A, S>::istream_type& |
1958 | basic_fbstring<E, T, A, S>::getlineImpl(istream_type& is, value_type delim) { |
1959 | Invariant checker(*this); |
1960 | |
1961 | clear(); |
1962 | size_t size = 0; |
1963 | while (true) { |
1964 | size_t avail = capacity() - size; |
1965 | // fbstring has 1 byte extra capacity for the null terminator, |
1966 | // and getline null-terminates the read string. |
1967 | is.getline(store_.expandNoinit(avail), avail + 1, delim); |
1968 | size += is.gcount(); |
1969 | |
1970 | if (is.bad() || is.eof() || !is.fail()) { |
1971 | // Done by either failure, end of file, or normal read. |
1972 | if (!is.bad() && !is.eof()) { |
1973 | --size; // gcount() also accounts for the delimiter. |
1974 | } |
1975 | resize(size); |
1976 | break; |
1977 | } |
1978 | |
1979 | assert(size == this->size()); |
1980 | assert(size == capacity()); |
1981 | // Start at minimum allocation 63 + terminator = 64. |
1982 | reserve(std::max<size_t>(63, 3 * size / 2)); |
1983 | // Clear the error so we can continue reading. |
1984 | is.clear(); |
1985 | } |
1986 | return is; |
1987 | } |
1988 | |
1989 | template <typename E, class T, class A, class S> |
1990 | inline typename basic_fbstring<E, T, A, S>::size_type |
1991 | basic_fbstring<E, T, A, S>::find( |
1992 | const value_type* needle, |
1993 | const size_type pos, |
1994 | const size_type nsize) const { |
1995 | auto const size = this->size(); |
1996 | // nsize + pos can overflow (eg pos == npos), guard against that by checking |
1997 | // that nsize + pos does not wrap around. |
1998 | if (nsize + pos > size || nsize + pos < pos) { |
1999 | return npos; |
2000 | } |
2001 | |
2002 | if (nsize == 0) { |
2003 | return pos; |
2004 | } |
2005 | // Don't use std::search, use a Boyer-Moore-like trick by comparing |
2006 | // the last characters first |
2007 | auto const haystack = data(); |
2008 | auto const nsize_1 = nsize - 1; |
2009 | auto const lastNeedle = needle[nsize_1]; |
2010 | |
2011 | // Boyer-Moore skip value for the last char in the needle. Zero is |
2012 | // not a valid value; skip will be computed the first time it's |
2013 | // needed. |
2014 | size_type skip = 0; |
2015 | |
2016 | const E* i = haystack + pos; |
2017 | auto iEnd = haystack + size - nsize_1; |
2018 | |
2019 | while (i < iEnd) { |
2020 | // Boyer-Moore: match the last element in the needle |
2021 | while (i[nsize_1] != lastNeedle) { |
2022 | if (++i == iEnd) { |
2023 | // not found |
2024 | return npos; |
2025 | } |
2026 | } |
2027 | // Here we know that the last char matches |
2028 | // Continue in pedestrian mode |
2029 | for (size_t j = 0;;) { |
2030 | assert(j < nsize); |
2031 | if (i[j] != needle[j]) { |
2032 | // Not found, we can skip |
2033 | // Compute the skip value lazily |
2034 | if (skip == 0) { |
2035 | skip = 1; |
2036 | while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) { |
2037 | ++skip; |
2038 | } |
2039 | } |
2040 | i += skip; |
2041 | break; |
2042 | } |
2043 | // Check if done searching |
2044 | if (++j == nsize) { |
2045 | // Yay |
2046 | return i - haystack; |
2047 | } |
2048 | } |
2049 | } |
2050 | return npos; |
2051 | } |
2052 | |
2053 | template <typename E, class T, class A, class S> |
2054 | inline typename basic_fbstring<E, T, A, S>::iterator |
2055 | basic_fbstring<E, T, A, S>::insertImplDiscr( |
2056 | const_iterator i, |
2057 | size_type n, |
2058 | value_type c, |
2059 | std::true_type) { |
2060 | Invariant checker(*this); |
2061 | |
2062 | assert(i >= cbegin() && i <= cend()); |
2063 | const size_type pos = i - cbegin(); |
2064 | |
2065 | auto oldSize = size(); |
2066 | store_.expandNoinit(n, /* expGrowth = */ true); |
2067 | auto b = begin(); |
2068 | fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n); |
2069 | fbstring_detail::podFill(b + pos, b + pos + n, c); |
2070 | |
2071 | return b + pos; |
2072 | } |
2073 | |
2074 | template <typename E, class T, class A, class S> |
2075 | template <class InputIter> |
2076 | inline typename basic_fbstring<E, T, A, S>::iterator |
2077 | basic_fbstring<E, T, A, S>::insertImplDiscr( |
2078 | const_iterator i, |
2079 | InputIter b, |
2080 | InputIter e, |
2081 | std::false_type) { |
2082 | return insertImpl( |
2083 | i, b, e, typename std::iterator_traits<InputIter>::iterator_category()); |
2084 | } |
2085 | |
2086 | template <typename E, class T, class A, class S> |
2087 | template <class FwdIterator> |
2088 | inline typename basic_fbstring<E, T, A, S>::iterator |
2089 | basic_fbstring<E, T, A, S>::insertImpl( |
2090 | const_iterator i, |
2091 | FwdIterator s1, |
2092 | FwdIterator s2, |
2093 | std::forward_iterator_tag) { |
2094 | Invariant checker(*this); |
2095 | |
2096 | assert(i >= cbegin() && i <= cend()); |
2097 | const size_type pos = i - cbegin(); |
2098 | auto n = std::distance(s1, s2); |
2099 | assert(n >= 0); |
2100 | |
2101 | auto oldSize = size(); |
2102 | store_.expandNoinit(n, /* expGrowth = */ true); |
2103 | auto b = begin(); |
2104 | fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n); |
2105 | std::copy(s1, s2, b + pos); |
2106 | |
2107 | return b + pos; |
2108 | } |
2109 | |
2110 | template <typename E, class T, class A, class S> |
2111 | template <class InputIterator> |
2112 | inline typename basic_fbstring<E, T, A, S>::iterator |
2113 | basic_fbstring<E, T, A, S>::insertImpl( |
2114 | const_iterator i, |
2115 | InputIterator b, |
2116 | InputIterator e, |
2117 | std::input_iterator_tag) { |
2118 | const auto pos = i - cbegin(); |
2119 | basic_fbstring temp(cbegin(), i); |
2120 | for (; b != e; ++b) { |
2121 | temp.push_back(*b); |
2122 | } |
2123 | temp.append(i, cend()); |
2124 | swap(temp); |
2125 | return begin() + pos; |
2126 | } |
2127 | |
2128 | template <typename E, class T, class A, class S> |
2129 | inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr( |
2130 | iterator i1, |
2131 | iterator i2, |
2132 | const value_type* s, |
2133 | size_type n, |
2134 | std::integral_constant<int, 2>) { |
2135 | assert(i1 <= i2); |
2136 | assert(begin() <= i1 && i1 <= end()); |
2137 | assert(begin() <= i2 && i2 <= end()); |
2138 | return replace(i1, i2, s, s + n); |
2139 | } |
2140 | |
2141 | template <typename E, class T, class A, class S> |
2142 | inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr( |
2143 | iterator i1, |
2144 | iterator i2, |
2145 | size_type n2, |
2146 | value_type c, |
2147 | std::integral_constant<int, 1>) { |
2148 | const size_type n1 = i2 - i1; |
2149 | if (n1 > n2) { |
2150 | std::fill(i1, i1 + n2, c); |
2151 | erase(i1 + n2, i2); |
2152 | } else { |
2153 | std::fill(i1, i2, c); |
2154 | insert(i2, n2 - n1, c); |
2155 | } |
2156 | assert(isSane()); |
2157 | return *this; |
2158 | } |
2159 | |
2160 | template <typename E, class T, class A, class S> |
2161 | template <class InputIter> |
2162 | inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr( |
2163 | iterator i1, |
2164 | iterator i2, |
2165 | InputIter b, |
2166 | InputIter e, |
2167 | std::integral_constant<int, 0>) { |
2168 | using Cat = typename std::iterator_traits<InputIter>::iterator_category; |
2169 | replaceImpl(i1, i2, b, e, Cat()); |
2170 | return *this; |
2171 | } |
2172 | |
2173 | template <typename E, class T, class A, class S> |
2174 | template <class FwdIterator> |
2175 | inline bool basic_fbstring<E, T, A, S>::replaceAliased( |
2176 | iterator i1, |
2177 | iterator i2, |
2178 | FwdIterator s1, |
2179 | FwdIterator s2, |
2180 | std::true_type) { |
2181 | std::less_equal<const value_type*> le{}; |
2182 | const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end()); |
2183 | if (!aliased) { |
2184 | return false; |
2185 | } |
2186 | // Aliased replace, copy to new string |
2187 | basic_fbstring temp; |
2188 | temp.reserve(size() - (i2 - i1) + std::distance(s1, s2)); |
2189 | temp.append(begin(), i1).append(s1, s2).append(i2, end()); |
2190 | swap(temp); |
2191 | return true; |
2192 | } |
2193 | |
2194 | template <typename E, class T, class A, class S> |
2195 | template <class FwdIterator> |
2196 | inline void basic_fbstring<E, T, A, S>::replaceImpl( |
2197 | iterator i1, |
2198 | iterator i2, |
2199 | FwdIterator s1, |
2200 | FwdIterator s2, |
2201 | std::forward_iterator_tag) { |
2202 | Invariant checker(*this); |
2203 | |
2204 | // Handle aliased replace |
2205 | using Sel = bool_constant< |
2206 | std::is_same<FwdIterator, iterator>::value || |
2207 | std::is_same<FwdIterator, const_iterator>::value>; |
2208 | if (replaceAliased(i1, i2, s1, s2, Sel())) { |
2209 | return; |
2210 | } |
2211 | |
2212 | auto const n1 = i2 - i1; |
2213 | assert(n1 >= 0); |
2214 | auto const n2 = std::distance(s1, s2); |
2215 | assert(n2 >= 0); |
2216 | |
2217 | if (n1 > n2) { |
2218 | // shrinks |
2219 | std::copy(s1, s2, i1); |
2220 | erase(i1 + n2, i2); |
2221 | } else { |
2222 | // grows |
2223 | s1 = fbstring_detail::copy_n(s1, n1, i1).first; |
2224 | insert(i2, s1, s2); |
2225 | } |
2226 | assert(isSane()); |
2227 | } |
2228 | |
2229 | template <typename E, class T, class A, class S> |
2230 | template <class InputIterator> |
2231 | inline void basic_fbstring<E, T, A, S>::replaceImpl( |
2232 | iterator i1, |
2233 | iterator i2, |
2234 | InputIterator b, |
2235 | InputIterator e, |
2236 | std::input_iterator_tag) { |
2237 | basic_fbstring temp(begin(), i1); |
2238 | temp.append(b, e).append(i2, end()); |
2239 | swap(temp); |
2240 | } |
2241 | |
2242 | template <typename E, class T, class A, class S> |
2243 | inline typename basic_fbstring<E, T, A, S>::size_type |
2244 | basic_fbstring<E, T, A, S>::rfind( |
2245 | const value_type* s, |
2246 | size_type pos, |
2247 | size_type n) const { |
2248 | if (n > length()) { |
2249 | return npos; |
2250 | } |
2251 | pos = std::min(pos, length() - n); |
2252 | if (n == 0) { |
2253 | return pos; |
2254 | } |
2255 | |
2256 | const_iterator i(begin() + pos); |
2257 | for (;; --i) { |
2258 | if (traits_type::eq(*i, *s) && traits_type::compare(&*i, s, n) == 0) { |
2259 | return i - begin(); |
2260 | } |
2261 | if (i == begin()) { |
2262 | break; |
2263 | } |
2264 | } |
2265 | return npos; |
2266 | } |
2267 | |
2268 | template <typename E, class T, class A, class S> |
2269 | inline typename basic_fbstring<E, T, A, S>::size_type |
2270 | basic_fbstring<E, T, A, S>::find_first_of( |
2271 | const value_type* s, |
2272 | size_type pos, |
2273 | size_type n) const { |
2274 | if (pos > length() || n == 0) { |
2275 | return npos; |
2276 | } |
2277 | const_iterator i(begin() + pos), finish(end()); |
2278 | for (; i != finish; ++i) { |
2279 | if (traits_type::find(s, n, *i) != nullptr) { |
2280 | return i - begin(); |
2281 | } |
2282 | } |
2283 | return npos; |
2284 | } |
2285 | |
2286 | template <typename E, class T, class A, class S> |
2287 | inline typename basic_fbstring<E, T, A, S>::size_type |
2288 | basic_fbstring<E, T, A, S>::find_last_of( |
2289 | const value_type* s, |
2290 | size_type pos, |
2291 | size_type n) const { |
2292 | if (!empty() && n > 0) { |
2293 | pos = std::min(pos, length() - 1); |
2294 | const_iterator i(begin() + pos); |
2295 | for (;; --i) { |
2296 | if (traits_type::find(s, n, *i) != nullptr) { |
2297 | return i - begin(); |
2298 | } |
2299 | if (i == begin()) { |
2300 | break; |
2301 | } |
2302 | } |
2303 | } |
2304 | return npos; |
2305 | } |
2306 | |
2307 | template <typename E, class T, class A, class S> |
2308 | inline typename basic_fbstring<E, T, A, S>::size_type |
2309 | basic_fbstring<E, T, A, S>::find_first_not_of( |
2310 | const value_type* s, |
2311 | size_type pos, |
2312 | size_type n) const { |
2313 | if (pos < length()) { |
2314 | const_iterator i(begin() + pos), finish(end()); |
2315 | for (; i != finish; ++i) { |
2316 | if (traits_type::find(s, n, *i) == nullptr) { |
2317 | return i - begin(); |
2318 | } |
2319 | } |
2320 | } |
2321 | return npos; |
2322 | } |
2323 | |
2324 | template <typename E, class T, class A, class S> |
2325 | inline typename basic_fbstring<E, T, A, S>::size_type |
2326 | basic_fbstring<E, T, A, S>::find_last_not_of( |
2327 | const value_type* s, |
2328 | size_type pos, |
2329 | size_type n) const { |
2330 | if (!this->empty()) { |
2331 | pos = std::min(pos, size() - 1); |
2332 | const_iterator i(begin() + pos); |
2333 | for (;; --i) { |
2334 | if (traits_type::find(s, n, *i) == nullptr) { |
2335 | return i - begin(); |
2336 | } |
2337 | if (i == begin()) { |
2338 | break; |
2339 | } |
2340 | } |
2341 | } |
2342 | return npos; |
2343 | } |
2344 | |
2345 | // non-member functions |
2346 | // C++11 21.4.8.1/1 |
2347 | template <typename E, class T, class A, class S> |
2348 | inline basic_fbstring<E, T, A, S> operator+( |
2349 | const basic_fbstring<E, T, A, S>& lhs, |
2350 | const basic_fbstring<E, T, A, S>& rhs) { |
2351 | basic_fbstring<E, T, A, S> result; |
2352 | result.reserve(lhs.size() + rhs.size()); |
2353 | result.append(lhs).append(rhs); |
2354 | return result; |
2355 | } |
2356 | |
2357 | // C++11 21.4.8.1/2 |
2358 | template <typename E, class T, class A, class S> |
2359 | inline basic_fbstring<E, T, A, S> operator+( |
2360 | basic_fbstring<E, T, A, S>&& lhs, |
2361 | const basic_fbstring<E, T, A, S>& rhs) { |
2362 | return std::move(lhs.append(rhs)); |
2363 | } |
2364 | |
2365 | // C++11 21.4.8.1/3 |
2366 | template <typename E, class T, class A, class S> |
2367 | inline basic_fbstring<E, T, A, S> operator+( |
2368 | const basic_fbstring<E, T, A, S>& lhs, |
2369 | basic_fbstring<E, T, A, S>&& rhs) { |
2370 | if (rhs.capacity() >= lhs.size() + rhs.size()) { |
2371 | // Good, at least we don't need to reallocate |
2372 | return std::move(rhs.insert(0, lhs)); |
2373 | } |
2374 | // Meh, no go. Forward to operator+(const&, const&). |
2375 | auto const& rhsC = rhs; |
2376 | return lhs + rhsC; |
2377 | } |
2378 | |
2379 | // C++11 21.4.8.1/4 |
2380 | template <typename E, class T, class A, class S> |
2381 | inline basic_fbstring<E, T, A, S> operator+( |
2382 | basic_fbstring<E, T, A, S>&& lhs, |
2383 | basic_fbstring<E, T, A, S>&& rhs) { |
2384 | return std::move(lhs.append(rhs)); |
2385 | } |
2386 | |
2387 | // C++11 21.4.8.1/5 |
2388 | template <typename E, class T, class A, class S> |
2389 | inline basic_fbstring<E, T, A, S> operator+( |
2390 | const E* lhs, |
2391 | const basic_fbstring<E, T, A, S>& rhs) { |
2392 | // |
2393 | basic_fbstring<E, T, A, S> result; |
2394 | const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs); |
2395 | result.reserve(len + rhs.size()); |
2396 | result.append(lhs, len).append(rhs); |
2397 | return result; |
2398 | } |
2399 | |
2400 | // C++11 21.4.8.1/6 |
2401 | template <typename E, class T, class A, class S> |
2402 | inline basic_fbstring<E, T, A, S> operator+( |
2403 | const E* lhs, |
2404 | basic_fbstring<E, T, A, S>&& rhs) { |
2405 | // |
2406 | const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs); |
2407 | if (rhs.capacity() >= len + rhs.size()) { |
2408 | // Good, at least we don't need to reallocate |
2409 | rhs.insert(rhs.begin(), lhs, lhs + len); |
2410 | return std::move(rhs); |
2411 | } |
2412 | // Meh, no go. Do it by hand since we have len already. |
2413 | basic_fbstring<E, T, A, S> result; |
2414 | result.reserve(len + rhs.size()); |
2415 | result.append(lhs, len).append(rhs); |
2416 | return result; |
2417 | } |
2418 | |
2419 | // C++11 21.4.8.1/7 |
2420 | template <typename E, class T, class A, class S> |
2421 | inline basic_fbstring<E, T, A, S> operator+( |
2422 | E lhs, |
2423 | const basic_fbstring<E, T, A, S>& rhs) { |
2424 | basic_fbstring<E, T, A, S> result; |
2425 | result.reserve(1 + rhs.size()); |
2426 | result.push_back(lhs); |
2427 | result.append(rhs); |
2428 | return result; |
2429 | } |
2430 | |
2431 | // C++11 21.4.8.1/8 |
2432 | template <typename E, class T, class A, class S> |
2433 | inline basic_fbstring<E, T, A, S> operator+( |
2434 | E lhs, |
2435 | basic_fbstring<E, T, A, S>&& rhs) { |
2436 | // |
2437 | if (rhs.capacity() > rhs.size()) { |
2438 | // Good, at least we don't need to reallocate |
2439 | rhs.insert(rhs.begin(), lhs); |
2440 | return std::move(rhs); |
2441 | } |
2442 | // Meh, no go. Forward to operator+(E, const&). |
2443 | auto const& rhsC = rhs; |
2444 | return lhs + rhsC; |
2445 | } |
2446 | |
2447 | // C++11 21.4.8.1/9 |
2448 | template <typename E, class T, class A, class S> |
2449 | inline basic_fbstring<E, T, A, S> operator+( |
2450 | const basic_fbstring<E, T, A, S>& lhs, |
2451 | const E* rhs) { |
2452 | typedef typename basic_fbstring<E, T, A, S>::size_type size_type; |
2453 | typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type; |
2454 | |
2455 | basic_fbstring<E, T, A, S> result; |
2456 | const size_type len = traits_type::length(rhs); |
2457 | result.reserve(lhs.size() + len); |
2458 | result.append(lhs).append(rhs, len); |
2459 | return result; |
2460 | } |
2461 | |
2462 | // C++11 21.4.8.1/10 |
2463 | template <typename E, class T, class A, class S> |
2464 | inline basic_fbstring<E, T, A, S> operator+( |
2465 | basic_fbstring<E, T, A, S>&& lhs, |
2466 | const E* rhs) { |
2467 | // |
2468 | return std::move(lhs += rhs); |
2469 | } |
2470 | |
2471 | // C++11 21.4.8.1/11 |
2472 | template <typename E, class T, class A, class S> |
2473 | inline basic_fbstring<E, T, A, S> operator+( |
2474 | const basic_fbstring<E, T, A, S>& lhs, |
2475 | E rhs) { |
2476 | basic_fbstring<E, T, A, S> result; |
2477 | result.reserve(lhs.size() + 1); |
2478 | result.append(lhs); |
2479 | result.push_back(rhs); |
2480 | return result; |
2481 | } |
2482 | |
2483 | // C++11 21.4.8.1/12 |
2484 | template <typename E, class T, class A, class S> |
2485 | inline basic_fbstring<E, T, A, S> operator+( |
2486 | basic_fbstring<E, T, A, S>&& lhs, |
2487 | E rhs) { |
2488 | // |
2489 | return std::move(lhs += rhs); |
2490 | } |
2491 | |
2492 | template <typename E, class T, class A, class S> |
2493 | inline bool operator==( |
2494 | const basic_fbstring<E, T, A, S>& lhs, |
2495 | const basic_fbstring<E, T, A, S>& rhs) { |
2496 | return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; |
2497 | } |
2498 | |
2499 | template <typename E, class T, class A, class S> |
2500 | inline bool operator==( |
2501 | const typename basic_fbstring<E, T, A, S>::value_type* lhs, |
2502 | const basic_fbstring<E, T, A, S>& rhs) { |
2503 | return rhs == lhs; |
2504 | } |
2505 | |
2506 | template <typename E, class T, class A, class S> |
2507 | inline bool operator==( |
2508 | const basic_fbstring<E, T, A, S>& lhs, |
2509 | const typename basic_fbstring<E, T, A, S>::value_type* rhs) { |
2510 | return lhs.compare(rhs) == 0; |
2511 | } |
2512 | |
2513 | template <typename E, class T, class A, class S> |
2514 | inline bool operator!=( |
2515 | const basic_fbstring<E, T, A, S>& lhs, |
2516 | const basic_fbstring<E, T, A, S>& rhs) { |
2517 | return !(lhs == rhs); |
2518 | } |
2519 | |
2520 | template <typename E, class T, class A, class S> |
2521 | inline bool operator!=( |
2522 | const typename basic_fbstring<E, T, A, S>::value_type* lhs, |
2523 | const basic_fbstring<E, T, A, S>& rhs) { |
2524 | return !(lhs == rhs); |
2525 | } |
2526 | |
2527 | template <typename E, class T, class A, class S> |
2528 | inline bool operator!=( |
2529 | const basic_fbstring<E, T, A, S>& lhs, |
2530 | const typename basic_fbstring<E, T, A, S>::value_type* rhs) { |
2531 | return !(lhs == rhs); |
2532 | } |
2533 | |
2534 | template <typename E, class T, class A, class S> |
2535 | inline bool operator<( |
2536 | const basic_fbstring<E, T, A, S>& lhs, |
2537 | const basic_fbstring<E, T, A, S>& rhs) { |
2538 | return lhs.compare(rhs) < 0; |
2539 | } |
2540 | |
2541 | template <typename E, class T, class A, class S> |
2542 | inline bool operator<( |
2543 | const basic_fbstring<E, T, A, S>& lhs, |
2544 | const typename basic_fbstring<E, T, A, S>::value_type* rhs) { |
2545 | return lhs.compare(rhs) < 0; |
2546 | } |
2547 | |
2548 | template <typename E, class T, class A, class S> |
2549 | inline bool operator<( |
2550 | const typename basic_fbstring<E, T, A, S>::value_type* lhs, |
2551 | const basic_fbstring<E, T, A, S>& rhs) { |
2552 | return rhs.compare(lhs) > 0; |
2553 | } |
2554 | |
2555 | template <typename E, class T, class A, class S> |
2556 | inline bool operator>( |
2557 | const basic_fbstring<E, T, A, S>& lhs, |
2558 | const basic_fbstring<E, T, A, S>& rhs) { |
2559 | return rhs < lhs; |
2560 | } |
2561 | |
2562 | template <typename E, class T, class A, class S> |
2563 | inline bool operator>( |
2564 | const basic_fbstring<E, T, A, S>& lhs, |
2565 | const typename basic_fbstring<E, T, A, S>::value_type* rhs) { |
2566 | return rhs < lhs; |
2567 | } |
2568 | |
2569 | template <typename E, class T, class A, class S> |
2570 | inline bool operator>( |
2571 | const typename basic_fbstring<E, T, A, S>::value_type* lhs, |
2572 | const basic_fbstring<E, T, A, S>& rhs) { |
2573 | return rhs < lhs; |
2574 | } |
2575 | |
2576 | template <typename E, class T, class A, class S> |
2577 | inline bool operator<=( |
2578 | const basic_fbstring<E, T, A, S>& lhs, |
2579 | const basic_fbstring<E, T, A, S>& rhs) { |
2580 | return !(rhs < lhs); |
2581 | } |
2582 | |
2583 | template <typename E, class T, class A, class S> |
2584 | inline bool operator<=( |
2585 | const basic_fbstring<E, T, A, S>& lhs, |
2586 | const typename basic_fbstring<E, T, A, S>::value_type* rhs) { |
2587 | return !(rhs < lhs); |
2588 | } |
2589 | |
2590 | template <typename E, class T, class A, class S> |
2591 | inline bool operator<=( |
2592 | const typename basic_fbstring<E, T, A, S>::value_type* lhs, |
2593 | const basic_fbstring<E, T, A, S>& rhs) { |
2594 | return !(rhs < lhs); |
2595 | } |
2596 | |
2597 | template <typename E, class T, class A, class S> |
2598 | inline bool operator>=( |
2599 | const basic_fbstring<E, T, A, S>& lhs, |
2600 | const basic_fbstring<E, T, A, S>& rhs) { |
2601 | return !(lhs < rhs); |
2602 | } |
2603 | |
2604 | template <typename E, class T, class A, class S> |
2605 | inline bool operator>=( |
2606 | const basic_fbstring<E, T, A, S>& lhs, |
2607 | const typename basic_fbstring<E, T, A, S>::value_type* rhs) { |
2608 | return !(lhs < rhs); |
2609 | } |
2610 | |
2611 | template <typename E, class T, class A, class S> |
2612 | inline bool operator>=( |
2613 | const typename basic_fbstring<E, T, A, S>::value_type* lhs, |
2614 | const basic_fbstring<E, T, A, S>& rhs) { |
2615 | return !(lhs < rhs); |
2616 | } |
2617 | |
2618 | // C++11 21.4.8.8 |
2619 | template <typename E, class T, class A, class S> |
2620 | void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) { |
2621 | lhs.swap(rhs); |
2622 | } |
2623 | |
2624 | // TODO: make this faster. |
2625 | template <typename E, class T, class A, class S> |
2626 | inline std::basic_istream< |
2627 | typename basic_fbstring<E, T, A, S>::value_type, |
2628 | typename basic_fbstring<E, T, A, S>::traits_type>& |
2629 | operator>>( |
2630 | std::basic_istream< |
2631 | typename basic_fbstring<E, T, A, S>::value_type, |
2632 | typename basic_fbstring<E, T, A, S>::traits_type>& is, |
2633 | basic_fbstring<E, T, A, S>& str) { |
2634 | typedef std::basic_istream< |
2635 | typename basic_fbstring<E, T, A, S>::value_type, |
2636 | typename basic_fbstring<E, T, A, S>::traits_type> |
2637 | _istream_type; |
2638 | typename _istream_type::sentry sentry(is); |
2639 | size_t = 0; |
2640 | typename _istream_type::iostate err = _istream_type::goodbit; |
2641 | if (sentry) { |
2642 | auto n = is.width(); |
2643 | if (n <= 0) { |
2644 | n = str.max_size(); |
2645 | } |
2646 | str.erase(); |
2647 | for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) { |
2648 | if (got == T::eof()) { |
2649 | err |= _istream_type::eofbit; |
2650 | is.width(0); |
2651 | break; |
2652 | } |
2653 | if (isspace(got)) { |
2654 | break; |
2655 | } |
2656 | str.push_back(got); |
2657 | got = is.rdbuf()->snextc(); |
2658 | } |
2659 | } |
2660 | if (!extracted) { |
2661 | err |= _istream_type::failbit; |
2662 | } |
2663 | if (err) { |
2664 | is.setstate(err); |
2665 | } |
2666 | return is; |
2667 | } |
2668 | |
2669 | template <typename E, class T, class A, class S> |
2670 | inline std::basic_ostream< |
2671 | typename basic_fbstring<E, T, A, S>::value_type, |
2672 | typename basic_fbstring<E, T, A, S>::traits_type>& |
2673 | operator<<( |
2674 | std::basic_ostream< |
2675 | typename basic_fbstring<E, T, A, S>::value_type, |
2676 | typename basic_fbstring<E, T, A, S>::traits_type>& os, |
2677 | const basic_fbstring<E, T, A, S>& str) { |
2678 | #if _LIBCPP_VERSION |
2679 | typedef std::basic_ostream< |
2680 | typename basic_fbstring<E, T, A, S>::value_type, |
2681 | typename basic_fbstring<E, T, A, S>::traits_type> |
2682 | _ostream_type; |
2683 | typename _ostream_type::sentry _s(os); |
2684 | if (_s) { |
2685 | typedef std::ostreambuf_iterator< |
2686 | typename basic_fbstring<E, T, A, S>::value_type, |
2687 | typename basic_fbstring<E, T, A, S>::traits_type> |
2688 | _Ip; |
2689 | size_t __len = str.size(); |
2690 | bool __left = |
2691 | (os.flags() & _ostream_type::adjustfield) == _ostream_type::left; |
2692 | if (__pad_and_output( |
2693 | _Ip(os), |
2694 | str.data(), |
2695 | __left ? str.data() + __len : str.data(), |
2696 | str.data() + __len, |
2697 | os, |
2698 | os.fill()) |
2699 | .failed()) { |
2700 | os.setstate(_ostream_type::badbit | _ostream_type::failbit); |
2701 | } |
2702 | } |
2703 | #elif defined(_MSC_VER) |
2704 | typedef decltype(os.precision()) streamsize; |
2705 | // MSVC doesn't define __ostream_insert |
2706 | os.write(str.data(), static_cast<streamsize>(str.size())); |
2707 | #else |
2708 | std::__ostream_insert(os, str.data(), str.size()); |
2709 | #endif |
2710 | return os; |
2711 | } |
2712 | |
2713 | template <typename E1, class T, class A, class S> |
2714 | constexpr typename basic_fbstring<E1, T, A, S>::size_type |
2715 | basic_fbstring<E1, T, A, S>::npos; |
2716 | |
2717 | // basic_string compatibility routines |
2718 | |
2719 | template <typename E, class T, class A, class S, class A2> |
2720 | inline bool operator==( |
2721 | const basic_fbstring<E, T, A, S>& lhs, |
2722 | const std::basic_string<E, T, A2>& rhs) { |
2723 | return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0; |
2724 | } |
2725 | |
2726 | template <typename E, class T, class A, class S, class A2> |
2727 | inline bool operator==( |
2728 | const std::basic_string<E, T, A2>& lhs, |
2729 | const basic_fbstring<E, T, A, S>& rhs) { |
2730 | return rhs == lhs; |
2731 | } |
2732 | |
2733 | template <typename E, class T, class A, class S, class A2> |
2734 | inline bool operator!=( |
2735 | const basic_fbstring<E, T, A, S>& lhs, |
2736 | const std::basic_string<E, T, A2>& rhs) { |
2737 | return !(lhs == rhs); |
2738 | } |
2739 | |
2740 | template <typename E, class T, class A, class S, class A2> |
2741 | inline bool operator!=( |
2742 | const std::basic_string<E, T, A2>& lhs, |
2743 | const basic_fbstring<E, T, A, S>& rhs) { |
2744 | return !(lhs == rhs); |
2745 | } |
2746 | |
2747 | template <typename E, class T, class A, class S, class A2> |
2748 | inline bool operator<( |
2749 | const basic_fbstring<E, T, A, S>& lhs, |
2750 | const std::basic_string<E, T, A2>& rhs) { |
2751 | return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) < 0; |
2752 | } |
2753 | |
2754 | template <typename E, class T, class A, class S, class A2> |
2755 | inline bool operator>( |
2756 | const basic_fbstring<E, T, A, S>& lhs, |
2757 | const std::basic_string<E, T, A2>& rhs) { |
2758 | return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) > 0; |
2759 | } |
2760 | |
2761 | template <typename E, class T, class A, class S, class A2> |
2762 | inline bool operator<( |
2763 | const std::basic_string<E, T, A2>& lhs, |
2764 | const basic_fbstring<E, T, A, S>& rhs) { |
2765 | return rhs > lhs; |
2766 | } |
2767 | |
2768 | template <typename E, class T, class A, class S, class A2> |
2769 | inline bool operator>( |
2770 | const std::basic_string<E, T, A2>& lhs, |
2771 | const basic_fbstring<E, T, A, S>& rhs) { |
2772 | return rhs < lhs; |
2773 | } |
2774 | |
2775 | template <typename E, class T, class A, class S, class A2> |
2776 | inline bool operator<=( |
2777 | const basic_fbstring<E, T, A, S>& lhs, |
2778 | const std::basic_string<E, T, A2>& rhs) { |
2779 | return !(lhs > rhs); |
2780 | } |
2781 | |
2782 | template <typename E, class T, class A, class S, class A2> |
2783 | inline bool operator>=( |
2784 | const basic_fbstring<E, T, A, S>& lhs, |
2785 | const std::basic_string<E, T, A2>& rhs) { |
2786 | return !(lhs < rhs); |
2787 | } |
2788 | |
2789 | template <typename E, class T, class A, class S, class A2> |
2790 | inline bool operator<=( |
2791 | const std::basic_string<E, T, A2>& lhs, |
2792 | const basic_fbstring<E, T, A, S>& rhs) { |
2793 | return !(lhs > rhs); |
2794 | } |
2795 | |
2796 | template <typename E, class T, class A, class S, class A2> |
2797 | inline bool operator>=( |
2798 | const std::basic_string<E, T, A2>& lhs, |
2799 | const basic_fbstring<E, T, A, S>& rhs) { |
2800 | return !(lhs < rhs); |
2801 | } |
2802 | |
2803 | typedef basic_fbstring<char> fbstring; |
2804 | |
2805 | // fbstring is relocatable |
2806 | template <class T, class R, class A, class S> |
2807 | FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>); |
2808 | |
2809 | } // namespace folly |
2810 | |
2811 | // Hash functions to make fbstring usable with e.g. unordered_map |
2812 | |
2813 | #define FOLLY_FBSTRING_HASH1(T) \ |
2814 | template <> \ |
2815 | struct hash<::folly::basic_fbstring<T>> { \ |
2816 | size_t operator()(const ::folly::basic_fbstring<T>& s) const { \ |
2817 | return ::folly::hash::fnv32_buf(s.data(), s.size() * sizeof(T)); \ |
2818 | } \ |
2819 | }; |
2820 | |
2821 | // The C++11 standard says that these four are defined for basic_string |
2822 | #define FOLLY_FBSTRING_HASH \ |
2823 | FOLLY_FBSTRING_HASH1(char) \ |
2824 | FOLLY_FBSTRING_HASH1(char16_t) \ |
2825 | FOLLY_FBSTRING_HASH1(char32_t) \ |
2826 | FOLLY_FBSTRING_HASH1(wchar_t) |
2827 | |
2828 | namespace std { |
2829 | |
2830 | FOLLY_FBSTRING_HASH |
2831 | |
2832 | } // namespace std |
2833 | |
2834 | #undef FOLLY_FBSTRING_HASH |
2835 | #undef FOLLY_FBSTRING_HASH1 |
2836 | |
2837 | FOLLY_POP_WARNING |
2838 | |
2839 | #undef FBSTRING_DISABLE_SSO |
2840 | |
2841 | namespace folly { |
2842 | template <class T> |
2843 | struct IsSomeString; |
2844 | |
2845 | template <> |
2846 | struct IsSomeString<fbstring> : std::true_type {}; |
2847 | } // namespace folly |
2848 | |