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'; 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 41 constexpr void reset_no_deallocate() { 42 buffer_ = get_empty_string(); 43 size_ = 0; 44 capacity_ = 0; 45 } 46 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: 54 LIBC_INLINE constexpr string() {} 55 LIBC_INLINE string(const string &other) { this->operator+=(other); } 56 LIBC_INLINE constexpr string(string &&other) 57 : buffer_(other.buffer_), size_(other.size_), capacity_(other.capacity_) { 58 other.reset_no_deallocate(); 59 } 60 LIBC_INLINE string(const char *cstr, size_t count) { 61 resize(count); 62 inline_memcpy(buffer_, cstr, count); 63 } 64 LIBC_INLINE string(const string_view &view) 65 : string(view.data(), view.size()) {} 66 LIBC_INLINE string(const char *cstr) 67 : string(cstr, ::LIBC_NAMESPACE::internal::string_length(cstr)) {} 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 90 LIBC_INLINE ~string() { 91 if (buffer_ != get_empty_string()) 92 ::free(buffer_); 93 } 94 95 LIBC_INLINE constexpr size_t capacity() const { return capacity_; } 96 LIBC_INLINE constexpr size_t size() const { return size_; } 97 LIBC_INLINE constexpr bool empty() const { return size_ == 0; } 98 99 LIBC_INLINE constexpr const char *data() const { return buffer_; } 100 LIBC_INLINE char *data() { return buffer_; } 101 102 LIBC_INLINE constexpr const char *begin() const { return data(); } 103 LIBC_INLINE char *begin() { return data(); } 104 105 LIBC_INLINE constexpr const char *end() const { return data() + size_; } 106 LIBC_INLINE char *end() { return data() + size_; } 107 108 LIBC_INLINE constexpr const char &front() const { return data()[0]; } 109 LIBC_INLINE char &front() { return data()[0]; } 110 111 LIBC_INLINE constexpr const char &back() const { return data()[size_ - 1]; } 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 119 LIBC_INLINE const char *c_str() const { return data(); } 120 121 LIBC_INLINE operator string_view() const { 122 return string_view(buffer_, size_); 123 } 124 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 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 { 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 206 LIBC_INLINE string to_string(int value) { 207 return internal::to_dec_string<int>(value); 208 } 209 LIBC_INLINE string to_string(long value) { 210 return internal::to_dec_string<long>(value); 211 } 212 LIBC_INLINE string to_string(long long value) { 213 return internal::to_dec_string<long long>(value); 214 } 215 LIBC_INLINE string to_string(unsigned value) { 216 return internal::to_dec_string<unsigned>(value); 217 } 218 LIBC_INLINE string to_string(unsigned long value) { 219 return internal::to_dec_string<unsigned long>(value); 220 } 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