Line data Source code
1 : /** @file flatstring.hpp
2 : *
3 : * Author: Roland Conybeare
4 : **/
5 :
6 : #pragma once
7 :
8 : #include <string_view>
9 : #include <sstream>
10 : #include <algorithm>
11 : #include <memory>
12 :
13 : namespace xo {
14 : /** @class flatstring
15 : * @brief class to represent a string with a fixed amount of storage space.
16 : *
17 : * - Flatstring memory layout is a fixed-size, null-terminated char array.
18 : * - With a few exceptions, flatstring methods are noexcept.
19 : * @c flatstring<N>::at() may throw, for consistency with @c std::string::at() behavior
20 : * - Construction and concatenation of flatstrings are constexpr,
21 : * and can be done at compile time.
22 : * We rely on this in related projects (e.g. https://github.com:rconybea/xo-unit)
23 : * - Preserves as much of the c++23 @c std::string api as practicable
24 : *
25 : * @c N includes mandatory null terminator, so we require @c N > 0.
26 : *
27 : * @invariant all flatstring instances are null-terminated.
28 : * @invariant sizeof(flatstring<N>) == N
29 : **/
30 : template <std::size_t N>
31 : struct flatstring {
32 : /** @defgroup flatstring-types template types
33 : * @brief Template types exposed by @c flatstring<N>
34 : **/
35 : ///@{
36 : /** @brief character traits for this flatstring **/
37 : using traits_type = std::char_traits<char>;
38 : /** @brief type of each character in this flatstring **/
39 : using value_type = char;
40 : using allocator_type = std::allocator<char>;
41 : using size_type = std::allocator_traits<allocator_type>::size_type;
42 : using difference_type = std::allocator_traits<allocator_type>::difference_type;
43 : /** @brief type of a character reference **/
44 : using reference = value_type &;
45 : /** @brief type of a readonly character reference **/
46 : using const_reference = const value_type &;
47 : using pointer = std::allocator_traits<allocator_type>::pointer;
48 : using const_pointer = std::allocator_traits<allocator_type>::const_pointer;
49 : /** @brief representation for a read/write iterator **/
50 : using iterator = char *;
51 : /** @brief representation for a readonly iterator **/
52 : using const_iterator = const char *;
53 :
54 : /** @brief representation for a read/write reverse iterator
55 : *
56 : * constexpr implementation is tricky here, since we can't
57 : * form the address 'just before the beginning of the string' for @p rend()
58 : * without losing constexprness (at least with gcc 13.1)
59 : *
60 : * Instead iterator always refers to the address immediately after its
61 : * real target. This works since @c rbegin() refers to the char just before
62 : * trailing null
63 : **/
64 : struct reverse_iterator {
65 : public:
66 52 : constexpr reverse_iterator(char * p) : p_{p} {}
67 :
68 : constexpr bool _has_pointer() const { return p_ != nullptr; }
69 :
70 416 : constexpr bool operator==(const reverse_iterator & rhs) const noexcept {
71 416 : return p_ == rhs.p_;
72 : }
73 :
74 : constexpr char & operator* () const { return *(p_ - 1); }
75 :
76 364 : constexpr reverse_iterator & operator++ () {
77 364 : --p_;
78 364 : return *this;
79 : }
80 :
81 : constexpr reverse_iterator operator++ (int) {
82 : reverse_iterator copy = *this;
83 : --p_;
84 : return copy;
85 : }
86 :
87 : private:
88 : char * p_;
89 : };
90 :
91 : /** @brief representation for a readonly reverse iterator
92 : *
93 : * constexpr implementation is tricky here, since we can't
94 : * form the address 'just before the beginning of the string' for @p rend()
95 : * without losing constexprness (at least with gcc 13.1)
96 : *
97 : * Instead iterator always refers to the address immediately after its
98 : * real target. This works since @c rbegin() refers to the char just before
99 : * trailing null
100 : **/
101 : struct const_reverse_iterator {
102 : public:
103 26 : constexpr const_reverse_iterator(const char * p) : p_{p} {}
104 :
105 : constexpr bool _has_pointer() const { return p_ != nullptr; }
106 :
107 208 : constexpr bool operator==(const const_reverse_iterator & rhs) const noexcept {
108 208 : return p_ == rhs.p_;
109 : }
110 :
111 : constexpr const char & operator* () const { return *(p_ - 1); }
112 :
113 182 : constexpr const_reverse_iterator & operator++ () {
114 182 : --p_;
115 182 : return *this;
116 : }
117 :
118 : constexpr const_reverse_iterator operator++ (int) {
119 : const_reverse_iterator copy = *this;
120 : --p_;
121 : return copy;
122 : }
123 :
124 : private:
125 : const char * p_;
126 : };
127 : ///@}
128 :
129 : /** @defgroup flatstring-constants constants **/
130 : ///@{
131 : static constexpr const size_type npos = size_type(-1);
132 :
133 : /** @brief capacity of this flatstring, including final null terminator.
134 : *
135 : * @note not present in @c std::string api
136 : **/
137 : static constexpr const std::size_t fixed_capacity = N;
138 : ///@}
139 :
140 : public:
141 : /** @defgroup flatstring-ctor constructors **/
142 : ///@{
143 : /** @brief create empty string literal. Will contain N null characters
144 : *
145 : * Example
146 : * @code
147 : * constexpr flatstring<5> s1;
148 : * static_assert(s1.empty());
149 : * @endcode
150 : **/
151 182 : constexpr flatstring() noexcept {
152 : /* note: clang verifies that we fully initialize memory; otherwise will not recognize
153 : * instance as constexpr
154 : */
155 104 : std::fill_n(value_, N, '\0');
156 : }
157 :
158 : /** @brief create string literal from a correctly-sized char array
159 : *
160 : * Example
161 : * @code
162 : * constexpr flatstring s1("hello");
163 : * static_assert(s1.size() > 0);
164 : * @endcode
165 : **/
166 : constexpr flatstring(const char (&str)[N]) noexcept {
167 : std::copy_n(str, N, value_);
168 : }
169 : ///@}
170 :
171 : /** @brief construct from another flatstring **/
172 : template <std::size_t N2>
173 : static constexpr flatstring from_flatstring(const flatstring<N2> & str) noexcept {
174 : flatstring retval;
175 :
176 : retval.assign(str);
177 :
178 : return retval;
179 : }
180 :
181 : /** @brief construct from char array **/
182 : template <std::size_t N2>
183 : static constexpr flatstring from_chars(const char (&str)[N2]) noexcept {
184 : flatstring retval;
185 :
186 : retval.assign(str);
187 :
188 : return retval;
189 : }
190 :
191 : /** @brief construct from integer **/
192 : static constexpr flatstring from_int(int x) {
193 : constexpr size_t buf_z = 20;
194 :
195 : bool negative_flag = (x < 0);
196 : std::size_t i = buf_z;
197 : char buf[buf_z];
198 : std::fill_n(buf, N, '\0');
199 :
200 : if (negative_flag)
201 : x = -x;
202 :
203 : buf[--i] = '\0';
204 :
205 : if (x == 0)
206 : buf[--i] = '0';
207 :
208 : while ((i > 0) && (x != 0)) {
209 : buf[--i] = ('0' + x % 10);
210 : x = x / 10;
211 : }
212 :
213 : if ((i > 0) && negative_flag)
214 : buf[--i] = '-';
215 :
216 : char retv[N];
217 : std::fill_n(retv, N, '\0');
218 : std::copy_n(buf + i, buf_z - i, retv);
219 :
220 : return retv;
221 : }
222 :
223 : /** @defgroup flatstring-properties property-methods **/
224 : ///@{
225 : /** @brief true if (and only if) string is empty **/
226 104 : constexpr bool empty() const noexcept { return value_[0] == '\0'; }
227 : /** @brief returns current size of this string **/
228 5062 : constexpr size_type size() const noexcept {
229 5062 : return this->cend() - this->cbegin();
230 : }
231 : /** @brief synonym for @c size() **/
232 52 : constexpr size_type length() const noexcept { return size(); }
233 :
234 : constexpr size_type capacity() const noexcept { return fixed_capacity - 1; }
235 : constexpr size_type max_size() const noexcept { return fixed_capacity - 1; }
236 :
237 : /** @brief contents as plain old C-style string. **/
238 2550 : constexpr const char * c_str() const noexcept { return value_; }
239 : ///@}
240 :
241 : /** @defgroup flatstring-access access methods **/
242 : ///@{
243 : /** @brief return char at position @p pos in this string (counting from zero).
244 : *
245 : * Throws @c std::out_of_range exception if @p pos >= @c N
246 : **/
247 : constexpr value_type & at(size_type pos) throw() { return this->at_aux(pos); }
248 : constexpr const value_type & at(size_type pos) const throw() { return const_cast<flatstring *>(this)->at_aux(pos); }
249 :
250 : /** @brief return char at position @p pos in this string (counting from zero).
251 : *
252 : * Does not check bounds: undefined behavior if @p pos >= @c N
253 : *
254 : * @pre 0<=pos<=N-1
255 : **/
256 364 : constexpr value_type & operator[](size_type pos) noexcept { return value_[pos]; }
257 : constexpr const value_type & operator[](size_type pos) const noexcept { return value_[pos]; }
258 : ///@}
259 :
260 : /** @defgroup flatstring-iterators iterators **/
261 : ///@{
262 26 : constexpr iterator begin() { return &value_[0]; }
263 416 : constexpr iterator end() { return this->last<iterator>(); }
264 :
265 26 : constexpr const_iterator cbegin() const { return &value_[0]; }
266 5070 : constexpr const_iterator cend() const { return const_cast<flatstring*>(this)->last<iterator>(); }
267 26 : constexpr const_iterator begin() const { return cbegin(); }
268 208 : constexpr const_iterator end() const { return cend(); }
269 :
270 52 : constexpr reverse_iterator rbegin() { return reverse_iterator(this->last<iterator>()); }
271 52 : constexpr reverse_iterator rend() { return reverse_iterator(&value_[0]); }
272 26 : constexpr const_reverse_iterator crbegin() const { return const_cast<flatstring*>(this)->last<iterator>(); }
273 26 : constexpr const_reverse_iterator crend() const { return &value_[0]; }
274 : constexpr const_reverse_iterator rbegin() const { return crbegin(); }
275 : constexpr const_reverse_iterator rend() const { return crend(); }
276 : ///@}
277 :
278 : /** @defgroup flatstring-assign assignment **/
279 : ///@{
280 : /** @brief put string into empty state. fills entire char array with nulls **/
281 28 : constexpr void clear() noexcept { std::fill_n(value_, N, '\0'); }
282 :
283 : /** @brief replace contents with min(count,N-1) copies of character ch **/
284 26 : constexpr flatstring & assign(size_type count, value_type ch) {
285 26 : std::size_t pos = 0;
286 416 : for (; pos < std::min(count, N-1); ++pos)
287 182 : value_[pos] = ch;
288 52 : for (; pos < N; ++pos)
289 26 : value_[pos] = '\0';
290 :
291 26 : return *this;
292 : }
293 : /** @brief replace contents with first N-1 characters of @p x **/
294 2288 : constexpr flatstring & assign(const flatstring & x) {
295 13182 : for (std::size_t pos = 0; pos < N-1; ++pos)
296 10738 : value_[pos] = x.value_[pos];
297 2444 : value_[N-1] = '\0';
298 : return *this;
299 : }
300 : /** @brief replace contents with substring [pos,pos+count] of str **/
301 : template <std::size_t N2>
302 2288 : constexpr flatstring & assign(const flatstring<N2> & x,
303 : size_type pos, size_type count = npos) {
304 2288 : std::size_t i = 0;
305 2288 : for (;
306 7510 : i < std::min(std::min(count,
307 : (x.fixed_capacity-1 > pos)
308 7510 : ? x.fixed_capacity-1 - pos
309 : : 0ul),
310 15020 : N-1);
311 : ++i)
312 5222 : value_[i] = x.value_[pos+i];
313 9364 : for (; i < N; ++i)
314 7076 : value_[i] = '\0';
315 :
316 2288 : return *this;
317 : }
318 : /** @brief replace contents with range [cstr, cstr + count) **/
319 156 : constexpr flatstring & assign(const value_type * cstr, size_type count) {
320 156 : std::size_t i = 0;
321 702 : for (; i < std::min(N-1, count); ++i)
322 322 : value_[i] = cstr[i];
323 718 : for (; i < N; ++i)
324 562 : value_[i] = '\0';
325 :
326 156 : return *this;
327 : }
328 : /** @brief replace contents with C-style string cstr **/
329 78 : constexpr flatstring & assign(const value_type * cstr) {
330 78 : std::size_t i = 0;
331 78 : const value_type * p = cstr;
332 500 : while ((i < N-1) && (*p != '\0')) {
333 422 : value_[i] = *p;
334 422 : ++i;
335 422 : ++p;
336 : }
337 254 : for (; i < N; ++i)
338 176 : value_[i] = '\0';
339 :
340 76 : return *this;
341 : }
342 : /** @brief replace contents with iterator range [first, last) **/
343 : template <typename InputIter>
344 : constexpr flatstring & assign(InputIter first, InputIter last) {
345 : InputIter ix = first;
346 : std::size_t i = 0;
347 : for (; (i < N-1) && (ix != last); ++i) {
348 : value_[i] = *ix;
349 : }
350 : for (; i < N; ++i)
351 : value_[i] = '\0';
352 : return *this;
353 : }
354 : ///@}
355 :
356 : /** @defgroup flatstring-append append **/
357 : ///@{
358 : /** @brief append contents of null-terminated string cstr **/
359 : constexpr flatstring & append(const value_type * cstr) {
360 : std::size_t z = this->size();
361 : std::size_t i = 0;
362 : for (; (z+i < N-1) && (cstr[i] != '\0'); ++i)
363 : value_[z+i] = cstr[i];
364 : for (; z+i < N; ++i)
365 : value_[z+i] = '\0';
366 :
367 : return *this;
368 : }
369 :
370 : /** @brief append the first count members of cstr[] **/
371 : constexpr flatstring & append(const value_type * cstr, size_type count) {
372 : std::size_t z = this->size();
373 : std::size_t i = 0;
374 : for (; z+i < std::min(N-1, count); ++i)
375 : value_[z+i] = cstr[i];
376 : for (; z+i < N; ++i)
377 : value_[z+i] = '\0';
378 :
379 : return *this;
380 : }
381 :
382 : /** @brief append substring [pos .. pos + count) of x **/
383 : template <std::size_t N2>
384 : constexpr flatstring & append(const flatstring<N2> & x,
385 : size_type pos, size_type count = npos)
386 : {
387 : std::size_t i_src = 0;
388 : std::size_t i_dest = size();
389 : for (;
390 : i_src < std::min(std::min(count,
391 : (x.fixed_capacity-1 > pos)
392 : ? x.fixed_capacity-1 - pos
393 : : 0ul),
394 : N-1);
395 : ++i_src, ++i_dest)
396 : value_[i_dest] = x.value_[pos+i_src];
397 : for (; i_dest < N; ++i_dest)
398 : value_[i_dest] = '\0';
399 :
400 : return *this;
401 : }
402 : ///@}
403 :
404 : // insert
405 : // insert_range
406 : // erase
407 : // push_back
408 : // append
409 : // append_range
410 : // operator+=
411 : // replace
412 : // replace_with_range
413 : // copy
414 : // find
415 : // rfind
416 : // find_first_of
417 : // find_first_not_of
418 : // find_last_of
419 : // find_last_not_of
420 : // compare
421 : // starts_with
422 : // end_with
423 : // contains
424 : // substr
425 :
426 : /** @defgroup flatstring-conversion-operators conversion operators **/
427 : ///@{
428 : /** @brief conversion to @c std::string
429 : *
430 : * Example
431 : * @code
432 : * constexpr flatstring s("bazinga!");
433 : * std::string s_str{s.str()};
434 : * @endcode
435 : **/
436 26 : std::string str() const { return std::string(value_); }
437 :
438 : /** @brief conversion operator to string_view **/
439 5412 : constexpr operator std::string_view() const noexcept { return std::string_view(value_); }
440 :
441 : /** @brief conversion operator to C-style string.
442 : *
443 : * Example
444 : * @code
445 : * constexpr flatstring s("obey gravity..");
446 : * strcmp(s, "obey...");
447 : * @endcode
448 : **/
449 2548 : constexpr operator const char * () const noexcept { return value_; }
450 : ///@}
451 :
452 : private:
453 : constexpr value_type & at_aux(size_type pos) {
454 : if (pos >= N) {
455 : #ifdef NOT_USING
456 : /* note: can't build stringstream at compile time */
457 : std::stringstream ss;
458 : ss << "flatstring<" << N << ">::at: expected pos=[" << pos << "] in interval [0," << N << ")" << std::endl;
459 : #endif
460 :
461 : throw std::out_of_range("at_aux: range error");
462 : }
463 :
464 : return (*this)[pos];
465 : }
466 :
467 : template <typename Iterator>
468 5244 : constexpr Iterator last() noexcept {
469 5252 : Iterator p = &value_[N-1];
470 :
471 : /* search backward for first padding '\0' */
472 10282 : while ((p > &value_[0]) && (*(p-1) == '\0'))
473 5038 : --p;
474 :
475 : return p;
476 : }
477 :
478 : public:
479 : /** @defgroup flatstring-instance-variables instance variables **/
480 : ///@{
481 :
482 : /** @brief characters comprising this literal string **/
483 : char value_[N];
484 :
485 : ///@}
486 : };
487 :
488 : /** @brief sentinel type, for forbidden stringliteral with no space for a null terminator **/
489 : template <>
490 : struct flatstring<0> { flatstring() = delete; };
491 :
492 : // non-member functions
493 : // erase
494 : // erase_if
495 : // operator<<
496 : // operator>>
497 : // getline
498 : // stoi
499 : // stol
500 : // stoll
501 : // stoul
502 : // stoull
503 : // stof
504 : // stod
505 : // stold
506 :
507 : #ifdef NOT_USING
508 : /** @brief all_same_v<T1, .., Tn> is true iff types T1 = .. = Tn
509 : **/
510 : template < typename First, typename... Rest >
511 : constexpr auto
512 : all_same_v = std::conjunction_v< std::is_same<First, Rest>... >;
513 : #endif
514 :
515 : /** @brief Concatenate flatstrings, possibly mixed with C-style char arrays
516 : *
517 : * Example:
518 : * @code
519 : * constexpr auto s = flatstring_concat(flatstring("hello"),
520 : * ", ",
521 : * flatstring("world"));
522 : * static_assert(s.capacity == 13);
523 : * @endcode
524 : *
525 : **/
526 : template < typename... Ts>
527 : constexpr auto
528 78 : flatstring_concat(Ts && ... args) noexcept
529 : {
530 : #ifdef NOT_USING
531 : static_assert(all_same_v<std::decay_t<Ts>...>,
532 : "string must share the same char type");
533 :
534 : using char_type = std::remove_const_t< std::remove_pointer_t < std::common_type_t < Ts... > > >;
535 : #endif
536 : using value_type = char;
537 :
538 : /** n1: total number of bytes used by arguments **/
539 78 : constexpr std::size_t n1 = (sizeof(Ts) + ...);
540 : /** z1: each string arg has a null terminator included in its size,
541 : * z1 is the number of arguments in parameter pack Ts,
542 : * which equals the number of null terminators used
543 : **/
544 78 : constexpr std::size_t z1 = sizeof...(Ts);
545 :
546 : /** n: number of chars in concatenated string. +1 for final null **/
547 78 : constexpr std::size_t n
548 : = (n1 / sizeof(value_type)) - z1 + 1;
549 :
550 78 : flatstring<n> result;
551 :
552 78 : std::size_t pos = 0;
553 :
554 294 : auto detail_concat = [ &pos, &result ](auto && arg) {
555 : /* tradeoff here:
556 : * 1. flatstring::size() is constexpr, so we can concat strings with size() < capacity().
557 : * (note flatstring::from_int() likely creates such strings)
558 : * 2. ..but no size() method on char arrays.
559 : * 3. std::size() not suitable: size of char array includes null terminator,
560 : * while flatstring.size() excludes it, and flatstring behavior is consistent with
561 : * std::string.size()
562 : * Consequence of using arg.size() here; have to wrap char arrays with
563 : * flatstring() to use them with flatstring_concat()
564 : */
565 208 : auto count = arg.size();
566 : //constexpr auto count = (sizeof(arg) - sizeof(value_type)) / sizeof(value_type);
567 :
568 208 : std::copy_n(/*arg.c_str()*/ static_cast<const char *>(arg), count, result.value_ + pos);
569 200 : pos += count;
570 : };
571 :
572 78 : (detail_concat(args), ...);
573 :
574 78 : return result;
575 : }
576 :
577 : /** @brief compare two flatstrings lexicographically.
578 : *
579 : * Example:
580 : * @code
581 : * constexpr auto cmp = flatstring_compare(stringliteral("foo"), stringliteral("bar"));
582 : * static_assert(cmp > 0);
583 : * @endcode
584 : **/
585 : template <std::size_t N1,
586 : std::size_t N2>
587 : constexpr auto
588 : flatstring_compare(const flatstring<N1> & s1,
589 : const flatstring<N2> & s2) noexcept
590 : {
591 : return (std::string_view(s1.value_) <=> std::string_view(s2.value_));
592 : }
593 :
594 : /** @defgroup flatstring-3way-compare 3way-compare **/
595 : ///@{
596 : /** @brief 3-way compare for two flatstrings
597 : *
598 : * Example
599 : * @code
600 : * constexpr auto cmp = (flatstring("foo") <=> flatstring("bar"));
601 : * static_assert(cmp != 0);
602 : * @endcode
603 : **/
604 : template <std::size_t N1,
605 : std::size_t N2>
606 : constexpr auto
607 2680 : operator<=>(const flatstring<N1> & s1,
608 : const flatstring<N2> & s2) noexcept
609 : {
610 2680 : return (std::string_view(s1) <=> std::string_view(s2));
611 : }
612 :
613 : /** @brief equality comparison for two flatstrings.
614 : *
615 : * Example
616 : * @code
617 : * constexpr bool cmp = (flatstring("foo") == flatstring("foo"));
618 : * static_assert(cmp == true);
619 : * @endcode
620 : *
621 : * @note spaceship operator alone isn't sufficient to get this defined,
622 : * at least with gcc 13.1
623 : **/
624 : template <std::size_t N1,
625 : std::size_t N2>
626 : constexpr bool
627 2654 : operator==(const flatstring<N1> & s1,
628 : const flatstring<N2> & s2) noexcept
629 : {
630 2654 : return ((s1 <=> s2) == std::strong_ordering::equal);
631 : }
632 : ///@}
633 : } /*namespace xo*/
634 :
635 : /** end stringliteral.hpp **/
|
