seq_marked/seq_marked/
mod.rs

1mod impl_display;
2mod impl_from_seqv;
3mod impl_seq_value;
4mod impl_try_from_meta_bytes;
5
6use std::fmt;
7
8use crate::Marked;
9
10/// Sequence-numbered marked value.
11///
12/// Ordered by sequence number first, then tombstone > normal.
13///
14/// ```rust
15/// use seq_marked::SeqMarked;
16///
17/// let v1 = SeqMarked::new_normal(1, "data");
18/// let v2 = SeqMarked::<&str>::new_tombstone(2);
19/// assert!(v1 < v2);
20/// ```
21#[derive(Debug)]
22#[derive(Clone, Copy)]
23#[derive(PartialEq, Eq)]
24#[derive(PartialOrd, Ord)]
25#[cfg_attr(
26    feature = "seq-marked-serde",
27    derive(serde::Serialize, serde::Deserialize)
28)]
29#[cfg_attr(
30    feature = "seq-marked-bincode",
31    derive(bincode::Encode, bincode::Decode)
32)]
33pub struct SeqMarked<D = Vec<u8>> {
34    // Keep the `seq` as the first field so that it can be compared first.
35    seq: u64,
36    marked: Marked<D>,
37}
38
39impl<D> SeqMarked<D> {
40    /// Creates a new `SeqMarked` with sequence number and marked data.
41    pub fn new(seq: u64, marked: Marked<D>) -> Self {
42        Self { seq, marked }
43    }
44
45    /// Creates normal value with sequence number.
46    pub fn new_normal(seq: u64, data: D) -> Self {
47        Self {
48            seq,
49            marked: Marked::Normal(data),
50        }
51    }
52
53    /// Creates tombstone with sequence number.
54    pub fn new_tombstone(seq: u64) -> Self {
55        Self {
56            seq,
57            marked: Marked::TombStone,
58        }
59    }
60
61    /// Represents an absent record (not even marked as deleted).
62    pub fn new_not_found() -> Self {
63        Self {
64            seq: 0,
65            marked: Marked::TombStone,
66        }
67    }
68
69    /// Returns `true` if this is normal data.
70    pub fn is_normal(&self) -> bool {
71        !self.is_tombstone()
72    }
73
74    /// Returns `true` if this is a tombstone.
75    pub fn is_tombstone(&self) -> bool {
76        match self.marked {
77            Marked::Normal(_) => false,
78            Marked::TombStone => true,
79        }
80    }
81
82    pub fn is_not_found(&self) -> bool {
83        self.is_absent()
84    }
85
86    pub fn is_absent(&self) -> bool {
87        self.seq == 0 && self.is_tombstone()
88    }
89
90    /// Transforms data `D` to `U` while preserving sequence and tombstone state.
91    ///
92    /// # Example
93    ///
94    /// ```rust
95    /// use seq_marked::SeqMarked;
96    ///
97    /// let a = SeqMarked::new_normal(1, "data");
98    /// let b = a.map(|x| x.len());
99    /// assert_eq!(b.data_ref(), Some(&4));
100    /// ```
101    pub fn map<U>(self, f: impl FnOnce(D) -> U) -> SeqMarked<U> {
102        SeqMarked {
103            seq: self.seq,
104            marked: match self.marked {
105                Marked::Normal(data) => Marked::<U>::Normal(f(data)),
106                Marked::TombStone => Marked::<U>::TombStone,
107            },
108        }
109    }
110
111    pub fn try_map<U, E>(self, f: impl FnOnce(D) -> Result<U, E>) -> Result<SeqMarked<U>, E> {
112        Ok(SeqMarked {
113            seq: self.seq,
114            marked: match self.marked {
115                Marked::Normal(data) => Marked::<U>::Normal(f(data)?),
116                Marked::TombStone => Marked::<U>::TombStone,
117            },
118        })
119    }
120
121    /// Creates reference to the data.
122    pub fn as_ref(&self) -> SeqMarked<&D> {
123        SeqMarked {
124            seq: self.seq,
125            marked: match &self.marked {
126                Marked::Normal(data) => Marked::Normal(data),
127                Marked::TombStone => Marked::TombStone,
128            },
129        }
130    }
131
132    /// Returns ordering key (sequence + tombstone state only).
133    pub fn order_key(&self) -> SeqMarked<()> {
134        SeqMarked {
135            seq: self.seq,
136            marked: match &self.marked {
137                Marked::Normal(_) => Marked::Normal(()),
138                Marked::TombStone => Marked::TombStone,
139            },
140        }
141    }
142
143    /// Returns the sequence number for internal use, tombstone also has a seq.
144    pub fn internal_seq(&self) -> u64 {
145        self.seq
146    }
147
148    /// Returns the sequence number for application use, tombstone always has seq 0.
149    pub fn user_seq(&self) -> u64 {
150        if self.is_tombstone() { 0 } else { self.seq }
151    }
152
153    /// Returns the maximum of two values.
154    pub fn max(a: Self, b: Self) -> Self {
155        if a.order_key() > b.order_key() { a } else { b }
156    }
157
158    /// Returns the maximum of two values.
159    pub fn max_ref<'l>(a: &'l Self, b: &'l Self) -> &'l Self {
160        if a.order_key() > b.order_key() { a } else { b }
161    }
162
163    /// Returns reference to data if normal, `None` if tombstone.
164    pub fn data_ref(&self) -> Option<&D> {
165        match self.marked {
166            Marked::Normal(ref d) => Some(d),
167            Marked::TombStone => None,
168        }
169    }
170
171    /// Consumes and returns data if normal, `None` if tombstone.
172    pub fn into_data(self) -> Option<D> {
173        match self.marked {
174            Marked::Normal(data) => Some(data),
175            Marked::TombStone => None,
176        }
177    }
178
179    pub fn into_parts(self) -> (u64, Marked<D>) {
180        (self.seq, self.marked)
181    }
182
183    /// Returns formatter for display using `Debug` trait.
184    pub fn display_with_debug(&self) -> impl fmt::Display + '_
185    where D: fmt::Debug {
186        struct DisplaySeqMarked<'a, D>(&'a SeqMarked<D>);
187
188        impl<D> fmt::Display for DisplaySeqMarked<'_, D>
189        where D: fmt::Debug
190        {
191            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
192                write!(f, "{{seq: {}, ", self.0.seq)?;
193                match &self.0.marked {
194                    Marked::Normal(data) => write!(f, "({:?})", data)?,
195                    Marked::TombStone => write!(f, "TOMBSTONE")?,
196                }
197                write!(f, "}}")
198            }
199        }
200
201        DisplaySeqMarked(self)
202    }
203}
204
205#[cfg(test)]
206mod tests {
207    use std::cmp::Ordering;
208
209    use Ordering::Equal;
210    use Ordering::Greater;
211    use Ordering::Less;
212
213    use super::*;
214    use crate::testing::norm;
215    use crate::testing::ts;
216
217    #[test]
218    fn test_seq_marked_is_copy() {
219        let seq_marked = SeqMarked::new(5, Marked::Normal("data"));
220        let seq_marked_copy = seq_marked;
221        assert_eq!(seq_marked, seq_marked_copy);
222    }
223
224    #[test]
225    fn test_new() {
226        let seq_marked = SeqMarked::new(5, Marked::Normal("data"));
227        assert_eq!(seq_marked.seq, 5);
228        assert_eq!(seq_marked.marked, Marked::Normal("data"));
229    }
230
231    #[test]
232    fn test_map() -> anyhow::Result<()> {
233        let a = norm(1, 1u64);
234        assert_eq!(norm(1, 2u32), a.map(|x| (x * 2) as u32));
235
236        let a = ts::<u64>(1);
237        assert_eq!(ts::<u32>(1), a.map(|x| (x * 2) as u32));
238
239        Ok(())
240    }
241
242    #[test]
243    fn test_as_ref() -> anyhow::Result<()> {
244        let a = norm(1, 1u64);
245        assert_eq!(norm(1, &1u64), a.as_ref());
246
247        let a = ts::<u64>(1);
248        assert_eq!(ts::<&u64>(1), a.as_ref());
249
250        Ok(())
251    }
252
253    #[test]
254    fn test_order_key() -> anyhow::Result<()> {
255        assert!(norm(1, 1u64).order_key() == norm(1, 1u64).order_key());
256        assert!(norm(1, 2u64).order_key() == norm(1, 1u64).order_key());
257        assert!(norm(2, 2u64).order_key() > norm(1, 1u64).order_key());
258
259        assert!(ts::<u64>(1).order_key() > norm(1, 1u64).order_key());
260        assert!(ts::<u64>(2).order_key() > norm(1, 1u64).order_key());
261
262        assert!(ts::<u64>(2).order_key() > ts::<u64>(1).order_key());
263        assert!(ts::<u64>(1).order_key() == ts::<u64>(1).order_key());
264
265        Ok(())
266    }
267
268    #[test]
269    fn test_partial_ord() -> anyhow::Result<()> {
270        fn pcmp<D: PartialOrd>(a: &SeqMarked<D>, b: &SeqMarked<D>) -> Option<Ordering> {
271            PartialOrd::partial_cmp(a, b)
272        }
273
274        // normal vs normal, with the same data
275
276        assert_eq!(Some(Greater), pcmp(&norm(2, 2u64), &norm(1, 2u64)));
277        assert_eq!(Some(Equal), pcmp(&norm(2, 2u64), &norm(2, 2u64)));
278        assert_eq!(Some(Less), pcmp(&norm(2, 2u64), &norm(3, 2u64)));
279
280        // normal vs normal, same seq, different value
281
282        assert_eq!(Some(Greater), pcmp(&norm(2, 2u64), &norm(2, 1u64)));
283        assert_eq!(Some(Equal), pcmp(&norm(2, 2u64), &norm(2, 2u64)));
284        assert_eq!(Some(Less), pcmp(&norm(2, 2u64), &norm(2, 3u64)));
285
286        // normal vs tombstone
287
288        assert_eq!(Some(Greater), pcmp(&norm(2, 2u64), &ts(1)));
289        assert_eq!(
290            Some(Less),
291            pcmp(&norm(2, 2u64), &ts(2)),
292            "tombstone is greater than a normal with the same seq"
293        );
294        assert_eq!(Some(Less), pcmp(&norm(2, 2u64), &ts(3)));
295
296        // tombstone vs normal
297
298        assert_eq!(Some(Less), pcmp(&ts(1), &norm(2, 2u64)));
299        assert_eq!(
300            Some(Greater),
301            pcmp(&ts(2), &norm(2, 2u64)),
302            "tombstone is greater than a normal with the same seq"
303        );
304        assert_eq!(Some(Greater), pcmp(&ts(3), &norm(2, 2u64)));
305
306        // tombstone vs tombstone
307
308        assert_eq!(Some(Greater), pcmp(&ts::<()>(2), &ts(1)));
309        assert_eq!(Some(Equal), pcmp(&ts::<()>(2), &ts(2)));
310        assert_eq!(Some(Less), pcmp(&ts::<()>(2), &ts(3)));
311        Ok(())
312    }
313
314    #[test]
315    fn test_ord_operator() -> anyhow::Result<()> {
316        // normal vs normal, with the same data
317
318        assert!(norm(2, 2u64) > norm(1, 2u64));
319        assert!(norm(2, 2u64) >= norm(1, 2u64));
320        assert!(norm(2, 2u64) == norm(2, 2u64));
321        assert!(norm(2, 2u64) <= norm(3, 2u64));
322        assert!(norm(2, 2u64) < norm(3, 2u64));
323
324        // normal vs normal, same seq, different value
325
326        assert!(norm(2, 2u64) > norm(2, 1u64));
327        assert!(norm(2, 2u64) >= norm(2, 1u64));
328        assert!(norm(2, 2u64) == norm(2, 2u64));
329        assert!(norm(2, 2u64) <= norm(2, 3u64));
330        assert!(norm(2, 2u64) < norm(2, 3u64));
331
332        // normal vs tombstone
333
334        assert!(norm(2, 2u64) > ts(1));
335        assert!(norm(2, 2u64) >= ts(1));
336        assert!(
337            norm(2, 2u64) < ts(2),
338            "tombstone is greater than a normal with the same seq"
339        );
340        assert!(
341            norm(2, 2u64) <= ts(2),
342            "tombstone is greater than a normal with the same seq"
343        );
344        assert!(norm(2, 2u64) < ts(3));
345        assert!(norm(2, 2u64) <= ts(3));
346
347        // tombstone vs normal
348
349        assert!(ts(1) < norm(2, 2u64));
350        assert!(ts(1) <= norm(2, 2u64));
351        assert!(
352            ts(2) > norm(2, 2u64),
353            "tombstone is greater than a normal with the same seq"
354        );
355        assert!(
356            ts(2) >= norm(2, 2u64),
357            "tombstone is greater than a normal with the same seq"
358        );
359        assert!(ts(3) > norm(2, 2u64));
360        assert!(ts(3) >= norm(2, 2u64));
361
362        // tombstone vs tombstone
363
364        assert!(ts::<()>(2) > ts(1));
365        assert!(ts::<()>(2) >= ts(1));
366        assert!(ts::<()>(2) >= ts(2));
367        assert!(ts::<()>(2) == ts(2));
368        assert!(ts::<()>(2) <= ts(2));
369        assert!(ts::<()>(2) <= ts(3));
370        assert!(ts::<()>(2) < ts(3));
371
372        Ok(())
373    }
374
375    #[test]
376    fn test_new_absent() {
377        let absent = SeqMarked::<u64>::new_not_found();
378        assert_eq!(absent.seq, 0);
379        assert!(absent.is_tombstone());
380    }
381
382    #[test]
383    fn test_max() {
384        assert_eq!(
385            SeqMarked::<u64>::new_normal(2, 1),
386            SeqMarked::<u64>::max(
387                SeqMarked::<u64>::new_normal(1, 1),
388                SeqMarked::<u64>::new_normal(2, 1)
389            )
390        );
391        assert_eq!(
392            SeqMarked::<u64>::new_normal(2, 1),
393            SeqMarked::<u64>::max(
394                SeqMarked::<u64>::new_normal(1, 2),
395                SeqMarked::<u64>::new_normal(2, 1)
396            )
397        );
398        assert_eq!(
399            SeqMarked::<u64>::new_tombstone(2),
400            SeqMarked::<u64>::max(
401                SeqMarked::<u64>::new_normal(2, 1),
402                SeqMarked::<u64>::new_tombstone(2)
403            )
404        );
405        assert_eq!(
406            SeqMarked::<u64>::new_tombstone(2),
407            SeqMarked::<u64>::max(
408                SeqMarked::<u64>::new_tombstone(1),
409                SeqMarked::<u64>::new_tombstone(2)
410            )
411        );
412    }
413
414    #[test]
415    fn test_max_ref() {
416        let m1 = SeqMarked::new_normal(1, 2);
417        let m2 = SeqMarked::new_normal(3, 2);
418        let m3 = SeqMarked::new_tombstone(2);
419
420        assert_eq!(SeqMarked::max_ref(&m1, &m2), &m2);
421        assert_eq!(SeqMarked::max_ref(&m1, &m3), &m3);
422        assert_eq!(SeqMarked::max_ref(&m2, &m3), &m2);
423
424        assert_eq!(SeqMarked::max_ref(&m1, &m1), &m1);
425        assert_eq!(SeqMarked::max_ref(&m2, &m2), &m2);
426        assert_eq!(SeqMarked::max_ref(&m3, &m3), &m3);
427    }
428
429    #[test]
430    fn test_is_not_found() {
431        assert!(SeqMarked::<u64>::new_not_found().is_not_found());
432        assert!(SeqMarked::<u64>::new_tombstone(0).is_not_found());
433        assert!(!SeqMarked::<u64>::new_tombstone(1).is_not_found());
434        assert!(!SeqMarked::<u64>::new_normal(1, 1).is_not_found());
435    }
436
437    #[test]
438    fn test_into_parts() {
439        let seq_marked = SeqMarked::new_normal(5, "data");
440        let (seq, marked) = seq_marked.into_parts();
441        assert_eq!(seq, 5);
442        assert_eq!(marked, Marked::Normal("data"));
443    }
444
445    #[test]
446    fn test_internal_seq() {
447        let seq_marked = SeqMarked::new_normal(5, "data");
448        assert_eq!(seq_marked.internal_seq(), 5);
449
450        let seq_marked_tombstone = SeqMarked::<u64>::new_tombstone(10);
451        assert_eq!(seq_marked_tombstone.internal_seq(), 10);
452    }
453
454    #[test]
455    fn test_user_seq() {
456        let seq_marked = SeqMarked::new_normal(5, "data");
457        assert_eq!(seq_marked.user_seq(), 5);
458
459        let seq_marked_tombstone = SeqMarked::<u64>::new_tombstone(10);
460        assert_eq!(seq_marked_tombstone.user_seq(), 0);
461    }
462
463    #[test]
464    fn test_display_with_debug() {
465        let seq_marked = SeqMarked::new_normal(5, "data");
466        assert_eq!(
467            format!("{}", seq_marked.display_with_debug()),
468            "{seq: 5, (\"data\")}"
469        );
470    }
471
472    #[test]
473    fn test_display_with_debug_tombstone() {
474        let seq_marked = SeqMarked::<u64>::new_tombstone(5);
475        assert_eq!(
476            format!("{}", seq_marked.display_with_debug()),
477            "{seq: 5, TOMBSTONE}"
478        );
479    }
480}
481
482#[cfg(test)]
483#[cfg(feature = "seq-marked-bincode")]
484mod tests_bincode {
485
486    use super::*;
487    use crate::testing::bincode_config;
488    use crate::testing::test_bincode_decode;
489
490    #[test]
491    fn test_marked_bincode() {
492        let a = SeqMarked::new_normal(5, 1u64);
493        let encoded = bincode::encode_to_vec(&a, bincode_config()).unwrap();
494        let (decoded, n): (SeqMarked<u64>, usize) =
495            bincode::decode_from_slice(&encoded, bincode_config()).unwrap();
496        assert_eq!(n, 3);
497        assert_eq!(a, decoded);
498    }
499
500    #[test]
501    fn test_marked_bincode_decode_v010() -> anyhow::Result<()> {
502        let value = SeqMarked::new_normal(5, 1u64);
503        let encoded = vec![5, 0, 1];
504
505        test_bincode_decode(&encoded, &value)?;
506
507        let value = SeqMarked::<u64>::new_tombstone(6);
508        let encoded = vec![6, 1];
509
510        test_bincode_decode(&encoded, &value)?;
511        Ok(())
512    }
513}
514
515#[cfg(test)]
516#[cfg(feature = "seq-marked-serde")]
517mod tests_serde {
518    use super::*;
519    use crate::testing::test_serde_decode;
520
521    #[test]
522    fn test_marked_serde() {
523        let a = SeqMarked::new_normal(5, 1u64);
524        let encoded = serde_json::to_string(&a).unwrap();
525        let decoded: SeqMarked<u64> = serde_json::from_str(&encoded).unwrap();
526        assert_eq!(a, decoded);
527    }
528
529    #[test]
530    fn test_marked_serde_decode_v010() -> anyhow::Result<()> {
531        let value = SeqMarked::new_normal(5, 1u64);
532        let encoded = r#"{"seq":5,"marked":{"Normal":1}}"#;
533
534        test_serde_decode(encoded, &value)?;
535
536        let value = SeqMarked::<u64>::new_tombstone(6);
537        let encoded = r#"{"seq":6,"marked":"TombStone"}"#;
538
539        test_serde_decode(encoded, &value)?;
540        Ok(())
541    }
542}
seq_marked/seq_marked/mod.rs

seq_marked/seq_marked/
mod.rs
