bt_hfp/call/
list.rs

1// Copyright 2021 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5/// The index associated with a call, that is guaranteed to be unique for the lifetime of the call,
6/// but will be recycled after the call is released.
7pub type Idx = usize;
8
9/// A collection designed for the specific requirements of storing Calls with an associated index.
10///
11/// The requirements found in HFP v1.8, Section 4.34.2, "+CLCC":
12///
13///   * Each call is assigned a number starting at 1.
14///   * Calls hold their number until they are released.
15///   * New calls take the lowest available number.
16///
17/// Note: "Insert" is a O(n) operation in order to simplify the implementation.
18/// This data structure is best suited towards small n for this reason.
19pub struct List<T> {
20    inner: Vec<Option<T>>,
21}
22
23impl<T> Default for List<T> {
24    fn default() -> Self {
25        Self { inner: Vec::default() }
26    }
27}
28
29impl<T: std::fmt::Debug> std::fmt::Debug for List<T> {
30    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
31        write!(f, "{:?}", self.inner)
32    }
33}
34
35impl<T> List<T> {
36    /// Insert a new value into the list, returning an index that is guaranteed to be unique until
37    /// the value is removed from the list.
38    pub fn insert(&mut self, value: T) -> Idx {
39        let index = if let Some(index) = self.inner.iter_mut().position(|v| v.is_none()) {
40            self.inner[index] = Some(value);
41            index
42        } else {
43            self.inner.push(Some(value));
44            self.inner.len() - 1
45        };
46
47        Self::to_call_index(index)
48    }
49
50    /// Retrieve a value by index. Returns `None` if the index does not point to a value.
51    pub fn get(&self, index: Idx) -> Option<&T> {
52        match Self::to_internal_index(index) {
53            Some(index) => self.inner.get(index).map(|v| v.as_ref()).unwrap_or(None),
54            None => None,
55        }
56    }
57
58    /// Retrieve a mutable reference to a value by index. Returns `None` if the index does not point
59    /// to a value.
60    pub fn get_mut(&mut self, index: Idx) -> Option<&mut T> {
61        match Self::to_internal_index(index) {
62            Some(index) => self.inner.get_mut(index).map(|v| v.as_mut()).unwrap_or(None),
63            None => None,
64        }
65    }
66
67    /// Remove a value by index. Returns `None` if the value did not point to a value.
68    pub fn remove(&mut self, index: Idx) -> Option<T> {
69        match Self::to_internal_index(index) {
70            Some(index) => self.inner.get_mut(index).map(|v| v.take()).unwrap_or(None),
71            None => None,
72        }
73    }
74
75    /// Return an iterator of the calls and associated call indices.
76    pub fn calls(&self) -> impl Iterator<Item = (Idx, &T)> + Clone {
77        self.inner
78            .iter()
79            .enumerate()
80            .flat_map(|(i, entry)| entry.as_ref().map(|v| (Self::to_call_index(i), v)))
81    }
82
83    /// Return an iterator of mutable references to the calls and associated call indices.
84    pub fn calls_mut(&mut self) -> impl Iterator<Item = (Idx, &mut T)> {
85        self.inner
86            .iter_mut()
87            .enumerate()
88            .flat_map(|(i, entry)| entry.as_mut().map(|v| (Self::to_call_index(i), v)))
89    }
90
91    /// Convert a `Idx` to the internal index used to locate a call.
92    ///
93    /// The Idx for a call starts at 1 instead of 0, so the internal index must be decremented
94    /// after being received by the user.
95    ///
96    /// Returns `None` if `index` is 0 because 0 is an invalid index.
97    fn to_internal_index(index: Idx) -> Option<usize> {
98        (index != 0).then(|| index - 1)
99    }
100
101    /// Convert the internal index for a call to the external `Idx`.
102    /// The Idx for a call starts at 1 instead of 0, so the internal index must be incremented
103    /// before being returned to the user.
104    fn to_call_index(internal: usize) -> Idx {
105        internal + 1
106    }
107
108    /// Returns the number of calls in the call list.
109    pub fn len(&self) -> usize {
110        self.inner.iter().map(Option::as_ref).filter(Option::is_some).count()
111    }
112}
113
114#[cfg(test)]
115mod tests {
116    use super::*;
117
118    #[fuchsia::test]
119    fn call_list_insert() {
120        let mut list = List::default();
121        let i1 = list.insert(1);
122        assert_eq!(i1, 1, "The first value must be assigned the number 1");
123        let i2 = list.insert(2);
124        assert_eq!(i2, 2, "The second value is assigned the next available number");
125    }
126
127    #[fuchsia::test]
128    fn call_list_get() {
129        let mut list = List::default();
130        let i1 = list.insert(1);
131        let i2 = list.insert(2);
132        assert_eq!(list.get(0), None);
133        assert_eq!(list.get(i1), Some(&1));
134        assert_eq!(list.get(i2), Some(&2));
135        assert_eq!(list.get(3), None);
136    }
137
138    #[fuchsia::test]
139    fn call_list_get_mut() {
140        let mut list = List::default();
141        let i1 = list.insert(1);
142        let i2 = list.insert(2);
143        assert_eq!(list.get_mut(i1), Some(&mut 1));
144        assert_eq!(list.get_mut(i2), Some(&mut 2));
145        assert_eq!(list.get_mut(3), None);
146    }
147
148    #[fuchsia::test]
149    fn call_list_remove() {
150        let mut list = List::default();
151        let i1 = list.insert(1);
152        let i2 = list.insert(2);
153        let removed = list.remove(i1);
154        assert!(removed.is_some());
155        assert_eq!(list.get(i1), None, "The value at i1 is removed");
156        assert_eq!(list.get(i2), Some(&2), "The value at i2 is untouched");
157        let invalid_idx = 0;
158        assert!(list.remove(invalid_idx).is_none());
159    }
160
161    #[fuchsia::test]
162    fn call_list_remove_and_insert_behaves() {
163        let mut list = List::default();
164        let i1 = list.insert(1);
165        let i2 = list.insert(2);
166        let i3 = list.insert(3);
167        let i4 = list.insert(4);
168        assert!(list.remove(i2).is_some());
169        assert!(list.remove(i1).is_some());
170        assert!(list.remove(i3).is_some());
171        let i5 = list.insert(5);
172        assert_eq!(i5, i1, "i5 is the lowest possible index (i1) even though i1 was not the first or last index removed");
173        assert_eq!(list.get(i5), Some(&5), "The value at i5 is correct");
174        let i6 = list.insert(6);
175        let i7 = list.insert(7);
176        assert_eq!(i6, i2, "i6 takes the next available index (i2)");
177        assert_eq!(i7, i3, "i7 takes the next available index (i3)");
178        let i8_ = list.insert(8);
179        assert_ne!(i8_, i4, "i4 is reserved, so i8_ must take a new index");
180        assert_eq!(
181            i8_, 5,
182            "i8_ takes an index of 5 since it is the last of the 5 values to be inserted"
183        );
184    }
185
186    #[fuchsia::test]
187    fn call_list_iter_returns_all_valid_values() {
188        let mut list = List::default();
189        let i1 = list.insert(1);
190        let i2 = list.insert(2);
191        let i3 = list.insert(3);
192        let i4 = list.insert(4);
193        assert!(list.remove(i2).is_some());
194        let actual: Vec<_> = list.calls().collect();
195        let expected = vec![(i1, &1), (i3, &3), (i4, &4)];
196        assert_eq!(actual, expected);
197    }
198}
bt_hfp/call/list.rs

bt_hfp/call/
list.rs
