diff options
Diffstat (limited to 'src/util')
-rw-r--r-- | src/util/bip32.cpp | 2 | ||||
-rw-r--r-- | src/util/bitdeque.h | 469 | ||||
-rw-r--r-- | src/util/message.cpp | 1 | ||||
-rw-r--r-- | src/util/strencodings.cpp | 1 | ||||
-rw-r--r-- | src/util/string.cpp | 8 | ||||
-rw-r--r-- | src/util/string.h | 39 | ||||
-rw-r--r-- | src/util/system.cpp | 10 | ||||
-rw-r--r-- | src/util/system.h | 2 | ||||
-rw-r--r-- | src/util/thread.cpp | 6 | ||||
-rw-r--r-- | src/util/thread.h | 3 |
10 files changed, 502 insertions, 39 deletions
diff --git a/src/util/bip32.cpp b/src/util/bip32.cpp index 39e43eeb31..796af4a544 100644 --- a/src/util/bip32.cpp +++ b/src/util/bip32.cpp @@ -6,12 +6,10 @@ #include <util/bip32.h> #include <util/strencodings.h> -#include <algorithm> #include <cstdint> #include <cstdio> #include <sstream> - bool ParseHDKeypath(const std::string& keypath_str, std::vector<uint32_t>& keypath) { std::stringstream ss(keypath_str); diff --git a/src/util/bitdeque.h b/src/util/bitdeque.h new file mode 100644 index 0000000000..1e34b72475 --- /dev/null +++ b/src/util/bitdeque.h @@ -0,0 +1,469 @@ +// Copyright (c) 2022 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_UTIL_BITDEQUE_H +#define BITCOIN_UTIL_BITDEQUE_H + +#include <bitset> +#include <cstddef> +#include <deque> +#include <limits> +#include <stdexcept> +#include <tuple> + +/** Class that mimics std::deque<bool>, but with std::vector<bool>'s bit packing. + * + * BlobSize selects the (minimum) number of bits that are allocated at once. + * Larger values reduce the asymptotic memory usage overhead, at the cost of + * needing larger up-front allocations. The default is 4096 bytes. + */ +template<int BlobSize = 4096 * 8> +class bitdeque +{ + // Internal definitions + using word_type = std::bitset<BlobSize>; + using deque_type = std::deque<word_type>; + static_assert(BlobSize > 0); + static constexpr int BITS_PER_WORD = BlobSize; + + // Forward and friend declarations of iterator types. + template<bool Const> class Iterator; + template<bool Const> friend class Iterator; + + /** Iterator to a bitdeque element, const or not. */ + template<bool Const> + class Iterator + { + using deque_iterator = std::conditional_t<Const, typename deque_type::const_iterator, typename deque_type::iterator>; + + deque_iterator m_it; + int m_bitpos{0}; + Iterator(const deque_iterator& it, int bitpos) : m_it(it), m_bitpos(bitpos) {} + friend class bitdeque; + + public: + using iterator_category = std::random_access_iterator_tag; + using value_type = bool; + using pointer = void; + using const_pointer = void; + using reference = std::conditional_t<Const, bool, typename word_type::reference>; + using const_reference = bool; + using difference_type = std::ptrdiff_t; + + /** Default constructor. */ + Iterator() = default; + + /** Default copy constructor. */ + Iterator(const Iterator&) = default; + + /** Conversion from non-const to const iterator. */ + template<bool ConstArg = Const, typename = std::enable_if_t<Const && ConstArg>> + Iterator(const Iterator<false>& x) : m_it(x.m_it), m_bitpos(x.m_bitpos) {} + + Iterator& operator+=(difference_type dist) + { + if (dist > 0) { + if (dist + m_bitpos >= BITS_PER_WORD) { + ++m_it; + dist -= BITS_PER_WORD - m_bitpos; + m_bitpos = 0; + } + auto jump = dist / BITS_PER_WORD; + m_it += jump; + m_bitpos += dist - jump * BITS_PER_WORD; + } else if (dist < 0) { + dist = -dist; + if (dist > m_bitpos) { + --m_it; + dist -= m_bitpos + 1; + m_bitpos = BITS_PER_WORD - 1; + } + auto jump = dist / BITS_PER_WORD; + m_it -= jump; + m_bitpos -= dist - jump * BITS_PER_WORD; + } + return *this; + } + + friend difference_type operator-(const Iterator& x, const Iterator& y) + { + return BITS_PER_WORD * (x.m_it - y.m_it) + x.m_bitpos - y.m_bitpos; + } + + Iterator& operator=(const Iterator&) = default; + Iterator& operator-=(difference_type dist) { return operator+=(-dist); } + Iterator& operator++() { ++m_bitpos; if (m_bitpos == BITS_PER_WORD) { m_bitpos = 0; ++m_it; }; return *this; } + Iterator operator++(int) { auto ret{*this}; operator++(); return ret; } + Iterator& operator--() { if (m_bitpos == 0) { m_bitpos = BITS_PER_WORD; --m_it; }; --m_bitpos; return *this; } + Iterator operator--(int) { auto ret{*this}; operator--(); return ret; } + friend Iterator operator+(Iterator x, difference_type dist) { x += dist; return x; } + friend Iterator operator+(difference_type dist, Iterator x) { x += dist; return x; } + friend Iterator operator-(Iterator x, difference_type dist) { x -= dist; return x; } + friend bool operator<(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) < std::tie(y.m_it, y.m_bitpos); } + friend bool operator>(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) > std::tie(y.m_it, y.m_bitpos); } + friend bool operator<=(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) <= std::tie(y.m_it, y.m_bitpos); } + friend bool operator>=(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) >= std::tie(y.m_it, y.m_bitpos); } + friend bool operator==(const Iterator& x, const Iterator& y) { return x.m_it == y.m_it && x.m_bitpos == y.m_bitpos; } + friend bool operator!=(const Iterator& x, const Iterator& y) { return x.m_it != y.m_it || x.m_bitpos != y.m_bitpos; } + reference operator*() const { return (*m_it)[m_bitpos]; } + reference operator[](difference_type pos) const { return *(*this + pos); } + }; + +public: + using value_type = bool; + using size_type = std::size_t; + using difference_type = typename deque_type::difference_type; + using reference = typename word_type::reference; + using const_reference = bool; + using iterator = Iterator<false>; + using const_iterator = Iterator<true>; + using pointer = void; + using const_pointer = void; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + +private: + /** Deque of bitsets storing the actual bit data. */ + deque_type m_deque; + + /** Number of unused bits at the front of m_deque.front(). */ + int m_pad_begin; + + /** Number of unused bits at the back of m_deque.back(). */ + int m_pad_end; + + /** Shrink the container by n bits, removing from the end. */ + void erase_back(size_type n) + { + if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_end)) { + n -= BITS_PER_WORD - m_pad_end; + m_pad_end = 0; + m_deque.erase(m_deque.end() - 1 - (n / BITS_PER_WORD), m_deque.end()); + n %= BITS_PER_WORD; + } + if (n) { + auto& last = m_deque.back(); + while (n) { + last.reset(BITS_PER_WORD - 1 - m_pad_end); + ++m_pad_end; + --n; + } + } + } + + /** Extend the container by n bits, adding at the end. */ + void extend_back(size_type n) + { + if (n > static_cast<size_type>(m_pad_end)) { + n -= m_pad_end + 1; + m_pad_end = BITS_PER_WORD - 1; + m_deque.insert(m_deque.end(), 1 + (n / BITS_PER_WORD), {}); + n %= BITS_PER_WORD; + } + m_pad_end -= n; + } + + /** Shrink the container by n bits, removing from the beginning. */ + void erase_front(size_type n) + { + if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_begin)) { + n -= BITS_PER_WORD - m_pad_begin; + m_pad_begin = 0; + m_deque.erase(m_deque.begin(), m_deque.begin() + 1 + (n / BITS_PER_WORD)); + n %= BITS_PER_WORD; + } + if (n) { + auto& first = m_deque.front(); + while (n) { + first.reset(m_pad_begin); + ++m_pad_begin; + --n; + } + } + } + + /** Extend the container by n bits, adding at the beginning. */ + void extend_front(size_type n) + { + if (n > static_cast<size_type>(m_pad_begin)) { + n -= m_pad_begin + 1; + m_pad_begin = BITS_PER_WORD - 1; + m_deque.insert(m_deque.begin(), 1 + (n / BITS_PER_WORD), {}); + n %= BITS_PER_WORD; + } + m_pad_begin -= n; + } + + /** Insert a sequence of falses anywhere in the container. */ + void insert_zeroes(size_type before, size_type count) + { + size_type after = size() - before; + if (before < after) { + extend_front(count); + std::move(begin() + count, begin() + count + before, begin()); + } else { + extend_back(count); + std::move_backward(begin() + before, begin() + before + after, end()); + } + } + +public: + /** Construct an empty container. */ + explicit bitdeque() : m_pad_begin{0}, m_pad_end{0} {} + + /** Set the container equal to count times the value of val. */ + void assign(size_type count, bool val) + { + m_deque.clear(); + m_deque.resize((count + BITS_PER_WORD - 1) / BITS_PER_WORD); + m_pad_begin = 0; + m_pad_end = 0; + if (val) { + for (auto& elem : m_deque) elem.flip(); + } + if (count % BITS_PER_WORD) { + erase_back(BITS_PER_WORD - (count % BITS_PER_WORD)); + } + } + + /** Construct a container containing count times the value of val. */ + bitdeque(size_type count, bool val) { assign(count, val); } + + /** Construct a container containing count false values. */ + explicit bitdeque(size_t count) { assign(count, false); } + + /** Copy constructor. */ + bitdeque(const bitdeque&) = default; + + /** Move constructor. */ + bitdeque(bitdeque&&) noexcept = default; + + /** Copy assignment operator. */ + bitdeque& operator=(const bitdeque& other) = default; + + /** Move assignment operator. */ + bitdeque& operator=(bitdeque&& other) noexcept = default; + + // Iterator functions. + iterator begin() noexcept { return {m_deque.begin(), m_pad_begin}; } + iterator end() noexcept { return iterator{m_deque.end(), 0} - m_pad_end; } + const_iterator begin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; } + const_iterator cbegin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; } + const_iterator end() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; } + const_iterator cend() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; } + reverse_iterator rbegin() noexcept { return reverse_iterator{end()}; } + reverse_iterator rend() noexcept { return reverse_iterator{begin()}; } + const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator{cend()}; } + const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{cend()}; } + const_reverse_iterator rend() const noexcept { return const_reverse_iterator{cbegin()}; } + const_reverse_iterator crend() const noexcept { return const_reverse_iterator{cbegin()}; } + + /** Count the number of bits in the container. */ + size_type size() const noexcept { return m_deque.size() * BITS_PER_WORD - m_pad_begin - m_pad_end; } + + /** Determine whether the container is empty. */ + bool empty() const noexcept + { + return m_deque.size() == 0 || (m_deque.size() == 1 && (m_pad_begin + m_pad_end == BITS_PER_WORD)); + } + + /** Return the maximum size of the container. */ + size_type max_size() const noexcept + { + if (m_deque.max_size() < std::numeric_limits<difference_type>::max() / BITS_PER_WORD) { + return m_deque.max_size() * BITS_PER_WORD; + } else { + return std::numeric_limits<difference_type>::max(); + } + } + + /** Set the container equal to the bits in [first,last). */ + template<typename It> + void assign(It first, It last) + { + size_type count = std::distance(first, last); + assign(count, false); + auto it = begin(); + while (first != last) { + *(it++) = *(first++); + } + } + + /** Set the container equal to the bits in ilist. */ + void assign(std::initializer_list<bool> ilist) + { + assign(ilist.size(), false); + auto it = begin(); + auto init = ilist.begin(); + while (init != ilist.end()) { + *(it++) = *(init++); + } + } + + /** Set the container equal to the bits in ilist. */ + bitdeque& operator=(std::initializer_list<bool> ilist) + { + assign(ilist); + return *this; + } + + /** Construct a container containing the bits in [first,last). */ + template<typename It> + bitdeque(It first, It last) { assign(first, last); } + + /** Construct a container containing the bits in ilist. */ + bitdeque(std::initializer_list<bool> ilist) { assign(ilist); } + + // Access an element of the container, with bounds checking. + reference at(size_type position) + { + if (position >= size()) throw std::out_of_range("bitdeque::at() out of range"); + return begin()[position]; + } + const_reference at(size_type position) const + { + if (position >= size()) throw std::out_of_range("bitdeque::at() out of range"); + return cbegin()[position]; + } + + // Access elements of the container without bounds checking. + reference operator[](size_type position) { return begin()[position]; } + const_reference operator[](size_type position) const { return cbegin()[position]; } + reference front() { return *begin(); } + const_reference front() const { return *cbegin(); } + reference back() { return end()[-1]; } + const_reference back() const { return cend()[-1]; } + + /** Release unused memory. */ + void shrink_to_fit() + { + m_deque.shrink_to_fit(); + } + + /** Empty the container. */ + void clear() noexcept + { + m_deque.clear(); + m_pad_begin = m_pad_end = 0; + } + + // Append an element to the container. + void push_back(bool val) + { + extend_back(1); + back() = val; + } + reference emplace_back(bool val) + { + extend_back(1); + auto ref = back(); + ref = val; + return ref; + } + + // Prepend an element to the container. + void push_front(bool val) + { + extend_front(1); + front() = val; + } + reference emplace_front(bool val) + { + extend_front(1); + auto ref = front(); + ref = val; + return ref; + } + + // Remove the last element from the container. + void pop_back() + { + erase_back(1); + } + + // Remove the first element from the container. + void pop_front() + { + erase_front(1); + } + + /** Resize the container. */ + void resize(size_type n) + { + if (n < size()) { + erase_back(size() - n); + } else { + extend_back(n - size()); + } + } + + // Swap two containers. + void swap(bitdeque& other) noexcept + { + std::swap(m_deque, other.m_deque); + std::swap(m_pad_begin, other.m_pad_begin); + std::swap(m_pad_end, other.m_pad_end); + } + friend void swap(bitdeque& b1, bitdeque& b2) noexcept { b1.swap(b2); } + + // Erase elements from the container. + iterator erase(const_iterator first, const_iterator last) + { + size_type before = std::distance(cbegin(), first); + size_type dist = std::distance(first, last); + size_type after = std::distance(last, cend()); + if (before < after) { + std::move_backward(begin(), begin() + before, end() - after); + erase_front(dist); + return begin() + before; + } else { + std::move(end() - after, end(), begin() + before); + erase_back(dist); + return end() - after; + } + } + + iterator erase(iterator first, iterator last) { return erase(const_iterator{first}, const_iterator{last}); } + iterator erase(const_iterator pos) { return erase(pos, pos + 1); } + iterator erase(iterator pos) { return erase(const_iterator{pos}, const_iterator{pos} + 1); } + + // Insert elements into the container. + iterator insert(const_iterator pos, bool val) + { + size_type before = pos - cbegin(); + insert_zeroes(before, 1); + auto it = begin() + before; + *it = val; + return it; + } + + iterator emplace(const_iterator pos, bool val) { return insert(pos, val); } + + iterator insert(const_iterator pos, size_type count, bool val) + { + size_type before = pos - cbegin(); + insert_zeroes(before, count); + auto it_begin = begin() + before; + auto it = it_begin; + auto it_end = it + count; + while (it != it_end) *(it++) = val; + return it_begin; + } + + template<typename It> + iterator insert(const_iterator pos, It first, It last) + { + size_type before = pos - cbegin(); + size_type count = std::distance(first, last); + insert_zeroes(before, count); + auto it_begin = begin() + before; + auto it = it_begin; + while (first != last) { + *(it++) = *(first++); + } + return it_begin; + } +}; + +#endif // BITCOIN_UTIL_BITDEQUE_H diff --git a/src/util/message.cpp b/src/util/message.cpp index 028251a5a8..7d6f3403f4 100644 --- a/src/util/message.cpp +++ b/src/util/message.cpp @@ -8,7 +8,6 @@ #include <key_io.h> #include <pubkey.h> #include <script/standard.h> -#include <serialize.h> #include <uint256.h> #include <util/message.h> #include <util/strencodings.h> diff --git a/src/util/strencodings.cpp b/src/util/strencodings.cpp index 303e19beec..b5ac151374 100644 --- a/src/util/strencodings.cpp +++ b/src/util/strencodings.cpp @@ -6,7 +6,6 @@ #include <span.h> #include <util/strencodings.h> -#include <algorithm> #include <array> #include <cassert> #include <cstring> diff --git a/src/util/string.cpp b/src/util/string.cpp index dff782c330..e994c85f1c 100644 --- a/src/util/string.cpp +++ b/src/util/string.cpp @@ -4,11 +4,11 @@ #include <util/string.h> -#include <boost/algorithm/string/replace.hpp> - +#include <regex> #include <string> -void ReplaceAll(std::string& in_out, std::string_view search, std::string_view substitute) +void ReplaceAll(std::string& in_out, const std::string& search, const std::string& substitute) { - boost::replace_all(in_out, search, substitute); + if (search.empty()) return; + in_out = std::regex_replace(in_out, std::regex(search), substitute); } diff --git a/src/util/string.h b/src/util/string.h index df20e34ae9..9b4c9a7e28 100644 --- a/src/util/string.h +++ b/src/util/string.h @@ -7,7 +7,6 @@ #include <util/spanparsing.h> -#include <algorithm> #include <array> #include <cstdint> #include <cstring> @@ -17,7 +16,7 @@ #include <string_view> #include <vector> -void ReplaceAll(std::string& in_out, std::string_view search, std::string_view substitute); +void ReplaceAll(std::string& in_out, const std::string& search, const std::string& substitute); [[nodiscard]] inline std::vector<std::string> SplitString(std::string_view str, char sep) { @@ -58,34 +57,30 @@ void ReplaceAll(std::string& in_out, std::string_view search, std::string_view s } /** - * Join a list of items + * Join all container items. Typically used to concatenate strings but accepts + * containers with elements of any type. * - * @param list The list to join - * @param separator The separator - * @param unary_op Apply this operator to each item in the list + * @param container The items to join + * @param separator The separator + * @param unary_op Apply this operator to each item */ -template <typename T, typename BaseType, typename UnaryOp> -auto Join(const std::vector<T>& list, const BaseType& separator, UnaryOp unary_op) - -> decltype(unary_op(list.at(0))) +template <typename C, typename S, typename UnaryOp> +auto Join(const C& container, const S& separator, UnaryOp unary_op) { - decltype(unary_op(list.at(0))) ret; - for (size_t i = 0; i < list.size(); ++i) { - if (i > 0) ret += separator; - ret += unary_op(list.at(i)); + decltype(unary_op(*container.begin())) ret; + bool first{true}; + for (const auto& item : container) { + if (!first) ret += separator; + ret += unary_op(item); + first = false; } return ret; } -template <typename T, typename T2> -T Join(const std::vector<T>& list, const T2& separator) +template <typename C, typename S> +auto Join(const C& container, const S& separator) { - return Join(list, separator, [](const T& i) { return i; }); -} - -// Explicit overload needed for c_str arguments, which would otherwise cause a substitution failure in the template above. -inline std::string Join(const std::vector<std::string>& list, std::string_view separator) -{ - return Join<std::string>(list, separator); + return Join(container, separator, [](const auto& i) { return i; }); } /** diff --git a/src/util/system.cpp b/src/util/system.cpp index 1953a9f836..c3c6cbfef6 100644 --- a/src/util/system.cpp +++ b/src/util/system.cpp @@ -831,7 +831,7 @@ std::string HelpMessageOpt(const std::string &option, const std::string &message std::string("\n\n"); } -static std::string FormatException(const std::exception* pex, const char* pszThread) +static std::string FormatException(const std::exception* pex, std::string_view thread_name) { #ifdef WIN32 char pszModule[MAX_PATH] = ""; @@ -841,15 +841,15 @@ static std::string FormatException(const std::exception* pex, const char* pszThr #endif if (pex) return strprintf( - "EXCEPTION: %s \n%s \n%s in %s \n", typeid(*pex).name(), pex->what(), pszModule, pszThread); + "EXCEPTION: %s \n%s \n%s in %s \n", typeid(*pex).name(), pex->what(), pszModule, thread_name); else return strprintf( - "UNKNOWN EXCEPTION \n%s in %s \n", pszModule, pszThread); + "UNKNOWN EXCEPTION \n%s in %s \n", pszModule, thread_name); } -void PrintExceptionContinue(const std::exception* pex, const char* pszThread) +void PrintExceptionContinue(const std::exception* pex, std::string_view thread_name) { - std::string message = FormatException(pex, pszThread); + std::string message = FormatException(pex, thread_name); LogPrintf("\n\n************************\n%s\n", message); tfm::format(std::cerr, "\n\n************************\n%s\n", message); } diff --git a/src/util/system.h b/src/util/system.h index 756e6642f2..c8e1de6700 100644 --- a/src/util/system.h +++ b/src/util/system.h @@ -51,7 +51,7 @@ bool error(const char* fmt, const Args&... args) return false; } -void PrintExceptionContinue(const std::exception *pex, const char* pszThread); +void PrintExceptionContinue(const std::exception* pex, std::string_view thread_name); /** * Ensure file contents are fully committed to disk, using a platform-specific diff --git a/src/util/thread.cpp b/src/util/thread.cpp index f9f427ba20..ae98abdb3d 100644 --- a/src/util/thread.cpp +++ b/src/util/thread.cpp @@ -10,10 +10,12 @@ #include <exception> #include <functional> +#include <string> +#include <utility> -void util::TraceThread(const char* thread_name, std::function<void()> thread_func) +void util::TraceThread(std::string_view thread_name, std::function<void()> thread_func) { - util::ThreadRename(thread_name); + util::ThreadRename(std::string{thread_name}); try { LogPrintf("%s thread start\n", thread_name); thread_func(); diff --git a/src/util/thread.h b/src/util/thread.h index ca2eccc0c3..b80bf046a0 100644 --- a/src/util/thread.h +++ b/src/util/thread.h @@ -6,12 +6,13 @@ #define BITCOIN_UTIL_THREAD_H #include <functional> +#include <string> namespace util { /** * A wrapper for do-something-once thread functions. */ -void TraceThread(const char* thread_name, std::function<void()> thread_func); +void TraceThread(std::string_view thread_name, std::function<void()> thread_func); } // namespace util |