git.cworth.org Git - vogl/blob - src/extlib/loki/include/loki/flex/smallstringopt.h

   1 ////////////////////////////////////////////////////////////////////////////////
   2 // flex_string
   3 // Copyright (c) 2001 by Andrei Alexandrescu
   4 // Permission to use, copy, modify, distribute and sell this software for any
   5 //     purpose is hereby granted without fee, provided that the above copyright
   6 //     notice appear in all copies and that both that copyright notice and this
   7 //     permission notice appear in supporting documentation.
   8 // The author makes no representations about the
   9 //     suitability of this software for any purpose. It is provided "as is"
  10 //     without express or implied warranty.
  11 ////////////////////////////////////////////////////////////////////////////////
  12
  13 #ifndef SMALL_STRING_OPT_INC_
  14 #define SMALL_STRING_OPT_INC_
  15
  16 // $Id: smallstringopt.h 836 2007-09-20 15:51:37Z aandrei $
  17
  18
  19 ////////////////////////////////////////////////////////////////////////////////
  20 // class template SmallStringOpt
  21 // Builds the small string optimization over any other storage
  22 ////////////////////////////////////////////////////////////////////////////////
  23
  24 /* This is the template for a storage policy
  25 ////////////////////////////////////////////////////////////////////////////////
  26 template <typename E, class A = @>
  27 class StoragePolicy
  28 {
  29     typedef E value_type;
  30     typedef @ iterator;
  31     typedef @ const_iterator;
  32     typedef A allocator_type;
  33     typedef @ size_type;
  34
  35     StoragePolicy(const StoragePolicy& s);
  36     StoragePolicy(const A&);
  37     StoragePolicy(const E* s, size_type len, const A&);
  38     StoragePolicy(size_type len, E c, const A&);
  39     ~StoragePolicy();
  40
  41     iterator begin();
  42     const_iterator begin() const;
  43     iterator end();
  44     const_iterator end() const;
  45
  46     size_type size() const;
  47     size_type max_size() const;
  48     size_type capacity() const;
  49
  50     void reserve(size_type res_arg);
  51
  52     void append(const E* s, size_type sz);
  53
  54     template <class InputIterator>
  55     void append(InputIterator b, InputIterator e);
  56
  57     void resize(size_type newSize, E fill);
  58
  59     void swap(StoragePolicy& rhs);
  60
  61     const E* c_str() const;
  62     const E* data() const;
  63
  64     A get_allocator() const;
  65 };
  66 ////////////////////////////////////////////////////////////////////////////////
  67 */
  68
  69 #include <memory>
  70 #include <algorithm>
  71 #include <functional>
  72 #include <cassert>
  73 #include <limits>
  74 #include <stdexcept>
  75 #include "flex_string_details.h"
  76
  77 ////////////////////////////////////////////////////////////////////////////////
  78 // class template SmallStringOpt
  79 // Builds the small string optimization over any other storage
  80 ////////////////////////////////////////////////////////////////////////////////
  81
  82 template <class Storage, unsigned int threshold,
  83          typename Align = typename Storage::value_type *>
  84 class SmallStringOpt
  85 {
  86 public:
  87         typedef typename Storage::value_type value_type;
  88         typedef value_type *iterator;
  89         typedef const value_type *const_iterator;
  90         typedef typename Storage::allocator_type allocator_type;
  91         typedef typename allocator_type::size_type size_type;
  92         typedef typename Storage::reference reference;
  93
  94 private:
  95         enum { temp1 = threshold * sizeof(value_type) > sizeof(Storage)
  96                        ? threshold  * sizeof(value_type)
  97                        : sizeof(Storage)
  98              };
  99
 100         enum { temp2 = temp1 > sizeof(Align) ? temp1 : sizeof(Align) };
 101
 102 public:
 103         enum { maxSmallString =
 104                    (temp2 + sizeof(value_type) - 1) / sizeof(value_type)
 105              };
 106
 107 private:
 108         enum { magic = maxSmallString + 1 };
 109
 110         union
 111         {
 112                 mutable value_type buf_[maxSmallString + 1];
 113                 Align align_;
 114         };
 115
 116         Storage &GetStorage()
 117         {
 118                 assert(buf_[maxSmallString] == magic);
 119                 Storage *p = reinterpret_cast<Storage *>(&buf_[0]);
 120                 return *p;
 121         }
 122
 123         const Storage &GetStorage() const
 124         {
 125                 assert(buf_[maxSmallString] == magic);
 126                 const Storage *p = reinterpret_cast<const Storage *>(&buf_[0]);
 127                 return *p;
 128         }
 129
 130         bool Small() const
 131         {
 132                 return buf_[maxSmallString] != magic;
 133         }
 134
 135 public:
 136         SmallStringOpt(const SmallStringOpt &s)
 137         {
 138                 if (s.Small())
 139                 {
 140                         flex_string_details::pod_copy(
 141                             s.buf_,
 142                             s.buf_ + s.size(),
 143                             buf_);
 144                 }
 145                 else
 146                 {
 147                         new(buf_) Storage(s.GetStorage());
 148                 }
 149                 buf_[maxSmallString] = s.buf_[maxSmallString];
 150         }
 151
 152         SmallStringOpt(const allocator_type &)
 153         {
 154                 buf_[maxSmallString] = maxSmallString;
 155         }
 156
 157         SmallStringOpt(const value_type *s, size_type len, const allocator_type &a)
 158         {
 159                 if (len <= maxSmallString)
 160                 {
 161                         flex_string_details::pod_copy(s, s + len, buf_);
 162                         buf_[maxSmallString] = value_type(maxSmallString - len);
 163                 }
 164                 else
 165                 {
 166                         new(buf_) Storage(s, len, a);
 167                         buf_[maxSmallString] = magic;
 168                 }
 169         }
 170
 171         SmallStringOpt(size_type len, value_type c, const allocator_type &a)
 172         {
 173                 if (len <= maxSmallString)
 174                 {
 175                         flex_string_details::pod_fill(buf_, buf_ + len, c);
 176                         buf_[maxSmallString] = value_type(maxSmallString - len);
 177                 }
 178                 else
 179                 {
 180                         new(buf_) Storage(len, c, a);
 181                         buf_[maxSmallString] = magic;
 182                 }
 183         }
 184
 185         // Fix suggested by Andrew Barnert on 07/03/2007
 186         SmallStringOpt &operator=(const SmallStringOpt &rhs)
 187         {
 188                 if (&rhs == this) return *this;
 189                 const size_t rhss = rhs.size();
 190                 // Will we use this' allocated buffer?
 191                 if (rhss > maxSmallString && capacity() > rhss)
 192                 {
 193                         const size_t s = size();
 194                         if (s >= rhss)
 195                         {
 196                                 // shrink
 197                                 resize(rhss, 0);
 198                                 std::copy(rhs.begin(), rhs.end(), begin());
 199                         }
 200                         else
 201                         {
 202                                 // grow
 203                                 std::copy(rhs.begin(), rhs.begin() + s, begin());
 204                                 append(rhs.begin() + s, rhs.end());
 205                         }
 206                 }
 207                 else
 208                 {
 209                         // this' buffer is useless
 210                         if (rhs.Small())
 211                         {
 212                                 // Just destroy and copy over (ugly but efficient)
 213                                 // Works because construction of a small string can't fail
 214                                 if (!Small()) this->~SmallStringOpt();
 215                                 new(this) SmallStringOpt(rhs);
 216                         }
 217                         else
 218                         {
 219                                 SmallStringOpt copy(rhs);
 220                                 if (Small())
 221                                 {
 222                                         // no need to swap, just destructively read copy into this
 223                                         // ugly but efficient again
 224                                         memcpy(this, &copy, sizeof(*this));
 225                                         copy.buf_[maxSmallString] = maxSmallString; // clear the copy
 226                                 }
 227                                 else
 228                                 {
 229                                         // Use the swap trick
 230                                         copy.swap(*this);
 231                                 }
 232                         }
 233                 }
 234                 return *this;
 235         }
 236
 237         ~SmallStringOpt()
 238         {
 239                 if (!Small()) GetStorage().~Storage();
 240         }
 241
 242         iterator begin()
 243         {
 244                 if (Small()) return buf_;
 245                 return &*GetStorage().begin();
 246         }
 247
 248         const_iterator begin() const
 249         {
 250                 if (Small()) return buf_;
 251                 return &*GetStorage().begin();
 252         }
 253
 254         iterator end()
 255         {
 256                 if (Small()) return buf_ + maxSmallString - buf_[maxSmallString];
 257                 return &*GetStorage().end();
 258         }
 259
 260         const_iterator end() const
 261         {
 262                 if (Small()) return buf_ + maxSmallString - buf_[maxSmallString];
 263                 return &*GetStorage().end();
 264         }
 265
 266         size_type size() const
 267         {
 268                 assert(!Small() || maxSmallString >= buf_[maxSmallString]);
 269                 return Small()
 270                        ? maxSmallString - buf_[maxSmallString]
 271                        : GetStorage().size();
 272         }
 273
 274         size_type max_size() const
 275         {
 276                 return get_allocator().max_size();
 277         }
 278
 279         size_type capacity() const
 280         {
 281                 return Small() ? maxSmallString : GetStorage().capacity();
 282         }
 283
 284         void reserve(size_type res_arg)
 285         {
 286                 if (Small())
 287                 {
 288                         if (res_arg <= maxSmallString) return;
 289                         SmallStringOpt temp(*this);
 290                         this->~SmallStringOpt();
 291                         new(buf_) Storage(temp.data(), temp.size(),
 292                                           temp.get_allocator());
 293                         buf_[maxSmallString] = magic;
 294                         GetStorage().reserve(res_arg);
 295                 }
 296                 else
 297                 {
 298                         GetStorage().reserve(res_arg);
 299                 }
 300                 assert(capacity() >= res_arg);
 301         }
 302
 303         template <class FwdIterator>
 304         void append(FwdIterator b, FwdIterator e)
 305         {
 306                 if (!Small())
 307                 {
 308                         GetStorage().append(b, e);
 309                 }
 310                 else
 311                 {
 312                         // append to a small string
 313                         const size_type
 314                         sz = std::distance(b, e),
 315                         neededCapacity = maxSmallString - buf_[maxSmallString] + sz;
 316
 317                         if (maxSmallString < neededCapacity)
 318                         {
 319                                 // need to change storage strategy
 320                                 allocator_type alloc;
 321                                 Storage temp(alloc);
 322                                 temp.reserve(neededCapacity);
 323                                 temp.append(buf_, buf_ + maxSmallString - buf_[maxSmallString]);
 324                                 temp.append(b, e);
 325                                 buf_[maxSmallString] = magic;
 326                                 new(buf_) Storage(temp.get_allocator());
 327                                 GetStorage().swap(temp);
 328                         }
 329                         else
 330                         {
 331                                 std::copy(b, e, buf_ + maxSmallString - buf_[maxSmallString]);
 332                                 buf_[maxSmallString] -= value_type(sz);
 333                         }
 334                 }
 335         }
 336
 337         void resize(size_type n, value_type c)
 338         {
 339                 if (Small())
 340                 {
 341                         if (n > maxSmallString)
 342                         {
 343                                 // Small string resized to big string
 344                                 SmallStringOpt temp(*this); // can't throw
 345                                 // 11-17-2001: correct exception safety bug
 346                                 Storage newString(temp.data(), temp.size(),
 347                                                   temp.get_allocator());
 348                                 newString.resize(n, c);
 349                                 // We make the reasonable assumption that an empty Storage
 350                                 //     constructor won't throw
 351                                 this->~SmallStringOpt();
 352                                 new(&buf_[0]) Storage(temp.get_allocator());
 353                                 buf_[maxSmallString] = value_type(magic);
 354                                 GetStorage().swap(newString);
 355                         }
 356                         else
 357                         {
 358                                 // Small string resized to small string
 359                                 // 11-17-2001: bug fix: terminating zero not copied
 360                                 size_type toFill = n > size() ? n - size() : 0;
 361                                 flex_string_details::pod_fill(end(), end() + toFill, c);
 362                                 buf_[maxSmallString] = value_type(maxSmallString - n);
 363                         }
 364                 }
 365                 else
 366                 {
 367                         if (n > maxSmallString)
 368                         {
 369                                 // Big string resized to big string
 370                                 GetStorage().resize(n, c);
 371                         }
 372                         else
 373                         {
 374                                 // Big string resized to small string
 375                                 // 11-17=2001: bug fix in the assertion below
 376                                 assert(capacity() > n);
 377                                 // The following two commented-out lines were fixed by
 378                                 // Jean-Francois Bastien, 07/26/2007
 379                                 //SmallStringOpt newObj(data(), n, get_allocator());
 380                                 // newObj.swap(*this);
 381                                 if (n <= size())
 382                                 {
 383                                         SmallStringOpt newObj(data(), n, get_allocator());
 384                                         newObj.swap(*this);
 385                                 }
 386                                 else
 387                                 {
 388                                         SmallStringOpt newObj(data(), size(), get_allocator());
 389                                         newObj.resize(n, c); // invoke this function recursively
 390                                         newObj.swap(*this);
 391                                 }
 392                         }
 393                 }
 394         }
 395
 396         void swap(SmallStringOpt &rhs)
 397         {
 398                 if (Small())
 399                 {
 400                         if (rhs.Small())
 401                         {
 402                                 // Small swapped with small
 403                                 std::swap_ranges(buf_, buf_ + maxSmallString + 1,
 404                                                  rhs.buf_);
 405                         }
 406                         else
 407                         {
 408                                 // Small swapped with big
 409                                 // Make a copy of myself - can't throw
 410                                 SmallStringOpt temp(*this);
 411                                 // Nuke myself
 412                                 this->~SmallStringOpt();
 413                                 // Make an empty storage for myself (likely won't throw)
 414                                 new(buf_) Storage(0, value_type(), rhs.get_allocator());
 415                                 buf_[maxSmallString] = magic;
 416                                 // Recurse to this same function
 417                                 swap(rhs);
 418                                 // Nuke rhs
 419                                 rhs.~SmallStringOpt();
 420                                 // Build the new small string into rhs
 421                                 new(&rhs) SmallStringOpt(temp);
 422                         }
 423                 }
 424                 else
 425                 {
 426                         if (rhs.Small())
 427                         {
 428                                 // Big swapped with small
 429                                 // Already implemented, recurse with reversed args
 430                                 rhs.swap(*this);
 431                         }
 432                         else
 433                         {
 434                                 // Big swapped with big
 435                                 GetStorage().swap(rhs.GetStorage());
 436                         }
 437                 }
 438         }
 439
 440         const value_type *c_str() const
 441         {
 442                 if (!Small()) return GetStorage().c_str();
 443                 buf_[maxSmallString - buf_[maxSmallString]] = value_type();
 444                 return buf_;
 445         }
 446
 447         const value_type *data() const
 448         {
 449                 return Small() ? buf_ : GetStorage().data();
 450         }
 451
 452         allocator_type get_allocator() const
 453         {
 454                 return allocator_type();
 455         }
 456 };
 457
 458
 459 #endif // SMALL_STRING_OPT_INC_