layout.hpp

Go to the documentation of this file.

#pragma once
 
#include <array>
#include <cstddef>
#include <tuple>
#include <type_traits>
#include <utility>
 
#include "../../slots/policies.hpp"
#include "erased_slot.hpp"
#include "policy.hpp"
#include "typed_slot.hpp"
 
namespace yorch::detail {
 
template <typename Plan, std::size_t... I>
[[nodiscard]] consteval auto make_payload_node_array(std::index_sequence<I...>) {
    return std::array<bool, sizeof...(I)> {
        (Plan::template output_storage_mode_for<I> == output_storage_mode::owned)...
    };
}
 
template <typename Plan, std::size_t... I>
[[nodiscard]] consteval auto make_slot_logical_policy_array(std::index_sequence<I...>) {
    return std::array<slot_logical_policy, sizeof...(I)> {
        Plan::template slot_logical_policy_for<I>...
    };
}
 
template <typename Plan>
inline constexpr auto payload_node_array_v =
    make_payload_node_array<Plan>(std::make_index_sequence<Plan::node_count> {});
 
template <typename Plan>
inline constexpr auto slot_logical_policy_array_v =
    make_slot_logical_policy_array<Plan>(std::make_index_sequence<Plan::node_count> {});
 
template <typename Plan>
inline constexpr std::size_t payload_node_count_v = [] {
    std::size_t count = 0;
    for (const bool payload : payload_node_array_v<Plan>) {
        if (payload) {
            ++count;
        }
    }
    return count;
}();
 
template <typename Plan>
[[nodiscard]] consteval auto make_one_to_one_physical_slot_indices() {
    std::array<std::size_t, Plan::node_count> indices {};
    indices.fill(no_physical_slot);
 
    std::size_t next = 0;
    for (std::size_t node = 0; node < Plan::node_count; ++node) {
        if (payload_node_array_v<Plan>[node]) {
            indices[node] = next++;
        }
    }
 
    return indices;
}
 
template <typename Plan>
struct compact_slot_index_layout {
    // Node -> physical slot mapping; non-owned nodes keep `no_physical_slot`.
    std::array<std::size_t, Plan::node_count> physical_slot_indices {};
    // Payload depth along each node's root-to-node path, including the node.
    std::array<std::size_t, Plan::node_count> payload_depths {};
    // Total physical slots needed, equal to the maximum payload depth.
    std::size_t physical_slot_count = 0;
};
 
template <typename Plan>
[[nodiscard]] consteval auto make_serial_dfs_compact_slot_layout() {
    compact_slot_index_layout<Plan> layout {};
    layout.physical_slot_indices.fill(no_physical_slot);
 
    for (std::size_t node = 0; node < Plan::node_count; ++node) {
        const auto parent = Plan::parent_indices[node];
        const auto parent_depth =
            parent == Plan::no_parent ? 0 : layout.payload_depths[parent];
        layout.payload_depths[node] =
            parent_depth + (payload_node_array_v<Plan>[node] ? 1U : 0U);
 
        if (payload_node_array_v<Plan>[node]) {
            layout.physical_slot_indices[node] = layout.payload_depths[node] - 1;
            if (layout.payload_depths[node] > layout.physical_slot_count) {
                layout.physical_slot_count = layout.payload_depths[node];
            }
        }
    }
 
    return layout;
}
 
constexpr slot_physical_policy join_slot_physical_policy(
    slot_physical_policy left,
    slot_logical_policy right) noexcept {
    if (right == slot_logical_policy::none) {
        return left;
    }
 
    if (left == slot_physical_policy::none) {
        return right == slot_logical_policy::must_payload
            ? slot_physical_policy::must_payload
            : slot_physical_policy::maybe_payload;
    }
 
    if (left == slot_physical_policy::maybe_payload ||
        right == slot_logical_policy::maybe_payload) {
        return slot_physical_policy::maybe_payload;
    }
 
    return slot_physical_policy::must_payload;
}
 
template <typename Plan, std::size_t PhysicalSlotCount, std::size_t... I>
[[nodiscard]] consteval auto make_physical_slot_sizes(
    const std::array<std::size_t, Plan::node_count>& indices,
    std::index_sequence<I...>) {
    std::array<std::size_t, PhysicalSlotCount> sizes {};
    ([&] {
        if constexpr (!std::is_void_v<typename Plan::template output_type<I>>) {
            const auto slot = indices[I];
            if (slot != no_physical_slot) {
                sizes[slot] = sizes[slot] < sizeof(typename Plan::template output_type<I>)
                    ? sizeof(typename Plan::template output_type<I>)
                    : sizes[slot];
            }
        }
    }(), ...);
    return sizes;
}
 
template <typename Plan, std::size_t PhysicalSlotCount, std::size_t... I>
[[nodiscard]] consteval auto make_physical_slot_alignments(
    const std::array<std::size_t, Plan::node_count>& indices,
    std::index_sequence<I...>) {
    std::array<std::size_t, PhysicalSlotCount> alignments {};
    ([&] {
        if constexpr (!std::is_void_v<typename Plan::template output_type<I>>) {
            const auto slot = indices[I];
            if (slot != no_physical_slot) {
                alignments[slot] = alignments[slot] < alignof(typename Plan::template output_type<I>)
                    ? alignof(typename Plan::template output_type<I>)
                    : alignments[slot];
            }
        }
    }(), ...);
    return alignments;
}
 
template <typename Plan, std::size_t PhysicalSlotCount, std::size_t... I>
[[nodiscard]] consteval auto make_physical_slot_policies(
    const std::array<std::size_t, Plan::node_count>& indices,
    std::index_sequence<I...>) {
    std::array<slot_physical_policy, PhysicalSlotCount> policies {};
    policies.fill(slot_physical_policy::none);
    (((indices[I] != no_physical_slot)
          ? policies[indices[I]] = join_slot_physical_policy(
                policies[indices[I]],
                Plan::template slot_logical_policy_for<I>)
          : slot_physical_policy::none),
     ...);
    return policies;
}
 
template <typename Plan, typename LayoutPolicy>
struct plan_slot_layout;
 
template <typename Plan>
struct plan_slot_layout<Plan, yorch::slot_layout_one_to_one_policy> {
    static constexpr auto physical_slot_indices =
        make_one_to_one_physical_slot_indices<Plan>();
    static constexpr std::size_t physical_slot_count = payload_node_count_v<Plan>;
    static constexpr auto physical_slot_sizes =
        make_physical_slot_sizes<Plan, physical_slot_count>(
            physical_slot_indices,
            std::make_index_sequence<Plan::node_count> {});
    static constexpr auto physical_slot_alignments =
        make_physical_slot_alignments<Plan, physical_slot_count>(
            physical_slot_indices,
            std::make_index_sequence<Plan::node_count> {});
    static constexpr auto physical_slot_policies =
        make_physical_slot_policies<Plan, physical_slot_count>(
            physical_slot_indices,
            std::make_index_sequence<Plan::node_count> {});
 
