util: add VecDeque #30161
util: add VecDeque #30161
Conversation
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. Code CoverageFor detailed information about the code coverage, see the test coverage report. ReviewsSee the guideline for information on the review process.
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update. ConflictsReviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first. |
9c4861a to
315dd68
Compare
|
🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the Possibly this is due to a silent merge conflict (the changes in this pull request being Leave a comment here, if you need help tracking down a confusing failure. |
|
Apparently |
|
Concept ACK. |
Then, perhaps, it's a good chance to avoid |
|
@hebasto I do prefer to stay compatible with the |
src/util/vecdeque.h
Outdated
| size_t old_pos = m_offset; | ||
| for (size_t new_pos = 0; new_pos < m_size; ++new_pos) { | ||
| std::construct_at<T>(new_buffer + new_pos, std::move(*(m_buffer + old_pos))); | ||
| std::destroy_at<T>(m_buffer + old_pos); |
There was a problem hiding this comment.
Does it make sense to skip this call if std::is_trivially_destructible_v<T>?
There was a problem hiding this comment.
I don't think so, since that case doesn't let us avoid the loop.
| VecDeque& operator=(const VecDeque& other) | ||
| { | ||
| clear(); | ||
| Reallocate(other.m_size); |
There was a problem hiding this comment.
The move assignment operator preserves the capacity. Maybe do the same here for consistency?
There was a problem hiding this comment.
I think it's better to match std::vector behavior here (technically, spec doesn't say anything about the capacity of a copied element, but common implementations make it just big enough to hold the copied data, I believe).
5e9abaf to
03cfb86
Compare
|
I've added some doxygen comments on |
|
🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the Possibly this is due to a silent merge conflict (the changes in this pull request being Leave a comment here, if you need help tracking down a confusing failure. |
|
reACK ee253ca reviewed via |
This is an STL-like container that interface-wise looks like std::deque, but is backed by a (fixed size, with vector-like capacity/reserve) circular buffer.
|
reACK 7b8eea0 reviewed via |
26a7f70 ci: enable self-assignment clang-tidy check (Cory Fields) 32b1d13 refactor: add self-assign checks to classes which violate the clang-tidy check (Cory Fields) Pull request description: See comment here: #30161 (comment) Our code failed these checks in three places, which have been fixed up here. Though these appear to have been harmless, adding the check avoids the copy in the self-assignment case so there should be no downside. ~Additionally, minisketch failed the check as well. See bitcoin-core/minisketch#87 Edit: Done After fixing up the violations, turn on the aggressive clang-tidy check. Note for reviewers: `git diff -w` makes this trivial to review. ACKs for top commit: hebasto: ACK 26a7f70, I have reviewed the code and it looks OK. TheCharlatan: ACK 26a7f70 Tree-SHA512: 74d8236a1b5a698f2f61c4740c4fc77788b7f882c4b395acc4e6bfef1ec8a4554ea8821a26b14d70cfa6c8e2e9ea305deeea3fbf323967fa19343c007a53c5ba
|
Ported to the CMake-based build system in hebasto#264. |
Extracted from #30126.
This adds a
VecDequedata type, inspired bystd::deque, but backed by a single allocated memory region used as a ring buffer instead of a linked list of arrays. This gives better memory locality and less allocation overhead, plus better guarantees (some C++ standard library implementations, though not libstdc++ and libc++, use a separate allocation per element in a deque).It is intended for the candidate set search queue in #30126, but may be useful as a replacement for
std::dequein other places too. It's not a full drop-in replacement, as I did not add iteration support which is unnecessary for the intended use case, but nothing prevents adding that if needed.Everything is tested through a simulation-based fuzz test that compares the behavior with normal
std::dequeequivalent operations, both for trivially-copyable/destructible types and others.