stringzilla 5.0.7

/**
 *  @brief Shared definitions for the StringZillas C++ library.
 *  @file include/stringzillas/types.hpp
 *  @author Ash Vardanian
 */
#ifndef STRINGZILLAS_TYPES_HPP_
#define STRINGZILLAS_TYPES_HPP_

#include <thread>   // `std::thread::hardware_concurrency`
#include <atomic>   // `std::atomic`, `std::memory_order`
#include <concepts> // `std::convertible_to`, `std::same_as`
#include <cstdlib>  // `std::malloc`, `std::free`
#include <memory>   // `std::addressof`

#include <forkunion.h> // `fu_pool_t`, `fu_topology_t`, capability-dispatched parallel loops

#include "stringzilla/types.hpp"

namespace ashvardanian {
namespace stringzillas {

using namespace ashvardanian::stringzilla;

enum bytes_per_cell_t : unsigned {
    zero_bytes_per_cell_k = 0,
    one_byte_per_cell_k = 1,
    two_bytes_per_cell_k = 2,
    four_bytes_per_cell_k = 4,
    eight_bytes_per_cell_k = 8,
};

struct dummy_mutex_t {
    constexpr void lock() noexcept {}
    constexpr void unlock() noexcept {}
};

/** @brief Minimal test-and-set spin lock guarding the executors' rare cross-thread merges; `lock_guard`-compatible. */
class spin_mutex_t {
    std::atomic<bool> locked_ {false};

  public:
    void lock() noexcept {
        while (locked_.exchange(true, std::memory_order_acquire)) {}
    }
    void unlock() noexcept { locked_.store(false, std::memory_order_release); }
};

/**
 *  @brief A `status_t` shared by parallel workers: keeps the @b first failure and lets the others bail out early.
 *
 *  Relaxed throughout, as the pool's join already establishes happens-before between the workers and the caller.
 *  Assigning @b success_k is a no-op, so the success path never writes to the shared line.
 */
struct atomic_status_t {
    std::atomic<status_t> status_ {status_t::success_k};

    atomic_status_t() = default;
    atomic_status_t(atomic_status_t const &) = delete;
    atomic_status_t &operator=(atomic_status_t const &) = delete;

    operator status_t() const noexcept { return status_.load(std::memory_order_relaxed); }
    atomic_status_t &operator=(status_t status) noexcept {
        if (status == status_t::success_k) return *this; // ? The flag starts here; never write it back.
        status_t expected = status_t::success_k;
        status_.compare_exchange_strong(expected, status, std::memory_order_relaxed, std::memory_order_relaxed);
        return *this;
    }
};

/**
 *  @brief Simple RAII lock guard analog to `std::lock_guard` for C++11 compatibility.
 *      Automatically locks the mutex on construction and unlocks on destruction.
 */
template <typename mutex_type_>
class lock_guard {
    mutex_type_ &mutex_;

  public:
    explicit lock_guard(mutex_type_ &mutex) noexcept : mutex_(mutex) { mutex_.lock(); }
    ~lock_guard() noexcept { mutex_.unlock(); }

    lock_guard(lock_guard &&) = delete;
    lock_guard(lock_guard const &) = delete;
    lock_guard &operator=(lock_guard &&) = delete;
    lock_guard &operator=(lock_guard const &) = delete;
};

struct dummy_prong_t {
    std::size_t task = 0;
    std::size_t thread = 0;

    operator std::size_t() const noexcept { return task; }
};

/**
 *  @brief C++17-compatible equivalent of std::remove_cvref (which was added in C++20).
 *      Removes const, volatile, and reference qualifiers from a type.
 */
template <typename type_>
using remove_cvref = typename std::remove_cv<typename std::remove_reference<type_>::type>::type;

struct dummy_executor_t {
    using prong_t = dummy_prong_t;
    using mutex_t = dummy_mutex_t;

    constexpr size_t threads_count() const noexcept { return 1; }
    constexpr mutex_t make_mutex() const noexcept { return {}; }

