🎩 You're Invited:Meet the Socket team at Black Hat in Las Vegas, August 3-6.RSVP →
Sign In

im-rc

Package Overview
Dependencies
Maintainers
1
Versions
16
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

im-rc - cargo Package Compare versions

Comparing version
14.3.0
 to
15.0.0
+17
-13
Cargo.toml

@@ -16,3 +16,3 @@ # THIS FILE IS AUTOMATICALLY GENERATED BY CARGO

name = "im-rc"
version = "14.3.0"
version = "15.0.0"
authors = ["Bodil Stokke <bodil@bodil.org>"]

@@ -38,3 +38,3 @@ build = "./build.rs"

[dependencies.bitmaps]
version = "2.0.0"
version = "2"

@@ -53,23 +53,23 @@ [dependencies.proptest]

[dependencies.rand_xoshiro]
version = "0.4.0"
version = "0.4"
[dependencies.rayon]
version = "1.0"
version = "1"
optional = true
[dependencies.refpool]
version = "0.2.2"
version = "0.4"
optional = true
[dependencies.serde]
version = "1.0"
version = "1"
optional = true
[dependencies.sized-chunks]
version = "0.5.1"
version = "0.6"
[dependencies.typenum]
version = "1.10"
version = "1.12"
[dev-dependencies.metrohash]
version = "1.0.6"
version = "1"

@@ -83,3 +83,3 @@ [dev-dependencies.pretty_assertions]

[dev-dependencies.proptest-derive]
version = "0.1.0"
version = "0.1"

@@ -91,12 +91,16 @@ [dev-dependencies.rand]

[dev-dependencies.rayon]
version = "1.0"
version = "1"
[dev-dependencies.serde]
version = "1.0"
version = "1"
[dev-dependencies.serde_json]
version = "1.0"
version = "1"
[build-dependencies.version_check]
version = "0.9"
[features]
debug = []
pool = ["refpool", "sized-chunks/refpool"]
[badges.travis-ci]
repository = "bodil/im-rs"
+27
-0
CHANGELOG.md

@@ -8,2 +8,29 @@ # Changelog

## [15.0.0] - 2020-05-15
### Changed
- Map iterators now return `(&K, &V)` and `(&K, &mut V)` respectively, to be consistent with
`std::collections`'s API. `DiffIter` for `OrdMap` has also changed in the same manner. (#121)
### Removed
- The `pool` feature flag has been removed from the `im` version of the crate, as `refpool` no
longer supports threadsafe pools.
- `HashSet::iter_mut()` has been removed, because if you modify the hashed values in a hash set,
you break the hash set.
### Added
- The `pool` feature flag was missing from the `im-rc` version of the crate, which is the version
where it's actually useful. It's been added now.
- `DiffIter` now has a `Debug` implementation.
- There is now a `Vector::is_inline()` method to determine whether a `Vector` is currently
inlined. (#129)
### Fixed
- A smarter implementation of the sorting algorithm for `Vector` has improved the performance of
`Vector::sort` by approximately 2x. (#126)
## [14.3.0] - 2020-03-03

@@ -10,0 +37,0 @@ 

+3
-47
src/hash/set.rs

@@ -34,5 +34,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public

use crate::nodes::hamt::{
hash_key, Drain as NodeDrain, HashValue, Iter as NodeIter, IterMut as NodeIterMut, Node,
};
use crate::nodes::hamt::{hash_key, Drain as NodeDrain, HashValue, Iter as NodeIter, Node};
use crate::ordset::OrdSet;

@@ -399,16 +397,2 @@ use crate::util::{Pool, PoolRef, Ref};

{
/// Get a mutable iterator over the values in a hash set.
///
/// Please note that the order is consistent between sets using the same
/// hasher, but no other ordering guarantee is offered. Items will not come
/// out in insertion order or sort order. They will, however, come out in
/// the same order every time for the same set.
#[must_use]
pub fn iter_mut(&mut self) -> IterMut<'_, A> {
let root = PoolRef::make_mut(&self.pool.0, &mut self.root);
IterMut {
it: NodeIterMut::new(&self.pool.0, root, self.size),
}
}
/// Insert a value into a set.

@@ -694,5 +678,3 @@ ///

}
let m1: ::std::collections::HashSet<A> = self.iter().cloned().collect();
let m2: ::std::collections::HashSet<A> = other.iter().cloned().collect();
m1.iter().partial_cmp(m2.iter())
self.iter().partial_cmp(other.iter())
}

