47 PetscErrorCode PetscKDTreeDestroy(PetscKDTree *tree)  in PetscKDTreeDestroy()  argument
50   if (*tree == NULL) PetscFunctionReturn(PETSC_SUCCESS);  in PetscKDTreeDestroy()
51   PetscCall(PetscFree((*tree)->stems));  in PetscKDTreeDestroy()
52   PetscCall(PetscFree((*tree)->leaves));  in PetscKDTreeDestroy()
53   PetscCall(PetscFree((*tree)->bucket_indices));  in PetscKDTreeDestroy()
54   PetscCall(PetscFree((*tree)->coords_owned));  in PetscKDTreeDestroy()
55   PetscCall(PetscFree(*tree));  in PetscKDTreeDestroy()
86   PetscKDTree tree;  member
91 static inline int PetscKDTreeSortFunc(PetscCount left, PetscCount right, PetscKDTree tree, uint8_t …  in PetscKDTreeSortFunc()  argument
93   const PetscReal *coords = tree->coords;  in PetscKDTreeSortFunc()
94   const PetscInt   dim    = tree->dim;  in PetscKDTreeSortFunc()
109 …return PetscKDTreeSortFunc(*(PetscCount *)l, *(PetscCount *)r, kd_ctx->tree, kd_ctx->initial_axis);  in PetscKDTreeTimSort()
112 static PetscErrorCode PetscKDTreeVerifySortedIndices(PetscKDTree tree, PetscCount sorted_indices[],…  in PetscKDTreeVerifySortedIndices()  argument
114   PetscCount num_coords = tree->num_coords, range_size = end - start, location;  in PetscKDTreeVerifySortedIndices()
122   for (PetscInt d = 1; d < tree->dim; d++) {  in PetscKDTreeVerifySortedIndices()
132   PetscKDTree    tree;  member
140   PetscKDTree tree = kd_build->tree;  in PetscKDTreeBuildStemAndLeaves()  local
141   PetscInt    dim  = tree->dim;  in PetscKDTreeBuildStemAndLeaves()
145 …if (kd_build->debug_build) PetscCall(PetscKDTreeVerifySortedIndices(tree, sorted_indices, temp, st…  in PetscKDTreeBuildStemAndLeaves()
146   if (end - start <= tree->max_bucket_size) {  in PetscKDTreeBuildStemAndLeaves()
165 …for (PetscInt d = 0; d < dim; d++) bucket_coords[d * leaf->count + i] = tree->coords[bucket_indice…  in PetscKDTreeBuildStemAndLeaves()
170     PetscCount num_coords = tree->num_coords;  in PetscKDTreeBuildStemAndLeaves()
183 …stem->split = (tree->coords[tree->dim * median_idx + axis] + tree->coords[tree->dim * medianp1_idx…  in PetscKDTreeBuildStemAndLeaves()
186     for (PetscInt d = 1; d < tree->dim; d++) {  in PetscKDTreeBuildStemAndLeaves()
191 …< median && PetscKDTreeSortFunc(sorted_indices[d * num_coords + i], median_idx, tree, axis) <= 0) {  in PetscKDTreeBuildStemAndLeaves()
200 …PetscCall(PetscArraycpy(&sorted_indices[(tree->dim - 1) * num_coords + start], temp, end - start));  in PetscKDTreeBuildStemAndLeaves()
238   PetscKDTree tree;  in PetscKDTreeCreate()  local
252   PetscCall(PetscNew(&tree));  in PetscKDTreeCreate()
253   tree->dim             = dim;  in PetscKDTreeCreate()
254   tree->max_bucket_size = max_bucket_size == PETSC_DECIDE ? 32 : max_bucket_size;  in PetscKDTreeCreate()
255   tree->num_coords      = num_coords;  in PetscKDTreeCreate()
259     tree->coords_owned = coords; // fallthrough  in PetscKDTreeCreate()
261     tree->coords = coords;  in PetscKDTreeCreate()
264     PetscCall(PetscMalloc1(num_coords * dim, &tree->coords_owned));  in PetscKDTreeCreate()
265     PetscCall(PetscArraycpy((PetscReal *)tree->coords_owned, coords, num_coords * dim));  in PetscKDTreeCreate()
266     tree->coords = tree->coords_owned;  in PetscKDTreeCreate()
273   kd_ctx->tree = tree;  in PetscKDTreeCreate()
281   PetscInt    num_leaves = (PetscInt)PetscCeilInt64(num_coords, tree->max_bucket_size);  in PetscKDTreeCreate()
285   kd_build->tree        = tree;  in PetscKDTreeCreate()
293 …temAndLeaves(kd_build, sorted_indices, temp, 0, num_coords, 0, &tree->is_root_leaf, &tree->root_ha…  in PetscKDTreeCreate()
295   PetscCall(PetscSegBufferGetSize(kd_build->stems, &tree->num_stems));  in PetscKDTreeCreate()
296   PetscCall(PetscSegBufferGetSize(kd_build->leaves, &tree->num_leaves));  in PetscKDTreeCreate()
297   PetscCall(PetscSegBufferGetSize(kd_build->bucket_indices, &tree->num_bucket_indices));  in PetscKDTreeCreate()
298   PetscCall(PetscSegBufferExtractAlloc(kd_build->stems, &tree->stems));  in PetscKDTreeCreate()
299   PetscCall(PetscSegBufferExtractAlloc(kd_build->leaves, &tree->leaves));  in PetscKDTreeCreate()
300   PetscCall(PetscSegBufferExtractAlloc(kd_build->bucket_indices, &tree->bucket_indices));  in PetscKDTreeCreate()
302     PetscCall(PetscFree(tree->coords_owned));  in PetscKDTreeCreate()
303     PetscCall(PetscSegBufferExtractAlloc(kd_build->bucket_coords, &tree->coords_owned));  in PetscKDTreeCreate()
304     tree->coords = tree->coords_owned;  in PetscKDTreeCreate()
312   *new_tree = tree;  in PetscKDTreeCreate()
324 static inline PetscErrorCode PetscKDTreeQueryLeaf(PetscKDTree tree, KDLeaf leaf, const PetscReal po…  in PetscKDTreeQueryLeaf()  argument
326   PetscInt dim = tree->dim;  in PetscKDTreeQueryLeaf()
332     PetscCount point_index = tree->bucket_indices[leaf.indices_handle + i];  in PetscKDTreeQueryLeaf()
333     PetscReal  dist        = PetscSquareDistance(dim, point, &tree->coords[point_index * dim]);  in PetscKDTreeQueryLeaf()
342 static inline PetscErrorCode PetscKDTreeQueryLeaf_CopyCoords(PetscKDTree tree, KDLeaf leaf, const P…  in PetscKDTreeQueryLeaf_CopyCoords()  argument
344   PetscInt dim = tree->dim;  in PetscKDTreeQueryLeaf_CopyCoords()
352 …for (PetscInt d = 0; d < dim; d++) dist += PetscSqr(point[d] - tree->coords[leaf.coords_handle + d…  in PetscKDTreeQueryLeaf_CopyCoords()
355       *index        = tree->bucket_indices[leaf.indices_handle + i];  in PetscKDTreeQueryLeaf_CopyCoords()
363 static PetscErrorCode PetscKDTreeQuery_Recurse(PetscKDTree tree, const PetscReal point[], PetscCoun…  in PetscKDTreeQuery_Recurse()  argument
368     KDLeaf     leaf = tree->leaves[node_handle];  in PetscKDTreeQuery_Recurse()
372 …if (leaf.coords_handle > -1) PetscCall(PetscKDTreeQueryLeaf_CopyCoords(tree, leaf, point, &point_i…  in PetscKDTreeQuery_Recurse()
373     else PetscCall(PetscKDTreeQueryLeaf(tree, leaf, point, &point_index, &dist));  in PetscKDTreeQuery_Recurse()
381   KDStem    stem       = tree->stems[node_handle];  in PetscKDTreeQuery_Recurse()
384 …PetscCall(PetscKDTreeQuery_Recurse(tree, point, stem.less_equal_handle, PetscBTLookup(&stem.are_ha…  in PetscKDTreeQuery_Recurse()
388 …PetscCall(PetscKDTreeQuery_Recurse(tree, point, stem.greater_handle, PetscBTLookup(&stem.are_handl…  in PetscKDTreeQuery_Recurse()
392 …PetscCall(PetscKDTreeQuery_Recurse(tree, point, stem.greater_handle, PetscBTLookup(&stem.are_handl…  in PetscKDTreeQuery_Recurse()
396 …PetscCall(PetscKDTreeQuery_Recurse(tree, point, stem.less_equal_handle, PetscBTLookup(&stem.are_ha…  in PetscKDTreeQuery_Recurse()
427 PetscErrorCode PetscKDTreeQueryPointsNearestNeighbor(PetscKDTree tree, PetscCount num_points, const…  in PetscKDTreeQueryPointsNearestNeighbor()  argument
433   if (tree == NULL) {  in PetscKDTreeQueryPointsNearestNeighbor()
440   PetscCall(PetscCalloc1(tree->dim, &offsets));  in PetscKDTreeQueryPointsNearestNeighbor()
446 …PetscCall(PetscKDTreeQuery_Recurse(tree, &points[p * tree->dim], tree->root_handle, (char)tree->is…  in PetscKDTreeQueryPointsNearestNeighbor()
467 PetscErrorCode PetscKDTreeView(PetscKDTree tree, PetscViewer viewer)  in PetscKDTreeView()  argument
472   if (tree == NULL) PetscFunctionReturn(PETSC_SUCCESS);  in PetscKDTreeView()
478   for (PetscCount i = 0; i < tree->num_stems; i++) {  in PetscKDTreeView()
479     KDStem stem = tree->stems[i];  in PetscKDTreeView()
487   for (PetscCount i = 0; i < tree->num_leaves; i++) {  in PetscKDTreeView()
488     KDLeaf leaf = tree->leaves[i];  in PetscKDTreeView()
493       PetscCount bucket_index = tree->bucket_indices[leaf.indices_handle + j];  in PetscKDTreeView()
500 …for (PetscInt k = 0; k < tree->dim; k++) PetscCall(PetscViewerASCIIPrintf(viewer, "%g ", (double)t…  in PetscKDTreeView()
503 …or (PetscInt k = 0; k < tree->dim; k++) PetscCall(PetscViewerASCIIPrintf(viewer, "%g ", (double)tr…  in PetscKDTreeView()