summaryrefslogtreecommitdiffstats
path: root/vendor/indexmap/src/map
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/indexmap/src/map')
-rw-r--r--vendor/indexmap/src/map/core.rs20
-rw-r--r--vendor/indexmap/src/map/core/raw.rs23
-rw-r--r--vendor/indexmap/src/map/slice.rs75
-rw-r--r--vendor/indexmap/src/map/tests.rs221
4 files changed, 313 insertions, 26 deletions
diff --git a/vendor/indexmap/src/map/core.rs b/vendor/indexmap/src/map/core.rs
index 3e392ace6..4a78035c9 100644
--- a/vendor/indexmap/src/map/core.rs
+++ b/vendor/indexmap/src/map/core.rs
@@ -410,6 +410,26 @@ impl<K, V> IndexMapCore<K, V> {
}
}
+ pub(crate) fn swap_indices(&mut self, a: usize, b: usize) {
+ // If they're equal and in-bounds, there's nothing to do.
+ if a == b && a < self.entries.len() {
+ return;
+ }
+
+ // We'll get a "nice" bounds-check from indexing `self.entries`,
+ // and then we expect to find it in the table as well.
+ let [ref_a, ref_b] = self
+ .indices
+ .get_many_mut(
+ [self.entries[a].hash.get(), self.entries[b].hash.get()],
+ move |i, &x| if i == 0 { x == a } else { x == b },
+ )
+ .expect("indices not found");
+
+ mem::swap(ref_a, ref_b);
+ self.entries.swap(a, b);
+ }
+
/// Remove an entry by swapping it with the last
pub(crate) fn swap_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)>
where
diff --git a/vendor/indexmap/src/map/core/raw.rs b/vendor/indexmap/src/map/core/raw.rs
index 332770cc2..be71c9cff 100644
--- a/vendor/indexmap/src/map/core/raw.rs
+++ b/vendor/indexmap/src/map/core/raw.rs
@@ -100,29 +100,6 @@ impl<K, V> IndexMapCore<K, V> {
// only the item references that are appropriately bound to `&mut self`.
unsafe { self.indices.iter().map(|bucket| bucket.as_mut()) }
}
-
- /// Return the raw bucket for the given index
- fn find_index(&self, index: usize) -> RawBucket {
- // We'll get a "nice" bounds-check from indexing `self.entries`,
- // and then we expect to find it in the table as well.
- let hash = self.entries[index].hash.get();
- self.indices
- .find(hash, move |&i| i == index)
- .expect("index not found")
- }
-
- pub(crate) fn swap_indices(&mut self, a: usize, b: usize) {
- // SAFETY: Can't take two `get_mut` references from one table, so we
- // must use raw buckets to do the swap. This is still safe because we
- // are locally sure they won't dangle, and we write them individually.
- unsafe {
- let raw_bucket_a = self.find_index(a);
- let raw_bucket_b = self.find_index(b);
- *raw_bucket_a.as_mut() = b;
- *raw_bucket_b.as_mut() = a;
- }
- self.entries.swap(a, b);
- }
}
/// A view into an occupied entry in a `IndexMap`.
diff --git a/vendor/indexmap/src/map/slice.rs b/vendor/indexmap/src/map/slice.rs
index 9fb876fd2..ebab208c9 100644
--- a/vendor/indexmap/src/map/slice.rs
+++ b/vendor/indexmap/src/map/slice.rs
@@ -27,7 +27,7 @@ pub struct Slice<K, V> {
// and reference lifetimes are bound together in function signatures.
#[allow(unsafe_code)]
impl<K, V> Slice<K, V> {
- pub(super) fn from_slice(entries: &[Bucket<K, V>]) -> &Self {
+ pub(super) const fn from_slice(entries: &[Bucket<K, V>]) -> &Self {
unsafe { &*(entries as *const [Bucket<K, V>] as *const Self) }
}
@@ -49,15 +49,25 @@ impl<K, V> Slice<K, V> {
self.into_boxed().into_vec()
}
+ /// Returns an empty slice.
+ pub const fn new<'a>() -> &'a Self {
+ Self::from_slice(&[])
+ }
+
+ /// Returns an empty mutable slice.
+ pub fn new_mut<'a>() -> &'a mut Self {
+ Self::from_mut_slice(&mut [])
+ }
+
/// Return the number of key-value pairs in the map slice.
#[inline]
- pub fn len(&self) -> usize {
+ pub const fn len(&self) -> usize {
self.entries.len()
}
/// Returns true if the map slice contains no elements.
#[inline]
- pub fn is_empty(&self) -> bool {
+ pub const fn is_empty(&self) -> bool {
self.entries.is_empty()
}
@@ -201,6 +211,65 @@ impl<K, V> Slice<K, V> {
pub fn into_values(self: Box<Self>) -> IntoValues<K, V> {
IntoValues::new(self.into_entries())
}
+
+ /// Search over a sorted map for a key.
+ ///
+ /// Returns the position where that key is present, or the position where it can be inserted to
+ /// maintain the sort. See [`slice::binary_search`] for more details.
+ ///
+ /// Computes in **O(log(n))** time, which is notably less scalable than looking the key up in
+ /// the map this is a slice from using [`IndexMap::get_index_of`], but this can also position
+ /// missing keys.
+ pub fn binary_search_keys(&self, x: &K) -> Result<usize, usize>
+ where
+ K: Ord,
+ {
+ self.binary_search_by(|p, _| p.cmp(x))
+ }
+
+ /// Search over a sorted map with a comparator function.
+ ///
+ /// Returns the position where that value is present, or the position where it can be inserted
+ /// to maintain the sort. See [`slice::binary_search_by`] for more details.
+ ///
+ /// Computes in **O(log(n))** time.
+ #[inline]
+ pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
+ where
+ F: FnMut(&'a K, &'a V) -> Ordering,
+ {
+ self.entries.binary_search_by(move |a| f(&a.key, &a.value))
+ }
+
+ /// Search over a sorted map with an extraction function.
+ ///
+ /// Returns the position where that value is present, or the position where it can be inserted
+ /// to maintain the sort. See [`slice::binary_search_by_key`] for more details.
+ ///
+ /// Computes in **O(log(n))** time.
+ #[inline]
+ pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
+ where
+ F: FnMut(&'a K, &'a V) -> B,
+ B: Ord,
+ {
+ self.binary_search_by(|k, v| f(k, v).cmp(b))
+ }
+
+ /// Returns the index of the partition point of a sorted map according to the given predicate
+ /// (the index of the first element of the second partition).
+ ///
+ /// See [`slice::partition_point`] for more details.
+ ///
+ /// Computes in **O(log(n))** time.
+ #[must_use]
+ pub fn partition_point<P>(&self, mut pred: P) -> usize
+ where
+ P: FnMut(&K, &V) -> bool,
+ {
+ self.entries
+ .partition_point(move |a| pred(&a.key, &a.value))
+ }
}
impl<'a, K, V> IntoIterator for &'a Slice<K, V> {
diff --git a/vendor/indexmap/src/map/tests.rs b/vendor/indexmap/src/map/tests.rs
index f273d7162..3d2315d3e 100644
--- a/vendor/indexmap/src/map/tests.rs
+++ b/vendor/indexmap/src/map/tests.rs
@@ -447,3 +447,224 @@ fn iter_default() {
assert_default::<ValuesMut<'static, K, V>>();
assert_default::<IntoValues<K, V>>();
}
+
+#[test]
+fn test_binary_search_by() {
+ // adapted from std's test for binary_search
+ let b: IndexMap<_, i32> = []
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(0));
+
+ let b: IndexMap<_, i32> = [4]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&3)), Err(0));
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&4)), Ok(0));
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(1));
+
+ let b: IndexMap<_, i32> = [1, 2, 4, 6, 8, 9]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(3));
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&6)), Ok(3));
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&7)), Err(4));
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&8)), Ok(4));
+
+ let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&9)), Err(6));
+
+ let b: IndexMap<_, i32> = [1, 2, 4, 6, 7, 8, 9]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&6)), Ok(3));
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(3));
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&8)), Ok(5));
+
+ let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8, 9]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&7)), Err(5));
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&0)), Err(0));
+
+ let b: IndexMap<_, i32> = [1, 3, 3, 3, 7]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&0)), Err(0));
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&1)), Ok(0));
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&2)), Err(1));
+ assert!(match b.binary_search_by(|_, x| x.cmp(&3)) {
+ Ok(1..=3) => true,
+ _ => false,
+ });
+ assert!(match b.binary_search_by(|_, x| x.cmp(&3)) {
+ Ok(1..=3) => true,
+ _ => false,
+ });
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&4)), Err(4));
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(4));
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&6)), Err(4));
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&7)), Ok(4));
+ assert_eq!(b.binary_search_by(|_, x| x.cmp(&8)), Err(5));
+}
+
+#[test]
+fn test_binary_search_by_key() {
+ // adapted from std's test for binary_search
+ let b: IndexMap<_, i32> = []
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(0));
+
+ let b: IndexMap<_, i32> = [4]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.binary_search_by_key(&3, |_, &x| x), Err(0));
+ assert_eq!(b.binary_search_by_key(&4, |_, &x| x), Ok(0));
+ assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(1));
+
+ let b: IndexMap<_, i32> = [1, 2, 4, 6, 8, 9]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(3));
+ assert_eq!(b.binary_search_by_key(&6, |_, &x| x), Ok(3));
+ assert_eq!(b.binary_search_by_key(&7, |_, &x| x), Err(4));
+ assert_eq!(b.binary_search_by_key(&8, |_, &x| x), Ok(4));
+
+ let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.binary_search_by_key(&9, |_, &x| x), Err(6));
+
+ let b: IndexMap<_, i32> = [1, 2, 4, 6, 7, 8, 9]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.binary_search_by_key(&6, |_, &x| x), Ok(3));
+ assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(3));
+ assert_eq!(b.binary_search_by_key(&8, |_, &x| x), Ok(5));
+
+ let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8, 9]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.binary_search_by_key(&7, |_, &x| x), Err(5));
+ assert_eq!(b.binary_search_by_key(&0, |_, &x| x), Err(0));
+
+ let b: IndexMap<_, i32> = [1, 3, 3, 3, 7]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.binary_search_by_key(&0, |_, &x| x), Err(0));
+ assert_eq!(b.binary_search_by_key(&1, |_, &x| x), Ok(0));
+ assert_eq!(b.binary_search_by_key(&2, |_, &x| x), Err(1));
+ assert!(match b.binary_search_by_key(&3, |_, &x| x) {
+ Ok(1..=3) => true,
+ _ => false,
+ });
+ assert!(match b.binary_search_by_key(&3, |_, &x| x) {
+ Ok(1..=3) => true,
+ _ => false,
+ });
+ assert_eq!(b.binary_search_by_key(&4, |_, &x| x), Err(4));
+ assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(4));
+ assert_eq!(b.binary_search_by_key(&6, |_, &x| x), Err(4));
+ assert_eq!(b.binary_search_by_key(&7, |_, &x| x), Ok(4));
+ assert_eq!(b.binary_search_by_key(&8, |_, &x| x), Err(5));
+}
+
+#[test]
+fn test_partition_point() {
+ // adapted from std's test for partition_point
+ let b: IndexMap<_, i32> = []
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.partition_point(|_, &x| x < 5), 0);
+
+ let b: IndexMap<_, i32> = [4]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.partition_point(|_, &x| x < 3), 0);
+ assert_eq!(b.partition_point(|_, &x| x < 4), 0);
+ assert_eq!(b.partition_point(|_, &x| x < 5), 1);
+
+ let b: IndexMap<_, i32> = [1, 2, 4, 6, 8, 9]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.partition_point(|_, &x| x < 5), 3);
+ assert_eq!(b.partition_point(|_, &x| x < 6), 3);
+ assert_eq!(b.partition_point(|_, &x| x < 7), 4);
+ assert_eq!(b.partition_point(|_, &x| x < 8), 4);
+
+ let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.partition_point(|_, &x| x < 9), 6);
+
+ let b: IndexMap<_, i32> = [1, 2, 4, 6, 7, 8, 9]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.partition_point(|_, &x| x < 6), 3);
+ assert_eq!(b.partition_point(|_, &x| x < 5), 3);
+ assert_eq!(b.partition_point(|_, &x| x < 8), 5);
+
+ let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8, 9]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.partition_point(|_, &x| x < 7), 5);
+ assert_eq!(b.partition_point(|_, &x| x < 0), 0);
+
+ let b: IndexMap<_, i32> = [1, 3, 3, 3, 7]
+ .into_iter()
+ .enumerate()
+ .map(|(i, x)| (i + 100, x))
+ .collect();
+ assert_eq!(b.partition_point(|_, &x| x < 0), 0);
+ assert_eq!(b.partition_point(|_, &x| x < 1), 0);
+ assert_eq!(b.partition_point(|_, &x| x < 2), 1);
+ assert_eq!(b.partition_point(|_, &x| x < 3), 1);
+ assert_eq!(b.partition_point(|_, &x| x < 4), 4);
+ assert_eq!(b.partition_point(|_, &x| x < 5), 4);
+ assert_eq!(b.partition_point(|_, &x| x < 6), 4);
+ assert_eq!(b.partition_point(|_, &x| x < 7), 4);
+ assert_eq!(b.partition_point(|_, &x| x < 8), 5);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-02-04 20:54:08 +0000