Changeset View
Changeset View
Standalone View
Standalone View
src/prevector.h
// Copyright (c) 2015-2016 The Bitcoin Core developers | // Copyright (c) 2015-2016 The Bitcoin Core developers | ||||
// Distributed under the MIT software license, see the accompanying | // Distributed under the MIT software license, see the accompanying | ||||
// file COPYING or http://www.opensource.org/licenses/mit-license.php. | // file COPYING or http://www.opensource.org/licenses/mit-license.php. | ||||
#ifndef BITCOIN_PREVECTOR_H | #ifndef BITCOIN_PREVECTOR_H | ||||
#define BITCOIN_PREVECTOR_H | #define BITCOIN_PREVECTOR_H | ||||
#include <cassert> | #include <cassert> | ||||
#include <cstdint> | #include <cstdint> | ||||
#include <cstdlib> | #include <cstdlib> | ||||
#include <cstring> | #include <cstring> | ||||
#include <cstddef> | |||||
#include <iterator> | #include <iterator> | ||||
#include <type_traits> | #include <type_traits> | ||||
#include <compat.h> | |||||
#pragma pack(push, 1) | #pragma pack(push, 1) | ||||
/** | /** | ||||
* Implements a drop-in replacement for std::vector<T> which stores up to N | * Implements a drop-in replacement for std::vector<T> which stores up to N | ||||
* elements directly (without heap allocation). The types Size and Diff are used | * elements directly (without heap allocation). The types Size and Diff are used | ||||
* to store element counts, and can be any unsigned + signed type. | * to store element counts, and can be any unsigned + signed type. | ||||
* | * | ||||
* Storage layout is either: | * Storage layout is either: | ||||
* - Direct allocation: | * - Direct allocation: | ||||
▲ Show 20 Lines • Show All 267 Lines • ▼ Show 20 Lines | private: | ||||
T *item_ptr(difference_type pos) { | T *item_ptr(difference_type pos) { | ||||
return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); | return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); | ||||
} | } | ||||
const T *item_ptr(difference_type pos) const { | const T *item_ptr(difference_type pos) const { | ||||
return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); | return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); | ||||
} | } | ||||
void fill(T *dst, ptrdiff_t count) { | |||||
if (IS_TRIVIALLY_CONSTRUCTIBLE<T>::value) { | |||||
// The most common use of prevector is where T=unsigned char. For | |||||
// trivially constructible types, we can use memset() to avoid | |||||
// looping. | |||||
::memset(dst, 0, count * sizeof(T)); | |||||
} else { | |||||
for (auto i = 0; i < count; ++i) { | |||||
new (static_cast<void *>(dst + i)) T(); | |||||
} | |||||
} | |||||
} | |||||
void fill(T *dst, ptrdiff_t count, const T &value) { | |||||
for (auto i = 0; i < count; ++i) { | |||||
new (static_cast<void *>(dst + i)) T(value); | |||||
} | |||||
} | |||||
template <typename InputIterator> | |||||
void fill(T *dst, InputIterator first, InputIterator last) { | |||||
while (first != last) { | |||||
new (static_cast<void *>(dst)) T(*first); | |||||
++dst; | |||||
++first; | |||||
} | |||||
} | |||||
public: | public: | ||||
void assign(size_type n, const T &val) { | void assign(size_type n, const T &val) { | ||||
clear(); | clear(); | ||||
if (capacity() < n) { | if (capacity() < n) { | ||||
change_capacity(n); | change_capacity(n); | ||||
} | } | ||||
while (size() < n) { | _size += n; | ||||
_size++; | fill(item_ptr(0), n, val); | ||||
new (static_cast<void *>(item_ptr(size() - 1))) T(val); | |||||
} | |||||
} | } | ||||
template <typename InputIterator> | template <typename InputIterator> | ||||
void assign(InputIterator first, InputIterator last) { | void assign(InputIterator first, InputIterator last) { | ||||
size_type n = last - first; | size_type n = last - first; | ||||
clear(); | clear(); | ||||
if (capacity() < n) { | if (capacity() < n) { | ||||
change_capacity(n); | change_capacity(n); | ||||
} | } | ||||
while (first != last) { | _size += n; | ||||
_size++; | fill(item_ptr(0), first, last); | ||||
new (static_cast<void *>(item_ptr(size() - 1))) T(*first); | |||||
++first; | |||||
} | |||||
} | } | ||||
prevector() : _size(0), _union{{}} {} | prevector() : _size(0), _union{{}} {} | ||||
explicit prevector(size_type n) : prevector() { resize(n); } | explicit prevector(size_type n) : prevector() { resize(n); } | ||||
explicit prevector(size_type n, const T &val) : prevector() { | explicit prevector(size_type n, const T &val) : prevector() { | ||||
change_capacity(n); | change_capacity(n); | ||||
while (size() < n) { | _size += n; | ||||
_size++; | fill(item_ptr(0), n, val); | ||||
new (static_cast<void *>(item_ptr(size() - 1))) T(val); | |||||
} | |||||
} | } | ||||
template <typename InputIterator> | template <typename InputIterator> | ||||
prevector(InputIterator first, InputIterator last) : prevector() { | prevector(InputIterator first, InputIterator last) : prevector() { | ||||
size_type n = last - first; | size_type n = last - first; | ||||
change_capacity(n); | change_capacity(n); | ||||
while (first != last) { | _size += n; | ||||
_size++; | fill(item_ptr(0), first, last); | ||||
new (static_cast<void *>(item_ptr(size() - 1))) T(*first); | |||||
++first; | |||||
} | |||||
} | } | ||||
prevector(const prevector<N, T, Size, Diff> &other) : prevector() { | prevector(const prevector<N, T, Size, Diff> &other) : prevector() { | ||||
change_capacity(other.size()); | size_type n = other.size(); | ||||
const_iterator it = other.begin(); | change_capacity(n); | ||||
while (it != other.end()) { | _size += n; | ||||
_size++; | fill(item_ptr(0), other.begin(), other.end()); | ||||
new (static_cast<void *>(item_ptr(size() - 1))) T(*it); | |||||
++it; | |||||
} | |||||
} | } | ||||
prevector(prevector<N, T, Size, Diff> &&other) : prevector() { | prevector(prevector<N, T, Size, Diff> &&other) : prevector() { | ||||
swap(other); | swap(other); | ||||
} | } | ||||
prevector &operator=(const prevector<N, T, Size, Diff> &other) { | prevector &operator=(const prevector<N, T, Size, Diff> &other) { | ||||
if (&other == this) { | if (&other == this) { | ||||
return *this; | return *this; | ||||
} | } | ||||
resize(0); | assign(other.begin(), other.end()); | ||||
change_capacity(other.size()); | |||||
const_iterator it = other.begin(); | |||||
while (it != other.end()) { | |||||
_size++; | |||||
new (static_cast<void *>(item_ptr(size() - 1))) T(*it); | |||||
++it; | |||||
} | |||||
return *this; | return *this; | ||||
} | } | ||||
prevector &operator=(prevector<N, T, Size, Diff> &&other) { | prevector &operator=(prevector<N, T, Size, Diff> &&other) { | ||||
swap(other); | swap(other); | ||||
return *this; | return *this; | ||||
} | } | ||||
Show All 23 Lines | size_t capacity() const { | ||||
} | } | ||||
} | } | ||||
T &operator[](size_type pos) { return *item_ptr(pos); } | T &operator[](size_type pos) { return *item_ptr(pos); } | ||||
const T &operator[](size_type pos) const { return *item_ptr(pos); } | const T &operator[](size_type pos) const { return *item_ptr(pos); } | ||||
void resize(size_type new_size) { | void resize(size_type new_size) { | ||||
if (size() > new_size) { | size_type cur_size = size(); | ||||
if (cur_size == new_size) { | |||||
return; | |||||
} | |||||
if (cur_size > new_size) { | |||||
erase(item_ptr(new_size), end()); | erase(item_ptr(new_size), end()); | ||||
return; | |||||
} | } | ||||
if (new_size > capacity()) { | if (new_size > capacity()) { | ||||
change_capacity(new_size); | change_capacity(new_size); | ||||
} | } | ||||
while (size() < new_size) { | ptrdiff_t increase = new_size - cur_size; | ||||
_size++; | fill(item_ptr(cur_size), increase); | ||||
new (static_cast<void *>(item_ptr(size() - 1))) T(); | _size += increase; | ||||
} | |||||
} | } | ||||
void reserve(size_type new_capacity) { | void reserve(size_type new_capacity) { | ||||
if (new_capacity > capacity()) { | if (new_capacity > capacity()) { | ||||
change_capacity(new_capacity); | change_capacity(new_capacity); | ||||
} | } | ||||
} | } | ||||
void shrink_to_fit() { change_capacity(size()); } | void shrink_to_fit() { change_capacity(size()); } | ||||
void clear() { resize(0); } | void clear() { resize(0); } | ||||
iterator insert(iterator pos, const T &value) { | iterator insert(iterator pos, const T &value) { | ||||
size_type p = pos - begin(); | size_type p = pos - begin(); | ||||
size_type new_size = size() + 1; | size_type new_size = size() + 1; | ||||
if (capacity() < new_size) { | if (capacity() < new_size) { | ||||
change_capacity(new_size + (new_size >> 1)); | change_capacity(new_size + (new_size >> 1)); | ||||
} | } | ||||
memmove(item_ptr(p + 1), item_ptr(p), (size() - p) * sizeof(T)); | T *ptr = item_ptr(p); | ||||
memmove(ptr + 1, ptr, (size() - p) * sizeof(T)); | |||||
_size++; | _size++; | ||||
new (static_cast<void *>(item_ptr(p))) T(value); | new (static_cast<void *>(ptr)) T(value); | ||||
return iterator(item_ptr(p)); | return iterator(ptr); | ||||
} | } | ||||
void insert(iterator pos, size_type count, const T &value) { | void insert(iterator pos, size_type count, const T &value) { | ||||
size_type p = pos - begin(); | size_type p = pos - begin(); | ||||
size_type new_size = size() + count; | size_type new_size = size() + count; | ||||
if (capacity() < new_size) { | if (capacity() < new_size) { | ||||
change_capacity(new_size + (new_size >> 1)); | change_capacity(new_size + (new_size >> 1)); | ||||
} | } | ||||
memmove(item_ptr(p + count), item_ptr(p), (size() - p) * sizeof(T)); | T *ptr = item_ptr(p); | ||||
memmove(ptr + count, ptr, (size() - p) * sizeof(T)); | |||||
_size += count; | _size += count; | ||||
for (size_type i = 0; i < count; i++) { | fill(item_ptr(p), count, value); | ||||
new (static_cast<void *>(item_ptr(p + i))) T(value); | |||||
} | |||||
} | } | ||||
template <typename InputIterator> | template <typename InputIterator> | ||||
void insert(iterator pos, InputIterator first, InputIterator last) { | void insert(iterator pos, InputIterator first, InputIterator last) { | ||||
size_type p = pos - begin(); | size_type p = pos - begin(); | ||||
difference_type count = last - first; | difference_type count = last - first; | ||||
size_type new_size = size() + count; | size_type new_size = size() + count; | ||||
if (capacity() < new_size) { | if (capacity() < new_size) { | ||||
change_capacity(new_size + (new_size >> 1)); | change_capacity(new_size + (new_size >> 1)); | ||||
} | } | ||||
memmove(item_ptr(p + count), item_ptr(p), (size() - p) * sizeof(T)); | T *ptr = item_ptr(p); | ||||
memmove(ptr + count, ptr, (size() - p) * sizeof(T)); | |||||
_size += count; | _size += count; | ||||
while (first != last) { | fill(ptr, first, last); | ||||
new (static_cast<void *>(item_ptr(p))) T(*first); | |||||
++p; | |||||
++first; | |||||
} | |||||
} | } | ||||
iterator erase(iterator pos) { return erase(pos, pos + 1); } | iterator erase(iterator pos) { return erase(pos, pos + 1); } | ||||
iterator erase(iterator first, iterator last) { | iterator erase(iterator first, iterator last) { | ||||
// Erase is not allowed to the change the object's capacity. That means | // Erase is not allowed to the change the object's capacity. That means | ||||
// that when starting with an indirectly allocated prevector with | // that when starting with an indirectly allocated prevector with | ||||
// size and capacity > N, the result may be a still indirectly allocated | // size and capacity > N, the result may be a still indirectly allocated | ||||
▲ Show 20 Lines • Show All 111 Lines • Show Last 20 Lines |