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> List<T> {
30    /// Insert a new value into the list, returning an index that is guaranteed to be unique until
31    /// the value is removed from the list.
32    pub fn insert(&mut self, value: T) -> Idx {
33        let index = if let Some(index) = self.inner.iter_mut().position(|v| v.is_none()) {
34            self.inner[index] = Some(value);
35            index
36        } else {
37            self.inner.push(Some(value));
38            self.inner.len() - 1
39        };
40
41        Self::to_call_index(index)
42    }
43
44    /// Retrieve a value by index. Returns `None` if the index does not point to a value.
45    pub fn get(&self, index: Idx) -> Option<&T> {
46        match Self::to_internal_index(index) {
47            Some(index) => self.inner.get(index).map(|v| v.as_ref()).unwrap_or(None),
48            None => None,
49        }
50    }
51
52    /// Retrieve a mutable reference to a value by index. Returns `None` if the index does not point
53    /// to a value.
54    pub fn get_mut(&mut self, index: Idx) -> Option<&mut T> {
55        match Self::to_internal_index(index) {
56            Some(index) => self.inner.get_mut(index).map(|v| v.as_mut()).unwrap_or(None),
57            None => None,
58        }
59    }
60
61    /// Remove a value by index. Returns `None` if the value did not point to a value.
62    pub fn remove(&mut self, index: Idx) -> Option<T> {
63        match Self::to_internal_index(index) {
64            Some(index) => self.inner.get_mut(index).map(|v| v.take()).unwrap_or(None),
65            None => None,
66        }
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    /// Convert a `Idx` to the internal index used to locate a call.
78    ///
79    /// The Idx for a call starts at 1 instead of 0, so the internal index must be decremented
80    /// after being received by the user.
81    ///
82    /// Returns `None` if `index` is 0 because 0 is an invalid index.
83    fn to_internal_index(index: Idx) -> Option<usize> {
84        (index != 0).then(|| index - 1)
85    }
86
87    /// Convert the internal index for a call to the external `Idx`.
88    /// The Idx for a call starts at 1 instead of 0, so the internal index must be incremented
89    /// before being returned to the user.
90    fn to_call_index(internal: usize) -> Idx {
91        internal + 1
92    }
93}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98
99    #[fuchsia::test]
100    fn call_list_insert() {
101        let mut list = List::default();
102        let i1 = list.insert(1);
103        assert_eq!(i1, 1, "The first value must be assigned the number 1");
104        let i2 = list.insert(2);
105        assert_eq!(i2, 2, "The second value is assigned the next available number");
106    }
107
108    #[fuchsia::test]
109    fn call_list_get() {
110        let mut list = List::default();
111        let i1 = list.insert(1);
112        let i2 = list.insert(2);
113        assert_eq!(list.get(0), None);
114        assert_eq!(list.get(i1), Some(&1));
115        assert_eq!(list.get(i2), Some(&2));
116        assert_eq!(list.get(3), None);
117    }
118
119    #[fuchsia::test]
120    fn call_list_get_mut() {
121        let mut list = List::default();
122        let i1 = list.insert(1);
123        let i2 = list.insert(2);
124        assert_eq!(list.get_mut(i1), Some(&mut 1));
125        assert_eq!(list.get_mut(i2), Some(&mut 2));
126        assert_eq!(list.get_mut(3), None);
127    }
128
129    #[fuchsia::test]
130    fn call_list_remove() {
131        let mut list = List::default();
132        let i1 = list.insert(1);
133        let i2 = list.insert(2);
134        let removed = list.remove(i1);
135        assert!(removed.is_some());
136        assert_eq!(list.get(i1), None, "The value at i1 is removed");
137        assert_eq!(list.get(i2), Some(&2), "The value at i2 is untouched");
138        let invalid_idx = 0;
139        assert!(list.remove(invalid_idx).is_none());
140    }
141
142    #[fuchsia::test]
143    fn call_list_remove_and_insert_behaves() {
144        let mut list = List::default();
145        let i1 = list.insert(1);
146        let i2 = list.insert(2);
147        let i3 = list.insert(3);
148        let i4 = list.insert(4);
149        assert!(list.remove(i2).is_some());
150        assert!(list.remove(i1).is_some());
151        assert!(list.remove(i3).is_some());
152        let i5 = list.insert(5);
153        assert_eq!(i5, i1, "i5 is the lowest possible index (i1) even though i1 was not the first or last index removed");
154        assert_eq!(list.get(i5), Some(&5), "The value at i5 is correct");
155        let i6 = list.insert(6);
156        let i7 = list.insert(7);
157        assert_eq!(i6, i2, "i6 takes the next available index (i2)");
158        assert_eq!(i7, i3, "i7 takes the next available index (i3)");
159        let i8_ = list.insert(8);
160        assert_ne!(i8_, i4, "i4 is reserved, so i8_ must take a new index");
161        assert_eq!(
162            i8_, 5,
163            "i8_ takes an index of 5 since it is the last of the 5 values to be inserted"
164        );
165    }
166
167    #[fuchsia::test]
168    fn call_list_iter_returns_all_valid_values() {
169        let mut list = List::default();
170        let i1 = list.insert(1);
171        let i2 = list.insert(2);
172        let i3 = list.insert(3);
173        let i4 = list.insert(4);
174        assert!(list.remove(i2).is_some());
175        let actual: Vec<_> = list.calls().collect();
176        let expected = vec![(i1, &1), (i3, &3), (i4, &4)];
177        assert_eq!(actual, expected);
178    }
179}
bt_hfp/call/list.rs

bt_hfp/call/
list.rs