    /**
     *  @brief Calls the @p function for each index from 0 to @p (n) in such
     *      a way that consecutive elements are likely to be processed by
     *      the same thread.
     */
    template <typename function_type_>
    inline void for_n(size_t n, function_type_ &&function) const noexcept {
        for (size_t i = 0; i < n; ++i) function(dummy_prong_t {i, 0});
    }

    /**
     *  @brief Calls the @p function on each thread propagating a 2 indices
     *      to the function. The first index is the start of the range
     *      and the second index is the exclusive end of the range to be
     *      handled by a particular thread.
     */
    template <typename function_type_>
    inline void for_slices(size_t n, function_type_ &&function) const noexcept {
        function(0, n);
    }

    /**
     *  @brief Calls the @p function for each index from 0 to @p (n) expecting
     *      that individual invocations can have drastically different duration,
     *      so each thread eagerly processes the next index in the range.
     */
    template <typename function_type_>
    inline void for_n_dynamic(size_t n, function_type_ &&function) const noexcept {
        for (size_t i = 0; i < n; ++i) function(dummy_prong_t {i, 0});
    }

    /**
     *  @brief Executes a function in parallel on the current and all worker threads.
     *  @param[in] function The callback, receiving the thread index as an argument.
     */
    template <typename function_type_>
    void for_threads(function_type_ &&function) noexcept {
        function(0);
    }
};

/**
 *  @brief Adapts a ForkUnion pool, consumed through its C API, to the `executor_like` shape the engines
 *      are templated on. The compiled ForkUnion runtime performs the capability dispatch (NUMA-aware
 *      placement, colocated scheduling, huge pages) behind the opaque `fu_pool_t` handle, so consumer
 *      translation units never instantiate its C++ core.
 */
class forkunion_executor_t {
    fu_topology_t topology_ = nullptr;
    fu_pool_t pool_ = nullptr;

  public:
    using prong_t = dummy_prong_t;
    using mutex_t = spin_mutex_t;

    forkunion_executor_t() noexcept = default;
    forkunion_executor_t(forkunion_executor_t const &) = delete;
    forkunion_executor_t &operator=(forkunion_executor_t const &) = delete;
    forkunion_executor_t(forkunion_executor_t &&) = delete;
    forkunion_executor_t &operator=(forkunion_executor_t &&) = delete;

    ~forkunion_executor_t() noexcept {
        if (pool_) fu_pool_delete(pool_);
        if (topology_) fu_topology_delete(topology_);
    }

    /** @brief Logical cores the process may actually use (affinity mask, cgroup cpuset), per the ForkUnion topology. */
    static size_t allowed_cores_count() noexcept {
        fu_topology_t topology = fu_topology_new();
        if (!topology) return 0;
        size_t const count = fu_logical_cores_count(topology);
        fu_topology_delete(topology);
        return count;
    }

    /** @brief Spawns @p threads workers (the caller included) over the detected machine topology. */
    status_t try_spawn(size_t threads) noexcept {
        topology_ = fu_topology_new();
        pool_ = fu_pool_new("stringzillas", fu_capabilities_all_k);
        if (!topology_ || !pool_) return status_t::bad_alloc_k;
        if (!fu_pool_spawn(topology_, pool_, threads, fu_caller_inclusive_k)) return status_t::bad_alloc_k;
        return status_t::success_k;
    }

    size_t threads_count() const noexcept { return fu_pool_threads_count(pool_); }
    mutex_t make_mutex() const noexcept { return {}; }

    /**
     *  @brief Calls the @p function for each index from 0 to @p (n) in such
     *      a way that consecutive elements are likely to be processed by
     *      the same thread.
     */
    template <typename function_type_>
    void for_n(size_t n, function_type_ &&function) const noexcept {
        using function_t = typename std::remove_reference<function_type_>::type;
        fu_pool_for_n(
            pool_, n,
            [](fu_lambda_context_t context, size_t task, size_t thread, size_t) noexcept {
                (*reinterpret_cast<function_t *>(context))(prong_t {task, thread});
            },
            const_cast<function_t *>(std::addressof(function)));
    }

