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 
9 namespace 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 
vector_t()19       __forceinline vector_t ()
20         : size_active(0), size_alloced(0), items(nullptr) {}
21 
vector_t(size_t sz)22       __forceinline explicit vector_t (size_t sz)
23         : size_active(0), size_alloced(0), items(nullptr) { internal_resize_init(sz); }
24 
25       template<typename M>
vector_t(M alloc,size_t sz)26       __forceinline explicit vector_t (M alloc, size_t sz)
27       : alloc(alloc), size_active(0), size_alloced(0), items(nullptr) { internal_resize_init(sz); }
28 
~vector_t()29       __forceinline ~vector_t() {
30         clear();
31       }
32 
vector_t(const vector_t & other)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 
vector_t(vector_t && other)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(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 
begin()70       __forceinline       iterator begin()       { return items; };
begin()71       __forceinline const_iterator begin() const { return items; };
72 
end()73       __forceinline       iterator end  ()       { return items+size_active; };
end()74       __forceinline const_iterator end  () const { return items+size_active; };
75 
76 
77       /********************** Capacity ****************************/
78 
empty()79       __forceinline bool   empty    () const { return size_active == 0; }
size()80       __forceinline size_t size     () const { return size_active; }
capacity()81       __forceinline size_t capacity () const { return size_alloced; }
82 
83 
resize(size_t new_size)84       __forceinline void resize(size_t new_size) {
85         internal_resize(new_size,internal_grow_size(new_size));
86       }
87 
reserve(size_t new_alloced)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(size_active,new_alloced);
96       }
97 
shrink_to_fit()98       __forceinline void shrink_to_fit() {
99         internal_resize(size_active,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 
at(size_t i)107       __forceinline       T& at(size_t i)       { assert(i < size_active); return items[i]; }
at(size_t i)108       __forceinline const T& at(size_t i) const { assert(i < size_active); return items[i]; }
109 
front()110       __forceinline T& front() const { assert(size_active > 0); return items[0]; };
back()111       __forceinline T& back () const { assert(size_active > 0); return items[size_active-1]; };
112 
data()113       __forceinline       T* data()       { return items; };
data()114       __forceinline const T* data() const { return items; };
115 
116 
117       /******************** Modifiers **************************/
118 
push_back(const T & nt)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(size_active,internal_grow_size(size_active+1));
123         ::new (&items[size_active++]) T(v);
124       }
125 
pop_back()126       __forceinline void pop_back()
127       {
128         assert(!empty());
129         size_active--;
130         alloc.destroy(&items[size_active]);
131       }
132 
clear()133       __forceinline void clear()
134       {
135         /* destroy elements */
136         for (size_t i=0; i<size_active; i++)
137           alloc.destroy(&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 
internal_resize_init(size_t new_active)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 
internal_resize(size_t new_active,size_t new_alloced)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             alloc.destroy(&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           alloc.destroy(&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 
internal_grow_size(size_t new_alloced)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(size_t(1),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