vector.h 7.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244
  1. // Copyright 2009-2021 Intel Corporation
  2. // SPDX-License-Identifier: Apache-2.0
  3. #pragma once
  4. #include "alloc.h"
  5. #include <algorithm>
  6. namespace embree
  7. {
  8. template<typename T, typename allocator>
  9. class vector_t
  10. {
  11. public:
  12. typedef T value_type;
  13. typedef T* iterator;
  14. typedef const T* const_iterator;
  15. __forceinline vector_t ()
  16. : size_active(0), size_alloced(0), items(nullptr) {}
  17. __forceinline explicit vector_t (size_t sz)
  18. : size_active(0), size_alloced(0), items(nullptr) { internal_resize_init(sz); }
  19. template<typename M>
  20. __forceinline explicit vector_t (M alloc, size_t sz)
  21. : alloc(alloc), size_active(0), size_alloced(0), items(nullptr) { internal_resize_init(sz); }
  22. __forceinline ~vector_t() {
  23. clear();
  24. }
  25. __forceinline vector_t (const vector_t& other)
  26. {
  27. size_active = other.size_active;
  28. size_alloced = other.size_alloced;
  29. items = alloc.allocate(size_alloced);
  30. for (size_t i=0; i<size_active; i++)
  31. ::new (&items[i]) value_type(other.items[i]);
  32. }
  33. __forceinline vector_t (vector_t&& other)
  34. : alloc(std::move(other.alloc))
  35. {
  36. size_active = other.size_active; other.size_active = 0;
  37. size_alloced = other.size_alloced; other.size_alloced = 0;
  38. items = other.items; other.items = nullptr;
  39. }
  40. __forceinline vector_t& operator=(const vector_t& other)
  41. {
  42. resize(other.size_active);
  43. for (size_t i=0; i<size_active; i++)
  44. items[i] = value_type(other.items[i]);
  45. return *this;
  46. }
  47. __forceinline vector_t& operator=(vector_t&& other)
  48. {
  49. clear();
  50. alloc = std::move(other.alloc);
  51. size_active = other.size_active; other.size_active = 0;
  52. size_alloced = other.size_alloced; other.size_alloced = 0;
  53. items = other.items; other.items = nullptr;
  54. return *this;
  55. }
  56. /********************** Iterators ****************************/
  57. __forceinline iterator begin() { return items; };
  58. __forceinline const_iterator begin() const { return items; };
  59. __forceinline iterator end () { return items+size_active; };
  60. __forceinline const_iterator end () const { return items+size_active; };
  61. /********************** Capacity ****************************/
  62. __forceinline bool empty () const { return size_active == 0; }
  63. __forceinline size_t size () const { return size_active; }
  64. __forceinline size_t capacity () const { return size_alloced; }
  65. __forceinline void resize(size_t new_size) {
  66. internal_resize(new_size,internal_grow_size(new_size));
  67. }
  68. __forceinline void reserve(size_t new_alloced)
  69. {
  70. /* do nothing if container already large enough */
  71. if (new_alloced <= size_alloced)
  72. return;
  73. /* resize exact otherwise */
  74. internal_resize(size_active,new_alloced);
  75. }
  76. __forceinline void shrink_to_fit() {
  77. internal_resize(size_active,size_active);
  78. }
  79. /******************** Element access **************************/
  80. __forceinline T& operator[](size_t i) { assert(i < size_active); return items[i]; }
  81. __forceinline const T& operator[](size_t i) const { assert(i < size_active); return items[i]; }
  82. __forceinline T& at(size_t i) { assert(i < size_active); return items[i]; }
  83. __forceinline const T& at(size_t i) const { assert(i < size_active); return items[i]; }
  84. __forceinline T& front() const { assert(size_active > 0); return items[0]; };
  85. __forceinline T& back () const { assert(size_active > 0); return items[size_active-1]; };
  86. __forceinline T* data() { return items; };
  87. __forceinline const T* data() const { return items; };
  88. /******************** Modifiers **************************/
  89. __forceinline void push_back(const T& nt)
  90. {
  91. const T v = nt; // need local copy as input reference could point to this vector
  92. internal_resize(size_active,internal_grow_size(size_active+1));
  93. ::new (&items[size_active++]) T(v);
  94. }
  95. __forceinline void pop_back()
  96. {
  97. assert(!empty());
  98. size_active--;
  99. items[size_active].~T();
  100. }
  101. __forceinline void clear()
  102. {
  103. /* destroy elements */
  104. for (size_t i=0; i<size_active; i++){
  105. items[i].~T();
  106. }
  107. /* free memory */
  108. alloc.deallocate(items,size_alloced);
  109. items = nullptr;
  110. size_active = size_alloced = 0;
  111. }
  112. /******************** Comparisons **************************/
  113. friend bool operator== (const vector_t& a, const vector_t& b)
  114. {
  115. if (a.size() != b.size()) return false;
  116. for (size_t i=0; i<a.size(); i++)
  117. if (a[i] != b[i])
  118. return false;
  119. return true;
  120. }
  121. friend bool operator!= (const vector_t& a, const vector_t& b) {
  122. return !(a==b);
  123. }
  124. private:
  125. __forceinline void internal_resize_init(size_t new_active)
  126. {
  127. assert(size_active == 0);
  128. assert(size_alloced == 0);
  129. assert(items == nullptr);
  130. if (new_active == 0) return;
  131. items = alloc.allocate(new_active);
  132. for (size_t i=0; i<new_active; i++) ::new (&items[i]) T();
  133. size_active = new_active;
  134. size_alloced = new_active;
  135. }
  136. __forceinline void internal_resize(size_t new_active, size_t new_alloced)
  137. {
  138. assert(new_active <= new_alloced);
  139. /* destroy elements */
  140. if (new_active < size_active)
  141. {
  142. for (size_t i=new_active; i<size_active; i++){
  143. items[i].~T();
  144. }
  145. size_active = new_active;
  146. }
  147. /* only reallocate if necessary */
  148. if (new_alloced == size_alloced) {
  149. for (size_t i=size_active; i<new_active; i++) ::new (&items[i]) T;
  150. size_active = new_active;
  151. return;
  152. }
  153. /* reallocate and copy items */
  154. T* old_items = items;
  155. items = alloc.allocate(new_alloced);
  156. for (size_t i=0; i<size_active; i++) {
  157. ::new (&items[i]) T(std::move(old_items[i]));
  158. old_items[i].~T();
  159. }
  160. for (size_t i=size_active; i<new_active; i++) {
  161. ::new (&items[i]) T;
  162. }
  163. alloc.deallocate(old_items,size_alloced);
  164. size_active = new_active;
  165. size_alloced = new_alloced;
  166. }
  167. __forceinline size_t internal_grow_size(size_t new_alloced)
  168. {
  169. /* do nothing if container already large enough */
  170. if (new_alloced <= size_alloced)
  171. return size_alloced;
  172. /* resize to next power of 2 otherwise */
  173. size_t new_size_alloced = size_alloced;
  174. while (new_size_alloced < new_alloced) {
  175. new_size_alloced = std::max(size_t(1),2*new_size_alloced);
  176. }
  177. return new_size_alloced;
  178. }
  179. private:
  180. allocator alloc;
  181. size_t size_active; // number of valid items
  182. size_t size_alloced; // number of items allocated
  183. T* items; // data array
  184. };
  185. /*! vector class that performs standard allocations */
  186. template<typename T>
  187. using vector = vector_t<T,std::allocator<T>>;
  188. /*! vector class that performs aligned allocations */
  189. template<typename T>
  190. using avector = vector_t<T,aligned_allocator<T,std::alignment_of<T>::value> >;
  191. /*! vector class that performs OS allocations */
  192. template<typename T>
  193. using ovector = vector_t<T,os_allocator<T> >;
  194. }