    /**
     *  @brief Calls the @p function for each index from 0 to @p (n) expecting
     *      that individual invocations can have drastically different duration,
     *      so each thread eagerly steals the next index in the range.
     */
    template <typename function_type_>
    void for_n_dynamic(size_t n, function_type_ &&function) const noexcept {
        using function_t = typename std::remove_reference<function_type_>::type;
        fu_pool_for_n_dynamic(
            pool_, n,
            [](fu_lambda_context_t context, size_t task, size_t thread, size_t) noexcept {
                (*reinterpret_cast<function_t *>(context))(prong_t {task, thread});
            },
            const_cast<function_t *>(std::addressof(function)));
    }

    /**
     *  @brief Calls the @p function on each thread propagating 2 indices to the
     *      function: the inclusive start and the exclusive end of the sub-range
     *      handled by that thread.
     */
    template <typename function_type_>
    void for_slices(size_t n, function_type_ &&function) const noexcept {
        using function_t = typename std::remove_reference<function_type_>::type;
        fu_pool_for_slices(
            pool_, n,
            [](fu_lambda_context_t context, size_t first, size_t count, size_t, size_t) noexcept {
                (*reinterpret_cast<function_t *>(context))(first, first + count);
            },
            const_cast<function_t *>(std::addressof(function)));
    }

    /**
     *  @brief Executes a function in parallel on the current and all worker threads.
     *  @param[in] function The callback, receiving the thread index as an argument.
     */
    template <typename function_type_>
    void for_threads(function_type_ &&function) const noexcept {
        using function_t = typename std::remove_reference<function_type_>::type;
        fu_pool_for_threads(
            pool_,
            [](fu_lambda_context_t context, size_t thread, size_t) noexcept {
                (*reinterpret_cast<function_t *>(context))(thread);
            },
            const_cast<function_t *>(std::addressof(function)));
    }
};

#if SZ_HAS_CONCEPTS_

template <typename executor_type_>
concept executor_like = requires(std::remove_reference_t<executor_type_> &executor) {
    { executor.threads_count() } -> std::convertible_to<size_t>;
    typename std::remove_reference_t<executor_type_>::prong_t;
};

template <typename results_type_>
concept indexed_results_like = requires(results_type_ results, size_t i) {
    { results[i] };
};

template <typename results_type_>
concept strided_results_like = requires(results_type_ results) {
    { results.data };
    { results.row_stride };
};

#endif

/** @brief Type trait to extract the value type from indexed results. */
template <typename results_type_>
struct indexed_results_type {
    using clean_type = typename std::remove_reference<results_type_>::type;
    using type = typename clean_type::value_type;
};

template <typename value_type_>
struct indexed_results_type<value_type_ *> {
    using type = value_type_;
};

template <typename value_type_>
struct indexed_results_type<value_type_ *&> {
    using type = value_type_;
};

/**
 *  @brief Row-major, query-major strided view of an output distance/score matrix.
 *
 *  The cross-product similarity engines score `rows` queries against `columns` candidates and write cell
 *  `(query_index, candidate_index)` to `data[query_index * row_stride + candidate_index]`, with
 *  `row_stride >= columns` elements between consecutive query rows (so callers can embed the matrix in a wider
 *  allocation). For symmetric self-similarity `rows == columns` and both triangles are filled.
 */
template <typename value_type_>
struct strided_rows {
    using value_type = value_type_;
    value_type_ *data = nullptr;
    size_t rows = 0;
    size_t columns = 0;
    size_t row_stride = 0;

