1 /*
2  * Copyright (c) 2024 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #ifndef API_BASE_CONTAINERS_STRING_H
17 #define API_BASE_CONTAINERS_STRING_H
18 
19 #include <cstddef>
20 #include <cstdint>
21 
22 #include <base/containers/allocator.h>
23 #include <base/containers/iterator.h>
24 #include <base/containers/string_view.h>
25 #include <base/containers/type_traits.h>
26 #include <base/namespace.h>
27 #include <base/util/log.h>
28 
29 BASE_BEGIN_NAMESPACE()
30 template<class CharT>
31 class basic_string;
32 
33 using string = BASE_NS::basic_string<char>;
34 using wstring = BASE_NS::basic_string<wchar_t>;
35 
36 template<class CharT>
37 class basic_string {
38 public:
39     using string_view = basic_string_view<CharT>;
40     using value_type = CharT;
41     using pointer = value_type*;
42     using const_pointer = const value_type*;
43     using reference = value_type&;
44     using const_reference = const value_type&;
45     using const_iterator = BASE_NS::const_iterator<basic_string>;
46     using iterator = BASE_NS::iterator<basic_string>;
47     using const_reverse_iterator = BASE_NS::reverse_iterator<const_iterator>;
48     using reverse_iterator = BASE_NS::reverse_iterator<iterator>;
49     using size_type = size_t;
50     using difference_type = ptrdiff_t;
51 
52     static constexpr size_type npos = size_type(-1);
53 
54     template<typename T>
55     using StringViewLikeNotCStr =
56         enable_if_t<is_convertible_v<const T&, string_view> && !is_convertible_v<const T&, const_pointer>>;
57 
58     template<typename T>
59     using StringViewLike = enable_if_t<is_convertible_v<const T&, string_view>>;
60 
basic_string()61     basic_string() noexcept : basic_string(default_allocator()) {}
62 
~basic_string()63     ~basic_string()
64     {
65         if (!is_short()) {
66             allocator_.free(data_.longString.begin);
67         }
68     }
69 
basic_string(allocator & alloc)70     explicit basic_string(allocator& alloc) noexcept : allocator_(alloc)
71     {
72         set_short(true);
73         data_.shortString.begin[1] = '\0';
74         data_.shortString.size = static_cast<value_type>(shortCapacity);
75     }
76 
basic_string(const basic_string & str)77     basic_string(const basic_string& str) : basic_string(str, default_allocator()) {}
78 
basic_string(const basic_string & str,allocator & alloc)79     basic_string(const basic_string& str, allocator& alloc) : allocator_(alloc)
80     {
81         if (str.data_.longString.isShort) {
82             data_.shortString = str.data_.shortString;
83         } else {
84             const auto len = str.data_.longString.size;
85             if (auto ptr = allocator_.alloc(len + 1); ptr) {
86                 // destination and source are valid and the allocation sizes are for at least len characters.
87                 CloneData(ptr, len * sizeof(value_type), str.data_.longString.begin, len * sizeof(value_type));
88                 ptr[len] = '\0';
89 
90                 data_.longString = str.data_.longString;
91                 data_.longString.capacity = len;
92                 data_.longString.begin = ptr;
93             } else {
94                 set_short(true);
95                 data_.shortString.begin[1] = '\0';
96                 data_.shortString.size = static_cast<value_type>(shortCapacity);
97             }
98         }
99     }
100 
basic_string(basic_string && a)101     basic_string(basic_string&& a) noexcept : allocator_(a.allocator_), data_(BASE_NS::move(a.data_))
102     {
103         a.set_short(true);
104         a.data_.shortString.begin[1] = '\0';
105         a.data_.shortString.size = static_cast<value_type>(shortCapacity);
106     }
107 
basic_string(const_pointer const str)108     basic_string(const_pointer const str) : basic_string(str, default_allocator()) {}
109 
basic_string(const_pointer const str,allocator & alloc)110     basic_string(const_pointer const str, allocator& alloc) : basic_string(str, constexpr_strlen(str), alloc) {}
111 
basic_string(const_pointer const str,size_type count)112     basic_string(const_pointer const str, size_type count) : basic_string(str, count, default_allocator()) {}
113 
basic_string(const_pointer const str,size_type count,allocator & alloc)114     basic_string(const_pointer const str, size_type count, allocator& alloc) : allocator_(alloc)
115     {
116         construct(str, count);
117     }
118 
basic_string(size_type count,const value_type a)119     basic_string(size_type count, const value_type a) : basic_string(count, a, default_allocator()) {}
120 
basic_string(size_type count,const value_type a,allocator & alloc)121     basic_string(size_type count, const value_type a, allocator& alloc) : allocator_(alloc)
122     {
123         set_short(true);
124         data_.shortString.size = static_cast<value_type>(shortCapacity);
125         assign(count, a);
126     }
127 
128     template<class StringT, class = StringViewLikeNotCStr<StringT>>
basic_string(const StringT & a)129     explicit basic_string(const StringT& a) : basic_string(a, default_allocator())
130     {}
131 
132     template<class StringT, class = StringViewLikeNotCStr<StringT>>
basic_string(const StringT & a,allocator & alloc)133     explicit basic_string(const StringT& a, allocator& alloc) : allocator_(alloc)
134     {
135         if constexpr (is_same_v<StringT, string_view>) {
136             construct(a.data(), a.size());
137         } else {
138             const auto view = string_view(a);
139             construct(view.data(), view.size());
140         }
141     }
142 
143     template<class StringT, class = StringViewLike<StringT>>
basic_string(const StringT & a,size_type pos,size_type n)144     basic_string(const StringT& a, size_type pos, size_type n) : basic_string(a, pos, n, default_allocator())
145     {}
146 
147     template<class StringT, class = StringViewLike<StringT>>
basic_string(const StringT & a,size_type pos,size_type n,allocator & alloc)148     basic_string(const StringT& a, size_type pos, size_type n, allocator& alloc)
149         : basic_string(string_view(a).substr(pos, n), alloc)
150     {}
151 
empty()152     bool empty() const noexcept
153     {
154         return !size();
155     }
156 
clear()157     void clear()
158     {
159         assign("", 0);
160     }
161 
back()162     value_type& back()
163     {
164         return *(data() + size() - 1);
165     }
166 
back()167     const value_type& back() const
168     {
169         return *(data() + size() - 1);
170     }
171 
front()172     value_type& front()
173     {
174         return *data();
175     }
176 
front()177     const value_type& front() const
178     {
179         return *data();
180     }
181 
capacity()182     size_type capacity() const noexcept
183     {
184         if (is_short()) {
185             return shortCapacity;
186         } else {
187             return data_.longString.capacity;
188         }
189     }
190 
length()191     size_type length() const noexcept
192     {
193         return size();
194     }
195 
size()196     size_type size() const noexcept
197     {
198         if (is_short()) {
199             return shortCapacity - data_.shortString.size;
200         } else {
201             return data_.longString.size;
202         }
203     }
204 
205     basic_string& operator=(const basic_string& a)
206     {
207         if (&a != this) {
208             assign(a.data(), a.length());
209         }
210         return *this;
211     }
212 
213     basic_string& operator=(basic_string&& a) noexcept
214     {
215         if (&a != this) {
216             if (!is_short()) {
217                 allocator_.free(data_.longString.begin);
218             }
219             allocator_ = a.allocator_;
220             data_ = BASE_NS::move(a.data_);
221 
222             a.set_short(true);
223             a.data_.shortString.begin[1] = '\0';
224             a.data_.shortString.size = static_cast<value_type>(shortCapacity);
225         }
226         return *this;
227     }
228 
229     basic_string& operator=(const value_type ch)
230     {
231         auto ptr = data();
232         *ptr++ = ch;
233         *ptr++ = '\0';
234         set_size(1);
235         return *this;
236     }
237 
238     basic_string& operator=(const_pointer const a)
239     {
240         if (data() != a) {
241             assign(a, constexpr_strlen(a));
242         }
243         return *this;
244     }
245 
246     template<class StringT, class = StringViewLikeNotCStr<StringT>>
247     basic_string& operator=(const StringT& a)
248     {
249         const auto view = string_view(a);
250         if (data() != view.data()) {
251             assign(view.data(), view.length());
252         } else {
253             resize(view.length());
254         }
255         return *this;
256     }
257 
assign(const_pointer const str)258     basic_string& assign(const_pointer const str)
259     {
260         const auto view = string_view(str);
261         return assign(view.data(), view.length());
262     }
263 
assign(const_pointer const str,size_type count)264     basic_string& assign(const_pointer const str, size_type count)
265     {
266         if (count) {
267             reserve(count);
268             const pointer dst = data();
269             const size_type cap = capacity();
270             if (static_cast<size_type>((dst > str) ? (dst - str) : (str - dst)) >= count) {
271                 CloneData(dst, cap * sizeof(value_type), str, count * sizeof(value_type));
272             } else {
273                 MoveData(dst, cap * sizeof(value_type), str, count * sizeof(value_type));
274             }
275             dst[count] = '\0';
276         } else {
277             const pointer dst = data();
278             *dst = '\0';
279         }
280         set_size(count);
281         return *this;
282     }
283 
assign(size_type count,value_type ch)284     basic_string& assign(size_type count, value_type ch)
285     {
286         if (count) {
287             reserve(count);
288             const pointer dst = data();
289             const size_type cap = capacity();
290             count = (count <= cap) ? count : cap;
291             // dst is valid, count fits capacity
292             ClearToValue(dst, cap * sizeof(value_type), static_cast<uint8_t>(ch), count * sizeof(value_type));
293             dst[count] = '\0';
294             set_size(count);
295         } else {
296             const pointer dst = data();
297             *dst = '\0';
298             set_size(0);
299         }
300         return *this;
301     }
302 
cbegin()303     const_iterator cbegin() const noexcept
304     {
305         return begin();
306     }
307 
cend()308     const_iterator cend() const noexcept
309     {
310         return end();
311     }
312 
begin()313     iterator begin() noexcept
314     {
315         return iterator(data());
316     }
317 
end()318     iterator end() noexcept
319     {
320         return iterator(data() + size());
321     }
322 
begin()323     const_iterator begin() const noexcept
324     {
325         return const_iterator(data());
326     }
327 
end()328     const_iterator end() const noexcept
329     {
330         return const_iterator(data() + size());
331     }
332 
data()333     pointer data() noexcept
334     {
335         if (is_short()) {
336             return data_.shortString.begin + 1;
337         } else {
338             return data_.longString.begin;
339         }
340     }
341 
data()342     const_pointer data() const noexcept
343     {
344         if (is_short()) {
345             return data_.shortString.begin + 1;
346         } else {
347             return data_.longString.begin;
348         }
349     }
350 
c_str()351     const_pointer c_str() const
352     {
353         return data();
354     }
355 
string_view()356     operator string_view() const noexcept
357     {
358         return string_view(data(), size());
359     }
360 
copy(pointer dst,size_type todo)361     size_type copy(pointer dst, size_type todo) const
362     {
363         if (const auto len = size(); todo > len) {
364             todo = len;
365         }
366         auto ptr = data();
367         const auto end = ptr + todo;
368         while (ptr != end) {
369             *dst++ = *ptr++;
370         }
371         return todo;
372     }
373 
reserve(size_type size)374     void reserve(size_type size)
375     {
376         if (size > capacity()) {
377             // setup new storage with old data
378             allocate(size);
379         }
380     }
381 
resize(size_type size,value_type ch)382     void resize(size_type size, value_type ch)
383     {
384         if (const auto oldSize = length(); size < oldSize) {
385             data()[size] = '\0';
386         } else if (size > oldSize) {
387             reserve(size);
388             const auto ptr = data() + oldSize;
389             const size_type cap = capacity();
390             size = (size <= cap) ? size : cap;
391             const auto count = size - oldSize;
392             // ptr is valid, count fits capacity
393             ClearToValue(ptr, cap * sizeof(value_type), static_cast<uint8_t>(ch), count * sizeof(value_type));
394             ptr[count] = '\0';
395         }
396 
397         set_size(size);
398     }
399 
resize(size_type size)400     void resize(size_type size)
401     {
402         resize(size, '\0');
403     }
404 
405     template<class StringT, class = StringViewLikeNotCStr<StringT>>
406     basic_string& operator+=(const StringT& a)
407     {
408         const auto view = string_view(a);
409         return append(view.data(), view.length());
410     }
411 
412     basic_string& operator+=(const value_type a)
413     {
414         return push_back(a);
415     }
416 
417     basic_string& operator+=(const_pointer const a)
418     {
419         return append(a, constexpr_strlen(a));
420     }
421 
422     const_reference operator[](size_type i) const
423     {
424         return data()[i];
425     }
426 
427     reference operator[](size_type i)
428     {
429         return data()[i];
430     }
431 
replace(const_iterator first,const_iterator last,const string_view & str)432     basic_string& replace(const_iterator first, const_iterator last, const string_view& str)
433     {
434         const auto pos = first - cbegin();
435         const auto replace = last - first;
436         const auto add = static_cast<difference_type>(str.length());
437         if (add < replace) {
438             CloneData(data() + pos, replace * sizeof(value_type), str.data(), add * sizeof(value_type));
439             erase(first + add, last);
440         } else if (add > replace) {
441             CloneData(data() + pos, replace * sizeof(value_type), str.data(), replace * sizeof(value_type));
442             insert(static_cast<size_type>(pos + replace), str.data() + replace, static_cast<size_type>(add - replace));
443         } else {
444             CloneData(data() + pos, replace * sizeof(value_type), str.data(), add * sizeof(value_type));
445         }
446         return *this;
447     }
448 
449     string_view substr(size_type pos = 0, size_type count = npos) const
450     {
451         return string_view(*this).substr(pos, count);
452     }
453 
erase()454     basic_string& erase()
455     {
456         return erase(0, npos);
457     }
458 
erase(const size_type off)459     basic_string& erase(const size_type off)
460     {
461         return erase(off, npos);
462     }
463 
erase(const size_type off,size_type count)464     basic_string& erase(const size_type off, size_type count)
465     {
466         const auto oldSize = size();
467         if (off > oldSize) {
468             return *this;
469         } else if (count == 0) {
470             return *this;
471         } else {
472             auto newSize = oldSize;
473             const auto dst = data() + off;
474             if (count < (oldSize - off)) {
475                 const auto dstSize = capacity() - off;
476                 const auto src = dst + count;
477                 const auto srcSize = oldSize + 1 - off - count;
478                 // dst and src are valid, dst < src, and srcSize doesn't exceed capacity.
479                 MoveData(dst, dstSize * sizeof(value_type), src, srcSize * sizeof(value_type));
480                 newSize -= count;
481             } else {
482                 *dst = '\0';
483                 newSize = off;
484             }
485 
486             set_size(newSize);
487         }
488         return *this;
489     }
490 
erase(const_iterator pos)491     iterator erase(const_iterator pos)
492     {
493         const auto offset = pos - cbegin();
494         const auto count = 1U;
495         erase(static_cast<size_type>(offset), count);
496 
497         return iterator(begin() + offset);
498     }
499 
erase(const_iterator first,const_iterator last)500     iterator erase(const_iterator first, const_iterator last)
501     {
502         const auto offset = first - cbegin();
503         const auto count = static_cast<size_type>(last - first);
504         erase(static_cast<size_type>(offset), count);
505 
506         return iterator(begin() + offset);
507     }
508 
insert(size_type pos,const_pointer str)509     basic_string& insert(size_type pos, const_pointer str)
510     {
511         const auto view = string_view(str);
512         return insert(pos, view.data(), view.length());
513     }
514 
insert(size_type pos,const_pointer str,size_type n)515     basic_string& insert(size_type pos, const_pointer str, size_type n)
516     {
517         const auto oldSize = size();
518         if (pos > oldSize) {
519             pos = oldSize;
520         }
521         const auto newSize = oldSize + n;
522         if (newSize > capacity()) {
523             const auto oldPtr = data();
524             const auto ptr = allocator_.alloc(newSize + 1);
525             CloneData(ptr, newSize * sizeof(value_type), oldPtr, pos * sizeof(value_type));
526             CloneData(ptr + pos + n, (newSize - pos - n) * sizeof(value_type), oldPtr + pos,
527                 (oldSize - pos) * sizeof(value_type));
528             CloneData(ptr + pos, (newSize - pos) * sizeof(value_type), str, n * sizeof(value_type));
529             ptr[newSize] = '\0';
530 
531             if (!is_short()) {
532                 allocator_.free(oldPtr);
533             }
534 
535             data_.longString.capacity = newSize;
536             data_.longString.size = newSize;
537             data_.longString.begin = ptr;
538             set_short(false);
539         } else {
540             auto ptr = data();
541             if (pos < oldSize) {
542                 auto dst = ptr + newSize;
543                 auto src = ptr + oldSize;
544                 auto count = oldSize + 1 - pos;
545                 while (count--) {
546                     *dst-- = *src--;
547                 }
548             }
549             CloneData(ptr + pos, (newSize - pos) * sizeof(value_type), str, n * sizeof(value_type));
550             ptr[newSize] = '\0';
551 
552             set_size(newSize);
553         }
554         return *this;
555     }
556 
push_back(value_type a)557     basic_string& push_back(value_type a)
558     {
559         const auto oldSize = size();
560         if (size_type cap = capacity(); oldSize == cap) {
561             if (!grow(1)) {
562                 return *this;
563             }
564         }
565 
566         const auto ptr = data();
567         ptr[oldSize] = a;
568         ptr[oldSize + 1] = '\0';
569         set_size(oldSize + 1);
570         return *this;
571     }
572 
append(size_type count,value_type a)573     basic_string& append(size_type count, value_type a)
574     {
575         if (count) {
576             const auto oldSize = size();
577             const auto newSize = oldSize + count;
578             if (size_type cap = capacity(); cap < newSize) {
579                 if (!grow(newSize)) {
580                     return *this;
581                 }
582             }
583 
584             const auto ptr = data();
585             for (auto i = ptr + oldSize; i != (ptr + newSize); ++i) {
586                 *i = a;
587             }
588             ptr[newSize] = '\0';
589 
590             set_size(newSize);
591         }
592         return *this;
593     }
594 
append(const_pointer const a)595     basic_string& append(const_pointer const a)
596     {
597         return append(a, constexpr_strlen(a));
598     }
599 
append(const_pointer const str,size_type count)600     basic_string& append(const_pointer const str, size_type count)
601     {
602         if (str && count) {
603             size_type oldSize;
604             size_type oldCapacity;
605             pointer dst;
606             if (is_short()) {
607                 oldSize = shortCapacity - data_.shortString.size;
608                 oldCapacity = shortCapacity;
609                 dst = data_.shortString.begin + 1;
610             } else {
611                 oldSize = data_.longString.size;
612                 oldCapacity = data_.longString.capacity;
613                 dst = data_.longString.begin;
614             }
615 
616             const auto newSize = oldSize + count;
617             if (oldCapacity < newSize) {
618                 oldCapacity += oldCapacity / 2;
619                 if (!allocate(newSize < oldCapacity ? oldCapacity : newSize)) {
620                     return *this;
621                 }
622                 dst = data_.longString.begin;
623                 oldCapacity = data_.longString.capacity;
624             }
625 
626             // dst and src are valid, oldSize + count is less than capacity.
627             CloneData(dst + oldSize, oldCapacity * sizeof(value_type), str, count * sizeof(value_type));
628             dst[newSize] = '\0';
629             set_size(newSize);
630         }
631         return *this;
632     }
633 
append(const string_view & b)634     basic_string& append(const string_view& b)
635     {
636         return append(b.data(), b.length());
637     }
638 
append(const string_view & b,size_type pos)639     basic_string& append(const string_view& b, size_type pos)
640     {
641         auto count = b.length();
642         count = (pos < count) ? (count - pos) : 0;
643         return append(b.data() + pos, count);
644     }
645 
append(const string_view & b,size_type pos,size_type count)646     basic_string& append(const string_view& b, size_type pos, size_type count)
647     {
648         auto const strLen = b.length();
649         if (pos > strLen) {
650             count = 0;
651             pos = strLen ? (strLen - 1) : strLen;
652         } else if (count == npos) {
653             count = strLen - pos;
654         } else if (count > (strLen - pos)) {
655             count = strLen - pos;
656         }
657         return append(b.data() + pos, count);
658     }
659 
660     /** compares two strings */
compare(string_view v)661     int compare(string_view v) const noexcept
662     {
663         return string_view(*this).compare(v);
664     }
665 
compare(size_type pos1,size_type count1,string_view v)666     int compare(size_type pos1, size_type count1, string_view v) const
667     {
668         return substr(pos1, count1).compare(v);
669     }
670 
compare(size_type pos1,size_type count1,string_view v,size_type pos2,size_type count2)671     int compare(size_type pos1, size_type count1, string_view v, size_type pos2, size_type count2) const
672     {
673         return substr(pos1, count1).compare(v.substr(pos2, count2));
674     }
675 
compare(CharT const * const s)676     int compare(CharT const* const s) const
677     {
678         return string_view(*this).compare(s);
679     }
680 
compare(size_type pos1,size_type count1,CharT const * const s)681     int compare(size_type pos1, size_type count1, CharT const* const s) const
682     {
683         return substr(pos1, count1).compare(s);
684     }
685 
compare(size_type pos1,size_type count1,CharT const * const s,size_type count2)686     int compare(size_type pos1, size_type count1, CharT const* const s, size_type count2) const
687     {
688         return substr(pos1, count1).compare(basic_string_view(s, count2));
689     }
690 
691     /** find substring in the view */
692     size_type find(const value_type str, size_type pos = 0) const noexcept
693     {
694         return string_view(*this).find(str, pos);
695     }
696 
697     size_type find(const string_view& str, size_type pos = 0) const noexcept
698     {
699         return string_view(*this).find(str, pos);
700     }
701 
702     /* find the last occurrence of a substring in the view */
703     size_type rfind(const value_type str, size_type pos = npos) const noexcept
704     {
705         return string_view(*this).rfind(str, pos);
706     }
707 
708     size_type rfind(const string_view& str, size_type pos = npos) const noexcept
709     {
710         return string_view(*this).rfind(str, pos);
711     }
712 
713     /* find first occurance of characters in the view */
714     size_type find_first_of(const string_view& str, size_type pos = 0) const noexcept
715     {
716         return string_view(*this).find_first_of(str, pos);
717     }
718 
719     size_type find_first_of(value_type ch, size_type pos = 0) const noexcept
720     {
721         return string_view(*this).find_first_of(ch, pos);
722     }
723 
724     /* find last occurrence of characters in the view */
725     size_type find_last_of(const string_view& str, size_type pos = npos) const noexcept
726     {
727         return string_view(*this).find_last_of(str, pos);
728     }
729 
730     size_type find_last_of(value_type ch, size_type pos = npos) const noexcept
731     {
732         return string_view(*this).find_last_of(ch, pos);
733     }
734 
735     /* checks if the string starts with the given prefix */
starts_with(basic_string_view<CharT> sv)736     bool starts_with(basic_string_view<CharT> sv) const noexcept
737     {
738         return operator basic_string_view<CharT>().starts_with(sv);
739     }
740 
starts_with(CharT ch)741     bool starts_with(CharT ch) const noexcept
742     {
743         return operator basic_string_view<CharT>().starts_with(ch);
744     }
745 
starts_with(const CharT * s)746     bool starts_with(const CharT* s) const
747     {
748         return operator basic_string_view<CharT>().starts_with(s);
749     }
750 
751     /* checks if the string ends with the given suffix */
ends_with(basic_string_view<CharT> sv)752     bool ends_with(basic_string_view<CharT> sv) const noexcept
753     {
754         return operator basic_string_view<CharT>().ends_with(sv);
755     }
756 
ends_with(CharT ch)757     bool ends_with(CharT ch) const noexcept
758     {
759         return operator basic_string_view<CharT>().ends_with(ch);
760     }
761 
ends_with(const CharT * s)762     bool ends_with(const CharT* s) const
763     {
764         return operator basic_string_view<CharT>().ends_with(s);
765     }
766     /* find first absence of characters
767     find_first_not_of
768 
769     find last absence of characters
770     find_last_not_of */
771 
upper()772     basic_string& upper()
773     {
774         for (size_type i = 0; i < length(); i++) {
775             if (data()[i] >= 'a' && data()[i] <= 'z') {
776                 data()[i] = (data()[i] - 'a') + 'A';
777             }
778         }
779         return *this;
780     }
781 
lower()782     basic_string& lower()
783     {
784         for (size_type i = 0; i < length(); i++) {
785             if (data()[i] >= 'A' && data()[i] <= 'Z') {
786                 data()[i] = (data()[i] - 'A') + 'a';
787             }
788         }
789         return *this;
790     }
791 
toUpper()792     basic_string toUpper() const
793     {
794         basic_string res;
795         res.resize(length());
796         for (size_type i = 0; i < length(); i++) {
797             if (data()[i] >= 'a' && data()[i] <= 'z') {
798                 res[i] = (data()[i] - 'a') + 'A';
799             } else {
800                 res[i] = data()[i];
801             }
802         }
803         return res;
804     }
805 
toLower()806     basic_string toLower() const
807     {
808         basic_string res;
809         res.resize(length());
810         for (size_type i = 0; i < length(); i++) {
811             if (data()[i] >= 'A' && data()[i] <= 'Z') {
812                 res[i] = (data()[i] - 'A') + 'a';
813             } else {
814                 res[i] = data()[i];
815             }
816         }
817         return res;
818     }
819 
820 protected:
is_short()821     inline bool is_short() const
822     {
823         return data_.longString.isShort;
824     }
825 
set_short(bool isShort)826     inline void set_short(bool isShort)
827     {
828         data_.longString.isShort = isShort;
829     }
830 
set_size(size_type size)831     inline void set_size(size_type size)
832     {
833         if (is_short()) {
834             data_.shortString.size = static_cast<value_type>(shortCapacity - size);
835         } else {
836             data_.longString.size = size;
837         }
838     }
839 
grow(const size_type minCapacity)840     inline bool grow(const size_type minCapacity)
841     {
842         auto cap = capacity();
843         cap += cap / 2;
844         return allocate(minCapacity < cap ? cap : minCapacity);
845     }
846 
allocate(size_type size)847     bool allocate(size_type size)
848     {
849         // setup new storage with old data
850         if (auto ptr = allocator_.alloc(size + 1); ptr) {
851             const auto oldSize = length();
852             if (oldSize) {
853                 CloneData(ptr, size * sizeof(value_type), data(), oldSize * sizeof(value_type));
854             }
855             ptr[oldSize] = '\0';
856 
857             if (!is_short()) {
858                 allocator_.free(data_.longString.begin);
859             }
860 
861             set_short(false);
862             data_.longString.capacity = size;
863             data_.longString.size = oldSize;
864             data_.longString.begin = ptr;
865             return true;
866         }
867         return false;
868     }
869 
construct(const_pointer const str,size_type count)870     void construct(const_pointer const str, size_type count)
871     {
872         if (!str || count == 0) {
873             set_short(true);
874             data_.shortString.begin[1] = '\0';
875             data_.shortString.size = static_cast<value_type>(shortCapacity);
876         } else {
877             pointer dst;
878             if (count <= shortCapacity) {
879                 dst = data_.shortString.begin + 1;
880                 set_short(true);
881                 data_.shortString.size = static_cast<value_type>(shortCapacity - count);
882             } else {
883                 dst = allocator_.alloc(count + 1);
884                 if (!dst) {
885                     set_short(true);
886                     data_.shortString.begin[1] = '\0';
887                     data_.shortString.size = static_cast<value_type>(shortCapacity);
888                     return;
889                 }
890                 set_short(false);
891                 data_.longString.capacity = count;
892                 data_.longString.size = count;
893                 data_.longString.begin = dst;
894             }
895             // destination and source are valid and the allocation sizes are for at least count characters.
896             CloneData(dst, count * sizeof(value_type), str, count * sizeof(value_type));
897             dst[count] = '\0';
898         }
899     }
900 
901     struct LongString {
902         bool isShort;
903         size_type capacity;
904         size_type size;
905         pointer begin;
906     };
907 
908     // short string capacity: one value_type for the size and another for isShort
909     static constexpr auto shortCapacity = (sizeof(LongString) - 2u * sizeof(value_type)) / sizeof(value_type);
910 
911     struct ShortString {
912         // add one for isShort in the begining
913         value_type begin[shortCapacity + 1];
914         value_type size;
915     };
916 
917     union Data {
918         LongString longString;
919         ShortString shortString;
920     };
921 
922     // Wrapper to create a "re-seatable" reference.
923     class Wrapper {
924     public:
Wrapper(allocator & a)925         inline Wrapper(allocator& a) : allocator_(&a) {}
926         inline Wrapper& operator=(allocator& a)
927         {
928             allocator_ = &a;
929             return *this;
930         }
alloc(size_type size)931         inline pointer alloc(size_type size)
932         {
933             if ((allocator_) && (allocator_->alloc)) {
934                 return static_cast<pointer>(allocator_->alloc(allocator_->instance, sizeof(value_type) * size));
935             }
936             return nullptr;
937         }
free(void * ptr)938         inline void free(void* ptr)
939         {
940             if ((allocator_) && (allocator_->free)) {
941                 allocator_->free(allocator_->instance, ptr);
942             }
943         }
get()944         allocator& get()
945         {
946             BASE_ASSERT(allocator_ != nullptr);
947             return *allocator_;
948         }
get()949         const allocator& get() const
950         {
951             BASE_ASSERT(allocator_ != nullptr);
952             return *allocator_;
953         }
954 
955     private:
956         allocator* allocator_ { nullptr };
957     } allocator_;
958     Data data_;
959 };
960 
961 inline string operator+(const string& a, const string& b)
962 {
963     string res;
964     res.reserve(a.length() + b.length());
965     res = a;
966     res += b;
967     return res;
968 }
969 
970 inline string operator+(const string& a, const char* b)
971 {
972     string res;
973     const auto sv = string_view(b);
974     res.reserve(a.length() + sv.length());
975     res = a;
976     res += sv;
977     return res;
978 }
979 
980 inline string operator+(const string& a, char b)
981 {
982     string res;
983     res.reserve(a.length() + 1);
984     res = a;
985     res += b;
986     return res;
987 }
988 
989 inline string operator+(const char* a, const string& b)
990 {
991     string res;
992     const auto sv = string_view(a);
993     res.reserve(sv.length() + b.length());
994     res = sv;
995     res += b;
996     return res;
997 }
998 
999 inline string operator+(char a, const string& b)
1000 {
1001     string res;
1002     res.reserve(1 + b.length());
1003     res = a;
1004     res += b;
1005     return res;
1006 }
1007 
1008 inline string operator+(const string_view& a, const string_view& b)
1009 {
1010     string res;
1011     res.reserve(a.length() + b.length());
1012     res = a;
1013     res += b;
1014     return res;
1015 }
1016 
1017 inline string operator+(const string_view& a, char b)
1018 {
1019     string res;
1020     res.reserve(a.length() + 1);
1021     res = a;
1022     res += b;
1023     return res;
1024 }
1025 
1026 inline string operator+(const char a, string_view& b)
1027 {
1028     string res;
1029     res.reserve(b.length() + 1);
1030     res = a;
1031     res += b;
1032     return res;
1033 }
1034 
1035 inline string operator+(string&& a, string&& b)
1036 {
1037     if (a.capacity() >= b.capacity()) {
1038         return move(a.append(b));
1039     } else {
1040         return move(b.insert(0, a.data(), a.size()));
1041     }
1042 }
1043 
1044 inline string operator+(string&& a, const char* b)
1045 {
1046     return move(a.append(b));
1047 }
1048 
1049 inline string operator+(string&& a, char b)
1050 {
1051     return move(a.push_back(b));
1052 }
1053 
1054 inline string operator+(const char* a, string&& b)
1055 {
1056     return move(b.insert(0, a));
1057 }
1058 
1059 inline string operator+(char a, string&& b)
1060 {
1061     return move(b.insert(0, &a, 1));
1062 }
1063 
1064 template<class CharT>
1065 inline bool operator==(const basic_string<CharT>& lhs, const basic_string<CharT>& rhs) noexcept
1066 {
1067     return string_view(lhs) == string_view(rhs);
1068 }
1069 
1070 template<class CharT>
1071 inline bool operator==(const basic_string<CharT>& lhs, const CharT* const rhs) noexcept
1072 {
1073     return string_view(lhs) == rhs;
1074 }
1075 
1076 template<class CharT>
1077 inline bool operator==(const CharT* const lhs, const basic_string<CharT>& rhs) noexcept
1078 {
1079     return lhs == string_view(rhs);
1080 }
1081 
1082 template<class CharT>
1083 inline bool operator!=(const basic_string<CharT>& lhs, const basic_string<CharT>& rhs) noexcept
1084 {
1085     return string_view(lhs) != string_view(rhs);
1086 }
1087 
1088 template<class CharT>
1089 inline bool operator!=(const basic_string<CharT>& lhs, const CharT* const rhs) noexcept
1090 {
1091     return string_view(lhs) != rhs;
1092 }
1093 
1094 template<class CharT>
1095 inline bool operator!=(const CharT* const lhs, const basic_string<CharT>& rhs) noexcept
1096 {
1097     return lhs != string_view(rhs);
1098 }
1099 
1100 template<class CharT>
1101 inline bool operator<(const basic_string<CharT>& lhs, const basic_string<CharT>& rhs) noexcept
1102 {
1103     return string_view(lhs) < string_view(rhs);
1104 }
1105 
1106 template<class CharT>
1107 inline bool operator<(const basic_string<CharT>& lhs, const CharT* const rhs) noexcept
1108 {
1109     return string_view(lhs) < rhs;
1110 }
1111 
1112 template<class CharT>
1113 inline bool operator<(const CharT* const lhs, const basic_string<CharT>& rhs) noexcept
1114 {
1115     return lhs < string_view(rhs);
1116 }
1117 
1118 template<class CharT>
1119 inline bool operator<=(const basic_string<CharT>& lhs, const basic_string<CharT>& rhs) noexcept
1120 {
1121     return string_view(lhs) <= string_view(rhs);
1122 }
1123 
1124 template<class CharT>
1125 inline bool operator<=(const basic_string<CharT>& lhs, const CharT* const rhs) noexcept
1126 {
1127     return string_view(lhs) <= rhs;
1128 }
1129 
1130 template<class CharT>
1131 inline bool operator<=(const CharT* const lhs, const basic_string<CharT>& rhs) noexcept
1132 {
1133     return lhs <= string_view(rhs);
1134 }
1135 
1136 template<class CharT>
1137 inline bool operator>(const basic_string<CharT>& lhs, const basic_string<CharT>& rhs) noexcept
1138 {
1139     return string_view(lhs) > string_view(rhs);
1140 }
1141 
1142 template<class CharT>
1143 inline bool operator>(const basic_string<CharT>& lhs, const CharT* const rhs) noexcept
1144 {
1145     return string_view(lhs) > rhs;
1146 }
1147 
1148 template<class CharT>
1149 inline bool operator>(const CharT* const lhs, const basic_string<CharT>& rhs) noexcept
1150 {
1151     return lhs > string_view(rhs);
1152 }
1153 
1154 template<class CharT>
1155 inline bool operator>=(const basic_string<CharT>& lhs, const basic_string<CharT>& rhs) noexcept
1156 {
1157     return string_view(lhs) >= string_view(rhs);
1158 }
1159 
1160 template<class CharT>
1161 inline bool operator>=(const basic_string<CharT>& lhs, const CharT* const rhs) noexcept
1162 {
1163     return string_view(lhs) >= rhs;
1164 }
1165 
1166 template<class CharT>
1167 inline bool operator>=(const CharT* const lhs, const basic_string<CharT>& rhs) noexcept
1168 {
1169     return lhs >= string_view(rhs);
1170 }
1171 
1172 template<typename T>
1173 uint64_t hash(const T&);
1174 
1175 template<>
hash(const string & value)1176 inline uint64_t hash(const string& value)
1177 {
1178     return BASE_NS::FNV1aHash(value.data(), value.size());
1179 }
1180 BASE_END_NAMESPACE()
1181 
1182 #endif // API_BASE_CONTAINERS_STRING_H
1183