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