diff --git a/src/Makefile.bench.include b/src/Makefile.bench.include index 6ebf4ac8c..4b1fb98e1 100644 --- a/src/Makefile.bench.include +++ b/src/Makefile.bench.include @@ -1,80 +1,80 @@ # Copyright (c) 2015-2016 The Bitcoin Core developers # Distributed under the MIT software license, see the accompanying # file COPYING or http://www.opensource.org/licenses/mit-license.php. bin_PROGRAMS += bench/bench_bitcoin BENCH_SRCDIR = bench BENCH_BINARY = bench/bench_bitcoin$(EXEEXT) RAW_TEST_FILES = \ bench/data/block413567.raw GENERATED_TEST_FILES = $(RAW_TEST_FILES:.raw=.raw.h) bench_bench_bitcoin_SOURCES = \ bench/bench_bitcoin.cpp \ bench/bench.cpp \ bench/bench.h \ bench/cashaddr.cpp \ bench/checkblock.cpp \ bench/checkqueue.cpp \ bench/Examples.cpp \ bench/rollingbloom.cpp \ bench/crypto_hash.cpp \ bench/ccoins_caching.cpp \ bench/mempool_eviction.cpp \ bench/base58.cpp \ bench/lockedpool.cpp \ bench/perf.cpp \ bench/perf.h \ - bench/prevector_destructor.cpp + bench/prevector.cpp nodist_bench_bench_bitcoin_SOURCES = $(GENERATED_TEST_FILES) bench_bench_bitcoin_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) $(EVENT_CLFAGS) $(EVENT_PTHREADS_CFLAGS) -I$(builddir)/bench/ bench_bench_bitcoin_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) bench_bench_bitcoin_LDADD = \ $(LIBBITCOIN_SERVER) \ $(LIBBITCOIN_COMMON) \ $(LIBBITCOIN_UTIL) \ $(LIBBITCOIN_CONSENSUS) \ $(LIBBITCOIN_CRYPTO) \ $(LIBLEVELDB) \ $(LIBLEVELDB_SSE42) \ $(LIBMEMENV) \ $(LIBSECP256K1) \ $(LIBUNIVALUE) if ENABLE_ZMQ bench_bench_bitcoin_LDADD += $(LIBBITCOIN_ZMQ) $(ZMQ_LIBS) endif if ENABLE_WALLET bench_bench_bitcoin_SOURCES += bench/coin_selection.cpp bench_bench_bitcoin_LDADD += $(LIBBITCOIN_WALLET) $(LIBBITCOIN_CRYPTO) endif bench_bench_bitcoin_LDADD += $(BOOST_LIBS) $(BDB_LIBS) $(SSL_LIBS) $(CRYPTO_LIBS) $(MINIUPNPC_LIBS) $(EVENT_PTHREADS_LIBS) $(EVENT_LIBS) bench_bench_bitcoin_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) CLEAN_BITCOIN_BENCH = bench/*.gcda bench/*.gcno $(GENERATED_TEST_FILES) CLEANFILES += $(CLEAN_BITCOIN_BENCH) bench/checkblock.cpp: bench/data/block413567.raw.h bitcoin_bench: $(BENCH_BINARY) bench: $(BENCH_BINARY) FORCE $(BENCH_BINARY) bitcoin_bench_clean : FORCE rm -f $(CLEAN_BITCOIN_BENCH) $(bench_bench_bitcoin_OBJECTS) $(BENCH_BINARY) %.raw.h: %.raw @$(MKDIR_P) $(@D) @{ \ echo "static unsigned const char $(*F)[] = {" && \ $(HEXDUMP) -v -e '8/1 "0x%02x, "' -e '"\n"' $< | $(SED) -e 's/0x ,//g' && \ echo "};"; \ } > "$@.new" && mv -f "$@.new" "$@" @echo "Generated $@" diff --git a/src/bench/prevector.cpp b/src/bench/prevector.cpp new file mode 100644 index 000000000..f014821ed --- /dev/null +++ b/src/bench/prevector.cpp @@ -0,0 +1,70 @@ +// Copyright (c) 2015-2017 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include +#include + +#include + +struct nontrivial_t { + int x; + nontrivial_t() : x(-1) {} +}; +static_assert(!IS_TRIVIALLY_CONSTRUCTIBLE::value, + "expected nontrivial_t to not be trivially constructible"); + +typedef unsigned char trivial_t; +static_assert(IS_TRIVIALLY_CONSTRUCTIBLE::value, + "expected trivial_t to be trivially constructible"); + +template static void PrevectorDestructor(benchmark::State &state) { + while (state.KeepRunning()) { + for (auto x = 0; x < 1000; ++x) { + prevector<28, T> t0; + prevector<28, T> t1; + t0.resize(28); + t1.resize(29); + } + } +} + +template static void PrevectorClear(benchmark::State &state) { + while (state.KeepRunning()) { + for (auto x = 0; x < 1000; ++x) { + prevector<28, T> t0; + prevector<28, T> t1; + t0.resize(28); + t0.clear(); + t1.resize(29); + t1.clear(); + } + } +} + +template void PrevectorResize(benchmark::State &state) { + while (state.KeepRunning()) { + prevector<28, T> t0; + prevector<28, T> t1; + for (auto x = 0; x < 1000; ++x) { + t0.resize(28); + t0.resize(0); + t1.resize(29); + t1.resize(0); + } + } +} + +#define PREVECTOR_TEST(name, nontrivops, trivops) \ + static void Prevector##name##Nontrivial(benchmark::State &state) { \ + Prevector##name(state); \ + } \ + BENCHMARK(Prevector##name##Nontrivial, nontrivops); \ + static void Prevector##name##Trivial(benchmark::State &state) { \ + Prevector##name(state); \ + } \ + BENCHMARK(Prevector##name##Trivial, trivops); + +PREVECTOR_TEST(Clear, 28300, 88600) +PREVECTOR_TEST(Destructor, 28800, 88900) +PREVECTOR_TEST(Resize, 28900, 90300) diff --git a/src/bench/prevector_destructor.cpp b/src/bench/prevector_destructor.cpp deleted file mode 100644 index b3c241e14..000000000 --- a/src/bench/prevector_destructor.cpp +++ /dev/null @@ -1,33 +0,0 @@ -// Copyright (c) 2015-2017 The Bitcoin Core developers -// Distributed under the MIT software license, see the accompanying -// file COPYING or http://www.opensource.org/licenses/mit-license.php. - -#include "bench.h" -#include "prevector.h" - -static void PrevectorDestructor(benchmark::State &state) { - while (state.KeepRunning()) { - for (auto x = 0; x < 1000; ++x) { - prevector<28, uint8_t> t0; - prevector<28, uint8_t> t1; - t0.resize(28); - t1.resize(29); - } - } -} - -static void PrevectorClear(benchmark::State &state) { - while (state.KeepRunning()) { - for (auto x = 0; x < 1000; ++x) { - prevector<28, uint8_t> t0; - prevector<28, uint8_t> t1; - t0.resize(28); - t0.clear(); - t1.resize(29); - t1.clear(); - } - } -} - -BENCHMARK(PrevectorDestructor, 5700); -BENCHMARK(PrevectorClear, 5600); diff --git a/src/compat.h b/src/compat.h index 62a9e3926..bf091de77 100644 --- a/src/compat.h +++ b/src/compat.h @@ -1,87 +1,97 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 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_COMPAT_H #define BITCOIN_COMPAT_H #if defined(HAVE_CONFIG_H) #include "config/bitcoin-config.h" #endif +#include + +// GCC 4.8 is missing some C++11 type_traits, +// https://www.gnu.org/software/gcc/gcc-5/changes.html +#if defined(__GNUC__) && __GNUC__ < 5 +#define IS_TRIVIALLY_CONSTRUCTIBLE std::is_trivial +#else +#define IS_TRIVIALLY_CONSTRUCTIBLE std::is_trivially_constructible +#endif + #ifdef WIN32 #ifdef _WIN32_WINNT #undef _WIN32_WINNT #endif #define _WIN32_WINNT 0x0501 #ifndef WIN32_LEAN_AND_MEAN #define WIN32_LEAN_AND_MEAN 1 #endif #ifndef NOMINMAX #define NOMINMAX #endif #ifdef FD_SETSIZE #undef FD_SETSIZE // prevent redefinition compiler warning #endif #define FD_SETSIZE 1024 // max number of fds in fd_set #include // Must be included before mswsock.h and windows.h #include #include #include #else #include #include #include #include #include #include #include #include #include #include #include #include #include #endif #ifndef WIN32 typedef unsigned int SOCKET; #include "errno.h" #define WSAGetLastError() errno #define WSAEINVAL EINVAL #define WSAEALREADY EALREADY #define WSAEWOULDBLOCK EWOULDBLOCK #define WSAEMSGSIZE EMSGSIZE #define WSAEINTR EINTR #define WSAEINPROGRESS EINPROGRESS #define WSAEADDRINUSE EADDRINUSE #define WSAENOTSOCK EBADF #define INVALID_SOCKET (SOCKET)(~0) #define SOCKET_ERROR -1 #endif #ifdef WIN32 #ifndef S_IRUSR #define S_IRUSR 0400 #define S_IWUSR 0200 #endif #else #define MAX_PATH 1024 #endif #if HAVE_DECL_STRNLEN == 0 size_t strnlen(const char *start, size_t max_len); #endif // HAVE_DECL_STRNLEN static bool inline IsSelectableSocket(SOCKET s) { #ifdef WIN32 return true; #else return (s < FD_SETSIZE); #endif } #endif // BITCOIN_COMPAT_H diff --git a/src/prevector.h b/src/prevector.h index 790981e43..f97d0c7f2 100644 --- a/src/prevector.h +++ b/src/prevector.h @@ -1,593 +1,605 @@ // Copyright (c) 2015-2016 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 #include #include #include #include +#include #include #include +#include + #pragma pack(push, 1) /** * Implements a drop-in replacement for std::vector which stores up to N * elements directly (without heap allocation). The types Size and Diff are used * to store element counts, and can be any unsigned + signed type. * * Storage layout is either: * - Direct allocation: * - Size _size: the number of used elements (between 0 and N) * - T direct[N]: an array of N elements of type T * (only the first _size are initialized). * - Indirect allocation: * - Size _size: the number of used elements plus N + 1 * - Size capacity: the number of allocated elements * - T* indirect: a pointer to an array of capacity elements of type T * (only the first _size are initialized). * * The data type T must be movable by memmove/realloc(). Once we switch to C++, * move constructors can be used instead. */ template class prevector { public: typedef Size size_type; typedef Diff difference_type; typedef T value_type; typedef value_type &reference; typedef const value_type &const_reference; typedef value_type *pointer; typedef const value_type *const_pointer; class iterator { T *ptr; public: typedef Diff difference_type; typedef T value_type; typedef T *pointer; typedef T &reference; typedef std::random_access_iterator_tag iterator_category; iterator() : ptr(nullptr) {} iterator(T *ptr_) : ptr(ptr_) {} T &operator*() const { return *ptr; } T *operator->() const { return ptr; } T &operator[](size_type pos) { return ptr[pos]; } const T &operator[](size_type pos) const { return ptr[pos]; } iterator &operator++() { ptr++; return *this; } iterator &operator--() { ptr--; return *this; } iterator operator++(int) { iterator copy(*this); ++(*this); return copy; } iterator operator--(int) { iterator copy(*this); --(*this); return copy; } difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); } iterator operator+(size_type n) { return iterator(ptr + n); } iterator &operator+=(size_type n) { ptr += n; return *this; } iterator operator-(size_type n) { return iterator(ptr - n); } iterator &operator-=(size_type n) { ptr -= n; return *this; } bool operator==(iterator x) const { return ptr == x.ptr; } bool operator!=(iterator x) const { return ptr != x.ptr; } bool operator>=(iterator x) const { return ptr >= x.ptr; } bool operator<=(iterator x) const { return ptr <= x.ptr; } bool operator>(iterator x) const { return ptr > x.ptr; } bool operator<(iterator x) const { return ptr < x.ptr; } }; class reverse_iterator { T *ptr; public: typedef Diff difference_type; typedef T value_type; typedef T *pointer; typedef T &reference; typedef std::bidirectional_iterator_tag iterator_category; reverse_iterator() : ptr(nullptr) {} reverse_iterator(T *ptr_) : ptr(ptr_) {} T &operator*() { return *ptr; } const T &operator*() const { return *ptr; } T *operator->() { return ptr; } const T *operator->() const { return ptr; } reverse_iterator &operator--() { ptr++; return *this; } reverse_iterator &operator++() { ptr--; return *this; } reverse_iterator operator++(int) { reverse_iterator copy(*this); ++(*this); return copy; } reverse_iterator operator--(int) { reverse_iterator copy(*this); --(*this); return copy; } bool operator==(reverse_iterator x) const { return ptr == x.ptr; } bool operator!=(reverse_iterator x) const { return ptr != x.ptr; } }; class const_iterator { const T *ptr; public: typedef Diff difference_type; typedef const T value_type; typedef const T *pointer; typedef const T &reference; typedef std::random_access_iterator_tag iterator_category; const_iterator() : ptr(nullptr) {} const_iterator(const T *ptr_) : ptr(ptr_) {} const_iterator(iterator x) : ptr(&(*x)) {} const T &operator*() const { return *ptr; } const T *operator->() const { return ptr; } const T &operator[](size_type pos) const { return ptr[pos]; } const_iterator &operator++() { ptr++; return *this; } const_iterator &operator--() { ptr--; return *this; } const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; } const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; } difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); } const_iterator operator+(size_type n) { return const_iterator(ptr + n); } const_iterator &operator+=(size_type n) { ptr += n; return *this; } const_iterator operator-(size_type n) { return const_iterator(ptr - n); } const_iterator &operator-=(size_type n) { ptr -= n; return *this; } bool operator==(const_iterator x) const { return ptr == x.ptr; } bool operator!=(const_iterator x) const { return ptr != x.ptr; } bool operator>=(const_iterator x) const { return ptr >= x.ptr; } bool operator<=(const_iterator x) const { return ptr <= x.ptr; } bool operator>(const_iterator x) const { return ptr > x.ptr; } bool operator<(const_iterator x) const { return ptr < x.ptr; } }; class const_reverse_iterator { const T *ptr; public: typedef Diff difference_type; typedef const T value_type; typedef const T *pointer; typedef const T &reference; typedef std::bidirectional_iterator_tag iterator_category; const_reverse_iterator() : ptr(nullptr) {} 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; } const_reverse_iterator &operator--() { ptr++; return *this; } const_reverse_iterator &operator++() { ptr--; return *this; } const_reverse_iterator operator++(int) { const_reverse_iterator copy(*this); ++(*this); return copy; } const_reverse_iterator operator--(int) { const_reverse_iterator copy(*this); --(*this); return copy; } bool operator==(const_reverse_iterator x) const { return ptr == x.ptr; } bool operator!=(const_reverse_iterator x) const { return ptr != x.ptr; } }; private: size_type _size; union direct_or_indirect { char direct[sizeof(T) * N]; struct { size_type capacity; char *indirect; }; } _union; T *direct_ptr(difference_type pos) { return reinterpret_cast(_union.direct) + pos; } const T *direct_ptr(difference_type pos) const { return reinterpret_cast(_union.direct) + pos; } T *indirect_ptr(difference_type pos) { return reinterpret_cast(_union.indirect) + pos; } const T *indirect_ptr(difference_type pos) const { return reinterpret_cast(_union.indirect) + pos; } bool is_direct() const { return _size <= N; } void change_capacity(size_type new_capacity) { if (new_capacity <= N) { if (!is_direct()) { T *indirect = indirect_ptr(0); T *src = indirect; T *dst = direct_ptr(0); memcpy(dst, src, size() * sizeof(T)); free(indirect); _size -= N + 1; } } 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(realloc( _union.indirect, ((size_t)sizeof(T)) * new_capacity)); assert(_union.indirect); _union.capacity = new_capacity; } else { char *new_indirect = static_cast( malloc(((size_t)sizeof(T)) * new_capacity)); assert(new_indirect); T *src = direct_ptr(0); T *dst = reinterpret_cast(new_indirect); memcpy(dst, src, size() * sizeof(T)); _union.indirect = new_indirect; _union.capacity = new_capacity; _size += N + 1; } } } 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::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(dst + i)) T(); + } + } + } + + void fill(T *dst, ptrdiff_t count, const T &value) { + for (auto i = 0; i < count; ++i) { + new (static_cast(dst + i)) T(value); + } + } + + template + void fill(T *dst, InputIterator first, InputIterator last) { + while (first != last) { + new (static_cast(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(item_ptr(size() - 1))) T(val); - } + _size += n; + fill(item_ptr(0), n, val); } template void assign(InputIterator first, InputIterator last) { size_type n = last - first; clear(); if (capacity() < n) { change_capacity(n); } - while (first != last) { - _size++; - new (static_cast(item_ptr(size() - 1))) T(*first); - ++first; - } + _size += n; + fill(item_ptr(0), first, last); } prevector() : _size(0), _union{{}} {} explicit prevector(size_type n) : prevector() { resize(n); } explicit prevector(size_type n, const T &val) : prevector() { change_capacity(n); - while (size() < n) { - _size++; - new (static_cast(item_ptr(size() - 1))) T(val); - } + _size += n; + fill(item_ptr(0), n, val); } template prevector(InputIterator first, InputIterator last) : prevector() { size_type n = last - first; change_capacity(n); - while (first != last) { - _size++; - new (static_cast(item_ptr(size() - 1))) T(*first); - ++first; - } + _size += n; + fill(item_ptr(0), first, last); } prevector(const prevector &other) : prevector() { - change_capacity(other.size()); - const_iterator it = other.begin(); - while (it != other.end()) { - _size++; - new (static_cast(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 &&other) : prevector() { swap(other); } prevector &operator=(const prevector &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(item_ptr(size() - 1))) T(*it); - ++it; - } + assign(other.begin(), other.end()); return *this; } prevector &operator=(prevector &&other) { swap(other); return *this; } size_type size() const { return is_direct() ? _size : _size - N - 1; } bool empty() const { return size() == 0; } iterator begin() { return iterator(item_ptr(0)); } const_iterator begin() const { return const_iterator(item_ptr(0)); } iterator end() { return iterator(item_ptr(size())); } const_iterator end() const { return const_iterator(item_ptr(size())); } reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); } const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); } reverse_iterator rend() { return reverse_iterator(item_ptr(-1)); } const_reverse_iterator rend() const { return const_reverse_iterator(item_ptr(-1)); } size_t capacity() const { if (is_direct()) { return N; } else { return _union.capacity; } } T &operator[](size_type pos) { return *item_ptr(pos); } const T &operator[](size_type pos) const { return *item_ptr(pos); } 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(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) { if (new_capacity > capacity()) { change_capacity(new_capacity); } } void shrink_to_fit() { change_capacity(size()); } void clear() { resize(0); } iterator insert(iterator pos, const T &value) { size_type p = pos - begin(); size_type new_size = size() + 1; 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(item_ptr(p))) T(value); - return iterator(item_ptr(p)); + new (static_cast(ptr)) T(value); + return iterator(ptr); } void insert(iterator pos, size_type count, const T &value) { size_type p = pos - begin(); size_type new_size = size() + count; 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(item_ptr(p + i))) T(value); - } + fill(item_ptr(p), count, value); } template void insert(iterator pos, InputIterator first, InputIterator last) { size_type p = pos - begin(); difference_type count = last - first; size_type new_size = size() + count; 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(item_ptr(p))) T(*first); - ++p; - ++first; - } + fill(ptr, first, last); } iterator erase(iterator pos) { return erase(pos, pos + 1); } 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()); if (!std::is_trivially_destructible::value) { while (p != last) { (*p).~T(); _size--; ++p; } } else { _size -= last - p; } memmove(&(*first), &(*last), endp - ((char *)(&(*last)))); return first; } void push_back(const T &value) { size_type new_size = size() + 1; if (capacity() < new_size) { change_capacity(new_size + (new_size >> 1)); } new (item_ptr(size())) T(value); _size++; } void pop_back() { erase(end() - 1, end()); } T &front() { return *item_ptr(0); } const T &front() const { return *item_ptr(0); } T &back() { return *item_ptr(size() - 1); } const T &back() const { return *item_ptr(size() - 1); } void swap(prevector &other) { std::swap(_union, other._union); std::swap(_size, other._size); } ~prevector() { if (!std::is_trivially_destructible::value) { clear(); } if (!is_direct()) { free(_union.indirect); _union.indirect = nullptr; } } bool operator==(const prevector &other) const { if (other.size() != size()) { return false; } const_iterator b1 = begin(); const_iterator b2 = other.begin(); const_iterator e1 = end(); while (b1 != e1) { if ((*b1) != (*b2)) { return false; } ++b1; ++b2; } return true; } bool operator!=(const prevector &other) const { return !(*this == other); } bool operator<(const prevector &other) const { if (size() < other.size()) { return true; } if (size() > other.size()) { return false; } const_iterator b1 = begin(); const_iterator b2 = other.begin(); const_iterator e1 = end(); while (b1 != e1) { if ((*b1) < (*b2)) { return true; } if ((*b2) < (*b1)) { return false; } ++b1; ++b2; } return false; } size_t allocated_memory() const { if (is_direct()) { return 0; } else { 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 // BITCOIN_PREVECTOR_H