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.
144    pub fn seq(&self) -> u64 {
145        self.seq
146    }
147
148    /// Returns the maximum of two values.
149    pub fn max(a: Self, b: Self) -> Self {
150        if a.order_key() > b.order_key() { a } else { b }
151    }
152
153    /// Returns the maximum of two values.
154    pub fn max_ref<'l>(a: &'l Self, b: &'l Self) -> &'l Self {
155        if a.order_key() > b.order_key() { a } else { b }
156    }
157
158    /// Returns reference to data if normal, `None` if tombstone.
159    pub fn data_ref(&self) -> Option<&D> {
160        match self.marked {
161            Marked::Normal(ref d) => Some(d),
162            Marked::TombStone => None,
163        }
164    }
165
166    /// Consumes and returns data if normal, `None` if tombstone.
167    pub fn into_data(self) -> Option<D> {
168        match self.marked {
169            Marked::Normal(data) => Some(data),
170            Marked::TombStone => None,
171        }
172    }
173
174    pub fn into_parts(self) -> (u64, Marked<D>) {
175        (self.seq, self.marked)
176    }
177
178    /// Returns formatter for display using `Debug` trait.
179    pub fn display_with_debug(&self) -> impl fmt::Display + '_
180    where D: fmt::Debug {
181        struct DisplaySeqMarked<'a, D>(&'a SeqMarked<D>);
182
183        impl<D> fmt::Display for DisplaySeqMarked<'_, D>
184        where D: fmt::Debug
185        {
186            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
187                write!(f, "{{seq: {}, ", self.0.seq)?;
188                match &self.0.marked {
189                    Marked::Normal(data) => write!(f, "({:?})", data)?,
190                    Marked::TombStone => write!(f, "TOMBSTONE")?,
191                }
192                write!(f, "}}")
193            }
194        }
195
196        DisplaySeqMarked(self)
197    }
198}
199
200#[cfg(test)]
201mod tests {
202    use std::cmp::Ordering;
203
204    use Ordering::Equal;
205    use Ordering::Greater;
206    use Ordering::Less;
207
208    use super::*;
209    use crate::testing::norm;
210    use crate::testing::ts;
211
212    #[test]
213    fn test_seq_marked_is_copy() {
214        let seq_marked = SeqMarked::new(5, Marked::Normal("data"));
215        let seq_marked_copy = seq_marked;
216        assert_eq!(seq_marked, seq_marked_copy);
217    }
218
219    #[test]
220    fn test_new() {
221        let seq_marked = SeqMarked::new(5, Marked::Normal("data"));
222        assert_eq!(seq_marked.seq, 5);
223        assert_eq!(seq_marked.marked, Marked::Normal("data"));
224    }
225
226    #[test]
227    fn test_map() -> anyhow::Result<()> {
228        let a = norm(1, 1u64);
229        assert_eq!(norm(1, 2u32), a.map(|x| (x * 2) as u32));
230
231        let a = ts::<u64>(1);
232        assert_eq!(ts::<u32>(1), a.map(|x| (x * 2) as u32));
233
234        Ok(())
235    }
236
237    #[test]
238    fn test_as_ref() -> anyhow::Result<()> {
239        let a = norm(1, 1u64);
240        assert_eq!(norm(1, &1u64), a.as_ref());
241
242        let a = ts::<u64>(1);
243        assert_eq!(ts::<&u64>(1), a.as_ref());
244
245        Ok(())
246    }
247
248    #[test]
249    fn test_order_key() -> anyhow::Result<()> {
250        assert!(norm(1, 1u64).order_key() == norm(1, 1u64).order_key());
251        assert!(norm(1, 2u64).order_key() == norm(1, 1u64).order_key());
252        assert!(norm(2, 2u64).order_key() > norm(1, 1u64).order_key());
253
254        assert!(ts::<u64>(1).order_key() > norm(1, 1u64).order_key());
255        assert!(ts::<u64>(2).order_key() > norm(1, 1u64).order_key());
256
257        assert!(ts::<u64>(2).order_key() > ts::<u64>(1).order_key());
258        assert!(ts::<u64>(1).order_key() == ts::<u64>(1).order_key());
259
260        Ok(())
261    }
262
263    #[test]
264    fn test_partial_ord() -> anyhow::Result<()> {
265        fn pcmp<D: PartialOrd>(a: &SeqMarked<D>, b: &SeqMarked<D>) -> Option<Ordering> {
266            PartialOrd::partial_cmp(a, b)
267        }
268
269        // normal vs normal, with the same data
270
271        assert_eq!(Some(Greater), pcmp(&norm(2, 2u64), &norm(1, 2u64)));
272        assert_eq!(Some(Equal), pcmp(&norm(2, 2u64), &norm(2, 2u64)));
273        assert_eq!(Some(Less), pcmp(&norm(2, 2u64), &norm(3, 2u64)));
274
275        // normal vs normal, same seq, different value
276
277        assert_eq!(Some(Greater), pcmp(&norm(2, 2u64), &norm(2, 1u64)));
278        assert_eq!(Some(Equal), pcmp(&norm(2, 2u64), &norm(2, 2u64)));
279        assert_eq!(Some(Less), pcmp(&norm(2, 2u64), &norm(2, 3u64)));
280
281        // normal vs tombstone
282
283        assert_eq!(Some(Greater), pcmp(&norm(2, 2u64), &ts(1)));
284        assert_eq!(
285            Some(Less),
286            pcmp(&norm(2, 2u64), &ts(2)),
287            "tombstone is greater than a normal with the same seq"
288        );
289        assert_eq!(Some(Less), pcmp(&norm(2, 2u64), &ts(3)));
290
291        // tombstone vs normal
292
293        assert_eq!(Some(Less), pcmp(&ts(1), &norm(2, 2u64)));
294        assert_eq!(
295            Some(Greater),
296            pcmp(&ts(2), &norm(2, 2u64)),
297            "tombstone is greater than a normal with the same seq"
298        );
299        assert_eq!(Some(Greater), pcmp(&ts(3), &norm(2, 2u64)));
300
301        // tombstone vs tombstone
302
303        assert_eq!(Some(Greater), pcmp(&ts::<()>(2), &ts(1)));
304        assert_eq!(Some(Equal), pcmp(&ts::<()>(2), &ts(2)));
305        assert_eq!(Some(Less), pcmp(&ts::<()>(2), &ts(3)));
306        Ok(())
307    }
308
309    #[test]
310    fn test_ord_operator() -> anyhow::Result<()> {
311        // normal vs normal, with the same data
312
313        assert!(norm(2, 2u64) > norm(1, 2u64));
314        assert!(norm(2, 2u64) >= norm(1, 2u64));
315        assert!(norm(2, 2u64) == norm(2, 2u64));
316        assert!(norm(2, 2u64) <= norm(3, 2u64));
317        assert!(norm(2, 2u64) < norm(3, 2u64));
318
319        // normal vs normal, same seq, different value
320
321        assert!(norm(2, 2u64) > norm(2, 1u64));
322        assert!(norm(2, 2u64) >= norm(2, 1u64));
323        assert!(norm(2, 2u64) == norm(2, 2u64));
324        assert!(norm(2, 2u64) <= norm(2, 3u64));
325        assert!(norm(2, 2u64) < norm(2, 3u64));
326
327        // normal vs tombstone
328
329        assert!(norm(2, 2u64) > ts(1));
330        assert!(norm(2, 2u64) >= ts(1));
331        assert!(
332            norm(2, 2u64) < ts(2),
333            "tombstone is greater than a normal with the same seq"
334        );
335        assert!(
336            norm(2, 2u64) <= ts(2),
337            "tombstone is greater than a normal with the same seq"
338        );
339        assert!(norm(2, 2u64) < ts(3));
340        assert!(norm(2, 2u64) <= ts(3));
341
342        // tombstone vs normal
343
344        assert!(ts(1) < norm(2, 2u64));
345        assert!(ts(1) <= norm(2, 2u64));
346        assert!(
347            ts(2) > norm(2, 2u64),
348            "tombstone is greater than a normal with the same seq"
349        );
350        assert!(
351            ts(2) >= norm(2, 2u64),
352            "tombstone is greater than a normal with the same seq"
353        );
354        assert!(ts(3) > norm(2, 2u64));
355        assert!(ts(3) >= norm(2, 2u64));
356
357        // tombstone vs tombstone
358
359        assert!(ts::<()>(2) > ts(1));
360        assert!(ts::<()>(2) >= ts(1));
361        assert!(ts::<()>(2) >= ts(2));
362        assert!(ts::<()>(2) == ts(2));
363        assert!(ts::<()>(2) <= ts(2));
364        assert!(ts::<()>(2) <= ts(3));
365        assert!(ts::<()>(2) < ts(3));
366
367        Ok(())
368    }
369
370    #[test]
371    fn test_new_absent() {
372        let absent = SeqMarked::<u64>::new_not_found();
373        assert_eq!(absent.seq, 0);
374        assert!(absent.is_tombstone());
375    }
376
377    #[test]
378    fn test_max() {
379        assert_eq!(
380            SeqMarked::<u64>::new_normal(2, 1),
381            SeqMarked::<u64>::max(
382                SeqMarked::<u64>::new_normal(1, 1),
383                SeqMarked::<u64>::new_normal(2, 1)
384            )
385        );
386        assert_eq!(
387            SeqMarked::<u64>::new_normal(2, 1),
388            SeqMarked::<u64>::max(
389                SeqMarked::<u64>::new_normal(1, 2),
390                SeqMarked::<u64>::new_normal(2, 1)
391            )
392        );
393        assert_eq!(
394            SeqMarked::<u64>::new_tombstone(2),
395            SeqMarked::<u64>::max(
396                SeqMarked::<u64>::new_normal(2, 1),
397                SeqMarked::<u64>::new_tombstone(2)
398            )
399        );
400        assert_eq!(
401            SeqMarked::<u64>::new_tombstone(2),
402            SeqMarked::<u64>::max(
403                SeqMarked::<u64>::new_tombstone(1),
404                SeqMarked::<u64>::new_tombstone(2)
405            )
406        );
407    }
408
409    #[test]
410    fn test_max_ref() {
411        let m1 = SeqMarked::new_normal(1, 2);
412        let m2 = SeqMarked::new_normal(3, 2);
413        let m3 = SeqMarked::new_tombstone(2);
414
415        assert_eq!(SeqMarked::max_ref(&m1, &m2), &m2);
416        assert_eq!(SeqMarked::max_ref(&m1, &m3), &m3);
417        assert_eq!(SeqMarked::max_ref(&m2, &m3), &m2);
418
419        assert_eq!(SeqMarked::max_ref(&m1, &m1), &m1);
420        assert_eq!(SeqMarked::max_ref(&m2, &m2), &m2);
421        assert_eq!(SeqMarked::max_ref(&m3, &m3), &m3);
422    }
423
424    #[test]
425    fn test_is_not_found() {
426        assert!(SeqMarked::<u64>::new_not_found().is_not_found());
427        assert!(SeqMarked::<u64>::new_tombstone(0).is_not_found());
428        assert!(!SeqMarked::<u64>::new_tombstone(1).is_not_found());
429        assert!(!SeqMarked::<u64>::new_normal(1, 1).is_not_found());
430    }
431
432    #[test]
433    fn test_into_parts() {
434        let seq_marked = SeqMarked::new_normal(5, "data");
435        let (seq, marked) = seq_marked.into_parts();
436        assert_eq!(seq, 5);
437        assert_eq!(marked, Marked::Normal("data"));
438    }
439
440    #[test]
441    fn test_display_with_debug() {
442        let seq_marked = SeqMarked::new_normal(5, "data");
443        assert_eq!(
444            format!("{}", seq_marked.display_with_debug()),
445            "{seq: 5, (\"data\")}"
446        );
447    }
448
449    #[test]
450    fn test_display_with_debug_tombstone() {
451        let seq_marked = SeqMarked::<u64>::new_tombstone(5);
452        assert_eq!(
453            format!("{}", seq_marked.display_with_debug()),
454            "{seq: 5, TOMBSTONE}"
455        );
456    }
457}
458
459#[cfg(test)]
460#[cfg(feature = "seq-marked-bincode")]
461mod tests_bincode {
462
463    use super::*;
464    use crate::testing::bincode_config;
465    use crate::testing::test_bincode_decode;
466
467    #[test]
468    fn test_marked_bincode() {
469        let a = SeqMarked::new_normal(5, 1u64);
470        let encoded = bincode::encode_to_vec(&a, bincode_config()).unwrap();
471        let (decoded, n): (SeqMarked<u64>, usize) =
472            bincode::decode_from_slice(&encoded, bincode_config()).unwrap();
473        assert_eq!(n, 3);
474        assert_eq!(a, decoded);
475    }
476
477    #[test]
478    fn test_marked_bincode_decode_v010() -> anyhow::Result<()> {
479        let value = SeqMarked::new_normal(5, 1u64);
480        let encoded = vec![5, 0, 1];
481
482        test_bincode_decode(&encoded, &value)?;
483
484        let value = SeqMarked::<u64>::new_tombstone(6);
485        let encoded = vec![6, 1];
486
487        test_bincode_decode(&encoded, &value)?;
488        Ok(())
489    }
490}
491
492#[cfg(test)]
493#[cfg(feature = "seq-marked-serde")]
494mod tests_serde {
495    use super::*;
496    use crate::testing::test_serde_decode;
497
498    #[test]
499    fn test_marked_serde() {
500        let a = SeqMarked::new_normal(5, 1u64);
501        let encoded = serde_json::to_string(&a).unwrap();
502        let decoded: SeqMarked<u64> = serde_json::from_str(&encoded).unwrap();
503        assert_eq!(a, decoded);
504    }
505
506    #[test]
507    fn test_marked_serde_decode_v010() -> anyhow::Result<()> {
508        let value = SeqMarked::new_normal(5, 1u64);
509        let encoded = r#"{"seq":5,"marked":{"Normal":1}}"#;
510
511        test_serde_decode(encoded, &value)?;
512
513        let value = SeqMarked::<u64>::new_tombstone(6);
514        let encoded = r#"{"seq":6,"marked":"TombStone"}"#;
515
516        test_serde_decode(encoded, &value)?;
517        Ok(())
518    }
519}
seq_marked/seq_marked/mod.rs

seq_marked/seq_marked/
mod.rs
