You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

prevector.h 18KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517
  1. // Copyright (c) 2015-2016 The Starwels developers
  2. // Distributed under the MIT software license, see the accompanying
  3. // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  4. #ifndef _STARWELS_PREVECTOR_H_
  5. #define _STARWELS_PREVECTOR_H_
  6. #include <assert.h>
  7. #include <stdlib.h>
  8. #include <stdint.h>
  9. #include <string.h>
  10. #include <iterator>
  11. #include <type_traits>
  12. #pragma pack(push, 1)
  13. /** Implements a drop-in replacement for std::vector<T> which stores up to N
  14. * elements directly (without heap allocation). The types Size and Diff are
  15. * used to store element counts, and can be any unsigned + signed type.
  16. *
  17. * Storage layout is either:
  18. * - Direct allocation:
  19. * - Size _size: the number of used elements (between 0 and N)
  20. * - T direct[N]: an array of N elements of type T
  21. * (only the first _size are initialized).
  22. * - Indirect allocation:
  23. * - Size _size: the number of used elements plus N + 1
  24. * - Size capacity: the number of allocated elements
  25. * - T* indirect: a pointer to an array of capacity elements of type T
  26. * (only the first _size are initialized).
  27. *
  28. * The data type T must be movable by memmove/realloc(). Once we switch to C++,
  29. * move constructors can be used instead.
  30. */
  31. template<unsigned int N, typename T, typename Size = uint32_t, typename Diff = int32_t>
  32. class prevector {
  33. public:
  34. typedef Size size_type;
  35. typedef Diff difference_type;
  36. typedef T value_type;
  37. typedef value_type& reference;
  38. typedef const value_type& const_reference;
  39. typedef value_type* pointer;
  40. typedef const value_type* const_pointer;
  41. class iterator {
  42. T* ptr;
  43. public:
  44. typedef Diff difference_type;
  45. typedef T value_type;
  46. typedef T* pointer;
  47. typedef T& reference;
  48. typedef std::random_access_iterator_tag iterator_category;
  49. iterator(T* ptr_) : ptr(ptr_) {}
  50. T& operator*() const { return *ptr; }
  51. T* operator->() const { return ptr; }
  52. T& operator[](size_type pos) { return ptr[pos]; }
  53. const T& operator[](size_type pos) const { return ptr[pos]; }
  54. iterator& operator++() { ptr++; return *this; }
  55. iterator& operator--() { ptr--; return *this; }
  56. iterator operator++(int) { iterator copy(*this); ++(*this); return copy; }
  57. iterator operator--(int) { iterator copy(*this); --(*this); return copy; }
  58. difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
  59. iterator operator+(size_type n) { return iterator(ptr + n); }
  60. iterator& operator+=(size_type n) { ptr += n; return *this; }
  61. iterator operator-(size_type n) { return iterator(ptr - n); }
  62. iterator& operator-=(size_type n) { ptr -= n; return *this; }
  63. bool operator==(iterator x) const { return ptr == x.ptr; }
  64. bool operator!=(iterator x) const { return ptr != x.ptr; }
  65. bool operator>=(iterator x) const { return ptr >= x.ptr; }
  66. bool operator<=(iterator x) const { return ptr <= x.ptr; }
  67. bool operator>(iterator x) const { return ptr > x.ptr; }
  68. bool operator<(iterator x) const { return ptr < x.ptr; }
  69. };
  70. class reverse_iterator {
  71. T* ptr;
  72. public:
  73. typedef Diff difference_type;
  74. typedef T value_type;
  75. typedef T* pointer;
  76. typedef T& reference;
  77. typedef std::bidirectional_iterator_tag iterator_category;
  78. reverse_iterator(T* ptr_) : ptr(ptr_) {}
  79. T& operator*() { return *ptr; }
  80. const T& operator*() const { return *ptr; }
  81. T* operator->() { return ptr; }
  82. const T* operator->() const { return ptr; }
  83. reverse_iterator& operator--() { ptr++; return *this; }
  84. reverse_iterator& operator++() { ptr--; return *this; }
  85. reverse_iterator operator++(int) { reverse_iterator copy(*this); ++(*this); return copy; }
  86. reverse_iterator operator--(int) { reverse_iterator copy(*this); --(*this); return copy; }
  87. bool operator==(reverse_iterator x) const { return ptr == x.ptr; }
  88. bool operator!=(reverse_iterator x) const { return ptr != x.ptr; }
  89. };
  90. class const_iterator {
  91. const T* ptr;
  92. public:
  93. typedef Diff difference_type;
  94. typedef const T value_type;
  95. typedef const T* pointer;
  96. typedef const T& reference;
  97. typedef std::random_access_iterator_tag iterator_category;
  98. const_iterator(const T* ptr_) : ptr(ptr_) {}
  99. const_iterator(iterator x) : ptr(&(*x)) {}
  100. const T& operator*() const { return *ptr; }
  101. const T* operator->() const { return ptr; }
  102. const T& operator[](size_type pos) const { return ptr[pos]; }
  103. const_iterator& operator++() { ptr++; return *this; }
  104. const_iterator& operator--() { ptr--; return *this; }
  105. const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
  106. const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
  107. difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
  108. const_iterator operator+(size_type n) { return const_iterator(ptr + n); }
  109. const_iterator& operator+=(size_type n) { ptr += n; return *this; }
  110. const_iterator operator-(size_type n) { return const_iterator(ptr - n); }
  111. const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
  112. bool operator==(const_iterator x) const { return ptr == x.ptr; }
  113. bool operator!=(const_iterator x) const { return ptr != x.ptr; }
  114. bool operator>=(const_iterator x) const { return ptr >= x.ptr; }
  115. bool operator<=(const_iterator x) const { return ptr <= x.ptr; }
  116. bool operator>(const_iterator x) const { return ptr > x.ptr; }
  117. bool operator<(const_iterator x) const { return ptr < x.ptr; }
  118. };
  119. class const_reverse_iterator {
  120. const T* ptr;
  121. public:
  122. typedef Diff difference_type;
  123. typedef const T value_type;
  124. typedef const T* pointer;
  125. typedef const T& reference;
  126. typedef std::bidirectional_iterator_tag iterator_category;
  127. const_reverse_iterator(const T* ptr_) : ptr(ptr_) {}
  128. const_reverse_iterator(reverse_iterator x) : ptr(&(*x)) {}
  129. const T& operator*() const { return *ptr; }
  130. const T* operator->() const { return ptr; }
  131. const_reverse_iterator& operator--() { ptr++; return *this; }
  132. const_reverse_iterator& operator++() { ptr--; return *this; }
  133. const_reverse_iterator operator++(int) { const_reverse_iterator copy(*this); ++(*this); return copy; }
  134. const_reverse_iterator operator--(int) { const_reverse_iterator copy(*this); --(*this); return copy; }
  135. bool operator==(const_reverse_iterator x) const { return ptr == x.ptr; }
  136. bool operator!=(const_reverse_iterator x) const { return ptr != x.ptr; }
  137. };
  138. private:
  139. size_type _size;
  140. union direct_or_indirect {
  141. char direct[sizeof(T) * N];
  142. struct {
  143. size_type capacity;
  144. char* indirect;
  145. };
  146. } _union;
  147. T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
  148. const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
  149. T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect) + pos; }
  150. const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect) + pos; }
  151. bool is_direct() const { return _size <= N; }
  152. void change_capacity(size_type new_capacity) {
  153. if (new_capacity <= N) {
  154. if (!is_direct()) {
  155. T* indirect = indirect_ptr(0);
  156. T* src = indirect;
  157. T* dst = direct_ptr(0);
  158. memcpy(dst, src, size() * sizeof(T));
  159. free(indirect);
  160. _size -= N + 1;
  161. }
  162. } else {
  163. if (!is_direct()) {
  164. /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert
  165. success. These should instead use an allocator or new/delete so that handlers
  166. are called as necessary, but performance would be slightly degraded by doing so. */
  167. _union.indirect = static_cast<char*>(realloc(_union.indirect, ((size_t)sizeof(T)) * new_capacity));
  168. assert(_union.indirect);
  169. _union.capacity = new_capacity;
  170. } else {
  171. char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
  172. assert(new_indirect);
  173. T* src = direct_ptr(0);
  174. T* dst = reinterpret_cast<T*>(new_indirect);
  175. memcpy(dst, src, size() * sizeof(T));
  176. _union.indirect = new_indirect;
  177. _union.capacity = new_capacity;
  178. _size += N + 1;
  179. }
  180. }
  181. }
  182. T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
  183. const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
  184. public:
  185. void assign(size_type n, const T& val) {
  186. clear();
  187. if (capacity() < n) {
  188. change_capacity(n);
  189. }
  190. while (size() < n) {
  191. _size++;
  192. new(static_cast<void*>(item_ptr(size() - 1))) T(val);
  193. }
  194. }
  195. template<typename InputIterator>
  196. void assign(InputIterator first, InputIterator last) {
  197. size_type n = last - first;
  198. clear();
  199. if (capacity() < n) {
  200. change_capacity(n);
  201. }
  202. while (first != last) {
  203. _size++;
  204. new(static_cast<void*>(item_ptr(size() - 1))) T(*first);
  205. ++first;
  206. }
  207. }
  208. prevector() : _size(0), _union{{}} {}
  209. explicit prevector(size_type n) : _size(0) {
  210. resize(n);
  211. }
  212. explicit prevector(size_type n, const T& val = T()) : _size(0) {
  213. change_capacity(n);
  214. while (size() < n) {
  215. _size++;
  216. new(static_cast<void*>(item_ptr(size() - 1))) T(val);
  217. }
  218. }
  219. template<typename InputIterator>
  220. prevector(InputIterator first, InputIterator last) : _size(0) {
  221. size_type n = last - first;
  222. change_capacity(n);
  223. while (first != last) {
  224. _size++;
  225. new(static_cast<void*>(item_ptr(size() - 1))) T(*first);
  226. ++first;
  227. }
  228. }
  229. prevector(const prevector<N, T, Size, Diff>& other) : _size(0) {
  230. change_capacity(other.size());
  231. const_iterator it = other.begin();
  232. while (it != other.end()) {
  233. _size++;
  234. new(static_cast<void*>(item_ptr(size() - 1))) T(*it);
  235. ++it;
  236. }
  237. }
  238. prevector(prevector<N, T, Size, Diff>&& other) : _size(0) {
  239. swap(other);
  240. }
  241. prevector& operator=(const prevector<N, T, Size, Diff>& other) {
  242. if (&other == this) {
  243. return *this;
  244. }
  245. resize(0);
  246. change_capacity(other.size());
  247. const_iterator it = other.begin();
  248. while (it != other.end()) {
  249. _size++;
  250. new(static_cast<void*>(item_ptr(size() - 1))) T(*it);
  251. ++it;
  252. }
  253. return *this;
  254. }
  255. prevector& operator=(prevector<N, T, Size, Diff>&& other) {
  256. swap(other);
  257. return *this;
  258. }
  259. size_type size() const {
  260. return is_direct() ? _size : _size - N - 1;
  261. }
  262. bool empty() const {
  263. return size() == 0;
  264. }
  265. iterator begin() { return iterator(item_ptr(0)); }
  266. const_iterator begin() const { return const_iterator(item_ptr(0)); }
  267. iterator end() { return iterator(item_ptr(size())); }
  268. const_iterator end() const { return const_iterator(item_ptr(size())); }
  269. reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); }
  270. const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); }
  271. reverse_iterator rend() { return reverse_iterator(item_ptr(-1)); }
  272. const_reverse_iterator rend() const { return const_reverse_iterator(item_ptr(-1)); }
  273. size_t capacity() const {
  274. if (is_direct()) {
  275. return N;
  276. } else {
  277. return _union.capacity;
  278. }
  279. }
  280. T& operator[](size_type pos) {
  281. return *item_ptr(pos);
  282. }
  283. const T& operator[](size_type pos) const {
  284. return *item_ptr(pos);
  285. }
  286. void resize(size_type new_size) {
  287. if (size() > new_size) {
  288. erase(item_ptr(new_size), end());
  289. }
  290. if (new_size > capacity()) {
  291. change_capacity(new_size);
  292. }
  293. while (size() < new_size) {
  294. _size++;
  295. new(static_cast<void*>(item_ptr(size() - 1))) T();
  296. }
  297. }
  298. void reserve(size_type new_capacity) {
  299. if (new_capacity > capacity()) {
  300. change_capacity(new_capacity);
  301. }
  302. }
  303. void shrink_to_fit() {
  304. change_capacity(size());
  305. }
  306. void clear() {
  307. resize(0);
  308. }
  309. iterator insert(iterator pos, const T& value) {
  310. size_type p = pos - begin();
  311. size_type new_size = size() + 1;
  312. if (capacity() < new_size) {
  313. change_capacity(new_size + (new_size >> 1));
  314. }
  315. memmove(item_ptr(p + 1), item_ptr(p), (size() - p) * sizeof(T));
  316. _size++;
  317. new(static_cast<void*>(item_ptr(p))) T(value);
  318. return iterator(item_ptr(p));
  319. }
  320. void insert(iterator pos, size_type count, const T& value) {
  321. size_type p = pos - begin();
  322. size_type new_size = size() + count;
  323. if (capacity() < new_size) {
  324. change_capacity(new_size + (new_size >> 1));
  325. }
  326. memmove(item_ptr(p + count), item_ptr(p), (size() - p) * sizeof(T));
  327. _size += count;
  328. for (size_type i = 0; i < count; i++) {
  329. new(static_cast<void*>(item_ptr(p + i))) T(value);
  330. }
  331. }
  332. template<typename InputIterator>
  333. void insert(iterator pos, InputIterator first, InputIterator last) {
  334. size_type p = pos - begin();
  335. difference_type count = last - first;
  336. size_type new_size = size() + count;
  337. if (capacity() < new_size) {
  338. change_capacity(new_size + (new_size >> 1));
  339. }
  340. memmove(item_ptr(p + count), item_ptr(p), (size() - p) * sizeof(T));
  341. _size += count;
  342. while (first != last) {
  343. new(static_cast<void*>(item_ptr(p))) T(*first);
  344. ++p;
  345. ++first;
  346. }
  347. }
  348. iterator erase(iterator pos) {
  349. return erase(pos, pos + 1);
  350. }
  351. iterator erase(iterator first, iterator last) {
  352. // Erase is not allowed to the change the object's capacity. That means
  353. // that when starting with an indirectly allocated prevector with
  354. // size and capacity > N, the result may be a still indirectly allocated
  355. // prevector with size <= N and capacity > N. A shrink_to_fit() call is
  356. // necessary to switch to the (more efficient) directly allocated
  357. // representation (with capacity N and size <= N).
  358. iterator p = first;
  359. char* endp = (char*)&(*end());
  360. if (!std::is_trivially_destructible<T>::value) {
  361. while (p != last) {
  362. (*p).~T();
  363. _size--;
  364. ++p;
  365. }
  366. } else {
  367. _size -= last - p;
  368. }
  369. memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
  370. return first;
  371. }
  372. void push_back(const T& value) {
  373. size_type new_size = size() + 1;
  374. if (capacity() < new_size) {
  375. change_capacity(new_size + (new_size >> 1));
  376. }
  377. new(item_ptr(size())) T(value);
  378. _size++;
  379. }
  380. void pop_back() {
  381. erase(end() - 1, end());
  382. }
  383. T& front() {
  384. return *item_ptr(0);
  385. }
  386. const T& front() const {
  387. return *item_ptr(0);
  388. }
  389. T& back() {
  390. return *item_ptr(size() - 1);
  391. }
  392. const T& back() const {
  393. return *item_ptr(size() - 1);
  394. }
  395. void swap(prevector<N, T, Size, Diff>& other) {
  396. std::swap(_union, other._union);
  397. std::swap(_size, other._size);
  398. }
  399. ~prevector() {
  400. if (!std::is_trivially_destructible<T>::value) {
  401. clear();
  402. }
  403. if (!is_direct()) {
  404. free(_union.indirect);
  405. _union.indirect = nullptr;
  406. }
  407. }
  408. bool operator==(const prevector<N, T, Size, Diff>& other) const {
  409. if (other.size() != size()) {
  410. return false;
  411. }
  412. const_iterator b1 = begin();
  413. const_iterator b2 = other.begin();
  414. const_iterator e1 = end();
  415. while (b1 != e1) {
  416. if ((*b1) != (*b2)) {
  417. return false;
  418. }
  419. ++b1;
  420. ++b2;
  421. }
  422. return true;
  423. }
  424. bool operator!=(const prevector<N, T, Size, Diff>& other) const {
  425. return !(*this == other);
  426. }
  427. bool operator<(const prevector<N, T, Size, Diff>& other) const {
  428. if (size() < other.size()) {
  429. return true;
  430. }
  431. if (size() > other.size()) {
  432. return false;
  433. }
  434. const_iterator b1 = begin();
  435. const_iterator b2 = other.begin();
  436. const_iterator e1 = end();
  437. while (b1 != e1) {
  438. if ((*b1) < (*b2)) {
  439. return true;
  440. }
  441. if ((*b2) < (*b1)) {
  442. return false;
  443. }
  444. ++b1;
  445. ++b2;
  446. }
  447. return false;
  448. }
  449. size_t allocated_memory() const {
  450. if (is_direct()) {
  451. return 0;
  452. } else {
  453. return ((size_t)(sizeof(T))) * _union.capacity;
  454. }
  455. }
  456. value_type* data() {
  457. return item_ptr(0);
  458. }
  459. const value_type* data() const {
  460. return item_ptr(0);
  461. }
  462. };
  463. #pragma pack(pop)
  464. #endif