    constexpr value_type_ *row(size_t query_index) const noexcept { return data + query_index * row_stride; }
};

/**
 *  @brief How a cross-product similarity call pairs its two input sets.
 *
 *  @b all_pairs_k scores every query against every candidate (a full `queries × candidates` matrix).
 *  @b symmetric_k scores one set against itself: only the lower triangle (incl. the diagonal) is computed and
 *  then mirrored into the upper triangle, halving the work for self-similarity matrices.
 */
enum class cross_similarities_t {
    all_pairs_k,
    symmetric_k,
};

/**
 *  @brief Column-major (transposed) view of a block of candidate strings scored against one shared query.
 *
 *  The inter-sequence (`sz_packing_candidates_across_lanes_k`) kernels place one candidate per SIMD lane and
 *  advance the Dynamic Programming matrix row-by-row, so they need character @p position across all lanes
 *  contiguously. We therefore store the block @b transposed: the character at @p position of lane
 *  @p lane_index lives at `transposed[position * lane_capacity + lane_index]`. A block holds up to
 *  @p lane_capacity candidates (64 for 8-bit cells, 32 for 16-bit); @p lanes_count counts the live lanes, the
 *  rest being a masked tail. @p lengths gives each lane's candidate length so the walker can latch that lane's
 *  result at its own final column, and @p longest_candidate bounds the row count of the walk.
 */
template <typename char_type_>
struct candidate_lanes_block {
    char_type_ const *transposed = nullptr;
    size_t lane_capacity = 0;        // ? SIMD width: 64 (u8), 32 (u16); also the transpose stride.
    size_t lanes_count = 0;          // ? Live candidates in this block, `<= lane_capacity` (tail underfills).
    size_t const *lengths = nullptr; // ? Per-lane candidate length, indexed by `lane_index`.
    size_t longest_candidate = 0;    // ? Max length across live lanes; the number of DP rows to walk.

    constexpr char_type_ const *position(size_t position_index) const noexcept {
        return transposed + position_index * lane_capacity;
    }
    constexpr char_type_ character_of_lane(size_t lane_index, size_t position_index) const noexcept {
        return transposed[position_index * lane_capacity + lane_index];
    }
};

/**
 *  @brief A batch of independent `(shorter, longer)` string pairs for one inter-sequence bit-parallel Myers launch -
 *      one pair per SIMD lane. The kernels score every lane's pair in lockstep; `positions[lane_index]` maps a lane
 *      to its destination slot in the caller's results writer. The active lane count is `shorters.size()`.
 */
template <typename char_type_>
struct lane_pairs_view {
    span<span<char_type_ const> const> shorters;
    span<span<char_type_ const> const> longers;
    span<size_t const> positions;

    constexpr size_t lanes_count() const noexcept { return shorters.size(); }
};

/**
 *  @brief An example of an executor that uses OpenMP for parallel execution.
 *  @note Fork Union is preferred over this for library builds, but this is useful for users already leveraging OpenMP.
 */
struct openmp_executor_t {
    using prong_t = std::size_t;

    /**
     *  @brief Calls the @p function for each index from 0 to @p (n) in such
     *      a way that consecutive elements are likely to be processed by
     *      the same thread.
     */
    template <typename function_type_>
    inline void for_n(size_t n, function_type_ &&function) const noexcept {
#pragma omp parallel for
        for (size_t i = 0; i < n; ++i) function(i);
    }

    /**
     *  @brief Calls the @p function on each thread propagating a 2 indices
     *      to the function. The first index is the start of the range
     *      and the second index is the exclusive end of the range to be
     *      handled by a particular thread.
     */
    template <typename function_type_>
    inline void for_slices(size_t n, function_type_ &&function) const noexcept {
        // OpenMP won't use more threads than the number of available cores
        // and by using STL to query that number, we avoid the need to link
        // against OpenMP libraries.
        size_t const total_threads = std::thread::hardware_concurrency();
        size_t const chunk_size = divide_round_up(n, total_threads);
#pragma omp parallel for schedule(static, 1)
        for (size_t i = 0; i < total_threads; ++i) {
            size_t const start = i * chunk_size;
            size_t const end = std::min(start + chunk_size, n);
            function(start, end);
        }
    }

    /**
     *  @brief Calls the @p function for each index from 0 to @p (n) expecting
     *      that individual invocations can have drastically different duration,
     *      so each thread eagerly processes the next index in the range.
     */
    template <typename function_type_>
    inline void for_n_dynamic(size_t n, function_type_ &&function) const noexcept {
#pragma omp parallel for schedule(dynamic, 1)
        for (size_t i = 0; i < n; ++i) function(i);
    }

