65 using Node = PatchTree::Node;
69 constexpr u64 omp_min_lookups = 1U << 16;
70 constexpr u64 omp_min_nodes = 1U << 17;
73 struct SerialTreeLayout {
75 std::vector<const Node *> nodes;
77 std::vector<u64> first_child_ids;
79 std::vector<u64> roots_ids;
89 SerialTreeLayout make_breadth_first_layout(
const PatchTree &ptree) {
90 SerialTreeLayout layout;
91 auto &nodes = layout.nodes;
92 auto &first_child_ids = layout.first_child_ids;
97 std::vector<u8> is_leaf;
99 nodes.reserve(ptree.tree.size());
100 first_child_ids.reserve(ptree.tree.size());
101 is_leaf.reserve(ptree.tree.size());
103 for (
u64 root_key : ptree.roots_id) {
104 const Node &root = ptree.tree.at(root_key);
105 layout.roots_ids.push_back(nodes.size());
106 nodes.push_back(&root);
107 is_leaf.push_back(root.tree_node.is_leaf);
112 u64 level_end = nodes.size();
113 while (level_begin < level_end) {
116 u64 next_level_end = level_end;
117 for (
u64 i = level_begin; i < level_end; i++) {
119 first_child_ids.push_back(
u64_max);
121 first_child_ids.push_back(next_level_end);
125 nodes.resize(next_level_end);
126 is_leaf.resize(next_level_end);
129 bool missing_child =
false;
130#pragma omp parallel for if (next_level_end - level_end > omp_min_lookups) \
131 reduction(|| : missing_child)
132 for (
u64 i = level_begin; i < level_end; i++) {
133 if (first_child_ids[i] ==
u64_max) {
136 for (
u32 c = 0; c < 8; c++) {
137 auto it = ptree.tree.find(nodes[i]->tree_node.childs_nid[c]);
138 if (it == ptree.tree.end()) {
139 missing_child =
true;
142 nodes[first_child_ids[i] + c] = &it->second;
143 is_leaf[first_child_ids[i] + c] = it->second.tree_node.is_leaf;
148 "a child referenced in the patch tree is not in the tree");
151 level_begin = level_end;
152 level_end = next_level_end;
161void SerialPatchTree<vec>::build_from_patch_tree(
165 SerialTreeLayout layout = make_breadth_first_layout(ptree);
167 roots_ids = std::move(layout.roots_ids);
168 root_count = roots_ids.size();
171 u64 node_count = layout.nodes.size();
172 serial_tree.resize(node_count);
173 linked_patch_ids.resize(node_count);
176#pragma omp parallel for if (node_count > omp_min_nodes) reduction(max : max_level)
177 for (
u64 i = 0; i < node_count; i++) {
178 const Node &node = *layout.nodes[i];
180 PtNode snode = node.convert(box_transform);
181 if (layout.first_child_ids[i] !=
u64_max) {
182 for (
u32 c = 0; c < 8; c++) {
183 snode.childs_id[c] = layout.first_child_ids[i] + c;
187 serial_tree[i] = snode;
188 linked_patch_ids[i] = node.linked_patchid;
189 max_level = sycl::max(max_level, node.tree_node.level);
191 level_count = max_level;
193 shamlog_debug_ln(
"Serial Patch Tree",
"tree cell count = ", serial_tree.size());
194 shamlog_debug_ln(
"Serial Patch Tree",
"level_count =", level_count);
197template void SerialPatchTree<f32_3>::build_from_patch_tree(
199template void SerialPatchTree<f64_3>::build_from_patch_tree(
201template void SerialPatchTree<i64_3>::build_from_patch_tree(
std::uint32_t u32
32 bit unsigned integer
std::uint64_t u64
64 bit unsigned integer
Patch Tree : Tree structure organisation for an abstract list of patches Nb : this tree is compatible...
ExcptTypes make_except_with_loc(std::string message, SourceLocation loc=SourceLocation{})
Create an exception with a message and a location.
constexpr u64 u64_max
u64 max value