1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/// Reusable buffers for allocation-free repeated searches.
///
/// Use this when running many searches against the same index to reuse the
/// result vector and traversal stack.
///
/// # Example
///
/// ```
/// use packed_spatial_index::{Index2DBuilder, Box2D, SearchWorkspace};
///
/// let mut builder = Index2DBuilder::new(1);
/// builder.add(Box2D::new(0.0, 0.0, 1.0, 1.0));
/// let index = builder.finish().unwrap();
///
/// let mut workspace = SearchWorkspace::new();
/// let hits = index.search_with(Box2D::new(0.5, 0.5, 0.5, 0.5), &mut workspace);
/// assert_eq!(hits, &[0]);
/// ```
#[derive(Debug, Default)]
pub struct SearchWorkspace {
pub(crate) results: Vec<usize>,
pub(crate) stack: Vec<usize>,
}
impl SearchWorkspace {
/// Create an empty workspace.
pub fn new() -> Self {
Self::default()
}
/// Create a workspace with preallocated result and traversal-stack capacity.
pub fn with_capacity(results: usize, stack: usize) -> Self {
Self {
results: Vec::with_capacity(results),
stack: Vec::with_capacity(stack),
}
}
/// Results from the latest `search_with` call.
pub fn results(&self) -> &[usize] {
&self.results
}
}
#[inline]
pub(crate) fn prefetch_read<T>(ptr: *const T) {
#[cfg(target_arch = "x86_64")]
// SAFETY: `_mm_prefetch` is a pure cache hint that never reads or dereferences
// `ptr`, so any pointer value (including dangling or out of bounds) is sound; it is
// `unsafe` only because it is a target-feature intrinsic, and SSE is baseline on
// x86-64.
unsafe {
use std::arch::x86_64::{_MM_HINT_T0, _mm_prefetch};
_mm_prefetch(ptr.cast::<i8>(), _MM_HINT_T0);
}
#[cfg(target_arch = "x86")]
// SAFETY: `_mm_prefetch` is a pure cache hint that never reads or dereferences
// `ptr`, so any pointer value is sound; it is `unsafe` only because it is a
// target-feature intrinsic.
unsafe {
use std::arch::x86::{_MM_HINT_T0, _mm_prefetch};
_mm_prefetch(ptr.cast::<i8>(), _MM_HINT_T0);
}
#[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))]
{
let _ = ptr;
}
}
pub(crate) fn upper_bound_level(level_bounds: &[usize], node_index: usize) -> usize {
let mut lo = 0usize;
let mut hi = level_bounds.len() - 1;
while lo < hi {
let mid = (lo + hi) / 2;
if level_bounds[mid] > node_index {
hi = mid;
} else {
lo = mid + 1;
}
}
lo
}