risingwave_hummock_sdk/
key_cmp.rs

1// Copyright 2025 RisingWave Labs
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::cmp::{self, Ordering};
16
17use super::key::split_key_epoch;
18use crate::key::UserKey;
19
20/// A comparator for comparing [`crate::key::FullKey`] and [`crate::key::UserKey`] with possibly
21/// different table key types.
22pub struct KeyComparator;
23
24impl KeyComparator {
25    /// Suppose parameter as `full_key` = (`user_key`, `epoch`), this function compares
26    /// `&[u8]` as if comparing the above tuple.
27    #[inline]
28    pub fn compare_encoded_full_key(lhs: &[u8], rhs: &[u8]) -> cmp::Ordering {
29        let (l_p, l_s) = split_key_epoch(lhs);
30        let (r_p, r_s) = split_key_epoch(rhs);
31        l_p.cmp(r_p).then_with(|| r_s.cmp(l_s))
32    }
33
34    #[inline]
35    pub fn encoded_full_key_less_than(lhs: &[u8], rhs: &[u8]) -> bool {
36        Self::compare_encoded_full_key(lhs, rhs) == cmp::Ordering::Less
37    }
38
39    /// Used to compare [`UserKey`] and its encoded format.
40    pub fn compare_user_key_cross_format(
41        encoded: impl AsRef<[u8]>,
42        unencoded: &UserKey<impl AsRef<[u8]>>,
43    ) -> Ordering {
44        UserKey::decode(encoded.as_ref()).cmp(&unencoded.as_ref())
45    }
46
47    #[inline(always)]
48    /// Used to compare [`UserKey`] and its encoded format.
49    pub fn encoded_less_than_unencoded(
50        encoded: impl AsRef<[u8]>,
51        unencoded: &UserKey<impl AsRef<[u8]>>,
52    ) -> bool {
53        Self::compare_user_key_cross_format(encoded, unencoded) == Ordering::Less
54    }
55
56    #[inline(always)]
57    /// Used to compare [`UserKey`] and its encoded format.
58    pub fn encoded_less_equal_unencoded(
59        encoded: impl AsRef<[u8]>,
60        unencoded: &UserKey<impl AsRef<[u8]>>,
61    ) -> bool {
62        Self::compare_user_key_cross_format(encoded, unencoded) != Ordering::Greater
63    }
64
65    #[inline(always)]
66    /// Used to compare [`UserKey`] and its encoded format.
67    pub fn encoded_greater_than_unencoded(
68        encoded: impl AsRef<[u8]>,
69        unencoded: &UserKey<impl AsRef<[u8]>>,
70    ) -> bool {
71        Self::compare_user_key_cross_format(encoded, unencoded) == Ordering::Greater
72    }
73}
74
75#[cfg(test)]
76mod tests {
77    use std::cmp::Ordering;
78
79    use risingwave_common::catalog::TableId;
80    use risingwave_common::util::epoch::test_epoch;
81
82    use crate::KeyComparator;
83    use crate::key::{FullKey, UserKey};
84
85    #[test]
86    fn test_cmp_encoded_full_key() {
87        // 1 compared with 256 under little-endian encoding would return wrong result.
88
89        let epoch = test_epoch(1);
90        let epoch2 = test_epoch(2);
91        let key1 = FullKey::for_test(TableId::new(0), b"0".to_vec(), epoch);
92        let key2 = FullKey::for_test(TableId::new(1), b"0".to_vec(), epoch);
93        let key3 = FullKey::for_test(TableId::new(1), b"1".to_vec(), epoch2);
94        let key4 = FullKey::for_test(TableId::new(1), b"1".to_vec(), epoch);
95
96        assert_eq!(
97            KeyComparator::compare_encoded_full_key(&key1.encode(), &key1.encode()),
98            Ordering::Equal
99        );
100        assert_eq!(
101            KeyComparator::compare_encoded_full_key(&key1.encode(), &key2.encode()),
102            Ordering::Less
103        );
104        assert_eq!(
105            KeyComparator::compare_encoded_full_key(&key2.encode(), &key3.encode()),
106            Ordering::Less
107        );
108        assert_eq!(
109            KeyComparator::compare_encoded_full_key(&key3.encode(), &key4.encode()),
110            Ordering::Less
111        );
112    }
113
114    #[test]
115    fn test_cmp_user_key_cross_format() {
116        let key1 = UserKey::for_test(TableId::new(0), b"0".to_vec());
117        let key2 = UserKey::for_test(TableId::new(0), b"1".to_vec());
118        let key3 = UserKey::for_test(TableId::new(1), b"0".to_vec());
119
120        assert_eq!(
121            KeyComparator::compare_user_key_cross_format(key1.encode(), &key1),
122            Ordering::Equal
123        );
124        assert_eq!(
125            KeyComparator::compare_user_key_cross_format(key1.encode(), &key2),
126            Ordering::Less
127        );
128        assert_eq!(
129            KeyComparator::compare_user_key_cross_format(key2.encode(), &key3),
130            Ordering::Less
131        );
132    }
133}
risingwave_hummock_sdk/key_cmp.rs

risingwave_hummock_sdk/
key_cmp.rs
