blob: 5410a7ff671ed7610912180230413c7113fbff5e [file] [log] [blame]
// 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