aboutsummaryrefslogtreecommitdiff
path: root/src/prevector.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/prevector.h')
-rw-r--r--src/prevector.h490
1 files changed, 490 insertions, 0 deletions
diff --git a/src/prevector.h b/src/prevector.h
new file mode 100644
index 0000000000..1da459bcfe
--- /dev/null
+++ b/src/prevector.h
@@ -0,0 +1,490 @@
+// Copyright (c) 2015 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 <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+
+#include <iterator>
+
+#pragma pack(push, 1)
+/** 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 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<unsigned int N, typename T, typename Size = uint32_t, typename Diff = int32_t>
+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(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(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(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(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<T*>(_union.direct) + pos; }
+ const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
+ T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect) + pos; }
+ const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_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()) {
+ _union.indirect = static_cast<char*>(realloc(_union.indirect, ((size_t)sizeof(T)) * new_capacity));
+ _union.capacity = new_capacity;
+ } else {
+ char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
+ T* src = direct_ptr(0);
+ T* dst = reinterpret_cast<T*>(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); }
+
+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);
+ }
+ }
+
+ template<typename InputIterator>
+ 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<void*>(item_ptr(size() - 1))) T(*first);
+ ++first;
+ }
+ }
+
+ prevector() : _size(0) {}
+
+ explicit prevector(size_type n) : _size(0) {
+ resize(n);
+ }
+
+ 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);
+ }
+ }
+
+ 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;
+ }
+ }
+
+ 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;
+ }
+ }
+
+ 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;
+ }
+ 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) {
+ while (size() > new_size) {
+ item_ptr(size() - 1)->~T();
+ _size--;
+ }
+ if (new_size > capacity()) {
+ change_capacity(new_size);
+ }
+ while (size() < new_size) {
+ _size++;
+ new(static_cast<void*>(item_ptr(size() - 1))) T();
+ }
+ }
+
+ 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));
+ _size++;
+ new(static_cast<void*>(item_ptr(p))) T(value);
+ return iterator(item_ptr(p));
+ }
+
+ 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));
+ _size += count;
+ for (size_type i = 0; i < count; i++) {
+ new(static_cast<void*>(item_ptr(p + i))) T(value);
+ }
+ }
+
+ template<typename InputIterator>
+ 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));
+ _size += count;
+ while (first != last) {
+ new(static_cast<void*>(item_ptr(p))) T(*first);
+ ++p;
+ ++first;
+ }
+ }
+
+ iterator erase(iterator pos) {
+ (*pos).~T();
+ memmove(&(*pos), &(*pos) + 1, ((char*)&(*end())) - ((char*)(1 + &(*pos))));
+ _size--;
+ return pos;
+ }
+
+ iterator erase(iterator first, iterator last) {
+ iterator p = first;
+ char* endp = (char*)&(*end());
+ while (p != last) {
+ (*p).~T();
+ _size--;
+ ++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() {
+ _size--;
+ }
+
+ 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<N, T, Size, Diff>& other) {
+ if (_size & other._size & 1) {
+ std::swap(_union.capacity, other._union.capacity);
+ std::swap(_union.indirect, other._union.indirect);
+ } else {
+ std::swap(_union, other._union);
+ }
+ std::swap(_size, other._size);
+ }
+
+ ~prevector() {
+ clear();
+ if (!is_direct()) {
+ free(_union.indirect);
+ _union.indirect = NULL;
+ }
+ }
+
+ bool operator==(const prevector<N, T, Size, Diff>& 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<N, T, Size, Diff>& other) const {
+ return !(*this == other);
+ }
+
+ bool operator<(const prevector<N, T, Size, Diff>& 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;
+ }
+ }
+};
+#pragma pack(pop)
+
+#endif
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-05 09:11:41 +0000