TLA Line data Source code
1 : use std::collections::BTreeMap;
2 : use std::ops::Range;
3 :
4 : use tracing::info;
5 :
6 : use crate::tenant::storage_layer::PersistentLayerDesc;
7 :
8 : use super::layer_coverage::LayerCoverageTuple;
9 :
10 : /// Layers in this module are identified and indexed by this data.
11 : ///
12 : /// This is a helper struct to enable sorting layers by lsn.start.
13 : ///
14 : /// These three values are enough to uniquely identify a layer, since
15 : /// a layer is obligated to contain all contents within range, so two
16 : /// deltas (or images) with the same range have identical content.
17 CBC 62174 : #[derive(Debug, PartialEq, Eq, Clone)]
18 : pub struct LayerKey {
19 : // TODO I use i128 and u64 because it was easy for prototyping,
20 : // testing, and benchmarking. If we can use the Lsn and Key
21 : // types without overhead that would be preferable.
22 : pub key: Range<i128>,
23 : pub lsn: Range<u64>,
24 : pub is_image: bool,
25 : }
26 :
27 : impl PartialOrd for LayerKey {
28 UBC 0 : fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
29 0 : Some(self.cmp(other))
30 0 : }
31 : }
32 :
33 : impl Ord for LayerKey {
34 CBC 800431 : fn cmp(&self, other: &Self) -> std::cmp::Ordering {
35 800431 : // NOTE we really care about comparing by lsn.start first
36 800431 : self.lsn
37 800431 : .start
38 800431 : .cmp(&other.lsn.start)
39 800431 : .then(self.lsn.end.cmp(&other.lsn.end))
40 800431 : .then(self.key.start.cmp(&other.key.start))
41 800431 : .then(self.key.end.cmp(&other.key.end))
42 800431 : .then(self.is_image.cmp(&other.is_image))
43 800431 : }
44 : }
45 :
46 : impl From<&PersistentLayerDesc> for LayerKey {
47 34205 : fn from(layer: &PersistentLayerDesc) -> Self {
48 34205 : let kr = layer.get_key_range();
49 34205 : let lr = layer.get_lsn_range();
50 34205 : LayerKey {
51 34205 : key: kr.start.to_i128()..kr.end.to_i128(),
52 34205 : lsn: lr.start.0..lr.end.0,
53 34205 : is_image: !layer.is_incremental(),
54 34205 : }
55 34205 : }
56 : }
57 :
58 : /// Efficiently queryable layer coverage for each LSN.
59 : ///
60 : /// Allows answering layer map queries very efficiently,
61 : /// but doesn't allow retroactive insertion, which is
62 : /// sometimes necessary. See BufferedHistoricLayerCoverage.
63 : pub struct HistoricLayerCoverage<Value> {
64 : /// The latest state
65 : head: LayerCoverageTuple<Value>,
66 :
67 : /// All previous states
68 : historic: BTreeMap<u64, LayerCoverageTuple<Value>>,
69 : }
70 :
71 : impl<T: Clone> Default for HistoricLayerCoverage<T> {
72 UBC 0 : fn default() -> Self {
73 0 : Self::new()
74 0 : }
75 : }
76 :
77 : impl<Value: Clone> HistoricLayerCoverage<Value> {
78 CBC 1313 : pub fn new() -> Self {
79 1313 : Self {
80 1313 : head: LayerCoverageTuple::default(),
81 1313 : historic: BTreeMap::default(),
82 1313 : }
83 1313 : }
84 :
85 : /// Add a layer
86 : ///
87 : /// Panics if new layer has older lsn.start than an existing layer.
88 : /// See BufferedHistoricLayerCoverage for a more general insertion method.
89 35530 : pub fn insert(&mut self, layer_key: LayerKey, value: Value) {
90 : // It's only a persistent map, not a retroactive one
91 35530 : if let Some(last_entry) = self.historic.iter().next_back() {
92 34298 : let last_lsn = last_entry.0;
93 34298 : if layer_key.lsn.start < *last_lsn {
94 UBC 0 : panic!("unexpected retroactive insert");
95 CBC 34298 : }
96 1232 : }
97 :
98 : // Insert into data structure
99 35530 : let target = if layer_key.is_image {
100 14002 : &mut self.head.image_coverage
101 : } else {
102 21528 : &mut self.head.delta_coverage
103 : };
104 :
105 35530 : target.insert(layer_key.key, layer_key.lsn.clone(), value);
106 35530 :
107 35530 : // Remember history. Clone is O(1)
108 35530 : self.historic.insert(layer_key.lsn.start, self.head.clone());
109 35530 : }
110 :
111 : /// Query at a particular LSN, inclusive
112 34580186 : pub fn get_version(&self, lsn: u64) -> Option<&LayerCoverageTuple<Value>> {
113 34580186 : match self.historic.range(..=lsn).next_back() {
114 33345319 : Some((_, v)) => Some(v),
115 1234867 : None => None,
116 : }
117 34580186 : }
118 :
119 : /// Remove all entries after a certain LSN (inclusive)
120 6041 : pub fn trim(&mut self, begin: &u64) {
121 6041 : self.historic.split_off(begin);
122 6041 : self.head = self
123 6041 : .historic
124 6041 : .iter()
125 6041 : .next_back()
126 6041 : .map(|(_, v)| v.clone())
127 6041 : .unwrap_or_default();
128 6041 : }
129 : }
130 :
131 : /// This is the most basic test that demonstrates intended usage.
132 : /// All layers in this test have height 1.
133 1 : #[test]
134 1 : fn test_persistent_simple() {
135 1 : let mut map = HistoricLayerCoverage::<String>::new();
136 1 : map.insert(
137 1 : LayerKey {
138 1 : key: 0..5,
139 1 : lsn: 100..101,
140 1 : is_image: true,
141 1 : },
142 1 : "Layer 1".to_string(),
143 1 : );
144 1 : map.insert(
145 1 : LayerKey {
146 1 : key: 3..9,
147 1 : lsn: 110..111,
148 1 : is_image: true,
149 1 : },
150 1 : "Layer 2".to_string(),
151 1 : );
152 1 : map.insert(
153 1 : LayerKey {
154 1 : key: 5..6,
155 1 : lsn: 120..121,
156 1 : is_image: true,
157 1 : },
158 1 : "Layer 3".to_string(),
159 1 : );
160 1 :
161 1 : // After Layer 1 insertion
162 1 : let version = map.get_version(105).unwrap();
163 1 : assert_eq!(version.image_coverage.query(1), Some("Layer 1".to_string()));
164 1 : assert_eq!(version.image_coverage.query(4), Some("Layer 1".to_string()));
165 :
166 : // After Layer 2 insertion
167 1 : let version = map.get_version(115).unwrap();
168 1 : assert_eq!(version.image_coverage.query(4), Some("Layer 2".to_string()));
169 1 : assert_eq!(version.image_coverage.query(8), Some("Layer 2".to_string()));
170 1 : assert_eq!(version.image_coverage.query(11), None);
171 :
172 : // After Layer 3 insertion
173 1 : let version = map.get_version(125).unwrap();
174 1 : assert_eq!(version.image_coverage.query(4), Some("Layer 2".to_string()));
175 1 : assert_eq!(version.image_coverage.query(5), Some("Layer 3".to_string()));
176 1 : assert_eq!(version.image_coverage.query(7), Some("Layer 2".to_string()));
177 1 : }
178 :
179 : /// Cover simple off-by-one edge cases
180 1 : #[test]
181 1 : fn test_off_by_one() {
182 1 : let mut map = HistoricLayerCoverage::<String>::new();
183 1 : map.insert(
184 1 : LayerKey {
185 1 : key: 3..5,
186 1 : lsn: 100..110,
187 1 : is_image: true,
188 1 : },
189 1 : "Layer 1".to_string(),
190 1 : );
191 1 :
192 1 : // Check different LSNs
193 1 : let version = map.get_version(99);
194 1 : assert!(version.is_none());
195 1 : let version = map.get_version(100).unwrap();
196 1 : assert_eq!(version.image_coverage.query(4), Some("Layer 1".to_string()));
197 1 : let version = map.get_version(110).unwrap();
198 1 : assert_eq!(version.image_coverage.query(4), Some("Layer 1".to_string()));
199 :
200 : // Check different keys
201 1 : let version = map.get_version(105).unwrap();
202 1 : assert_eq!(version.image_coverage.query(2), None);
203 1 : assert_eq!(version.image_coverage.query(3), Some("Layer 1".to_string()));
204 1 : assert_eq!(version.image_coverage.query(4), Some("Layer 1".to_string()));
205 1 : assert_eq!(version.image_coverage.query(5), None);
206 1 : }
207 :
208 : /// White-box regression test, checking for incorrect removal of node at key.end
209 1 : #[test]
210 1 : fn test_regression() {
211 1 : let mut map = HistoricLayerCoverage::<String>::new();
212 1 : map.insert(
213 1 : LayerKey {
214 1 : key: 0..5,
215 1 : lsn: 0..5,
216 1 : is_image: false,
217 1 : },
218 1 : "Layer 1".to_string(),
219 1 : );
220 1 : map.insert(
221 1 : LayerKey {
222 1 : key: 0..5,
223 1 : lsn: 1..2,
224 1 : is_image: false,
225 1 : },
226 1 : "Layer 2".to_string(),
227 1 : );
228 1 :
229 1 : // If an insertion operation improperly deletes the endpoint of a previous layer
230 1 : // (which is more likely to happen with layers that collide on key.end), we will
231 1 : // end up with an infinite layer, covering the entire keyspace. Here we assert
232 1 : // that there's no layer at key 100 because we didn't insert any layer there.
233 1 : let version = map.get_version(100).unwrap();
234 1 : assert_eq!(version.delta_coverage.query(100), None);
235 1 : }
236 :
237 : /// Cover edge cases where layers begin or end on the same key
238 1 : #[test]
239 1 : fn test_key_collision() {
240 1 : let mut map = HistoricLayerCoverage::<String>::new();
241 1 :
242 1 : map.insert(
243 1 : LayerKey {
244 1 : key: 3..5,
245 1 : lsn: 100..110,
246 1 : is_image: true,
247 1 : },
248 1 : "Layer 10".to_string(),
249 1 : );
250 1 : map.insert(
251 1 : LayerKey {
252 1 : key: 5..8,
253 1 : lsn: 100..110,
254 1 : is_image: true,
255 1 : },
256 1 : "Layer 11".to_string(),
257 1 : );
258 1 : map.insert(
259 1 : LayerKey {
260 1 : key: 3..4,
261 1 : lsn: 200..210,
262 1 : is_image: true,
263 1 : },
264 1 : "Layer 20".to_string(),
265 1 : );
266 1 :
267 1 : // Check after layer 11
268 1 : let version = map.get_version(105).unwrap();
269 1 : assert_eq!(version.image_coverage.query(2), None);
270 1 : assert_eq!(
271 1 : version.image_coverage.query(3),
272 1 : Some("Layer 10".to_string())
273 1 : );
274 1 : assert_eq!(
275 1 : version.image_coverage.query(5),
276 1 : Some("Layer 11".to_string())
277 1 : );
278 1 : assert_eq!(
279 1 : version.image_coverage.query(7),
280 1 : Some("Layer 11".to_string())
281 1 : );
282 1 : assert_eq!(version.image_coverage.query(8), None);
283 :
284 : // Check after layer 20
285 1 : let version = map.get_version(205).unwrap();
286 1 : assert_eq!(version.image_coverage.query(2), None);
287 1 : assert_eq!(
288 1 : version.image_coverage.query(3),
289 1 : Some("Layer 20".to_string())
290 1 : );
291 1 : assert_eq!(
292 1 : version.image_coverage.query(5),
293 1 : Some("Layer 11".to_string())
294 1 : );
295 1 : assert_eq!(
296 1 : version.image_coverage.query(7),
297 1 : Some("Layer 11".to_string())
298 1 : );
299 1 : assert_eq!(version.image_coverage.query(8), None);
300 1 : }
301 :
302 : /// Test when rectangles have nontrivial height and possibly overlap
303 1 : #[test]
304 1 : fn test_persistent_overlapping() {
305 1 : let mut map = HistoricLayerCoverage::<String>::new();
306 1 :
307 1 : // Add 3 key-disjoint layers with varying LSN ranges
308 1 : map.insert(
309 1 : LayerKey {
310 1 : key: 1..2,
311 1 : lsn: 100..200,
312 1 : is_image: true,
313 1 : },
314 1 : "Layer 1".to_string(),
315 1 : );
316 1 : map.insert(
317 1 : LayerKey {
318 1 : key: 4..5,
319 1 : lsn: 110..200,
320 1 : is_image: true,
321 1 : },
322 1 : "Layer 2".to_string(),
323 1 : );
324 1 : map.insert(
325 1 : LayerKey {
326 1 : key: 7..8,
327 1 : lsn: 120..300,
328 1 : is_image: true,
329 1 : },
330 1 : "Layer 3".to_string(),
331 1 : );
332 1 :
333 1 : // Add wide and short layer
334 1 : map.insert(
335 1 : LayerKey {
336 1 : key: 0..9,
337 1 : lsn: 130..199,
338 1 : is_image: true,
339 1 : },
340 1 : "Layer 4".to_string(),
341 1 : );
342 1 :
343 1 : // Add wide layer taller than some
344 1 : map.insert(
345 1 : LayerKey {
346 1 : key: 0..9,
347 1 : lsn: 140..201,
348 1 : is_image: true,
349 1 : },
350 1 : "Layer 5".to_string(),
351 1 : );
352 1 :
353 1 : // Add wide layer taller than all
354 1 : map.insert(
355 1 : LayerKey {
356 1 : key: 0..9,
357 1 : lsn: 150..301,
358 1 : is_image: true,
359 1 : },
360 1 : "Layer 6".to_string(),
361 1 : );
362 1 :
363 1 : // After layer 4 insertion
364 1 : let version = map.get_version(135).unwrap();
365 1 : assert_eq!(version.image_coverage.query(0), Some("Layer 4".to_string()));
366 1 : assert_eq!(version.image_coverage.query(1), Some("Layer 1".to_string()));
367 1 : assert_eq!(version.image_coverage.query(2), Some("Layer 4".to_string()));
368 1 : assert_eq!(version.image_coverage.query(4), Some("Layer 2".to_string()));
369 1 : assert_eq!(version.image_coverage.query(5), Some("Layer 4".to_string()));
370 1 : assert_eq!(version.image_coverage.query(7), Some("Layer 3".to_string()));
371 1 : assert_eq!(version.image_coverage.query(8), Some("Layer 4".to_string()));
372 :
373 : // After layer 5 insertion
374 1 : let version = map.get_version(145).unwrap();
375 1 : assert_eq!(version.image_coverage.query(0), Some("Layer 5".to_string()));
376 1 : assert_eq!(version.image_coverage.query(1), Some("Layer 5".to_string()));
377 1 : assert_eq!(version.image_coverage.query(2), Some("Layer 5".to_string()));
378 1 : assert_eq!(version.image_coverage.query(4), Some("Layer 5".to_string()));
379 1 : assert_eq!(version.image_coverage.query(5), Some("Layer 5".to_string()));
380 1 : assert_eq!(version.image_coverage.query(7), Some("Layer 3".to_string()));
381 1 : assert_eq!(version.image_coverage.query(8), Some("Layer 5".to_string()));
382 :
383 : // After layer 6 insertion
384 1 : let version = map.get_version(155).unwrap();
385 1 : assert_eq!(version.image_coverage.query(0), Some("Layer 6".to_string()));
386 1 : assert_eq!(version.image_coverage.query(1), Some("Layer 6".to_string()));
387 1 : assert_eq!(version.image_coverage.query(2), Some("Layer 6".to_string()));
388 1 : assert_eq!(version.image_coverage.query(4), Some("Layer 6".to_string()));
389 1 : assert_eq!(version.image_coverage.query(5), Some("Layer 6".to_string()));
390 1 : assert_eq!(version.image_coverage.query(7), Some("Layer 6".to_string()));
391 1 : assert_eq!(version.image_coverage.query(8), Some("Layer 6".to_string()));
392 1 : }
393 :
394 : /// Wrapper for HistoricLayerCoverage that allows us to hack around the lack
395 : /// of support for retroactive insertion by rebuilding the map since the
396 : /// change.
397 : ///
398 : /// Why is this needed? We most often insert new layers with newer LSNs,
399 : /// but during compaction we create layers with non-latest LSN, and during
400 : /// GC we delete historic layers.
401 : ///
402 : /// Even though rebuilding is an expensive (N log N) solution to the problem,
403 : /// it's not critical since we do something equally expensive just to decide
404 : /// whether or not to create new image layers.
405 : /// TODO It's not expensive but it's not great to hold a layer map write lock
406 : /// for that long.
407 : ///
408 : /// If this becomes an actual bottleneck, one solution would be to build a
409 : /// segment tree that holds PersistentLayerMaps. Though this would mean that
410 : /// we take an additional log(N) performance hit for queries, which will probably
411 : /// still be more critical.
412 : ///
413 : /// See this for more on persistent and retroactive techniques:
414 : /// <https://www.youtube.com/watch?v=WqCWghETNDc&t=581s>
415 : pub struct BufferedHistoricLayerCoverage<Value> {
416 : /// A persistent layer map that we rebuild when we need to retroactively update
417 : historic_coverage: HistoricLayerCoverage<Value>,
418 :
419 : /// We buffer insertion into the PersistentLayerMap to decrease the number of rebuilds.
420 : buffer: BTreeMap<LayerKey, Option<Value>>,
421 :
422 : /// All current layers. This is not used for search. Only to make rebuilds easier.
423 : layers: BTreeMap<LayerKey, Value>,
424 : }
425 :
426 : impl<T: std::fmt::Debug> std::fmt::Debug for BufferedHistoricLayerCoverage<T> {
427 UBC 0 : fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
428 0 : f.debug_struct("RetroactiveLayerMap")
429 0 : .field("buffer", &self.buffer)
430 0 : .field("layers", &self.layers)
431 0 : .finish()
432 0 : }
433 : }
434 :
435 : impl<T: Clone> Default for BufferedHistoricLayerCoverage<T> {
436 CBC 1306 : fn default() -> Self {
437 1306 : Self::new()
438 1306 : }
439 : }
440 :
441 : impl<Value: Clone> BufferedHistoricLayerCoverage<Value> {
442 1308 : pub fn new() -> Self {
443 1308 : Self {
444 1308 : historic_coverage: HistoricLayerCoverage::<Value>::new(),
445 1308 : buffer: BTreeMap::new(),
446 1308 : layers: BTreeMap::new(),
447 1308 : }
448 1308 : }
449 :
450 26659 : pub fn insert(&mut self, layer_key: LayerKey, value: Value) {
451 26659 : self.buffer.insert(layer_key, Some(value));
452 26659 : }
453 :
454 7553 : pub fn remove(&mut self, layer_key: LayerKey) {
455 7553 : self.buffer.insert(layer_key, None);
456 7553 : }
457 :
458 7290 : pub fn rebuild(&mut self) {
459 : // Find the first LSN that needs to be rebuilt
460 7290 : let rebuild_since: u64 = match self.buffer.iter().next() {
461 6041 : Some((LayerKey { lsn, .. }, _)) => lsn.start,
462 1249 : None => return, // No need to rebuild if buffer is empty
463 : };
464 :
465 : // Apply buffered updates to self.layers
466 6041 : let num_updates = self.buffer.len();
467 33304 : self.buffer.retain(|layer_key, layer| {
468 33304 : match layer {
469 26659 : Some(l) => {
470 26659 : self.layers.insert(layer_key.clone(), l.clone());
471 26659 : }
472 6645 : None => {
473 6645 : self.layers.remove(layer_key);
474 6645 : }
475 : };
476 33304 : false
477 33304 : });
478 6041 :
479 6041 : // Rebuild
480 6041 : let mut num_inserted = 0;
481 6041 : self.historic_coverage.trim(&rebuild_since);
482 35515 : for (layer_key, layer) in self.layers.range(
483 6041 : LayerKey {
484 6041 : lsn: rebuild_since..0,
485 6041 : key: 0..0,
486 6041 : is_image: false,
487 6041 : }..,
488 35515 : ) {
489 35515 : self.historic_coverage
490 35515 : .insert(layer_key.clone(), layer.clone());
491 35515 : num_inserted += 1;
492 35515 : }
493 :
494 : // TODO maybe only warn if ratio is at least 10
495 6041 : info!(
496 6032 : "Rebuilt layer map. Did {} insertions to process a batch of {} updates.",
497 6032 : num_inserted, num_updates,
498 6032 : )
499 7290 : }
500 :
501 : /// Iterate all the layers
502 4543 : pub fn iter(&self) -> impl '_ + Iterator<Item = Value> {
503 4543 : // NOTE we can actually perform this without rebuilding,
504 4543 : // but it's not necessary for now.
505 4543 : if !self.buffer.is_empty() {
506 UBC 0 : panic!("rebuild pls")
507 CBC 4543 : }
508 4543 :
509 4543 : self.layers.values().cloned()
510 4543 : }
511 :
512 : /// Return a reference to a queryable map, assuming all updates
513 : /// have already been processed using self.rebuild()
514 34580169 : pub fn get(&self) -> anyhow::Result<&HistoricLayerCoverage<Value>> {
515 34580169 : // NOTE we error here instead of implicitly rebuilding because
516 34580169 : // rebuilding is somewhat expensive.
517 34580169 : // TODO maybe implicitly rebuild and log/sentry an error?
518 34580169 : if !self.buffer.is_empty() {
519 UBC 0 : anyhow::bail!("rebuild required")
520 CBC 34580169 : }
521 34580169 :
522 34580169 : Ok(&self.historic_coverage)
523 34580169 : }
524 : }
525 :
526 1 : #[test]
527 1 : fn test_retroactive_regression_1() {
528 1 : let mut map = BufferedHistoricLayerCoverage::new();
529 1 :
530 1 : map.insert(
531 1 : LayerKey {
532 1 : key: 0..21267647932558653966460912964485513215,
533 1 : lsn: 23761336..23761457,
534 1 : is_image: false,
535 1 : },
536 1 : "sdfsdfs".to_string(),
537 1 : );
538 1 :
539 1 : map.rebuild();
540 1 :
541 1 : let version = map.get().unwrap().get_version(23761457).unwrap();
542 1 : assert_eq!(
543 1 : version.delta_coverage.query(100),
544 1 : Some("sdfsdfs".to_string())
545 1 : );
546 1 : }
547 :
548 1 : #[test]
549 1 : fn test_retroactive_simple() {
550 1 : let mut map = BufferedHistoricLayerCoverage::new();
551 1 :
552 1 : // Append some images in increasing LSN order
553 1 : map.insert(
554 1 : LayerKey {
555 1 : key: 0..5,
556 1 : lsn: 100..101,
557 1 : is_image: true,
558 1 : },
559 1 : "Image 1".to_string(),
560 1 : );
561 1 : map.insert(
562 1 : LayerKey {
563 1 : key: 3..9,
564 1 : lsn: 110..111,
565 1 : is_image: true,
566 1 : },
567 1 : "Image 2".to_string(),
568 1 : );
569 1 : map.insert(
570 1 : LayerKey {
571 1 : key: 4..6,
572 1 : lsn: 120..121,
573 1 : is_image: true,
574 1 : },
575 1 : "Image 3".to_string(),
576 1 : );
577 1 : map.insert(
578 1 : LayerKey {
579 1 : key: 8..9,
580 1 : lsn: 120..121,
581 1 : is_image: true,
582 1 : },
583 1 : "Image 4".to_string(),
584 1 : );
585 1 :
586 1 : // Add a delta layer out of order
587 1 : map.insert(
588 1 : LayerKey {
589 1 : key: 2..5,
590 1 : lsn: 105..106,
591 1 : is_image: false,
592 1 : },
593 1 : "Delta 1".to_string(),
594 1 : );
595 1 :
596 1 : // Rebuild so we can start querying
597 1 : map.rebuild();
598 1 :
599 1 : {
600 1 : let map = map.get().expect("rebuilt");
601 1 :
602 1 : let version = map.get_version(90);
603 1 : assert!(version.is_none());
604 1 : let version = map.get_version(102).unwrap();
605 1 : assert_eq!(version.image_coverage.query(4), Some("Image 1".to_string()));
606 :
607 1 : let version = map.get_version(107).unwrap();
608 1 : assert_eq!(version.image_coverage.query(4), Some("Image 1".to_string()));
609 1 : assert_eq!(version.delta_coverage.query(4), Some("Delta 1".to_string()));
610 :
611 1 : let version = map.get_version(115).unwrap();
612 1 : assert_eq!(version.image_coverage.query(4), Some("Image 2".to_string()));
613 :
614 1 : let version = map.get_version(125).unwrap();
615 1 : assert_eq!(version.image_coverage.query(4), Some("Image 3".to_string()));
616 : }
617 :
618 : // Remove Image 3
619 1 : map.remove(LayerKey {
620 1 : key: 4..6,
621 1 : lsn: 120..121,
622 1 : is_image: true,
623 1 : });
624 1 : map.rebuild();
625 1 :
626 1 : {
627 1 : // Check deletion worked
628 1 : let map = map.get().expect("rebuilt");
629 1 : let version = map.get_version(125).unwrap();
630 1 : assert_eq!(version.image_coverage.query(4), Some("Image 2".to_string()));
631 1 : assert_eq!(version.image_coverage.query(8), Some("Image 4".to_string()));
632 : }
633 1 : }
|
