commit 969902f: [Rework] Use another version of hash table from the same author
Vsevolod Stakhov
vsevolod at rspamd.com
Sun Jul 17 19:42:04 UTC 2022
Author: Vsevolod Stakhov
Date: 2022-07-17 16:43:47 +0100
URL: https://github.com/rspamd/rspamd/commit/969902f04569ab12e69e0d57ef1f6e9f0c42f855
[Rework] Use another version of hash table from the same author
---
contrib/DEPENDENCY_INFO.md | 73 +-
contrib/{robin-hood => ankerl}/LICENSE | 2 +-
contrib/ankerl/svector.h | 993 +++++++++
contrib/ankerl/unordered_dense.h | 1199 +++++++++++
contrib/robin-hood/robin_hood.h | 2430 ----------------------
src/libmime/received.cxx | 2 +-
src/libmime/received.hxx | 8 +-
src/libserver/composites/composites.cxx | 4 +-
src/libserver/composites/composites_internal.hxx | 2 +-
src/libserver/composites/composites_manager.cxx | 4 +-
src/libserver/css/css.cxx | 4 +-
src/libserver/css/css_colors_list.hxx | 4 +-
src/libserver/css/css_rule.hxx | 4 +-
src/libserver/css/css_value.cxx | 2 +-
src/libserver/html/html_entities.cxx | 8 +-
src/libserver/html/html_tag_defs.hxx | 6 +-
src/libserver/redis_pool.cxx | 19 +-
src/libserver/symcache/symcache_internal.hxx | 8 +-
src/libserver/symcache/symcache_item.cxx | 2 +-
src/libserver/symcache/symcache_item.hxx | 2 +-
src/libstat/backends/cdb_backend.cxx | 4 +-
src/libstat/backends/http_backend.cxx | 4 +-
src/libutil/cxx/hash_util.hxx | 6 +-
src/lua/lua_html.cxx | 4 +-
24 files changed, 2281 insertions(+), 2513 deletions(-)
diff --git a/contrib/DEPENDENCY_INFO.md b/contrib/DEPENDENCY_INFO.md
index fd01fa5ae..9c5cdb431 100644
--- a/contrib/DEPENDENCY_INFO.md
+++ b/contrib/DEPENDENCY_INFO.md
@@ -1,38 +1,39 @@
# Rspamd Dependency Info
-| Name | Version | License | Patched | Notes |
-| --- |---------| --- | --- | --- |
-| aho-corasick | ? | LGPL-3.0 | YES | lowercase support |
-| cdb | 1.1.0 | Public Domain / CC0 | NO | |
-| hiredis | 0.13.3 | BSD-3-Clause | YES | many changes |
-| libev | 4.33 | BSD-2-Clause | YES | many changes |
-| lc-btrie | ? | BSD-3-Clause | YES | mempool support |
-| libottery | ? | Public Domain / CC0 | YES | many changes |
-| librdns | ? | BSD-2-Clause | YES | |
-| libucl | ? | BSD-2-Clause | YES | |
-| replxx | 6d93360 | BSD-2-Clause | YES | libicu usage |
-| lua-argparse | 0.7.1 | MIT | NO | |
-| lua-bit | 1.0.2 | MIT | YES | build fixes |
-| lua-fun | ? | MIT | YES | rspamd text |
-| lua-lpeg | 1.0 | MIT | YES | rspamd text + alloc|
-| lua-moses | ? | MIT | NO | |
-| lua-lupa | ? | MIT | NO | |
-| lua-tableshape | ae67256 | MIT | NO | |
-| mumhash | ? | MIT | NO | |
-| ngx-http-parser | 2.2.0 | MIT | YES | spamc support |
-| Mozilla-PublicSuffix | ? | MIT | NO | |
-| snowball | ? | BSD-3-Clause | NO | |
-| t1ha | ? | Zlib | NO | |
-| uthash | 1.9.8 | BSD | YES | |
-| xxhash | 0.8.1 | BSD | NO | |
-| zstd | 1.4.5 | BSD | NO | |
-| google-ced | 37529e6 | Apache 2 | YES | build fixes |
-| kann | ? | MIT | YES | blas/lapack changes|
-| fpconv | ? | Boost | YES | many changes |
-| fastutf8 | ? | MIT | YES | many changes |
-| expected | v1.0 | Public Domain / CC0 | NO | |
-| robin-hood | 3.9.1 | MIT | NO | |
-| frozen | 1.0.1 | Apache 2 | NO | |
-| fmt | 8.1.1 | MIT | NO | |
-| doctest | 2.4.6 | MIT | NO | |
-| function2 | 4.1.0 | Boost | NO | |
+| Name | Version | License | Patched | Notes |
+|------------------------|---------|---------------------| --- | --- |
+| aho-corasick | ? | LGPL-3.0 | YES | lowercase support |
+| cdb | 1.1.0 | Public Domain / CC0 | NO | |
+| hiredis | 0.13.3 | BSD-3-Clause | YES | many changes |
+| libev | 4.33 | BSD-2-Clause | YES | many changes |
+| lc-btrie | ? | BSD-3-Clause | YES | mempool support |
+| libottery | ? | Public Domain / CC0 | YES | many changes |
+| librdns | ? | BSD-2-Clause | YES | |
+| libucl | ? | BSD-2-Clause | YES | |
+| replxx | 6d93360 | BSD-2-Clause | YES | libicu usage |
+| lua-argparse | 0.7.1 | MIT | NO | |
+| lua-bit | 1.0.2 | MIT | YES | build fixes |
+| lua-fun | ? | MIT | YES | rspamd text |
+| lua-lpeg | 1.0 | MIT | YES | rspamd text + alloc|
+| lua-moses | ? | MIT | NO | |
+| lua-lupa | ? | MIT | NO | |
+| lua-tableshape | ae67256 | MIT | NO | |
+| mumhash | ? | MIT | NO | |
+| ngx-http-parser | 2.2.0 | MIT | YES | spamc support |
+| Mozilla-PublicSuffix | ? | MIT | NO | |
+| snowball | ? | BSD-3-Clause | NO | |
+| t1ha | ? | Zlib | NO | |
+| uthash | 1.9.8 | BSD | YES | |
+| xxhash | 0.8.1 | BSD | NO | |
+| zstd | 1.4.5 | BSD | NO | |
+| google-ced | 37529e6 | Apache 2 | YES | build fixes |
+| kann | ? | MIT | YES | blas/lapack changes|
+| fpconv | ? | Boost | YES | many changes |
+| fastutf8 | ? | MIT | YES | many changes |
+| expected | v1.0 | Public Domain / CC0 | NO | |
+| frozen | 1.0.1 | Apache 2 | NO | |
+| fmt | 8.1.1 | MIT | NO | |
+| doctest | 2.4.6 | MIT | NO | |
+| function2 | 4.1.0 | Boost | NO | |
+| ankerl/svector | 1.0.0 | MIT | NO | |
+| ankerl/unordered_dense | 1.0.2 | MIT | NO | |
\ No newline at end of file
diff --git a/contrib/robin-hood/LICENSE b/contrib/ankerl/LICENSE
similarity index 96%
rename from contrib/robin-hood/LICENSE
rename to contrib/ankerl/LICENSE
index e9a58ad65..c4d1a0e48 100644
--- a/contrib/robin-hood/LICENSE
+++ b/contrib/ankerl/LICENSE
@@ -1,6 +1,6 @@
MIT License
-Copyright (c) 2018-2019 Martin Ankerl
+Copyright (c) 2022 Martin Leitner-Ankerl
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
diff --git a/contrib/ankerl/svector.h b/contrib/ankerl/svector.h
new file mode 100644
index 000000000..b6ef1ad68
--- /dev/null
+++ b/contrib/ankerl/svector.h
@@ -0,0 +1,993 @@
+// ┌─┐┬ ┬┌─┐┌─┐┌┬┐┌─┐┬─┐ Compact SVO optimized vector C++17 or higher
+// └─┐└┐┌┘├┤ │ │ │ │├┬┘ Version 1.0.0
+// └─┘ └┘ └─┘└─┘ ┴ └─┘┴└─ https://github.com/martinus/svector
+//
+// Licensed under the MIT License <http://opensource.org/licenses/MIT>.
+// SPDX-License-Identifier: MIT
+// Copyright (c) 2022 Martin Leitner-Ankerl <martin.ankerl at gmail.com>
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in all
+// copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+// SOFTWARE.
+
+#ifndef ANKERL_SVECTOR_H
+#define ANKERL_SVECTOR_H
+
+// see https://semver.org/spec/v2.0.0.html
+#define ANKERL_SVECTOR_VERSION_MAJOR 1 // incompatible API changes
+#define ANKERL_SVECTOR_VERSION_MINOR 0 // add functionality in a backwards compatible manner
+#define ANKERL_SVECTOR_VERSION_PATCH 0 // backwards compatible bug fixes
+
+// API versioning with inline namespace, see https://www.foonathan.net/2018/11/inline-namespaces/
+#define ANKERL_SVECTOR_VERSION_CONCAT1(major, minor, patch) v##major##_##minor##_##patch
+#define ANKERL_SVECTOR_VERSION_CONCAT(major, minor, patch) ANKERL_SVECTOR_VERSION_CONCAT1(major, minor, patch)
+#define ANKERL_SVECTOR_NAMESPACE \
+ ANKERL_SVECTOR_VERSION_CONCAT(ANKERL_SVECTOR_VERSION_MAJOR, ANKERL_SVECTOR_VERSION_MINOR, ANKERL_SVECTOR_VERSION_PATCH)
+
+#include <algorithm>
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <cstring>
+#include <initializer_list>
+#include <iterator>
+#include <limits>
+#include <memory>
+#include <new>
+#include <stdexcept>
+#include <type_traits>
+#include <utility>
+
+namespace ankerl {
+inline namespace ANKERL_SVECTOR_NAMESPACE {
+namespace detail {
+
+template <typename Condition, typename T = void>
+using enable_if_t = typename std::enable_if<Condition::value, T>::type;
+
+template <typename It>
+using is_input_iterator = std::is_base_of<std::input_iterator_tag, typename std::iterator_traits<It>::iterator_category>;
+
+constexpr auto round_up(size_t n, size_t multiple) -> size_t {
+ return ((n + (multiple - 1)) / multiple) * multiple;
+}
+
+template <typename T>
+constexpr auto cx_min(T a, T b) -> T {
+ return a < b ? a : b;
+}
+
+template <typename T>
+constexpr auto cx_max(T a, T b) -> T {
+ return a > b ? a : b;
+}
+
+template <typename T>
+constexpr auto alignment_of_svector() -> size_t {
+ return cx_max(sizeof(void*), std::alignment_of_v<T>);
+}
+
+/**
+ * @brief Calculates sizeof(svector<T, N>) for a given type and inline capacity
+ */
+template <typename T>
+constexpr auto size_of_svector(size_t min_inline_capacity) -> size_t {
+ // + 1 for one byte size in direct mode
+ return round_up(sizeof(T) * min_inline_capacity + 1, alignment_of_svector<T>());
+}
+
+/**
+ * @brief Calculates how many T we can actually store inside of an svector without increasing its sizeof().
+ *
+ * E.g. svector<char, 1> could store 7 bytes even though 1 is specified. This makes sure we don't waste any
+ * of the padding.
+ */
+template <typename T>
+constexpr auto automatic_capacity(size_t min_inline_capacity) -> size_t {
+ return cx_min((size_of_svector<T>(min_inline_capacity) - 1U) / sizeof(T), size_t(127));
+}
+
+/**
+ * Holds size & capacity, a glorified struct.
+ */
+class header {
+ size_t m_size{};
+ size_t const m_capacity;
+
+public:
+ inline explicit header(size_t capacity)
+ : m_capacity{capacity} {}
+
+ [[nodiscard]] inline auto size() const -> size_t {
+ return m_size;
+ }
+
+ [[nodiscard]] inline auto capacity() const -> size_t {
+ return m_capacity;
+ }
+
+ inline void size(size_t s) {
+ m_size = s;
+ }
+};
+
+/**
+ * @brief Holds header (size+capacity) plus an arbitrary number of T.
+ *
+ * To make storage compact, we don't actually store a pointer to T. We don't have to
+ * because we know exactly at which location it begins.
+ */
+template <typename T>
+struct storage : public header {
+ static constexpr auto alignment_of_t = std::alignment_of_v<T>;
+ static constexpr auto max_alignment = std::max(std::alignment_of_v<header>, std::alignment_of_v<T>);
+ static constexpr auto offset_to_data = detail::round_up(sizeof(header), alignment_of_t);
+ static_assert(max_alignment <= __STDCPP_DEFAULT_NEW_ALIGNMENT__);
+
+ explicit storage(size_t capacity)
+ : header(capacity) {}
+
+ auto data() -> T* {
+ auto ptr_to_data = reinterpret_cast<std::byte*>(this) + offset_to_data;
+ return std::launder(reinterpret_cast<T*>(ptr_to_data));
+ }
+
+ /**
+ * @brief Allocates space for storage plus capacity*T objects.
+ *
+ * Checks to make sure that allocation won't overflow.
+ *
+ * @param capacity Number of T to allocate.
+ * @return storage<T>*
+ */
+ static auto alloc(size_t capacity) -> storage<T>* {
+ // make sure we don't overflow!
+ auto mem = sizeof(T) * capacity;
+ if (mem < capacity) {
+ throw std::bad_alloc();
+ }
+ if (offset_to_data + mem < mem) {
+ throw std::bad_alloc();
+ }
+ mem += offset_to_data;
+ if (static_cast<uint64_t>(mem) > static_cast<uint64_t>(std::numeric_limits<std::ptrdiff_t>::max())) {
+ throw std::bad_alloc();
+ }
+
+ void* ptr = ::operator new(offset_to_data + sizeof(T) * capacity);
+ if (nullptr == ptr) {
+ throw std::bad_alloc();
+ }
+ // use void* to ensure we don't use an overload for T*
+ return new (ptr) storage<T>(capacity);
+ }
+};
+
+} // namespace detail
+
+template <typename T, size_t MinInlineCapacity>
+class svector {
+ static_assert(MinInlineCapacity <= 127, "sorry, can't have more than 127 direct elements");
+ static constexpr auto N = detail::automatic_capacity<T>(MinInlineCapacity);
+
+ enum class direction { direct, indirect };
+
+ /**
+ * A buffer to hold the data of the svector Depending on direct/indirect mode, the content it holds is like so:
+ *
+ * direct:
+ * m_data[0] & 1: lowest bit is 1 for direct mode.
+ * m_data[0] >> 1: size for direct mode
+ * Then 0-X bytes unused (padding), and then the actual inline T data.
+ * indirect:
+ * m_data[0] & 1: lowest bit is 0 for indirect mode
+ * m_data[0..7]: stores an uintptr_t, which points to the indirect data.
+ */
+ alignas(detail::alignment_of_svector<T>()) std::array<uint8_t, detail::size_of_svector<T>(MinInlineCapacity)> m_data;
+
+ // direct mode ///////////////////////////////////////////////////////////
+
+ [[nodiscard]] auto is_direct() const -> bool {
+ return (m_data[0] & 1U) != 0U;
+ }
+
+ [[nodiscard]] auto direct_size() const -> size_t {
+ return m_data[0] >> 1U;
+ }
+
+ // sets size of direct mode and mode to direct too.
+ constexpr void set_direct_and_size(size_t s) {
+ m_data[0] = (s << 1U) | 1U;
+ }
+
+ [[nodiscard]] auto direct_data() -> T* {
+ return std::launder(reinterpret_cast<T*>(m_data.data() + std::alignment_of_v<T>));
+ }
+
+ // indirect mode /////////////////////////////////////////////////////////
+
+ [[nodiscard]] auto indirect() -> detail::storage<T>* {
+ detail::storage<T>* ptr; // NOLINT(cppcoreguidelines-init-variables)
+ std::memcpy(&ptr, m_data.data(), sizeof(ptr));
+ return ptr;
+ }
+
+ [[nodiscard]] auto indirect() const -> detail::storage<T> const* {
+ return const_cast<svector*>(this)->indirect(); // NOLINT(cppcoreguidelines-pro-type-const-cast)
+ }
+
+ void set_indirect(detail::storage<T>* ptr) {
+ std::memcpy(m_data.data(), &ptr, sizeof(ptr));
+
+ // safety check to guarantee the lowest bit is 0
+ if (is_direct()) {
+ throw std::bad_alloc(); // LCOV_EXCL_LINE
+ }
+ }
+
+ // helpers ///////////////////////////////////////////////////////////////
+
+ /**
+ * @brief Moves size objects from source_ptr to target_ptr, and destroys what remains in source_ptr.
+ *
+ * Assumes data is not overlapping
+ */
+ static void uninitialized_move_and_destroy(T* source_ptr, T* target_ptr, size_t size) {
+ if constexpr (std::is_trivially_copyable_v<T>) {
+ std::memcpy(target_ptr, source_ptr, size * sizeof(T));
+ } else {
+ std::uninitialized_move_n(source_ptr, size, target_ptr);
+ std::destroy_n(source_ptr, size);
+ }
+ }
+
+ /**
+ * @brief Reallocates all data when capacity changes.
+ *
+ * if new_capacity <= N chooses direct memory, otherwise indirect.
+ */
+ void realloc(size_t new_capacity) {
+ if (new_capacity <= N) {
+ // put everything into direct storage
+ if (is_direct()) {
+ // direct -> direct: nothing to do!
+ return;
+ }
+
+ // indirect -> direct
+ auto* storage = indirect();
+ uninitialized_move_and_destroy(storage->data(), direct_data(), storage->size());
+ set_direct_and_size(storage->size());
+ delete storage;
+ } else {
+ // put everything into indirect storage
+ auto* storage = detail::storage<T>::alloc(new_capacity);
+ if (is_direct()) {
+ // direct -> indirect
+ uninitialized_move_and_destroy(data<direction::direct>(), storage->data(), size<direction::direct>());
+ storage->size(size<direction::direct>());
+ } else {
+ // indirect -> indirect
+ uninitialized_move_and_destroy(data<direction::indirect>(), storage->data(), size<direction::indirect>());
+ storage->size(size<direction::indirect>());
+ delete indirect();
+ }
+ set_indirect(storage);
+ }
+ }
+
+ /**
+ * @brief Doubles starting_capacity until it is >= size_to_fit.
+ */
+ [[nodiscard]] static auto calculate_new_capacity(size_t size_to_fit, size_t starting_capacity) -> size_t {
+ if (size_to_fit > max_size()) {
+ // not enough space
+ throw std::bad_alloc();
+ }
+
+ if (size_to_fit == 0) {
+ // special handling for 0 so N==0 works
+ return starting_capacity;
+ }
+ // start with at least 1, so N==0 works
+ auto new_capacity = std::max<size_t>(1, starting_capacity);
+
+ // double capacity until its large enough, but make sure we don't overflow
+ while (new_capacity < size_to_fit && new_capacity * 2 > new_capacity) {
+ new_capacity *= 2;
+ }
+ if (new_capacity < size_to_fit) {
+ // got an overflow, set capacity to max
+ new_capacity = max_size();
+ }
+ return std::min(new_capacity, max_size());
+ }
+
+ template <direction D>
+ [[nodiscard]] auto capacity() const -> size_t {
+ if constexpr (D == direction::direct) {
+ return N;
+ } else {
+ return indirect()->capacity();
+ }
+ }
+
+ template <direction D>
+ [[nodiscard]] auto size() const -> size_t {
+ if constexpr (D == direction::direct) {
+ return direct_size();
+ } else {
+ return indirect()->size();
+ }
+ }
+
+ template <direction D>
+ void set_size(size_t s) {
+ if constexpr (D == direction::direct) {
+ set_direct_and_size(s);
+ } else {
+ indirect()->size(s);
+ }
+ }
+
+ void set_size(size_t s) {
+ if (is_direct()) {
+ set_size<direction::direct>(s);
+ } else {
+ set_size<direction::indirect>(s);
+ }
+ }
+
+ template <direction D>
+ [[nodiscard]] auto data() -> T* {
+ if constexpr (D == direction::direct) {
+ return direct_data();
+ } else {
+ return indirect()->data();
+ }
+ }
+
+ template <direction D>
+ [[nodiscard]] auto data() const -> T const* {
+ return const_cast<svector*>(this)->data<D>(); // NOLINT(cppcoreguidelines-pro-type-const-cast)
+ }
+
+ template <direction D>
+ void pop_back() {
+ if constexpr (std::is_trivially_destructible_v<T>) {
+ set_size<D>(size<D>() - 1);
+ } else {
+ auto s = size<D>() - 1;
+ (data<D>() + s)->~T();
+ set_size<D>(s);
+ }
+ }
+
+ /**
+ * @brief We need variadic arguments so we can either use copy ctor or default ctor
+ */
+ template <direction D, class... Args>
+ void resize_after_reserve(size_t count, Args&&... args) {
+ auto current_size = size<D>();
+ if (current_size > count) {
+ if constexpr (!std::is_trivially_destructible_v<T>) {
+ auto* d = data<D>();
+ std::destroy(d + count, d + current_size);
+ }
+ } else {
+ auto* d = data<D>();
+ for (auto ptr = d + current_size, end = d + count; ptr != end; ++ptr) {
+ new (static_cast<void*>(ptr)) T(std::forward<Args>(args)...);
+ }
+ }
+ set_size<D>(count);
+ }
+
+ // Makes sure that to is not past the end iterator
+ template <direction D>
+ auto erase_checked_end(T const* cfrom, T const* to) -> T* {
+ auto* const erase_begin = const_cast<T*>(cfrom); // NOLINT(cppcoreguidelines-pro-type-const-cast)
+ auto* const container_end = data<D>() + size<D>();
+ auto* const erase_end = std::min(const_cast<T*>(to), container_end); // NOLINT(cppcoreguidelines-pro-type-const-cast)
+
+ std::move(erase_end, container_end, erase_begin);
+ auto const num_erased = std::distance(erase_begin, erase_end);
+ std::destroy(container_end - num_erased, container_end);
+ set_size<D>(size<D>() - num_erased);
+ return erase_begin;
+ }
+
+ template <typename It>
+ void assign(It first, It last, std::input_iterator_tag /*unused*/) {
+ clear();
+
+ // TODO this can be made faster, e.g. by setting size only when finished.
+ while (first != last) {
+ push_back(*first);
+ ++first;
+ }
+ }
+
+ template <typename It>
+ void assign(It first, It last, std::forward_iterator_tag /*unused*/) {
+ clear();
+
+ auto s = std::distance(first, last);
+ reserve(s);
+ std::uninitialized_copy(first, last, data());
+ set_size(s);
+ }
+
+ // precondition: all uninitialized
+ void do_move_assign(svector&& other) {
+ if (!other.is_direct()) {
+ // take other's memory, even when empty
+ set_indirect(other.indirect());
+ } else {
+ auto* other_ptr = other.data<direction::direct>();
+ auto s = other.size<direction::direct>();
+ auto* other_end = other_ptr + s;
+
+ std::uninitialized_move(other_ptr, other_end, data<direction::direct>());
+ std::destroy(other_ptr, other_end);
+ set_size(s);
+ }
+ other.set_direct_and_size(0);
+ }
+
+ /**
+ * @brief Shifts data [source_begin, source_end( to the right, starting on target_begin.
+ *
+ * Preconditions:
+ * * contiguous memory
+ * * source_begin <= target_begin
+ * * source_end onwards is uninitialized memory
+ *
+ * Destroys then empty elements in [source_begin, source_end(
+ */
+ static auto shift_right(T* source_begin, T* source_end, T* target_begin) {
+ // 1. uninitialized moves
+ auto const num_moves = std::distance(source_begin, source_end);
+ auto const target_end = target_begin + num_moves;
+ auto const num_uninitialized_move = std::min(num_moves, std::distance(source_end, target_end));
+ std::uninitialized_move(source_end - num_uninitialized_move, source_end, target_end - num_uninitialized_move);
+ std::move_backward(source_begin, source_end - num_uninitialized_move, target_end - num_uninitialized_move);
+ std::destroy(source_begin, std::min(source_end, target_begin));
+ }
+
+ template <direction D>
+ [[nodiscard]] auto make_uninitialized_space_new(size_t s, T* p, size_t count) -> T* {
+ auto target = svector();
+ // we know target is indirect because we're increasing capacity
+ target.reserve(s + count);
+
+ // move everything [begin, pos[
+ auto* target_pos = std::uninitialized_move(data<D>(), p, target.template data<direction::indirect>());
+
+ // move everything [pos, end]
+ std::uninitialized_move(p, data<D>() + s, target_pos + count);
+
+ target.template set_size<direction::indirect>(s + count);
+ *this = std::move(target);
+ return target_pos;
+ }
+
+ template <direction D>
+ [[nodiscard]] auto make_uninitialized_space(T const* pos, size_t count) -> T* {
+ auto* const p = const_cast<T*>(pos); // NOLINT(cppcoreguidelines-pro-type-const-cast)
+ auto s = size<D>();
+ if (s + count > capacity<D>()) {
+ return make_uninitialized_space_new<D>(s, p, count);
+ }
+
+ shift_right(p, data<D>() + s, p + count);
+ set_size<D>(s + count);
+ return p;
+ }
+
+ // makes space for uninitialized data of cout elements. Also updates size.
+ [[nodiscard]] auto make_uninitialized_space(T const* pos, size_t count) -> T* {
+ if (is_direct()) {
+ return make_uninitialized_space<direction::direct>(pos, count);
+ }
+ return make_uninitialized_space<direction::indirect>(pos, count);
+ }
+
+ void destroy() {
+ auto const is_dir = is_direct();
+ if constexpr (!std::is_trivially_destructible_v<T>) {
+ T* ptr = nullptr;
+ size_t s = 0;
+ if (is_dir) {
+ ptr = data<direction::direct>();
+ s = size<direction::direct>();
+ } else {
+ ptr = data<direction::indirect>();
+ s = size<direction::indirect>();
+ }
+ std::destroy_n(ptr, s);
+ }
+ if (!is_dir) {
+ delete indirect();
+ }
+ }
+
+ // performs a const_cast so we don't need this implementation twice
+ template <direction D>
+ auto at(size_t idx) -> T& {
+ if (idx >= size<D>()) {
+ throw std::out_of_range{"svector: idx out of range"};
+ }
+ auto* ptr = const_cast<T*>(data<D>() + idx); // NOLINT(cppcoreguidelines-pro-type-const-cast)
+ return *ptr;
+ } // LCOV_EXCL_LINE why is this single } marked as not covered? gcov bug?
+
+public:
+ using value_type = T;
+ using size_type = size_t;
+ using difference_type = std::ptrdiff_t;
+ using reference = value_type&;
+ using const_reference = value_type const&;
+ using pointer = T*;
+ using const_pointer = T const*;
+ using iterator = T*;
+ using const_iterator = T const*;
+ using reverse_iterator = std::reverse_iterator<iterator>;
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
+ svector() {
+ set_direct_and_size(0);
+ }
+
+ svector(size_t count, T const& value)
+ : svector() {
+ resize(count, value);
+ }
+
+ explicit svector(size_t count)
+ : svector() {
+ reserve(count);
+ if (is_direct()) {
+ resize_after_reserve<direction::direct>(count);
*** OUTPUT TRUNCATED, 4507 LINES SKIPPED ***
More information about the Commits
mailing list