    /**
     *  @brief Executes a function in parallel on the current and all worker threads.
     *  @param[in] function The callback, receiving the thread index as an argument.
     */
    template <typename function_type_>
    void for_threads(function_type_ const &function) noexcept {
        // ! Using the `omp_get_thread_num()` would force us to include the OpenMP headers
        // ! and link to the right symbols, which is not always possible.
        std::atomic<size_t> atomic_thread_index = 0;
#pragma omp parallel
        {
            size_t const thread_index = atomic_thread_index.fetch_add(1, std::memory_order_relaxed);
            function(thread_index);
        }
    }

    inline size_t threads_count() const noexcept {
        // ! Using the `omp_get_num_threads()` would force us to include the OpenMP headers
        // ! and link to the right symbols, which is not always possible.
        std::atomic<size_t> atomic_thread_index = 0;
#pragma omp parallel
        { atomic_thread_index.fetch_add(1, std::memory_order_relaxed); }
        return atomic_thread_index.load(std::memory_order_relaxed);
    }
};

#if SZ_HAS_CONCEPTS_
static_assert(executor_like<dummy_executor_t>);
static_assert(executor_like<openmp_executor_t>);
static_assert(!executor_like<int>);

template <typename continuous_type_>
concept continuous_like = requires(continuous_type_ container) {
    { container.data() } -> std::same_as<typename continuous_type_::value_type *>;
    { container.size() } -> std::convertible_to<size_t>;
};

static_assert(continuous_like<span<char>>);
static_assert(!continuous_like<int>);
#endif

/**
 *  @brief A function that takes a range of elements and a @p callback function and groups the elements
 *      that @p equality function considers equal. Analogous to `std::ranges::group_by`.
 *  @return The number of groups formed.
 */
template <typename begin_iterator_type_, typename end_iterator_type_, typename equality_type_,
          typename slice_callback_type_>
size_t group_by(begin_iterator_type_ const begin, end_iterator_type_ const end, equality_type_ &&equality,
                slice_callback_type_ &&slice_callback) {

    auto slice_start = begin;
    size_t group_count = 0;

    while (slice_start != end) {
        // Find the end of the current group by advancing `slice_end`
        auto slice_end = slice_start + 1;
        while (slice_end != end && equality(*slice_start, *slice_end)) ++slice_end;
        slice_callback(slice_start, slice_end);
        group_count++;
        // Move `slice_start` to the beginning of the next potential group
        slice_start = slice_end;
    }

    return group_count;
}

/**
 *  @brief Safer alternative to `std::vector`, that avoids exceptions, copy constructors,
 *      and provides alternative `try_push_back` and `try_reserve` for faulty memory allocations.
 */
template <typename value_type_, typename allocator_type_>
class safe_vector {
  public:
    using value_type = value_type_;
    using size_type = std::size_t;
    using allocator_type = allocator_type_;

    using allocator_traits = std::allocator_traits<allocator_type>;
    using allocated_type = typename allocator_traits::value_type;
    static_assert(sizeof(value_type) == sizeof(allocated_type),
                  "Allocator value type must be the same size as the vector value type");
    static_assert(allocator_traits::propagate_on_container_move_assignment::value,
                  "Allocator must propagate on move assignment, otherwise the move assignment won't be `noexcept`.");

  private:
    value_type *data_;
    size_type size_;
    size_type capacity_;
    allocator_type alloc_;

    /**
     *  @brief Whether the host may dereference what @ref allocator_type hands out, which growing requires.
     *
     *  Growth moves live elements on the host, so an allocator over memory the host cannot touch opts out with
     *  `static constexpr bool host_accessible_k = false` and gets a build error here instead of a segmentation fault
     *  (see `device_alloc` in `stringzillas/types.cuh`). Allocators that say nothing - `std::allocator` included -
     *  are assumed reachable, so nothing else needs changing.
     *
     *  @note Detected by overload resolution rather than a `requires` expression: this header is compiled at
     *        C++17 by the Python extension, where concepts are unavailable.
     */
    template <typename probed_type_>
    static constexpr bool allocator_host_accessible_(decltype(probed_type_::host_accessible_k) *) noexcept {
        return probed_type_::host_accessible_k;
    }
    template <typename probed_type_>
    static constexpr bool allocator_host_accessible_(...) noexcept {
        return true;
    }
    static constexpr bool allocator_reachable_from_host_() noexcept {
        return allocator_host_accessible_<allocator_type>(nullptr);
    }

