sel4_shared_ring_buffer_bookkeeping/
slot_tracker.rs

Help
1//
2// Copyright 2023, Colias Group, LLC
3//
4// SPDX-License-Identifier: BSD-2-Clause
5//
6
7extern crate alloc;
8
9use alloc::vec::Vec;
10use core::iter;
11use core::mem;
12
13type Result<T> = core::result::Result<T, SlotTrackerError>;
14
15pub trait SlotStateTypes {
16    type Common;
17    type Free;
18    type Occupied;
19}
20
21pub struct SlotTracker<T: SlotStateTypes> {
22    entries: Vec<Entry<T>>,
23    free_list_head_index: Option<usize>,
24    num_free: usize,
25}
26
27struct Entry<T: SlotStateTypes> {
28    common: T::Common,
29    state: StateInternal<T>,
30}
31
32enum StateInternal<T: SlotStateTypes> {
33    Free {
34        free_list_next_index: Option<usize>,
35        value: T::Free,
36    },
37    Occupied {
38        value: T::Occupied,
39    },
40}
41
42impl<T: SlotStateTypes> StateInternal<T> {
43    fn project(&self) -> SlotState {
44        match self {
45            Self::Free { .. } => SlotState::Free,
46            Self::Occupied { .. } => SlotState::Occupied,
47        }
48    }
49}
50
51impl<T: SlotStateTypes> SlotTracker<T> {
52    pub fn new(iter: impl Iterator<Item = (T::Common, T::Free)>) -> Self {
53        let mut entries = Vec::new();
54        let mut free_list_head_index = None;
55        entries.extend(iter.enumerate().map(|(i, (v_common, v_free))| Entry {
56            common: v_common,
57            state: StateInternal::Free {
58                free_list_next_index: free_list_head_index.replace(i),
59                value: v_free,
60            },
61        }));
62        let num_free = entries.len();
63        Self {
64            entries,
65            free_list_head_index,
66            num_free,
67        }
68    }
69
70    pub fn new_with_capacity(common: T::Common, free: T::Free, capacity: usize) -> Self
71    where
72        T: SlotStateTypes<Common: Clone, Free: Clone>,
73    {
74        Self::new(iter::repeat_n((common, free), capacity))
75    }
76
77    pub fn new_occupied(iter: impl Iterator<Item = (T::Common, T::Occupied)>) -> Self {
78        let entries = iter
79            .map(|(v_common, v_occupied)| Entry {
80                common: v_common,
81                state: StateInternal::Occupied { value: v_occupied },
82            })
83            .collect();
84        Self {
85            entries,
86            free_list_head_index: None,
87            num_free: 0,
88        }
89    }
90
91    pub fn new_occupied_with_capacity(
92        common: T::Common,
93        occupied: T::Occupied,
94        capacity: usize,
95    ) -> Self
96    where
97        T: SlotStateTypes<Common: Clone, Occupied: Clone>,
98    {
99        Self::new_occupied(iter::repeat_n((common, occupied), capacity))
100    }
101
102    pub fn capacity(&self) -> usize {
103        self.entries.capacity()
104    }
105
106    pub fn num_free(&self) -> usize {
107        self.num_free
108    }
109
110    pub fn num_occupied(&self) -> usize {
111        self.capacity() - self.num_free()
112    }
113
114    pub fn peek_next_free_index(&self) -> Option<usize> {
115        self.free_list_head_index
116    }
117
118    pub fn peek_next_free_value(&self) -> Option<&T::Free> {
119        let index = self.peek_next_free_index()?;
120        Some(self.get_state_value(index).unwrap().as_free().unwrap())
121    }
122
123    fn get_entry(&self, index: usize) -> Result<&Entry<T>> {
124        self.entries.get(index).ok_or(SlotTrackerError::OutOfBounds)
125    }
126
127    fn get_entry_mut(&mut self, index: usize) -> Result<&mut Entry<T>> {
128        self.entries
129            .get_mut(index)
130            .ok_or(SlotTrackerError::OutOfBounds)
131    }
132
133    pub fn get_common_value(&self, index: usize) -> Result<&T::Common> {
134        Ok(&self.get_entry(index)?.common)
135    }
136
137    pub fn get_common_value_mut(&mut self, index: usize) -> Result<&mut T::Common> {
138        Ok(&mut self.get_entry_mut(index)?.common)
139    }
140
141    pub fn get_state(&self, index: usize) -> Result<SlotState> {
142        Ok(self.get_entry(index)?.state.project())
143    }
144
145    pub fn get_state_value(&self, index: usize) -> Result<SlotStateValueRef<T>> {
146        Ok(match self.get_entry(index)?.state {
147            StateInternal::Free { ref value, .. } => SlotStateValueRef::Free(value),
148            StateInternal::Occupied { ref value, .. } => SlotStateValueRef::Occupied(value),
149        })
150    }
151
152    pub fn get_state_value_mut(&mut self, index: usize) -> Result<SlotStateValueRefMut<T>> {
153        Ok(match self.get_entry_mut(index)?.state {
154            StateInternal::Free { ref mut value, .. } => SlotStateValueRefMut::Free(value),
155            StateInternal::Occupied { ref mut value, .. } => SlotStateValueRefMut::Occupied(value),
156        })
157    }
158
159    pub fn occupy(&mut self, value: T::Occupied) -> Option<(usize, T::Free)> {
160        let index = self.free_list_head_index?;
161        let new_state = StateInternal::Occupied { value };
162        let old_state = self.replace_state(index, new_state);
163        let value = match old_state {
164            StateInternal::Free {
165                free_list_next_index,
166                value,
167            } => {
168                self.free_list_head_index = free_list_next_index;
169                value
170            }
171            _ => {
172                unreachable!()
173            }
174        };
175        self.num_free -= 1;
176        Some((index, value))
177    }
178
179    pub fn free(&mut self, index: usize, value: T::Free) -> Result<T::Occupied> {
180        self.ensure_state(index, SlotState::Occupied)?;
181        let new_state = StateInternal::Free {
182            free_list_next_index: self.free_list_head_index.replace(index),
183            value,
184        };
185        let old_state = self.replace_state(index, new_state);
186        let value = match old_state {
187            StateInternal::Occupied { value } => value,
188            _ => unreachable!(),
189        };
190        self.num_free += 1;
191        Ok(value)
192    }
193
194    fn ensure_state(&self, index: usize, state: SlotState) -> Result<()> {
195        if self.get_state(index)? == state {
196            Ok(())
197        } else {
198            Err(SlotTrackerError::StateMismatch)
199        }
200    }
201
202    fn replace_state(&mut self, index: usize, new_state: StateInternal<T>) -> StateInternal<T> {
203        mem::replace(&mut self.get_entry_mut(index).unwrap().state, new_state)
204    }
205}
206
207#[derive(Debug, Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Hash)]
208pub enum SlotState {
209    Free,
210    Occupied,
211}
212
213impl SlotState {
214    pub fn is_free(&self) -> bool {
215        *self == Self::Free
216    }
217
218    pub fn is_occupied(&self) -> bool {
219        *self == Self::Occupied
220    }
221}
222
223#[derive(Debug, Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Hash)]
224pub enum SlotStateValueRef<'a, T: SlotStateTypes> {
225    Free(&'a T::Free),
226    Occupied(&'a T::Occupied),
227}
228
229impl<'a, T: SlotStateTypes> SlotStateValueRef<'a, T> {
230    pub fn as_free(self) -> Result<&'a T::Free> {
231        match self {
232            Self::Free(r) => Ok(r),
233            _ => Err(SlotTrackerError::StateMismatch),
234        }
235    }
236
237    pub fn as_occupied(self) -> Result<&'a T::Occupied> {
238        match self {
239            Self::Occupied(r) => Ok(r),
240            _ => Err(SlotTrackerError::StateMismatch),
241        }
242    }
243}
244
245#[derive(Debug, PartialOrd, Ord, PartialEq, Eq, Hash)]
246pub enum SlotStateValueRefMut<'a, T: SlotStateTypes> {
247    Free(&'a mut T::Free),
248    Occupied(&'a mut T::Occupied),
249}
250
251impl<'a, T: SlotStateTypes> SlotStateValueRefMut<'a, T> {
252    pub fn as_free(self) -> Result<&'a mut T::Free> {
253        match self {
254            Self::Free(r) => Ok(r),
255            _ => Err(SlotTrackerError::StateMismatch),
256        }
257    }
258
259    pub fn as_occupied(self) -> Result<&'a mut T::Occupied> {
260        match self {
261            Self::Occupied(r) => Ok(r),
262            _ => Err(SlotTrackerError::StateMismatch),
263        }
264    }
265}
266
267#[derive(Debug, Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Hash)]
268pub enum SlotTrackerError {
269    OutOfBounds,
270    StateMismatch,
271}
sel4_shared_ring_buffer_bookkeeping/slot_tracker.rs

sel4_shared_ring_buffer_bookkeeping/
slot_tracker.rs
