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

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