Merging upstream version 1.67.1+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

3 files changed, 360 insertions, 0 deletions

diff --git a/vendor/litemap/src/store/mod.rs b/vendor/litemap/src/store/mod.rs
new file mode 100644
index 000000000..e4ba6f7b9
--- /dev/null
+++ b/vendor/litemap/src/store/mod.rs
@@ -0,0 +1,165 @@
+// This file is part of ICU4X. For terms of use, please see the file
+// called LICENSE at the top level of the ICU4X source tree
+// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
+
+//! Traits for pluggable LiteMap backends.
+//!
+//! By default, LiteMap is backed by a `Vec`. However, in some environments, it may be desirable
+//! to use a different data store while still using LiteMap to manage proper ordering of items.
+//!
+//! The general guidelines for a performant data store are:
+//!
+//! 1. Must support efficient random access for binary search
+//! 2. Should support efficient append operations for deserialization
+//!
+//! To plug a custom data store into LiteMap, implement:
+//!
+//! - [`Store`] for most of the methods
+//! - [`StoreIterable`] for methods that return iterators
+//! - [`StoreFromIterator`] to enable `FromIterator` for LiteMap
+//!
+//! To test your implementation, enable the `"testing"` feature and use [`check_store()`].
+//!
+//! [`check_store()`]: crate::testing::check_store
+
+mod slice_impl;
+#[cfg(feature = "alloc")]
+mod vec_impl;
+
+use core::cmp::Ordering;
+use core::iter::DoubleEndedIterator;
+use core::iter::FromIterator;
+use core::iter::Iterator;
+
+/// Trait to enable const construction of empty store.
+pub trait StoreConstEmpty<K: ?Sized, V: ?Sized> {
+    /// An empty store
+    const EMPTY: Self;
+}
+
+/// Trait to enable pluggable backends for LiteMap.
+///
+/// Some methods have default implementations provided for convenience; however, it is generally
+/// better to implement all methods that your data store supports.
+pub trait Store<K: ?Sized, V: ?Sized>: Sized {
+    /// Returns the number of elements in the store.
+    fn lm_len(&self) -> usize;
+
+    /// Returns whether the store is empty (contains 0 elements).
+    fn lm_is_empty(&self) -> bool {
+        self.lm_len() == 0
+    }
+
+    /// Gets a key/value pair at the specified index.
+    fn lm_get(&self, index: usize) -> Option<(&K, &V)>;
+
+    /// Gets the last element in the store, or None if the store is empty.
+    fn lm_last(&self) -> Option<(&K, &V)> {
+        let len = self.lm_len();
+        if len == 0 {
+            None
+        } else {
+            self.lm_get(len - 1)
+        }
+    }
+
+    /// Searches the store for a particular element with a comparator function.
+    ///
+    /// See the binary search implementation on `slice` for more information.
+    fn lm_binary_search_by<F>(&self, cmp: F) -> Result<usize, usize>
+    where
+        F: FnMut(&K) -> Ordering;
+}
+
+pub trait StoreMut<K, V>: Store<K, V> {
+    /// Creates a new store with the specified capacity hint.
+    ///
+    /// Implementations may ignore the argument if they do not support pre-allocating capacity.
+    fn lm_with_capacity(capacity: usize) -> Self;
+
+    /// Reserves additional capacity in the store.
+    ///
+    /// Implementations may ignore the argument if they do not support pre-allocating capacity.
+    fn lm_reserve(&mut self, additional: usize);
+
+    /// Gets a key/value pair at the specified index, with a mutable value.
+    fn lm_get_mut(&mut self, index: usize) -> Option<(&K, &mut V)>;
+    /// Pushes one additional item onto the store.
+    fn lm_push(&mut self, key: K, value: V);
+
+    /// Inserts an item at a specific index in the store.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than the length.
+    fn lm_insert(&mut self, index: usize, key: K, value: V);
+
+    /// Removes an item at a specific index in the store.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than the length.
+    fn lm_remove(&mut self, index: usize) -> (K, V);
+
+    /// Removes all items from the store.
+    fn lm_clear(&mut self);
+
+    /// Retains items satisfying a predicate in this store.
+    fn lm_retain<F>(&mut self, mut predicate: F)
+    where
+        F: FnMut(&K, &V) -> bool,
+    {
+        let mut i = 0;
+        while i < self.lm_len() {
+            #[allow(clippy::unwrap_used)] // i is in range
+            let (k, v) = self.lm_get(i).unwrap();
+            if predicate(k, v) {
+                i += 1;
+            } else {
+                self.lm_remove(i);
+            }
+        }
+    }
+}
+
+/// Iterator methods for the LiteMap store.
+pub trait StoreIterable<'a, K: 'a, V: 'a>: Store<K, V> {
+    type KeyValueIter: Iterator<Item = (&'a K, &'a V)> + DoubleEndedIterator + 'a;
+
+    /// Returns an iterator over key/value pairs.
+    fn lm_iter(&'a self) -> Self::KeyValueIter;
+}
+
+pub trait StoreIterableMut<'a, K: 'a, V: 'a>: StoreMut<K, V> + StoreIterable<'a, K, V> {
+    type KeyValueIterMut: Iterator<Item = (&'a K, &'a mut V)> + DoubleEndedIterator + 'a;
+    type KeyValueIntoIter: Iterator<Item = (K, V)>;
+
+    /// Returns an iterator over key/value pairs, with a mutable value.
+    fn lm_iter_mut(&'a mut self) -> Self::KeyValueIterMut;
+
+    /// Returns an iterator that moves every item from this store.
+    fn lm_into_iter(self) -> Self::KeyValueIntoIter;
+
+    /// Adds items from another store to the end of this store.
+    fn lm_extend_end(&mut self, other: Self)
+    where
+        Self: Sized,
+    {
+        for item in other.lm_into_iter() {
+            self.lm_push(item.0, item.1);
+        }
+    }
+
+    /// Adds items from another store to the beginning of this store.
+    fn lm_extend_start(&mut self, other: Self)
+    where
+        Self: Sized,
+    {
+        for (i, item) in other.lm_into_iter().enumerate() {
+            self.lm_insert(i, item.0, item.1);
+        }
+    }
+}
+
+/// A store that can be built from a tuple iterator.
+pub trait StoreFromIterator<K, V>: FromIterator<(K, V)> {}
diff --git a/vendor/litemap/src/store/slice_impl.rs b/vendor/litemap/src/store/slice_impl.rs
new file mode 100644
index 000000000..4afb4fac2
--- /dev/null
+++ b/vendor/litemap/src/store/slice_impl.rs
@@ -0,0 +1,55 @@
+// This file is part of ICU4X. For terms of use, please see the file
+// called LICENSE at the top level of the ICU4X source tree
+// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
+
+use super::*;
+
+type MapF<K, V> = fn(&(K, V)) -> (&K, &V);
+
+#[inline]
+fn map_f<K, V>(input: &(K, V)) -> (&K, &V) {
+    (&input.0, &input.1)
+}
+
+impl<'a, K: 'a, V: 'a> StoreConstEmpty<K, V> for &'a [(K, V)] {
+    const EMPTY: &'a [(K, V)] = &[];
+}
+
+impl<'a, K: 'a, V: 'a> Store<K, V> for &'a [(K, V)] {
+    #[inline]
+    fn lm_len(&self) -> usize {
+        self.len()
+    }
+
+    #[inline]
+    fn lm_is_empty(&self) -> bool {
+        self.is_empty()
+    }
+
+    #[inline]
+    fn lm_get(&self, index: usize) -> Option<(&K, &V)> {
+        self.get(index).map(map_f)
+    }
+
+    #[inline]
+    fn lm_last(&self) -> Option<(&K, &V)> {
+        self.last().map(map_f)
+    }
+
+    #[inline]
+    fn lm_binary_search_by<F>(&self, mut cmp: F) -> Result<usize, usize>
+    where
+        F: FnMut(&K) -> Ordering,
+    {
+        self.binary_search_by(|(k, _)| cmp(k))
+    }
+}
+
+impl<'a, K: 'a, V: 'a> StoreIterable<'a, K, V> for &'a [(K, V)] {
+    type KeyValueIter = core::iter::Map<core::slice::Iter<'a, (K, V)>, MapF<K, V>>;
+
+    #[inline]
+    fn lm_iter(&'a self) -> Self::KeyValueIter {
+        self.iter().map(map_f)
+    }
+}
diff --git a/vendor/litemap/src/store/vec_impl.rs b/vendor/litemap/src/store/vec_impl.rs
new file mode 100644
index 000000000..e94e0fb7f
--- /dev/null
+++ b/vendor/litemap/src/store/vec_impl.rs
@@ -0,0 +1,140 @@
+// This file is part of ICU4X. For terms of use, please see the file
+// called LICENSE at the top level of the ICU4X source tree
+// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
+
+use super::*;
+use alloc::vec::Vec;
+
+type MapF<K, V> = fn(&(K, V)) -> (&K, &V);
+
+#[inline]
+fn map_f<K, V>(input: &(K, V)) -> (&K, &V) {
+    (&input.0, &input.1)
+}
+
+type MapFMut<K, V> = fn(&mut (K, V)) -> (&K, &mut V);
+
+#[inline]
+fn map_f_mut<K, V>(input: &mut (K, V)) -> (&K, &mut V) {
+    (&input.0, &mut input.1)
+}
+
+impl<K, V> StoreConstEmpty<K, V> for Vec<(K, V)> {
+    const EMPTY: Vec<(K, V)> = Vec::new();
+}
+
+impl<K, V> Store<K, V> for Vec<(K, V)> {
+    #[inline]
+    fn lm_len(&self) -> usize {
+        self.as_slice().len()
+    }
+
+    #[inline]
+    fn lm_is_empty(&self) -> bool {
+        self.as_slice().is_empty()
+    }
+
+    #[inline]
+    fn lm_get(&self, index: usize) -> Option<(&K, &V)> {
+        self.as_slice().get(index).map(map_f)
+    }
+
+    #[inline]
+    fn lm_last(&self) -> Option<(&K, &V)> {
+        self.as_slice().last().map(map_f)
+    }
+
+    #[inline]
+    fn lm_binary_search_by<F>(&self, mut cmp: F) -> Result<usize, usize>
+    where
+        F: FnMut(&K) -> Ordering,
+    {
+        self.as_slice().binary_search_by(|(k, _)| cmp(k))
+    }
+}
+
+impl<K, V> StoreMut<K, V> for Vec<(K, V)> {
+    #[inline]
+    fn lm_with_capacity(capacity: usize) -> Self {
+        Self::with_capacity(capacity)
+    }
+
+    #[inline]
+    fn lm_reserve(&mut self, additional: usize) {
+        self.reserve(additional)
+    }
+
+    #[inline]
+    fn lm_get_mut(&mut self, index: usize) -> Option<(&K, &mut V)> {
+        self.as_mut_slice().get_mut(index).map(map_f_mut)
+    }
+
+    #[inline]
+    fn lm_push(&mut self, key: K, value: V) {
+        self.push((key, value))
+    }
+
+    #[inline]
+    fn lm_insert(&mut self, index: usize, key: K, value: V) {
+        self.insert(index, (key, value))
+    }
+
+    #[inline]
+    fn lm_remove(&mut self, index: usize) -> (K, V) {
+        self.remove(index)
+    }
+
+    #[inline]
+    fn lm_clear(&mut self) {
+        self.clear()
+    }
+
+    #[inline]
+    fn lm_retain<F>(&mut self, mut predicate: F)
+    where
+        F: FnMut(&K, &V) -> bool,
+    {
+        self.retain(|(k, v)| predicate(k, v))
+    }
+}
+
+impl<'a, K: 'a, V: 'a> StoreIterable<'a, K, V> for Vec<(K, V)> {
+    type KeyValueIter = core::iter::Map<core::slice::Iter<'a, (K, V)>, MapF<K, V>>;
+
+    #[inline]
+    fn lm_iter(&'a self) -> Self::KeyValueIter {
+        self.as_slice().iter().map(map_f)
+    }
+}
+
+impl<'a, K: 'a, V: 'a> StoreIterableMut<'a, K, V> for Vec<(K, V)> {
+    type KeyValueIterMut = core::iter::Map<core::slice::IterMut<'a, (K, V)>, MapFMut<K, V>>;
+    type KeyValueIntoIter = alloc::vec::IntoIter<(K, V)>;
+
+    #[inline]
+    fn lm_iter_mut(&'a mut self) -> Self::KeyValueIterMut {
+        self.as_mut_slice().iter_mut().map(map_f_mut)
+    }
+
+    #[inline]
+    fn lm_into_iter(self) -> Self::KeyValueIntoIter {
+        IntoIterator::into_iter(self)
+    }
+
+    #[inline]
+    fn lm_extend_end(&mut self, other: Self) {
+        self.extend(other)
+    }
+
+    #[inline]
+    fn lm_extend_start(&mut self, other: Self) {
+        self.splice(0..0, other);
+    }
+}
+
+impl<K, V> StoreFromIterator<K, V> for Vec<(K, V)> {}
+
+#[test]
+fn test_vec_impl() {
+    crate::testing::check_store_full::<Vec<(u32, u64)>>();
+}