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 174 : pub fn partition(&self, target_size: u64) -> KeyPartitioning {
23 174 : // Assume that each value is 8k in size.
24 174 : let target_nblocks = (target_size / BLCKSZ as u64) as usize;
25 174 :
26 174 : let mut parts = Vec::new();
27 174 : let mut current_part = Vec::new();
28 174 : let mut current_part_size: usize = 0;
29 1218 : 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 1044 : let this_size = key_range_size(range) as usize;
33 1044 : 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 1044 : }
40 :
41 : // If the next range is larger than 'target_size', split it into
42 : // 'target_size' chunks.
43 1044 : let mut remain_size = this_size;
44 1044 : let mut start = range.start;
45 1044 : 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 1044 : current_part.push(start..range.end);
54 1044 : current_part_size += remain_size;
55 : }
56 :
57 : // add last partition that wasn't full yet.
58 174 : if !current_part.is_empty() {
59 174 : parts.push(KeySpace {
60 174 : ranges: current_part,
61 174 : });
62 174 : }
63 :
64 174 : KeyPartitioning { parts }
65 174 : }
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 464 : pub fn total_size(&self) -> usize {
151 464 : self.ranges
152 464 : .iter()
153 464 : .map(|range| key_range_size(range) as usize)
154 464 : .sum()
155 464 : }
156 :
157 102 : fn overlaps_at(&self, range: &Range<Key>) -> Option<usize> {
158 134 : match self.ranges.binary_search_by_key(&range.end, |r| r.start) {
159 2 : Ok(0) => None,
160 24 : 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 102 : }
166 :
167 : ///
168 : /// Check if key space contains overlapping range
169 : ///
170 26 : pub fn overlaps(&self, range: &Range<Key>) -> bool {
171 26 : self.overlaps_at(range).is_some()
172 26 : }
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 482 : #[derive(Clone, Debug, Default)]
183 : pub struct KeyPartitioning {
184 : pub parts: Vec<KeySpace>,
185 : }
186 :
187 : impl KeyPartitioning {
188 296 : pub fn new() -> Self {
189 296 : KeyPartitioning { parts: Vec::new() }
190 296 : }
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 16918 : #[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 7368 : pub fn new() -> Self {
208 7368 : Self {
209 7368 : accum: None,
210 7368 : ranges: Vec::new(),
211 7368 : size: 0,
212 7368 : }
213 7368 : }
214 :
215 : #[inline(always)]
216 2077864 : pub fn add_key(&mut self, key: Key) {
217 2077864 : self.add_range(singleton_range(key))
218 2077864 : }
219 :
220 : #[inline(always)]
221 2089536 : pub fn add_range(&mut self, range: Range<Key>) {
222 2089536 : self.size += key_range_size(&range) as u64;
223 2089536 :
224 2089536 : match self.accum.as_mut() {
225 2068626 : Some(accum) => {
226 2068626 : if range.start == accum.end {
227 2064728 : accum.end = range.end;
228 2064728 : } 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 3898 : assert!(range.start > accum.end);
233 3898 : self.ranges.push(accum.clone());
234 3898 : *accum = range;
235 : }
236 : }
237 20910 : None => self.accum = Some(range),
238 : }
239 2089536 : }
240 :
241 24194 : pub fn to_keyspace(mut self) -> KeySpace {
242 24194 : if let Some(accum) = self.accum.take() {
243 20902 : self.ranges.push(accum);
244 20902 : }
245 24194 : KeySpace {
246 24194 : ranges: self.ranges,
247 24194 : }
248 24194 : }
249 :
250 448 : pub fn consume_keyspace(&mut self) -> KeySpace {
251 448 : std::mem::take(self).to_keyspace()
252 448 : }
253 :
254 598 : pub fn size(&self) -> u64 {
255 598 : self.size
256 598 : }
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 18 : #[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 38 : pub fn to_keyspace(mut self) -> KeySpace {
282 38 : let mut ranges = Vec::new();
283 38 : 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 10 : }
299 38 : KeySpace { ranges }
300 38 : }
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 : #[inline(always)]
311 2091030 : pub fn key_range_size(key_range: &Range<Key>) -> u32 {
312 2091030 : let start = key_range.start;
313 2091030 : let end = key_range.end;
314 2091030 :
315 2091030 : if end.field1 != start.field1
316 2091030 : || end.field2 != start.field2
317 2091030 : || end.field3 != start.field3
318 2091030 : || end.field4 != start.field4
319 : {
320 0 : return u32::MAX;
321 2091030 : }
322 2091030 :
323 2091030 : let start = (start.field5 as u64) << 32 | start.field6 as u64;
324 2091030 : let end = (end.field5 as u64) << 32 | end.field6 as u64;
325 2091030 :
326 2091030 : let diff = end - start;
327 2091030 : if diff > u32::MAX as u64 {
328 0 : u32::MAX
329 : } else {
330 2091030 : diff as u32
331 : }
332 2091030 : }
333 :
334 2078184 : pub fn singleton_range(key: Key) -> Range<Key> {
335 2078184 : key..key.next()
336 2078184 : }
337 :
338 : #[cfg(test)]
339 : mod tests {
340 : use super::*;
341 : use std::fmt::Write;
342 :
343 : // Helper function to create a key range.
344 : //
345 : // Make the tests below less verbose.
346 92 : fn kr(irange: Range<i128>) -> Range<Key> {
347 92 : Key::from_i128(irange.start)..Key::from_i128(irange.end)
348 92 : }
349 :
350 : #[allow(dead_code)]
351 0 : fn dump_keyspace(ks: &KeySpace) {
352 0 : for r in ks.ranges.iter() {
353 0 : println!(" {}..{}", r.start.to_i128(), r.end.to_i128());
354 0 : }
355 0 : }
356 :
357 22 : fn assert_ks_eq(actual: &KeySpace, expected: Vec<Range<Key>>) {
358 22 : if actual.ranges != expected {
359 0 : let mut msg = String::new();
360 0 :
361 0 : writeln!(msg, "expected:").unwrap();
362 0 : for r in &expected {
363 0 : writeln!(msg, " {}..{}", r.start.to_i128(), r.end.to_i128()).unwrap();
364 0 : }
365 0 : writeln!(msg, "got:").unwrap();
366 0 : for r in &actual.ranges {
367 0 : writeln!(msg, " {}..{}", r.start.to_i128(), r.end.to_i128()).unwrap();
368 0 : }
369 0 : panic!("{}", msg);
370 22 : }
371 22 : }
372 :
373 2 : #[test]
374 2 : fn keyspace_consume() {
375 2 : let ranges = vec![kr(0..10), kr(20..35), kr(40..45)];
376 2 :
377 2 : let mut accum = KeySpaceAccum::new();
378 8 : for range in &ranges {
379 6 : accum.add_range(range.clone());
380 6 : }
381 :
382 6 : let expected_size: u64 = ranges.iter().map(|r| key_range_size(r) as u64).sum();
383 2 : assert_eq!(accum.size(), expected_size);
384 :
385 2 : assert_ks_eq(&accum.consume_keyspace(), ranges.clone());
386 2 : assert_eq!(accum.size(), 0);
387 :
388 2 : assert_ks_eq(&accum.consume_keyspace(), vec![]);
389 2 : assert_eq!(accum.size(), 0);
390 :
391 8 : for range in &ranges {
392 6 : accum.add_range(range.clone());
393 6 : }
394 2 : assert_ks_eq(&accum.to_keyspace(), ranges);
395 2 : }
396 :
397 2 : #[test]
398 2 : fn keyspace_add_range() {
399 2 : // two separate ranges
400 2 : //
401 2 : // #####
402 2 : // #####
403 2 : let mut ks = KeySpaceRandomAccum::default();
404 2 : ks.add_range(kr(0..10));
405 2 : ks.add_range(kr(20..30));
406 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..10), kr(20..30)]);
407 2 :
408 2 : // two separate ranges, added in reverse order
409 2 : //
410 2 : // #####
411 2 : // #####
412 2 : let mut ks = KeySpaceRandomAccum::default();
413 2 : ks.add_range(kr(20..30));
414 2 : ks.add_range(kr(0..10));
415 2 :
416 2 : // add range that is adjacent to the end of an existing range
417 2 : //
418 2 : // #####
419 2 : // #####
420 2 : ks.add_range(kr(0..10));
421 2 : ks.add_range(kr(10..30));
422 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..30)]);
423 2 :
424 2 : // add range that is adjacent to the start of an existing range
425 2 : //
426 2 : // #####
427 2 : // #####
428 2 : let mut ks = KeySpaceRandomAccum::default();
429 2 : ks.add_range(kr(10..30));
430 2 : ks.add_range(kr(0..10));
431 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..30)]);
432 2 :
433 2 : // add range that overlaps with the end of an existing range
434 2 : //
435 2 : // #####
436 2 : // #####
437 2 : let mut ks = KeySpaceRandomAccum::default();
438 2 : ks.add_range(kr(0..10));
439 2 : ks.add_range(kr(5..30));
440 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..30)]);
441 2 :
442 2 : // add range that overlaps with the start of an existing range
443 2 : //
444 2 : // #####
445 2 : // #####
446 2 : let mut ks = KeySpaceRandomAccum::default();
447 2 : ks.add_range(kr(5..30));
448 2 : ks.add_range(kr(0..10));
449 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..30)]);
450 2 :
451 2 : // add range that is fully covered by an existing range
452 2 : //
453 2 : // #########
454 2 : // #####
455 2 : let mut ks = KeySpaceRandomAccum::default();
456 2 : ks.add_range(kr(0..30));
457 2 : ks.add_range(kr(10..20));
458 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..30)]);
459 2 :
460 2 : // add range that extends an existing range from both ends
461 2 : //
462 2 : // #####
463 2 : // #########
464 2 : let mut ks = KeySpaceRandomAccum::default();
465 2 : ks.add_range(kr(10..20));
466 2 : ks.add_range(kr(0..30));
467 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..30)]);
468 2 :
469 2 : // add a range that overlaps with two existing ranges, joining them
470 2 : //
471 2 : // ##### #####
472 2 : // #######
473 2 : let mut ks = KeySpaceRandomAccum::default();
474 2 : ks.add_range(kr(0..10));
475 2 : ks.add_range(kr(20..30));
476 2 : ks.add_range(kr(5..25));
477 2 : assert_ks_eq(&ks.to_keyspace(), vec![kr(0..30)]);
478 2 : }
479 :
480 2 : #[test]
481 2 : fn keyspace_overlaps() {
482 2 : let mut ks = KeySpaceRandomAccum::default();
483 2 : ks.add_range(kr(10..20));
484 2 : ks.add_range(kr(30..40));
485 2 : let ks = ks.to_keyspace();
486 2 :
487 2 : // ##### #####
488 2 : // xxxx
489 2 : assert!(!ks.overlaps(&kr(0..5)));
490 :
491 : // ##### #####
492 : // xxxx
493 2 : assert!(!ks.overlaps(&kr(5..9)));
494 :
495 : // ##### #####
496 : // xxxx
497 2 : assert!(!ks.overlaps(&kr(5..10)));
498 :
499 : // ##### #####
500 : // xxxx
501 2 : assert!(ks.overlaps(&kr(5..11)));
502 :
503 : // ##### #####
504 : // xxxx
505 2 : assert!(ks.overlaps(&kr(10..15)));
506 :
507 : // ##### #####
508 : // xxxx
509 2 : assert!(ks.overlaps(&kr(15..20)));
510 :
511 : // ##### #####
512 : // xxxx
513 2 : assert!(ks.overlaps(&kr(15..25)));
514 :
515 : // ##### #####
516 : // xxxx
517 2 : assert!(!ks.overlaps(&kr(22..28)));
518 :
519 : // ##### #####
520 : // xxxx
521 2 : assert!(!ks.overlaps(&kr(25..30)));
522 :
523 : // ##### #####
524 : // xxxx
525 2 : assert!(ks.overlaps(&kr(35..35)));
526 :
527 : // ##### #####
528 : // xxxx
529 2 : assert!(!ks.overlaps(&kr(40..45)));
530 :
531 : // ##### #####
532 : // xxxx
533 2 : assert!(!ks.overlaps(&kr(45..50)));
534 :
535 : // ##### #####
536 : // xxxxxxxxxxx
537 2 : assert!(ks.overlaps(&kr(0..30))); // XXXXX This fails currently!
538 2 : }
539 :
540 2 : #[test]
541 2 : fn test_remove_full_overlapps() {
542 2 : let mut key_space1 = KeySpace {
543 2 : ranges: vec![
544 2 : Key::from_i128(1)..Key::from_i128(4),
545 2 : Key::from_i128(5)..Key::from_i128(8),
546 2 : Key::from_i128(10)..Key::from_i128(12),
547 2 : ],
548 2 : };
549 2 : let key_space2 = KeySpace {
550 2 : ranges: vec![
551 2 : Key::from_i128(2)..Key::from_i128(3),
552 2 : Key::from_i128(6)..Key::from_i128(7),
553 2 : Key::from_i128(11)..Key::from_i128(13),
554 2 : ],
555 2 : };
556 2 : key_space1.remove_overlapping_with(&key_space2);
557 2 : assert_eq!(
558 2 : key_space1.ranges,
559 2 : vec![
560 2 : Key::from_i128(1)..Key::from_i128(2),
561 2 : Key::from_i128(3)..Key::from_i128(4),
562 2 : Key::from_i128(5)..Key::from_i128(6),
563 2 : Key::from_i128(7)..Key::from_i128(8),
564 2 : Key::from_i128(10)..Key::from_i128(11)
565 2 : ]
566 2 : );
567 2 : }
568 :
569 2 : #[test]
570 2 : fn test_remove_partial_overlaps() {
571 2 : // Test partial ovelaps
572 2 : let mut key_space1 = KeySpace {
573 2 : ranges: vec![
574 2 : Key::from_i128(1)..Key::from_i128(5),
575 2 : Key::from_i128(7)..Key::from_i128(10),
576 2 : Key::from_i128(12)..Key::from_i128(15),
577 2 : ],
578 2 : };
579 2 : let key_space2 = KeySpace {
580 2 : ranges: vec![
581 2 : Key::from_i128(3)..Key::from_i128(6),
582 2 : Key::from_i128(8)..Key::from_i128(11),
583 2 : Key::from_i128(14)..Key::from_i128(17),
584 2 : ],
585 2 : };
586 2 : key_space1.remove_overlapping_with(&key_space2);
587 2 : assert_eq!(
588 2 : key_space1.ranges,
589 2 : vec![
590 2 : Key::from_i128(1)..Key::from_i128(3),
591 2 : Key::from_i128(7)..Key::from_i128(8),
592 2 : Key::from_i128(12)..Key::from_i128(14),
593 2 : ]
594 2 : );
595 2 : }
596 :
597 2 : #[test]
598 2 : fn test_remove_no_overlaps() {
599 2 : let mut key_space1 = KeySpace {
600 2 : ranges: vec![
601 2 : Key::from_i128(1)..Key::from_i128(5),
602 2 : Key::from_i128(7)..Key::from_i128(10),
603 2 : Key::from_i128(12)..Key::from_i128(15),
604 2 : ],
605 2 : };
606 2 : let key_space2 = KeySpace {
607 2 : ranges: vec![
608 2 : Key::from_i128(6)..Key::from_i128(7),
609 2 : Key::from_i128(11)..Key::from_i128(12),
610 2 : Key::from_i128(15)..Key::from_i128(17),
611 2 : ],
612 2 : };
613 2 : key_space1.remove_overlapping_with(&key_space2);
614 2 : assert_eq!(
615 2 : key_space1.ranges,
616 2 : vec![
617 2 : Key::from_i128(1)..Key::from_i128(5),
618 2 : Key::from_i128(7)..Key::from_i128(10),
619 2 : Key::from_i128(12)..Key::from_i128(15),
620 2 : ]
621 2 : );
622 2 : }
623 :
624 2 : #[test]
625 2 : fn test_remove_one_range_overlaps_multiple() {
626 2 : let mut key_space1 = KeySpace {
627 2 : ranges: vec![
628 2 : Key::from_i128(1)..Key::from_i128(3),
629 2 : Key::from_i128(3)..Key::from_i128(6),
630 2 : Key::from_i128(6)..Key::from_i128(10),
631 2 : Key::from_i128(12)..Key::from_i128(15),
632 2 : Key::from_i128(17)..Key::from_i128(20),
633 2 : Key::from_i128(20)..Key::from_i128(30),
634 2 : Key::from_i128(30)..Key::from_i128(40),
635 2 : ],
636 2 : };
637 2 : let key_space2 = KeySpace {
638 2 : ranges: vec![Key::from_i128(9)..Key::from_i128(19)],
639 2 : };
640 2 : key_space1.remove_overlapping_with(&key_space2);
641 2 : assert_eq!(
642 2 : key_space1.ranges,
643 2 : vec![
644 2 : Key::from_i128(1)..Key::from_i128(3),
645 2 : Key::from_i128(3)..Key::from_i128(6),
646 2 : Key::from_i128(6)..Key::from_i128(9),
647 2 : Key::from_i128(19)..Key::from_i128(20),
648 2 : Key::from_i128(20)..Key::from_i128(30),
649 2 : Key::from_i128(30)..Key::from_i128(40),
650 2 : ]
651 2 : );
652 2 : }
653 : }
|
