1 //===-- A simple implementation of the string class -------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #ifndef LLVM_LIBC_SRC___SUPPORT_CPP_STRING_H
10 #define LLVM_LIBC_SRC___SUPPORT_CPP_STRING_H
11
12 #include "hdr/func/free.h"
13 #include "hdr/func/malloc.h"
14 #include "hdr/func/realloc.h"
15 #include "src/__support/CPP/string_view.h"
16 #include "src/__support/integer_to_string.h" // IntegerToString
17 #include "src/__support/macros/config.h"
18 #include "src/string/memory_utils/inline_memcpy.h"
19 #include "src/string/memory_utils/inline_memset.h"
20 #include "src/string/string_utils.h" // string_length
21
22 #include <stddef.h> // size_t
23
24 namespace LIBC_NAMESPACE_DECL {
25 namespace cpp {
26
27 // This class mimics std::string but does not intend to be a full fledged
28 // implementation. Most notably it does not provide support for character traits
29 // nor custom allocator.
30 class string {
31 private:
32 static constexpr char NULL_CHARACTER = '\0';
get_empty_string()33 static constexpr char *get_empty_string() {
34 return const_cast<char *>(&NULL_CHARACTER);
35 }
36
37 char *buffer_ = get_empty_string();
38 size_t size_ = 0;
39 size_t capacity_ = 0;
40
reset_no_deallocate()41 constexpr void reset_no_deallocate() {
42 buffer_ = get_empty_string();
43 size_ = 0;
44 capacity_ = 0;
45 }
46
set_size_and_add_null_character(size_t size)47 void set_size_and_add_null_character(size_t size) {
48 size_ = size;
49 if (buffer_ != get_empty_string())
50 buffer_[size_] = NULL_CHARACTER;
51 }
52
53 public:
string()54 LIBC_INLINE constexpr string() {}
string(const string & other)55 LIBC_INLINE string(const string &other) { this->operator+=(other); }
string(string && other)56 LIBC_INLINE constexpr string(string &&other)
57 : buffer_(other.buffer_), size_(other.size_), capacity_(other.capacity_) {
58 other.reset_no_deallocate();
59 }
string(const char * cstr,size_t count)60 LIBC_INLINE string(const char *cstr, size_t count) {
61 resize(count);
62 inline_memcpy(buffer_, cstr, count);
63 }
string(const string_view & view)64 LIBC_INLINE string(const string_view &view)
65 : string(view.data(), view.size()) {}
string(const char * cstr)66 LIBC_INLINE string(const char *cstr)
67 : string(cstr, ::LIBC_NAMESPACE::internal::string_length(cstr)) {}
string(size_t size_,char value)68 LIBC_INLINE string(size_t size_, char value) {
69 resize(size_);
70 inline_memset((void *)buffer_, value, size_);
71 }
72
73 LIBC_INLINE string &operator=(const string &other) {
74 resize(0);
75 return (*this) += other;
76 }
77
78 LIBC_INLINE string &operator=(string &&other) {
79 buffer_ = other.buffer_;
80 size_ = other.size_;
81 capacity_ = other.capacity_;
82 other.reset_no_deallocate();
83 return *this;
84 }
85
86 LIBC_INLINE string &operator=(const string_view &view) {
87 return *this = string(view);
88 }
89
~string()90 LIBC_INLINE ~string() {
91 if (buffer_ != get_empty_string())
92 ::free(buffer_);
93 }
94
capacity()95 LIBC_INLINE constexpr size_t capacity() const { return capacity_; }
size()96 LIBC_INLINE constexpr size_t size() const { return size_; }
empty()97 LIBC_INLINE constexpr bool empty() const { return size_ == 0; }
98
data()99 LIBC_INLINE constexpr const char *data() const { return buffer_; }
data()100 LIBC_INLINE char *data() { return buffer_; }
101
begin()102 LIBC_INLINE constexpr const char *begin() const { return data(); }
begin()103 LIBC_INLINE char *begin() { return data(); }
104
end()105 LIBC_INLINE constexpr const char *end() const { return data() + size_; }
end()106 LIBC_INLINE char *end() { return data() + size_; }
107
front()108 LIBC_INLINE constexpr const char &front() const { return data()[0]; }
front()109 LIBC_INLINE char &front() { return data()[0]; }
110
back()111 LIBC_INLINE constexpr const char &back() const { return data()[size_ - 1]; }
back()112 LIBC_INLINE char &back() { return data()[size_ - 1]; }
113
114 LIBC_INLINE constexpr const char &operator[](size_t index) const {
115 return data()[index];
116 }
117 LIBC_INLINE char &operator[](size_t index) { return data()[index]; }
118
c_str()119 LIBC_INLINE const char *c_str() const { return data(); }
120
string_view()121 LIBC_INLINE operator string_view() const {
122 return string_view(buffer_, size_);
123 }
124
reserve(size_t new_capacity)125 LIBC_INLINE void reserve(size_t new_capacity) {
126 ++new_capacity; // Accounting for the terminating '\0'
127 if (new_capacity <= capacity_)
128 return;
129 // We extend the capacity to amortize buffer_ reallocations.
130 // We choose to augment the value by 11 / 8, this is about +40% and division
131 // by 8 is cheap. We guard the extension so the operation doesn't overflow.
132 if (new_capacity < SIZE_MAX / 11)
133 new_capacity = new_capacity * 11 / 8;
134 if (void *Ptr = ::realloc(buffer_ == get_empty_string() ? nullptr : buffer_,
135 new_capacity)) {
136 buffer_ = static_cast<char *>(Ptr);
137 capacity_ = new_capacity;
138 } else {
139 __builtin_unreachable(); // out of memory
140 }
141 }
142
resize(size_t size)143 LIBC_INLINE void resize(size_t size) {
144 if (size > capacity_) {
145 reserve(size);
146 const size_t size_extension = size - size_;
147 inline_memset(data() + size_, '\0', size_extension);
148 }
149 set_size_and_add_null_character(size);
150 }
151
152 LIBC_INLINE string &operator+=(const string &rhs) {
153 const size_t new_size = size_ + rhs.size();
154 reserve(new_size);
155 inline_memcpy(buffer_ + size_, rhs.data(), rhs.size());
156 set_size_and_add_null_character(new_size);
157 return *this;
158 }
159
160 LIBC_INLINE string &operator+=(const char c) {
161 const size_t new_size = size_ + 1;
162 reserve(new_size);
163 buffer_[size_] = c;
164 set_size_and_add_null_character(new_size);
165 return *this;
166 }
167 };
168
169 LIBC_INLINE bool operator==(const string &lhs, const string &rhs) {
170 return string_view(lhs) == string_view(rhs);
171 }
172 LIBC_INLINE bool operator!=(const string &lhs, const string &rhs) {
173 return string_view(lhs) != string_view(rhs);
174 }
175 LIBC_INLINE bool operator<(const string &lhs, const string &rhs) {
176 return string_view(lhs) < string_view(rhs);
177 }
178 LIBC_INLINE bool operator<=(const string &lhs, const string &rhs) {
179 return string_view(lhs) <= string_view(rhs);
180 }
181 LIBC_INLINE bool operator>(const string &lhs, const string &rhs) {
182 return string_view(lhs) > string_view(rhs);
183 }
184 LIBC_INLINE bool operator>=(const string &lhs, const string &rhs) {
185 return string_view(lhs) >= string_view(rhs);
186 }
187
188 LIBC_INLINE string operator+(const string &lhs, const string &rhs) {
189 string Tmp(lhs);
190 return Tmp += rhs;
191 }
192 LIBC_INLINE string operator+(const string &lhs, const char *rhs) {
193 return lhs + string(rhs);
194 }
195 LIBC_INLINE string operator+(const char *lhs, const string &rhs) {
196 return string(lhs) + rhs;
197 }
198
199 namespace internal {
to_dec_string(T value)200 template <typename T> string to_dec_string(T value) {
201 const IntegerToString<T> buffer(value);
202 return buffer.view();
203 }
204 } // namespace internal
205
to_string(int value)206 LIBC_INLINE string to_string(int value) {
207 return internal::to_dec_string<int>(value);
208 }
to_string(long value)209 LIBC_INLINE string to_string(long value) {
210 return internal::to_dec_string<long>(value);
211 }
to_string(long long value)212 LIBC_INLINE string to_string(long long value) {
213 return internal::to_dec_string<long long>(value);
214 }
to_string(unsigned value)215 LIBC_INLINE string to_string(unsigned value) {
216 return internal::to_dec_string<unsigned>(value);
217 }
to_string(unsigned long value)218 LIBC_INLINE string to_string(unsigned long value) {
219 return internal::to_dec_string<unsigned long>(value);
220 }
to_string(unsigned long long value)221 LIBC_INLINE string to_string(unsigned long long value) {
222 return internal::to_dec_string<unsigned long long>(value);
223 }
224
225 // TODO: Support floating point
226 // LIBC_INLINE string to_string(float value);
227 // LIBC_INLINE string to_string(double value);
228 // LIBC_INLINE string to_string(long double value);
229
230 } // namespace cpp
231 } // namespace LIBC_NAMESPACE_DECL
232
233 #endif // LLVM_LIBC_SRC___SUPPORT_CPP_STRING_H
234