  public:
    safe_vector() noexcept : data_(nullptr), size_(0), capacity_(0), alloc_() {}
    safe_vector(allocator_type alloc) noexcept : data_(nullptr), size_(0), capacity_(0), alloc_(alloc) {}
    ~safe_vector() noexcept { reset(); }

    void clear() noexcept {
        if constexpr (!std::is_trivially_destructible<value_type>::value)
            for (size_type i = 0; i < size_; ++i) data_[i].~value_type();
        size_ = 0;
    }

    void reset() noexcept {
        clear();
        if (data_) alloc_.deallocate((allocated_type *)data_, capacity_);
        data_ = nullptr;
        size_ = 0;
        capacity_ = 0;
    }

    /** @warning Use `try_assign` instead to handle out-of-memory failures. */
    safe_vector(safe_vector const &other) = delete;
    /** @warning Use `try_assign` instead to handle out-of-memory failures. */
    safe_vector &operator=(safe_vector const &other) = delete;

    safe_vector(safe_vector &&other) noexcept
        : data_(other.data_), size_(other.size_), capacity_(other.capacity_), alloc_(std::move(other.alloc_)) {
        other.data_ = nullptr;
        other.size_ = 0;
        other.capacity_ = 0;
    }

    safe_vector &operator=(safe_vector &&other) noexcept {
        if (this != &other) {
            clear();
            if (data_) alloc_.deallocate((allocated_type *)data_, capacity_);
            data_ = other.data_;
            size_ = other.size_;
            capacity_ = other.capacity_;
            alloc_ = std::move(other.alloc_);
            other.data_ = nullptr;
            other.size_ = 0;
            other.capacity_ = 0;
        }
        return *this;
    }

    status_t try_assign(span<value_type const> const other) noexcept {
        reset();

        if (other.size() == 0) return status_t::success_k; // Nothing to do :)

        // Allocate exact needed capacity
        size_type new_cap = other.size();
        allocated_type *raw = allocator_traits::allocate(alloc_, new_cap);
        if (!raw) return status_t::bad_alloc_k;
        data_ = reinterpret_cast<value_type *>(raw);
        capacity_ = new_cap;

        // Copy‐construct each element
        if constexpr (!std::is_trivially_constructible<value_type>::value)
            for (size_type i = 0; i < other.size(); ++i) new (data_ + i) value_type(other[i]);
        else
            for (size_type i = 0; i < other.size(); ++i) data_[i] = other[i];
        size_ = other.size();
        return status_t::success_k;
    }

    template <typename other_allocator_type_ = allocator_type>
    status_t try_assign(safe_vector<value_type, other_allocator_type_> const &other) noexcept {
        if constexpr (allocator_traits::propagate_on_container_copy_assignment::value) alloc_ = other.alloc_;
        return try_assign(span<value_type>(other.data(), other.size()));
    }

    status_t try_reserve(size_type new_cap) noexcept {
        static_assert(allocator_reachable_from_host_(),
                      "Growing host-moves live elements, so device-only storage must use `try_resize_uninitialized`");
        if (new_cap <= capacity_) return status_t::success_k;
        value_type *new_data = (value_type *)alloc_.allocate(new_cap);
        if (!new_data) return status_t::bad_alloc_k;
        for (size_type i = 0; i < size_; ++i) {
            new (new_data + i) value_type(std::move(data_[i]));
            if constexpr (!std::is_trivially_destructible<value_type>::value) data_[i].~value_type();
        }
        if (data_) alloc_.deallocate((allocated_type *)data_, capacity_);
        data_ = new_data;
        capacity_ = new_cap;
        return status_t::success_k;
    }

