1 /****************************************************************************
2 **
3 ** Copyright (C) 2016 The Qt Company Ltd.
4 ** Contact: https://www.qt.io/licensing/
5 **
6 ** This file is part of Qt Creator.
7 **
8 ** Commercial License Usage
9 ** Licensees holding valid commercial Qt licenses may use this file in
10 ** accordance with the commercial license agreement provided with the
11 ** Software or, alternatively, in accordance with the terms contained in
12 ** a written agreement between you and The Qt Company. For licensing terms
13 ** and conditions see https://www.qt.io/terms-conditions. For further
14 ** information use the contact form at https://www.qt.io/contact-us.
15 **
16 ** GNU General Public License Usage
17 ** Alternatively, this file may be used under the terms of the GNU
18 ** General Public License version 3 as published by the Free Software
19 ** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
20 ** included in the packaging of this file. Please review the following
21 ** information to ensure the GNU General Public License requirements will
22 ** be met: https://www.gnu.org/licenses/gpl-3.0.html.
23 **
24 ****************************************************************************/
25
26 #pragma once
27
28 #include "utils_global.h"
29
30 #include "smallstringliteral.h"
31 #include "smallstringiterator.h"
32 #include "smallstringview.h"
33 #include "smallstringmemory.h"
34
35 #include <QByteArray>
36 #include <QString>
37
38 #include <algorithm>
39 #include <cmath>
40 #include <cstdlib>
41 #include <climits>
42 #include <cstring>
43 #include <initializer_list>
44 #include <numeric>
45 #include <string>
46 #include <unordered_map>
47 #include <utility>
48 #include <vector>
49
50 #ifdef UNIT_TESTS
51 #define unittest_public public
52 #else
53 #define unittest_public private
54 #endif
55
56 #if defined(__GNUC__) && !defined(__clang__)
57 #pragma GCC diagnostic push
58 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
59 #endif
60
61 namespace Utils {
62
63 template<uint Size>
64 class BasicSmallString
65 {
66 public:
67 using const_iterator = Internal::SmallStringIterator<std::random_access_iterator_tag, const char>;
68 using iterator = Internal::SmallStringIterator<std::random_access_iterator_tag, char>;
69 using reverse_iterator = std::reverse_iterator<iterator>;
70 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
71 using size_type = std::size_t;
72
73 static_assert(Size < 64
74 ? sizeof(Internal::StringDataLayout<Size>) == Size + 1
75 : sizeof(Internal::StringDataLayout<Size>) == Size + 2,
76 "Size is wrong");
77 constexpr
BasicSmallString()78 BasicSmallString() noexcept
79 : m_data(Internal::StringDataLayout<Size>())
80 {
81 }
82
83 constexpr
BasicSmallString(const BasicSmallStringLiteral<Size> & stringReference)84 BasicSmallString(const BasicSmallStringLiteral<Size> &stringReference)
85 : m_data(stringReference.m_data)
86 {
87 }
88
89 template<size_type ArraySize>
90 constexpr
BasicSmallString(const char (& string)[ArraySize])91 BasicSmallString(const char(&string)[ArraySize])
92 : m_data(string)
93 {}
94
BasicSmallString(const char * string,size_type size,size_type capacity)95 BasicSmallString(const char *string, size_type size, size_type capacity)
96 {
97 if (Q_LIKELY(capacity <= shortStringCapacity())) {
98 std::char_traits<char>::copy(m_data.shortString.string, string, size);
99 m_data.shortString.string[size] = 0;
100 m_data.shortString.control.setShortStringSize(size);
101 m_data.shortString.control.setIsShortString(true);
102 m_data.shortString.control.setIsReadOnlyReference(false);
103 } else {
104 m_data.allocated.data.pointer = Memory::allocate(capacity + 1);
105 std::char_traits<char>::copy(m_data.allocated.data.pointer, string, size);
106 initializeLongString(size, capacity);
107 }
108 }
109
BasicSmallString(SmallStringView stringView)110 explicit BasicSmallString(SmallStringView stringView)
111 : BasicSmallString(stringView.data(), stringView.size(), stringView.size())
112 {}
113
BasicSmallString(const char * string,size_type size)114 BasicSmallString(const char *string, size_type size)
115 : BasicSmallString(string, size, size)
116 {}
117
BasicSmallString(const_iterator begin,const_iterator end)118 explicit BasicSmallString(const_iterator begin, const_iterator end)
119 : BasicSmallString{std::addressof(*begin), static_cast<std::size_t>(std::distance(begin, end))}
120 {}
121
BasicSmallString(iterator begin,iterator end)122 explicit BasicSmallString(iterator begin, iterator end)
123
124 : BasicSmallString{std::addressof(*begin), static_cast<std::size_t>(std::distance(begin, end))}
125 {}
126
127 template<typename Type, typename = std::enable_if_t<std::is_pointer<Type>::value>>
BasicSmallString(Type characterPointer)128 BasicSmallString(Type characterPointer)
129 : BasicSmallString(characterPointer, std::char_traits<char>::length(characterPointer))
130 {
131 static_assert(!std::is_array<Type>::value, "Input type is array and not char pointer!");
132 }
133
BasicSmallString(const QString & qString)134 BasicSmallString(const QString &qString)
135 : BasicSmallString(BasicSmallString::fromQString(qString))
136 {}
137
BasicSmallString(const QByteArray & qByteArray)138 BasicSmallString(const QByteArray &qByteArray)
139 : BasicSmallString(qByteArray.constData(), qByteArray.size())
140 {}
141
142 template<typename String,
143 typename Utils::enable_if_has_char_data_pointer<String> = 0>
BasicSmallString(const String & string)144 BasicSmallString(const String &string)
145 : BasicSmallString(string.data(), string.size())
146 {
147 }
148
149 template<typename BeginIterator,
150 typename EndIterator,
151 typename = std::enable_if_t<std::is_same<BeginIterator, EndIterator>::value>
152 >
BasicSmallString(BeginIterator begin,EndIterator end)153 BasicSmallString(BeginIterator begin, EndIterator end)
154 : BasicSmallString(&(*begin), size_type(end - begin))
155 {}
156
~BasicSmallString()157 ~BasicSmallString() noexcept
158 {
159 if (Q_UNLIKELY(hasAllocatedMemory()))
160 Memory::deallocate(m_data.allocated.data.pointer);
161 }
162
BasicSmallString(const BasicSmallString & string)163 BasicSmallString(const BasicSmallString &string)
164 {
165 if (string.isShortString() || string.isReadOnlyReference())
166 m_data = string.m_data;
167 else
168 new (this) BasicSmallString{string.data(), string.size()};
169 }
170
171 BasicSmallString &operator=(const BasicSmallString &other)
172 {
173 BasicSmallString copy = other;
174
175 swap(*this, copy);
176
177 return *this;
178 }
179
BasicSmallString(BasicSmallString && other)180 BasicSmallString(BasicSmallString &&other) noexcept
181 : m_data(std::move(other.m_data))
182 {
183 other.m_data.reset();
184 }
185
186 BasicSmallString &operator=(BasicSmallString &&other) noexcept
187 {
188 if (this == &other)
189 return *this;
190
191 this->~BasicSmallString();
192
193 m_data = std::move(other.m_data);
194 other.m_data.reset();
195
196 return *this;
197 }
198
clone()199 BasicSmallString clone() const
200 {
201 BasicSmallString clonedString(m_data);
202
203 if (Q_UNLIKELY(hasAllocatedMemory()))
204 new (&clonedString) BasicSmallString{m_data.allocated.data.pointer,
205 m_data.allocated.data.size,
206 m_data.allocated.data.capacity};
207
208 return clonedString;
209 }
210
swap(BasicSmallString & first,BasicSmallString & second)211 friend void swap(BasicSmallString &first, BasicSmallString &second) noexcept
212 {
213 using std::swap;
214
215 swap(first.m_data, second.m_data);
216 }
217
toQByteArray()218 QByteArray toQByteArray() const noexcept
219 {
220 return QByteArray(data(), int(size()));
221 }
222
toQString()223 QString toQString() const
224 {
225 return QString::fromUtf8(data(), int(size()));
226 }
227
toStringView()228 SmallStringView toStringView() const
229 {
230 return SmallStringView(data(), size());
231 }
232
SmallStringView()233 operator SmallStringView() const
234 {
235 return SmallStringView(data(), size());
236 }
237
238 explicit
QString()239 operator QString() const
240 {
241 return toQString();
242 }
243
244 explicit
string()245 operator std::string() const
246 {
247 return std::string(data(), size());
248 }
249
250 static
fromUtf8(const char * characterPointer)251 BasicSmallString fromUtf8(const char *characterPointer)
252 {
253 return BasicSmallString(characterPointer, std::char_traits<char>::length(characterPointer));
254 }
255
reserve(size_type newCapacity)256 void reserve(size_type newCapacity)
257 {
258 if (fitsNotInCapacity(newCapacity)) {
259 if (Q_UNLIKELY(hasAllocatedMemory())) {
260 m_data.allocated.data.pointer = Memory::reallocate(m_data.allocated.data.pointer,
261 newCapacity + 1);
262 m_data.allocated.data.capacity = newCapacity;
263 } else if (newCapacity <= shortStringCapacity()) {
264 new (this) BasicSmallString{m_data.allocated.data.pointer, m_data.allocated.data.size};
265 } else {
266 const size_type oldSize = size();
267 newCapacity = std::max(newCapacity, oldSize);
268 const char *oldData = data();
269
270 char *newData = Memory::allocate(newCapacity + 1);
271 std::char_traits<char>::copy(newData, oldData, oldSize);
272 m_data.allocated.data.pointer = newData;
273 initializeLongString(oldSize, newCapacity);
274 }
275 }
276 }
277
resize(size_type newSize)278 void resize(size_type newSize)
279 {
280 reserve(newSize);
281 setSize(newSize);
282 at(newSize) = 0;
283 }
284
clear()285 void clear() noexcept
286 {
287 this->~BasicSmallString();
288 m_data = Internal::StringDataLayout<Size>();
289 }
290
data()291 char *data() noexcept
292 {
293 return Q_LIKELY(isShortString()) ? m_data.shortString.string : m_data.allocated.data.pointer;
294 }
295
data()296 const char *data() const noexcept
297 {
298 return Q_LIKELY(isShortString()) ? m_data.shortString.string : m_data.allocated.data.pointer;
299 }
300
constData()301 const char *constData() const noexcept
302 {
303 return data();
304 }
305
begin()306 iterator begin() noexcept
307 {
308 return data();
309 }
310
end()311 iterator end() noexcept
312 {
313 return data() + size();
314 }
315
rbegin()316 reverse_iterator rbegin() noexcept
317 {
318 return reverse_iterator(end());
319 }
320
rend()321 reverse_iterator rend() noexcept
322 {
323 return reverse_iterator(begin());
324 }
325
rbegin()326 const_reverse_iterator rbegin() const noexcept
327 {
328 return const_reverse_iterator(end());
329 }
330
rend()331 const_reverse_iterator rend() const noexcept
332 {
333 return const_reverse_iterator(begin());
334 }
335
begin()336 const_iterator begin() const noexcept
337 {
338 return constData();
339 }
340
end()341 const_iterator end() const noexcept
342 {
343 return data() + size();
344 }
345
cbegin()346 const_iterator cbegin() const noexcept
347 {
348 return begin();
349 }
350
cend()351 const_iterator cend() const noexcept
352 {
353 return end();
354 }
355
356 static
fromQString(const QString & qString)357 BasicSmallString fromQString(const QString &qString)
358 {
359 const QByteArray &utf8ByteArray = qString.toUtf8();
360
361 return BasicSmallString(utf8ByteArray.constData(), uint(utf8ByteArray.size()));
362 }
363
364 static
fromQByteArray(const QByteArray & utf8ByteArray)365 BasicSmallString fromQByteArray(const QByteArray &utf8ByteArray)
366 {
367 return BasicSmallString(utf8ByteArray.constData(), uint(utf8ByteArray.size()));
368 }
369
370 // precondition: has to be null terminated
contains(SmallStringView subStringToSearch)371 bool contains(SmallStringView subStringToSearch) const
372 {
373 const char *found = std::strstr(data(), subStringToSearch.data());
374
375 return found != nullptr;
376 }
377
contains(char characterToSearch)378 bool contains(char characterToSearch) const
379 {
380 auto found = std::char_traits<char>::find(data(), size(), characterToSearch);
381
382 return found != nullptr;
383 }
384
startsWith(SmallStringView subStringToSearch)385 bool startsWith(SmallStringView subStringToSearch) const noexcept
386 {
387 if (size() >= subStringToSearch.size())
388 return !std::char_traits<char>::compare(data(),
389 subStringToSearch.data(),
390 subStringToSearch.size());
391
392 return false;
393 }
394
startsWith(char characterToSearch)395 bool startsWith(char characterToSearch) const noexcept
396 {
397 return data()[0] == characterToSearch;
398 }
399
endsWith(SmallStringView subStringToSearch)400 bool endsWith(SmallStringView subStringToSearch) const noexcept
401 {
402 if (size() >= subStringToSearch.size()) {
403 const int comparison = std::char_traits<char>::compare(end().data()
404 - subStringToSearch.size(),
405 subStringToSearch.data(),
406 subStringToSearch.size());
407 return comparison == 0;
408 }
409
410 return false;
411 }
412
endsWith(char character)413 bool endsWith(char character) const noexcept
414 {
415 return at(size() - 1) == character;
416 }
417
size()418 size_type size() const noexcept
419 {
420 if (!isShortString())
421 return m_data.allocated.data.size;
422
423 return m_data.shortString.control.shortStringSize();
424 }
425
capacity()426 size_type capacity() const noexcept
427 {
428 if (!isShortString())
429 return m_data.allocated.data.capacity;
430
431 return shortStringCapacity();
432 }
433
isEmpty()434 bool isEmpty() const noexcept
435 {
436 return size() == 0;
437 }
438
empty()439 bool empty() const noexcept
440 {
441 return isEmpty();
442 }
443
hasContent()444 bool hasContent() const noexcept
445 {
446 return size() != 0;
447 }
448
mid(size_type position)449 SmallStringView mid(size_type position) const noexcept
450 {
451 return SmallStringView(data() + position, size() - position);
452 }
453
mid(size_type position,size_type length)454 SmallStringView mid(size_type position, size_type length) const noexcept
455 {
456 return SmallStringView(data() + position, length);
457 }
458
append(SmallStringView string)459 void append(SmallStringView string)
460 {
461 size_type oldSize = size();
462 size_type newSize = oldSize + string.size();
463
464 reserve(optimalCapacity(newSize));
465 std::char_traits<char>::copy(data() + oldSize, string.data(), string.size());
466 at(newSize) = 0;
467 setSize(newSize);
468 }
469
470 BasicSmallString &operator+=(SmallStringView string)
471 {
472 append(string);
473
474 return *this;
475 }
476
477 BasicSmallString &operator+=(std::initializer_list<SmallStringView> list)
478 {
479 appendInitializerList(list, size());
480
481 return *this;
482 }
483
replace(SmallStringView fromText,SmallStringView toText)484 void replace(SmallStringView fromText, SmallStringView toText)
485 {
486 if (toText.size() == fromText.size())
487 replaceEqualSized(fromText, toText);
488 else if (toText.size() < fromText.size())
489 replaceSmallerSized(fromText, toText);
490 else
491 replaceLargerSized(fromText, toText);
492 }
493
replace(char fromCharacter,char toCharacter)494 void replace(char fromCharacter, char toCharacter)
495 {
496 reserve(size());
497
498 std::replace(begin(), end(), fromCharacter, toCharacter);
499 }
500
replace(size_type position,size_type length,SmallStringView replacementText)501 void replace(size_type position, size_type length, SmallStringView replacementText)
502 {
503 size_type newSize = size() - length + replacementText.size();
504
505 reserve(optimalCapacity(newSize));
506
507 auto replaceStart = begin() + position;
508 auto replaceEnd = replaceStart + length;
509 auto replacementEnd = replaceStart + replacementText.size();
510 size_type tailSize = size_type(end() - replaceEnd + 1);
511
512 std::memmove(replacementEnd.data(),
513 replaceEnd.data(), tailSize);
514 std::memcpy(replaceStart.data(), replacementText.data(), replacementText.size());
515
516 setSize(newSize);
517 }
518
toCarriageReturnsStripped()519 BasicSmallString toCarriageReturnsStripped() const
520 {
521 BasicSmallString text = *this;
522
523 text.replace("\r", "");
524
525 return text;
526 }
527
528 constexpr static
shortStringCapacity()529 size_type shortStringCapacity() noexcept
530 {
531 return Internal::StringDataLayout<Size>::shortStringCapacity();
532 }
533
optimalCapacity(const size_type size)534 size_type optimalCapacity(const size_type size)
535 {
536 if (fitsNotInCapacity(size))
537 return optimalHeapCapacity(size + 1) - 1;
538
539 return size;
540 }
541
542 constexpr
shortStringSize()543 size_type shortStringSize() const
544 {
545 return m_data.shortString.control.shortStringSize();
546 }
547
548 static
join(std::initializer_list<SmallStringView> list)549 BasicSmallString join(std::initializer_list<SmallStringView> list)
550 {
551 size_type totalSize = 0;
552 for (SmallStringView string : list)
553 totalSize += string.size();
554
555 BasicSmallString joinedString;
556 joinedString.reserve(totalSize);
557
558 for (SmallStringView string : list)
559 joinedString.append(string);
560
561 return joinedString;
562 }
563
564 static
number(int number)565 BasicSmallString number(int number)
566 {
567 char buffer[12];
568 std::size_t size = itoa(number, buffer, 10);
569
570 return BasicSmallString(buffer, size);
571 }
572
573 static
number(long long int number)574 BasicSmallString number(long long int number)
575 {
576 char buffer[22];
577 std::size_t size = itoa(number, buffer, 10);
578
579 return BasicSmallString(buffer, size);
580 }
581
582 static
number(double number)583 BasicSmallString number(double number)
584 {
585 return std::to_string(number);
586 }
587
588 char &operator[](std::size_t index)
589 {
590 return *(data() + index);
591 }
592
593 char operator[](std::size_t index) const
594 {
595 return *(data() + index);
596 }
597
598 friend BasicSmallString operator+(const BasicSmallString &first, const BasicSmallString &second)
599 {
600 BasicSmallString text;
601 text.reserve(first.size() + second.size());
602
603 text.append(first);
604 text.append(second);
605
606 return text;
607 }
608
609 friend BasicSmallString operator+(const BasicSmallString &first, SmallStringView second)
610 {
611 BasicSmallString text;
612 text.reserve(first.size() + second.size());
613
614 text.append(first);
615 text.append(second);
616
617 return text;
618 }
619
620 friend BasicSmallString operator+(SmallStringView first, const BasicSmallString &second)
621 {
622 BasicSmallString text;
623 text.reserve(first.size() + second.size());
624
625 text.append(first);
626 text.append(second);
627
628 return text;
629 }
630
631 template<size_type ArraySize>
632 friend BasicSmallString operator+(const BasicSmallString &first, const char(&second)[ArraySize])
633 {
634
635 return operator+(first, SmallStringView(second));
636 }
637
638 template<size_type ArraySize>
639 friend BasicSmallString operator+(const char(&first)[ArraySize], const BasicSmallString &second)
640 {
641 return operator+(SmallStringView(first), second);
642 }
643
644 unittest_public:
645 constexpr
isShortString()646 bool isShortString() const noexcept
647 {
648 return m_data.shortString.control.isShortString();
649 }
650
651 constexpr
isReadOnlyReference()652 bool isReadOnlyReference() const noexcept
653 {
654 return m_data.shortString.control.isReadOnlyReference();
655 }
656
657 constexpr
hasAllocatedMemory()658 bool hasAllocatedMemory() const noexcept
659 {
660 return !isShortString() && !isReadOnlyReference();
661 }
662
fitsNotInCapacity(size_type capacity)663 bool fitsNotInCapacity(size_type capacity) const noexcept
664 {
665 return (isShortString() && capacity > shortStringCapacity())
666 || (!isShortString() && capacity > m_data.allocated.data.capacity);
667 }
668
669 static
optimalHeapCapacity(const size_type size)670 size_type optimalHeapCapacity(const size_type size)
671 {
672 const size_type cacheLineSize = 64;
673
674 size_type cacheLineBlocks = (size - 1) / cacheLineSize;
675
676 return (cacheLineBlocks + 1) * cacheLineSize;
677 }
678
countOccurrence(SmallStringView text)679 size_type countOccurrence(SmallStringView text)
680 {
681 auto found = begin();
682
683 size_type count = 0;
684
685 while (true) {
686 found = std::search(found,
687 end(),
688 text.begin(),
689 text.end());
690 if (found == end())
691 break;
692
693 ++count;
694 found += text.size();
695 }
696
697 return count;
698 }
699
700 private:
BasicSmallString(const Internal::StringDataLayout<Size> & data)701 BasicSmallString(const Internal::StringDataLayout<Size> &data) noexcept
702 : m_data(data)
703 {
704 }
705
appendInitializerList(std::initializer_list<SmallStringView> list,std::size_t initialSize)706 void appendInitializerList(std::initializer_list<SmallStringView> list, std::size_t initialSize)
707 {
708 auto addSize = [] (std::size_t size, SmallStringView string) {
709 return size + string.size();
710 };
711
712 std::size_t size = std::accumulate(list.begin(), list.end(), initialSize, addSize);
713
714 reserve(size);
715 setSize(size);
716
717 char *currentData = data() + initialSize;
718
719 for (SmallStringView string : list) {
720 std::memcpy(currentData, string.data(), string.size());
721 currentData += string.size();
722 }
723
724 at(size) = 0;
725 }
726
initializeLongString(size_type size,size_type capacity)727 constexpr void initializeLongString(size_type size, size_type capacity)
728 {
729 m_data.allocated.data.pointer[size] = 0;
730 m_data.allocated.data.size = size;
731 m_data.allocated.data.capacity = capacity;
732 m_data.shortString.control.setShortStringSize(0);
733 m_data.shortString.control.setIsReference(true);
734 m_data.shortString.control.setIsReadOnlyReference(false);
735 }
736
at(size_type index)737 char &at(size_type index)
738 {
739 return *(data() + index);
740 }
741
at(size_type index)742 char at(size_type index) const
743 {
744 return *(data() + index);
745 }
746
replaceEqualSized(SmallStringView fromText,SmallStringView toText)747 void replaceEqualSized(SmallStringView fromText, SmallStringView toText)
748 {
749 reserve(size());
750
751 auto start = begin();
752 auto found = std::search(start,
753 end(),
754 fromText.begin(),
755 fromText.end());
756
757 while (found != end()) {
758 start = found + toText.size();
759
760 std::char_traits<char>::copy(found.data(), toText.data(), toText.size());
761
762 found = std::search(start,
763 end(),
764 fromText.begin(),
765 fromText.end());
766
767 }
768 }
769
replaceSmallerSized(SmallStringView fromText,SmallStringView toText)770 void replaceSmallerSized(SmallStringView fromText, SmallStringView toText)
771 {
772 auto found = std::search(begin(),
773 end(),
774 fromText.begin(),
775 fromText.end());
776
777 if (found != end()) {
778 size_type newSize = size();
779 {
780 size_type foundIndex = found - begin();
781 reserve(newSize);
782 found = begin() + foundIndex;
783 }
784 size_type sizeDifference = 0;
785
786 while (found != end()) {
787 auto start = found + fromText.size();
788
789 auto nextFound = std::search(start,
790 end(),
791 fromText.begin(),
792 fromText.end());
793
794 auto replacedTextEndPosition = found + fromText.size();
795 auto replacementTextEndPosition = found + toText.size() - sizeDifference;
796 auto replacementTextStartPosition = found - sizeDifference;
797 std::memmove(replacementTextEndPosition.data(),
798 replacedTextEndPosition.data(),
799 std::distance(start, nextFound));
800 std::memcpy(replacementTextStartPosition.data(), toText.data(), toText.size());
801
802 sizeDifference += fromText.size() - toText.size();
803 found = nextFound;
804 }
805
806 newSize -= sizeDifference;
807 setSize(newSize);
808 at(newSize) = '\0';
809 }
810 }
811
replaceLargerSizedRecursive(size_type startIndex,SmallStringView fromText,SmallStringView toText,size_type sizeDifference)812 iterator replaceLargerSizedRecursive(size_type startIndex,
813 SmallStringView fromText,
814 SmallStringView toText,
815 size_type sizeDifference)
816 {
817 auto found = std::search(begin() + startIndex,
818 end(),
819 fromText.begin(),
820 fromText.end());
821
822 auto foundIndex = found - begin();
823
824 if (found != end()) {
825 size_type startNextSearchIndex = foundIndex + fromText.size();
826 size_type newSizeDifference = sizeDifference + (toText.size() - fromText.size());
827
828 auto nextFound = replaceLargerSizedRecursive(startNextSearchIndex,
829 fromText,
830 toText,
831 newSizeDifference);
832
833 auto startFound = begin() + foundIndex;
834 auto endOfFound = begin() + startNextSearchIndex;
835
836 auto replacedTextEndPosition = endOfFound;
837 auto replacementTextEndPosition = endOfFound + newSizeDifference;
838 auto replacementTextStartPosition = startFound + sizeDifference;
839
840 std::memmove(replacementTextEndPosition.data(),
841 replacedTextEndPosition.data(),
842 std::distance(endOfFound, nextFound));
843 std::memcpy(replacementTextStartPosition.data(), toText.data(), toText.size());
844 } else if (startIndex != 0) {
845 size_type newSize = size() + sizeDifference;
846 setSize(newSize);
847 at(newSize) = 0;
848 }
849
850 return begin() + foundIndex;
851 }
852
replaceLargerSized(SmallStringView fromText,SmallStringView toText)853 void replaceLargerSized(SmallStringView fromText, SmallStringView toText)
854 {
855 size_type sizeDifference = 0;
856 size_type startIndex = 0;
857
858 size_type replacementTextSizeDifference = toText.size() - fromText.size();
859 size_type occurrences = countOccurrence(fromText);
860 size_type newSize = size() + (replacementTextSizeDifference * occurrences);
861
862 if (occurrences > 0) {
863 reserve(optimalCapacity(newSize));
864
865 replaceLargerSizedRecursive(startIndex, fromText, toText, sizeDifference);
866 }
867 }
868
setSize(size_type size)869 void setSize(size_type size)
870 {
871 if (isShortString())
872 m_data.shortString.control.setShortStringSize(size);
873 else
874 m_data.allocated.data.size = size;
875 }
876
877 static
itoa(long long int number,char * string,uint base)878 std::size_t itoa(long long int number, char* string, uint base)
879 {
880 using llint = long long int;
881 using lluint = long long unsigned int;
882 std::size_t size = 0;
883 bool isNegative = false;
884 lluint unsignedNumber = 0;
885
886 if (number == 0)
887 {
888 string[size] = '0';
889 string[++size] = '\0';
890
891 return size;
892 }
893
894 if (number < 0 && base == 10)
895 {
896 isNegative = true;
897 if (number == std::numeric_limits<llint>::min())
898 unsignedNumber = lluint(std::numeric_limits<llint>::max()) + 1;
899 else
900 unsignedNumber = lluint(-number);
901 } else {
902 unsignedNumber = lluint(number);
903 }
904
905 while (unsignedNumber != 0)
906 {
907 int remainder = int(unsignedNumber % base);
908 string[size++] = (remainder > 9) ? char((remainder - 10) + 'a') : char(remainder + '0');
909 unsignedNumber /= base;
910 }
911
912 if (isNegative)
913 string[size++] = '-';
914
915 string[size] = '\0';
916
917 std::reverse(string, string+size);
918
919 return size;
920 }
921
922 private:
923 Internal::StringDataLayout<Size> m_data;
924 };
925
926 template<template<uint> class String, uint Size>
927 using isSameString = std::is_same<std::remove_reference_t<std::remove_cv_t<String<Size>>>,
928 BasicSmallString<Size>>;
929
930 template<typename Key,
931 typename Value,
932 typename Hash = std::hash<Key>,
933 typename KeyEqual = std::equal_to<Key>,
934 typename Allocator = std::allocator<std::pair<const Key, Value>>>
935 std::unordered_map<Key, Value, Hash, KeyEqual, Allocator>
clone(const std::unordered_map<Key,Value,Hash,KeyEqual,Allocator> & map)936 clone(const std::unordered_map<Key, Value, Hash, KeyEqual, Allocator> &map)
937 {
938 std::unordered_map<Key, Value, Hash, KeyEqual, Allocator> clonedMap;
939 clonedMap.reserve(clonedMap.size());
940
941 for (auto &&entry : map)
942 clonedMap.emplace(entry.first, entry.second.clone());
943
944 return clonedMap;
945 }
946
947 template<typename Type>
clone(const Type & vector)948 Type clone(const Type &vector)
949 {
950 return vector;
951 }
952
953 using SmallString = BasicSmallString<31>;
954 using PathString = BasicSmallString<190>;
955
956 inline
957 SmallString operator+(SmallStringView first, SmallStringView second)
958 {
959 SmallString text;
960 text.reserve(first.size() + second.size());
961
962 text.append(first);
963 text.append(second);
964
965 return text;
966 }
967
968 template<std::size_t Size>
969 inline
970 SmallString operator+(SmallStringView first, const char(&second)[Size])
971 {
972 return operator+(first, SmallStringView(second));
973 }
974
975 template<std::size_t Size>
976 inline
977 SmallString operator+(const char(&first)[Size], SmallStringView second)
978 {
979 return operator+(SmallStringView(first), second);
980 }
981
982 } // namespace Utils
983
984 #if defined(__GNUC__) && !defined(__clang__)
985 #pragma GCC diagnostic pop
986 #endif
987