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

bt_hfp/call/
list.rs
