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