@@ -710,5 +692,3 @@ }

}
let m1: ::std::collections::HashSet<A> = self.iter().cloned().collect();
let m2: ::std::collections::HashSet<A> = other.iter().cloned().collect();
m1.iter().cmp(m2.iter())
self.iter().cmp(other.iter())
}

@@ -883,26 +863,2 @@ }

/// A mutable iterator over the elements of a set.
pub struct IterMut<'a, A> {
it: NodeIterMut<'a, Value<A>>,
}
impl<'a, A> Iterator for IterMut<'a, A>
where
A: 'a + Clone,
{
type Item = &'a mut A;
fn next(&mut self) -> Option<Self::Item> {
self.it.next().map(|(v, _)| &mut v.0)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.it.size_hint()
}
}
impl<'a, A> ExactSizeIterator for IterMut<'a, A> where A: Clone {}
impl<'a, A> FusedIterator for IterMut<'a, A> where A: Clone {}
/// A consuming iterator over the elements of a set.

@@ -909,0 +865,0 @@ pub struct ConsumingIter<A>

+12
-7
src/lib.rs

@@ -306,3 +306,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public

//! | ------- | ----------- |
//! | [`pool`](https://crates.io/crates/refpool) | Constructors and pool types for [`refpool`](https://crates.io/crates/refpool) memory pools (recommended only for `im-rc`) |
//! | [`pool`](https://crates.io/crates/refpool) | Constructors and pool types for [`refpool`](https://crates.io/crates/refpool) memory pools (only available in `im-rc`) |
//! | [`proptest`](https://crates.io/crates/proptest) | Strategies for all `im` datatypes under a `proptest` namespace, eg. `im::vector::proptest::vector()` |

@@ -328,7 +328,7 @@ //! | [`quickcheck`](https://crates.io/crates/quickcheck) | [`quickcheck::Arbitrary`](https://docs.rs/quickcheck/latest/quickcheck/trait.Arbitrary.html) implementations for all `im` datatypes (not available in `im-rc`) |

//! [std::marker::Sync]: https://doc.rust-lang.org/std/marker/trait.Sync.html
//! [hashmap::HashMap]: ./hashmap/struct.HashMap.html
//! [hashset::HashSet]: ./hashset/struct.HashSet.html
//! [ordmap::OrdMap]: ./ordmap/struct.OrdMap.html
//! [ordset::OrdSet]: ./ordset/struct.OrdSet.html
//! [vector::Vector]: ./vector/enum.Vector.html
//! [hashmap::HashMap]: ./struct.HashMap.html
//! [hashset::HashSet]: ./struct.HashSet.html
//! [ordmap::OrdMap]: ./struct.OrdMap.html
//! [ordset::OrdSet]: ./struct.OrdSet.html
//! [vector::Vector]: ./struct.Vector.html
//! [vector::Vector::push_back]: ./vector/enum.Vector.html#method.push_back

@@ -387,5 +387,10 @@ //! [rrb-tree]: https://infoscience.epfl.ch/record/213452/files/rrbvector.pdf

#[cfg(not(feature = "pool"))]
#[cfg(any(threadsafe, not(feature = "pool")))]
mod fakepool;
#[cfg(all(threadsafe, feature = "pool"))]
compile_error!(
"The `pool` feature is not threadsafe but you've enabled it on a threadsafe version of `im`."
);
pub use crate::hashmap::HashMap;

@@ -392,0 +397,0 @@ pub use crate::hashset::HashSet;

+1
-1
src/nodes/btree.rs

@@ -1230,3 +1230,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public

