KarrasRadixTree.hpp

Go to the documentation of this file.

// -------------------------------------------------------//
//
// SHAMROCK code for hydrodynamics
// Copyright (c) 2021-2026 Timothée David--Cléris <tim.shamrock@proton.me>
// SPDX-License-Identifier: CeCILL Free Software License Agreement v2.1
// Shamrock is licensed under the CeCILL 2.1 License, see LICENSE for more information
//
// -------------------------------------------------------//
 
#pragma once
 
#include "shambase/aliases_int.hpp"
#include "shambackends/DeviceBuffer.hpp"
#include "shambackends/DeviceScheduler.hpp"
#include "shamtree/KarrasTreeTraverser.hpp"
 
namespace shamtree {
 
    class KarrasRadixTree;
 
} // namespace shamtree
 
class shamtree::KarrasRadixTree {
 
    public:
    inline u32 get_internal_cell_count() const { return buf_lchild_id.get_size(); }
 
    inline u32 get_leaf_count() const { return get_internal_cell_count() + 1; }
 
    inline u32 get_total_cell_count() const { return get_internal_cell_count() + get_leaf_count(); }
 
    sham::DeviceBuffer<u32> buf_lchild_id;  
    sham::DeviceBuffer<u32> buf_rchild_id;  
    sham::DeviceBuffer<u8> buf_lchild_flag; 
    sham::DeviceBuffer<u8> buf_rchild_flag; 
    sham::DeviceBuffer<u32> buf_endrange;   
 
    u32 tree_depth;
 
    KarrasRadixTree(
        sham::DeviceBuffer<u32> &&buf_lchild_id,
        sham::DeviceBuffer<u32> &&buf_rchild_id,
        sham::DeviceBuffer<u8> &&buf_lchild_flag,
        sham::DeviceBuffer<u8> &&buf_rchild_flag,
        sham::DeviceBuffer<u32> &&buf_endrange,
        u32 tree_depth)
        : buf_lchild_id(std::move(buf_lchild_id)), buf_rchild_id(std::move(buf_rchild_id)),
          buf_lchild_flag(std::move(buf_lchild_flag)), buf_rchild_flag(std::move(buf_rchild_flag)),
          buf_endrange(std::move(buf_endrange)), tree_depth(tree_depth) {}
 
    inline KarrasTreeTraverser get_structure_traverser() const {
        return KarrasTreeTraverser{
            buf_lchild_id,
            buf_rchild_id,
            buf_lchild_flag,
            buf_rchild_flag,
            get_internal_cell_count()};
    }
 
    inline KarrasTreeTraverserHost get_structure_traverser_host() const {
        return KarrasTreeTraverserHost{
            buf_lchild_id.copy_to_stdvec(),
            buf_rchild_id.copy_to_stdvec(),
            buf_lchild_flag.copy_to_stdvec(),
            buf_rchild_flag.copy_to_stdvec(),
            get_internal_cell_count()};
    }
 
    static inline KarrasRadixTree make_empty(sham::DeviceScheduler_ptr dev_sched) {
        return KarrasRadixTree{
            sham::DeviceBuffer<u32>(0, dev_sched),
            sham::DeviceBuffer<u32>(0, dev_sched),
            sham::DeviceBuffer<u8>(0, dev_sched),
            sham::DeviceBuffer<u8>(0, dev_sched),
            sham::DeviceBuffer<u32>(0, dev_sched),
            0};
    }
 
    inline bool is_root_leaf() const { return get_internal_cell_count() == 0; }
};
 
namespace shamtree {
 
    template<class Tmorton>
    KarrasRadixTree karras_tree_from_morton_set(
        sham::DeviceScheduler_ptr dev_sched,
        u32 morton_count,
        sham::DeviceBuffer<Tmorton> &morton_codes,
        KarrasRadixTree &&recycled_tree);
 
    template<class Tmorton>
    KarrasRadixTree karras_tree_from_morton_set(
        sham::DeviceScheduler_ptr dev_sched,
        u32 morton_count,
        sham::DeviceBuffer<Tmorton> &morton_codes);
 
    std::string karras_tree_to_dot_graph(KarrasRadixTree &recycled_tree);
 
} // namespace shamtree