openMSX
strCat.hh
Go to the documentation of this file.
1 #ifndef STRCAT_HH
2 #define STRCAT_HH
3 
4 #include "TemporaryString.hh"
5 #include "xrange.hh"
6 #include "zstring_view.hh"
7 #include <climits>
8 #include <cstring>
9 #include <limits>
10 #include <sstream>
11 #include <string>
12 #include <string_view>
13 #include <tuple>
14 #include <utility>
15 
16 // strCat and strAppend()
17 //
18 // Inspired by google's absl::StrCat (similar interface, different implementation).
19 // See https://abseil.io/blog/20171023-cppcon-strcat
20 // and https://github.com/abseil/abseil-cpp/blob/master/absl/strings/str_cat.h
21 
22 
23 // --- Public interface ---
24 
25 // Concatenate a bunch of 'printable' objects.
26 //
27 // Conceptually each object is converted to a string, all those strings are
28 // concatenated, and that result is returned.
29 //
30 // For example:
31 // auto s = strCat("foobar", s, ' ', 123);
32 // is equivalent to
33 // auto s = "foobar" + s + ' ' + std::to_string(123);
34 //
35 // The former executes faster than the latter because (among other things) it
36 // immediately creates a result of the correct size instead of (re)allocating
37 // all intermediate strings. Also it doesn't create temporary string objects
38 // for the integer conversions.
39 template<typename... Ts>
40 [[nodiscard]] std::string strCat(Ts&& ...ts);
41 
42 // Consider using 'tmpStrCat()' as an alternative for 'strCat()'. The only
43 // difference is that this one returns a 'TemporaryString' instead of a
44 // 'std::string'. This can be faster (e.g. no heap allocation) when the result
45 // is not required to be a 'std::string' (std::string_view is sufficient) and
46 // when it really is a temporary (short lived) string.
47 template<typename... Ts>
48 [[nodiscard]] TemporaryString tmpStrCat(Ts&&... ts);
49 
50 // Append a bunch of 'printable' objects to an exiting string.
51 //
52 // Can be used to optimize
53 // s += strCat(a, b, c);
54 // to
55 // strAppend(s, a, b, c);
56 //
57 // This latter will immediately construct the result in 's' instead of first
58 // formatting to a temporary string followed by appending that temporary to 's'.
59 //
60 // There's one limitation though: it's not allowed to append a string to
61 // itself, not even parts of the string (strCat() doesn't have this
62 // limitation). So the following is invalid:
63 // strAppend(s, s); // INVALID, append s to itself
64 //
65 // string_view v = s;
66 // v.substr(10, 20);
67 // strAppend(s, v); // INVALID, append part of s to itself
68 template<typename... Ts>
69 void strAppend(std::string& result, Ts&& ...ts);
70 
71 
72 // Format an integer as a fixed-width hexadecimal value and insert it into
73 // a strCat() or strAppend() sequence.
74 // - If the value is small, leading zeros are printed.
75 // - If the value is too big, it gets truncated. Only the rightmost characters
76 // are kept.
77 //
78 // For example:
79 // s = strCat("The value is: 0x", hex_string<4>(value), '.');
82 
83 
84 // Insert 'n' spaces into a strCat() or strAppend() sequence.
85 //
86 // For example:
87 // s = strCat("The result is ", spaces(30 - item.size()), item);
88 //
89 // This can be more efficient than creating a temporary string containing 'n'
90 // spaces, like this
91 // s = strCat("The result is ", std::string(30 - item.size(), ' '), item);
93 
94 
95 // --- Implementation details ---
96 
97 namespace strCatImpl {
98 
99 // ConcatUnit
100 // These implement various mechanisms to concatentate an object to a string.
101 // All these classes implement:
102 //
103 // - size_t size() const;
104 // Returns the (exact) size in characters of the formatted object.
105 //
106 // - char* copy(char* dst) const;
107 // Copy the formatted object to 'dst', returns an updated pointer.
108 template<typename T> struct ConcatUnit;
109 
110 
111 // Helper for types which are formatted via a temporary string object
113 {
114  ConcatViaString(std::string s_)
115  : s(std::move(s_))
116  {
117  }
118 
119  [[nodiscard]] size_t size() const
120  {
121  return s.size();
122  }
123 
124  [[nodiscard]] char* copy(char* dst) const
125  {
126  auto sz = s.size();
127  memcpy(dst, s.data(), sz);
128  return dst + sz;
129  }
130 
131 private:
132  std::string s;
133 };
134 
135 #if 0
136 // Dingux doesn't have std::to_string() ???
137 
138 // Helper for types which are printed via std::to_string(),
139 // e.g. floating point types.
140 template<typename T>
141 struct ConcatToString : ConcatViaString
142 {
143  ConcatToString(T t)
144  : ConcatViaString(std::to_string(t))
145  {
146  }
147 };
148 #endif
149 
150 // The default (slow) implementation uses 'operator<<(ostream&, T)'
151 template<typename T>
153 {
154  ConcatUnit(const T& t)
155  : ConcatViaString([&](){
156  std::ostringstream os;
157  os << t;
158  return os.str();
159  }())
160  {
161  }
162 };
163 
164 
165 // ConcatUnit<string_view>:
166 // store the string view (copies the view, not the string)
167 template<> struct ConcatUnit<std::string_view>
168 {
169  ConcatUnit(const std::string_view v_)
170  : v(v_)
171  {
172  }
173 
174  [[nodiscard]] size_t size() const
175  {
176  return v.size();
177  }
178 
179  [[nodiscard]] char* copy(char* dst) const
180  {
181  auto sz = v.size();
182  if (sz) memcpy(dst, v.data(), sz);
183  return dst + sz;
184  }
185 
186 private:
187  std::string_view v;
188 };
189 
190 
191 // ConcatUnit<char>:
192 // store single char (length is constant 1)
193 template<> struct ConcatUnit<char>
194 {
195  ConcatUnit(char c_)
196  : c(c_)
197  {
198  }
199 
200  [[nodiscard]] size_t size() const
201  {
202  return 1;
203  }
204 
205  [[nodiscard]] char* copy(char* dst) const
206  {
207  *dst = c;
208  return dst + 1;
209  }
210 
211 private:
212  char c;
213 };
214 
215 
216 // ConcatUnit<bool>:
217 // store bool (length is constant 1)
218 template<> struct ConcatUnit<bool>
219 {
220  ConcatUnit(bool b_)
221  : b(b_)
222  {
223  }
224 
225  [[nodiscard]] size_t size() const
226  {
227  return 1;
228  }
229 
230  [[nodiscard]] char* copy(char* dst) const
231  {
232  *dst = b ? '1' : '0';
233  return dst + 1;
234  }
235 
236 private:
237  bool b;
238 };
239 
240 
241 // Helper classes/functions for fast integer -> string conversion.
242 
243 // Returns a fast type that is wide enough to hold the absolute value for
244 // values of the given type.
245 //
246 // On x86 32-bit operations are faster than e.g. 16-bit operations.
247 // So this function returns a 32-bit type unless 64-bit are needed.
248 //
249 // 'long' is special because it's either 32-bit (windows) or 64-bit (Linux).
250 template<typename T> struct FastUnsignedImpl { using type = unsigned; };
251 template<> struct FastUnsignedImpl< long> { using type = unsigned long; };
252 template<> struct FastUnsignedImpl<unsigned long> { using type = unsigned long; };
253 template<> struct FastUnsignedImpl< long long> { using type = unsigned long long; };
254 template<> struct FastUnsignedImpl<unsigned long long> { using type = unsigned long long; };
255 template<typename T> using FastUnsigned = typename FastUnsignedImpl<T>::type;
256 
257 // Helper function to take the absolute value of a signed or unsigned type.
258 // (without compiler warning on 't < 0' and '-t' when t is unsigned)
259 template<std::unsigned_integral T>
260 [[nodiscard]] FastUnsigned<T> absHelper(T t) { return t; }
261 
262 template<std::signed_integral T>
263 [[nodiscard]] FastUnsigned<T> absHelper(T t) { return (t < 0)? -t : t; }
264 
265 
266 // Optimized integer printing.
267 //
268 // Prints the value to an internal buffer. The formatted characters are
269 // generated from back to front. This means the final result is not aligned
270 // with the start of this internal buffer.
271 //
272 // Next to the internal buffer we also store the size (in characters) of the
273 // result. This size can be used to calculate the start position in the buffer.
274 template<std::integral T> struct ConcatIntegral
275 {
276  static constexpr bool IS_SIGNED = std::numeric_limits<T>::is_signed;
277  static constexpr size_t BUF_SIZE = 1 + std::numeric_limits<T>::digits10 + IS_SIGNED;
278 
280  {
281  char* p = this->end();
282  std::unsigned_integral auto a = absHelper(t);
283 
284  do {
285  *--p = static_cast<char>('0' + (a % 10));
286  a /= 10;
287  } while (a);
288 
289  if constexpr (IS_SIGNED) {
290  if (t < 0) *--p = '-';
291  }
292  this->sz = static_cast<unsigned char>(this->end() - p);
293  }
294 
295  [[nodiscard]] size_t size() const
296  {
297  return sz;
298  }
299 
300  [[nodiscard]] char* copy(char* dst) const
301  {
302  memcpy(dst, begin(), sz);
303  return dst + sz;
304  }
305 
306  [[nodiscard]] operator std::string() const
307  {
308  return std::string(begin(), this->size());
309  }
310 
311 private:
312  [[nodiscard]] const char* begin() const
313  {
314  return &buf[BUF_SIZE] - sz;
315  }
316 
317  [[nodiscard]] char* end()
318  {
319  return &buf[BUF_SIZE];
320  }
321 
322 private:
323  char buf[BUF_SIZE];
324  unsigned char sz;
325 };
326 
327 
328 // Format an integral as a hexadecimal value with a fixed number of characters.
329 // This fixed width means it either adds leading zeros or truncates the result
330 // (it keeps the rightmost digits).
331 template<size_t N, std::integral T> struct ConcatFixedWidthHexIntegral
332 {
334  : t(t_)
335  {
336  }
337 
338  [[nodiscard]] size_t size() const
339  {
340  return N;
341  }
342 
343  [[nodiscard]] char* copy(char* dst) const
344  {
345  char* p = dst + N;
346  auto u = static_cast<FastUnsigned<T>>(t);
347 
348  repeat(N, [&] {
349  auto d = u & 15;
350  *--p = (d < 10) ? static_cast<char>(d + '0')
351  : static_cast<char>(d - 10 + 'a');
352  u >>= 4;
353  });
354 
355  return dst + N;
356  }
357 
358 private:
359  T t;
360 };
361 
362 
363 // Prints a number of spaces (without constructing a temporary string).
365 {
366  ConcatSpaces(size_t n_)
367  : n(n_)
368  {
369  }
370 
371  [[nodiscard]] size_t size() const
372  {
373  return n;
374  }
375 
376  [[nodiscard]] char* copy(char* dst) const
377  {
378  memset(dst, ' ', n);
379  return dst + n;
380  }
381 
382 private:
383  size_t n;
384 };
385 
386 
387 // Create a 'ConcatUnit<T>' wrapper object for a given 'T' value.
388 
389 // Generic version: use the corresponding ConcatUnit<T> class. This can be
390 // a specialized version for 'T', or the generic (slow) version which uses
391 // operator<<(ostream&, T).
392 template<typename T>
393 [[nodiscard]] inline auto makeConcatUnit(const T& t)
394 {
395  return ConcatUnit<T>(t);
396 }
397 
398 // Overloads for various cases (strings, integers, floats, ...).
399 [[nodiscard]] inline auto makeConcatUnit(const std::string& s)
400 {
402 }
403 
404 [[nodiscard]] inline auto makeConcatUnit(const char* s)
405 {
407 }
408 
409 [[nodiscard]] inline auto makeConcatUnit(char* s)
410 {
412 }
413 [[nodiscard]] inline auto makeConcatUnit(const TemporaryString& s)
414 {
416 }
417 [[nodiscard]] inline auto makeConcatUnit(zstring_view s)
418 {
420 }
421 
422 // Note: no ConcatIntegral<char> because that is printed as a single character
423 [[nodiscard]] inline auto makeConcatUnit(signed char c)
424 {
425  return ConcatIntegral<signed char>(c);
426 }
427 
428 [[nodiscard]] inline auto makeConcatUnit(unsigned char c)
429 {
431 }
432 
433 [[nodiscard]] inline auto makeConcatUnit(short s)
434 {
435  return ConcatIntegral<short>(s);
436 }
437 
438 [[nodiscard]] inline auto makeConcatUnit(unsigned short s)
439 {
441 }
442 
443 [[nodiscard]] inline auto makeConcatUnit(int i)
444 {
445  return ConcatIntegral<int>(i);
446 }
447 
448 [[nodiscard]] inline auto makeConcatUnit(unsigned u)
449 {
450  return ConcatIntegral<unsigned>(u);
451 }
452 
453 [[nodiscard]] inline auto makeConcatUnit(long l)
454 {
455  return ConcatIntegral<long>(l);
456 }
457 
458 [[nodiscard]] inline auto makeConcatUnit(unsigned long l)
459 {
461 }
462 
463 [[nodiscard]] inline auto makeConcatUnit(long long l)
464 {
465  return ConcatIntegral<long long>(l);
466 }
467 
468 [[nodiscard]] inline auto makeConcatUnit(unsigned long long l)
469 {
471 }
472 
473 #if 0
474 // Converting float->string via std::to_string() might be faster than via
475 // std::stringstream. Though the former doesn't seem to work on Dingux??
476 //
477 // But for openMSX this isn't critical, so we can live with the default
478 // (slower?) version.
479 
480 [[nodiscard]] inline auto makeConcatUnit(float f)
481 {
482  return ConcatToString<float>(f);
483 }
484 
485 [[nodiscard]] inline auto makeConcatUnit(double d)
486 {
487  return ConcatToString<double>(d);
488 }
489 
490 [[nodiscard]] inline auto makeConcatUnit(long double d)
491 {
492  return ConcatToString<long double>(d);
493 }
494 #endif
495 
496 template<size_t N, std::integral T>
497 [[nodiscard]] inline auto makeConcatUnit(const ConcatFixedWidthHexIntegral<N, T>& t)
498 {
499  return t;
500 }
501 
502 [[nodiscard]] inline auto makeConcatUnit(const ConcatSpaces& t)
503 {
504  return t;
505 }
506 
507 
508 // Calculate the total size for a bunch (a tuple) of ConcatUnit<T> objects.
509 // That is, calculate the sum of calling the size() method on each ConcatUnit.
510 template<typename Tuple, size_t... Is>
511 [[nodiscard]] size_t calcTotalSizeHelper(const Tuple& t, std::index_sequence<Is...>)
512 {
513  return (... + std::get<Is>(t).size());
514 }
515 
516 template<typename... Ts>
517 [[nodiscard]] size_t calcTotalSize(const std::tuple<Ts...>& t)
518 {
519  return calcTotalSizeHelper(t, std::index_sequence_for<Ts...>{});
520 }
521 
522 
523 // Copy each ConcatUnit<T> in the given tuple to the final result.
524 template<typename Tuple, size_t... Is>
525 void copyUnitsHelper(char* dst, const Tuple& t, std::index_sequence<Is...>)
526 {
527  auto l = { ((dst = std::get<Is>(t).copy(dst)) , 0)... };
528  (void)l;
529 }
530 
531 template<typename... Ts>
532 void copyUnits(char* dst, const std::tuple<Ts...>& t)
533 {
534  copyUnitsHelper(dst, t, std::index_sequence_for<Ts...>{});
535 }
536 
537 // Fast integral -> string conversion. (Standalone version, result is not part
538 // of a larger string).
539 [[nodiscard]] inline std::string to_string(std::integral auto x)
540 {
541  return ConcatIntegral(x);
542 }
543 
544 } // namespace strCatImpl
545 
546 
547 // Generic version
548 template<typename... Ts>
549 [[nodiscard]] std::string strCat(Ts&& ...ts)
550 {
551  // Strategy:
552  // - For each parameter (of any type) we create a ConcatUnit object.
553  // - We sum the results of callings size() on all those objects.
554  // - We allocate a string of that total size.
555  // - We copy() each ConcatUnit into that string.
556 
557  auto t = std::tuple(strCatImpl::makeConcatUnit(std::forward<Ts>(ts))...);
559  // Ideally we want an uninitialized string with given size, but that's not
560  // yet possible. Though see the following proposal (for c++20):
561  // www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1072r0.html
562  std::string result(size, ' ');
563  char* dst = result.data();
564  strCatImpl::copyUnits(dst, t);
565  return result;
566 }
567 
568 // Optimized strCat() for the case that the 1st parameter is a temporary
569 // (rvalue) string. In that case we can append to that temporary.
570 template<typename... Ts>
571 [[nodiscard]] std::string strCat(std::string&& first, Ts&& ...ts)
572 {
573  strAppend(first, std::forward<Ts>(ts)...);
574  return std::move(first);
575 }
576 
577 // Degenerate case
578 [[nodiscard]] inline std::string strCat()
579 {
580  return std::string();
581 }
582 
583 // Extra overloads. These don't change and/or extend the above functionality,
584 // but in some cases they might improve performance a bit (see notes above
585 // about uninitialized string resize). With these overloads strCat()/strAppend()
586 // should never be less efficient than a sequence of + or += string-operations.
587 [[nodiscard]] inline std::string strCat(const std::string& x) { return x; }
588 [[nodiscard]] inline std::string strCat(std::string&& x) { return std::move(x); }
589 [[nodiscard]] inline std::string strCat(const char* x) { return std::string(x); }
590 [[nodiscard]] inline std::string strCat(char x) { return std::string(1, x); }
591 [[nodiscard]] inline std::string strCat(std::string_view x) { return std::string(x.data(), x.size()); }
592 
593 [[nodiscard]] inline std::string strCat(signed char x) { return strCatImpl::to_string(x); }
594 [[nodiscard]] inline std::string strCat(unsigned char x) { return strCatImpl::to_string(x); }
595 [[nodiscard]] inline std::string strCat(short x) { return strCatImpl::to_string(x); }
596 [[nodiscard]] inline std::string strCat(unsigned short x) { return strCatImpl::to_string(x); }
597 [[nodiscard]] inline std::string strCat(int x) { return strCatImpl::to_string(x); }
598 [[nodiscard]] inline std::string strCat(unsigned x) { return strCatImpl::to_string(x); }
599 [[nodiscard]] inline std::string strCat(long x) { return strCatImpl::to_string(x); }
600 [[nodiscard]] inline std::string strCat(unsigned long x) { return strCatImpl::to_string(x); }
601 [[nodiscard]] inline std::string strCat(long long x) { return strCatImpl::to_string(x); }
602 [[nodiscard]] inline std::string strCat(unsigned long long x) { return strCatImpl::to_string(x); }
603 
604 [[nodiscard]] inline std::string strCat(const std::string& x, const std::string& y) { return x + y; }
605 [[nodiscard]] inline std::string strCat(const char* x, const std::string& y) { return x + y; }
606 [[nodiscard]] inline std::string strCat(char x, const std::string& y) { return x + y; }
607 [[nodiscard]] inline std::string strCat(const std::string& x, const char* y) { return x + y; }
608 [[nodiscard]] inline std::string strCat(const std::string& x, char y) { return x + y; }
609 [[nodiscard]] inline std::string strCat(std::string&& x, const std::string& y) { return x + y; }
610 [[nodiscard]] inline std::string strCat(const std::string& x, std::string&& y) { return x + y; }
611 [[nodiscard]] inline std::string strCat(std::string&& x, std::string&& y) { return x + y; }
612 [[nodiscard]] inline std::string strCat(const char* x, std::string&& y) { return x + y; }
613 [[nodiscard]] inline std::string strCat(char x, std::string&& y) { return x + y; }
614 [[nodiscard]] inline std::string strCat(std::string&& x, const char* y) { return x + y; }
615 [[nodiscard]] inline std::string strCat(std::string&& x, char y) { return x + y; }
616 
617 template<typename... Ts> [[nodiscard]] TemporaryString tmpStrCat(Ts&&... ts)
618 {
619  auto t = std::tuple(strCatImpl::makeConcatUnit(std::forward<Ts>(ts))...);
621  return TemporaryString(
622  size, [&](char* dst) { strCatImpl::copyUnits(dst, t); });
623 }
624 
625 // Generic version
626 template<typename... Ts>
627 void strAppend(std::string& result, Ts&& ...ts)
628 {
629  // Implementation strategy is similar to strCat(). Main difference is
630  // that we now extend an existing string instead of creating a new one.
631 
632  auto t = std::tuple(strCatImpl::makeConcatUnit(std::forward<Ts>(ts))...);
633  auto extraSize = strCatImpl::calcTotalSize(t);
634  auto oldSize = result.size();
635  result.append(extraSize, ' '); // see note in strCat() about uninitialized string
636  char* dst = &result[oldSize];
637  strCatImpl::copyUnits(dst, t);
638 }
639 
640 // Degenerate case
641 inline void strAppend(std::string& /*x*/)
642 {
643  // nothing
644 }
645 
646 // Extra overloads, see strCat().
647 inline void strAppend(std::string& x, const std::string& y) { x += y; }
648 inline void strAppend(std::string& x, const char* y) { x += y; }
649 inline void strAppend(std::string& x, std::string_view y) { x.append(y.data(), y.size()); }
650 
651 
652 template<size_t N, std::integral T>
654 {
655  return {t};
656 }
657 
658 [[nodiscard]] inline strCatImpl::ConcatSpaces spaces(size_t n)
659 {
660  return {n};
661 }
662 
663 #endif
TclObject t
TemporaryString.
Like std::string_view, but with the extra guarantee that it refers to a zero-terminated string.
Definition: zstring_view.hh:22
constexpr unsigned N
Definition: ResampleHQ.cc:226
constexpr KeyMatrixPosition x
Keyboard bindings.
Definition: Keyboard.cc:127
FastUnsigned< T > absHelper(T t)
Definition: strCat.hh:260
auto makeConcatUnit(const T &t)
Definition: strCat.hh:393
void copyUnits(char *dst, const std::tuple< Ts... > &t)
Definition: strCat.hh:532
void copyUnitsHelper(char *dst, const Tuple &t, std::index_sequence< Is... >)
Definition: strCat.hh:525
typename FastUnsignedImpl< T >::type FastUnsigned
Definition: strCat.hh:255
size_t calcTotalSizeHelper(const Tuple &t, std::index_sequence< Is... >)
Definition: strCat.hh:511
size_t calcTotalSize(const std::tuple< Ts... > &t)
Definition: strCat.hh:517
std::string to_string(std::integral auto x)
Definition: strCat.hh:539
size_t size(std::string_view utf8)
strCatImpl::ConcatFixedWidthHexIntegral< N, T > hex_string(T t)
Definition: strCat.hh:653
strCatImpl::ConcatSpaces spaces(size_t n)
Definition: strCat.hh:658
TemporaryString tmpStrCat(Ts &&... ts)
Definition: strCat.hh:617
std::string strCat(Ts &&...ts)
Definition: strCat.hh:549
void strAppend(std::string &result, Ts &&...ts)
Definition: strCat.hh:627
char * copy(char *dst) const
Definition: strCat.hh:343
size_t size() const
Definition: strCat.hh:295
static constexpr size_t BUF_SIZE
Definition: strCat.hh:277
char * copy(char *dst) const
Definition: strCat.hh:300
static constexpr bool IS_SIGNED
Definition: strCat.hh:276
char * copy(char *dst) const
Definition: strCat.hh:376
ConcatSpaces(size_t n_)
Definition: strCat.hh:366
size_t size() const
Definition: strCat.hh:371
char * copy(char *dst) const
Definition: strCat.hh:230
char * copy(char *dst) const
Definition: strCat.hh:205
ConcatUnit(const std::string_view v_)
Definition: strCat.hh:169
ConcatUnit(const T &t)
Definition: strCat.hh:154
size_t size() const
Definition: strCat.hh:119
ConcatViaString(std::string s_)
Definition: strCat.hh:114
char * copy(char *dst) const
Definition: strCat.hh:124
constexpr void repeat(T n, Op op)
Repeat the given operation 'op' 'n' times.
Definition: xrange.hh:148