mirror of
https://github.com/wichtounet/thor-os.git
synced 2025-09-10 04:52:14 -04:00
707 lines
18 KiB
C++
707 lines
18 KiB
C++
//=======================================================================
|
|
// Copyright Baptiste Wicht 2013-2018.
|
|
// Distributed under the terms of the MIT License.
|
|
// (See accompanying file LICENSE or copy at
|
|
// http://www.opensource.org/licenses/MIT)
|
|
//=======================================================================
|
|
|
|
#ifndef DEQUE_H
|
|
#define DEQUE_H
|
|
|
|
#include <initializer_list.hpp>
|
|
#include <types.hpp>
|
|
#include <algorithms.hpp>
|
|
#include <new.hpp>
|
|
#include <iterator.hpp>
|
|
|
|
namespace std {
|
|
|
|
template <typename T>
|
|
struct deque;
|
|
|
|
template <typename T>
|
|
struct deque_iterator {
|
|
using iterator_type = deque_iterator<T>; ///< The iterator type
|
|
using value_type = T; ///< The value type
|
|
using difference_type = int64_t; ///< The difference type
|
|
using pointer = value_type*; ///< The pointer type
|
|
using reference = value_type&; ///< The reference type
|
|
|
|
deque_iterator(deque<T>* container, int64_t index)
|
|
: container(container), index(index) {
|
|
// Nothing else to init
|
|
}
|
|
|
|
deque_iterator(const deque_iterator& rhs) : container(rhs.container), index(rhs.index) {
|
|
// Nothing else to init
|
|
}
|
|
|
|
deque_iterator& operator=(const deque_iterator& rhs){
|
|
if(this != &rhs){
|
|
this->container = rhs.container;
|
|
this->index = rhs.index;
|
|
}
|
|
|
|
return *this;
|
|
}
|
|
|
|
T& operator*() {
|
|
return (*container)[index];
|
|
}
|
|
|
|
deque_iterator& operator++() {
|
|
++index;
|
|
return *this;
|
|
}
|
|
|
|
deque_iterator operator++(int) {
|
|
auto it = *this;
|
|
++(*this);
|
|
return it;
|
|
}
|
|
|
|
deque_iterator& operator--() {
|
|
--index;
|
|
return *this;
|
|
}
|
|
|
|
deque_iterator operator--(int) {
|
|
auto it = *this;
|
|
--(*this);
|
|
return it;
|
|
}
|
|
|
|
deque_iterator& operator+=(int n) {
|
|
index += n;
|
|
return *this;
|
|
}
|
|
|
|
deque_iterator operator+(int n) {
|
|
auto it = *this;
|
|
it += n;
|
|
return it;
|
|
}
|
|
|
|
deque_iterator& operator-=(int n) {
|
|
index -= n;
|
|
return *this;
|
|
}
|
|
|
|
deque_iterator operator-(int n) {
|
|
auto it = *this;
|
|
it -= n;
|
|
return it;
|
|
}
|
|
|
|
bool operator==(const deque_iterator& rhs) {
|
|
return index == rhs.index;
|
|
}
|
|
|
|
bool operator!=(const deque_iterator& rhs) {
|
|
return index != rhs.index;
|
|
}
|
|
|
|
difference_type operator-(const deque_iterator& rhs) {
|
|
return index - rhs.index;
|
|
}
|
|
|
|
friend struct deque<T>;
|
|
|
|
private:
|
|
deque<T>* container;
|
|
int64_t index;
|
|
};
|
|
|
|
// TODO We should find a way to get rid of the painful situation when size
|
|
// = 0 for the indices
|
|
|
|
/*!
|
|
* \brief A double-ended queue.
|
|
*
|
|
* Insertions at the front and at the back are done in O(1) and random access is
|
|
* possible in O(1). Insertions at other positions is done in O(n).
|
|
*/
|
|
template <typename T>
|
|
struct deque {
|
|
using value_type = T; ///< The value type contained in the vector
|
|
using pointer_type = value_type*; ///< The pointer type contained in the vector
|
|
using size_type = size_t; ///< The size type
|
|
using reference_type = value_type&; ///< The reference type
|
|
using const_reference_type = const value_type&; ///< The const reference type
|
|
|
|
using iterator = deque_iterator<T>; ///< The iterator type
|
|
using const_iterator = deque_iterator<const T>; ///< The const iterator type
|
|
|
|
using reverse_iterator = std::reverse_iterator<iterator>; ///< The reverse iterator type
|
|
using const_reverse_iterator = std::reverse_iterator<const_iterator>; ///< The const reverse iterator type
|
|
|
|
static constexpr const size_t block_elements = 16; ///< Number of entries per block
|
|
static constexpr const size_t block_size = block_elements * sizeof(T); ///< Size of a block, in bytes
|
|
|
|
/*!
|
|
* \brief Construct an empty deque
|
|
*/
|
|
deque()
|
|
: data(nullptr), first_element(0), last_element(0), blocks(0), _size(0) {
|
|
// By default, no capacity
|
|
}
|
|
|
|
/*!
|
|
* \brief Construct a deque containing the given values
|
|
*/
|
|
deque(initializer_list<T> values)
|
|
: deque() {
|
|
ensure_capacity_back(values.size());
|
|
|
|
for (auto& value : values) {
|
|
push_back(value);
|
|
}
|
|
}
|
|
|
|
//TODO
|
|
deque(const deque& rhs) = delete;
|
|
deque& operator=(const deque& rhs) = delete;
|
|
|
|
deque(deque&& rhs) : data(rhs.data), first_element(rhs.first_element), last_element(rhs.last_element), blocks(rhs.blocks), _size(rhs._size){
|
|
rhs.data = nullptr;
|
|
rhs.first_element = 0;
|
|
rhs.last_element = 0;
|
|
rhs.blocks = 0;
|
|
rhs._size = 0;
|
|
}
|
|
|
|
deque& operator=(deque&& rhs){
|
|
if(this != &rhs){
|
|
this->data = rhs.data;
|
|
this->first_element = rhs.first_element;
|
|
this->last_element = rhs.last_element;
|
|
this->blocks = rhs.blocks;
|
|
this->_size = rhs._size;
|
|
|
|
rhs.data = nullptr;
|
|
rhs.first_element = 0;
|
|
rhs.last_element = 0;
|
|
rhs.blocks = 0;
|
|
rhs._size = 0;
|
|
}
|
|
|
|
return *this;
|
|
}
|
|
|
|
void destruct_all(){
|
|
for (size_t i = 0; i < _size; ++i) {
|
|
(*this)[i].~value_type();
|
|
}
|
|
}
|
|
|
|
~deque() {
|
|
destruct_all();
|
|
|
|
for(size_t i = 0; i < blocks; ++i){
|
|
deallocate(data[i]);
|
|
}
|
|
|
|
delete[] data;
|
|
}
|
|
|
|
/*!
|
|
* \brief Push an element at the back of the deque
|
|
*/
|
|
void push_back(T&& element) {
|
|
ensure_capacity_back(1);
|
|
|
|
if (_size) {
|
|
auto block = (last_element + 1) / block_elements;
|
|
auto index = (last_element + 1) % block_elements;
|
|
|
|
new (&data[block][index]) T(std::move(element));
|
|
|
|
++last_element;
|
|
} else {
|
|
auto block = last_element / block_elements;
|
|
auto index = last_element % block_elements;
|
|
|
|
new (&data[block][index]) T(std::move(element));
|
|
}
|
|
|
|
++_size;
|
|
}
|
|
|
|
/*!
|
|
* \brief Push an element at the back of the deque
|
|
*/
|
|
void push_back(const T& element) {
|
|
ensure_capacity_back(1);
|
|
|
|
if (_size) {
|
|
auto block = (last_element + 1) / block_elements;
|
|
auto index = (last_element + 1) % block_elements;
|
|
|
|
new (&data[block][index]) T(element);
|
|
|
|
++last_element;
|
|
} else {
|
|
auto block = last_element / block_elements;
|
|
auto index = last_element % block_elements;
|
|
|
|
new (&data[block][index]) T(element);
|
|
}
|
|
|
|
++_size;
|
|
}
|
|
|
|
/*!
|
|
* \brief Construct an element at the back of the vector, enplace.
|
|
*/
|
|
reference_type emplace_back() {
|
|
ensure_capacity_back(1);
|
|
|
|
if (_size) {
|
|
auto block = (last_element + 1) / block_elements;
|
|
auto index = (last_element + 1) % block_elements;
|
|
|
|
new (&data[block][index]) T();
|
|
|
|
++last_element;
|
|
} else {
|
|
auto block = last_element / block_elements;
|
|
auto index = last_element % block_elements;
|
|
|
|
new (&data[block][index]) T();
|
|
}
|
|
|
|
++_size;
|
|
|
|
return back();
|
|
}
|
|
|
|
/*!
|
|
* \brief Construct an element at the back of the vector, enplace.
|
|
*/
|
|
template <typename... Args>
|
|
reference_type emplace_back(Args&&... args) {
|
|
ensure_capacity_back(1);
|
|
|
|
if (_size) {
|
|
auto block = (last_element + 1) / block_elements;
|
|
auto index = (last_element + 1) % block_elements;
|
|
|
|
new (&data[block][index]) T(std::forward<Args>(args)...);
|
|
|
|
++last_element;
|
|
} else {
|
|
auto block = last_element / block_elements;
|
|
auto index = last_element % block_elements;
|
|
|
|
new (&data[block][index]) T(std::forward<Args>(args)...);
|
|
}
|
|
|
|
++_size;
|
|
|
|
return back();
|
|
}
|
|
|
|
/*!
|
|
* \brief Push an element at the front of the deque
|
|
*/
|
|
void push_front(T&& element) {
|
|
ensure_capacity_front(1);
|
|
|
|
if (_size) {
|
|
auto block = (first_element - 1) / block_elements;
|
|
auto index = (first_element - 1) % block_elements;
|
|
|
|
new (&data[block][index]) T(std::move(element));
|
|
|
|
--first_element;
|
|
} else {
|
|
auto block = first_element / block_elements;
|
|
auto index = first_element % block_elements;
|
|
|
|
new (&data[block][index]) T(std::move(element));
|
|
}
|
|
|
|
++_size;
|
|
}
|
|
|
|
/*!
|
|
* \brief Push an element at the front of the deque
|
|
*/
|
|
void push_front(const T& element) {
|
|
ensure_capacity_front(1);
|
|
|
|
if (_size) {
|
|
auto block = (first_element - 1) / block_elements;
|
|
auto index = (first_element - 1) % block_elements;
|
|
|
|
new (&data[block][index]) T(element);
|
|
|
|
--first_element;
|
|
} else {
|
|
auto block = first_element / block_elements;
|
|
auto index = first_element % block_elements;
|
|
|
|
new (&data[block][index]) T(element);
|
|
}
|
|
|
|
++_size;
|
|
}
|
|
|
|
/*!
|
|
* \brief Construct an element at the front of the vector, enplace.
|
|
*/
|
|
reference_type emplace_front() {
|
|
ensure_capacity_front(1);
|
|
|
|
if (_size) {
|
|
auto block = (first_element - 1) / block_elements;
|
|
auto index = (first_element - 1) % block_elements;
|
|
|
|
new (&data[block][index]) T();
|
|
|
|
--first_element;
|
|
} else {
|
|
auto block = first_element / block_elements;
|
|
auto index = first_element % block_elements;
|
|
|
|
new (&data[block][index]) T();
|
|
}
|
|
|
|
++_size;
|
|
}
|
|
|
|
/*!
|
|
* \brief Construct an element at the front of the vector, enplace.
|
|
*/
|
|
template <typename... Args>
|
|
reference_type emplace_front(Args&&... args) {
|
|
ensure_capacity_front(1);
|
|
|
|
if (_size) {
|
|
auto block = (first_element - 1) / block_elements;
|
|
auto index = (first_element - 1) % block_elements;
|
|
|
|
new (&data[block][index]) T(std::forward<Args>(args)...);
|
|
|
|
--first_element;
|
|
} else {
|
|
auto block = first_element / block_elements;
|
|
auto index = first_element % block_elements;
|
|
|
|
new (&data[block][index]) T(std::forward<Args>(args)...);
|
|
}
|
|
|
|
++_size;
|
|
}
|
|
|
|
/*!
|
|
* \brief Removes an element from the back of the deque
|
|
*/
|
|
void pop_back() {
|
|
auto block = (last_element) / block_elements;
|
|
auto index = (last_element) % block_elements;
|
|
data[block][index].~value_type();
|
|
|
|
--_size;
|
|
--last_element;
|
|
|
|
if (!_size) {
|
|
first_element = last_element = 0;
|
|
}
|
|
}
|
|
|
|
/*!
|
|
* \brief Removes an element from the front of the deque
|
|
*/
|
|
void pop_front() {
|
|
auto block = (first_element) / block_elements;
|
|
auto index = (first_element) % block_elements;
|
|
data[block][index].~value_type();
|
|
|
|
--_size;
|
|
++first_element;
|
|
|
|
if (!_size) {
|
|
first_element = last_element = 0;
|
|
}
|
|
}
|
|
|
|
/*!
|
|
* \brief Erase the element at the given position
|
|
*/
|
|
void erase(size_t position) {
|
|
for (size_t i = position; i < _size - 1; ++i) {
|
|
(*this)[i] = std::move((*this)[i + 1]);
|
|
}
|
|
|
|
auto block = (last_element) / block_elements;
|
|
auto index = (last_element) % block_elements;
|
|
data[block][index].~value_type();
|
|
|
|
--last_element;
|
|
--_size;
|
|
}
|
|
|
|
/*!
|
|
* \brief Erase the element at the given position
|
|
*/
|
|
iterator erase(iterator position) {
|
|
erase(position.index);
|
|
|
|
return position;
|
|
}
|
|
|
|
/*!
|
|
* \brief Erase all the elements of the given range
|
|
*/
|
|
void erase(iterator first, iterator last) {
|
|
auto n = last - first;
|
|
|
|
for (size_t i = first.index; i < _size - n; ++i) {
|
|
(*this)[i] = std::move((*this)[i + n]);
|
|
}
|
|
|
|
for (size_t i = _size - n; i < _size; ++i) {
|
|
(*this)[i].~value_type();
|
|
}
|
|
|
|
_size -= n;
|
|
last_element -= n;
|
|
}
|
|
|
|
/*!
|
|
* \brief Removes all the elements of the deque
|
|
*/
|
|
void clear() {
|
|
destruct_all();
|
|
|
|
first_element = 0;
|
|
last_element = 0;
|
|
|
|
_size = 0;
|
|
}
|
|
|
|
/*!
|
|
* \brief Returns the size of the deque
|
|
*/
|
|
size_t size() const {
|
|
return _size;
|
|
}
|
|
|
|
/*!
|
|
* \brief Returns the current maximum size of the deque
|
|
*/
|
|
size_t max_size() const {
|
|
return blocks * block_elements;
|
|
}
|
|
|
|
/*!
|
|
* \brief Retuns a reference to the element at position i
|
|
*/
|
|
reference_type operator[](size_t i) {
|
|
auto block = (i + first_element) / block_elements;
|
|
auto index = (i + first_element) % block_elements;
|
|
return data[block][index];
|
|
}
|
|
|
|
/*!
|
|
* \brief Retuns a reference to the element at position i
|
|
*/
|
|
const_reference_type operator[](size_t i) const {
|
|
auto block = (i + first_element) / block_elements;
|
|
auto index = (i + first_element) % block_elements;
|
|
return data[block][index];
|
|
}
|
|
|
|
/*!
|
|
* \brief Returns a reference to the back element of the deque
|
|
*/
|
|
reference_type back() {
|
|
auto block = (last_element) / block_elements;
|
|
auto index = (last_element) % block_elements;
|
|
return data[block][index];
|
|
}
|
|
|
|
/*!
|
|
* \brief Returns a reference to the back element of the deque
|
|
*/
|
|
const_reference_type back() const {
|
|
auto block = (last_element) / block_elements;
|
|
auto index = (last_element) % block_elements;
|
|
return data[block][index];
|
|
}
|
|
|
|
/*!
|
|
* \brief Returns a reference to the front element of the deque
|
|
*/
|
|
reference_type front() {
|
|
auto block = (first_element) / block_elements;
|
|
auto index = (first_element) % block_elements;
|
|
return data[block][index];
|
|
}
|
|
|
|
/*!
|
|
* \brief Returns a reference to the front element of the deque
|
|
*/
|
|
const_reference_type front() const {
|
|
auto block = (first_element) / block_elements;
|
|
auto index = (first_element) % block_elements;
|
|
return data[block][index];
|
|
}
|
|
|
|
//Iterators
|
|
|
|
/*!
|
|
* \brief Return an iterator to point to the first element
|
|
*/
|
|
iterator begin() {
|
|
return iterator(this, 0);
|
|
}
|
|
|
|
/*!
|
|
* \brief Return an iterator to point to the first element
|
|
*/
|
|
constexpr const_iterator begin() const {
|
|
return const_iterator(this, 0);
|
|
}
|
|
|
|
/*!
|
|
* \brief Return an iterator to point to the past-the-end element
|
|
*/
|
|
iterator end() {
|
|
return iterator(this, _size);
|
|
}
|
|
|
|
/*!
|
|
* \brief Return an iterator to point to the past-the-end element
|
|
*/
|
|
constexpr const_iterator end() const {
|
|
return const_iterator(this, _size);
|
|
}
|
|
|
|
//Iterators
|
|
|
|
/*!
|
|
* \brief Return a reverse iterator to point to the first element
|
|
*/
|
|
reverse_iterator rbegin() {
|
|
return reverse_iterator(iterator(this, _size - 1));
|
|
}
|
|
|
|
/*!
|
|
* \brief Return a reverse iterator to point to the first element
|
|
*/
|
|
constexpr const_reverse_iterator rbegin() const {
|
|
return const_iterator(const_iterator(this, _size - 1));
|
|
}
|
|
|
|
/*!
|
|
* \brief Return a reverse iterator point to the past-the-end element
|
|
*/
|
|
reverse_iterator rend() {
|
|
return reverse_iterator(iterator(this, -1));
|
|
}
|
|
|
|
/*!
|
|
* \brief Return a reverse iterator point to the past-the-end element
|
|
*/
|
|
constexpr const_reverse_iterator rend() const {
|
|
return const_reverse_iterator(const_iterator(this, -1));
|
|
}
|
|
|
|
private:
|
|
static value_type* allocate(size_t n){
|
|
return reinterpret_cast<value_type*>(new char[n * sizeof(value_type)]);
|
|
}
|
|
|
|
static void deallocate(value_type* ptr){
|
|
delete[] reinterpret_cast<char*>(ptr);
|
|
}
|
|
|
|
void ensure_capacity_front(size_t n) {
|
|
auto capacity_front = first_element;
|
|
|
|
if (capacity_front < n) {
|
|
if (!data) {
|
|
blocks = n % block_elements == 0 ? n / block_elements : (n / block_elements) + 1;
|
|
|
|
data = new T*[blocks];
|
|
|
|
for (size_t i = 0; i < blocks; ++i) {
|
|
data[i] = allocate(block_elements);
|
|
}
|
|
|
|
first_element = blocks * block_elements - 1;
|
|
last_element = blocks * block_elements - 1;
|
|
} else {
|
|
auto expand_front = n - capacity_front;
|
|
auto new_blocks = expand_front % block_elements == 0 ? expand_front / block_elements : (expand_front / block_elements) + 1;
|
|
|
|
auto new_data = new T*[blocks + new_blocks];
|
|
|
|
for (size_t i = 0; i < blocks; ++i) {
|
|
new_data[i + new_blocks] = data[i];
|
|
}
|
|
|
|
for (size_t i = 0; i < new_blocks; ++i) {
|
|
new_data[i] = allocate(block_elements);
|
|
}
|
|
|
|
first_element += new_blocks * block_elements;
|
|
last_element += new_blocks * block_elements;
|
|
|
|
delete[] data;
|
|
data = new_data;
|
|
blocks += new_blocks;
|
|
}
|
|
}
|
|
}
|
|
|
|
void ensure_capacity_back(size_t n) {
|
|
auto very_last_element = blocks ? blocks * block_elements - 1 : 0;
|
|
auto capacity_back = very_last_element - last_element;
|
|
|
|
if (capacity_back < n) {
|
|
if (!data) {
|
|
blocks = n % block_elements == 0 ? n / block_elements : (n / block_elements) + 1;
|
|
|
|
data = new T*[blocks];
|
|
|
|
for (size_t i = 0; i < blocks; ++i) {
|
|
data[i] = allocate(block_elements);
|
|
}
|
|
|
|
first_element = 0;
|
|
last_element = 0;
|
|
} else {
|
|
auto expand_back = n - capacity_back;
|
|
auto new_blocks = expand_back % block_elements == 0 ? expand_back / block_elements : (expand_back / block_elements) + 1;
|
|
|
|
auto new_data = new T*[blocks + new_blocks];
|
|
|
|
for (size_t i = 0; i < blocks; ++i) {
|
|
new_data[i] = data[i];
|
|
}
|
|
|
|
for (size_t i = blocks; i < blocks + new_blocks; ++i) {
|
|
new_data[i] = allocate(block_elements);
|
|
}
|
|
|
|
delete[] data;
|
|
data = new_data;
|
|
blocks += new_blocks;
|
|
}
|
|
}
|
|
}
|
|
|
|
T** data;
|
|
size_t first_element;
|
|
size_t last_element;
|
|
size_t blocks;
|
|
size_t _size;
|
|
};
|
|
|
|
} //end of namespace std
|
|
|
|
#endif
|