    template <std::size_t I>
    static constexpr std::size_t physical_slot_index = physical_slot_indices[I];
 
    template <std::size_t K>
    static constexpr slot_physical_policy physical_slot_policy = physical_slot_policies[K];
};
 
template <typename Plan>
struct plan_slot_layout<Plan, yorch::slot_layout_serial_dfs_compact_policy> {
    static constexpr auto compact_layout =
        make_serial_dfs_compact_slot_layout<Plan>();
    static constexpr auto physical_slot_indices = compact_layout.physical_slot_indices;
    static constexpr auto payload_depths = compact_layout.payload_depths;
    static constexpr std::size_t physical_slot_count = compact_layout.physical_slot_count;
    static constexpr auto physical_slot_sizes =
        make_physical_slot_sizes<Plan, physical_slot_count>(
            physical_slot_indices,
            std::make_index_sequence<Plan::node_count> {});
    static constexpr auto physical_slot_alignments =
        make_physical_slot_alignments<Plan, physical_slot_count>(
            physical_slot_indices,
            std::make_index_sequence<Plan::node_count> {});
    static constexpr auto physical_slot_policies =
        make_physical_slot_policies<Plan, physical_slot_count>(
            physical_slot_indices,
            std::make_index_sequence<Plan::node_count> {});
 
    template <std::size_t I>
    static constexpr std::size_t physical_slot_index = physical_slot_indices[I];
 
    template <std::size_t K>
    static constexpr slot_physical_policy physical_slot_policy = physical_slot_policies[K];
};
 
template <typename Layout, std::size_t... K>
[[nodiscard]] auto make_erased_slots_tuple(std::index_sequence<K...>)
    -> std::tuple<erased_slot<
        Layout::physical_slot_sizes[K],
        Layout::physical_slot_alignments[K],
        Layout::template physical_slot_policy<K>>...>;
 
template <typename Layout>
using plan_erased_slots_tuple_t =
    decltype(make_erased_slots_tuple<Layout>(
        std::make_index_sequence<Layout::physical_slot_count> {}));
 
template <typename Plan, std::size_t PhysicalSlot>
[[nodiscard]] consteval std::size_t one_to_one_physical_slot_owner_node() {
    constexpr auto indices = make_one_to_one_physical_slot_indices<Plan>();
    for (std::size_t node = 0; node < Plan::node_count; ++node) {
        if (indices[node] == PhysicalSlot) {
            return node;
        }
    }
 
    return no_physical_slot;
}
 
template <typename Plan, std::size_t... K>
[[nodiscard]] auto make_typed_slots_tuple(std::index_sequence<K...>)
    -> std::tuple<typed_slot<
        typename Plan::template output_type<one_to_one_physical_slot_owner_node<Plan, K>()>,
        Plan::template slot_logical_policy_for<one_to_one_physical_slot_owner_node<Plan, K>()>>...>;
 
template <typename Plan>
using plan_typed_slots_tuple_t =
    decltype(make_typed_slots_tuple<Plan>(
        std::make_index_sequence<payload_node_count_v<Plan>> {}));
 
template <typename Plan, std::size_t I>
concept payload_node =
    Plan::template output_storage_mode_for<I> == output_storage_mode::owned;
 
} // namespace yorch::detail