risingwave_common/types/
sentinel.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 enum_as_inner::EnumAsInner;
16use risingwave_common_estimate_size::EstimateSize;
17
18/// [`Sentinelled<T>`] wraps type `T` to provide smallest (smaller than any normal `T` value) and largest
19/// (larger than ant normal `T` value) sentinel value for `T`.
20///
21/// Sentinel is a very common technique used to simplify tree/list/array algorithms. The main idea is to
22/// insert sentinel node to the beginning or/and the end, so that algorithms don't need to handle complex
23/// edge cases.
24#[derive(Debug, Clone, PartialEq, Eq, EnumAsInner)]
25pub enum Sentinelled<T> {
26    Smallest,
27    Normal(T),
28    Largest,
29}
30
31impl<T> Sentinelled<T> {
32    pub fn as_normal_expect(&self) -> &T {
33        self.as_normal().expect("expect normal key")
34    }
35
36    pub fn is_sentinel(&self) -> bool {
37        matches!(self, Self::Smallest | Self::Largest)
38    }
39
40    pub fn cmp_by(
41        &self,
42        other: &Self,
43        cmp_fn: impl FnOnce(&T, &T) -> std::cmp::Ordering,
44    ) -> std::cmp::Ordering {
45        use Sentinelled::*;
46        match (self, other) {
47            (Smallest, Smallest) => std::cmp::Ordering::Equal,
48            (Smallest, _) => std::cmp::Ordering::Less,
49            (_, Smallest) => std::cmp::Ordering::Greater,
50            (Largest, Largest) => std::cmp::Ordering::Equal,
51            (Largest, _) => std::cmp::Ordering::Greater,
52            (_, Largest) => std::cmp::Ordering::Less,
53            (Normal(a), Normal(b)) => cmp_fn(a, b),
54        }
55    }
56
57    pub fn map<U>(self, map_fn: impl FnOnce(T) -> U) -> Sentinelled<U> {
58        use Sentinelled::*;
59        match self {
60            Smallest => Smallest,
61            Normal(inner) => Normal(map_fn(inner)),
62            Largest => Largest,
63        }
64    }
65}
66
67impl<T> From<T> for Sentinelled<T> {
68    fn from(inner: T) -> Self {
69        Self::Normal(inner)
70    }
71}
72
73impl<T> PartialOrd for Sentinelled<T>
74where
75    T: Ord,
76{
77    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
78        Some(self.cmp(other))
79    }
80}
81
82impl<T> Ord for Sentinelled<T>
83where
84    T: Ord,
85{
86    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
87        self.cmp_by(other, T::cmp)
88    }
89}
90
91impl<T: EstimateSize> EstimateSize for Sentinelled<T> {
92    fn estimated_heap_size(&self) -> usize {
93        match self {
94            Self::Smallest => 0,
95            Self::Normal(inner) => inner.estimated_heap_size(),
96            Self::Largest => 0,
97        }
98    }
99}
risingwave_common/types/sentinel.rs

risingwave_common/types/
sentinel.rs
