openMSX
strCat.hh
Go to the documentation of this file.
1 #ifndef STRCAT_H
2 #define STRCAT_H
3 
4 #include "string_view.hh"
5 #include <climits>
6 #include <cstring>
7 #include <limits>
8 #include <sstream>
9 #include <string>
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 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  size_t size() const
110  {
111  return s.size();
112  }
113 
114  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<string_view>
158 {
160  : v(v_)
161  {
162  }
163 
164  size_t size() const
165  {
166  return v.size();
167  }
168 
169  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  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  size_t size() const
191  {
192  return 1;
193  }
194 
195  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  size_t size() const
216  {
217  return 1;
218  }
219 
220  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  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  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 const bool IS_SIGNED = std::numeric_limits<T>::is_signed;
310  static const 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  size_t size() const
327  {
328  return sz;
329  }
330 
331  char* copy(char* dst) const
332  {
333  memcpy(dst, begin(), sz);
334  return dst + sz;
335  }
336 
337  operator std::string() const
338  {
339  return std::string(begin(), this->size());
340  }
341 
342 private:
343  const char* begin() const
344  {
345  return &buf[BUF_SIZE] - sz;
346  }
347 
348  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  size_t size() const
370  {
371  return N;
372  }
373 
374  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  size_t size() const
403  {
404  return n;
405  }
406 
407  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 inline auto makeConcatUnit(const T& t)
425 {
426  return ConcatUnit<T>(t);
427 }
428 
429 // Overloads for various cases (strings, integers, floats, ...).
430 inline auto makeConcatUnit(const std::string& s)
431 {
432  return ConcatUnit<string_view>(s);
433 }
434 
435 inline auto makeConcatUnit(const char* s)
436 {
437  return ConcatUnit<string_view>(s);
438 }
439 
440 inline auto makeConcatUnit(char* s)
441 {
442  return ConcatUnit<string_view>(s);
443 }
444 
445 // Note: no ConcatIntegral<char> because that is printed as a single character
446 inline auto makeConcatUnit(signed char c)
447 {
448  return ConcatIntegral<signed char>(c);
449 }
450 
451 inline auto makeConcatUnit(unsigned char c)
452 {
454 }
455 
456 inline auto makeConcatUnit(short s)
457 {
458  return ConcatIntegral<short>(s);
459 }
460 
461 inline auto makeConcatUnit(unsigned short s)
462 {
464 }
465 
466 inline auto makeConcatUnit(int i)
467 {
468  return ConcatIntegral<int>(i);
469 }
470 
471 inline auto makeConcatUnit(unsigned u)
472 {
473  return ConcatIntegral<unsigned>(u);
474 }
475 
476 inline auto makeConcatUnit(long l)
477 {
478  return ConcatIntegral<long>(l);
479 }
480 
481 inline auto makeConcatUnit(unsigned long l)
482 {
484 }
485 
486 inline auto makeConcatUnit(long long l)
487 {
488  return ConcatIntegral<long long>(l);
489 }
490 
491 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 inline auto makeConcatUnit(float f)
504 {
505  return ConcatToString<float>(f);
506 }
507 
508 inline auto makeConcatUnit(double d)
509 {
510  return ConcatToString<double>(d);
511 }
512 
513 inline auto makeConcatUnit(long double d)
514 {
515  return ConcatToString<long double>(d);
516 }
517 #endif
518 
519 template<size_t N, typename T>
521 {
522  return t;
523 }
524 
525 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 size_t calcTotalSizeHelper(const Tuple& t, std::index_sequence<Is...>)
535 {
536  // TODO implementation can be simplified by using c++17 fold expressions
537  size_t total = 0;
538  auto l = { ((total += std::get<Is>(t).size()) , 0)... };
539  (void)l;
540  return total;
541 }
542 
543 template<typename... Ts>
544 size_t calcTotalSize(const std::tuple<Ts...>& t)
545 {
546  return calcTotalSizeHelper(t, std::index_sequence_for<Ts...>{});
547 }
548 
549 
550 // Copy each ConcatUnit<T> in the given tuple to the final result.
551 template<typename Tuple, size_t... Is>
552 void copyUnitsHelper(char* dst, const Tuple& t, std::index_sequence<Is...>)
553 {
554  auto l = { ((dst = std::get<Is>(t).copy(dst)) , 0)... };
555  (void)l;
556 }
557 
558 template<typename... Ts>
559 void copyUnits(char* dst, const std::tuple<Ts...>& t)
560 {
561  copyUnitsHelper(dst, t, std::index_sequence_for<Ts...>{});
562 }
563 
564 // Fast integral -> string conversion. (Standalone version, result is not part
565 // of a larger string).
566 template<typename T>
567 inline std::string to_string(T x)
568 {
569  return ConcatIntegral<T>(x);
570 }
571 
572 } // namespace strCatImpl
573 
574 
575 // Generic version
576 template<typename... Ts>
577 std::string strCat(Ts&& ...ts)
578 {
579  // Strategy:
580  // - For each parameter (of any type) we create a ConcatUnit object.
581  // - We sum the results of callings size() on all those objects.
582  // - We allocate a string of that total size.
583  // - We copy() each ConcatUnit into that string.
584 
585  auto t = std::make_tuple(strCatImpl::makeConcatUnit(std::forward<Ts>(ts))...);
587  // Ideally we want an uninitialized string with given size, but that's not
588  // yet possible. Though see the following proposal (for c++20):
589  // www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1072r0.html
590  std::string result(size, ' ');
591  char* dst = &result[0]; // C++17 result.data()
592  strCatImpl::copyUnits(dst, t);
593  return result;
594 }
595 
596 // Optimized strCat() for the case that the 1st parameter is a temporary
597 // (rvalue) string. In that case we can append to that temporary.
598 template<typename... Ts>
599 std::string strCat(std::string&& first, Ts&& ...ts)
600 {
601  strAppend(first, std::forward<Ts>(ts)...);
602  return std::move(first);
603 }
604 
605 // Degenerate case
606 inline std::string strCat()
607 {
608  return std::string();
609 }
610 
611 // Extra overloads. These don't change and/or extend the above functionality,
612 // but in some cases they might improve performance a bit (see notes above
613 // about uninitialized string resize). With these overloads strCat()/strAppend()
614 // should never be less efficient than a sequence of + or += string-operations.
615 inline std::string strCat(const std::string& x) { return x; }
616 inline std::string strCat(std::string&& x) { return std::move(x); }
617 inline std::string strCat(const char* x) { return std::string(x); }
618 inline std::string strCat(char x) { return std::string(1, x); }
619 inline std::string strCat(string_view x) { return std::string(x.data(), x.size()); }
620 
621 inline std::string strCat(signed char x) { return strCatImpl::to_string(x); }
622 inline std::string strCat(unsigned char x) { return strCatImpl::to_string(x); }
623 inline std::string strCat(short x) { return strCatImpl::to_string(x); }
624 inline std::string strCat(unsigned short x) { return strCatImpl::to_string(x); }
625 inline std::string strCat(int x) { return strCatImpl::to_string(x); }
626 inline std::string strCat(unsigned x) { return strCatImpl::to_string(x); }
627 inline std::string strCat(long x) { return strCatImpl::to_string(x); }
628 inline std::string strCat(unsigned long x) { return strCatImpl::to_string(x); }
629 inline std::string strCat(long long x) { return strCatImpl::to_string(x); }
630 inline std::string strCat(unsigned long long x) { return strCatImpl::to_string(x); }
631 
632 inline std::string strCat(const std::string& x, const std::string& y) { return x + y; }
633 inline std::string strCat(const char* x, const std::string& y) { return x + y; }
634 inline std::string strCat(char x, const std::string& y) { return x + y; }
635 inline std::string strCat(const std::string& x, const char* y) { return x + y; }
636 inline std::string strCat(const std::string& x, char y) { return x + y; }
637 inline std::string strCat(std::string&& x, const std::string& y) { return x + y; }
638 inline std::string strCat(const std::string& x, std::string&& y) { return x + y; }
639 inline std::string strCat(std::string&& x, std::string&& y) { return x + y; }
640 inline std::string strCat(const char* x, std::string&& y) { return x + y; }
641 inline std::string strCat(char x, std::string&& y) { return x + y; }
642 inline std::string strCat(std::string&& x, const char* y) { return x + y; }
643 inline std::string strCat(std::string&& x, char y) { return x + y; }
644 
645 
646 // Generic version
647 template<typename... Ts>
648 void strAppend(std::string& result, Ts&& ...ts)
649 {
650  // Implementation strategy is similar to strCat(). Main difference is
651  // that we now extend an existing string instead of creating a new one.
652 
653  auto t = std::make_tuple(strCatImpl::makeConcatUnit(std::forward<Ts>(ts))...);
654  auto extraSize = strCatImpl::calcTotalSize(t);
655  auto oldSize = result.size();
656  result.append(extraSize, ' '); // see note in strCat() about uninitialized string
657  char* dst = &result[oldSize];
658  strCatImpl::copyUnits(dst, t);
659 }
660 
661 // Degenerate case
662 inline void strAppend(std::string& /*x*/)
663 {
664  // nothing
665 }
666 
667 // Extra overloads, see strCat().
668 inline void strAppend(std::string& x, const std::string& y) { x += y; }
669 inline void strAppend(std::string& x, const char* y) { x += y; }
670 inline void strAppend(std::string& x, string_view y) { x.append(y.data(), y.size()); }
671 
672 
673 template<size_t N, typename T>
675 {
676  return {t};
677 }
678 
680 {
681  return {n};
682 }
683 
684 #endif
const char * data() const
Definition: string_view.hh:57
char * copy(char *dst) const
Definition: strCat.hh:195
void copyUnits(char *dst, const std::tuple< Ts... > &t)
Definition: strCat.hh:559
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:544
STL namespace.
char * copy(char *dst) const
Definition: strCat.hh:169
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:648
auto begin(const string_view &x)
Definition: string_view.hh:151
std::string to_string(T x)
Definition: strCat.hh:567
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:552
This class implements a (close approximation) of the std::string_view class.
Definition: string_view.hh:16
ConcatUnit(const string_view v_)
Definition: strCat.hh:159
strCatImpl::ConcatFixedWidthHexIntegral< N, T > hex_string(T t)
Definition: strCat.hh:674
void operator()(T t, char *&p) const
Definition: strCat.hh:284
ConcatViaString(std::string s_)
Definition: strCat.hh:104
char * copy(char *dst) const
Definition: strCat.hh:374
strCatImpl::ConcatSpaces spaces(size_t n)
Definition: strCat.hh:679
std::string strCat(Ts &&...ts)
Definition: strCat.hh:577
size_type size() const
Definition: string_view.hh:44
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 end(const string_view &x)
Definition: string_view.hh:152
auto makeConcatUnit(const T &t)
Definition: strCat.hh:424