1 use core::mem;
2 use core::fmt;
3 use core::slice;
4 use core::borrow::Borrow;
5 use core::ops::{Bound, RangeBounds};
6 
7 #[cfg(feature = "std")]
8 use std::collections::BTreeMap;
9 #[cfg(feature = "std")]
10 use std::collections::btree_map::{Iter as BTreeIter, IterMut as BTreeIterMut,
11                                   Range as BTreeRange};
12 #[cfg(all(feature = "alloc", not(feature = "std")))]
13 use alloc::collections::btree_map::BTreeMap;
14 #[cfg(all(feature = "alloc", not(feature = "std")))]
15 use alloc::collections::btree_map::{Iter as BTreeIter, IterMut as BTreeIterMut,
16                                     Range as BTreeRange};
17 
18 /// A managed map.
19 ///
20 /// This enum can be used to represent exclusive access to maps.
21 /// In Rust, exclusive access to an object is obtained by either owning the object,
22 /// or owning a mutable pointer to the object; hence, "managed".
23 ///
24 /// The purpose of this enum is providing good ergonomics with `std` present while making
25 /// it possible to avoid having a heap at all (which of course means that `std` is not present).
26 /// To achieve this, the variants other than `Borrow` are only available when the corresponding
27 /// feature is opted in.
28 ///
29 /// Unlike [Managed](enum.Managed.html) and [ManagedSlice](enum.ManagedSlice.html),
30 /// the managed map is implemented using a B-tree map when allocation is available,
31 /// and a sorted slice of key-value pairs when it is not. Thus, algorithmic complexity
32 /// of operations on it depends on the kind of map.
33 ///
34 /// A function that requires a managed object should be generic over an `Into<ManagedMap<'a, T>>`
35 /// argument; then, it will be possible to pass either a `Vec<T>`, or a `&'a mut [T]`
36 /// without any conversion at the call site.
37 ///
38 /// See also [Managed](enum.Managed.html).
39 pub enum ManagedMap<'a, K: 'a, V: 'a> {
40     /// Borrowed variant.
41     Borrowed(&'a mut [Option<(K, V)>]),
42     /// Owned variant, only available with the `std` or `alloc` feature enabled.
43     #[cfg(any(feature = "std", feature = "alloc"))]
44     Owned(BTreeMap<K, V>)
45 }
46 
47 impl<'a, K: 'a, V: 'a> fmt::Debug for ManagedMap<'a, K, V>
48         where K: fmt::Debug, V: fmt::Debug {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result49     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
50         match self {
51             &ManagedMap::Borrowed(ref x) => write!(f, "Borrowed({:?})", x),
52             #[cfg(any(feature = "std", feature = "alloc"))]
53             &ManagedMap::Owned(ref x)    => write!(f, "Owned({:?})", x)
54         }
55     }
56 }
57 
58 impl<'a, K: 'a, V: 'a> From<&'a mut [Option<(K, V)>]> for ManagedMap<'a, K, V> {
from(value: &'a mut [Option<(K, V)>]) -> Self59     fn from(value: &'a mut [Option<(K, V)>]) -> Self {
60         ManagedMap::Borrowed(value)
61     }
62 }
63 
64 #[cfg(any(feature = "std", feature = "alloc"))]
65 impl<'a, K: 'a, V: 'a> From<BTreeMap<K, V>> for ManagedMap<'a, K, V> {
from(value: BTreeMap<K, V>) -> Self66     fn from(value: BTreeMap<K, V>) -> Self {
67         ManagedMap::Owned(value)
68     }
69 }
70 
71 /// Like `Option`, but with `Some` values sorting first.
72 #[derive(PartialEq, Eq, PartialOrd, Ord)]
73 enum RevOption<T> {
74     Some(T),
75     None
76 }
77 
78 impl<T> From<Option<T>> for RevOption<T> {
from(other: Option<T>) -> Self79     fn from(other: Option<T>) -> Self {
80         match other {
81             Some(x) => RevOption::Some(x),
82             None => RevOption::None
83         }
84     }
85 }
86 
87 impl<T> Into<Option<T>> for RevOption<T> {
into(self) -> Option<T>88     fn into(self) -> Option<T> {
89         match self {
90             RevOption::Some(x) => Some(x),
91             RevOption::None => None
92         }
93     }
94 }
95 
96 #[derive(Debug, Clone)]
97 enum RangeInner<'a, K: 'a, V: 'a> {
98     /// Borrowed variant.
99     Borrowed { slice: &'a [Option<(K, V)>], begin: usize, end: usize },
100     /// Owned variant, only available with the `std` or `alloc` feature enabled.
101     #[cfg(any(feature = "std", feature = "alloc"))]
102     Owned(BTreeRange<'a, K, V>),
103 }
104 
105 #[derive(Debug, Clone)]
106 pub struct Range<'a, K: 'a, V: 'a>(RangeInner<'a, K, V>);
107 
108 impl<'a, K: 'a, V: 'a> Iterator for Range<'a, K, V> {
109     type Item = (&'a K, &'a V);
110 
next(&mut self) -> Option<Self::Item>111     fn next(&mut self) -> Option<Self::Item> {
112         match self.0 {
113             RangeInner::Borrowed { ref slice, ref mut begin, ref end } => {
114                 *begin += 1;
115                 if *begin-1 >= *end {
116                     None
117                 } else {
118                     match slice[*begin-1] {
119                         None => None,
120                         Some((ref k, ref v)) => Some((k, v))
121                     }
122                 }
123             },
124             #[cfg(any(feature = "std", feature = "alloc"))]
125             RangeInner::Owned(ref mut range) => range.next(),
126         }
127     }
128 }
129 
130 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Range<'a, K, V> {
next_back(&mut self) -> Option<Self::Item>131     fn next_back(&mut self) -> Option<Self::Item> {
132         match self.0 {
133             RangeInner::Borrowed { ref slice, ref begin, ref mut end } => {
134                 if *begin >= *end {
135                     None
136                 } else {
137                     *end -= 1;
138                     match slice[*end] {
139                         None => None,
140                         Some((ref k, ref v)) => Some((k, v))
141                     }
142                 }
143             },
144             #[cfg(any(feature = "std", feature = "alloc"))]
145             RangeInner::Owned(ref mut range) => range.next_back(),
146         }
147     }
148 }
149 
binary_search_by_key_range<'a, K, V, Q: 'a, R>(slice: &[Option<(K, V)>], range: R) -> Result<(usize, usize), ()> where K: Ord + Borrow<Q>, Q: Ord + ?Sized, R: RangeBounds<Q>150 fn binary_search_by_key_range<'a, K, V, Q: 'a, R>(slice: &[Option<(K, V)>], range: R) -> Result<(usize, usize), ()>
151     where K: Ord + Borrow<Q>, Q: Ord + ?Sized, R: RangeBounds<Q>
152 {
153     if slice.len() == 0 {
154         return Err(())
155     }
156     let (mut left, mut right) = (0, slice.len() - 1);
157 
158     macro_rules! key {
159         ( $e:expr) => { $e.as_ref().map(|&(ref key, _)| key.borrow()) }
160     }
161 
162     // We cannot use slice.binary_search_by_key instead of each of the
163     // two loops here, because we need the left-most match (for begin) and
164     // the right-most match (for end), and the stdlib does not provide
165     // any of these guarantees.
166 
167     // Find the beginning
168     let begin;
169     if let Bound::Unbounded = range.start_bound() {
170         begin = 0;
171     } else {
172         macro_rules! is_before_range {
173             ( $item: expr) => {
174                 match &range.start_bound() {
175                     Bound::Included(ref key_begin) => $item < Some(key_begin.borrow()),
176                     Bound::Excluded(ref key_begin) => $item <= Some(key_begin.borrow()),
177                     Bound::Unbounded => unreachable!()
178                 }
179             }
180         };
181         while left < right {
182             let middle = left + (right - left) / 2;
183             if is_before_range!(key!(slice[middle])) {
184                 left = middle + 1;
185             } else if middle > 0 && !is_before_range!(key!(slice[middle - 1])) {
186                 right = middle - 1;
187             } else {
188                 left = middle;
189                 break
190             }
191         }
192         if left == slice.len() || is_before_range!(key!(slice[left])) {
193             return Err(())
194         }
195         begin = left
196     };
197 
198     // Find the ending
199     let end;
200     if let Bound::Unbounded = range.end_bound() {
201         end = slice.len()
202     } else {
203         macro_rules! is_after_range {
204             ( $item:expr ) => {
205                 match &range.end_bound() {
206                     Bound::Included(ref key_end) => $item > Some(key_end.borrow()),
207                     Bound::Excluded(ref key_end) => $item >= Some(key_end.borrow()),
208                     Bound::Unbounded => unreachable!()
209                 }
210             }
211         };
212         right = slice.len(); // no need to reset left
213         while left < right {
214             let middle = left + (right - left + 1) / 2;
215             if is_after_range!(key!(slice[middle - 1])) {
216                 right = middle - 1;
217             } else if middle < slice.len() && !is_after_range!(key!(slice[middle])) {
218                 left = middle + 1;
219             } else {
220                 right = middle;
221                 break
222             }
223         }
224         if right == 0 || is_after_range!(key!(slice[right - 1])) {
225             return Err(())
226         }
227         end = right
228     };
229 
230     Ok((begin, end))
231 }
232 
binary_search_by_key<K, V, Q>(slice: &[Option<(K, V)>], key: &Q) -> Result<usize, usize> where K: Ord + Borrow<Q>, Q: Ord + ?Sized233 fn binary_search_by_key<K, V, Q>(slice: &[Option<(K, V)>], key: &Q) -> Result<usize, usize>
234     where K: Ord + Borrow<Q>, Q: Ord + ?Sized
235 {
236     slice.binary_search_by_key(&RevOption::Some(key), |entry| {
237         entry.as_ref().map(|&(ref key, _)| key.borrow()).into()
238     })
239 }
240 
pair_by_key<'a, K, Q, V>(slice: &'a [Option<(K, V)>], key: &Q) -> Result<&'a (K, V), usize> where K: Ord + Borrow<Q>, Q: Ord + ?Sized241 fn pair_by_key<'a, K, Q, V>(slice: &'a [Option<(K, V)>], key: &Q) ->
242                            Result<&'a (K, V), usize>
243     where K: Ord + Borrow<Q>, Q: Ord + ?Sized
244 {
245     binary_search_by_key(slice, key).map(move |idx| slice[idx].as_ref().unwrap())
246 }
247 
pair_mut_by_key<'a, K, Q, V>(slice: &'a mut [Option<(K, V)>], key: &Q) -> Result<&'a mut (K, V), usize> where K: Ord + Borrow<Q>, Q: Ord + ?Sized248 fn pair_mut_by_key<'a, K, Q, V>(slice: &'a mut [Option<(K, V)>], key: &Q) ->
249                                Result<&'a mut (K, V), usize>
250     where K: Ord + Borrow<Q>, Q: Ord + ?Sized
251 {
252     binary_search_by_key(slice, key).map(move |idx| slice[idx].as_mut().unwrap())
253 }
254 
255 impl<'a, K: Ord + 'a, V: 'a> ManagedMap<'a, K, V> {
clear(&mut self)256     pub fn clear(&mut self) {
257         match self {
258             &mut ManagedMap::Borrowed(ref mut pairs) => {
259                 for item in pairs.iter_mut() {
260                     *item = None
261                 }
262             },
263             #[cfg(any(feature = "std", feature = "alloc"))]
264             &mut ManagedMap::Owned(ref mut map) => map.clear()
265         }
266     }
267 
get<Q>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord + ?Sized268     pub fn get<Q>(&self, key: &Q) -> Option<&V>
269         where K: Borrow<Q>, Q: Ord + ?Sized
270     {
271         match self {
272             &ManagedMap::Borrowed(ref pairs) => {
273                 match pair_by_key(pairs, key.borrow()) {
274                     Ok(&(_, ref value)) => Some(value),
275                     Err(_) => None
276                 }
277             },
278             #[cfg(any(feature = "std", feature = "alloc"))]
279             &ManagedMap::Owned(ref map) => map.get(key)
280         }
281     }
282 
get_mut<Q>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord + ?Sized283     pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
284         where K: Borrow<Q>, Q: Ord + ?Sized
285     {
286         match self {
287             &mut ManagedMap::Borrowed(ref mut pairs) => {
288                 match pair_mut_by_key(pairs, key.borrow()) {
289                     Ok(&mut (_, ref mut value)) => Some(value),
290                     Err(_) => None
291                 }
292             },
293             #[cfg(any(feature = "std", feature = "alloc"))]
294             &mut ManagedMap::Owned(ref mut map) => map.get_mut(key)
295         }
296     }
297 
range<'b, 'c, Q: 'c, R>(&'b self, range: R) -> Range<'a, K, V> where K: Borrow<Q>, Q: Ord + ?Sized, R: RangeBounds<Q>, 'b: 'a298     pub fn range<'b, 'c, Q: 'c, R>(&'b self, range: R) -> Range<'a, K, V>
299             where K: Borrow<Q>, Q: Ord + ?Sized, R: RangeBounds<Q>, 'b: 'a
300     {
301         match self {
302             &ManagedMap::Borrowed(ref pairs) => {
303                 match binary_search_by_key_range(&pairs[0..self.len()], range) {
304                     Ok((begin, end)) => Range(RangeInner::Borrowed {
305                         slice: &pairs[begin..end], begin: 0, end: end-begin }),
306                     Err(()) => Range(RangeInner::Borrowed {
307                         slice: &[], begin: 0, end: 0 }),
308                 }
309             },
310             #[cfg(any(feature = "std", feature = "alloc"))]
311             &ManagedMap::Owned(ref map) => {
312                 Range(RangeInner::Owned(map.range(range)))
313             },
314         }
315     }
316 
insert(&mut self, key: K, new_value: V) -> Result<Option<V>, (K, V)>317     pub fn insert(&mut self, key: K, new_value: V) -> Result<Option<V>, (K, V)> {
318         match self {
319             &mut ManagedMap::Borrowed(ref mut pairs) if pairs.len() < 1 =>
320                 Err((key, new_value)), // no space at all
321             &mut ManagedMap::Borrowed(ref mut pairs) => {
322                 match binary_search_by_key(pairs, &key) {
323                     Err(_) if pairs[pairs.len() - 1].is_some() =>
324                         Err((key, new_value)), // full
325                     Err(idx) => {
326                         let rotate_by = pairs.len() - idx - 1;
327                         pairs[idx..].rotate_left(rotate_by);
328                         assert!(pairs[idx].is_none(), "broken invariant");
329                         pairs[idx] = Some((key, new_value));
330                         Ok(None)
331                     }
332                     Ok(idx) => {
333                         let mut swap_pair = Some((key, new_value));
334                         mem::swap(&mut pairs[idx], &mut swap_pair);
335                         let (_key, value) = swap_pair.expect("broken invariant");
336                         Ok(Some(value))
337                     }
338                 }
339             },
340             #[cfg(any(feature = "std", feature = "alloc"))]
341             &mut ManagedMap::Owned(ref mut map) => Ok(map.insert(key, new_value))
342         }
343     }
344 
remove<Q>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord + ?Sized345     pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
346         where K: Borrow<Q>, Q: Ord + ?Sized
347     {
348         match self {
349             &mut ManagedMap::Borrowed(ref mut pairs) => {
350                 match binary_search_by_key(pairs, key) {
351                     Ok(idx) => {
352                         let (_key, value) = pairs[idx].take().expect("broken invariant");
353                         pairs[idx..].rotate_left(1);
354                         Some(value)
355                     }
356                     Err(_) => None
357                 }
358             },
359             #[cfg(any(feature = "std", feature = "alloc"))]
360             &mut ManagedMap::Owned(ref mut map) => map.remove(key)
361         }
362     }
363 
364     /// ManagedMap contains no elements?
is_empty(&self) -> bool365     pub fn is_empty(&self) -> bool {
366         match self {
367             &ManagedMap::Borrowed(ref pairs) =>
368                 pairs.iter().all(|item| item.is_none()),
369             #[cfg(any(feature = "std", feature = "alloc"))]
370             &ManagedMap::Owned(ref map) =>
371                 map.is_empty()
372         }
373     }
374 
375     /// Returns the number of elements in the ManagedMap.
len(&self) -> usize376     pub fn len(&self) -> usize {
377         match self {
378             &ManagedMap::Borrowed(ref pairs) =>
379                 pairs.iter()
380                 .take_while(|item| item.is_some())
381                 .count(),
382             #[cfg(any(feature = "std", feature = "alloc"))]
383             &ManagedMap::Owned(ref map) =>
384                 map.len()
385         }
386     }
387 
iter(&self) -> Iter<K, V>388     pub fn iter(&self) -> Iter<K, V> {
389         match self {
390             &ManagedMap::Borrowed(ref pairs) =>
391                 Iter::Borrowed(pairs.iter()),
392             #[cfg(any(feature = "std", feature = "alloc"))]
393             &ManagedMap::Owned(ref map) =>
394                 Iter::Owned(map.iter()),
395         }
396     }
397 
iter_mut(&mut self) -> IterMut<K, V>398     pub fn iter_mut(&mut self) -> IterMut<K, V> {
399         match self {
400             &mut ManagedMap::Borrowed(ref mut pairs) =>
401                 IterMut::Borrowed(pairs.iter_mut()),
402             #[cfg(any(feature = "std", feature = "alloc"))]
403             &mut ManagedMap::Owned(ref mut map) =>
404                 IterMut::Owned(map.iter_mut()),
405         }
406     }
407 }
408 
409 pub enum Iter<'a, K: 'a, V: 'a> {
410     /// Borrowed variant.
411     Borrowed(slice::Iter<'a, Option<(K, V)>>),
412     /// Owned variant, only available with the `std` or `alloc` feature enabled.
413     #[cfg(any(feature = "std", feature = "alloc"))]
414     Owned(BTreeIter<'a, K, V>),
415 }
416 
417 impl<'a, K: Ord + 'a, V: 'a> Iterator for Iter<'a, K, V> {
418     type Item = (&'a K, &'a V);
419 
next(&mut self) -> Option<Self::Item>420     fn next(&mut self) -> Option<Self::Item> {
421         match self {
422             &mut Iter::Borrowed(ref mut iter) =>
423                 match iter.next() {
424                     Some(&Some((ref k, ref v))) => Some((&k, &v)),
425                     Some(&None) => None,
426                     None => None,
427                 },
428             #[cfg(any(feature = "std", feature = "alloc"))]
429             &mut Iter::Owned(ref mut iter) =>
430                 iter.next(),
431         }
432     }
433 
size_hint(&self) -> (usize, Option<usize>)434     fn size_hint(&self) -> (usize, Option<usize>) {
435         match self {
436             &Iter::Borrowed(ref iter) => {
437                 let len = iter.clone()
438                     .take_while(|item| item.is_some())
439                     .count();
440                 (len, Some(len))
441             },
442             #[cfg(any(feature = "std", feature = "alloc"))]
443             &Iter::Owned(ref iter) =>
444                 iter.size_hint(),
445         }
446     }
447 }
448 
449 pub enum IterMut<'a, K: 'a, V: 'a> {
450     /// Borrowed variant.
451     Borrowed(slice::IterMut<'a, Option<(K, V)>>),
452     /// Owned variant, only available with the `std` or `alloc` feature enabled.
453     #[cfg(any(feature = "std", feature = "alloc"))]
454     Owned(BTreeIterMut<'a, K, V>),
455 }
456 
457 impl<'a, K: Ord + 'a, V: 'a> Iterator for IterMut<'a, K, V> {
458     type Item = (&'a K, &'a mut V);
459 
next(&mut self) -> Option<Self::Item>460     fn next(&mut self) -> Option<Self::Item> {
461         match self {
462             &mut IterMut::Borrowed(ref mut iter) =>
463                 match iter.next() {
464                     Some(&mut Some((ref k, ref mut v))) => Some((&k, v)),
465                     Some(&mut None) => None,
466                     None => None,
467                 },
468             #[cfg(any(feature = "std", feature = "alloc"))]
469             &mut IterMut::Owned(ref mut iter) =>
470                 iter.next(),
471         }
472     }
473 
size_hint(&self) -> (usize, Option<usize>)474     fn size_hint(&self) -> (usize, Option<usize>) {
475         match self {
476             &IterMut::Borrowed(ref iter) => {
477                 let (_, upper) = iter.size_hint();
478                 (0, upper)
479             },
480             #[cfg(any(feature = "std", feature = "alloc"))]
481             &IterMut::Owned(ref iter) =>
482                 iter.size_hint(),
483         }
484     }
485 }
486 
487 // LCOV_EXCL_START
488 #[cfg(test)]
489 mod test {
490     use super::ManagedMap;
491     use core::ops::Bound::*;
492 
all_pairs_empty() -> [Option<(&'static str, u32)>; 4]493     fn all_pairs_empty() -> [Option<(&'static str, u32)>; 4] {
494         [None; 4]
495     }
496 
one_pair_full() -> [Option<(&'static str, u32)>; 4]497     fn one_pair_full() -> [Option<(&'static str, u32)>; 4] {
498         [Some(("a", 1)), None, None, None]
499     }
500 
all_pairs_full() -> [Option<(&'static str, u32)>; 4]501     fn all_pairs_full() -> [Option<(&'static str, u32)>; 4] {
502         [Some(("a", 1)), Some(("b", 2)), Some(("c", 3)), Some(("d", 4))]
503     }
504 
unwrap<'a, K, V>(map: &'a ManagedMap<'a, K, V>) -> &'a [Option<(K, V)>]505     fn unwrap<'a, K, V>(map: &'a ManagedMap<'a, K, V>) -> &'a [Option<(K, V)>] {
506         match map {
507             &ManagedMap::Borrowed(ref map) => map,
508             _ => unreachable!()
509         }
510     }
511 
512     #[test]
test_clear()513     fn test_clear() {
514         let mut pairs = all_pairs_full();
515         let mut map = ManagedMap::Borrowed(&mut pairs);
516         map.clear();
517         assert!(map.is_empty());
518         assert_eq!(map.len(), 0);
519         assert_eq!(unwrap(&map), all_pairs_empty());
520     }
521 
522     #[test]
test_get_some()523     fn test_get_some() {
524         let mut pairs = all_pairs_full();
525         let map = ManagedMap::Borrowed(&mut pairs);
526         assert_eq!(map.len(), 4);
527         assert_eq!(map.get("a"), Some(&1));
528         assert_eq!(map.get("b"), Some(&2));
529         assert_eq!(map.get("c"), Some(&3));
530         assert_eq!(map.get("d"), Some(&4));
531     }
532 
533     #[test]
test_get_some_one_pair()534     fn test_get_some_one_pair() {
535         let mut pairs = one_pair_full();
536         let map = ManagedMap::Borrowed(&mut pairs);
537         assert_eq!(map.len(), 1);
538         assert_eq!(map.get("a"), Some(&1));
539     }
540 
541     #[test]
test_get_none_full()542     fn test_get_none_full() {
543         let mut pairs = all_pairs_full();
544         let map = ManagedMap::Borrowed(&mut pairs);
545         assert_eq!(map.len(), 4);
546         assert!(!map.is_empty());
547         assert_eq!(map.get("q"), None);
548         assert_eq!(map.get("0"), None);
549     }
550 
551     #[test]
test_get_none()552     fn test_get_none() {
553         let mut pairs = one_pair_full();
554         let map = ManagedMap::Borrowed(&mut pairs);
555         assert_eq!(map.len(), 1);
556         assert!(!map.is_empty());
557         assert_eq!(map.get("0"), None);
558         assert_eq!(map.get("q"), None);
559     }
560 
561     #[test]
test_get_none_empty()562     fn test_get_none_empty() {
563         let mut pairs = all_pairs_empty();
564         let map = ManagedMap::Borrowed(&mut pairs);
565         assert_eq!(map.len(), 0);
566         assert!(map.is_empty());
567         assert_eq!(map.get("q"), None);
568     }
569 
570     #[test]
test_range_full_unbounded()571     fn test_range_full_unbounded() {
572         let mut pairs = all_pairs_full();
573         let map = ManagedMap::Borrowed(&mut pairs);
574         assert_eq!(map.len(), 4);
575 
576         let mut range = map.range("a"..);
577         assert_eq!(range.next(), Some((&"a", &1)));
578         assert_eq!(range.next(), Some((&"b", &2)));
579         assert_eq!(range.next(), Some((&"c", &3)));
580         assert_eq!(range.next(), Some((&"d", &4)));
581         assert_eq!(range.next(), None);
582         assert_eq!(range.next_back(), None);
583 
584         let mut range = map.range("a"..);
585         assert_eq!(range.next(), Some((&"a", &1)));
586         assert_eq!(range.next_back(), Some((&"d", &4)));
587         assert_eq!(range.next_back(), Some((&"c", &3)));
588         assert_eq!(range.next(), Some((&"b", &2)));
589         assert_eq!(range.next_back(), None);
590         assert_eq!(range.next(), None);
591 
592         let mut range = map.range("b"..);
593         assert_eq!(range.next(), Some((&"b", &2)));
594         assert_eq!(range.next(), Some((&"c", &3)));
595         assert_eq!(range.next(), Some((&"d", &4)));
596         assert_eq!(range.next(), None);
597         assert_eq!(range.next_back(), None);
598 
599         let mut range = map.range("d"..);
600         assert_eq!(range.next(), Some((&"d", &4)));
601         assert_eq!(range.next(), None);
602         assert_eq!(range.next_back(), None);
603 
604         let mut range = map.range(.."e");
605         assert_eq!(range.next(), Some((&"a", &1)));
606         assert_eq!(range.next(), Some((&"b", &2)));
607         assert_eq!(range.next(), Some((&"c", &3)));
608         assert_eq!(range.next(), Some((&"d", &4)));
609         assert_eq!(range.next(), None);
610         assert_eq!(range.next_back(), None);
611 
612         let mut range = map.range(.."d");
613         assert_eq!(range.next(), Some((&"a", &1)));
614         assert_eq!(range.next(), Some((&"b", &2)));
615         assert_eq!(range.next(), Some((&"c", &3)));
616         assert_eq!(range.next(), None);
617         assert_eq!(range.next_back(), None);
618 
619         let mut range = map.range(.."b");
620         assert_eq!(range.next(), Some((&"a", &1)));
621         assert_eq!(range.next(), None);
622         assert_eq!(range.next_back(), None);
623 
624         let mut range = map.range(.."a");
625         assert_eq!(range.next(), None);
626         assert_eq!(range.next_back(), None);
627 
628         let mut range = map.range::<&str, _>(..);
629         assert_eq!(range.next(), Some((&"a", &1)));
630         assert_eq!(range.next(), Some((&"b", &2)));
631         assert_eq!(range.next(), Some((&"c", &3)));
632         assert_eq!(range.next(), Some((&"d", &4)));
633         assert_eq!(range.next(), None);
634         assert_eq!(range.next_back(), None);
635     }
636 
637     #[test]
test_range_full_exclude_left()638     fn test_range_full_exclude_left() {
639         let mut pairs = all_pairs_full();
640         let map = ManagedMap::Borrowed(&mut pairs);
641         assert_eq!(map.len(), 4);
642 
643         let mut range = map.range::<&str, _>((Excluded("a"), Excluded("a")));
644         assert_eq!(range.next(), None);
645         let mut range = map.range::<&str, _>((Excluded("a"), Excluded("b")));
646         assert_eq!(range.next(), None);
647         let mut range = map.range::<&str, _>((Excluded("a"), Excluded("c")));
648         assert_eq!(range.next(), Some((&"b", &2)));
649         assert_eq!(range.next(), None);
650         let mut range = map.range::<&str, _>((Excluded("a"), Excluded("d")));
651         assert_eq!(range.next(), Some((&"b", &2)));
652         assert_eq!(range.next(), Some((&"c", &3)));
653         assert_eq!(range.next(), None);
654         let mut range = map.range::<&str, _>((Excluded("a"), Excluded("e")));
655         assert_eq!(range.next(), Some((&"b", &2)));
656         assert_eq!(range.next(), Some((&"c", &3)));
657         assert_eq!(range.next(), Some((&"d", &4)));
658         assert_eq!(range.next(), None);
659     }
660 
661     #[test]
test_range_full_include_right()662     fn test_range_full_include_right() {
663         let mut pairs = all_pairs_full();
664         let map = ManagedMap::Borrowed(&mut pairs);
665         assert_eq!(map.len(), 4);
666 
667         let mut range = map.range::<&str, _>((Included("b"), Included("a")));
668         assert_eq!(range.next(), None);
669         let mut range = map.range::<&str, _>((Included("b"), Included("b")));
670         assert_eq!(range.next(), Some((&"b", &2)));
671         assert_eq!(range.next(), None);
672         let mut range = map.range::<&str, _>((Included("b"), Included("c")));
673         assert_eq!(range.next(), Some((&"b", &2)));
674         assert_eq!(range.next(), Some((&"c", &3)));
675         assert_eq!(range.next(), None);
676         let mut range = map.range::<&str, _>((Included("b"), Included("d")));
677         assert_eq!(range.next(), Some((&"b", &2)));
678         assert_eq!(range.next(), Some((&"c", &3)));
679         assert_eq!(range.next(), Some((&"d", &4)));
680         assert_eq!(range.next(), None);
681         let mut range = map.range::<&str, _>((Included("b"), Included("e")));
682         assert_eq!(range.next(), Some((&"b", &2)));
683         assert_eq!(range.next(), Some((&"c", &3)));
684         assert_eq!(range.next(), Some((&"d", &4)));
685         assert_eq!(range.next(), None);
686 
687         let mut range = map.range::<&str, _>((Included("b"), Included("a")));
688         assert_eq!(range.next_back(), None);
689         let mut range = map.range::<&str, _>((Included("b"), Included("b")));
690         assert_eq!(range.next_back(), Some((&"b", &2)));
691         assert_eq!(range.next_back(), None);
692         let mut range = map.range::<&str, _>((Included("b"), Included("c")));
693         assert_eq!(range.next_back(), Some((&"c", &3)));
694         assert_eq!(range.next_back(), Some((&"b", &2)));
695         assert_eq!(range.next_back(), None);
696         let mut range = map.range::<&str, _>((Included("b"), Included("d")));
697         assert_eq!(range.next_back(), Some((&"d", &4)));
698         assert_eq!(range.next_back(), Some((&"c", &3)));
699         assert_eq!(range.next_back(), Some((&"b", &2)));
700         assert_eq!(range.next_back(), None);
701         let mut range = map.range::<&str, _>((Included("b"), Included("e")));
702         assert_eq!(range.next_back(), Some((&"d", &4)));
703         assert_eq!(range.next_back(), Some((&"c", &3)));
704         assert_eq!(range.next_back(), Some((&"b", &2)));
705         assert_eq!(range.next_back(), None);
706     }
707 
708     #[test]
test_range_full()709     fn test_range_full() {
710         let mut pairs = all_pairs_full();
711         let map = ManagedMap::Borrowed(&mut pairs);
712         assert_eq!(map.len(), 4);
713 
714         let mut range = map.range("0".."a");
715         assert_eq!(range.next(), None);
716         let mut range = map.range("0".."b");
717         assert_eq!(range.next(), Some((&"a", &1)));
718         assert_eq!(range.next(), None);
719         let mut range = map.range("0".."c");
720         assert_eq!(range.next(), Some((&"a", &1)));
721         assert_eq!(range.next(), Some((&"b", &2)));
722         assert_eq!(range.next(), None);
723         let mut range = map.range("0".."d");
724         assert_eq!(range.next(), Some((&"a", &1)));
725         assert_eq!(range.next(), Some((&"b", &2)));
726         assert_eq!(range.next(), Some((&"c", &3)));
727         assert_eq!(range.next(), None);
728         let mut range = map.range("0".."e");
729         assert_eq!(range.next(), Some((&"a", &1)));
730         assert_eq!(range.next(), Some((&"b", &2)));
731         assert_eq!(range.next(), Some((&"c", &3)));
732         assert_eq!(range.next(), Some((&"d", &4)));
733         assert_eq!(range.next(), None);
734 
735         let mut range = map.range("a".."a");
736         assert_eq!(range.next(), None);
737         let mut range = map.range("a".."b");
738         assert_eq!(range.next(), Some((&"a", &1)));
739         assert_eq!(range.next(), None);
740         let mut range = map.range("a".."c");
741         assert_eq!(range.next(), Some((&"a", &1)));
742         assert_eq!(range.next(), Some((&"b", &2)));
743         assert_eq!(range.next(), None);
744         let mut range = map.range("a".."d");
745         assert_eq!(range.next(), Some((&"a", &1)));
746         assert_eq!(range.next(), Some((&"b", &2)));
747         assert_eq!(range.next(), Some((&"c", &3)));
748         assert_eq!(range.next(), None);
749         let mut range = map.range("a".."e");
750         assert_eq!(range.next(), Some((&"a", &1)));
751         assert_eq!(range.next(), Some((&"b", &2)));
752         assert_eq!(range.next(), Some((&"c", &3)));
753         assert_eq!(range.next(), Some((&"d", &4)));
754         assert_eq!(range.next(), None);
755 
756         let mut range = map.range("b".."a");
757         assert_eq!(range.next(), None);
758         let mut range = map.range("b".."b");
759         assert_eq!(range.next(), None);
760         let mut range = map.range("b".."c");
761         assert_eq!(range.next(), Some((&"b", &2)));
762         assert_eq!(range.next(), None);
763         let mut range = map.range("b".."d");
764         assert_eq!(range.next(), Some((&"b", &2)));
765         assert_eq!(range.next(), Some((&"c", &3)));
766         assert_eq!(range.next(), None);
767         let mut range = map.range("b".."e");
768         assert_eq!(range.next(), Some((&"b", &2)));
769         assert_eq!(range.next(), Some((&"c", &3)));
770         assert_eq!(range.next(), Some((&"d", &4)));
771         assert_eq!(range.next(), None);
772 
773         let mut range = map.range("c".."a");
774         assert_eq!(range.next(), None);
775         let mut range = map.range("c".."b");
776         assert_eq!(range.next(), None);
777         let mut range = map.range("c".."c");
778         assert_eq!(range.next(), None);
779         let mut range = map.range("c".."d");
780         assert_eq!(range.next(), Some((&"c", &3)));
781         assert_eq!(range.next(), None);
782         let mut range = map.range("c".."e");
783         assert_eq!(range.next(), Some((&"c", &3)));
784         assert_eq!(range.next(), Some((&"d", &4)));
785         assert_eq!(range.next(), None);
786 
787         let mut range = map.range("d".."a");
788         assert_eq!(range.next(), None);
789         let mut range = map.range("d".."b");
790         assert_eq!(range.next(), None);
791         let mut range = map.range("d".."c");
792         assert_eq!(range.next(), None);
793         let mut range = map.range("d".."d");
794         assert_eq!(range.next(), None);
795         let mut range = map.range("d".."e");
796         assert_eq!(range.next(), Some((&"d", &4)));
797         assert_eq!(range.next(), None);
798 
799         let mut range = map.range("e".."a");
800         assert_eq!(range.next(), None);
801         let mut range = map.range("e".."b");
802         assert_eq!(range.next(), None);
803         let mut range = map.range("e".."c");
804         assert_eq!(range.next(), None);
805         let mut range = map.range("e".."d");
806         assert_eq!(range.next(), None);
807         let mut range = map.range("e".."e");
808         assert_eq!(range.next(), None);
809     }
810 
811     #[test]
test_range_one_pair()812     fn test_range_one_pair() {
813         let mut pairs = one_pair_full();
814         let map = ManagedMap::Borrowed(&mut pairs);
815         assert_eq!(map.len(), 1);
816 
817         let mut range = map.range("0".."a");
818         assert_eq!(range.next(), None);
819         let mut range = map.range("0".."b");
820         assert_eq!(range.next(), Some((&"a", &1)));
821         assert_eq!(range.next(), None);
822         let mut range = map.range("0".."c");
823         assert_eq!(range.next(), Some((&"a", &1)));
824         assert_eq!(range.next(), None);
825 
826         let mut range = map.range("a".."a");
827         assert_eq!(range.next(), None);
828         let mut range = map.range("a".."b");
829         assert_eq!(range.next(), Some((&"a", &1)));
830         assert_eq!(range.next(), None);
831         let mut range = map.range("a".."c");
832         assert_eq!(range.next(), Some((&"a", &1)));
833         assert_eq!(range.next(), None);
834 
835         let mut range = map.range("b".."a");
836         assert_eq!(range.next(), None);
837         let mut range = map.range("b".."b");
838         assert_eq!(range.next(), None);
839         let mut range = map.range("b".."c");
840         assert_eq!(range.next(), None);
841     }
842 
843     #[test]
test_range_empty()844     fn test_range_empty() {
845         let mut pairs = all_pairs_empty();
846         let map = ManagedMap::Borrowed(&mut pairs);
847         assert_eq!(map.len(), 0);
848 
849         let mut range = map.range("b".."a");
850         assert_eq!(range.next(), None);
851         let mut range = map.range("b".."b");
852         assert_eq!(range.next(), None);
853         let mut range = map.range("b".."c");
854         assert_eq!(range.next(), None);
855     }
856 
857     #[test]
test_get_mut_some()858     fn test_get_mut_some() {
859         let mut pairs = all_pairs_full();
860         let mut map = ManagedMap::Borrowed(&mut pairs);
861         assert_eq!(map.len(), 4);
862         assert!(!map.is_empty());
863         assert_eq!(map.get_mut("a"), Some(&mut 1));
864         assert_eq!(map.get_mut("b"), Some(&mut 2));
865         assert_eq!(map.get_mut("c"), Some(&mut 3));
866         assert_eq!(map.get_mut("d"), Some(&mut 4));
867     }
868 
869     #[test]
test_get_mut_none()870     fn test_get_mut_none() {
871         let mut pairs = one_pair_full();
872         let mut map = ManagedMap::Borrowed(&mut pairs);
873         assert_eq!(map.get_mut("q"), None);
874     }
875 
876     #[test]
test_insert_empty()877     fn test_insert_empty() {
878         let mut pairs = all_pairs_empty();
879         let mut map = ManagedMap::Borrowed(&mut pairs);
880         assert_eq!(map.len(), 0);
881         assert!(map.is_empty());
882 
883         assert_eq!(map.insert("a", 1), Ok(None));
884         assert_eq!(map.len(), 1);
885         assert!(!map.is_empty());
886         assert_eq!(unwrap(&map),       [Some(("a", 1)), None, None, None]);
887     }
888 
889     #[test]
test_insert_replace()890     fn test_insert_replace() {
891         let mut pairs = all_pairs_empty();
892         let mut map = ManagedMap::Borrowed(&mut pairs);
893         assert_eq!(map.insert("a", 1), Ok(None));
894         assert_eq!(map.insert("a", 2), Ok(Some(1)));
895         assert_eq!(map.len(), 1);
896         assert!(!map.is_empty());
897         assert_eq!(unwrap(&map),       [Some(("a", 2)), None, None, None]);
898     }
899 
900     #[test]
test_insert_full()901     fn test_insert_full() {
902         let mut pairs = all_pairs_full();
903         let mut map = ManagedMap::Borrowed(&mut pairs);
904         assert_eq!(map.insert("q", 1), Err(("q", 1)));
905         assert_eq!(map.len(), 4);
906         assert_eq!(unwrap(&map),       all_pairs_full());
907     }
908 
909     #[test]
test_insert_one()910     fn test_insert_one() {
911         let mut pairs = one_pair_full();
912         let mut map = ManagedMap::Borrowed(&mut pairs);
913         assert_eq!(map.insert("b", 2), Ok(None));
914         assert_eq!(unwrap(&map),       [Some(("a", 1)), Some(("b", 2)), None, None]);
915     }
916 
917     #[test]
test_insert_shift()918     fn test_insert_shift() {
919         let mut pairs = one_pair_full();
920         let mut map = ManagedMap::Borrowed(&mut pairs);
921         assert_eq!(map.insert("c", 3), Ok(None));
922         assert_eq!(map.insert("b", 2), Ok(None));
923         assert_eq!(unwrap(&map),       [Some(("a", 1)), Some(("b", 2)), Some(("c", 3)), None]);
924     }
925 
926     #[test]
test_insert_no_space()927     fn test_insert_no_space() {
928         // Zero-sized backing store
929         let mut map = ManagedMap::Borrowed(&mut []);
930         assert_eq!(map.insert("a", 1), Err(("a", 1)));
931     }
932 
933     #[test]
test_remove_nonexistent()934     fn test_remove_nonexistent() {
935         let mut pairs = one_pair_full();
936         let mut map = ManagedMap::Borrowed(&mut pairs);
937         assert_eq!(map.remove("b"), None);
938         assert_eq!(map.len(), 1);
939     }
940 
941     #[test]
test_remove_one()942     fn test_remove_one() {
943         let mut pairs = all_pairs_full();
944         let mut map = ManagedMap::Borrowed(&mut pairs);
945         assert_eq!(map.remove("a"), Some(1));
946         assert_eq!(map.len(), 3);
947         assert_eq!(unwrap(&map),    [Some(("b", 2)), Some(("c", 3)), Some(("d", 4)), None]);
948     }
949 
950     #[test]
test_iter_none()951     fn test_iter_none() {
952         let mut pairs = all_pairs_empty();
953         let map = ManagedMap::Borrowed(&mut pairs);
954         let mut iter = map.iter();
955         assert_eq!(iter.size_hint(), (0, Some(0)));
956         assert_eq!(iter.next(), None);
957     }
958 
959     #[test]
test_iter_one()960     fn test_iter_one() {
961         let mut pairs = one_pair_full();
962         let map = ManagedMap::Borrowed(&mut pairs);
963         let mut iter = map.iter();
964         assert_eq!(iter.size_hint(), (1, Some(1)));
965         assert_eq!(iter.next(), Some((&"a", &1)));
966         assert_eq!(iter.size_hint(), (0, Some(0)));
967         assert_eq!(iter.next(), None);
968     }
969 
970     #[test]
test_iter_full()971     fn test_iter_full() {
972         let mut pairs = all_pairs_full();
973         let map = ManagedMap::Borrowed(&mut pairs);
974         let mut iter = map.iter();
975         assert_eq!(iter.size_hint(), (4, Some(4)));
976         assert_eq!(iter.next(), Some((&"a", &1)));
977         assert_eq!(iter.next(), Some((&"b", &2)));
978         assert_eq!(iter.next(), Some((&"c", &3)));
979         assert_eq!(iter.next(), Some((&"d", &4)));
980         assert_eq!(iter.next(), None);
981     }
982 
983     #[test]
test_iter_mut_full()984     fn test_iter_mut_full() {
985         let mut pairs = all_pairs_full();
986         let mut map = ManagedMap::Borrowed(&mut pairs);
987 
988         {
989             let mut iter = map.iter_mut();
990             assert_eq!(iter.size_hint(), (0, Some(4)));
991             for (_k, mut v) in &mut iter {
992                 *v += 1;
993             }
994             assert_eq!(iter.size_hint(), (0, Some(0)));
995             // Scope for `iter` ends here so that it can be borrowed
996             // again with the following `iter`.
997         }
998         {
999             let mut iter = map.iter();
1000             assert_eq!(iter.next(), Some((&"a", &2)));
1001             assert_eq!(iter.next(), Some((&"b", &3)));
1002             assert_eq!(iter.next(), Some((&"c", &4)));
1003             assert_eq!(iter.next(), Some((&"d", &5)));
1004             assert_eq!(iter.next(), None);
1005         }
1006     }
1007 }
1008