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