diff options
Diffstat (limited to 'src/prevector.h')
| -rw-r--r-- | src/prevector.h | 174 |
1 files changed, 111 insertions, 63 deletions
diff --git a/src/prevector.h b/src/prevector.h index a0e1e140b4..033952c959 100644 --- a/src/prevector.h +++ b/src/prevector.h @@ -1,15 +1,20 @@ -// Copyright (c) 2015 The Bitcoin Core developers +// Copyright (c) 2015-2018 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. -#ifndef _BITCOIN_PREVECTOR_H_ -#define _BITCOIN_PREVECTOR_H_ +#ifndef BITCOIN_PREVECTOR_H +#define BITCOIN_PREVECTOR_H +#include <assert.h> #include <stdlib.h> #include <stdint.h> #include <string.h> +#include <cstddef> #include <iterator> +#include <type_traits> + +#include <compat.h> #pragma pack(push, 1) /** Implements a drop-in replacement for std::vector<T> which stores up to N @@ -130,7 +135,7 @@ public: typedef const T* pointer; typedef const T& reference; typedef std::bidirectional_iterator_tag iterator_category; - const_reverse_iterator(T* ptr_) : ptr(ptr_) {} + const_reverse_iterator(const T* ptr_) : ptr(ptr_) {} const_reverse_iterator(reverse_iterator x) : ptr(&(*x)) {} const T& operator*() const { return *ptr; } const T* operator->() const { return ptr; } @@ -170,10 +175,15 @@ private: } } else { if (!is_direct()) { + /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert + success. These should instead use an allocator or new/delete so that handlers + are called as necessary, but performance would be slightly degraded by doing so. */ _union.indirect = static_cast<char*>(realloc(_union.indirect, ((size_t)sizeof(T)) * new_capacity)); + assert(_union.indirect); _union.capacity = new_capacity; } else { char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity)); + assert(new_indirect); T* src = direct_ptr(0); T* dst = reinterpret_cast<T*>(new_indirect); memcpy(dst, src, size() * sizeof(T)); @@ -187,16 +197,42 @@ private: T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); } const T* item_ptr(difference_type pos) const { 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: void assign(size_type n, const T& val) { clear(); if (capacity() < n) { change_capacity(n); } - while (size() < n) { - _size++; - new(static_cast<void*>(item_ptr(size() - 1))) T(val); - } + _size += n; + fill(item_ptr(0), n, val); } template<typename InputIterator> @@ -206,14 +242,11 @@ public: if (capacity() < n) { change_capacity(n); } - while (first != last) { - _size++; - new(static_cast<void*>(item_ptr(size() - 1))) T(*first); - ++first; - } + _size += n; + fill(item_ptr(0), first, last); } - prevector() : _size(0) {} + prevector() : _size(0), _union{{}} {} explicit prevector(size_type n) : _size(0) { resize(n); @@ -221,45 +254,39 @@ public: explicit prevector(size_type n, const T& val = T()) : _size(0) { change_capacity(n); - while (size() < n) { - _size++; - new(static_cast<void*>(item_ptr(size() - 1))) T(val); - } + _size += n; + fill(item_ptr(0), n, val); } template<typename InputIterator> prevector(InputIterator first, InputIterator last) : _size(0) { size_type n = last - first; change_capacity(n); - while (first != last) { - _size++; - new(static_cast<void*>(item_ptr(size() - 1))) T(*first); - ++first; - } + _size += n; + fill(item_ptr(0), first, last); } prevector(const prevector<N, T, Size, Diff>& other) : _size(0) { - 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; - } + size_type n = other.size(); + change_capacity(n); + _size += n; + fill(item_ptr(0), other.begin(), other.end()); + } + + prevector(prevector<N, T, Size, Diff>&& other) : _size(0) { + swap(other); } prevector& operator=(const prevector<N, T, Size, Diff>& other) { if (&other == this) { return *this; } - resize(0); - 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; - } + assign(other.begin(), other.end()); + return *this; + } + + prevector& operator=(prevector<N, T, Size, Diff>&& other) { + swap(other); return *this; } @@ -298,16 +325,20 @@ public: } 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()); + return; } if (new_size > capacity()) { change_capacity(new_size); } - while (size() < new_size) { - _size++; - new(static_cast<void*>(item_ptr(size() - 1))) T(); - } + ptrdiff_t increase = new_size - cur_size; + fill(item_ptr(cur_size), increase); + _size += increase; } void reserve(size_type new_capacity) { @@ -330,10 +361,11 @@ public: if (capacity() < new_size) { 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++; - new(static_cast<void*>(item_ptr(p))) T(value); - return iterator(item_ptr(p)); + new(static_cast<void*>(ptr)) T(value); + return iterator(ptr); } void insert(iterator pos, size_type count, const T& value) { @@ -342,11 +374,10 @@ public: if (capacity() < new_size) { 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; - for (size_type i = 0; i < count; i++) { - new(static_cast<void*>(item_ptr(p + i))) T(value); - } + fill(item_ptr(p), count, value); } template<typename InputIterator> @@ -357,13 +388,10 @@ public: if (capacity() < new_size) { 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; - while (first != last) { - new(static_cast<void*>(item_ptr(p))) T(*first); - ++p; - ++first; - } + fill(ptr, first, last); } iterator erase(iterator pos) { @@ -371,12 +399,22 @@ public: } iterator erase(iterator first, iterator last) { + // Erase is not allowed to the change the object's capacity. That means + // that when starting with an indirectly allocated prevector with + // size and capacity > N, the result may be a still indirectly allocated + // prevector with size <= N and capacity > N. A shrink_to_fit() call is + // necessary to switch to the (more efficient) directly allocated + // representation (with capacity N and size <= N). iterator p = first; char* endp = (char*)&(*end()); - while (p != last) { - (*p).~T(); - _size--; - ++p; + if (!std::is_trivially_destructible<T>::value) { + while (p != last) { + (*p).~T(); + _size--; + ++p; + } + } else { + _size -= last - p; } memmove(&(*first), &(*last), endp - ((char*)(&(*last)))); return first; @@ -417,10 +455,12 @@ public: } ~prevector() { - clear(); + if (!std::is_trivially_destructible<T>::value) { + clear(); + } if (!is_direct()) { free(_union.indirect); - _union.indirect = NULL; + _union.indirect = nullptr; } } @@ -475,7 +515,15 @@ public: return ((size_t)(sizeof(T))) * _union.capacity; } } + + value_type* data() { + return item_ptr(0); + } + + const value_type* data() const { + return item_ptr(0); + } }; #pragma pack(pop) -#endif +#endif // BITCOIN_PREVECTOR_H |