1 ////////////////////////////////////////////////////////////////////////////////
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 ////////////////////////////////////////////////////////////////////////////////
13 #ifndef SMALL_STRING_OPT_INC_
14 #define SMALL_STRING_OPT_INC_
16 // $Id: smallstringopt.h 836 2007-09-20 15:51:37Z aandrei $
19 ////////////////////////////////////////////////////////////////////////////////
20 // class template SmallStringOpt
21 // Builds the small string optimization over any other storage
22 ////////////////////////////////////////////////////////////////////////////////
24 /* This is the template for a storage policy
25 ////////////////////////////////////////////////////////////////////////////////
26 template <typename E, class A = @>
31 typedef @ const_iterator;
32 typedef A allocator_type;
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&);
42 const_iterator begin() const;
44 const_iterator end() const;
46 size_type size() const;
47 size_type max_size() const;
48 size_type capacity() const;
50 void reserve(size_type res_arg);
52 void append(const E* s, size_type sz);
54 template <class InputIterator>
55 void append(InputIterator b, InputIterator e);
57 void resize(size_type newSize, E fill);
59 void swap(StoragePolicy& rhs);
61 const E* c_str() const;
62 const E* data() const;
64 A get_allocator() const;
66 ////////////////////////////////////////////////////////////////////////////////
75 #include "flex_string_details.h"
77 ////////////////////////////////////////////////////////////////////////////////
78 // class template SmallStringOpt
79 // Builds the small string optimization over any other storage
80 ////////////////////////////////////////////////////////////////////////////////
82 template <class Storage, unsigned int threshold,
83 typename Align = typename Storage::value_type *>
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;
95 enum { temp1 = threshold * sizeof(value_type) > sizeof(Storage)
96 ? threshold * sizeof(value_type)
100 enum { temp2 = temp1 > sizeof(Align) ? temp1 : sizeof(Align) };
103 enum { maxSmallString =
104 (temp2 + sizeof(value_type) - 1) / sizeof(value_type)
108 enum { magic = maxSmallString + 1 };
112 mutable value_type buf_[maxSmallString + 1];
116 Storage &GetStorage()
118 assert(buf_[maxSmallString] == magic);
119 Storage *p = reinterpret_cast<Storage *>(&buf_[0]);
123 const Storage &GetStorage() const
125 assert(buf_[maxSmallString] == magic);
126 const Storage *p = reinterpret_cast<const Storage *>(&buf_[0]);
132 return buf_[maxSmallString] != magic;
136 SmallStringOpt(const SmallStringOpt &s)
140 flex_string_details::pod_copy(
147 new(buf_) Storage(s.GetStorage());
149 buf_[maxSmallString] = s.buf_[maxSmallString];
152 SmallStringOpt(const allocator_type &)
154 buf_[maxSmallString] = maxSmallString;
157 SmallStringOpt(const value_type *s, size_type len, const allocator_type &a)
159 if (len <= maxSmallString)
161 flex_string_details::pod_copy(s, s + len, buf_);
162 buf_[maxSmallString] = value_type(maxSmallString - len);
166 new(buf_) Storage(s, len, a);
167 buf_[maxSmallString] = magic;
171 SmallStringOpt(size_type len, value_type c, const allocator_type &a)
173 if (len <= maxSmallString)
175 flex_string_details::pod_fill(buf_, buf_ + len, c);
176 buf_[maxSmallString] = value_type(maxSmallString - len);
180 new(buf_) Storage(len, c, a);
181 buf_[maxSmallString] = magic;
185 // Fix suggested by Andrew Barnert on 07/03/2007
186 SmallStringOpt &operator=(const SmallStringOpt &rhs)
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)
193 const size_t s = size();
198 std::copy(rhs.begin(), rhs.end(), begin());
203 std::copy(rhs.begin(), rhs.begin() + s, begin());
204 append(rhs.begin() + s, rhs.end());
209 // this' buffer is useless
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);
219 SmallStringOpt copy(rhs);
222 // no need to swap, just destructively read copy into this
223 // ugly but efficient again
224 memcpy(this, ©, sizeof(*this));
225 copy.buf_[maxSmallString] = maxSmallString; // clear the copy
229 // Use the swap trick
239 if (!Small()) GetStorage().~Storage();
244 if (Small()) return buf_;
245 return &*GetStorage().begin();
248 const_iterator begin() const
250 if (Small()) return buf_;
251 return &*GetStorage().begin();
256 if (Small()) return buf_ + maxSmallString - buf_[maxSmallString];
257 return &*GetStorage().end();
260 const_iterator end() const
262 if (Small()) return buf_ + maxSmallString - buf_[maxSmallString];
263 return &*GetStorage().end();
266 size_type size() const
268 assert(!Small() || maxSmallString >= buf_[maxSmallString]);
270 ? maxSmallString - buf_[maxSmallString]
271 : GetStorage().size();
274 size_type max_size() const
276 return get_allocator().max_size();
279 size_type capacity() const
281 return Small() ? maxSmallString : GetStorage().capacity();
284 void reserve(size_type res_arg)
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);
298 GetStorage().reserve(res_arg);
300 assert(capacity() >= res_arg);
303 template <class FwdIterator>
304 void append(FwdIterator b, FwdIterator e)
308 GetStorage().append(b, e);
312 // append to a small string
314 sz = std::distance(b, e),
315 neededCapacity = maxSmallString - buf_[maxSmallString] + sz;
317 if (maxSmallString < neededCapacity)
319 // need to change storage strategy
320 allocator_type alloc;
322 temp.reserve(neededCapacity);
323 temp.append(buf_, buf_ + maxSmallString - buf_[maxSmallString]);
325 buf_[maxSmallString] = magic;
326 new(buf_) Storage(temp.get_allocator());
327 GetStorage().swap(temp);
331 std::copy(b, e, buf_ + maxSmallString - buf_[maxSmallString]);
332 buf_[maxSmallString] -= value_type(sz);
337 void resize(size_type n, value_type c)
341 if (n > maxSmallString)
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);
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);
367 if (n > maxSmallString)
369 // Big string resized to big string
370 GetStorage().resize(n, c);
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);
383 SmallStringOpt newObj(data(), n, get_allocator());
388 SmallStringOpt newObj(data(), size(), get_allocator());
389 newObj.resize(n, c); // invoke this function recursively
396 void swap(SmallStringOpt &rhs)
402 // Small swapped with small
403 std::swap_ranges(buf_, buf_ + maxSmallString + 1,
408 // Small swapped with big
409 // Make a copy of myself - can't throw
410 SmallStringOpt temp(*this);
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
419 rhs.~SmallStringOpt();
420 // Build the new small string into rhs
421 new(&rhs) SmallStringOpt(temp);
428 // Big swapped with small
429 // Already implemented, recurse with reversed args
434 // Big swapped with big
435 GetStorage().swap(rhs.GetStorage());
440 const value_type *c_str() const
442 if (!Small()) return GetStorage().c_str();
443 buf_[maxSmallString - buf_[maxSmallString]] = value_type();
447 const value_type *data() const
449 return Small() ? buf_ : GetStorage().data();
452 allocator_type get_allocator() const
454 return allocator_type();
459 #endif // SMALL_STRING_OPT_INC_