locum 0.1.3

Captures everything a Direct3D 11 game draws in a frame, to look at, query, change and replay: d3d11.dll and dxgi.dll beside the game that watch every call on its way to the real runtime.
Documentation 
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

//! Dynamic interval index. Overlapping placed resources remain separate candidates;
//! a lookup visits one segment, not every live allocation.
use std::collections::{BTreeMap, BTreeSet};

#[derive(Clone, Default)]
pub(super) struct Ranges {
    segments: BTreeMap<u64, BTreeSet<u64>>,
    objects: BTreeMap<u64, (u64, u64)>,
}
impl Ranges {
    fn boundary(&mut self, at: u64) {
        if !self.segments.contains_key(&at) {
            let previous = self
                .segments
                .range(..at)
                .next_back()
                .map(|(_, v)| v.clone())
                .unwrap_or_default();
            self.segments.insert(at, previous);
        }
    }
    pub fn insert(&mut self, id: u64, start: u64, size: u64) {
        self.remove(id);
        let Some(end) = start.checked_add(size).filter(|end| *end > start) else {
            return;
        };
        self.boundary(start);
        self.boundary(end);
        for (_, ids) in self.segments.range_mut(start..end) {
            ids.insert(id);
        }
        self.objects.insert(id, (start, end));
    }
    pub fn remove(&mut self, id: u64) {
        let Some((start, end)) = self.objects.remove(&id) else {
            return;
        };
        self.boundary(start);
        self.boundary(end);
        for (_, ids) in self.segments.range_mut(start..end) {
            ids.remove(&id);
        }
        let points: Vec<_> = self.segments.range(start..=end).map(|(&at, _)| at).collect();
        for at in points {
            let same = self.segments.range(..at).next_back().map_or_else(
                || self.segments[&at].is_empty(),
                |(_, previous)| *previous == self.segments[&at],
            );
            if same {
                self.segments.remove(&at);
            }
        }
    }
    pub fn get(&self, address: u64) -> impl Iterator<Item = u64> + '_ {
        self.segments
            .range(..=address)
            .next_back()
            .into_iter()
            .flat_map(|(_, ids)| ids.iter().copied())
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn overlaps_reuse_and_removal_match_an_exhaustive_oracle() {
        let mut index = Ranges::default();
        let mut oracle = BTreeMap::new();
        for n in 0..500u64 {
            let id = n % 31;
            if n % 5 == 0 {
                index.remove(id);
                oracle.remove(&id);
            } else {
                let (start, size) = ((n * 37) % 257, 1 + (n * 19) % 87);
                index.insert(id, start, size);
                oracle.insert(id, (start, size));
            }
            for address in 0..350 {
                let expected: Vec<_> = oracle
                    .iter()
                    .filter(|(_, (start, size))| address >= *start && address - start < *size)
                    .map(|(&id, _)| id)
                    .collect();
                assert_eq!(
                    index.get(address).collect::<Vec<_>>(),
                    expected,
                    "step {n}, address {address}"
                );
            }
        }
        for id in 0..31 {
            index.remove(id);
        }
        assert!(index.segments.is_empty());
    }
    #[test]
    fn large_disjoint_population_has_one_candidate_per_lookup() {
        let mut index = Ranges::default();
        for id in 0..60_000 {
            index.insert(id, id * 4096, 256);
        }
        let start = std::time::Instant::now();
        for n in 0..1_000_000 {
            let id = n % 60_000;
            assert_eq!(index.get(id * 4096 + 128).collect::<Vec<_>>(), vec![id]);
        }
        eprintln!(
            "1,000,000 lookups across 60,000 allocations: {:?}",
            start.elapsed()
        );
    }
}