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 static_assert(sizeof(char) == sizeof(uint8_t)); 71 inline_memset((void *)buffer_, static_cast<uint8_t>(value), size_); 72 } 73 74 LIBC_INLINE string &operator=(const string &other) { 75 resize(0); 76 return (*this) += other; 77 } 78 79 LIBC_INLINE string &operator=(string &&other) { 80 buffer_ = other.buffer_; 81 size_ = other.size_; 82 capacity_ = other.capacity_; 83 other.reset_no_deallocate(); 84 return *this; 85 } 86 87 LIBC_INLINE string &operator=(const string_view &view) { 88 return *this = string(view); 89 } 90 91 LIBC_INLINE ~string() { 92 if (buffer_ != get_empty_string()) 93 ::free(buffer_); 94 } 95 96 LIBC_INLINE constexpr size_t capacity() const { return capacity_; } 97 LIBC_INLINE constexpr size_t size() const { return size_; } 98 LIBC_INLINE constexpr bool empty() const { return size_ == 0; } 99 100 LIBC_INLINE constexpr const char *data() const { return buffer_; } 101 LIBC_INLINE char *data() { return buffer_; } 102 103 LIBC_INLINE constexpr const char *begin() const { return data(); } 104 LIBC_INLINE char *begin() { return data(); } 105 106 LIBC_INLINE constexpr const char *end() const { return data() + size_; } 107 LIBC_INLINE char *end() { return data() + size_; } 108 109 LIBC_INLINE constexpr const char &front() const { return data()[0]; } 110 LIBC_INLINE char &front() { return data()[0]; } 111 112 LIBC_INLINE constexpr const char &back() const { return data()[size_ - 1]; } 113 LIBC_INLINE char &back() { return data()[size_ - 1]; } 114 115 LIBC_INLINE constexpr const char &operator[](size_t index) const { 116 return data()[index]; 117 } 118 LIBC_INLINE char &operator[](size_t index) { return data()[index]; } 119 120 LIBC_INLINE const char *c_str() const { return data(); } 121 122 LIBC_INLINE operator string_view() const { 123 return string_view(buffer_, size_); 124 } 125 126 LIBC_INLINE void reserve(size_t new_capacity) { 127 ++new_capacity; // Accounting for the terminating '\0' 128 if (new_capacity <= capacity_) 129 return; 130 // We extend the capacity to amortize buffer_ reallocations. 131 // We choose to augment the value by 11 / 8, this is about +40% and division 132 // by 8 is cheap. We guard the extension so the operation doesn't overflow. 133 if (new_capacity < SIZE_MAX / 11) 134 new_capacity = new_capacity * 11 / 8; 135 if (void *Ptr = ::realloc(buffer_ == get_empty_string() ? nullptr : buffer_, 136 new_capacity)) { 137 buffer_ = static_cast<char *>(Ptr); 138 capacity_ = new_capacity; 139 } else { 140 __builtin_unreachable(); // out of memory 141 } 142 } 143 144 LIBC_INLINE void resize(size_t size) { 145 if (size > capacity_) { 146 reserve(size); 147 const size_t size_extension = size - size_; 148 inline_memset(data() + size_, '\0', size_extension); 149 } 150 set_size_and_add_null_character(size); 151 } 152 153 LIBC_INLINE string &operator+=(const string &rhs) { 154 const size_t new_size = size_ + rhs.size(); 155 reserve(new_size); 156 inline_memcpy(buffer_ + size_, rhs.data(), rhs.size()); 157 set_size_and_add_null_character(new_size); 158 return *this; 159 } 160 161 LIBC_INLINE string &operator+=(const char c) { 162 const size_t new_size = size_ + 1; 163 reserve(new_size); 164 buffer_[size_] = c; 165 set_size_and_add_null_character(new_size); 166 return *this; 167 } 168 }; 169 170 LIBC_INLINE bool operator==(const string &lhs, const string &rhs) { 171 return string_view(lhs) == string_view(rhs); 172 } 173 LIBC_INLINE bool operator!=(const string &lhs, const string &rhs) { 174 return string_view(lhs) != string_view(rhs); 175 } 176 LIBC_INLINE bool operator<(const string &lhs, const string &rhs) { 177 return string_view(lhs) < string_view(rhs); 178 } 179 LIBC_INLINE bool operator<=(const string &lhs, const string &rhs) { 180 return string_view(lhs) <= string_view(rhs); 181 } 182 LIBC_INLINE bool operator>(const string &lhs, const string &rhs) { 183 return string_view(lhs) > string_view(rhs); 184 } 185 LIBC_INLINE bool operator>=(const string &lhs, const string &rhs) { 186 return string_view(lhs) >= string_view(rhs); 187 } 188 189 LIBC_INLINE string operator+(const string &lhs, const string &rhs) { 190 string Tmp(lhs); 191 return Tmp += rhs; 192 } 193 LIBC_INLINE string operator+(const string &lhs, const char *rhs) { 194 return lhs + string(rhs); 195 } 196 LIBC_INLINE string operator+(const char *lhs, const string &rhs) { 197 return string(lhs) + rhs; 198 } 199 200 namespace internal { 201 template <typename T> string to_dec_string(T value) { 202 const IntegerToString<T> buffer(value); 203 return buffer.view(); 204 } 205 } // namespace internal 206 207 LIBC_INLINE string to_string(int value) { 208 return internal::to_dec_string<int>(value); 209 } 210 LIBC_INLINE string to_string(long value) { 211 return internal::to_dec_string<long>(value); 212 } 213 LIBC_INLINE string to_string(long long value) { 214 return internal::to_dec_string<long long>(value); 215 } 216 LIBC_INLINE string to_string(unsigned value) { 217 return internal::to_dec_string<unsigned>(value); 218 } 219 LIBC_INLINE string to_string(unsigned long value) { 220 return internal::to_dec_string<unsigned long>(value); 221 } 222 LIBC_INLINE string to_string(unsigned long long value) { 223 return internal::to_dec_string<unsigned long long>(value); 224 } 225 226 // TODO: Support floating point 227 // LIBC_INLINE string to_string(float value); 228 // LIBC_INLINE string to_string(double value); 229 // LIBC_INLINE string to_string(long double value); 230 231 } // namespace cpp 232 } // namespace LIBC_NAMESPACE_DECL 233 234 #endif // LLVM_LIBC_SRC___SUPPORT_CPP_STRING_H 235