sui_inverted_index/
event_seq.rs

1// Copyright (c) Mysten Labs, Inc.
2// SPDX-License-Identifier: Apache-2.0
3
4//! Packed event-sequence encoding used by bitmap index storage.
5//!
6//! The public cursor/query layers use `(tx_seq, event_index)`. Bitmap storage
7//! packs that coordinate into `event_seq = (tx_seq << EVENT_BITS) | event_idx`.
8
9use std::ops::{Bound, Range};
10
11/// Number of low bits of `event_seq` reserved for the per-tx event index.
12pub const EVENT_BITS: u32 = 16;
13
14/// Maximum number of events per tx representable in a packed event_seq.
15pub const MAX_EVENTS_PER_TX: u32 = 1 << EVENT_BITS;
16
17/// Maximum tx_seq representable in a packed event_seq.
18pub const MAX_TX_SEQ: u64 = u64::MAX >> EVENT_BITS;
19/// Pack `(tx_seq, event_idx)` into a globally ordered event_seq.
20#[inline]
21pub fn encode_event_seq(tx_seq: u64, event_idx: u32) -> u64 {
22    debug_assert!(event_idx < MAX_EVENTS_PER_TX);
23    debug_assert!(
24        tx_seq <= MAX_TX_SEQ,
25        "tx_seq {} exceeds {} bits and would lose data when shifted by EVENT_BITS={}",
26        tx_seq,
27        64 - EVENT_BITS,
28        EVENT_BITS,
29    );
30    (tx_seq << EVENT_BITS) | (event_idx as u64)
31}
32
33/// Unpack a packed event_seq back into `(tx_seq, event_idx)`.
34#[inline]
35pub fn decode_event_seq(event_seq: u64) -> (u64, u32) {
36    let tx_seq = event_seq >> EVENT_BITS;
37    let event_idx = (event_seq & (MAX_EVENTS_PER_TX as u64 - 1)) as u32;
38    (tx_seq, event_idx)
39}
40
41/// Lowest possible event_seq for a given tx_seq (idx 0).
42#[inline]
43pub fn event_seq_lo(tx_seq: u64) -> u64 {
44    tx_seq << EVENT_BITS
45}
46
47/// Convert semantic event-coordinate bounds into the packed half-open range
48/// scanned by bitmap indexes. Accepts any coordinate type that projects to
49/// `(tx_seq, event_idx)`, so callers can pass their own position type without
50/// this crate knowing about it.
51pub fn packed_range<T: Into<(u64, u32)>>(lo: Bound<T>, hi: Bound<T>) -> Range<u64> {
52    let start = match lo.map(Into::into) {
53        Bound::Included((tx_seq, event_idx)) => saturating_lo(tx_seq, event_idx),
54        Bound::Excluded((tx_seq, event_idx)) => saturating_successor(tx_seq, event_idx),
55        Bound::Unbounded => 0,
56    };
57
58    let end = match hi.map(Into::into) {
59        Bound::Included((tx_seq, event_idx)) => saturating_successor(tx_seq, event_idx),
60        Bound::Excluded((tx_seq, event_idx)) => saturating_lo(tx_seq, event_idx),
61        Bound::Unbounded => u64::MAX,
62    };
63
64    start..end
65}
66
67#[inline]
68fn saturating_lo(tx_seq: u64, event_idx: u32) -> u64 {
69    if tx_seq > MAX_TX_SEQ {
70        return u64::MAX;
71    }
72
73    if event_idx >= MAX_EVENTS_PER_TX {
74        return tx_seq
75            .checked_add(1)
76            .filter(|next_tx| *next_tx <= MAX_TX_SEQ)
77            .map(event_seq_lo)
78            .unwrap_or(u64::MAX);
79    }
80
81    encode_event_seq(tx_seq, event_idx)
82}
83
84#[inline]
85fn saturating_successor(tx_seq: u64, event_idx: u32) -> u64 {
86    if event_idx.saturating_add(1) < MAX_EVENTS_PER_TX {
87        saturating_lo(tx_seq, event_idx + 1)
88    } else {
89        saturating_lo(tx_seq.saturating_add(1), 0)
90    }
91}
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96
97    #[test]
98    fn test_encode_decode_event_seq_roundtrip() {
99        for (tx_seq, event_idx) in [
100            (0, 0),
101            (0, 1023),
102            (1, 0),
103            (1_000_000, 42),
104            (u64::MAX >> EVENT_BITS, MAX_EVENTS_PER_TX - 1),
105        ] {
106            let packed = encode_event_seq(tx_seq, event_idx);
107            assert_eq!(decode_event_seq(packed), (tx_seq, event_idx));
108        }
109    }
110
111    #[test]
112    fn test_event_seq_ordering() {
113        let a = encode_event_seq(100, 0);
114        let b = encode_event_seq(100, 5);
115        assert!(a < b);
116
117        let c = encode_event_seq(101, 0);
118        assert!(b < c);
119    }
120
121    #[test]
122    fn test_packed_range_whole_tx_span() {
123        assert_eq!(
124            packed_range(Bound::Included((10, 0)), Bound::Excluded((13, 0))),
125            event_seq_lo(10)..event_seq_lo(13),
126        );
127    }
128
129    #[test]
130    fn test_packed_range_excluded_start_advances() {
131        assert_eq!(
132            packed_range(Bound::Excluded((10, 1)), Bound::Excluded((11, 0))).start,
133            encode_event_seq(10, 2),
134        );
135    }
136
137    #[test]
138    fn test_packed_range_forged_extremes_saturate() {
139        let oversized_event = packed_range(
140            Bound::Included((10, u32::MAX)),
141            Bound::Excluded((10, u32::MAX)),
142        );
143        assert!(oversized_event.is_empty());
144        assert_eq!(oversized_event.start, event_seq_lo(11));
145
146        let oversized_tx = packed_range(
147            Bound::Included((u64::MAX, 0)),
148            Bound::Excluded((u64::MAX, 0)),
149        );
150        assert!(oversized_tx.is_empty());
151        assert_eq!(oversized_tx.start, u64::MAX);
152        assert_eq!(oversized_tx.end, u64::MAX);
153    }
154}
sui_inverted_index/event_seq.rs

sui_inverted_index/
event_seq.rs
