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    /// Convert a `Idx` to the internal index used to locate a call.
84    ///
85    /// The Idx for a call starts at 1 instead of 0, so the internal index must be decremented
86    /// after being received by the user.
87    ///
88    /// Returns `None` if `index` is 0 because 0 is an invalid index.
89    fn to_internal_index(index: Idx) -> Option<usize> {
90        (index != 0).then(|| index - 1)
91    }
92
93    /// Convert the internal index for a call to the external `Idx`.
94    /// The Idx for a call starts at 1 instead of 0, so the internal index must be incremented
95    /// before being returned to the user.
96    fn to_call_index(internal: usize) -> Idx {
97        internal + 1
98    }
99
100    /// Returns the number of calls in the call list.
101    pub fn len(&self) -> usize {
102        self.inner.iter().map(Option::as_ref).filter(Option::is_some).count()
103    }
104}
105
106#[cfg(test)]
107mod tests {
108    use super::*;
109
110    #[fuchsia::test]
111    fn call_list_insert() {
112        let mut list = List::default();
113        let i1 = list.insert(1);
114        assert_eq!(i1, 1, "The first value must be assigned the number 1");
115        let i2 = list.insert(2);
116        assert_eq!(i2, 2, "The second value is assigned the next available number");
117    }
118
119    #[fuchsia::test]
120    fn call_list_get() {
121        let mut list = List::default();
122        let i1 = list.insert(1);
123        let i2 = list.insert(2);
124        assert_eq!(list.get(0), None);
125        assert_eq!(list.get(i1), Some(&1));
126        assert_eq!(list.get(i2), Some(&2));
127        assert_eq!(list.get(3), None);
128    }
129
130    #[fuchsia::test]
131    fn call_list_get_mut() {
132        let mut list = List::default();
133        let i1 = list.insert(1);
134        let i2 = list.insert(2);
135        assert_eq!(list.get_mut(i1), Some(&mut 1));
136        assert_eq!(list.get_mut(i2), Some(&mut 2));
137        assert_eq!(list.get_mut(3), None);
138    }
139
140    #[fuchsia::test]
141    fn call_list_remove() {
142        let mut list = List::default();
143        let i1 = list.insert(1);
144        let i2 = list.insert(2);
145        let removed = list.remove(i1);
146        assert!(removed.is_some());
147        assert_eq!(list.get(i1), None, "The value at i1 is removed");
148        assert_eq!(list.get(i2), Some(&2), "The value at i2 is untouched");
149        let invalid_idx = 0;
150        assert!(list.remove(invalid_idx).is_none());
151    }
152
153    #[fuchsia::test]
154    fn call_list_remove_and_insert_behaves() {
155        let mut list = List::default();
156        let i1 = list.insert(1);
157        let i2 = list.insert(2);
158        let i3 = list.insert(3);
159        let i4 = list.insert(4);
160        assert!(list.remove(i2).is_some());
161        assert!(list.remove(i1).is_some());
162        assert!(list.remove(i3).is_some());
163        let i5 = list.insert(5);
164        assert_eq!(i5, i1, "i5 is the lowest possible index (i1) even though i1 was not the first or last index removed");
165        assert_eq!(list.get(i5), Some(&5), "The value at i5 is correct");
166        let i6 = list.insert(6);
167        let i7 = list.insert(7);
168        assert_eq!(i6, i2, "i6 takes the next available index (i2)");
169        assert_eq!(i7, i3, "i7 takes the next available index (i3)");
170        let i8_ = list.insert(8);
171        assert_ne!(i8_, i4, "i4 is reserved, so i8_ must take a new index");
172        assert_eq!(
173            i8_, 5,
174            "i8_ takes an index of 5 since it is the last of the 5 values to be inserted"
175        );
176    }
177
178    #[fuchsia::test]
179    fn call_list_iter_returns_all_valid_values() {
180        let mut list = List::default();
181        let i1 = list.insert(1);
182        let i2 = list.insert(2);
183        let i3 = list.insert(3);
184        let i4 = list.insert(4);
185        assert!(list.remove(i2).is_some());
186        let actual: Vec<_> = list.calls().collect();
187        let expected = vec![(i1, &1), (i3, &3), (i4, &4)];
188        assert_eq!(actual, expected);
189    }
190}
bt_hfp/call/list.rs

bt_hfp/call/
list.rs
