| // Copyright 2019 The SwiftShader Authors. All Rights Reserved. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| // The yarn::containers namespace holds STL-like container implementations that |
| // are optimized for avoiding heap allocations. |
| // Note that unlike many other types in yarn, these containers offer no |
| // protection for concurrent access and are considered 'thread-unsafe'. |
| |
| #ifndef yarn_containers_hpp |
| #define yarn_containers_hpp |
| |
| #include "Debug.hpp" |
| |
| #include <algorithm> // std::max |
| #include <type_traits> // std::aligned_storage |
| #include <utility> // std::move |
| |
| #include <stddef.h> // size_t |
| |
| namespace yarn { |
| namespace containers { |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| // vector<T, BASE_CAPACITY> |
| //////////////////////////////////////////////////////////////////////////////// |
| |
| // vector is a container of contiguously stored elements. |
| // Unlike std::vector, yarn::containers::vector keeps the first BASE_CAPACITY |
| // elements internally, which will avoid dynamic heap allocations. |
| // Once the vector exceeds BASE_CAPACITY elements, vector will allocate storage |
| // from the heap. |
| template <typename T, int BASE_CAPACITY> |
| class vector |
| { |
| public: |
| inline vector() = default; |
| |
| template <int BASE_CAPACITY_2> |
| inline vector(const vector<T, BASE_CAPACITY_2>& other); |
| |
| template <int BASE_CAPACITY_2> |
| inline vector(vector<T, BASE_CAPACITY_2>&& other); |
| |
| inline ~vector(); |
| |
| template <int BASE_CAPACITY_2> |
| inline vector<T, BASE_CAPACITY>& operator = (const vector<T, BASE_CAPACITY_2>&); |
| |
| template <int BASE_CAPACITY_2> |
| inline vector<T, BASE_CAPACITY>& operator = (vector<T, BASE_CAPACITY_2>&&); |
| |
| inline void push_back(const T& el); |
| inline void emplace_back(T&& el); |
| inline void pop_back(); |
| inline T& front(); |
| inline T& back(); |
| inline T* begin(); |
| inline T* end(); |
| inline T& operator[] (size_t i); |
| inline const T& operator[] (size_t i) const; |
| inline size_t size() const; |
| inline size_t cap() const; |
| inline void resize(size_t n); |
| inline void reserve(size_t n); |
| |
| private: |
| using TStorage = typename std::aligned_storage<sizeof(T), alignof(T)>::type; |
| |
| inline void free(); |
| |
| size_t count = 0; |
| size_t capacity = BASE_CAPACITY; |
| TStorage buffer[BASE_CAPACITY]; |
| TStorage* elements = buffer; |
| }; |
| |
| template <typename T, int BASE_CAPACITY> |
| template <int BASE_CAPACITY_2> |
| vector<T, BASE_CAPACITY>::vector(const vector<T, BASE_CAPACITY_2>& other) |
| { |
| *this = other; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| template <int BASE_CAPACITY_2> |
| vector<T, BASE_CAPACITY>::vector(vector<T, BASE_CAPACITY_2>&& other) |
| { |
| *this = std::move(other); |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| vector<T, BASE_CAPACITY>::~vector() |
| { |
| free(); |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| template <int BASE_CAPACITY_2> |
| vector<T, BASE_CAPACITY>& vector<T, BASE_CAPACITY>::operator = (const vector<T, BASE_CAPACITY_2>& other) |
| { |
| free(); |
| reserve(other.size()); |
| count = other.size(); |
| for (size_t i = 0; i < count; i++) |
| { |
| new (&reinterpret_cast<T*>(elements)[i]) T(other[i]); |
| } |
| return *this; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| template <int BASE_CAPACITY_2> |
| vector<T, BASE_CAPACITY>& vector<T, BASE_CAPACITY>::operator = (vector<T, BASE_CAPACITY_2>&& other) |
| { |
| free(); |
| reserve(other.size()); |
| count = other.size(); |
| for (size_t i = 0; i < count; i++) |
| { |
| new (&reinterpret_cast<T*>(elements)[i]) T(std::move(other[i])); |
| } |
| other.resize(0); |
| return *this; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| void vector<T, BASE_CAPACITY>::push_back(const T& el) |
| { |
| reserve(count + 1); |
| new (&reinterpret_cast<T*>(elements)[count]) T(el); |
| count++; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| void vector<T, BASE_CAPACITY>::emplace_back(T&& el) |
| { |
| reserve(count + 1); |
| new (&reinterpret_cast<T*>(elements)[count]) T(std::move(el)); |
| count++; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| void vector<T, BASE_CAPACITY>::pop_back() |
| { |
| YARN_ASSERT(count > 0, "pop_back() called on empty vector"); |
| count--; |
| reinterpret_cast<T*>(elements)[count].~T(); |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| T& vector<T, BASE_CAPACITY>::front() |
| { |
| YARN_ASSERT(count > 0, "front() called on empty vector"); |
| return reinterpret_cast<T*>(elements)[0]; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| T& vector<T, BASE_CAPACITY>::back() |
| { |
| YARN_ASSERT(count > 0, "back() called on empty vector"); |
| return reinterpret_cast<T*>(elements)[count - 1]; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| T* vector<T, BASE_CAPACITY>::begin() |
| { |
| return reinterpret_cast<T*>(elements); |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| T* vector<T, BASE_CAPACITY>::end() |
| { |
| return reinterpret_cast<T*>(elements) + count; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| T& vector<T, BASE_CAPACITY>::operator[] (size_t i) |
| { |
| YARN_ASSERT(i < count, "index %d exceeds vector size %d", int(i), int(count)); |
| return reinterpret_cast<T*>(elements)[i]; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| const T& vector<T, BASE_CAPACITY>::operator[] (size_t i) const |
| { |
| YARN_ASSERT(i < count, "index %d exceeds vector size %d", int(i), int(count)); |
| return reinterpret_cast<T*>(elements)[i]; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| size_t vector<T, BASE_CAPACITY>::size() const |
| { |
| return count; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| void vector<T, BASE_CAPACITY>::resize(size_t n) |
| { |
| reserve(n); |
| while (count < n) |
| { |
| new (&reinterpret_cast<T*>(elements)[count++]) T(); |
| } |
| while (n < count) |
| { |
| reinterpret_cast<T*>(elements)[--count].~T(); |
| } |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| void vector<T, BASE_CAPACITY>::reserve(size_t n) |
| { |
| if (n > capacity) |
| { |
| capacity = std::max<size_t>(n * 2, 8); |
| auto grown = new TStorage[capacity]; |
| for (size_t i = 0; i < count; i++) |
| { |
| new (&reinterpret_cast<T*>(grown)[i]) T(std::move(reinterpret_cast<T*>(elements)[i])); |
| } |
| free(); |
| elements = grown; |
| } |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| void vector<T, BASE_CAPACITY>::free() |
| { |
| for (size_t i = 0; i < count; i++) |
| { |
| reinterpret_cast<T*>(elements)[i].~T(); |
| } |
| |
| if (elements != buffer) |
| { |
| delete []elements; |
| elements = nullptr; |
| } |
| } |
| |
| } // namespace containers |
| } // namespace yarn |
| |
| #endif // yarn_containers_hpp |