    status_t try_resize(size_type new_size) noexcept {
        if (new_size > capacity_ && try_reserve(new_size) != status_t::success_k) return status_t::bad_alloc_k;

        if (new_size > size_) {
            if constexpr (!std::is_trivially_constructible<value_type>::value)
                for (size_type i = size_; i < new_size; ++i) new (data_ + i) value_type();
        }
        else if (new_size < size_) {
            if constexpr (!std::is_trivially_destructible<value_type>::value)
                for (size_type i = new_size; i < size_; ++i) data_[i].~value_type();
        }

        size_ = new_size;
        return status_t::success_k;
    }

    /**
     *  @brief Resizes WITHOUT constructing, destroying, or moving any element - the caller guarantees to overwrite
     *         every live element before reading it. On growth it allocates fresh storage and discards the old
     *         contents (no element move), so it is safe even when the storage lives in @b device memory the host
     *         cannot dereference (e.g. a `device_alloc`-backed task array). Requires a trivially-destructible type.
     */
    status_t try_resize_uninitialized(size_type new_size) noexcept {
        static_assert(std::is_trivially_destructible<value_type>::value,
                      "try_resize_uninitialized requires a trivially-destructible value type");
        if (new_size > capacity_) {
            value_type *new_data = (value_type *)alloc_.allocate(new_size);
            if (!new_data) return status_t::bad_alloc_k;
            if (data_) alloc_.deallocate((allocated_type *)data_, capacity_);
            data_ = new_data;
            capacity_ = new_size;
        }
        size_ = new_size;
        return status_t::success_k;
    }

    status_t try_push_back(value_type const &val) noexcept {
        if (size_ == capacity_) {
            size_type new_cap = capacity_ ? capacity_ * 2 : 1;
            if (try_reserve(new_cap) != status_t::success_k) return status_t::bad_alloc_k;
        }
        new (data_ + size_) value_type(val);
        ++size_;
        return status_t::success_k;
    }

    status_t try_push_back(value_type &&val) noexcept {
        if (size_ == capacity_) {
            size_type new_cap = capacity_ ? capacity_ * 2 : 1;
            if (try_reserve(new_cap) != status_t::success_k) return status_t::bad_alloc_k;
        }
        new (data_ + size_) value_type(std::move(val));
        ++size_;
        return status_t::success_k;
    }

    status_t try_append(span<value_type const> source) noexcept {
        size_type needed = size_ + source.size();
        if (needed > capacity_) {
            size_type new_cap = capacity_ ? capacity_ : 1;
            while (new_cap < needed) new_cap *= 2;
            if (try_reserve(new_cap) != status_t::success_k) return status_t::bad_alloc_k;
        }
        for (size_type i = 0; i < source.size(); ++i) new (data_ + size_ + i) value_type(source[i]);
        size_ = needed;
        return status_t::success_k;
    }

    value_type *begin() noexcept { return data_; }
    value_type const *begin() const noexcept { return data_; }
    value_type *end() noexcept { return data_ + size_; }
    value_type const *end() const noexcept { return data_ + size_; }
    value_type &operator[](size_type i) noexcept {
        sz_assert_(i < size_);
        return data_[i];
    }
    value_type const &operator[](size_type i) const noexcept {
        sz_assert_(i < size_);
        return data_[i];
    }
    value_type *data() noexcept { return data_; }
    value_type const *data() const noexcept { return data_; }
    value_type &front() noexcept {
        sz_assert_(size_ != 0);
        return data_[0];
    }
    value_type const &front() const noexcept {
        sz_assert_(size_ != 0);
        return data_[0];
    }
    value_type &back() noexcept {
        sz_assert_(size_ != 0);
        return data_[size_ - 1];
    }
    value_type const &back() const noexcept {
        sz_assert_(size_ != 0);
        return data_[size_ - 1];
    }
    size_type size() const noexcept { return size_; }
    size_type capacity() const noexcept { return capacity_; }
    operator span<value_type>() noexcept { return {data_, size_}; }
    operator span<value_type const>() const noexcept { return {data_, size_}; }
};

} // namespace stringzillas
} // namespace ashvardanian

#endif // STRINGZILLAS_TYPES_HPP_