| // Copyright 2019 The Marl Authors. |
| // |
| // 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 |
| // |
| // https://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. |
| |
| #ifndef marl_containers_h |
| #define marl_containers_h |
| |
| #include "debug.h" |
| #include "memory.h" |
| |
| #include <algorithm> // std::max |
| #include <cstddef> // size_t |
| #include <utility> // std::move |
| |
| #include <deque> |
| #include <map> |
| #include <set> |
| #include <unordered_map> |
| #include <unordered_set> |
| |
| namespace marl { |
| namespace containers { |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| // STL wrappers |
| // STL containers that use a marl::StlAllocator backed by a marl::Allocator. |
| // Note: These may be re-implemented to optimize for marl's usage cases. |
| // See: https://github.com/google/marl/issues/129 |
| //////////////////////////////////////////////////////////////////////////////// |
| template <typename T> |
| using deque = std::deque<T, StlAllocator<T>>; |
| |
| template <typename K, typename V, typename C = std::less<K>> |
| using map = std::map<K, V, C, StlAllocator<std::pair<const K, V>>>; |
| |
| template <typename K, typename C = std::less<K>> |
| using set = std::set<K, C, StlAllocator<K>>; |
| |
| template <typename K, |
| typename V, |
| typename H = std::hash<K>, |
| typename E = std::equal_to<K>> |
| using unordered_map = |
| std::unordered_map<K, V, H, E, StlAllocator<std::pair<const K, V>>>; |
| |
| template <typename K, typename H = std::hash<K>, typename E = std::equal_to<K>> |
| using unordered_set = std::unordered_set<K, H, E, StlAllocator<K>>; |
| |
| // take() takes and returns the front value from the deque. |
| template <typename T> |
| MARL_NO_EXPORT inline T take(deque<T>& queue) { |
| auto out = std::move(queue.front()); |
| queue.pop_front(); |
| return out; |
| } |
| |
| // take() takes and returns the first value from the unordered_set. |
| template <typename T, typename H, typename E> |
| MARL_NO_EXPORT inline T take(unordered_set<T, H, E>& set) { |
| auto it = set.begin(); |
| auto out = std::move(*it); |
| set.erase(it); |
| return out; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| // vector<T, BASE_CAPACITY> |
| //////////////////////////////////////////////////////////////////////////////// |
| |
| // vector is a container of contiguously stored elements. |
| // Unlike std::vector, marl::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: |
| MARL_NO_EXPORT inline vector(Allocator* allocator = Allocator::Default); |
| |
| template <int BASE_CAPACITY_2> |
| MARL_NO_EXPORT inline vector(const vector<T, BASE_CAPACITY_2>& other, |
| Allocator* allocator = Allocator::Default); |
| |
| template <int BASE_CAPACITY_2> |
| MARL_NO_EXPORT inline vector(vector<T, BASE_CAPACITY_2>&& other, |
| Allocator* allocator = Allocator::Default); |
| |
| MARL_NO_EXPORT inline ~vector(); |
| |
| MARL_NO_EXPORT inline vector& operator=(const vector&); |
| |
| template <int BASE_CAPACITY_2> |
| MARL_NO_EXPORT inline vector<T, BASE_CAPACITY>& operator=( |
| const vector<T, BASE_CAPACITY_2>&); |
| |
| template <int BASE_CAPACITY_2> |
| MARL_NO_EXPORT inline vector<T, BASE_CAPACITY>& operator=( |
| vector<T, BASE_CAPACITY_2>&&); |
| |
| MARL_NO_EXPORT inline void push_back(const T& el); |
| MARL_NO_EXPORT inline void emplace_back(T&& el); |
| MARL_NO_EXPORT inline void pop_back(); |
| MARL_NO_EXPORT inline T& front(); |
| MARL_NO_EXPORT inline T& back(); |
| MARL_NO_EXPORT inline const T& front() const; |
| MARL_NO_EXPORT inline const T& back() const; |
| MARL_NO_EXPORT inline T* begin(); |
| MARL_NO_EXPORT inline T* end(); |
| MARL_NO_EXPORT inline const T* begin() const; |
| MARL_NO_EXPORT inline const T* end() const; |
| MARL_NO_EXPORT inline T& operator[](size_t i); |
| MARL_NO_EXPORT inline const T& operator[](size_t i) const; |
| MARL_NO_EXPORT inline size_t size() const; |
| MARL_NO_EXPORT inline size_t cap() const; |
| MARL_NO_EXPORT inline void resize(size_t n); |
| MARL_NO_EXPORT inline void reserve(size_t n); |
| MARL_NO_EXPORT inline T* data(); |
| MARL_NO_EXPORT inline const T* data() const; |
| |
| Allocator* const allocator; |
| |
| private: |
| using TStorage = typename marl::aligned_storage<sizeof(T), alignof(T)>::type; |
| |
| vector(const vector&) = delete; |
| |
| MARL_NO_EXPORT inline void free(); |
| |
| size_t count = 0; |
| size_t capacity = BASE_CAPACITY; |
| TStorage buffer[BASE_CAPACITY]; |
| TStorage* elements = buffer; |
| Allocation allocation; |
| }; |
| |
| template <typename T, int BASE_CAPACITY> |
| vector<T, BASE_CAPACITY>::vector( |
| Allocator* allocator /* = Allocator::Default */) |
| : allocator(allocator) {} |
| |
| template <typename T, int BASE_CAPACITY> |
| template <int BASE_CAPACITY_2> |
| vector<T, BASE_CAPACITY>::vector( |
| const vector<T, BASE_CAPACITY_2>& other, |
| Allocator* allocator /* = Allocator::Default */) |
| : allocator(allocator) { |
| *this = other; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| template <int BASE_CAPACITY_2> |
| vector<T, BASE_CAPACITY>::vector( |
| vector<T, BASE_CAPACITY_2>&& other, |
| Allocator* allocator /* = Allocator::Default */) |
| : allocator(allocator) { |
| *this = std::move(other); |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| vector<T, BASE_CAPACITY>::~vector() { |
| free(); |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| vector<T, BASE_CAPACITY>& vector<T, BASE_CAPACITY>::operator=( |
| const vector& 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=( |
| 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() { |
| MARL_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() { |
| MARL_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() { |
| MARL_ASSERT(count > 0, "back() called on empty vector"); |
| return reinterpret_cast<T*>(elements)[count - 1]; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| const T& vector<T, BASE_CAPACITY>::front() const { |
| MARL_ASSERT(count > 0, "front() called on empty vector"); |
| return reinterpret_cast<T*>(elements)[0]; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| const T& vector<T, BASE_CAPACITY>::back() const { |
| MARL_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> |
| const T* vector<T, BASE_CAPACITY>::begin() const { |
| return reinterpret_cast<T*>(elements); |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| const T* vector<T, BASE_CAPACITY>::end() const { |
| return reinterpret_cast<T*>(elements) + count; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| T& vector<T, BASE_CAPACITY>::operator[](size_t i) { |
| MARL_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 { |
| MARL_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); |
| |
| Allocation::Request request; |
| request.size = sizeof(T) * capacity; |
| request.alignment = alignof(T); |
| request.usage = Allocation::Usage::Vector; |
| |
| auto alloc = allocator->allocate(request); |
| auto grown = reinterpret_cast<TStorage*>(alloc.ptr); |
| 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; |
| allocation = alloc; |
| } |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| T* vector<T, BASE_CAPACITY>::data() { |
| return elements; |
| } |
| |
| template <typename T, int BASE_CAPACITY> |
| const T* vector<T, BASE_CAPACITY>::data() const { |
| return elements; |
| } |
| |
| 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 (allocation.ptr != nullptr) { |
| allocator->free(allocation); |
| allocation = {}; |
| elements = nullptr; |
| } |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| // list<T, BASE_CAPACITY> |
| //////////////////////////////////////////////////////////////////////////////// |
| |
| // list is a minimal std::list like container that supports constant time |
| // insertion and removal of elements. |
| // list keeps hold of allocations (it only releases allocations on destruction), |
| // to avoid repeated heap allocations and frees when frequently inserting and |
| // removing elements. |
| template <typename T> |
| class list { |
| struct Entry { |
| T data; |
| Entry* next; |
| Entry* prev; |
| }; |
| |
| public: |
| class iterator { |
| public: |
| MARL_NO_EXPORT inline iterator(Entry*); |
| MARL_NO_EXPORT inline T* operator->(); |
| MARL_NO_EXPORT inline T& operator*(); |
| MARL_NO_EXPORT inline iterator& operator++(); |
| MARL_NO_EXPORT inline bool operator==(const iterator&) const; |
| MARL_NO_EXPORT inline bool operator!=(const iterator&) const; |
| |
| private: |
| friend list; |
| Entry* entry; |
| }; |
| |
| MARL_NO_EXPORT inline list(Allocator* allocator = Allocator::Default); |
| MARL_NO_EXPORT inline ~list(); |
| |
| MARL_NO_EXPORT inline iterator begin(); |
| MARL_NO_EXPORT inline iterator end(); |
| MARL_NO_EXPORT inline size_t size() const; |
| |
| template <typename... Args> |
| MARL_NO_EXPORT inline iterator emplace_front(Args&&... args); |
| MARL_NO_EXPORT inline void erase(iterator); |
| |
| private: |
| // copy / move is currently unsupported. |
| list(const list&) = delete; |
| list(list&&) = delete; |
| list& operator=(const list&) = delete; |
| list& operator=(list&&) = delete; |
| |
| struct AllocationChain { |
| Allocation allocation; |
| AllocationChain* next; |
| }; |
| |
| MARL_NO_EXPORT inline void grow(size_t count); |
| |
| MARL_NO_EXPORT static inline void unlink(Entry* entry, Entry*& list); |
| MARL_NO_EXPORT static inline void link(Entry* entry, Entry*& list); |
| |
| Allocator* const allocator; |
| size_t size_ = 0; |
| size_t capacity = 0; |
| AllocationChain* allocations = nullptr; |
| Entry* free = nullptr; |
| Entry* head = nullptr; |
| }; |
| |
| template <typename T> |
| list<T>::iterator::iterator(Entry* entry) : entry(entry) {} |
| |
| template <typename T> |
| T* list<T>::iterator::operator->() { |
| return &entry->data; |
| } |
| |
| template <typename T> |
| T& list<T>::iterator::operator*() { |
| return entry->data; |
| } |
| |
| template <typename T> |
| typename list<T>::iterator& list<T>::iterator::operator++() { |
| entry = entry->next; |
| return *this; |
| } |
| |
| template <typename T> |
| bool list<T>::iterator::operator==(const iterator& rhs) const { |
| return entry == rhs.entry; |
| } |
| |
| template <typename T> |
| bool list<T>::iterator::operator!=(const iterator& rhs) const { |
| return entry != rhs.entry; |
| } |
| |
| template <typename T> |
| list<T>::list(Allocator* allocator /* = Allocator::Default */) |
| : allocator(allocator) {} |
| |
| template <typename T> |
| list<T>::~list() { |
| for (auto el = head; el != nullptr; el = el->next) { |
| el->data.~T(); |
| } |
| |
| auto curr = allocations; |
| while (curr != nullptr) { |
| auto next = curr->next; |
| allocator->free(curr->allocation); |
| curr = next; |
| } |
| } |
| |
| template <typename T> |
| typename list<T>::iterator list<T>::begin() { |
| return {head}; |
| } |
| |
| template <typename T> |
| typename list<T>::iterator list<T>::end() { |
| return {nullptr}; |
| } |
| |
| template <typename T> |
| size_t list<T>::size() const { |
| return size_; |
| } |
| |
| template <typename T> |
| template <typename... Args> |
| typename list<T>::iterator list<T>::emplace_front(Args&&... args) { |
| if (free == nullptr) { |
| grow(std::max<size_t>(capacity, 8)); |
| } |
| |
| auto entry = free; |
| |
| unlink(entry, free); |
| link(entry, head); |
| |
| new (&entry->data) T(std::forward<T>(args)...); |
| size_++; |
| |
| return entry; |
| } |
| |
| template <typename T> |
| void list<T>::erase(iterator it) { |
| auto entry = it.entry; |
| unlink(entry, head); |
| link(entry, free); |
| |
| entry->data.~T(); |
| size_--; |
| } |
| |
| template <typename T> |
| void list<T>::grow(size_t count) { |
| auto const entriesSize = sizeof(Entry) * count; |
| auto const allocChainOffset = alignUp(entriesSize, alignof(AllocationChain)); |
| auto const allocSize = allocChainOffset + sizeof(AllocationChain); |
| |
| Allocation::Request request; |
| request.size = allocSize; |
| request.alignment = std::max(alignof(Entry), alignof(AllocationChain)); |
| request.usage = Allocation::Usage::List; |
| auto alloc = allocator->allocate(request); |
| |
| auto entries = reinterpret_cast<Entry*>(alloc.ptr); |
| for (size_t i = 0; i < count; i++) { |
| auto entry = &entries[i]; |
| entry->prev = nullptr; |
| entry->next = free; |
| if (free) { |
| free->prev = entry; |
| } |
| free = entry; |
| } |
| |
| auto allocChain = reinterpret_cast<AllocationChain*>( |
| reinterpret_cast<uint8_t*>(alloc.ptr) + allocChainOffset); |
| |
| allocChain->allocation = alloc; |
| allocChain->next = allocations; |
| allocations = allocChain; |
| |
| capacity += count; |
| } |
| |
| template <typename T> |
| void list<T>::unlink(Entry* entry, Entry*& list) { |
| if (list == entry) { |
| list = list->next; |
| } |
| if (entry->prev) { |
| entry->prev->next = entry->next; |
| } |
| if (entry->next) { |
| entry->next->prev = entry->prev; |
| } |
| entry->prev = nullptr; |
| entry->next = nullptr; |
| } |
| |
| template <typename T> |
| void list<T>::link(Entry* entry, Entry*& list) { |
| MARL_ASSERT(entry->next == nullptr, "link() called on entry already linked"); |
| MARL_ASSERT(entry->prev == nullptr, "link() called on entry already linked"); |
| if (list) { |
| entry->next = list; |
| list->prev = entry; |
| } |
| list = entry; |
| } |
| |
| } // namespace containers |
| } // namespace marl |
| |
| #endif // marl_containers_h |