1 /* 2 * Copyright (C) 2022 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #pragma once 18 19 #include <algorithm> 20 #include <string> 21 #include <string_view> 22 23 namespace android::mediautils { 24 25 /* 26 * FixedString is a stack allocatable string buffer that supports 27 * simple appending of other strings and string_views. 28 * 29 * It is designed for no-malloc operation when std::string 30 * small buffer optimization is insufficient. 31 * 32 * To keep code small, use asStringView() for operations on this. 33 * 34 * Notes: 35 * 1) Appending beyond the internal buffer size results in truncation. 36 * 37 * Alternatives: 38 * 1) If you want a sharable copy-on-write string implementation, 39 * consider using the legacy android::String8(). 40 * 2) Using std::string with a fixed stack allocator may suit your needs, 41 * but exception avoidance is tricky. 42 * 3) Using C++20 ranges https://en.cppreference.com/w/cpp/ranges if you don't 43 * need backing store. Be careful about allocation with ranges. 44 * 45 * Good small sizes are multiples of 16 minus 2, e.g. 14, 30, 46, 62. 46 * 47 * Implementation Notes: 48 * 1) No iterators or [] for FixedString - please convert to std::string_view. 49 * 2) For small N (e.g. less than 62), consider a change to always zero fill and 50 * potentially prevent always zero terminating (if one only does append). 51 * 52 * Possible arguments to create/append: 53 * 1) A FixedString. 54 * 2) A single char. 55 * 3) A char * pointer. 56 * 4) A std::string. 57 * 5) A std::string_view (or something convertible to it). 58 * 59 * Example: 60 * 61 * FixedString s1(std::string("a")); // ctor 62 * s1 << "bc" << 'd' << '\n'; // streaming append 63 * s1 += "hello"; // += append 64 * ASSERT_EQ(s1, "abcd\nhello"); 65 */ 66 template <uint32_t N> 67 struct FixedString 68 { 69 // Find the best size type. 70 using strsize_t = std::conditional_t<(N > 255), uint32_t, uint8_t>; 71 72 // constructors FixedStringFixedString73 FixedString() { // override default 74 buffer_[0] = '\0'; 75 } 76 FixedStringFixedString77 FixedString(const FixedString& other) { // override default. 78 copyFrom<N>(other); 79 } 80 81 // The following constructor is not explicit to allow 82 // FixedString<8> s = "abcd"; 83 template <typename ...Types> FixedStringFixedString84 FixedString(Types&&... args) { 85 append(std::forward<Types>(args)...); 86 } 87 88 // copy assign (copyFrom checks for equality and returns *this). 89 FixedString& operator=(const FixedString& other) { // override default. 90 return copyFrom<N>(other); 91 } 92 93 template <typename ...Types> 94 FixedString& operator=(Types&&... args) { 95 size_ = 0; 96 return append(std::forward<Types>(args)...); 97 } 98 99 // operator equals 100 bool operator==(const char *s) const { 101 return strncmp(c_str(), s, capacity() + 1) == 0; 102 } 103 104 bool operator==(std::string_view s) const { 105 return size() == s.size() && memcmp(data(), s.data(), size()) == 0; 106 } 107 108 // operator not-equals 109 template <typename T> 110 bool operator!=(const T& other) const { 111 return !operator==(other); 112 } 113 114 // operator += 115 template <typename ...Types> 116 FixedString& operator+=(Types&&... args) { 117 return append(std::forward<Types>(args)...); 118 } 119 120 // conversion to std::string_view. string_viewFixedString121 operator std::string_view() const { 122 return asStringView(); 123 } 124 125 // basic observers buffer_offsetFixedString126 size_t buffer_offset() const { return offsetof(std::decay_t<decltype(*this)>, buffer_); } capacityFixedString127 static constexpr uint32_t capacity() { return N; } sizeFixedString128 uint32_t size() const { return size_; } remainingFixedString129 uint32_t remaining() const { return size_ >= N ? 0 : N - size_; } emptyFixedString130 bool empty() const { return size_ == 0; } fullFixedString131 bool full() const { return size_ == N; } // when full, possible truncation risk. dataFixedString132 char * data() { return buffer_; } dataFixedString133 const char * data() const { return buffer_; } c_strFixedString134 const char * c_str() const { return buffer_; } 135 asStringViewFixedString136 inline std::string_view asStringView() const { 137 return { buffer_, static_cast<size_t>(size_) }; 138 } asStringFixedString139 inline std::string asString() const { 140 return { buffer_, static_cast<size_t>(size_) }; 141 } 142 clearFixedString143 void clear() { size_ = 0; buffer_[0] = 0; } 144 145 // Implementation of append - using templates 146 // to guarantee precedence in the presence of ambiguity. 147 // 148 // Consider C++20 template overloading through constraints and concepts. 149 template <typename T> appendFixedString150 FixedString& append(const T& t) { 151 using decayT = std::decay_t<T>; 152 if constexpr (is_specialization_v<decayT, FixedString>) { 153 // A FixedString<U> 154 if (size_ == 0) { 155 // optimization to erase everything. 156 return copyFrom(t); 157 } else { 158 return appendStringView({t.data(), t.size()}); 159 } 160 } else if constexpr(std::is_same_v<decayT, char>) { 161 if (size_ < N) { 162 buffer_[size_++] = t; 163 buffer_[size_] = '\0'; 164 } 165 return *this; 166 } else if constexpr(std::is_same_v<decayT, char *>) { 167 // Some char* ptr. 168 return appendString(t); 169 } else if constexpr (std::is_convertible_v<decayT, std::string_view>) { 170 // std::string_view, std::string, or some other convertible type. 171 return appendStringView(t); 172 } else /* constexpr */ { 173 static_assert(dependent_false_v<T>, "non-matching append type"); 174 } 175 } 176 appendStringViewFixedString177 FixedString& appendStringView(std::string_view s) { 178 uint32_t total = std::min(static_cast<size_t>(N - size_), s.size()); 179 memcpy(buffer_ + size_, s.data(), total); 180 size_ += total; 181 buffer_[size_] = '\0'; 182 return *this; 183 } 184 appendStringFixedString185 FixedString& appendString(const char *s) { 186 // strncpy zero pads to the end, 187 // strlcpy returns total expected length, 188 // we don't have strncpy_s in Bionic, 189 // so we write our own here. 190 while (size_ < N && *s != '\0') { 191 buffer_[size_++] = *s++; 192 } 193 buffer_[size_] = '\0'; 194 return *this; 195 } 196 197 // Copy initialize the struct. 198 // Note: We are POD but customize the copying for acceleration 199 // of moving small strings embedded in a large buffers. 200 template <uint32_t U> copyFromFixedString201 FixedString& copyFrom(const FixedString<U>& other) { 202 if ((void*)this != (void*)&other) { // not a self-assignment 203 if (other.size() == 0) { 204 size_ = 0; 205 buffer_[0] = '\0'; 206 return *this; 207 } 208 constexpr size_t kSizeToCopyWhole = 64; 209 if constexpr (N == U && 210 sizeof(*this) == sizeof(other) && 211 sizeof(*this) <= kSizeToCopyWhole) { 212 // As we have the same str size type, we can just 213 // memcpy with fixed size, which can be easily optimized. 214 memcpy(static_cast<void*>(this), static_cast<const void*>(&other), sizeof(*this)); 215 return *this; 216 } 217 if constexpr (std::is_same_v<strsize_t, typename FixedString<U>::strsize_t>) { 218 constexpr size_t kAlign = 8; // align to a multiple of 8. 219 static_assert((kAlign & (kAlign - 1)) == 0); // power of 2. 220 // we check any alignment issues. 221 if (buffer_offset() == other.buffer_offset() && other.size() <= capacity()) { 222 // improve on standard POD copying by reducing size. 223 const size_t mincpy = buffer_offset() + other.size() + 1 /* nul */; 224 const size_t maxcpy = std::min(sizeof(*this), sizeof(other)); 225 const size_t cpysize = std::min(mincpy + kAlign - 1 & ~(kAlign - 1), maxcpy); 226 memcpy(static_cast<void*>(this), static_cast<const void*>(&other), cpysize); 227 return *this; 228 } 229 } 230 size_ = std::min(other.size(), capacity()); 231 memcpy(buffer_, other.data(), size_); 232 buffer_[size_] = '\0'; // zero terminate. 233 } 234 return *this; 235 } 236 237 private: 238 // Template helper methods 239 240 template <typename Test, template <uint32_t> class Ref> 241 struct is_specialization : std::false_type {}; 242 243 template <template <uint32_t> class Ref, uint32_t UU> 244 struct is_specialization<Ref<UU>, Ref>: std::true_type {}; 245 246 template <typename Test, template <uint32_t> class Ref> 247 static inline constexpr bool is_specialization_v = is_specialization<Test, Ref>::value; 248 249 // For static assert(false) we need a template version to avoid early failure. 250 template <typename T> 251 static inline constexpr bool dependent_false_v = false; 252 253 // POD variables 254 strsize_t size_ = 0; 255 char buffer_[N + 1 /* allow zero termination */]; 256 }; 257 258 // Stream operator syntactic sugar. 259 // Example: 260 // s << 'b' << "c" << "d" << '\n'; 261 template <uint32_t N, typename ...Types> 262 FixedString<N>& operator<<(FixedString<N>& fs, Types&&... args) { 263 return fs.append(std::forward<Types>(args)...); 264 } 265 266 // We do not use a default size for fixed string as changing 267 // the default size would lead to different behavior - we want the 268 // size to be explicitly known. 269 270 // FixedString62 of 62 chars fits in one typical cache line. 271 using FixedString62 = FixedString<62>; 272 273 // Slightly smaller 274 using FixedString30 = FixedString<30>; 275 276 // Since we have added copy and assignment optimizations, 277 // we are no longer trivially assignable and copyable. 278 // But we check standard layout here to prevent inclusion of unacceptable members or virtuals. 279 static_assert(std::is_standard_layout_v<FixedString62>); 280 static_assert(std::is_standard_layout_v<FixedString30>); 281 282 } // namespace android::mediautils 283