src/ceph/src/common/sstring.hh

   1 /*
   2  * This file is open source software, licensed to you under the terms
   3  * of the Apache License, Version 2.0 (the "License").  See the NOTICE file
   4  * distributed with this work for additional information regarding copyright
   5  * ownership.  You may not use this file except in compliance with the License.
   6  *
   7  * You may obtain a copy of the License at
   8  *
   9  *   http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing,
  12  * software distributed under the License is distributed on an
  13  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  14  * KIND, either express or implied.  See the License for the
  15  * specific language governing permissions and limitations
  16  * under the License.
  17  */
  18 /*
  19  * Copyright 2014 Cloudius Systems
  20  */
  21 /*
  22  * C++2014 dependencies removed.  Uses of std::string_view adapted to
  23  * boost::string_ref.  Matt Benjamin <mbenjamin@redhat.com>
  24  */
  25
  26 #ifndef SSTRING_HH_
  27 #define SSTRING_HH_
  28
  29 #include <type_traits>
  30 #include <boost/utility/string_view.hpp>
  31
  32 #include "include/buffer.h"
  33 #include "include/denc.h"
  34
  35 template <typename char_type, typename Size, Size max_size>
  36 class basic_sstring;
  37
  38 using sstring = basic_sstring<char, uint32_t, 15>;
  39
  40 template <typename string_type = sstring, typename T>
  41 inline string_type to_sstring(T value);
  42
  43 template <typename char_type, typename Size, Size max_size>
  44 class basic_sstring {
  45     static_assert(
  46             (std::is_same<char_type, char>::value
  47              || std::is_same<char_type, signed char>::value
  48              || std::is_same<char_type, unsigned char>::value),
  49             "basic_sstring only supports single byte char types");
  50     union contents {
  51         struct external_type {
  52             char_type* str;
  53             Size size;
  54             int8_t pad;
  55         } external;
  56         struct internal_type {
  57             char_type str[max_size];
  58             int8_t size;
  59         } internal;
  60         static_assert(sizeof(external_type) <= sizeof(internal_type), "max_size too small");
  61         static_assert(max_size <= 127, "max_size too large");
  62     } u;
  63     bool is_internal() const noexcept {
  64         return u.internal.size >= 0;
  65     }
  66     bool is_external() const noexcept {
  67         return !is_internal();
  68     }
  69     const char_type* str() const {
  70         return is_internal() ? u.internal.str : u.external.str;
  71     }
  72     char_type* str() {
  73         return is_internal() ? u.internal.str : u.external.str;
  74     }
  75
  76     template <typename string_type, typename T>
  77     static inline string_type to_sstring_sprintf(T value, const char* fmt) {
  78         char tmp[sizeof(value) * 3 + 2];
  79         auto len = std::sprintf(tmp, fmt, value);
  80         using ch_type = typename string_type::value_type;
  81         return string_type(reinterpret_cast<ch_type*>(tmp), len);
  82     }
  83
  84     template <typename string_type>
  85     static inline string_type to_sstring(int value) {
  86         return to_sstring_sprintf<string_type>(value, "%d");
  87     }
  88
  89     template <typename string_type>
  90     static inline string_type to_sstring(unsigned value) {
  91         return to_sstring_sprintf<string_type>(value, "%u");
  92     }
  93
  94     template <typename string_type>
  95     static inline string_type to_sstring(long value) {
  96         return to_sstring_sprintf<string_type>(value, "%ld");
  97     }
  98
  99     template <typename string_type>
 100     static inline string_type to_sstring(unsigned long value) {
 101         return to_sstring_sprintf<string_type>(value, "%lu");
 102     }
 103
 104     template <typename string_type>
 105     static inline string_type to_sstring(long long value) {
 106         return to_sstring_sprintf<string_type>(value, "%lld");
 107     }
 108
 109     template <typename string_type>
 110     static inline string_type to_sstring(unsigned long long value) {
 111         return to_sstring_sprintf<string_type>(value, "%llu");
 112     }
 113
 114     template <typename string_type>
 115     static inline string_type to_sstring(float value) {
 116         return to_sstring_sprintf<string_type>(value, "%g");
 117     }
 118
 119     template <typename string_type>
 120     static inline string_type to_sstring(double value) {
 121         return to_sstring_sprintf<string_type>(value, "%g");
 122     }
 123
 124     template <typename string_type>
 125     static inline string_type to_sstring(long double value) {
 126         return to_sstring_sprintf<string_type>(value, "%Lg");
 127     }
 128
 129     template <typename string_type>
 130     static inline string_type to_sstring(const char* value) {
 131         return string_type(value);
 132     }
 133
 134     template <typename string_type>
 135     static inline string_type to_sstring(sstring value) {
 136         return value;
 137     }
 138
 139 public:
 140     using value_type = char_type;
 141     using traits_type = std::char_traits<char_type>;
 142     using allocator_type = std::allocator<char_type>;
 143     using reference = char_type&;
 144     using const_reference = const char_type&;
 145     using pointer = char_type*;
 146     using const_pointer = const char_type*;
 147     using iterator = char_type*;
 148     using const_iterator = const char_type*;
 149     // FIXME: add reverse_iterator and friend
 150     using difference_type = ssize_t;  // std::make_signed_t<Size> can be too small
 151     using size_type = Size;
 152     static constexpr size_type  npos = static_cast<size_type>(-1);
 153 public:
 154     struct initialized_later {};
 155
 156     basic_sstring() noexcept {
 157         u.internal.size = 0;
 158         u.internal.str[0] = '\0';
 159     }
 160     basic_sstring(const basic_sstring& x) {
 161         if (x.is_internal()) {
 162             u.internal = x.u.internal;
 163         } else {
 164             u.internal.size = -1;
 165             u.external.str = reinterpret_cast<char_type*>(std::malloc(x.u.external.size + 1));
 166             if (!u.external.str) {
 167                 throw std::bad_alloc();
 168             }
 169             std::copy(x.u.external.str, x.u.external.str + x.u.external.size + 1, u.external.str);
 170             u.external.size = x.u.external.size;
 171         }
 172     }
 173     basic_sstring(basic_sstring&& x) noexcept {
 174         u = x.u;
 175         x.u.internal.size = 0;
 176         x.u.internal.str[0] = '\0';
 177     }
 178     basic_sstring(initialized_later, size_t size) {
 179         if (size_type(size) != size) {
 180             throw std::overflow_error("sstring overflow");
 181         }
 182         if (size + 1 <= sizeof(u.internal.str)) {
 183             u.internal.str[size] = '\0';
 184             u.internal.size = size;
 185         } else {
 186             u.internal.size = -1;
 187             u.external.str = reinterpret_cast<char_type*>(std::malloc(size + 1));
 188             if (!u.external.str) {
 189                 throw std::bad_alloc();
 190             }
 191             u.external.size = size;
 192             u.external.str[size] = '\0';
 193         }
 194     }
 195     basic_sstring(const char_type* x, size_t size) {
 196         if (size_type(size) != size) {
 197             throw std::overflow_error("sstring overflow");
 198         }
 199         if (size + 1 <= sizeof(u.internal.str)) {
 200             std::copy(x, x + size, u.internal.str);
 201             u.internal.str[size] = '\0';
 202             u.internal.size = size;
 203         } else {
 204             u.internal.size = -1;
 205             u.external.str = reinterpret_cast<char_type*>(std::malloc(size + 1));
 206             if (!u.external.str) {
 207                 throw std::bad_alloc();
 208             }
 209             u.external.size = size;
 210             std::copy(x, x + size, u.external.str);
 211             u.external.str[size] = '\0';
 212         }
 213     }
 214
 215     basic_sstring(size_t size, char_type x) : basic_sstring(initialized_later(), size) {
 216         memset(begin(), x, size);
 217     }
 218
 219     basic_sstring(const char* x) : basic_sstring(reinterpret_cast<const char_type*>(x), std::strlen(x)) {}
 220     basic_sstring(std::basic_string<char_type>& x) : basic_sstring(x.c_str(), x.size()) {}
 221     basic_sstring(std::initializer_list<char_type> x) : basic_sstring(x.begin(), x.end() - x.begin()) {}
 222     basic_sstring(const char_type* b, const char_type* e) : basic_sstring(b, e - b) {}
 223     basic_sstring(const std::basic_string<char_type>& s)
 224         : basic_sstring(s.data(), s.size()) {}
 225     template <typename InputIterator>
 226     basic_sstring(InputIterator first, InputIterator last)
 227             : basic_sstring(initialized_later(), std::distance(first, last)) {
 228         std::copy(first, last, begin());
 229     }
 230     ~basic_sstring() noexcept {
 231         if (is_external()) {
 232             std::free(u.external.str);
 233         }
 234     }
 235     basic_sstring& operator=(const basic_sstring& x) {
 236         basic_sstring tmp(x);
 237         swap(tmp);
 238         return *this;
 239     }
 240     basic_sstring& operator=(basic_sstring&& x) noexcept {
 241         if (this != &x) {
 242             swap(x);
 243             x.reset();
 244         }
 245         return *this;
 246     }
 247     operator std::basic_string<char_type>() const {
 248         return { str(), size() };
 249     }
 250     size_t size() const noexcept {
 251         return is_internal() ? u.internal.size : u.external.size;
 252     }
 253
 254     size_t length() const noexcept {
 255         return size();
 256     }
 257
 258     size_t find(char_type t, size_t pos = 0) const noexcept {
 259         const char_type* it = str() + pos;
 260         const char_type* end = str() + size();
 261         while (it < end) {
 262             if (*it == t) {
 263                 return it - str();
 264             }
 265             it++;
 266         }
 267         return npos;
 268     }
 269
 270     size_t find(const basic_sstring& s, size_t pos = 0) const noexcept {
 271         const char_type* it = str() + pos;
 272         const char_type* end = str() + size();
 273         const char_type* c_str = s.str();
 274         const char_type* c_str_end = s.str() + s.size();
 275
 276         while (it < end) {
 277             auto i = it;
 278             auto j = c_str;
 279             while ( i < end && j < c_str_end && *i == *j) {
 280                 i++;
 281                 j++;
 282             }
 283             if (j == c_str_end) {
 284                 return it - str();
 285             }
 286             it++;
 287         }
 288         return npos;
 289     }
 290
 291     /**
 292      * find_last_of find the last occurrence of c in the string.
 293      * When pos is specified, the search only includes characters
 294      * at or before position pos.
 295      *
 296      */
 297     size_t find_last_of (char_type c, size_t pos = npos) const noexcept {
 298         const char_type* str_start = str();
 299         if (size()) {
 300             if (pos >= size()) {
 301                 pos = size() - 1;
 302             }
 303             const char_type* p = str_start + pos + 1;
 304             do {
 305                 p--;
 306                 if (*p == c) {
 307                     return (p - str_start);
 308                 }
 309             } while (p != str_start);
 310         }
 311         return npos;
 312     }
 313
 314     /**
 315      *  Append a C substring.
 316      *  @param s  The C string to append.
 317      *  @param n  The number of characters to append.
 318      *  @return  Reference to this string.
 319      */
 320     basic_sstring& append (const char_type* s, size_t n) {
 321         basic_sstring ret(initialized_later(), size() + n);
 322         std::copy(begin(), end(), ret.begin());
 323         std::copy(s, s + n, ret.begin() + size());
 324         *this = std::move(ret);
 325         return *this;
 326     }
 327
 328     /**
 329      *  Replace characters with a value of a C style substring.
 330      *
 331      */
 332     basic_sstring& replace(size_type pos, size_type n1, const char_type* s,
 333              size_type n2) {
 334         if (pos > size()) {
 335             throw std::out_of_range("sstring::replace out of range");
 336         }
 337
 338         if (n1 > size() - pos) {
 339             n1 = size() - pos;
 340         }
 341
 342         if (n1 == n2) {
 343             if (n2) {
 344                 std::copy(s, s + n2, begin() + pos);
 345             }
 346             return *this;
 347         }
 348         basic_sstring ret(initialized_later(), size() + n2 - n1);
 349         char_type* p= ret.begin();
 350         std::copy(begin(), begin() + pos, p);
 351         p += pos;
 352         if (n2) {
 353             std::copy(s, s + n2, p);
 354         }
 355         p += n2;
 356         std::copy(begin() + pos + n1, end(), p);
 357         *this = std::move(ret);
 358         return *this;
 359     }
 360
 361     template <class InputIterator>
 362     basic_sstring& replace (const_iterator i1, const_iterator i2,
 363             InputIterator first, InputIterator last) {
 364         if (i1 < begin() || i1 > end() || i2 < begin()) {
 365             throw std::out_of_range("sstring::replace out of range");
 366         }
 367         if (i2 > end()) {
 368             i2 = end();
 369         }
 370
 371         if (i2 - i1 == last - first) {
 372             //in place replacement
 373             std::copy(first, last, const_cast<char_type*>(i1));
 374             return *this;
 375         }
 376         basic_sstring ret(initialized_later(), size() + (last - first) - (i2 - i1));
 377         char_type* p = ret.begin();
 378         p = std::copy(cbegin(), i1, p);
 379         p = std::copy(first, last, p);
 380         std::copy(i2, cend(), p);
 381         *this = std::move(ret);
 382         return *this;
 383     }
 384
 385     iterator erase(iterator first, iterator last) {
 386         size_t pos = first - begin();
 387         replace(pos, last - first, nullptr, 0);
 388         return begin() + pos;
 389     }
 390
 391     /**
 392      * Inserts additional characters into the string right before
 393      * the character indicated by p.
 394      */
 395     template <class InputIterator>
 396     void insert(const_iterator p, InputIterator beg, InputIterator end) {
 397         replace(p, p, beg, end);
 398     }
 399
 400     /**
 401      *  Returns a read/write reference to the data at the last
 402      *  element of the string.
 403      *  This function shall not be called on empty strings.
 404      */
 405     reference
 406     back() noexcept {
 407         return operator[](size() - 1);
 408     }
 409
 410     /**
 411      *  Returns a  read-only (constant) reference to the data at the last
 412      *  element of the string.
 413      *  This function shall not be called on empty strings.
 414      */
 415     const_reference
 416     back() const noexcept {
 417         return operator[](size() - 1);
 418     }
 419
 420     basic_sstring substr(size_t from, size_t len = npos)  const {
 421         if (from > size()) {
 422             throw std::out_of_range("sstring::substr out of range");
 423         }
 424         if (len > size() - from) {
 425             len = size() - from;
 426         }
 427         if (len == 0) {
 428             return "";
 429         }
 430         return { str() + from , len };
 431     }
 432
 433     const char_type& at(size_t pos) const {
 434         if (pos >= size()) {
 435             throw std::out_of_range("sstring::at out of range");
 436         }
 437         return *(str() + pos);
 438     }
 439
 440     char_type& at(size_t pos) {
 441         if (pos >= size()) {
 442             throw std::out_of_range("sstring::at out of range");
 443         }
 444         return *(str() + pos);
 445     }
 446
 447     bool empty() const noexcept {
 448         return u.internal.size == 0;
 449     }
 450     void reset() noexcept {
 451         if (is_external()) {
 452             std::free(u.external.str);
 453         }
 454         u.internal.size = 0;
 455         u.internal.str[0] = '\0';
 456     }
 457
 458     int compare(const basic_sstring& x) const noexcept {
 459         auto n = traits_type::compare(begin(), x.begin(), std::min(size(), x.size()));
 460         if (n != 0) {
 461             return n;
 462         }
 463         if (size() < x.size()) {
 464             return -1;
 465         } else if (size() > x.size()) {
 466             return 1;
 467         } else {
 468             return 0;
 469         }
 470     }
 471
 472     int compare(size_t pos, size_t sz, const basic_sstring& x) const {
 473         if (pos > size()) {
 474             throw std::out_of_range("pos larger than string size");
 475         }
 476
 477         sz = std::min(size() - pos, sz);
 478         auto n = traits_type::compare(begin() + pos, x.begin(), std::min(sz, x.size()));
 479         if (n != 0) {
 480             return n;
 481         }
 482         if (sz < x.size()) {
 483             return -1;
 484         } else if (sz > x.size()) {
 485             return 1;
 486         } else {
 487             return 0;
 488         }
 489     }
 490
 491     void swap(basic_sstring& x) noexcept {
 492         contents tmp;
 493         tmp = x.u;
 494         x.u = u;
 495         u = tmp;
 496     }
 497     const char_type* c_str() const {
 498         return str();
 499     }
 500     const char_type* begin() const { return str(); }
 501     const char_type* end() const { return str() + size(); }
 502     const char_type* cbegin() const { return str(); }
 503     const char_type* cend() const { return str() + size(); }
 504     char_type* begin() { return str(); }
 505     char_type* end() { return str() + size(); }
 506     bool operator==(const basic_sstring& x) const {
 507         return size() == x.size() && std::equal(begin(), end(), x.begin());
 508     }
 509     bool operator!=(const basic_sstring& x) const {
 510         return !operator==(x);
 511     }
 512     bool operator<(const basic_sstring& x) const {
 513         return compare(x) < 0;
 514     }
 515     basic_sstring operator+(const basic_sstring& x) const {
 516         basic_sstring ret(initialized_later(), size() + x.size());
 517         std::copy(begin(), end(), ret.begin());
 518         std::copy(x.begin(), x.end(), ret.begin() + size());
 519         return ret;
 520     }
 521     basic_sstring& operator+=(const basic_sstring& x) {
 522         return *this = *this + x;
 523     }
 524     char_type& operator[](size_type pos) {
 525         return str()[pos];
 526     }
 527     const char_type& operator[](size_type pos) const {
 528         return str()[pos];
 529     }
 530     operator boost::basic_string_view<char_type, traits_type>() const {
 531                 return boost::basic_string_view<char_type, traits_type>(str(), size());
 532     }
 533     template <typename string_type, typename T>
 534     friend inline string_type to_sstring(T value);
 535 };
 536 template <typename char_type, typename Size, Size max_size>
 537 constexpr Size basic_sstring<char_type, Size, max_size>::npos;
 538
 539 template <typename char_type, typename size_type, size_type Max, size_type N>
 540 inline
 541 basic_sstring<char_type, size_type, Max>
 542 operator+(const char(&s)[N], const basic_sstring<char_type, size_type, Max>& t) {
 543     using sstring = basic_sstring<char_type, size_type, Max>;
 544     // don't copy the terminating NUL character
 545     sstring ret(typename sstring::initialized_later(), N-1 + t.size());
 546     auto p = std::copy(std::begin(s), std::end(s)-1, ret.begin());
 547     std::copy(t.begin(), t.end(), p);
 548     return ret;
 549 }
 550
 551 template <size_t N>
 552 static inline
 553 size_t str_len(const char(&s)[N]) { return N - 1; }
 554
 555 template <size_t N>
 556 static inline
 557 const char* str_begin(const char(&s)[N]) { return s; }
 558
 559 template <size_t N>
 560 static inline
 561 const char* str_end(const char(&s)[N]) { return str_begin(s) + str_len(s); }
 562
 563 template <typename char_type, typename size_type, size_type max_size>
 564 static inline
 565 const char_type* str_begin(const basic_sstring<char_type, size_type, max_size>& s) { return s.begin(); }
 566
 567 template <typename char_type, typename size_type, size_type max_size>
 568 static inline
 569 const char_type* str_end(const basic_sstring<char_type, size_type, max_size>& s) { return s.end(); }
 570
 571 template <typename char_type, typename size_type, size_type max_size>
 572 static inline
 573 size_type str_len(const basic_sstring<char_type, size_type, max_size>& s) { return s.size(); }
 574
 575 template <typename First, typename Second, typename... Tail>
 576 static inline
 577 size_t str_len(const First& first, const Second& second, const Tail&... tail) {
 578     return str_len(first) + str_len(second, tail...);
 579 }
 580
 581 template <typename char_type, typename size_type, size_type max_size>
 582 inline
 583 void swap(basic_sstring<char_type, size_type, max_size>& x,
 584           basic_sstring<char_type, size_type, max_size>& y) noexcept
 585 {
 586     return x.swap(y);
 587 }
 588
 589 template <typename char_type, typename size_type, size_type max_size, typename char_traits>
 590 inline
 591 std::basic_ostream<char_type, char_traits>&
 592 operator<<(std::basic_ostream<char_type, char_traits>& os,
 593         const basic_sstring<char_type, size_type, max_size>& s) {
 594     return os.write(s.begin(), s.size());
 595 }
 596
 597 template <typename char_type, typename size_type, size_type max_size, typename char_traits>
 598 inline
 599 std::basic_istream<char_type, char_traits>&
 600 operator>>(std::basic_istream<char_type, char_traits>& is,
 601         basic_sstring<char_type, size_type, max_size>& s) {
 602     std::string tmp;
 603     is >> tmp;
 604     s = tmp;
 605     return is;
 606 }
 607
 608 namespace std {
 609
 610 template <typename char_type, typename size_type, size_type max_size>
 611 struct hash<basic_sstring<char_type, size_type, max_size>> {
 612     size_t operator()(const basic_sstring<char_type, size_type, max_size>& s) const {
 613                 using traits_type = std::char_traits<char_type>;
 614                 return std::hash<boost::basic_string_view<char_type,traits_type>>()(s);
 615     }
 616 };
 617
 618 }
 619
 620 static inline
 621 char* copy_str_to(char* dst) {
 622     return dst;
 623 }
 624
 625 template <typename Head, typename... Tail>
 626 static inline
 627 char* copy_str_to(char* dst, const Head& head, const Tail&... tail) {
 628     return copy_str_to(std::copy(str_begin(head), str_end(head), dst), tail...);
 629 }
 630
 631 template <typename String = sstring, typename... Args>
 632 static String make_sstring(Args&&... args)
 633 {
 634     String ret(sstring::initialized_later(), str_len(args...));
 635     copy_str_to(ret.begin(), args...);
 636     return ret;
 637 }
 638
 639 template <typename string_type, typename T>
 640 inline string_type to_sstring(T value) {
 641     return sstring::to_sstring<string_type>(value);
 642 }
 643
 644
 645 // encode/decode
 646 template <typename Char, typename Size, Size Max>
 647 struct denc_traits<basic_sstring<Char, Size, Max>> {
 648 private:
 649   using value_type = basic_sstring<Char, Size, Max>;
 650 public:
 651   static constexpr bool supported = true;
 652   static constexpr bool featured = false;
 653   static constexpr bool bounded = false;
 654
 655   static void bound_encode(const value_type& s, size_t& p, uint64_t f=0) {
 656     p += sizeof(Size) + s.size();
 657   }
 658
 659   static void encode_nohead(const value_type& s,
 660                             buffer::list::contiguous_appender& p)
 661   {
 662     auto len = s.size();
 663     if (len) {
 664       p.append(reinterpret_cast<const char*>(s.c_str()), len);
 665     }
 666   }
 667
 668   static void decode_nohead(size_t len, value_type& s,
 669                             buffer::ptr::iterator& p)
 670   {
 671     s.reset();
 672     if (len) {
 673       s.append(reinterpret_cast<const Char*>(p.get_pos_add(len)), len);
 674     }
 675   }
 676
 677   static void encode(const value_type& s,
 678                      buffer::list::contiguous_appender& p,
 679                      uint64_t f=0)
 680   {
 681     Size len = (Size)(s.size());
 682     ::denc(len, p);
 683     if (len) {
 684       p.append(reinterpret_cast<const char*>(s.c_str()), len);
 685     }
 686   }
 687
 688   static void decode(value_type& s,
 689                      buffer::ptr::iterator& p,
 690                      uint64_t f=0)
 691   {
 692     Size len;
 693     ::denc(len, p);
 694     decode_nohead(len, s, p);
 695   }
 696 };
 697
 698 #if 0 /* XXX conflicts w/Ceph types.h */
 699 template <typename T>
 700 inline
 701 std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
 702     bool first = true;
 703     os << "{";
 704     for (auto&& elem : v) {
 705         if (!first) {
 706             os << ", ";
 707         } else {
 708             first = false;
 709         }
 710         os << elem;
 711     }
 712     os << "}";
 713     return os;
 714 }
 715 #endif
 716
 717 #endif /* SSTRING_HH_ */