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.
39template<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.
47template<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
68template<typename... Ts>
69void 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
97namespace 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.
108template<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
131private:
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.
140template<typename T>
141struct 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)'
151template<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)
167template<> 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
186private:
187 std::string_view v;
188};
189
190
191// ConcatUnit<char>:
192// store single char (length is constant 1)
193template<> 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
211private:
212 char c;
213};
214
215
216// ConcatUnit<bool>:
217// store bool (length is constant 1)
218template<> 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
236private:
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).
250template<typename T> struct FastUnsignedImpl { using type = unsigned; };
251template<> struct FastUnsignedImpl< long> { using type = unsigned long; };
252template<> struct FastUnsignedImpl<unsigned long> { using type = unsigned long; };
253template<> struct FastUnsignedImpl< long long> { using type = unsigned long long; };
254template<> struct FastUnsignedImpl<unsigned long long> { using type = unsigned long long; };
255template<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)
259template<std::unsigned_integral T>
260[[nodiscard]] FastUnsigned<T> absHelper(T t) { return t; }
261
262template<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.
274template<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
311private:
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
322private:
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).
331template<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
358private:
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
382private:
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).
392template<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{
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{
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
496template<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.
510template<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
516template<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.
524template<typename Tuple, size_t... Is>
525void 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
531template<typename... Ts>
532void 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
548template<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();
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.
570template<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
617template<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
626template<typename... Ts>
627void 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];
638}
639
640// Degenerate case
641inline void strAppend(std::string& /*x*/)
642{
643 // nothing
644}
645
646// Extra overloads, see strCat().
647inline void strAppend(std::string& x, const std::string& y) { x += y; }
648inline void strAppend(std::string& x, const char* y) { x += y; }
649inline void strAppend(std::string& x, std::string_view y) { x.append(y.data(), y.size()); }
650
651
652template<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
STL namespace.
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
char * copy(char *dst) const
Definition: strCat.hh:300
static constexpr size_t BUF_SIZE
Definition: strCat.hh:277
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
char * copy(char *dst) const
Definition: strCat.hh:124
size_t size() const
Definition: strCat.hh:119
ConcatViaString(std::string s_)
Definition: strCat.hh:114
constexpr void repeat(T n, Op op)
Repeat the given operation 'op' 'n' times.
Definition: xrange.hh:148