smallstringopt.h 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447
  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. #ifndef DAHUA_SMALL_STRING_OPT_INC_
  13. #define DAHUA_SMALL_STRING_OPT_INC_
  14. // revision 1007
  15. ////////////////////////////////////////////////////////////////////////////////
  16. // class template SmallStringOpt
  17. // Builds the small string optimization over any other storage
  18. ////////////////////////////////////////////////////////////////////////////////
  19. /* This is the template for a storage policy
  20. ////////////////////////////////////////////////////////////////////////////////
  21. template <typename E, class A = @>
  22. class StoragePolicy
  23. {
  24. typedef E value_type;
  25. typedef @ iterator;
  26. typedef @ const_iterator;
  27. typedef A allocator_type;
  28. typedef @ size_type;
  29. StoragePolicy(const StoragePolicy& s);
  30. StoragePolicy(const A&);
  31. StoragePolicy(const E* s, size_type len, const A&);
  32. StoragePolicy(size_type len, E c, const A&);
  33. ~StoragePolicy();
  34. iterator begin();
  35. const_iterator begin() const;
  36. iterator end();
  37. const_iterator end() const;
  38. size_type size() const;
  39. size_type max_size() const;
  40. size_type capacity() const;
  41. void reserve(size_type res_arg);
  42. void append(const E* s, size_type sz);
  43. template <class InputIterator>
  44. void append(InputIterator b, InputIterator e);
  45. void resize(size_type newSize, E fill);
  46. void swap(StoragePolicy& rhs);
  47. const E* c_str() const;
  48. const E* data() const;
  49. A get_allocator() const;
  50. };
  51. ////////////////////////////////////////////////////////////////////////////////
  52. */
  53. #include <memory>
  54. #include <algorithm>
  55. #include <functional>
  56. #include <cassert>
  57. #include <limits>
  58. #include <stdexcept>
  59. #include "flex_string_details.h"
  60. namespace Dahua {
  61. namespace Infra {
  62. namespace SmallStringOptImpl
  63. {
  64. // The threshold for SmallStringOpt cannot be greater than 126. See Loki bug #2666059 for more details:
  65. // https://sourceforge.net/tracker2/?func=detail&aid=2666059&group_id=29557&atid=396644
  66. template<int Expression> struct BufferSizeCannotBeGreaterThan126;
  67. template<> struct BufferSizeCannotBeGreaterThan126<true> { };
  68. #define LOKI_FLEX_STRING_BUFFERSIZECANNOTBEGREATERTHAN126(expression) \
  69. { SmallStringOptImpl::BufferSizeCannotBeGreaterThan126<((expression) != 0)> \
  70. bufferSizeCannotBeGreaterThan126; (void)bufferSizeCannotBeGreaterThan126; }
  71. }
  72. ////////////////////////////////////////////////////////////////////////////////
  73. // class template SmallStringOpt
  74. // Builds the small string optimization over any other storage
  75. ////////////////////////////////////////////////////////////////////////////////
  76. template <class Storage, unsigned int threshold,
  77. typename Align = DAHUA_DEDUCED_TYPENAME Storage::value_type*>
  78. class SmallStringOpt
  79. {
  80. public:
  81. typedef typename Storage::value_type value_type;
  82. typedef value_type* iterator;
  83. typedef const value_type* const_iterator;
  84. typedef typename Storage::allocator_type allocator_type;
  85. typedef typename allocator_type::size_type size_type;
  86. typedef typename Storage::reference reference;
  87. private:
  88. enum { temp1 = threshold * sizeof(value_type) > sizeof(Storage)
  89. ? threshold * sizeof(value_type)
  90. : sizeof(Storage) };
  91. enum { temp2 = temp1 > sizeof(Align) ? temp1 : sizeof(Align) };
  92. public:
  93. enum { maxSmallString =
  94. (temp2 + sizeof(value_type) - 1) / sizeof(value_type) };
  95. private:
  96. enum { magic = maxSmallString + 1 };
  97. union
  98. {
  99. mutable value_type buf_[maxSmallString + 1];
  100. Align align_;
  101. };
  102. Storage& GetStorage()
  103. {
  104. assert(buf_[maxSmallString] == magic);
  105. Storage* p = reinterpret_cast<Storage*>(&buf_[0]);
  106. return *p;
  107. }
  108. const Storage& GetStorage() const
  109. {
  110. assert(buf_[maxSmallString] == magic);
  111. const Storage *p = reinterpret_cast<const Storage*>(&buf_[0]);
  112. return *p;
  113. }
  114. bool Small() const
  115. {
  116. return buf_[maxSmallString] != magic;
  117. }
  118. public:
  119. SmallStringOpt(const SmallStringOpt& s)
  120. {
  121. LOKI_FLEX_STRING_BUFFERSIZECANNOTBEGREATERTHAN126(maxSmallString <= 126)
  122. if (s.Small())
  123. {
  124. flex_string_details::pod_copy(
  125. s.buf_,
  126. s.buf_ + s.size(),
  127. buf_);
  128. }
  129. else
  130. {
  131. new(buf_) Storage(s.GetStorage());
  132. }
  133. buf_[maxSmallString] = s.buf_[maxSmallString];
  134. }
  135. SmallStringOpt(const allocator_type&)
  136. {
  137. buf_[maxSmallString] = maxSmallString;
  138. }
  139. SmallStringOpt(const value_type* s, size_type len, const allocator_type& a)
  140. {
  141. if (len <= maxSmallString)
  142. {
  143. flex_string_details::pod_copy(s, s + len, buf_);
  144. buf_[maxSmallString] = value_type(maxSmallString - len);
  145. }
  146. else
  147. {
  148. new(buf_) Storage(s, len, a);
  149. buf_[maxSmallString] = magic;
  150. }
  151. }
  152. SmallStringOpt(size_type len, value_type c, const allocator_type& a)
  153. {
  154. if (len <= maxSmallString)
  155. {
  156. flex_string_details::pod_fill(buf_, buf_ + len, c);
  157. buf_[maxSmallString] = value_type(maxSmallString - len);
  158. }
  159. else
  160. {
  161. new(buf_) Storage(len, c, a);
  162. buf_[maxSmallString] = magic;
  163. }
  164. }
  165. // Fix suggested by Andrew Barnert on 07/03/2007
  166. SmallStringOpt& operator=(const SmallStringOpt& rhs)
  167. {
  168. if (&rhs == this) return *this;
  169. const size_t rhss = rhs.size();
  170. // Will we use this' allocated buffer?
  171. if (rhss > maxSmallString && capacity() > rhss) {
  172. const size_t s = size();
  173. if (s >= rhss) {
  174. // shrink
  175. resize(rhss, 0);
  176. std::copy(rhs.begin(), rhs.end(), begin());
  177. } else {
  178. // grow
  179. std::copy(rhs.begin(), rhs.begin() + s, begin());
  180. append(rhs.begin() + s, rhs.end());
  181. }
  182. } else {
  183. // this' buffer is useless
  184. if (rhs.Small()) {
  185. // Just destroy and copy over (ugly but efficient)
  186. // Works because construction of a small string can't fail
  187. if (!Small()) this->~SmallStringOpt();
  188. new(this) SmallStringOpt(rhs);
  189. } else {
  190. SmallStringOpt copy(rhs);
  191. copy.swap(*this);
  192. }
  193. }
  194. return *this;
  195. }
  196. ~SmallStringOpt()
  197. {
  198. if (!Small()) GetStorage().~Storage();
  199. }
  200. iterator begin()
  201. {
  202. if (Small()) return buf_;
  203. return &*GetStorage().begin();
  204. }
  205. const_iterator begin() const
  206. {
  207. if (Small()) return buf_;
  208. return &*GetStorage().begin();
  209. }
  210. iterator end()
  211. {
  212. if (Small()) return buf_ + maxSmallString - buf_[maxSmallString];
  213. return &*GetStorage().end();
  214. }
  215. const_iterator end() const
  216. {
  217. if (Small()) return buf_ + maxSmallString - buf_[maxSmallString];
  218. return &*GetStorage().end();
  219. }
  220. size_type size() const
  221. {
  222. assert(!Small() || maxSmallString >= buf_[maxSmallString]);
  223. return Small()
  224. ? maxSmallString - buf_[maxSmallString]
  225. : GetStorage().size();
  226. }
  227. size_type max_size() const
  228. { return get_allocator().max_size(); }
  229. size_type capacity() const
  230. { return Small() ? maxSmallString : GetStorage().capacity(); }
  231. void reserve(size_type res_arg)
  232. {
  233. if (Small())
  234. {
  235. if (res_arg <= maxSmallString) return;
  236. SmallStringOpt temp(*this);
  237. this->~SmallStringOpt();
  238. new(buf_) Storage(temp.data(), temp.size(),
  239. temp.get_allocator());
  240. buf_[maxSmallString] = magic;
  241. GetStorage().reserve(res_arg);
  242. }
  243. else
  244. {
  245. GetStorage().reserve(res_arg);
  246. }
  247. assert(capacity() >= res_arg);
  248. }
  249. template <class FwdIterator>
  250. void append(FwdIterator b, FwdIterator e)
  251. {
  252. if (!Small())
  253. {
  254. GetStorage().append(b, e);
  255. }
  256. else
  257. {
  258. // append to a small string
  259. const size_type
  260. sz = std::distance(b, e),
  261. neededCapacity = maxSmallString - buf_[maxSmallString] + sz;
  262. if (maxSmallString < neededCapacity)
  263. {
  264. // need to change storage strategy
  265. allocator_type alloc;
  266. Storage temp(alloc);
  267. temp.reserve(neededCapacity);
  268. temp.append(buf_, buf_ + maxSmallString - buf_[maxSmallString]);
  269. temp.append(b, e);
  270. buf_[maxSmallString] = magic;
  271. new(buf_) Storage(temp.get_allocator());
  272. GetStorage().swap(temp);
  273. }
  274. else
  275. {
  276. std::copy(b, e, buf_ + maxSmallString - buf_[maxSmallString]);
  277. buf_[maxSmallString] -= value_type(sz);
  278. }
  279. }
  280. }
  281. void resize(size_type n, value_type c)
  282. {
  283. if (Small())
  284. {
  285. if (n > maxSmallString)
  286. {
  287. // Small string resized to big string
  288. SmallStringOpt temp(*this); // can't throw
  289. // 11-17-2001: correct exception safety bug
  290. Storage newString(temp.data(), temp.size(),
  291. temp.get_allocator());
  292. newString.resize(n, c);
  293. // We make the reasonable assumption that an empty Storage
  294. // constructor won't throw
  295. this->~SmallStringOpt();
  296. new(&buf_[0]) Storage(temp.get_allocator());
  297. buf_[maxSmallString] = value_type(magic);
  298. GetStorage().swap(newString);
  299. }
  300. else
  301. {
  302. // Small string resized to small string
  303. // 11-17-2001: bug fix: terminating zero not copied
  304. size_type toFill = n > size() ? n - size() : 0;
  305. flex_string_details::pod_fill(end(), end() + toFill, c);
  306. buf_[maxSmallString] = value_type(maxSmallString - n);
  307. }
  308. }
  309. else
  310. {
  311. if (n > maxSmallString)
  312. {
  313. // Big string resized to big string
  314. GetStorage().resize(n, c);
  315. }
  316. else
  317. {
  318. // Big string resized to small string
  319. // 11-17=2001: bug fix in the assertion below
  320. assert(capacity() > n);
  321. // The following two commented-out lines were fixed by
  322. // Jean-Francois Bastien, 07/26/2007
  323. //SmallStringOpt newObj(data(), n, get_allocator());
  324. // newObj.swap(*this);
  325. if (n <= size()) {
  326. SmallStringOpt newObj(data(), n, get_allocator());
  327. newObj.swap(*this);
  328. } else {
  329. SmallStringOpt newObj(data(), size(), get_allocator());
  330. newObj.resize(n, c); // invoke this function recursively
  331. newObj.swap(*this);
  332. }
  333. }
  334. }
  335. }
  336. void swap(SmallStringOpt& rhs)
  337. {
  338. if (Small())
  339. {
  340. if (rhs.Small())
  341. {
  342. // Small swapped with small
  343. std::swap_ranges(buf_, buf_ + maxSmallString + 1,
  344. rhs.buf_);
  345. }
  346. else
  347. {
  348. // Small swapped with big
  349. // Make a copy of myself - can't throw
  350. SmallStringOpt temp(*this);
  351. // Nuke myself
  352. this->~SmallStringOpt();
  353. // Make an empty storage for myself (likely won't throw)
  354. new(buf_) Storage(0, value_type(), rhs.get_allocator());
  355. buf_[maxSmallString] = magic;
  356. // Recurse to this same function
  357. swap(rhs);
  358. // Nuke rhs
  359. rhs.~SmallStringOpt();
  360. // Build the new small string into rhs
  361. new(&rhs) SmallStringOpt(temp);
  362. }
  363. }
  364. else
  365. {
  366. if (rhs.Small())
  367. {
  368. // Big swapped with small
  369. // Already implemented, recurse with reversed args
  370. rhs.swap(*this);
  371. }
  372. else
  373. {
  374. // Big swapped with big
  375. GetStorage().swap(rhs.GetStorage());
  376. }
  377. }
  378. }
  379. const value_type* c_str() const
  380. {
  381. if (!Small()) return GetStorage().c_str();
  382. buf_[maxSmallString - buf_[maxSmallString]] = value_type();
  383. return buf_;
  384. }
  385. const value_type* data() const
  386. { return Small() ? buf_ : GetStorage().data(); }
  387. allocator_type get_allocator() const
  388. { return allocator_type(); }
  389. };
  390. } // namespace Infra
  391. } // namespace Dahua
  392. #endif // DAHUA_SMALL_STRING_OPT_INC_