Revision control
++ // Copyright 2009-2021 Intel Corporation
++ // SPDX-License-Identifier: Apache-2.0
++
++ #pragma once
++
++ #include "alloc.h"
++ #include <algorithm>
++ #include <type_traits>
++
++ namespace embree
++ {
++ template<typename T, typename allocator>
++ class vector_t
++ {
++ public:
++ typedef T value_type;
++ typedef T* iterator;
++ typedef const T* const_iterator;
++
++ __forceinline vector_t ()
++ : size_active(0), size_alloced(0), items(nullptr) {}
++
++ __forceinline explicit vector_t (size_t sz)
++ : size_active(0), size_alloced(0), items(nullptr) { internal_resize_init(sz); }
++
++ template<typename M>
++ __forceinline explicit vector_t (M alloc, size_t sz)
++ : alloc(alloc), size_active(0), size_alloced(0), items(nullptr) { internal_resize_init(sz); }
++
++ __forceinline ~vector_t() {
++ clear();
++ }
++
++ __forceinline vector_t (const vector_t& other)
++ {
++ size_active = other.size_active;
++ size_alloced = other.size_alloced;
++ items = alloc.allocate(size_alloced);
++ for (size_t i=0; i<size_active; i++)
++ ::new (&items[i]) value_type(other.items[i]);
++ }
++
++ __forceinline vector_t (vector_t&& other)
++ : alloc(std::move(other.alloc))
++ {
++ size_active = other.size_active; other.size_active = 0;
++ size_alloced = other.size_alloced; other.size_alloced = 0;
++ items = other.items; other.items = nullptr;
++ }
++
++ __forceinline vector_t& operator=(const vector_t& other)
++ {
++ resize(other.size_active);
++ for (size_t i=0; i<size_active; i++)
++ items[i] = value_type(other.items[i]);
++ return *this;
++ }
++
++ __forceinline vector_t& operator=(vector_t&& other)
++ {
++ clear();
++ alloc = std::move(other.alloc);
++ size_active = other.size_active; other.size_active = 0;
++ size_alloced = other.size_alloced; other.size_alloced = 0;
++ items = other.items; other.items = nullptr;
++ return *this;
++ }
++
++ /********************** Iterators ****************************/
++
++ __forceinline iterator begin() { return items; };
++ __forceinline const_iterator begin() const { return items; };
++
++ __forceinline iterator end () { return items+size_active; };
++ __forceinline const_iterator end () const { return items+size_active; };
++
++
++ /********************** Capacity ****************************/
++
++ __forceinline bool empty () const { return size_active == 0; }
++ __forceinline size_t size () const { return size_active; }
++ __forceinline size_t capacity () const { return size_alloced; }
++
++
++ __forceinline void resize(size_t new_size) {
++ internal_resize(new_size,internal_grow_size(new_size));
++ }
++
++ __forceinline void reserve(size_t new_alloced)
++ {
++ /* do nothing if container already large enough */
++ if (new_alloced <= size_alloced)
++ return;
++
++ /* resize exact otherwise */
++ internal_resize(size_active,new_alloced);
++ }
++
++ __forceinline void shrink_to_fit() {
++ internal_resize(size_active,size_active);
++ }
++
++ /******************** Element access **************************/
++
++ __forceinline T& operator[](size_t i) { assert(i < size_active); return items[i]; }
++ __forceinline const T& operator[](size_t i) const { assert(i < size_active); return items[i]; }
++
++ __forceinline T& at(size_t i) { assert(i < size_active); return items[i]; }
++ __forceinline const T& at(size_t i) const { assert(i < size_active); return items[i]; }
++
++ __forceinline T& front() const { assert(size_active > 0); return items[0]; };
++ __forceinline T& back () const { assert(size_active > 0); return items[size_active-1]; };
++
++ __forceinline T* data() { return items; };
++ __forceinline const T* data() const { return items; };
++
++
++ /******************** Modifiers **************************/
++
++ __forceinline void push_back(const T& nt)
++ {
++ const T v = nt; // need local copy as input reference could point to this vector
++ internal_resize(size_active,internal_grow_size(size_active+1));
++ ::new (&items[size_active++]) T(v);
++ }
++
++ __forceinline void pop_back()
++ {
++ assert(!empty());
++ size_active--;
++ std::allocator_traits<decltype(alloc)>::destroy(alloc, &items[size_active]);
++ }
++
++ __forceinline void clear()
++ {
++ /* destroy elements */
++ for (size_t i=0; i<size_active; i++)
++ std::allocator_traits<decltype(alloc)>::destroy(alloc, &items[i]);
++
++ /* free memory */
++ alloc.deallocate(items,size_alloced);
++ items = nullptr;
++ size_active = size_alloced = 0;
++ }
++
++ /******************** Comparisons **************************/
++
++ friend bool operator== (const vector_t& a, const vector_t& b)
++ {
++ if (a.size() != b.size()) return false;
++ for (size_t i=0; i<a.size(); i++)
++ if (a[i] != b[i])
++ return false;
++ return true;
++ }
++
++ friend bool operator!= (const vector_t& a, const vector_t& b) {
++ return !(a==b);
++ }
++
++ private:
++
++ __forceinline void internal_resize_init(size_t new_active)
++ {
++ assert(size_active == 0);
++ assert(size_alloced == 0);
++ assert(items == nullptr);
++ if (new_active == 0) return;
++ items = alloc.allocate(new_active);
++ for (size_t i=0; i<new_active; i++) ::new (&items[i]) T();
++ size_active = new_active;
++ size_alloced = new_active;
++ }
++
++ __forceinline void internal_resize(size_t new_active, size_t new_alloced)
++ {
++ assert(new_active <= new_alloced);
++
++ /* destroy elements */
++ if (new_active < size_active)
++ {
++ for (size_t i=new_active; i<size_active; i++)
++ std::allocator_traits<decltype(alloc)>::destroy(alloc, &items[i]);
++ size_active = new_active;
++ }
++
++ /* only reallocate if necessary */
++ if (new_alloced == size_alloced) {
++ for (size_t i=size_active; i<new_active; i++) ::new (&items[i]) T;
++ size_active = new_active;
++ return;
++ }
++
++ /* reallocate and copy items */
++ T* old_items = items;
++ items = alloc.allocate(new_alloced);
++ for (size_t i=0; i<size_active; i++) {
++ ::new (&items[i]) T(std::move(old_items[i]));
++ std::allocator_traits<decltype(alloc)>::destroy(alloc, &old_items[i]);
++ }
++
++ for (size_t i=size_active; i<new_active; i++) {
++ ::new (&items[i]) T;
++ }
++
++ alloc.deallocate(old_items,size_alloced);
++ size_active = new_active;
++ size_alloced = new_alloced;
++ }
++
++ __forceinline size_t internal_grow_size(size_t new_alloced)
++ {
++ /* do nothing if container already large enough */
++ if (new_alloced <= size_alloced)
++ return size_alloced;
++
++ /* resize to next power of 2 otherwise */
++ size_t new_size_alloced = size_alloced;
++ while (new_size_alloced < new_alloced) {
++ new_size_alloced = std::max(size_t(1),2*new_size_alloced);
++ }
++ return new_size_alloced;
++ }
++
++ private:
++ allocator alloc;
++ size_t size_active; // number of valid items
++ size_t size_alloced; // number of items allocated
++ T* items; // data array
++ };
++
++ /*! vector class that performs standard allocations */
++ template<typename T>
++ using vector = vector_t<T,std::allocator<T>>;
++
++ /*! vector class that performs aligned allocations */
++ template<typename T>
++ using avector = vector_t<T,aligned_allocator<T,std::alignment_of<T>::value> >;
++
++ /*! vector class that performs OS allocations */
++ template<typename T>
++ using ovector = vector_t<T,os_allocator<T> >;
++ }