Line data Source code
1 : use postgres_ffi::BLCKSZ;
2 : use std::ops::Range;
3 :
4 : use crate::key::Key;
5 : use itertools::Itertools;
6 :
7 : ///
8 : /// Represents a set of Keys, in a compact form.
9 : ///
10 11770 : #[derive(Clone, Debug, Default, PartialEq, Eq)]
11 : pub struct KeySpace {
12 : /// Contiguous ranges of keys that belong to the key space. In key order,
13 : /// and with no overlap.
14 : pub ranges: Vec<Range<Key>>,
15 : }
16 :
17 : impl KeySpace {
18 : ///
19 : /// Partition a key space into roughly chunks of roughly 'target_size' bytes
20 : /// in each partition.
21 : ///
22 170 : pub fn partition(&self, target_size: u64) -> KeyPartitioning {
23 170 : // Assume that each value is 8k in size.
24 170 : let target_nblocks = (target_size / BLCKSZ as u64) as usize;
25 170 :
26 170 : let mut parts = Vec::new();
27 170 : let mut current_part = Vec::new();
28 170 : let mut current_part_size: usize = 0;
29 1190 : for range in &self.ranges {
30 : // If appending the next contiguous range in the keyspace to the current
31 : // partition would cause it to be too large, start a new partition.
32 1020 : let this_size = key_range_size(range) as usize;
33 1020 : if current_part_size + this_size > target_nblocks && !current_part.is_empty() {
34 0 : parts.push(KeySpace {
35 0 : ranges: current_part,
36 0 : });
37 0 : current_part = Vec::new();
38 0 : current_part_size = 0;
39 1020 : }
40 :
41 : // If the next range is larger than 'target_size', split it into
42 : // 'target_size' chunks.
43 1020 : let mut remain_size = this_size;
44 1020 : let mut start = range.start;
45 1020 : while remain_size > target_nblocks {
46 0 : let next = start.add(target_nblocks as u32);
47 0 : parts.push(KeySpace {
48 0 : ranges: vec![start..next],
49 0 : });
50 0 : start = next;
51 0 : remain_size -= target_nblocks
52 : }
53 1020 : current_part.push(start..range.end);
54 1020 : current_part_size += remain_size;
55 : }
56 :
57 : // add last partition that wasn't full yet.
58 170 : if !current_part.is_empty() {
59 170 : parts.push(KeySpace {
60 170 : ranges: current_part,
61 170 : });
62 170 : }
63 :
64 170 : KeyPartitioning { parts }
65 170 : }
66 :
67 : /// Merge another keyspace into the current one.
68 : /// Note: the keyspaces must not ovelap (enforced via assertions)
69 20 : pub fn merge(&mut self, other: &KeySpace) {
70 20 : let all_ranges = self
71 20 : .ranges
72 20 : .iter()
73 20 : .merge_by(other.ranges.iter(), |lhs, rhs| lhs.start < rhs.start);
74 20 :
75 20 : let mut accum = KeySpaceAccum::new();
76 20 : let mut prev: Option<&Range<Key>> = None;
77 30 : for range in all_ranges {
78 10 : if let Some(prev) = prev {
79 0 : let overlap =
80 0 : std::cmp::max(range.start, prev.start) < std::cmp::min(range.end, prev.end);
81 0 : assert!(
82 0 : !overlap,
83 0 : "Attempt to merge ovelapping keyspaces: {:?} overlaps {:?}",
84 : prev, range
85 : );
86 10 : }
87 :
88 10 : accum.add_range(range.clone());
89 10 : prev = Some(range);
90 : }
91 :
92 20 : self.ranges = accum.to_keyspace().ranges;
93 20 : }
94 :
95 : /// Remove all keys in `other` from `self`.
96 : /// This can involve splitting or removing of existing ranges.
97 38 : pub fn remove_overlapping_with(&mut self, other: &KeySpace) {
98 38 : let (self_start, self_end) = match (self.start(), self.end()) {
99 38 : (Some(start), Some(end)) => (start, end),
100 : _ => {
101 : // self is empty
102 0 : return;
103 : }
104 : };
105 :
106 : // Key spaces are sorted by definition, so skip ahead to the first
107 : // potentially intersecting range. Similarly, ignore ranges that start
108 : // after the current keyspace ends.
109 38 : let other_ranges = other
110 38 : .ranges
111 38 : .iter()
112 38 : .skip_while(|range| self_start >= range.end)
113 40 : .take_while(|range| self_end > range.start);
114 :
115 76 : for range in other_ranges {
116 76 : while let Some(overlap_at) = self.overlaps_at(range) {
117 38 : let overlapped = self.ranges[overlap_at].clone();
118 38 :
119 38 : if overlapped.start < range.start && overlapped.end <= range.end {
120 10 : // Higher part of the range is completely overlapped.
121 10 : self.ranges[overlap_at].end = range.start;
122 28 : }
123 38 : if overlapped.start >= range.start && overlapped.end > range.end {
124 2 : // Lower part of the range is completely overlapped.
125 2 : self.ranges[overlap_at].start = range.end;
126 36 : }
127 38 : if overlapped.start < range.start && overlapped.end > range.end {
128 4 : // Middle part of the range is overlapped.
129 4 : self.ranges[overlap_at].end = range.start;
130 4 : self.ranges
131 4 : .insert(overlap_at + 1, range.end..overlapped.end);
132 34 : }
133 38 : if overlapped.start >= range.start && overlapped.end <= range.end {
134 22 : // Whole range is overlapped
135 22 : self.ranges.remove(overlap_at);
136 22 : }
137 : }
138 : }
139 38 : }
140 :
141 38 : pub fn start(&self) -> Option<Key> {
142 38 : self.ranges.first().map(|range| range.start)
143 38 : }
144 :
145 38 : pub fn end(&self) -> Option<Key> {
146 38 : self.ranges.last().map(|range| range.end)
147 38 : }
148 :
149 : #[allow(unused)]
150 440 : pub fn total_size(&self) -> usize {
151 440 : self.ranges
152 440 : .iter()
153 440 : .map(|range| key_range_size(range) as usize)
154 440 : .sum()
155 440 : }
156 :
157 396 : fn overlaps_at(&self, range: &Range<Key>) -> Option<usize> {
158 396 : match self.ranges.binary_search_by_key(&range.end, |r| r.start) {
159 2 : Ok(0) => None,
160 318 : Err(0) => None,
161 18 : Ok(index) if self.ranges[index - 1].end > range.start => Some(index - 1),
162 58 : Err(index) if self.ranges[index - 1].end > range.start => Some(index - 1),
163 26 : _ => None,
164 : }
165 396 : }
166 :
167 : ///
168 : /// Check if key space contains overlapping range
169 : ///
170 320 : pub fn overlaps(&self, range: &Range<Key>) -> bool {
171 320 : self.overlaps_at(range).is_some()
172 320 : }
173 : }
174 :
175 : ///
176 : /// Represents a partitioning of the key space.
177 : ///
178 : /// The only kind of partitioning we do is to partition the key space into
179 : /// partitions that are roughly equal in physical size (see KeySpace::partition).
180 : /// But this data structure could represent any partitioning.
181 : ///
182 478 : #[derive(Clone, Debug, Default)]
183 : pub struct KeyPartitioning {
184 : pub parts: Vec<KeySpace>,
185 : }
186 :
187 : impl KeyPartitioning {
188 292 : pub fn new() -> Self {
189 292 : KeyPartitioning { parts: Vec::new() }
190 292 : }
191 : }
192 :
193 : ///
194 : /// A helper object, to collect a set of keys and key ranges into a KeySpace
195 : /// object. This takes care of merging adjacent keys and key ranges into
196 : /// contiguous ranges.
197 : ///
198 16894 : #[derive(Clone, Debug, Default)]
199 : pub struct KeySpaceAccum {
200 : accum: Option<Range<Key>>,
201 :
202 : ranges: Vec<Range<Key>>,
203 : size: u64,
204 : }
205 :
206 : impl KeySpaceAccum {
207 7360 : pub fn new() -> Self {
208 7360 : Self {
209 7360 : accum: None,
210 7360 : ranges: Vec::new(),
211 7360 : size: 0,
212 7360 : }
213 7360 : }
214 :
215 : #[inline(always)]
216 2077800 : pub fn add_key(&mut self, key: Key) {
217 2077800 : self.add_range(singleton_range(key))
218 2077800 : }
219 :
220 : #[inline(always)]
221 2089472 : pub fn add_range(&mut self, range: Range<Key>) {
222 2089472 : self.size += key_range_size(&range) as u64;
223 2089472 :
224 2089472 : match self.accum.as_mut() {
225 2068590 : Some(accum) => {
226 2068590 : if range.start == accum.end {
227 2064712 : accum.end = range.end;
228 2064712 : } else {
229 : // TODO: to efficiently support small sharding stripe sizes, we should avoid starting
230 : // a new range here if the skipped region was all keys that don't belong on this shard.
231 : // (https://github.com/neondatabase/neon/issues/6247)
232 3878 : assert!(range.start > accum.end);
233 3878 : self.ranges.push(accum.clone());
234 3878 : *accum = range;
235 : }
236 : }
237 20882 : None => self.accum = Some(range),
238 : }
239 2089472 : }
240 :
241 24166 : pub fn to_keyspace(mut self) -> KeySpace {
242 24166 : if let Some(accum) = self.accum.take() {
243 20874 : self.ranges.push(accum);
244 20874 : }
245 24166 : KeySpace {
246 24166 : ranges: self.ranges,
247 24166 : }
248 24166 : }
249 :
250 424 : pub fn consume_keyspace(&mut self) -> KeySpace {
251 424 : std::mem::take(self).to_keyspace()
252 424 : }
253 :
254 566 : pub fn size(&self) -> u64 {
255 566 : self.size
256 566 : }
257 : }
258 :
259 : ///
260 : /// A helper object, to collect a set of keys and key ranges into a KeySpace
261 : /// object. Key ranges may be inserted in any order and can overlap.
262 : ///
263 426 : #[derive(Clone, Debug, Default)]
264 : pub struct KeySpaceRandomAccum {
265 : ranges: Vec<Range<Key>>,
266 : }
267 :
268 : impl KeySpaceRandomAccum {
269 30 : pub fn new() -> Self {
270 30 : Self { ranges: Vec::new() }
271 30 : }
272 :
273 320 : pub fn add_key(&mut self, key: Key) {
274 320 : self.add_range(singleton_range(key))
275 320 : }
276 :
277 362 : pub fn add_range(&mut self, range: Range<Key>) {
278 362 : self.ranges.push(range);
279 362 : }
280 :
281 446 : pub fn to_keyspace(mut self) -> KeySpace {
282 446 : let mut ranges = Vec::new();
283 446 : if !self.ranges.is_empty() {
284 680 : self.ranges.sort_by_key(|r| r.start);
285 28 : let mut start = self.ranges.first().unwrap().start;
286 28 : let mut end = self.ranges.first().unwrap().end;
287 390 : for r in self.ranges {
288 362 : assert!(r.start >= start);
289 362 : if r.start > end {
290 4 : ranges.push(start..end);
291 4 : start = r.start;
292 4 : end = r.end;
293 358 : } else if r.end > end {
294 322 : end = r.end;
295 322 : }
296 : }
297 28 : ranges.push(start..end);
298 418 : }
299 446 : KeySpace { ranges }
300 446 : }
301 :
302 20 : pub fn consume_keyspace(&mut self) -> KeySpace {
303 20 : let mut prev_accum = KeySpaceRandomAccum::new();
304 20 : std::mem::swap(self, &mut prev_accum);
305 20 :
306 20 : prev_accum.to_keyspace()
307 20 : }
308 : }
309 :
310 2090918 : pub fn key_range_size(key_range: &Range<Key>) -> u32 {
311 2090918 : let start = key_range.start;
312 2090918 : let end = key_range.end;
313 2090918 :
314 2090918 : if end.field1 != start.field1
315 2090918 : || end.field2 != start.field2
316 2090918 : || end.field3 != start.field3
317 2090918 : || end.field4 != start.field4
318 : {
319 0 : return u32::MAX;
320 2090918 : }
321 2090918 :
322 2090918 : let start = (start.field5 as u64) << 32 | start.field6 as u64;
323 2090918 : let end = (end.field5 as u64) << 32 | end.field6 as u64;
324 2090918 :
325 2090918 : let diff = end - start;
326 2090918 : if diff > u32::MAX as u64 {
327 0 : u32::MAX
328 : } else {
329 2090918 : diff as u32
330 : }
331 2090918 : }
332 :
333 2078120 : pub fn singleton_range(key: Key) -> Range<Key> {
334 2078120 : key..key.next()
335 2078120 : }
336 :
337 : #[cfg(test)]
338 : mod tests {
339 : use super::*;
340 : use std::fmt::Write;
341 :
342 : // Helper function to create a key range.
343 : //
344 : // Make the tests below less verbose.
345 92 : fn kr(irange: Range<i128>) -> Range<Key> {
346 92 : Key::from_i128(irange.start)..Key::from_i128(irange.end)
347 92 : }
348 :
349 : #[allow(dead_code)]
350 0 : fn dump_keyspace(ks: &KeySpace) {
351 0 : for r in ks.ranges.iter() {
352 0 : println!(" {}..{}", r.start.to_i128(), r.end.to_i128());
353 0 : }
354 0 : }
355 :
356 22 : fn assert_ks_eq(actual: &KeySpace, expected: Vec<Range<Key>>) {
357 22 : if actual.ranges != expected {
358 0 : let mut msg = String::new();
359 0 :
360 0 : writeln!(msg, "expected:").unwrap();
361 0 : for r in &expected {
362 0 : writeln!(msg, " {}..{}", r.start.to_i128(), r.end.to_i128()).unwrap();
363 0 : }
364 0 : writeln!(msg, "got:").unwrap();
365 0 : for r in &actual.ranges {
366 0 : writeln!(msg, " {}..{}", r.start.to_i128(), r.end.to_i128()).unwrap();
367 0 : }
368 0 : panic!("{}", msg);
369 22 : }
370 22 : }
371 :
372 2 : #[test]
373 2 : fn keyspace_consume() {
374 2 : let ranges = vec![kr(0..10), kr(20..35), kr(40..45)];
375 2 :
376 2 : let mut accum = KeySpaceAccum::new();
377 8 : for range in &ranges {
378 6 : accum.add_range(range.clone());
379 6 : }
380 :
381 6 : let expected_size: u64 = ranges.iter().map(|r| key_range_size(r) as u64).sum();
382 2 : assert_eq!(accum.size(), expected_size);
383 :
384 2 : assert_ks_eq(&accum.consume_keyspace(), ranges.clone());
385 2 : assert_eq!(accum.size(), 0);
386 :
387 2 : assert_ks_eq(&accum.consume_keyspace(), vec![]);
388 2 : assert_eq!(accum.size(), 0);
389 :
390 8 : for range in &ranges {
391 6 : accum.add_range(range.clone());
392 6 : }
393 2 : assert_ks_eq(&accum.to_keyspace(), ranges);
394 2 : }
395 :
396 2 : #[test]
397 2 : fn keyspace_add_range() {
398 2 : // two separate ranges
399 2 : //
400 2 : // #####
401 2 : // #####
402 2 : let mut ks = KeySpaceRandomAccum::default();
403 2 : ks.add_range(kr(0..10));
404 2 : ks.add_range(kr(20..30));
405 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..10), kr(20..30)]);
406 2 :
407 2 : // two separate ranges, added in reverse order
408 2 : //
409 2 : // #####
410 2 : // #####
411 2 : let mut ks = KeySpaceRandomAccum::default();
412 2 : ks.add_range(kr(20..30));
413 2 : ks.add_range(kr(0..10));
414 2 :
415 2 : // add range that is adjacent to the end of an existing range
416 2 : //
417 2 : // #####
418 2 : // #####
419 2 : ks.add_range(kr(0..10));
420 2 : ks.add_range(kr(10..30));
421 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..30)]);
422 2 :
423 2 : // add range that is adjacent to the start of an existing range
424 2 : //
425 2 : // #####
426 2 : // #####
427 2 : let mut ks = KeySpaceRandomAccum::default();
428 2 : ks.add_range(kr(10..30));
429 2 : ks.add_range(kr(0..10));
430 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..30)]);
431 2 :
432 2 : // add range that overlaps with the end of an existing range
433 2 : //
434 2 : // #####
435 2 : // #####
436 2 : let mut ks = KeySpaceRandomAccum::default();
437 2 : ks.add_range(kr(0..10));
438 2 : ks.add_range(kr(5..30));
439 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..30)]);
440 2 :
441 2 : // add range that overlaps with the start of an existing range
442 2 : //
443 2 : // #####
444 2 : // #####
445 2 : let mut ks = KeySpaceRandomAccum::default();
446 2 : ks.add_range(kr(5..30));
447 2 : ks.add_range(kr(0..10));
448 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..30)]);
449 2 :
450 2 : // add range that is fully covered by an existing range
451 2 : //
452 2 : // #########
453 2 : // #####
454 2 : let mut ks = KeySpaceRandomAccum::default();
455 2 : ks.add_range(kr(0..30));
456 2 : ks.add_range(kr(10..20));
457 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..30)]);
458 2 :
459 2 : // add range that extends an existing range from both ends
460 2 : //
461 2 : // #####
462 2 : // #########
463 2 : let mut ks = KeySpaceRandomAccum::default();
464 2 : ks.add_range(kr(10..20));
465 2 : ks.add_range(kr(0..30));
466 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..30)]);
467 2 :
468 2 : // add a range that overlaps with two existing ranges, joining them
469 2 : //
470 2 : // ##### #####
471 2 : // #######
472 2 : let mut ks = KeySpaceRandomAccum::default();
473 2 : ks.add_range(kr(0..10));
474 2 : ks.add_range(kr(20..30));
475 2 : ks.add_range(kr(5..25));
476 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..30)]);
477 2 : }
478 :
479 2 : #[test]
480 2 : fn keyspace_overlaps() {
481 2 : let mut ks = KeySpaceRandomAccum::default();
482 2 : ks.add_range(kr(10..20));
483 2 : ks.add_range(kr(30..40));
484 2 : let ks = ks.to_keyspace();
485 2 :
486 2 : // ##### #####
487 2 : // xxxx
488 2 : assert!(!ks.overlaps(&kr(0..5)));
489 :
490 : // ##### #####
491 : // xxxx
492 2 : assert!(!ks.overlaps(&kr(5..9)));
493 :
494 : // ##### #####
495 : // xxxx
496 2 : assert!(!ks.overlaps(&kr(5..10)));
497 :
498 : // ##### #####
499 : // xxxx
500 2 : assert!(ks.overlaps(&kr(5..11)));
501 :
502 : // ##### #####
503 : // xxxx
504 2 : assert!(ks.overlaps(&kr(10..15)));
505 :
506 : // ##### #####
507 : // xxxx
508 2 : assert!(ks.overlaps(&kr(15..20)));
509 :
510 : // ##### #####
511 : // xxxx
512 2 : assert!(ks.overlaps(&kr(15..25)));
513 :
514 : // ##### #####
515 : // xxxx
516 2 : assert!(!ks.overlaps(&kr(22..28)));
517 :
518 : // ##### #####
519 : // xxxx
520 2 : assert!(!ks.overlaps(&kr(25..30)));
521 :
522 : // ##### #####
523 : // xxxx
524 2 : assert!(ks.overlaps(&kr(35..35)));
525 :
526 : // ##### #####
527 : // xxxx
528 2 : assert!(!ks.overlaps(&kr(40..45)));
529 :
530 : // ##### #####
531 : // xxxx
532 2 : assert!(!ks.overlaps(&kr(45..50)));
533 :
534 : // ##### #####
535 : // xxxxxxxxxxx
536 2 : assert!(ks.overlaps(&kr(0..30))); // XXXXX This fails currently!
537 2 : }
538 :
539 2 : #[test]
540 2 : fn test_remove_full_overlapps() {
541 2 : let mut key_space1 = KeySpace {
542 2 : ranges: vec![
543 2 : Key::from_i128(1)..Key::from_i128(4),
544 2 : Key::from_i128(5)..Key::from_i128(8),
545 2 : Key::from_i128(10)..Key::from_i128(12),
546 2 : ],
547 2 : };
548 2 : let key_space2 = KeySpace {
549 2 : ranges: vec![
550 2 : Key::from_i128(2)..Key::from_i128(3),
551 2 : Key::from_i128(6)..Key::from_i128(7),
552 2 : Key::from_i128(11)..Key::from_i128(13),
553 2 : ],
554 2 : };
555 2 : key_space1.remove_overlapping_with(&key_space2);
556 2 : assert_eq!(
557 2 : key_space1.ranges,
558 2 : vec![
559 2 : Key::from_i128(1)..Key::from_i128(2),
560 2 : Key::from_i128(3)..Key::from_i128(4),
561 2 : Key::from_i128(5)..Key::from_i128(6),
562 2 : Key::from_i128(7)..Key::from_i128(8),
563 2 : Key::from_i128(10)..Key::from_i128(11)
564 2 : ]
565 2 : );
566 2 : }
567 :
568 2 : #[test]
569 2 : fn test_remove_partial_overlaps() {
570 2 : // Test partial ovelaps
571 2 : let mut key_space1 = KeySpace {
572 2 : ranges: vec![
573 2 : Key::from_i128(1)..Key::from_i128(5),
574 2 : Key::from_i128(7)..Key::from_i128(10),
575 2 : Key::from_i128(12)..Key::from_i128(15),
576 2 : ],
577 2 : };
578 2 : let key_space2 = KeySpace {
579 2 : ranges: vec![
580 2 : Key::from_i128(3)..Key::from_i128(6),
581 2 : Key::from_i128(8)..Key::from_i128(11),
582 2 : Key::from_i128(14)..Key::from_i128(17),
583 2 : ],
584 2 : };
585 2 : key_space1.remove_overlapping_with(&key_space2);
586 2 : assert_eq!(
587 2 : key_space1.ranges,
588 2 : vec![
589 2 : Key::from_i128(1)..Key::from_i128(3),
590 2 : Key::from_i128(7)..Key::from_i128(8),
591 2 : Key::from_i128(12)..Key::from_i128(14),
592 2 : ]
593 2 : );
594 2 : }
595 :
596 2 : #[test]
597 2 : fn test_remove_no_overlaps() {
598 2 : let mut key_space1 = KeySpace {
599 2 : ranges: vec![
600 2 : Key::from_i128(1)..Key::from_i128(5),
601 2 : Key::from_i128(7)..Key::from_i128(10),
602 2 : Key::from_i128(12)..Key::from_i128(15),
603 2 : ],
604 2 : };
605 2 : let key_space2 = KeySpace {
606 2 : ranges: vec![
607 2 : Key::from_i128(6)..Key::from_i128(7),
608 2 : Key::from_i128(11)..Key::from_i128(12),
609 2 : Key::from_i128(15)..Key::from_i128(17),
610 2 : ],
611 2 : };
612 2 : key_space1.remove_overlapping_with(&key_space2);
613 2 : assert_eq!(
614 2 : key_space1.ranges,
615 2 : vec![
616 2 : Key::from_i128(1)..Key::from_i128(5),
617 2 : Key::from_i128(7)..Key::from_i128(10),
618 2 : Key::from_i128(12)..Key::from_i128(15),
619 2 : ]
620 2 : );
621 2 : }
622 :
623 2 : #[test]
624 2 : fn test_remove_one_range_overlaps_multiple() {
625 2 : let mut key_space1 = KeySpace {
626 2 : ranges: vec![
627 2 : Key::from_i128(1)..Key::from_i128(3),
628 2 : Key::from_i128(3)..Key::from_i128(6),
629 2 : Key::from_i128(6)..Key::from_i128(10),
630 2 : Key::from_i128(12)..Key::from_i128(15),
631 2 : Key::from_i128(17)..Key::from_i128(20),
632 2 : Key::from_i128(20)..Key::from_i128(30),
633 2 : Key::from_i128(30)..Key::from_i128(40),
634 2 : ],
635 2 : };
636 2 : let key_space2 = KeySpace {
637 2 : ranges: vec![Key::from_i128(9)..Key::from_i128(19)],
638 2 : };
639 2 : key_space1.remove_overlapping_with(&key_space2);
640 2 : assert_eq!(
641 2 : key_space1.ranges,
642 2 : vec![
643 2 : Key::from_i128(1)..Key::from_i128(3),
644 2 : Key::from_i128(3)..Key::from_i128(6),
645 2 : Key::from_i128(6)..Key::from_i128(9),
646 2 : Key::from_i128(19)..Key::from_i128(20),
647 2 : Key::from_i128(20)..Key::from_i128(30),
648 2 : Key::from_i128(30)..Key::from_i128(40),
649 2 : ]
650 2 : );
651 2 : }
652 : }
|