/// A description of a difference between two ordered sets.
#[derive(PartialEq, Eq)]
#[derive(PartialEq, Eq, Debug)]
pub enum DiffItem<'a, A> {

@@ -1233,0 +1233,0 @@ /// This value has been added to the new set.

+19
-8
src/nodes/rrb.rs

@@ -38,3 +38,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public

Size::Size(s) => *s,
Size::Table(sizes) => sizes.iter().sum(),
Size::Table(sizes) => *sizes.last().unwrap_or(&0),
}

@@ -53,7 +53,8 @@ }

let mut remaining = size;
let child_size = NODE_SIZE.pow(level as u32);
while remaining > child_size {
let next_value = chunk.last().unwrap_or(&0) + child_size;
chunk.push_back(next_value);
remaining -= child_size;
if let Some(child_size) = NODE_SIZE.checked_pow(level as u32) {
while remaining > child_size {
let next_value = chunk.last().unwrap_or(&0) + child_size;
chunk.push_back(next_value);
remaining -= child_size;
}
}

@@ -400,3 +401,9 @@ if remaining > 0 {

// level 1, etc.
self.size() == NODE_SIZE.pow(level as u32 + 1)
if let Some(expected_size) = NODE_SIZE.checked_pow(level as u32 + 1) {
self.size() == expected_size
} else {
// We overflowed a usize, there's no way we can be completely dense as we know the size
// fits in a usize.
false
}
}

@@ -450,3 +457,7 @@

fn index_in(&self, level: usize, index: usize) -> Option<usize> {
let mut target_idx = index / NODE_SIZE.pow(level as u32);
let mut target_idx = if let Some(child_size) = NODE_SIZE.checked_pow(level as u32) {
index / child_size
} else {
0
};
if target_idx >= self.children.len() {

@@ -453,0 +464,0 @@ return None;

+144
-57
src/sort.rs

@@ -8,2 +8,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public

use std::cmp::Ordering;
use std::mem;

@@ -17,10 +18,9 @@ fn gen_range<R: RngCore>(rng: &mut R, min: usize, max: usize) -> usize {

// http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf
// Should be O(n) to O(n log n)
fn do_quicksort<A, F, R>(
vector: &mut FocusMut<'_, A>,
left: usize,
right: usize,
cmp: &F,
rng: &mut R,
) where
// There are a couple of modifications made here to make it more performant on the tree structure of
// the Vector. Instead of moving of handling equal and nonequal items in a single pass we make two
// additional passes to find the exact partition places. This allows us to split the focus into
// three correctly sized parts for less than, equal to and greater than items. As a bonus this
// doesn't need to reorder the equal items to the center of the vector.
fn do_quicksort<A, F, R>(vector: FocusMut<'_, A>, cmp: &F, rng: &mut R)
where
A: Clone,

@@ -30,63 +30,150 @@ F: Fn(&A, &A) -> Ordering,

{
if right <= left {
if vector.len() <= 1 {
return;
}
let l = left as isize;
let r = right as isize;
let p = gen_range(rng, left, right + 1) as isize;
let mut l1 = l;
let mut r1 = r;
let mut l2 = l - 1;
let mut r2 = r;
// We know there are at least 2 elements here
let pivot_index = gen_range(rng, 0, vector.len());
let (mut first, mut rest) = vector.split_at(1);
vector.swap(r as usize, p as usize);
loop {
while l1 != r && vector.pair(l1 as usize, r as usize, |a, b| cmp(a, b)) == Ordering::Less {
l1 += 1;
if pivot_index > 0 {
mem::swap(rest.index_mut(pivot_index - 1), first.index_mut(0));
}
// Pivot is now always in the first slice
let pivot_item = first.index(0);
// Find the exact place to put the pivot or pivot-equal items
let mut less_count = 0;
let mut equal_count = 0;
for index in 0..rest.len() {
let item = rest.index(index);
let comp = cmp(item, pivot_item);
match comp {
Ordering::Less => less_count += 1,
Ordering::Equal => equal_count += 1,
Ordering::Greater => {}
}
r1 -= 1;
while r1 != r && vector.pair(r as usize, r1 as usize, |a, b| cmp(a, b)) == Ordering::Less {
if r1 == l {
break;
}
r1 -= 1;
}
// If by accident we picked the minimum element as a pivot, we just call sort again with the
// rest of the vector.
if less_count == 0 {
do_quicksort(rest, cmp, rng);
return;
}
// We know here that there is at least one item before the pivot, so we move the minimum to the
// beginning part of the vector. First, however we swap the pivot to the start of the equal
// zone.
less_count -= 1;
equal_count += 1;
let first_item = first.index_mut(0);
mem::swap(first_item, rest.index_mut(less_count));
for index in 0..rest.len() {
if index == less_count {
// This is the position we swapped the pivot to. We can't move it from its position, and
// we know its not the minimum.
continue;
}
if l1 >= r1 {
break;
let rest_item = rest.index_mut(index);
if cmp(rest_item, first_item) == Ordering::Less {
mem::swap(first_item, rest_item);
}
vector.swap(l1 as usize, r1 as usize);
if l1 != r && vector.pair(l1 as usize, r as usize, |a, b| cmp(a, b)) == Ordering::Equal {
l2 += 1;
vector.swap(l2 as usize, l1 as usize);
}
// Split the vector up into less_than, equal to and greater than parts.
let (remaining, mut greater_focus) = rest.split_at(less_count + equal_count);
let (mut less_focus, mut equal_focus) = remaining.split_at(less_count);
let mut less_position = 0;
let mut equal_position = 0;
let mut greater_position = 0;
while less_position != less_focus.len() || greater_position != greater_focus.len() {
// At start of this loop, equal_position always points to an equal item
let mut equal_swap_side = None;
let equal_item = equal_focus.index(equal_position);
// Advance the less_position until we find an out of place item
while less_position != less_focus.len() {
let less_item = less_focus.index(less_position);
match cmp(less_item, equal_item) {
Ordering::Equal => {
equal_swap_side = Some(Ordering::Less);
break;
}
Ordering::Greater => {
break;
}
_ => {}
}
less_position += 1;
}
if r1 != r && vector.pair(r as usize, r1 as usize, |a, b| cmp(a, b)) == Ordering::Equal {
r2 -= 1;
vector.swap(r1 as usize, r2 as usize);
// Advance the greater until we find an out of place item
while greater_position != greater_focus.len() {
let greater_item = greater_focus.index(greater_position);
match cmp(greater_item, equal_item) {
Ordering::Less => break,
Ordering::Equal => {
equal_swap_side = Some(Ordering::Greater);
break;
}
_ => {}
}
greater_position += 1;
}
}
vector.swap(l1 as usize, r as usize);
r1 = l1 - 1;
l1 += 1;
let mut k = l;
while k < l2 {
vector.swap(k as usize, r1 as usize);
r1 -= 1;
k += 1;
if let Some(swap_side) = equal_swap_side {
// One of the sides is equal to the pivot, advance the pivot
let item = if swap_side == Ordering::Less {
less_focus.index_mut(less_position)
} else {
greater_focus.index_mut(greater_position)
};
// We are guaranteed not to hit the end of the equal focus
while cmp(item, equal_focus.index(equal_position)) == Ordering::Equal {
equal_position += 1;
}
// Swap the equal position and the desired side, it's important to note that only the
// equals focus is guaranteed to have made progress so we don't advance the side's index
mem::swap(item, equal_focus.index_mut(equal_position));
} else if less_position != less_focus.len() && greater_position != greater_focus.len() {
// Both sides are out of place and not equal to the pivot, this can only happen if there
// is a greater item in the lesser zone and a lesser item in the greater zone. The
// solution is to swap both sides and advance both side's indices.
debug_assert_ne!(
cmp(
less_focus.index(less_position),
equal_focus.index(equal_position)
),
Ordering::Equal
);
debug_assert_ne!(
cmp(
greater_focus.index(greater_position),
equal_focus.index(equal_position)
),
Ordering::Equal
);
mem::swap(
less_focus.index_mut(less_position),
greater_focus.index_mut(greater_position),
);
less_position += 1;
greater_position += 1;
}
}
k = r - 1;
while k > r2 {
vector.swap(l1 as usize, k as usize);
k -= 1;
l1 += 1;
}
if r1 >= 0 {
do_quicksort(vector, left, r1 as usize, cmp, rng);
// Now we have partitioned both sides correctly, we just have to recurse now
do_quicksort(less_focus, cmp, rng);
if !greater_focus.is_empty() {
do_quicksort(greater_focus, cmp, rng);
}
do_quicksort(vector, l1 as usize, right, cmp, rng);
}
pub(crate) fn quicksort<A, F>(vector: &mut FocusMut<'_, A>, left: usize, right: usize, cmp: &F)
pub(crate) fn quicksort<A, F>(vector: FocusMut<'_, A>, cmp: &F)
where

@@ -97,3 +184,3 @@ A: Clone,

let mut rng = rand_xoshiro::Xoshiro256Plus::seed_from_u64(0);
do_quicksort(vector, left, right, cmp, &mut rng);
do_quicksort(vector, cmp, &mut rng);
}

@@ -111,7 +198,7 @@

#[test]
fn test_quicksort(ref input in vector(i32::ANY, 0..1000)) {
fn test_quicksort(ref input in vector(i32::ANY, 0..10000)) {
let mut vec = input.clone();
let len = vec.len();
if len > 1 {
quicksort(&mut vec.focus_mut(), 0, len - 1, &Ord::cmp);
quicksort(vec.focus_mut(), &Ord::cmp);
}

@@ -118,0 +205,0 @@ assert!(is_sorted(vec));

+14
-1
src/tests/vector.rs

@@ -96,3 +96,3 @@ #![allow(clippy::unit_arg)]

let index = cap_index(expected.len(), *index);
expected.split_off(index);
expected.truncate(index);
writeln!(out, "vec.split_off({:?});", index)?

@@ -221,1 +221,14 @@ }

}
#[test]
fn test_inserts() {
const N: usize = 2000;
let mut v = Vector::new();
for i in 0..N {
v.insert(v.len() / 2, i);
}
let mut rv: Vec<usize> = Vec::new();
rv.extend((0..N).skip(1).step_by(2));
rv.extend((0..N).step_by(2).rev());
assert_eq!(Vector::from_iter(rv.iter().cloned()), v);
}
+3
-9
src/util.rs

@@ -17,11 +17,5 @@ // This Source Code Form is subject to the terms of the Mozilla Public

// `Arc` without refpool
#[cfg(all(threadsafe, not(feature = "pool")))]
#[cfg(all(threadsafe))]
pub(crate) use crate::fakepool::{Arc as PoolRef, Pool, PoolClone, PoolDefault};
// `Arc` with refpool
#[cfg(all(threadsafe, feature = "pool"))]
pub(crate) type PoolRef<A> = refpool::PoolRef<A, refpool::PoolSync>;
#[cfg(all(threadsafe, feature = "pool"))]
pub(crate) type Pool<A> = refpool::Pool<A, refpool::PoolSync>;
// `Ref` == `Arc` when threadsafe

@@ -37,5 +31,5 @@ #[cfg(threadsafe)]

#[cfg(all(not(threadsafe), feature = "pool"))]
pub(crate) type PoolRef<A> = refpool::PoolRef<A, refpool::PoolUnsync>;
pub(crate) type PoolRef<A> = refpool::PoolRef<A>;
#[cfg(all(not(threadsafe), feature = "pool"))]
pub(crate) type Pool<A> = refpool::Pool<A, refpool::PoolUnsync>;
pub(crate) type Pool<A> = refpool::Pool<A>;

@@ -42,0 +36,0 @@ // `Ref` == `Rc` when not threadsafe

Cargo.toml.orig

Sorry, the diff of this file is not supported yet

src/hash/map.rs

Sorry, the diff of this file is too big to display

src/ord/map.rs

Sorry, the diff of this file is too big to display

src/vector/mod.rs

Sorry, the diff of this file is too big to display