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

source code of qtquick3d/src/3rdparty/embree/common/sys/vector.h