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