Snap for 8254899 from 98e40769d39769b0f1a9103bc60bf79d0e6deaf2 to tm-release
Change-Id: Ie8bfe89f717f2505cdbd68ddb107028cd6046b7b
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 6f8967e..bace32e 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,5 @@
{
"git": {
- "sha1": "80489689035c908f1096c07a8a0c51250f3dc979"
+ "sha1": "c4ac207b8f266ff3becd123f693f07536b97d088"
}
}
diff --git a/.github/dependabot.yml b/.github/dependabot.yml
new file mode 100644
index 0000000..cf039be
--- /dev/null
+++ b/.github/dependabot.yml
@@ -0,0 +1,8 @@
+version: 2
+updates:
+- package-ecosystem: cargo
+ directory: "/"
+ schedule:
+ interval: daily
+ time: "11:00"
+ open-pull-requests-limit: 10
diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml
new file mode 100644
index 0000000..df81fe8
--- /dev/null
+++ b/.github/workflows/ci.yml
@@ -0,0 +1,71 @@
+on: [push, pull_request]
+
+name: CI
+
+jobs:
+ check:
+ name: Check
+ runs-on: ubuntu-latest
+ strategy:
+ matrix:
+ rust:
+ - stable
+ - 1.46.0
+ features:
+ - --features=std
+ - --no-default-features --features=alloc,ahash
+ steps:
+ - uses: actions/checkout@v2
+ - uses: actions-rs/toolchain@v1
+ with:
+ profile: minimal
+ toolchain: ${{ matrix.rust }}
+ override: true
+ - uses: actions-rs/cargo@v1
+ with:
+ command: check
+ args: --all-targets ${{ matrix.features }}
+
+ test:
+ name: Test Suite
+ runs-on: ubuntu-latest
+ strategy:
+ matrix:
+ rust:
+ - stable
+ - 1.46.0
+ features:
+ - --features=std
+ - --no-default-features --features=alloc,ahash
+ steps:
+ - uses: actions/checkout@v2
+ - uses: actions-rs/toolchain@v1
+ with:
+ profile: minimal
+ toolchain: ${{ matrix.rust }}
+ override: true
+ - uses: actions-rs/cargo@v1
+ with:
+ command: test
+ args: ${{ matrix.features }}
+
+ clippy:
+ name: Clippy
+ runs-on: ubuntu-latest
+ strategy:
+ matrix:
+ rust:
+ - stable
+ - 1.46.0
+ steps:
+ - uses: actions/checkout@v2
+ - uses: actions-rs/toolchain@v1
+ with:
+ profile: minimal
+ toolchain: ${{ matrix.rust }}
+ override: true
+ - run: rustup component add clippy
+ - uses: actions-rs/cargo@v1
+ with:
+ command: clippy
+ args: -- -D warnings
diff --git a/.travis.yml b/.travis.yml
deleted file mode 100644
index 563df5b..0000000
--- a/.travis.yml
+++ /dev/null
@@ -1,23 +0,0 @@
-language: rust
-rust:
- - stable
- - beta
- - nightly
-# Oldest supported version:
- - 1.32.0
-
-dist: trusty
-sudo: false
-
-matrix:
- allow_failures:
- - rust: nightly
-
-notifications:
- email:
- on_success: never
-
-addons:
- apt:
- packages:
- - texinfo
diff --git a/Android.bp b/Android.bp
index c5216d4..2ff1215 100644
--- a/Android.bp
+++ b/Android.bp
@@ -23,7 +23,11 @@
host_supported: true,
crate_name: "weak_table",
cargo_env_compat: true,
- cargo_pkg_version: "0.3.0",
+ cargo_pkg_version: "0.3.2",
srcs: ["src/lib.rs"],
edition: "2018",
+ features: [
+ "default",
+ "std",
+ ],
}
diff --git a/CHANGELOG.md b/CHANGELOG.md
new file mode 100644
index 0000000..68c526e
--- /dev/null
+++ b/CHANGELOG.md
@@ -0,0 +1,89 @@
+# Changelog
+
+All notable changes to this project will be documented in this file.
+
+The format is based on [Keep a Changelog] and this project adheres to
+[Semantic Versioning].
+
+[Keep a Changelog]: http://keepachangelog.com/en/1.0.0/
+[Semantic Versioning]: http://semver.org/spec/v2.0.0.html
+
+## [Next Release]
+
+## [0.3.2] - 2021-12-01
+
+## [0.3.1] - 2021-11-30
+
+### Added
+- `no_std` compatibility (h/t @tsao-chi)
+
+## [0.2.4] - 2020-06-27
+
+### Fixed
+- Bad bucket selection on collision (h/t Andrew Browne
+ `<dersaidin@dersaidin.net>`).
+
+## [0.2.3] - 2018-05-30
+
+### Fixed
+- Use `Rc::ptr_eq` to compare `Rc`s by address.
+
+## [0.2.2] - 2018-05-22
+
+### Fixed
+- Weak–weak submap operations were missing a line of code.
+
+### Added
+- `{PtrWeakHashSet,PtrWeakKeyHashMap}::is_empty()` methods.
+
+## [0.2.1] - 2018-05-22
+
+### Fixed
+- documentation
+- a test that was breaking on an older `rustc`
+
+## [0.2.0] - 2018-05-22
+
+### Renamed
+- from `WeakElement::expired` to `WeakElement::is_expired`
+
+### Improved
+- documentation
+
+## [0.1.3] - 2018-05-22
+
+### Added
+- documentation of minimum supported `rustc`
+- a test
+
+## [0.1.2] - 2018-05-21
+
+### Added
+- `WeakKeyHashMap::{get_key, get_both, get_both_mut}` methods
+- `WeakWeakHashMap::{get_key, get_both}` methods
+- `WeakHashSet::get` method
+
+### Changed
+- Values stored behind `Rc`s can now be `?Sized`.
+
+### Removed
+- `struct RcKey<K>`
+
+### Improved
+- documentation
+
+## [0.1.1] - 2018-03-05
+
+Initial release.
+
+[Next Release]: <https://github.com/tov/weak-table-rs/compare/v0.3.2...HEAD>
+[0.3.2]: <https://github.com/tov/weak-table-rs/compare/v0.3.1...v0.3.2>
+[0.3.1]: <https://github.com/tov/weak-table-rs/compare/v0.3.1-alpha.0...v0.3.1>
+[0.2.4]: <https://github.com/tov/weak-table-rs/compare/0.2.3...0.2.4>
+[0.2.3]: <https://github.com/tov/weak-table-rs/compare/0.2.2...0.2.3>
+[0.2.2]: <https://github.com/tov/weak-table-rs/compare/0.2.1...0.2.2>
+[0.2.1]: <https://github.com/tov/weak-table-rs/compare/0.2.0...0.2.1>
+[0.2.0]: <https://github.com/tov/weak-table-rs/compare/0.1.3...0.2.0>
+[0.1.3]: <https://github.com/tov/weak-table-rs/compare/0.1.2...0.1.3>
+[0.1.2]: <https://github.com/tov/weak-table-rs/compare/0.1.1...0.1.2>
+[0.1.1]: <https://github.com/tov/weak-table-rs/tree/0.1.1>
diff --git a/Cargo.toml b/Cargo.toml
index 343cfab..b2e6cc8 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -3,27 +3,33 @@
# When uploading crates to the registry Cargo will automatically
# "normalize" Cargo.toml files for maximal compatibility
# with all versions of Cargo and also rewrite `path` dependencies
-# to registry (e.g., crates.io) dependencies
+# to registry (e.g., crates.io) dependencies.
#
-# If you believe there's an error in this file please file an
-# issue against the rust-lang/cargo repository. If you're
-# editing this file be aware that the upstream Cargo.toml
-# will likely look very different (and much more reasonable)
+# If you are reading this file be aware that the original Cargo.toml
+# will likely look very different (and much more reasonable).
+# See Cargo.toml.orig for the original contents.
[package]
edition = "2018"
name = "weak-table"
-version = "0.3.0"
+version = "0.3.2"
authors = ["Jesse A. Tov <jesse.tov@gmail.com>"]
description = "Weak hash maps and sets"
readme = "README.md"
-keywords = ["containers", "Rc", "Arc", "weak"]
+keywords = ["containers", "Rc", "Arc", "weak", "no_std"]
license = "MIT"
repository = "https://github.com/tov/weak-table-rs"
-
-[dependencies]
+[dependencies.ahash]
+version = "0.7.6"
+features = []
+optional = true
[dev-dependencies.quickcheck]
-version = "0.9"
+version = "1"
[dev-dependencies.rand]
-version = "0.7.2"
+version = "0.8.4"
+
+[features]
+alloc = []
+default = ["std"]
+std = []
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index 7cb87e3..3594791 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,17 +1,24 @@
[package]
name = "weak-table"
-version = "0.3.0"
+version = "0.3.2"
authors = ["Jesse A. Tov <jesse.tov@gmail.com>"]
description = "Weak hash maps and sets"
repository = "https://github.com/tov/weak-table-rs"
readme = "README.md"
license = "MIT"
-keywords = ["containers", "Rc", "Arc", "weak"]
+keywords = ["containers", "Rc", "Arc", "weak", "no_std"]
edition = "2018"
[dependencies]
+ahash = { version = "0.7.6", optional = true, features = [] }
[dev-dependencies]
-quickcheck = "0.9"
-rand = "0.7.2"
+quickcheck = "1"
+rand = "0.8.4"
+[features]
+default = ["std"]
+std = []
+
+# This feature doesn’t actually do anything. TODO: remove in v0.4.
+alloc = []
diff --git a/METADATA b/METADATA
index 29097c3..3317bcc 100644
--- a/METADATA
+++ b/METADATA
@@ -1,7 +1,5 @@
name: "weak-table"
-description:
- "Weak hash maps and sets"
-
+description: "Weak hash maps and sets"
third_party {
url {
type: HOMEPAGE
@@ -9,9 +7,13 @@
}
url {
type: ARCHIVE
- value: "https://static.crates.io/crates/weak-table/weak-table-0.3.0.crate"
+ value: "https://static.crates.io/crates/weak-table/weak-table-0.3.2.crate"
}
- version: "0.3.0"
- last_upgrade_date { year: 2020 month: 10 day: 9 }
+ version: "0.3.2"
license_type: NOTICE
+ last_upgrade_date {
+ year: 2022
+ month: 3
+ day: 1
+ }
}
diff --git a/README.md b/README.md
index 56fa462..9d4ac80 100644
--- a/README.md
+++ b/README.md
@@ -1,13 +1,25 @@
# weak-table: weak hash maps and sets for Rust
-[](https://travis-ci.org/tov/weak-table-rs)
+[](https://github.com/tov/weak-table-rs/actions)
[](https://crates.io/crates/weak-table)
[](LICENSE-MIT)
This crate defines several kinds of weak hash maps and sets. See
the [full API documentation](http://docs.rs/weak-table/) for details.
-This crate supports Rust version 1.32 and later.
+### Rust version support
+
+This crate supports Rust version 1.46 and later.
+
+### Crate features
+
+`weak-table` is built with the `std` feature, which enables
+functionality dependent on the `std` library, enabled by default.
+Optionally, the following dependency may be enabled:
+
+ - `ahash`: use `ahash`’s hasher rather than the `std` hasher
+
+If the `std` feature is disabled (for no_std) then the `ahash` dependency **must** be enabled.
### Examples
diff --git a/release.toml b/release.toml
index 5d7a460..03d6f0d 100644
--- a/release.toml
+++ b/release.toml
@@ -1,3 +1,17 @@
-pre-release-replacements = [
- { file="src/lib.rs", search="https://docs[.]rs/weak-table/[0-9.]*", replace="https://docs.rs/weak-table/{{version}}" }
-]
+tag-name = "v{{version}}"
+
+[[pre-release-replacements]]
+file = "src/lib.rs"
+search = "https://docs[.]rs/weak-table/[0-9.]*"
+replace = "https://docs.rs/weak-table/{{version}}"
+
+[[pre-release-replacements]]
+file = "CHANGELOG.md"
+search = "## \\[Next Release\\]"
+replace = "## [Next Release]\n\n## [{{version}}] - {{date}}"
+
+[[pre-release-replacements]]
+file = "CHANGELOG.md"
+search = "\\[Next Release\\]: <https://github.com/tov/weak-table-rs/compare/v*[0-9.]*[.][.][.]HEAD>"
+replace = '''[Next Release]: <https://github.com/tov/weak-table-rs/compare/v{{version}}...HEAD>
+[{{version}}]: <https://github.com/tov/weak-table-rs/compare/v{{prev_version}}...v{{version}}>'''
diff --git a/src/by_ptr.rs b/src/by_ptr.rs
index b541f9e..7dc4c77 100644
--- a/src/by_ptr.rs
+++ b/src/by_ptr.rs
@@ -1,4 +1,4 @@
-use std::ops::Deref;
+use crate::compat::*;
use super::traits::*;
diff --git a/src/compat.rs b/src/compat.rs
new file mode 100644
index 0000000..4644b17
--- /dev/null
+++ b/src/compat.rs
@@ -0,0 +1,56 @@
+//! `no_std` compatibility
+
+// If we depend on `ahash`, use its hasher.
+#[cfg(feature = "ahash")]
+pub use ahash::RandomState;
+
+// Use the `std` hasher if we don’t depend on `ahash` but do depend on
+// `std`.
+#[cfg(all(not(feature = "ahash"), feature = "std"))]
+pub use std::collections::hash_map::RandomState;
+
+// If we depend on neither `ahash` nor `std` then it’s an error.
+#[cfg(not(any(feature = "ahash", feature = "std")))]
+compile_error!("weak-table: no_std requires that you enable the `ahash` feature.");
+
+// If we depend on `std`, alias `lib` to `std`.
+#[cfg(feature = "std")]
+mod lib {
+ extern crate std;
+ pub use std::*;
+}
+
+// Otherwise, we are `no_std`, so alias `lib` to `alloc`.
+#[cfg(not(feature = "std"))]
+mod lib {
+ extern crate alloc;
+ pub use alloc::*;
+}
+
+// Stuff from `std`/`alloc` that we use often.
+pub use lib::{
+ boxed::Box,
+ rc,
+ slice,
+ string::String,
+ sync,
+ vec::{self, Vec},
+};
+
+// Stuff from `core` that we use often:
+pub use core::{
+ borrow::Borrow,
+ cmp::max,
+ hash::{BuildHasher, Hash, Hasher},
+ iter::{self, FromIterator},
+ fmt::{self, Debug, Formatter},
+ mem,
+ ops::{self, Deref, Index, IndexMut},
+};
+
+// When testing, we need the `eprintln` macro from `std`:
+#[cfg(test)]
+extern crate std;
+
+#[cfg(test)]
+pub use std::eprintln;
diff --git a/src/lib.rs b/src/lib.rs
index ce5e596..6851e7b 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,4 +1,3 @@
-#![doc(html_root_url = "https://docs.rs/weak-table/0.3.0")]
//! This library offers a variety of weak hash tables:
//!
//! - For a hash map where the keys are held by weak pointers and compared by key value, see
@@ -27,7 +26,32 @@
//! To add support for your own weak pointers, see
//! [the traits `WeakElement` and `WeakKey`](traits/).
//!
-//! This crate supports Rust version 1.32 and later.
+//! ## Rust version support
+//!
+//! This crate supports Rust version 1.46 and later.
+//!
+//! ## Asymptotic complexity
+//!
+//! Most operations have documented asymptotic time complexities. When time complexities are
+//! given in big-*O* notation, the following parameters are used consistently:
+//!
+//! - *n*: the *capacity* of the map or set being accessed or constructed
+//!
+//! - *m*: the *capacity* of a second map/set involved in a submap/subset operation
+//!
+//! - *p*: the length of the probe sequence for the key in question
+//!
+//! Note that *p* ∈ *O*(*n*), but we expect it to be *O*(1).
+//!
+//! # Crate features
+//!
+//! `weak-table` is built with the `std` feature, which enables
+//! functionality dependent on the `std` library, enabled by default.
+//! Optionally, the following dependency may be enabled:
+//!
+//! - `ahash`: use `ahash`’s hasher rather than the `std` hasher
+//!
+//! If the `std` feature is disabled (for no_std) then the `ahash` dependency **must** be enabled.
//!
//! # Examples
//!
@@ -117,7 +141,11 @@
//! }
//! ```
-use std::collections::hash_map::RandomState;
+#![doc(html_root_url = "https://docs.rs/weak-table/0.3.2")]
+
+#![cfg_attr(not(feature = "std"), no_std)]
+
+use self::compat::*;
pub mod traits;
pub mod weak_key_hash_map;
@@ -128,6 +156,7 @@
pub mod weak_hash_set;
pub mod ptr_weak_hash_set;
+mod compat;
mod util;
mod by_ptr;
mod size_policy;
diff --git a/src/ptr_weak_hash_set.rs b/src/ptr_weak_hash_set.rs
index 9a38b4e..9f6cb71 100644
--- a/src/ptr_weak_hash_set.rs
+++ b/src/ptr_weak_hash_set.rs
@@ -1,10 +1,6 @@
//! A hash set where the elements are held by weak pointers and compared by pointer.
-use std::collections::hash_map::RandomState;
-use std::fmt::{self, Debug};
-use std::hash::BuildHasher;
-use std::iter::FromIterator;
-use std::ops::Deref;
+use crate::compat::*;
use super::traits::*;
use super::ptr_weak_key_hash_map as base;
@@ -16,11 +12,15 @@
where T::Strong: Deref
{
/// Creates an empty `PtrWeakHashSet`.
+ ///
+ /// *O*(1) time
pub fn new() -> Self {
PtrWeakHashSet(base::PtrWeakKeyHashMap::new())
}
/// Creates an empty `PtrWeakHashSet` with the given capacity.
+ ///
+ /// *O*(*n*) time
pub fn with_capacity(capacity: usize) -> Self {
PtrWeakHashSet(base::PtrWeakKeyHashMap::with_capacity(capacity))
}
@@ -30,41 +30,57 @@
where T::Strong: Deref
{
/// Creates an empty `PtrWeakHashSet` with the given capacity and hasher.
+ ///
+ /// *O*(*n*) time
pub fn with_hasher(hash_builder: S) -> Self {
PtrWeakHashSet(base::PtrWeakKeyHashMap::with_hasher(hash_builder))
}
/// Creates an empty `PtrWeakHashSet` with the given capacity and hasher.
+ ///
+ /// *O*(*n*) time
pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
PtrWeakHashSet(base::PtrWeakKeyHashMap::with_capacity_and_hasher(capacity, hash_builder))
}
/// Returns a reference to the map's `BuildHasher`.
+ ///
+ /// *O*(1) time
pub fn hasher(&self) -> &S {
self.0.hasher()
}
/// Returns the number of elements the map can hold without reallocating.
+ ///
+ /// *O*(1) time
pub fn capacity(&self) -> usize {
self.0.capacity()
}
/// Removes all mappings whose keys have expired.
+ ///
+ /// *O*(*n*) time
pub fn remove_expired(&mut self) {
self.0.remove_expired()
}
/// Reserves room for additional elements.
+ ///
+ /// *O*(*n*) time
pub fn reserve(&mut self, additional_capacity: usize) {
self.0.reserve(additional_capacity)
}
/// Shrinks the capacity to the minimum allowed to hold the current number of elements.
+ ///
+ /// *O*(*n*) time
pub fn shrink_to_fit(&mut self) {
self.0.shrink_to_fit()
}
/// Returns an over-approximation of the number of elements.
+ ///
+ /// *O*(1) time
pub fn len(&self) -> usize {
self.0.len()
}
@@ -73,6 +89,8 @@
///
/// This could answer `false` for an empty set whose elements have
/// expired but have yet to be collected.
+ ///
+ /// *O*(1) time
pub fn is_empty(&self) -> bool {
self.len() == 0
}
@@ -81,27 +99,37 @@
/// The proportion of buckets that are used.
///
/// This is an over-approximation because of expired elements.
+ ///
+ /// *O*(1) time
pub fn load_factor(&self) -> f32 {
self.0.load_factor()
}
/// Removes all associations from the map.
+ ///
+ /// *O*(*n*) time
pub fn clear(&mut self) {
self.0.clear()
}
/// Returns true if the map contains the specified key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn contains(&self, key: &T::Strong) -> bool {
self.0.contains_key(key)
}
/// Unconditionally inserts the value, returning the old value if already present. Does not
/// replace the key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn insert(&mut self, key: T::Strong) -> bool {
self.0.insert(key, ()).is_some()
}
/// Removes the entry with the given key, if it exists, and returns the value.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn remove(&mut self, key: &T::Strong) -> bool {
self.0.remove(key).is_some()
}
@@ -109,6 +137,8 @@
/// Removes all mappings not satisfying the given predicate.
///
/// Also removes any expired mappings.
+ ///
+ /// *O*(*n*) time
pub fn retain<F>(&mut self, mut f: F)
where F: FnMut(T::Strong) -> bool
{
@@ -116,6 +146,10 @@
}
/// Is self a subset of other?
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn is_subset<S1>(&self, other: &PtrWeakHashSet<T, S1>) -> bool
where S1: BuildHasher
{
@@ -172,11 +206,15 @@
where T::Strong: Deref
{
/// Gets an iterator over the keys and values.
+ ///
+ /// *O*(1) time
pub fn iter(&self) -> Iter<T> {
Iter(self.0.keys())
}
/// Gets a draining iterator, which removes all the values but retains the storage.
+ ///
+ /// *O*(1) time (and *O*(*n*) time to dispose of the result)
pub fn drain(&mut self) -> Drain<T> {
Drain(self.0.drain())
}
@@ -239,6 +277,9 @@
type Item = T::Strong;
type IntoIter = IntoIter<T>;
+ /// Creates an owning iterator from `self`.
+ ///
+ /// *O*(1) time (and *O*(*n*) time to dispose of the result)
fn into_iter(self) -> Self::IntoIter {
IntoIter(self.0.into_iter())
}
@@ -250,6 +291,9 @@
type Item = T::Strong;
type IntoIter = Iter<'a, T>;
+ /// Creates a borrowing iterator from `self`.
+ ///
+ /// *O*(1) time
fn into_iter(self) -> Self::IntoIter {
Iter(self.0.keys())
}
diff --git a/src/ptr_weak_key_hash_map.rs b/src/ptr_weak_key_hash_map.rs
index cd48809..2cd5591 100644
--- a/src/ptr_weak_key_hash_map.rs
+++ b/src/ptr_weak_key_hash_map.rs
@@ -1,10 +1,6 @@
//! A hash map where the keys are held by weak pointers and compared by pointer.
-use std::collections::hash_map::RandomState;
-use std::fmt::{self, Debug};
-use std::hash::BuildHasher;
-use std::iter::FromIterator;
-use std::ops::{Deref, Index, IndexMut};
+use crate::compat::*;
use super::by_ptr::*;
use super::traits::*;
@@ -17,11 +13,15 @@
where K::Strong: Deref
{
/// Creates an empty `PtrWeakKeyHashMap`.
+ ///
+ /// *O*(1) time
pub fn new() -> Self {
PtrWeakKeyHashMap(base::WeakKeyHashMap::new())
}
/// Creates an empty `PtrWeakKeyHashMap` with the given capacity.
+ ///
+ /// *O*(*n*) time
pub fn with_capacity(capacity: usize) -> Self {
PtrWeakKeyHashMap(base::WeakKeyHashMap::with_capacity(capacity))
}
@@ -31,41 +31,57 @@
where K::Strong: Deref
{
/// Creates an empty `PtrWeakKeyHashMap` with the given capacity and hasher.
+ ///
+ /// *O*(*n*) time
pub fn with_hasher(hash_builder: S) -> Self {
PtrWeakKeyHashMap(base::WeakKeyHashMap::with_hasher(hash_builder))
}
/// Creates an empty `PtrWeakKeyHashMap` with the given capacity and hasher.
+ ///
+ /// *O*(*n*) time
pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
PtrWeakKeyHashMap(base::WeakKeyHashMap::with_capacity_and_hasher(capacity, hash_builder))
}
/// Returns a reference to the map's `BuildHasher`.
+ ///
+ /// *O*(1) time
pub fn hasher(&self) -> &S {
self.0.hasher()
}
/// Returns the number of elements the map can hold without reallocating.
+ ///
+ /// *O*(1) time
pub fn capacity(&self) -> usize {
self.0.capacity()
}
/// Removes all mappings whose keys have expired.
+ ///
+ /// *O*(*n*) time
pub fn remove_expired(&mut self) {
self.0.remove_expired()
}
/// Reserves room for additional elements.
+ ///
+ /// *O*(*n*) time
pub fn reserve(&mut self, additional_capacity: usize) {
self.0.reserve(additional_capacity)
}
/// Shrinks the capacity to the minimum allowed to hold the current number of elements.
+ ///
+ /// *O*(*n*) time
pub fn shrink_to_fit(&mut self) {
self.0.shrink_to_fit()
}
/// Returns an over-approximation of the number of elements.
+ ///
+ /// *O*(1) time
pub fn len(&self) -> usize {
self.0.len()
}
@@ -74,6 +90,8 @@
///
/// This could answer `false` for an empty map whose keys have
/// expired but have yet to be collected.
+ ///
+ /// *O*(1) time
pub fn is_empty(&self) -> bool {
self.len() == 0
}
@@ -81,42 +99,58 @@
/// The proportion of buckets that are used.
///
/// This is an over-approximation because of expired keys.
+ ///
+ /// *O*(1) time
pub fn load_factor(&self) -> f32 {
self.0.load_factor()
}
/// Gets the requested entry.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn entry(&mut self, key: K::Strong) -> Entry<ByPtr<K>, V> {
self.0.entry(key)
}
/// Removes all associations from the map.
+ ///
+ /// *O*(*n*) time
pub fn clear(&mut self) {
self.0.clear()
}
/// Returns a reference to the value corresponding to the key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn get(&self, key: &K::Strong) -> Option<&V> {
self.0.get(&(key.deref() as *const _))
}
/// Returns true if the map contains the specified key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn contains_key(&self, key:&K::Strong) -> bool {
self.0.contains_key(&(key.deref() as *const _))
}
/// Returns a mutable reference to the value corresponding to the key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn get_mut(&mut self, key: &K::Strong) -> Option<&mut V> {
self.0.get_mut(&(key.deref() as *const _))
}
/// Unconditionally inserts the value, returning the old value if already present. Does not
/// replace the key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn insert(&mut self, key: K::Strong, value: V) -> Option<V> {
self.0.insert(key, value)
}
/// Removes the entry with the given key, if it exists, and returns the value.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn remove(&mut self, key: &K::Strong) -> Option<V> {
self.0.remove(&(key.deref() as *const _))
}
@@ -124,6 +158,8 @@
/// Removes all mappings not satisfying the given predicate.
///
/// Also removes any expired mappings.
+ ///
+ /// *O*(*n*) time
pub fn retain<F>(&mut self, f: F)
where F: FnMut(K::Strong, &mut V) -> bool
{
@@ -134,6 +170,10 @@
///
/// In particular, all the keys of self must be in other and the values must compare true with
/// value_equal.
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn submap_with<F, S1, V1>(&self, other: &PtrWeakKeyHashMap<K, V1, S1>, value_equal: F) -> bool
where F: FnMut(&V, &V1) -> bool,
S1: BuildHasher
@@ -142,6 +182,10 @@
}
/// Is self a submap of other?
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn is_submap<V1, S1>(&self, other: &PtrWeakKeyHashMap<K, V1, S1>) -> bool
where V: PartialEq<V1>,
S1: BuildHasher
@@ -150,6 +194,10 @@
}
/// Are the keys of self a subset of the keys of other?
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn domain_is_subset<V1, S1>(&self, other: &PtrWeakKeyHashMap<K, V1, S1>) -> bool
where S1: BuildHasher
{
@@ -161,31 +209,43 @@
where K::Strong: Deref
{
/// Gets an iterator over the keys and values.
+ ///
+ /// *O*(1) time
pub fn iter(&self) -> Iter<ByPtr<K>, V> {
self.0.iter()
}
/// Gets an iterator over the keys.
+ ///
+ /// *O*(1) time
pub fn keys(&self) -> Keys<ByPtr<K>, V> {
self.0.keys()
}
/// Gets an iterator over the values.
+ ///
+ /// *O*(1) time
pub fn values(&self) -> Values<ByPtr<K>, V> {
self.0.values()
}
/// Gets an iterator over the keys and mutable values.
+ ///
+ /// *O*(1) time
pub fn iter_mut(&mut self) -> IterMut<ByPtr<K>, V> {
self.0.iter_mut()
}
/// Gets an iterator over the mutable values.
+ ///
+ /// *O*(1) time
pub fn values_mut(&mut self) -> ValuesMut<ByPtr<K>, V> {
self.0.values_mut()
}
/// Gets a draining iterator, which removes all the values but retains the storage.
+ ///
+ /// *O*(1) time (and *O*(*n*) time to dispose of the result)
pub fn drain(&mut self) -> Drain<ByPtr<K>, V> {
self.0.drain()
}
@@ -283,6 +343,9 @@
type Item = (K::Strong, V);
type IntoIter = IntoIter<ByPtr<K>, V>;
+ /// Creates an owning iterator from `self`.
+ ///
+ /// *O*(1) time (and *O*(*n*) time to dispose of the result)
fn into_iter(self) -> Self::IntoIter {
self.0.into_iter()
}
@@ -292,6 +355,9 @@
type Item = (K::Strong, &'a V);
type IntoIter = Iter<'a, ByPtr<K>, V>;
+ /// Creates a borrowing iterator from `self`.
+ ///
+ /// *O*(1) time
fn into_iter(self) -> Self::IntoIter {
(&self.0).into_iter()
}
@@ -301,17 +367,22 @@
type Item = (K::Strong, &'a mut V);
type IntoIter = IterMut<'a, ByPtr<K>, V>;
+ /// Creates a borrowing iterator from `self`.
+ ///
+ /// *O*(1) time
fn into_iter(self) -> Self::IntoIter {
(&mut self.0).into_iter()
}
}
#[cfg(test)]
-mod test
-{
- use crate::PtrWeakKeyHashMap;
- use crate::weak_key_hash_map::Entry;
- use std::rc::{Rc, Weak};
+mod test {
+ use crate::compat::{
+ eprintln,
+ rc::{Rc, Weak},
+ Vec,
+ };
+ use super::{Entry, PtrWeakKeyHashMap};
// fn show_me(weakmap: &PtrWeakKeyHashMap<Weak<u32>, f32>) {
// for (key, _) in weakmap {
diff --git a/src/ptr_weak_weak_hash_map.rs b/src/ptr_weak_weak_hash_map.rs
index e842cd2..fb49ae7 100644
--- a/src/ptr_weak_weak_hash_map.rs
+++ b/src/ptr_weak_weak_hash_map.rs
@@ -1,11 +1,7 @@
//! A hash map where the keys and values are both held by weak pointers, and keys are compared by
//! pointer.
-use std::collections::hash_map::RandomState;
-use std::fmt::{self, Debug};
-use std::hash::BuildHasher;
-use std::iter::FromIterator;
-use std::ops::Deref;
+use crate::compat::*;
use super::by_ptr::*;
use super::traits::*;
@@ -18,11 +14,15 @@
where K::Strong: Deref
{
/// Creates an empty `PtrWeakWeakHashMap`.
+ ///
+ /// *O*(1) time
pub fn new() -> Self {
PtrWeakWeakHashMap(base::WeakWeakHashMap::new())
}
/// Creates an empty `PtrWeakWeakHashMap` with the given capacity.
+ ///
+ /// *O*(*n*) time
pub fn with_capacity(capacity: usize) -> Self {
PtrWeakWeakHashMap(base::WeakWeakHashMap::with_capacity(capacity))
}
@@ -32,41 +32,57 @@
where K::Strong: Deref
{
/// Creates an empty `PtrWeakWeakHashMap` with the given capacity and hasher.
+ ///
+ /// *O*(*n*) time
pub fn with_hasher(hash_builder: S) -> Self {
PtrWeakWeakHashMap(base::WeakWeakHashMap::with_hasher(hash_builder))
}
/// Creates an empty `PtrWeakWeakHashMap` with the given capacity and hasher.
+ ///
+ /// *O*(*n*) time
pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
PtrWeakWeakHashMap(base::WeakWeakHashMap::with_capacity_and_hasher(capacity, hash_builder))
}
/// Returns a reference to the map's `BuildHasher`.
+ ///
+ /// *O*(1) time
pub fn hasher(&self) -> &S {
self.0.hasher()
}
/// Returns the number of elements the map can hold without reallocating.
+ ///
+ /// *O*(1) time
pub fn capacity(&self) -> usize {
self.0.capacity()
}
/// Removes all mappings whose keys have expired.
+ ///
+ /// *O*(*n*) time
pub fn remove_expired(&mut self) {
self.0.remove_expired()
}
/// Reserves room for additional elements.
+ ///
+ /// *O*(*n*) time
pub fn reserve(&mut self, additional_capacity: usize) {
self.0.reserve(additional_capacity)
}
/// Shrinks the capacity to the minimum allowed to hold the current number of elements.
+ ///
+ /// *O*(*n*) time
pub fn shrink_to_fit(&mut self) {
self.0.shrink_to_fit()
}
/// Returns an over-approximation of the number of elements.
+ ///
+ /// *O*(1) time
pub fn len(&self) -> usize {
self.0.len()
}
@@ -75,6 +91,8 @@
///
/// Note that this may return false even if all keys in the map have
/// expired, if they haven't been collected yet.
+ ///
+ /// *O*(1) time
pub fn is_empty(&self) -> bool {
self.0.is_empty()
}
@@ -82,37 +100,51 @@
/// The proportion of buckets that are used.
///
/// This is an over-approximation because of expired keys.
+ ///
+ /// *O*(1) time
pub fn load_factor(&self) -> f32 {
self.0.load_factor()
}
/// Gets the requested entry.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn entry(&mut self, key: K::Strong) -> Entry<ByPtr<K>, V> {
self.0.entry(key)
}
/// Removes all associations from the map.
+ ///
+ /// *O*(*n*) time
pub fn clear(&mut self) {
self.0.clear()
}
/// Returns a reference to the value corresponding to the key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn get(&self, key: &K::Strong) -> Option<V::Strong> {
self.0.get(&(key.deref() as *const _))
}
/// Returns true if the map contains the specified key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn contains_key(&self, key: &K::Strong) -> bool {
self.0.contains_key(&(key.deref() as *const _))
}
/// Unconditionally inserts the value, returning the old value if already present. Does not
/// replace the key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn insert(&mut self, key: K::Strong, value: V::Strong) -> Option<V::Strong> {
self.0.insert(key, value)
}
/// Removes the entry with the given key, if it exists, and returns the value.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn remove(&mut self, key: &K::Strong) -> Option<V::Strong> {
self.0.remove(&(key.deref() as *const _))
}
@@ -120,6 +152,8 @@
/// Removes all mappings not satisfying the given predicate.
///
/// Also removes any expired mappings.
+ ///
+ /// *O*(*n*) time
pub fn retain<F>(&mut self, f: F)
where F: FnMut(K::Strong, V::Strong) -> bool
{
@@ -130,6 +164,10 @@
///
/// In particular, all the keys of self must be in other and the values must compare true with
/// value_equal.
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn submap_with<F, S1, V1>(&self, other: &PtrWeakWeakHashMap<K, V1, S1>, value_equal: F) -> bool
where F: FnMut(V::Strong, V1::Strong) -> bool,
V1: WeakElement,
@@ -139,6 +177,10 @@
}
/// Is self a submap of other?
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn is_submap<V1, S1>(&self, other: &PtrWeakWeakHashMap<K, V1, S1>) -> bool
where V1: WeakElement,
V::Strong: PartialEq<V1::Strong>,
@@ -148,6 +190,10 @@
}
/// Are the keys of self a subset of the keys of other?
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn domain_is_subset<V1, S1>(&self, other: &PtrWeakWeakHashMap<K, V1, S1>) -> bool
where V1: WeakElement,
S1: BuildHasher
@@ -160,21 +206,29 @@
where K::Strong: Deref
{
/// Gets an iterator over the keys and values.
+ ///
+ /// *O*(1) time
pub fn iter(&self) -> Iter<ByPtr<K>, V> {
self.0.iter()
}
/// Gets an iterator over the keys.
+ ///
+ /// *O*(1) time
pub fn keys(&self) -> Keys<ByPtr<K>, V> {
self.0.keys()
}
/// Gets an iterator over the values.
+ ///
+ /// *O*(1) time
pub fn values(&self) -> Values<ByPtr<K>, V> {
self.0.values()
}
/// Gets a draining iterator, which removes all the values but retains the storage.
+ ///
+ /// *O*(1) time (and *O*(*n*) time to dispose of the result)
pub fn drain(&mut self) -> Drain<ByPtr<K>, V> {
self.0.drain()
}
@@ -245,6 +299,9 @@
type Item = (K::Strong, V::Strong);
type IntoIter = IntoIter<ByPtr<K>, V>;
+ /// Creates an owning iterator from `self`.
+ ///
+ /// *O*(1) time (and *O*(*n*) time to dispose of the result)
fn into_iter(self) -> Self::IntoIter {
self.0.into_iter()
}
@@ -254,17 +311,22 @@
type Item = (K::Strong, V::Strong);
type IntoIter = Iter<'a, ByPtr<K>, V>;
+ /// Creates a borrowing iterator from `self`.
+ ///
+ /// *O*(1) time
fn into_iter(self) -> Self::IntoIter {
(&self.0).into_iter()
}
}
#[cfg(test)]
-mod test
-{
- use crate::PtrWeakWeakHashMap;
- use crate::weak_weak_hash_map::Entry;
- use std::rc::{Rc, Weak};
+mod test {
+ use crate::compat::{
+ eprintln,
+ rc::{Rc, Weak},
+ Vec,
+ };
+ use super::{Entry, PtrWeakWeakHashMap};
// fn show_me(weakmap: &PtrWeakWeakHashMap<Weak<u32>, Weak<f32>>) {
// for (key, _) in weakmap {
diff --git a/src/traits.rs b/src/traits.rs
index 440a6c9..878e5a3 100644
--- a/src/traits.rs
+++ b/src/traits.rs
@@ -7,8 +7,7 @@
//! as a weak element, you need to implement `WeakElement` for your weak pointer type; to use it
//! as a weak key, implement `WeakKey` as well.
-use std::hash::Hash;
-use std::{rc, sync};
+use crate::compat::*;
/// Interface for elements that can be stored in weak hash tables.
///
@@ -70,6 +69,19 @@
/// strong pointer.
fn with_key<F, R>(view: &Self::Strong, f: F) -> R
where F: FnOnce(&Self::Key) -> R;
+
+ /// Hashes the key `view` into the given `Hasher`.
+ fn hash<H: Hasher>(view: &Self::Strong, h: &mut H) {
+ Self::with_key(view, |k| k.hash(h));
+ }
+
+ /// Returns whether the key `view` equals the given `key`.
+ fn equals<Q>(view: &Self::Strong, key: &Q) -> bool
+ where Q: ?Sized + Eq,
+ Self::Key: Borrow<Q>
+ {
+ Self::with_key(view, |k| k.borrow() == key)
+ }
}
impl<T: ?Sized> WeakElement for rc::Weak<T> {
@@ -94,7 +106,7 @@
fn with_key<F, R>(view: &Self::Strong, f: F) -> R
where F: FnOnce(&Self::Key) -> R
{
- f(&view)
+ f(view)
}
}
@@ -121,7 +133,7 @@
fn with_key<F, R>(view: &Self::Strong, f: F) -> R
where F: FnOnce(&Self::Key) -> R
{
- f(&view)
+ f(view)
}
}
diff --git a/src/util.rs b/src/util.rs
index 3792ec7..9affd7f 100644
--- a/src/util.rs
+++ b/src/util.rs
@@ -1,3 +1,5 @@
+use crate::compat::*;
+
pub fn new_boxed_option_slice<T>(size: usize) -> Box<[Option<T>]> {
let mut vector = Vec::with_capacity(size);
for _ in 0 .. size {
diff --git a/src/weak_hash_set.rs b/src/weak_hash_set.rs
index a3bc151..bbff3b8 100644
--- a/src/weak_hash_set.rs
+++ b/src/weak_hash_set.rs
@@ -1,10 +1,6 @@
//! A hash set where the elements are held by weak pointers and compared by value.
-use std::borrow::Borrow;
-use std::collections::hash_map::RandomState;
-use std::fmt::{self, Debug};
-use std::hash::{BuildHasher, Hash};
-use std::iter::FromIterator;
+use crate::compat::*;
use super::traits::*;
use super::weak_key_hash_map as base;
@@ -13,11 +9,15 @@
impl <T: WeakKey> WeakHashSet<T, RandomState> {
/// Creates an empty `WeakHashSet`.
+ ///
+ /// *O*(1) time
pub fn new() -> Self {
WeakHashSet(base::WeakKeyHashMap::new())
}
/// Creates an empty `WeakHashSet` with the given capacity.
+ ///
+ /// *O*(*n*) time
pub fn with_capacity(capacity: usize) -> Self {
WeakHashSet(base::WeakKeyHashMap::with_capacity(capacity))
}
@@ -25,41 +25,57 @@
impl <T: WeakKey, S: BuildHasher> WeakHashSet<T, S> {
/// Creates an empty `WeakHashSet` with the given capacity and hasher.
+ ///
+ /// *O*(*n*) time
pub fn with_hasher(hash_builder: S) -> Self {
WeakHashSet(base::WeakKeyHashMap::with_hasher(hash_builder))
}
/// Creates an empty `WeakHashSet` with the given capacity and hasher.
+ ///
+ /// *O*(*n*) time
pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
WeakHashSet(base::WeakKeyHashMap::with_capacity_and_hasher(capacity, hash_builder))
}
/// Returns a reference to the map's `BuildHasher`.
+ ///
+ /// *O*(1) time
pub fn hasher(&self) -> &S {
self.0.hasher()
}
/// Returns the number of elements the map can hold without reallocating.
+ ///
+ /// *O*(1) time
pub fn capacity(&self) -> usize {
self.0.capacity()
}
/// Removes all mappings whose keys have expired.
+ ///
+ /// *O*(*n*) time
pub fn remove_expired(&mut self) {
self.0.remove_expired()
}
/// Reserves room for additional elements.
+ ///
+ /// *O*(*n*) time
pub fn reserve(&mut self, additional_capacity: usize) {
self.0.reserve(additional_capacity)
}
/// Shrinks the capacity to the minimum allowed to hold the current number of elements.
+ ///
+ /// *O*(*n*) time
pub fn shrink_to_fit(&mut self) {
self.0.shrink_to_fit()
}
/// Returns an over-approximation of the number of elements.
+ ///
+ /// *O*(1) time
pub fn len(&self) -> usize {
self.0.len()
}
@@ -68,6 +84,8 @@
///
/// Note that this may return false even if all keys in the set have
/// expired, if they haven't been collected yet.
+ ///
+ /// *O*(1) time
pub fn is_empty(&self) -> bool {
self.0.is_empty()
}
@@ -75,11 +93,15 @@
/// The proportion of buckets that are used.
///
/// This is an over-approximation because of expired elements.
+ ///
+ /// *O*(1) time
pub fn load_factor(&self) -> f32 {
self.0.load_factor()
}
/// Removes all associations from the map.
+ ///
+ /// *O*(*n*) time
pub fn clear(&mut self) {
self.0.clear()
}
@@ -87,6 +109,8 @@
// Non-ptr WeakHashSet should probably have `get` method.
/// Returns true if the map contains the specified key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn contains<Q>(&self, key: &Q) -> bool
where Q: ?Sized + Eq + Hash,
T::Key: Borrow<Q>
@@ -112,6 +136,8 @@
///
/// assert!(Rc::ptr_eq( &a, &also_a ));
/// ```
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn get<Q>(&self, key: &Q) -> Option<T::Strong>
where Q: ?Sized + Eq + Hash,
T::Key: Borrow<Q>
@@ -121,11 +147,15 @@
/// Unconditionally inserts the value, returning the old value if already present. Does not
/// replace the key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn insert(&mut self, key: T::Strong) -> bool {
self.0.insert(key, ()).is_some()
}
/// Removes the entry with the given key, if it exists, and returns the value.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn remove<Q>(&mut self, key: &Q) -> bool
where Q: ?Sized + Eq + Hash,
T::Key: Borrow<Q>
@@ -136,6 +166,8 @@
/// Removes all mappings not satisfying the given predicate.
///
/// Also removes any expired mappings.
+ ///
+ /// *O*(*n*) time
pub fn retain<F>(&mut self, mut f: F)
where F: FnMut(T::Strong) -> bool
{
@@ -143,6 +175,10 @@
}
/// Is self a subset of other?
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn is_subset<S1>(&self, other: &WeakHashSet<T, S1>) -> bool
where S1: BuildHasher
{
@@ -197,11 +233,15 @@
impl<T: WeakKey, S> WeakHashSet<T, S> {
/// Gets an iterator over the keys and values.
+ ///
+ /// *O*(1) time
pub fn iter(&self) -> Iter<T> {
Iter(self.0.keys())
}
/// Gets a draining iterator, which removes all the values but retains the storage.
+ ///
+ /// *O*(1) time (and *O*(*n*) time to dispose of the result)
pub fn drain(&mut self) -> Drain<T> {
Drain(self.0.drain())
}
@@ -255,6 +295,9 @@
type Item = T::Strong;
type IntoIter = IntoIter<T>;
+ /// Creates an owning iterator from `self`.
+ ///
+ /// *O*(1) time (and *O*(*n*) time to dispose of the result)
fn into_iter(self) -> Self::IntoIter {
IntoIter(self.0.into_iter())
}
@@ -264,6 +307,9 @@
type Item = T::Strong;
type IntoIter = Iter<'a, T>;
+ /// Creates a borrowing iterator from `self`.
+ ///
+ /// *O*(1) time
fn into_iter(self) -> Self::IntoIter {
Iter(self.0.keys())
}
diff --git a/src/weak_key_hash_map.rs b/src/weak_key_hash_map.rs
index 91bee2a..7dcb8c4 100644
--- a/src/weak_key_hash_map.rs
+++ b/src/weak_key_hash_map.rs
@@ -1,12 +1,5 @@
//! A hash map where the keys are held by weak pointers and compared by key value.
-use std::borrow::Borrow;
-use std::cmp::max;
-use std::collections::hash_map::RandomState;
-use std::hash::{BuildHasher, Hash, Hasher};
-use std::fmt::{self, Debug, Formatter};
-use std::mem;
-
use super::*;
use super::size_policy::*;
use super::traits::*;
@@ -36,7 +29,7 @@
/// An iterator over the keys and values of the weak hash map.
#[derive(Clone, Debug)]
pub struct Iter<'a, K: 'a, V: 'a> {
- base: ::std::slice::Iter<'a, Bucket<K, V>>,
+ base: slice::Iter<'a, Bucket<K, V>>,
size: usize,
}
@@ -44,7 +37,7 @@
type Item = (K::Strong, &'a V);
fn next(&mut self) -> Option<Self::Item> {
- while let Some(bucket) = self.base.next() {
+ for bucket in &mut self.base {
if let Some((ref weak_ptr, ref value, _)) = *bucket {
self.size -= 1;
if let Some(strong_ptr) = weak_ptr.view() {
@@ -64,7 +57,7 @@
#[derive(Debug)]
/// An iterator over the keys and mutable values of the weak hash map.
pub struct IterMut<'a, K: 'a, V: 'a> {
- base: ::std::slice::IterMut<'a, Bucket<K, V>>,
+ base: slice::IterMut<'a, Bucket<K, V>>,
size: usize,
}
@@ -72,7 +65,7 @@
type Item = (K::Strong, &'a mut V);
fn next(&mut self) -> Option<Self::Item> {
- while let Some(bucket) = self.base.next() {
+ for bucket in &mut self.base {
if let Some((ref weak_ptr, ref mut value, _)) = *bucket {
self.size -= 1;
if let Some(strong_ptr) = weak_ptr.view() {
@@ -140,7 +133,7 @@
#[derive(Debug)]
/// An iterator that consumes the values of a weak hash map, leaving it empty.
pub struct Drain<'a, K: 'a, V: 'a> {
- base: ::std::slice::IterMut<'a, Bucket<K, V>>,
+ base: slice::IterMut<'a, Bucket<K, V>>,
size: usize,
}
@@ -148,7 +141,7 @@
type Item = (K::Strong, V);
fn next(&mut self) -> Option<Self::Item> {
- while let Some(bucket) = self.base.next() {
+ for bucket in &mut self.base {
if let Some((weak_ptr, value, _)) = bucket.take() {
self.size -= 1;
if let Some(strong_ptr) = weak_ptr.view() {
@@ -167,7 +160,7 @@
impl<'a, K, V> Drop for Drain<'a, K, V> {
fn drop(&mut self) {
- while let Some(option) = self.base.next() {
+ for option in &mut self.base {
*option = None;
}
}
@@ -175,7 +168,7 @@
/// An iterator that consumes the values of a weak hash map, leaving it empty.
pub struct IntoIter<K, V> {
- base: ::std::vec::IntoIter<Bucket<K, V>>,
+ base: vec::IntoIter<Bucket<K, V>>,
size: usize,
}
@@ -183,12 +176,10 @@
type Item = (K::Strong, V);
fn next(&mut self) -> Option<Self::Item> {
- while let Some(bucket) = self.base.next() {
- if let Some((weak_ptr, value, _)) = bucket {
- self.size -= 1;
- if let Some(strong_ptr) = weak_ptr.view() {
- return Some((strong_ptr, value));
- }
+ for (weak_ptr, value, _) in (&mut self.base).flatten() {
+ self.size -= 1;
+ if let Some(strong_ptr) = weak_ptr.view() {
+ return Some((strong_ptr, value));
}
}
@@ -203,11 +194,15 @@
impl<K: WeakKey, V> WeakKeyHashMap<K, V, RandomState>
{
/// Creates an empty `WeakKeyHashMap`.
+ ///
+ /// *O*(1) time
pub fn new() -> Self {
Self::with_capacity(DEFAULT_INITIAL_CAPACITY)
}
/// Creates an empty `WeakKeyHashMap` with the given capacity.
+ ///
+ /// *O*(*n*) time
pub fn with_capacity(capacity: usize) -> Self {
Self::with_capacity_and_hasher(capacity, Default::default())
}
@@ -216,11 +211,15 @@
impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
{
/// Creates an empty `WeakKeyHashMap` with the given capacity and hasher.
+ ///
+ /// *O*(*n*) time
pub fn with_hasher(hash_builder: S) -> Self {
Self::with_capacity_and_hasher(DEFAULT_INITIAL_CAPACITY, hash_builder)
}
/// Creates an empty `WeakKeyHashMap` with the given capacity and hasher.
+ ///
+ /// *O*(*n*) time
pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
WeakKeyHashMap {
hash_builder,
@@ -232,11 +231,15 @@
}
/// Returns a reference to the map's `BuildHasher`.
+ ///
+ /// *O*(1) time
pub fn hasher(&self) -> &S {
&self.hash_builder
}
/// Returns the number of elements the map can hold without reallocating.
+ ///
+ /// *O*(1) time
pub fn capacity(&self) -> usize {
self.inner.capacity()
}
@@ -259,17 +262,23 @@
}
/// Removes all mappings whose keys have expired.
+ ///
+ /// *O*(*n*) time
pub fn remove_expired(&mut self) {
self.retain(|_, _| true)
}
/// Reserves room for additional elements.
+ ///
+ /// *O*(*n*) time
pub fn reserve(&mut self, additional_capacity: usize) {
let new_capacity = additional_capacity + self.capacity();
self.resize(new_capacity);
}
/// Shrinks the capacity to the minimum allowed to hold the current number of elements.
+ ///
+ /// *O*(*n*) time
pub fn shrink_to_fit(&mut self) {
self.remove_expired();
let new_capacity = (self.len() as f32 / COLLECT_LOAD_FACTOR).ceil() as usize;
@@ -277,6 +286,8 @@
}
/// Returns an over-approximation of the number of elements.
+ ///
+ /// *O*(1) time
pub fn len(&self) -> usize {
self.inner.len
}
@@ -285,6 +296,8 @@
///
/// Note that this may return false even if all keys in the map have
/// expired, if they haven't been collected yet.
+ ///
+ /// *O*(1) time
pub fn is_empty(&self) -> bool {
self.len() == 0
}
@@ -292,6 +305,8 @@
/// The proportion of buckets that are used.
///
/// This is an over-approximation because of expired keys.
+ ///
+ /// *O*(1) time
pub fn load_factor(&self) -> f32 {
(self.len() as f32 + 1.0) / self.capacity() as f32
}
@@ -311,6 +326,8 @@
}
/// Gets the requested entry.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn entry(&mut self, key: K::Strong) -> Entry<K, V> {
self.maybe_adjust_size();
self.entry_no_grow(key)
@@ -318,7 +335,7 @@
fn entry_no_grow(&mut self, key: K::Strong) -> Entry<K, V> {
let mut inner = {
- let hash_code = K::with_key(&key, |k| self.hash(k));
+ let hash_code = self.hash(&key, K::hash);
InnerEntry {
pos: self.which_bucket(hash_code),
map: &mut self.inner,
@@ -347,6 +364,8 @@
}
/// Removes all associations from the map.
+ ///
+ /// *O*(*n*) time
pub fn clear(&mut self) {
self.drain();
}
@@ -357,14 +376,14 @@
{
if self.capacity() == 0 { return None; }
- let hash_code = self.hash(key);
+ let hash_code = self.hash(key, Q::hash);
let mut pos = self.which_bucket(hash_code);
for dist in 0 .. self.capacity() {
if let Some((ref weak_key, _, bucket_hash_code)) = self.inner.buckets[pos] {
if bucket_hash_code == hash_code {
if let Some(bucket_key) = weak_key.view() {
- if K::with_key(&bucket_key, |k| k.borrow() == key) {
+ if K::equals(&bucket_key, key) {
return Some((pos, bucket_key, bucket_hash_code));
}
}
@@ -386,6 +405,8 @@
}
/// Returns a reference to the value corresponding to the key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn get<Q>(&self, key: &Q) -> Option<&V>
where Q: ?Sized + Hash + Eq,
K::Key: Borrow<Q>
@@ -395,6 +416,8 @@
}
/// Returns true if the map contains the specified key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn contains_key<Q>(&self, key: &Q) -> bool
where Q: ?Sized + Hash + Eq,
K::Key: Borrow<Q>
@@ -403,6 +426,8 @@
}
/// Returns a strong reference to the key, if found.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn get_key<Q>(&self, key: &Q) -> Option<K::Strong>
where Q: ?Sized + Hash + Eq,
K::Key: Borrow<Q>
@@ -411,6 +436,8 @@
}
/// Returns a pair of a strong reference to the key, and a reference to the value, if present.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn get_both<Q>(&self, key: &Q) -> Option<(K::Strong, &V)>
where Q: ?Sized + Hash + Eq,
K::Key: Borrow<Q>
@@ -420,6 +447,8 @@
}
/// Returns a mutable reference to the value corresponding to the key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
where Q: ?Sized + Hash + Eq,
K::Key: Borrow<Q>
@@ -430,6 +459,8 @@
/// Returns a pair of a strong reference to the key, and a mutable reference to the value,
/// if present.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn get_both_mut<Q>(&mut self, key: &Q) -> Option<(K::Strong, &mut V)>
where Q: ?Sized + Hash + Eq,
K::Key: Borrow<Q>
@@ -441,6 +472,8 @@
/// Unconditionally inserts the value, returning the old value if already present.
///
/// Unlike `std::collections::HashMap`, this replaced the key even if occupied.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn insert(&mut self, key: K::Strong, value: V) -> Option<V> {
match self.entry(key) {
Entry::Occupied(mut occupied) => {
@@ -454,6 +487,8 @@
}
/// Removes the entry with the given key, if it exists, and returns the value.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
where Q: ?Sized + Hash + Eq,
K::Key: Borrow<Q>
@@ -471,6 +506,8 @@
/// Removes all mappings not satisfying the given predicate.
///
/// Also removes any expired mappings.
+ ///
+ /// *O*(*n*) time
pub fn retain<F>(&mut self, mut f: F)
where F: FnMut(K::Strong, &mut V) -> bool
{
@@ -490,18 +527,24 @@
}
}
- /// Is this map a submap of the other, using the given value comparison.
+ /// Is this map a submap of the other under the given value comparison `cmp`?
///
- /// In particular, all the keys of `self` must be in `other` and the values must compare
- /// `true` with `value_equal`.
+ /// In particular, for every key `k` of `self`,
+ ///
+ /// - `k` must also be a key of `other` and
+ /// - `cmp(self[k], other[k])` must hold.
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn is_submap_with<F, S1, V1>(&self, other: &WeakKeyHashMap<K, V1, S1>,
- mut value_equal: F) -> bool
+ mut cmp: F) -> bool
where F: FnMut(&V, &V1) -> bool,
S1: BuildHasher
{
for (key, value1) in self {
if let Some(value2) = K::with_key(&key, |k| other.get(k)) {
- if !value_equal(value1, value2) {
+ if !cmp(value1, value2) {
return false;
}
} else {
@@ -513,6 +556,10 @@
}
/// Is `self` a submap of `other`?
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn is_submap<V1, S1>(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool
where V: PartialEq<V1>,
S1: BuildHasher
@@ -521,18 +568,21 @@
}
/// Are the keys of `self` a subset of the keys of `other`?
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn domain_is_subset<V1, S1>(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool
where S1: BuildHasher
{
self.is_submap_with(other, |_, _| true)
}
- fn hash<Q>(&self, key: &Q) -> HashCode
- where Q: ?Sized + Hash,
- K::Key: Borrow<Q>
+ fn hash<Q, H>(&self, key: Q, hash: H) -> HashCode
+ where H: FnOnce(Q, &mut S::Hasher)
{
- let mut hasher = self.hash_builder.build_hasher();
- key.hash(&mut hasher);
+ let hasher = &mut self.hash_builder.build_hasher();
+ hash(key, hasher);
HashCode(hasher.finish())
}
}
@@ -556,7 +606,7 @@
}
}
-impl<'a, K, V, S, Q> ::std::ops::Index<&'a Q> for WeakKeyHashMap<K, V, S>
+impl<'a, K, V, S, Q> ops::Index<&'a Q> for WeakKeyHashMap<K, V, S>
where K: WeakKey,
K::Key: Borrow<Q>,
S: BuildHasher,
@@ -569,7 +619,7 @@
}
}
-impl<'a, K, V, S, Q> ::std::ops::IndexMut<&'a Q> for WeakKeyHashMap<K, V, S>
+impl<'a, K, V, S, Q> ops::IndexMut<&'a Q> for WeakKeyHashMap<K, V, S>
where K: WeakKey,
K::Key: Borrow<Q>,
S: BuildHasher,
@@ -580,7 +630,7 @@
}
}
-impl<K, V, S> ::std::iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
+impl<K, V, S> iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
where K: WeakKey,
S: BuildHasher + Default
{
@@ -591,7 +641,7 @@
}
}
-impl<K, V, S> ::std::iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
+impl<K, V, S> iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
where K: WeakKey,
S: BuildHasher
{
@@ -602,7 +652,7 @@
}
}
-impl<'a, K, V, S> ::std::iter::Extend<(&'a K::Strong, &'a V)> for WeakKeyHashMap<K, V, S>
+impl<'a, K, V, S> iter::Extend<(&'a K::Strong, &'a V)> for WeakKeyHashMap<K, V, S>
where K: 'a + WeakKey,
K::Strong: Clone,
V: 'a + Clone,
@@ -628,7 +678,7 @@
Some(bucket) => {
if bucket.2 == self.hash_code {
if let Some(key) = bucket.0.view() {
- if K::with_key(&self.key, |k1| K::with_key(&key, |k2| k1 == k2)) {
+ if K::with_key(&self.key, |k| K::equals(&key, k)) {
return BucketStatus::MatchesKey;
}
}
@@ -647,6 +697,8 @@
/// Ensures a value is in the entry by inserting a default value
/// if empty, and returns a mutable reference to the value in the
/// entry.
+ ///
+ /// *O*(1) time
pub fn or_insert(self, default: V) -> &'a mut V {
self.or_insert_with(|| default)
}
@@ -654,6 +706,8 @@
/// Ensures a value is in the entry by inserting the result of the
/// default function if empty, and returns a mutable reference to
/// the value in the entry.
+ ///
+ /// *O*(1) time
pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
match self {
Entry::Occupied(occupied) => occupied.into_mut(),
@@ -662,6 +716,8 @@
}
/// Returns a reference to this entry's key.
+ ///
+ /// *O*(1) time
pub fn key(&self) -> &K::Strong {
match *self {
Entry::Occupied(ref occupied) => occupied.key(),
@@ -672,11 +728,15 @@
impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> {
/// Gets a reference to the key held by the entry.
+ ///
+ /// *O*(1) time
pub fn key(&self) -> &K::Strong {
&self.0.key
}
/// Takes ownership of the key and value from the map.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn remove_entry(self) -> (K::Strong, V) {
let (_, value, _) = self.0.map.buckets[self.0.pos].take().unwrap();
self.0.map.remove_index(self.0.pos);
@@ -684,21 +744,29 @@
}
/// Gets a reference to the value in the entry.
+ ///
+ /// *O*(1) time
pub fn get(&self) -> &V {
&self.0.map.buckets[self.0.pos].as_ref().unwrap().1
}
/// Gets a mutable reference to the value in the entry.
+ ///
+ /// *O*(1) time
pub fn get_mut(&mut self) -> &mut V {
&mut self.0.map.buckets[self.0.pos].as_mut().unwrap().1
}
/// Turns the entry into a mutable reference to the value borrowed from the map.
+ ///
+ /// *O*(1) time
pub fn into_mut(self) -> &'a mut V {
&mut self.0.map.buckets[self.0.pos].as_mut().unwrap().1
}
/// Replaces the value in the entry with the given value.
+ ///
+ /// *O*(1) time
pub fn insert(&mut self, mut value: V) -> V {
self.0.map.buckets[self.0.pos].as_mut().unwrap().0 = K::new(&self.0.key);
mem::swap(self.get_mut(), &mut value);
@@ -706,6 +774,8 @@
}
/// Removes the entry, returning the value.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn remove(self) -> V {
self.remove_entry().1
}
@@ -714,17 +784,23 @@
impl<'a, K: WeakKey, V> VacantEntry<'a, K, V> {
/// Gets a reference to the key that would be used when inserting a
/// value through the `VacantEntry`.
+ ///
+ /// *O*(1) time
pub fn key(&self) -> &K::Strong {
&self.0.key
}
/// Returns ownership of the key.
+ ///
+ /// *O*(1) time
pub fn into_key(self) -> K::Strong {
self.0.key
}
/// Inserts the key and value into the map and return a mutable
/// reference to the value.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn insert(self, value: V) -> &'a mut V {
let old_bucket = mem::replace(
&mut self.0.map.buckets[self.0.pos],
@@ -934,6 +1010,9 @@
type Item = (K::Strong, V);
type IntoIter = IntoIter<K, V>;
+ /// Creates an owning iterator from `self`.
+ ///
+ /// *O*(1) time (and *O*(*n*) time to dispose of the result)
fn into_iter(self) -> Self::IntoIter {
IntoIter {
size: self.inner.len,
@@ -946,6 +1025,9 @@
type Item = (K::Strong, &'a V);
type IntoIter = Iter<'a, K, V>;
+ /// Creates a borrowing iterator from `self`.
+ ///
+ /// *O*(1) time
fn into_iter(self) -> Self::IntoIter {
Iter {
base: self.inner.buckets.iter(),
@@ -958,6 +1040,9 @@
type Item = (K::Strong, &'a mut V);
type IntoIter = IterMut<'a, K, V>;
+ /// Creates a borrowing iterator from `self`.
+ ///
+ /// *O*(1) time
fn into_iter(self) -> Self::IntoIter {
IterMut {
base: self.inner.buckets.iter_mut(),
@@ -968,31 +1053,43 @@
impl<K: WeakElement, V, S> WeakKeyHashMap<K, V, S> {
/// Gets an iterator over the keys and values.
+ ///
+ /// *O*(1) time
pub fn iter(&self) -> Iter<K, V> {
self.into_iter()
}
/// Gets an iterator over the keys.
+ ///
+ /// *O*(1) time
pub fn keys(&self) -> Keys<K, V> {
Keys(self.iter())
}
/// Gets an iterator over the values.
+ ///
+ /// *O*(1) time
pub fn values(&self) -> Values<K, V> {
Values(self.iter())
}
/// Gets an iterator over the keys and mutable values.
+ ///
+ /// *O*(1) time
pub fn iter_mut(&mut self) -> IterMut<K, V> {
self.into_iter()
}
/// Gets an iterator over the mutable values.
+ ///
+ /// *O*(1) time
pub fn values_mut(&mut self) -> ValuesMut<K, V> {
ValuesMut(self.iter_mut())
}
/// Gets a draining iterator, which removes all the values but retains the storage.
+ ///
+ /// *O*(1) time (and *O*(*n*) time to dispose of the result)
pub fn drain(&mut self) -> Drain<K, V> {
let old_len = self.inner.len;
self.inner.len = 0;
@@ -1004,8 +1101,13 @@
}
#[cfg(test)]
-mod tests {
- use std::rc::{Rc, Weak};
+mod test {
+ use crate::compat::{
+ eprintln,
+ rc::{Rc, Weak},
+ String,
+ Vec,
+ };
use super::{Entry, WeakKeyHashMap};
#[test]
@@ -1014,7 +1116,7 @@
assert_eq!( map.len(), 0 );
assert!( !map.contains_key("five") );
- let five: Rc<str> = Rc::from("five".to_string());
+ let five: Rc<str> = Rc::from(String::from("five"));
map.insert(five.clone(), 5);
assert_eq!( map.len(), 1 );
diff --git a/src/weak_value_hash_map.rs b/src/weak_value_hash_map.rs
index 8b60a17..7177e41 100644
--- a/src/weak_value_hash_map.rs
+++ b/src/weak_value_hash_map.rs
@@ -1,12 +1,5 @@
//! A hash map where the values are held by weak pointers.
-use std::borrow::Borrow;
-use std::cmp::max;
-use std::collections::hash_map::RandomState;
-use std::hash::{BuildHasher, Hash, Hasher};
-use std::fmt::{self, Debug, Formatter};
-use std::mem;
-
use super::*;
use super::size_policy::*;
use super::traits::*;
@@ -41,7 +34,7 @@
/// An iterator over the keys and values of the weak hash map.
#[derive(Clone, Debug)]
pub struct Iter<'a, K: 'a, V: 'a> {
- base: ::std::slice::Iter<'a, Bucket<K, V>>,
+ base: slice::Iter<'a, Bucket<K, V>>,
size: usize,
}
@@ -49,7 +42,7 @@
type Item = (&'a K, V::Strong);
fn next(&mut self) -> Option<Self::Item> {
- while let Some(bucket) = self.base.next() {
+ for bucket in &mut self.base {
if let Some((ref key, ref weak_value, _)) = *bucket {
self.size -= 1;
if let Some(value) = weak_value.view() {
@@ -101,7 +94,7 @@
#[derive(Debug)]
/// An iterator that consumes the values of a weak hash map, leaving it empty.
pub struct Drain<'a, K: 'a, V: 'a> {
- base: ::std::slice::IterMut<'a, Bucket<K, V>>,
+ base: slice::IterMut<'a, Bucket<K, V>>,
size: usize,
}
@@ -109,7 +102,7 @@
type Item = (K, V::Strong);
fn next(&mut self) -> Option<Self::Item> {
- while let Some(bucket) = self.base.next() {
+ for bucket in &mut self.base {
if let Some((key, weak_value, _)) = bucket.take() {
self.size -= 1;
if let Some(value) = weak_value.view() {
@@ -128,7 +121,7 @@
impl<'a, K, V> Drop for Drain<'a, K, V> {
fn drop(&mut self) {
- while let Some(option) = self.base.next() {
+ for option in &mut self.base {
*option = None;
}
}
@@ -136,7 +129,7 @@
/// An iterator that consumes the values of a weak hash map, leaving it empty.
pub struct IntoIter<K, V> {
- base: ::std::vec::IntoIter<Bucket<K, V>>,
+ base: vec::IntoIter<Bucket<K, V>>,
size: usize,
}
@@ -144,12 +137,10 @@
type Item = (K, V::Strong);
fn next(&mut self) -> Option<Self::Item> {
- while let Some(bucket) = self.base.next() {
- if let Some((key, weak_value, _)) = bucket {
- self.size -= 1;
- if let Some(value) = weak_value.view() {
- return Some((key, value));
- }
+ for (key, weak_value, _) in (&mut self.base).flatten() {
+ self.size -= 1;
+ if let Some(value) = weak_value.view() {
+ return Some((key, value));
}
}
@@ -164,11 +155,15 @@
impl<K: Eq + Hash, V: WeakElement> WeakValueHashMap<K, V, RandomState>
{
/// Creates an empty `WeakValueHashMap`.
+ ///
+ /// *O*(1) time
pub fn new() -> Self {
Self::with_capacity(DEFAULT_INITIAL_CAPACITY)
}
/// Creates an empty `WeakValueHashMap` with the given capacity.
+ ///
+ /// *O*(*n*) time
pub fn with_capacity(capacity: usize) -> Self {
Self::with_capacity_and_hasher(capacity, Default::default())
}
@@ -177,11 +172,15 @@
impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
{
/// Creates an empty `WeakValueHashMap` with the given capacity and hasher.
+ ///
+ /// *O*(*n*) time
pub fn with_hasher(hash_builder: S) -> Self {
Self::with_capacity_and_hasher(DEFAULT_INITIAL_CAPACITY, hash_builder)
}
/// Creates an empty `WeakValueHashMap` with the given capacity and hasher.
+ ///
+ /// *O*(*n*) time
pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
WeakValueHashMap {
hash_builder,
@@ -193,11 +192,15 @@
}
/// Returns a reference to the map's `BuildHasher`.
+ ///
+ /// *O*(1) time
pub fn hasher(&self) -> &S {
&self.hash_builder
}
/// Returns the number of elements the map can hold without reallocating.
+ ///
+ /// *O*(1) time
pub fn capacity(&self) -> usize {
self.inner.capacity()
}
@@ -220,17 +223,23 @@
}
/// Removes all mappings whose keys have expired.
+ ///
+ /// *O*(*n*) time
pub fn remove_expired(&mut self) {
self.retain(|_, _| true)
}
/// Reserves room for additional elements.
+ ///
+ /// *O*(*n*) time
pub fn reserve(&mut self, additional_capacity: usize) {
let new_capacity = additional_capacity + self.capacity();
self.resize(new_capacity);
}
/// Shrinks the capacity to the minimum allowed to hold the current number of elements.
+ ///
+ /// *O*(*n*) time
pub fn shrink_to_fit(&mut self) {
self.remove_expired();
let new_capacity = (self.len() as f32 / COLLECT_LOAD_FACTOR).ceil() as usize;
@@ -238,6 +247,8 @@
}
/// Returns an over-approximation of the number of elements.
+ ///
+ /// *O*(1) time
pub fn len(&self) -> usize {
self.inner.len
}
@@ -246,6 +257,8 @@
///
/// Note that this may return false even if all keys in the map have
/// expired, if they haven't been collected yet.
+ ///
+ /// *O*(1) time
pub fn is_empty(&self) -> bool {
self.len() == 0
}
@@ -253,6 +266,8 @@
/// The proportion of buckets that are used.
///
/// This is an over-approximation because of expired keys.
+ ///
+ /// *O*(1) time
pub fn load_factor(&self) -> f32 {
(self.len() as f32 + 1.0) / self.capacity() as f32
}
@@ -272,6 +287,8 @@
}
/// Gets the requested entry.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn entry(&mut self, key: K) -> Entry<K, V> {
self.maybe_adjust_size();
self.entry_no_grow(key)
@@ -309,6 +326,8 @@
}
/// Removes all associations from the map.
+ ///
+ /// *O*(*n*) time
pub fn clear(&mut self) {
self.drain();
}
@@ -348,6 +367,8 @@
}
/// Returns a reference to the value corresponding to the key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn get<Q>(&self, key: &Q) -> Option<V::Strong>
where Q: ?Sized + Hash + Eq,
K: Borrow<Q>
@@ -356,6 +377,8 @@
}
/// Returns true if the map contains the specified key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn contains_key<Q>(&self, key: &Q) -> bool
where Q: ?Sized + Hash + Eq,
K: Borrow<Q>
@@ -366,6 +389,8 @@
/// Unconditionally inserts the value, returning the old value if already present.
///
/// Like `std::collections::HashMap`, this does not replace the key if occupied.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn insert(&mut self, key: K, value: V::Strong) -> Option<V::Strong> {
match self.entry(key) {
Entry::Occupied(mut occupied) => {
@@ -379,6 +404,8 @@
}
/// Removes the entry with the given key, if it exists, and returns the value.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn remove<Q>(&mut self, key: &Q) -> Option<V::Strong>
where Q: ?Sized + Hash + Eq,
K: Borrow<Q>
@@ -394,6 +421,8 @@
/// Removes all mappings not satisfying the given predicate.
///
/// Also removes any expired mappings.
+ ///
+ /// *O*(*n*) time
pub fn retain<F>(&mut self, mut f: F)
where F: FnMut(&K, V::Strong) -> bool
{
@@ -417,6 +446,10 @@
///
/// In particular, all the keys of `self` must be in `other` and the values must compare
/// `true` with `value_equal`.
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn is_submap_with<F, S1, V1>(&self, other: &WeakValueHashMap<K, V1, S1>,
mut value_equal: F) -> bool
where V1: WeakElement,
@@ -437,6 +470,10 @@
}
/// Is `self` a submap of `other`?
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn is_submap<V1, S1>(&self, other: &WeakValueHashMap<K, V1, S1>) -> bool
where V1: WeakElement,
V::Strong: PartialEq<V1::Strong>,
@@ -446,6 +483,10 @@
}
/// Are the keys of `self` a subset of the keys of `other`?
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn domain_is_subset<V1, S1>(&self, other: &WeakValueHashMap<K, V1, S1>) -> bool
where V1: WeakElement,
S1: BuildHasher
@@ -486,7 +527,7 @@
}
}
-impl<K, V, S> ::std::iter::FromIterator<(K, V::Strong)> for WeakValueHashMap<K, V, S>
+impl<K, V, S> iter::FromIterator<(K, V::Strong)> for WeakValueHashMap<K, V, S>
where K: Eq + Hash,
V: WeakElement,
S: BuildHasher + Default
@@ -554,12 +595,16 @@
impl<'a, K, V: WeakElement> Entry<'a, K, V> {
/// Ensures a value is in the entry by inserting a default value
/// if empty.
+ ///
+ /// *O*(1) time
pub fn or_insert(self, default: V::Strong) -> V::Strong {
self.or_insert_with(|| default)
}
/// Ensures a value is in the entry by inserting the result of the
/// default function if empty.
+ ///
+ /// *O*(1) time
pub fn or_insert_with<F: FnOnce() -> V::Strong>(self, default: F) -> V::Strong {
match self {
Entry::Occupied(occupied) => occupied.get_strong(),
@@ -568,6 +613,8 @@
}
/// Returns a reference to this entry's key.
+ ///
+ /// *O*(1) time
pub fn key(&self) -> &K {
match *self {
Entry::Occupied(ref occupied) => occupied.key(),
@@ -578,11 +625,15 @@
impl<'a, K, V: WeakElement> OccupiedEntry<'a, K, V> {
/// Gets a reference to the key held by the entry.
+ ///
+ /// *O*(1) time
pub fn key(&self) -> &K {
&self.inner.key
}
/// Takes ownership of the key and value from the map.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn remove_entry(self) -> (K, V::Strong) {
let (key, w_value, _) = self.inner.map.buckets[self.inner.pos].take().unwrap();
let value = w_value.view().unwrap();
@@ -591,22 +642,30 @@
}
/// Gets a reference to the value in the entry.
+ ///
+ /// *O*(1) time
pub fn get(&self) -> &V::Strong {
&self.value
}
/// Gets a copy of the strong value reference stored in the entry.
+ ///
+ /// *O*(1) time
pub fn get_strong(&self) -> V::Strong {
V::clone(&self.value)
}
/// Replaces the value in the entry with the given value, returning the old value.
+ ///
+ /// *O*(1) time
pub fn insert(&mut self, value: V::Strong) -> V::Strong {
self.inner.map.buckets[self.inner.pos].as_mut().unwrap().1 = V::new(&value);
mem::replace(&mut self.value, value)
}
/// Removes the entry, returning the value.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn remove(self) -> V::Strong {
self.remove_entry().1
}
@@ -615,16 +674,22 @@
impl<'a, K, V: WeakElement> VacantEntry<'a, K, V> {
/// Gets a reference to the key that would be used when inserting a
/// value through the `VacantEntry`.
+ ///
+ /// *O*(1) time
pub fn key(&self) -> &K {
&self.inner.key
}
/// Returns ownership of the key.
+ ///
+ /// *O*(1) time
pub fn into_key(self) -> K {
self.inner.key
}
/// Inserts the value into the map, returning the same value.
+ ///
+ /// *O*(1) time
pub fn insert(self, value: V::Strong) -> V::Strong {
let InnerEntry { map, key, hash_code, pos } = self.inner;
@@ -836,6 +901,9 @@
type Item = (K, V::Strong);
type IntoIter = IntoIter<K, V>;
+ /// Creates an owning iterator from `self`.
+ ///
+ /// *O*(1) time (and *O*(*n*) time to dispose of the result)
fn into_iter(self) -> Self::IntoIter {
IntoIter {
size: self.inner.len,
@@ -848,6 +916,9 @@
type Item = (&'a K, V::Strong);
type IntoIter = Iter<'a, K, V>;
+ /// Creates a borrowing iterator from `self`.
+ ///
+ /// *O*(1) time
fn into_iter(self) -> Self::IntoIter {
Iter {
base: self.inner.buckets.iter(),
@@ -858,21 +929,29 @@
impl<K, V: WeakElement, S> WeakValueHashMap<K, V, S> {
/// Gets an iterator over the keys and values.
+ ///
+ /// *O*(1) time
pub fn iter(&self) -> Iter<K, V> {
self.into_iter()
}
/// Gets an iterator over the keys.
+ ///
+ /// *O*(1) time
pub fn keys(&self) -> Keys<K, V> {
Keys(self.iter())
}
/// Gets an iterator over the values.
+ ///
+ /// *O*(1) time
pub fn values(&self) -> Values<K, V> {
Values(self.iter())
}
/// Gets a draining iterator, which removes all the values but retains the storage.
+ ///
+ /// *O*(1) time (and *O*(*n*) time to dispose of the result)
pub fn drain(&mut self) -> Drain<K, V> {
let old_len = self.inner.len;
self.inner.len = 0;
diff --git a/src/weak_weak_hash_map.rs b/src/weak_weak_hash_map.rs
index 0ed89f6..801bc64 100644
--- a/src/weak_weak_hash_map.rs
+++ b/src/weak_weak_hash_map.rs
@@ -1,13 +1,6 @@
//! A hash map where the keys and values are both held by weak pointers, and keys are compared by
//! value.
-use std::borrow::Borrow;
-use std::cmp::max;
-use std::collections::hash_map::RandomState;
-use std::hash::{BuildHasher, Hash, Hasher};
-use std::fmt::{self, Debug, Formatter};
-use std::mem;
-
use super::*;
use super::size_policy::*;
use super::traits::*;
@@ -42,7 +35,7 @@
/// An iterator over the keys and values of the weak hash map.
#[derive(Clone, Debug)]
pub struct Iter<'a, K: 'a, V: 'a> {
- base: ::std::slice::Iter<'a, Bucket<K, V>>,
+ base: slice::Iter<'a, Bucket<K, V>>,
size: usize,
}
@@ -50,7 +43,7 @@
type Item = (K::Strong, V::Strong);
fn next(&mut self) -> Option<Self::Item> {
- while let Some(bucket) = self.base.next() {
+ for bucket in &mut self.base {
if let Some((ref weak_key, ref weak_value, _)) = *bucket {
self.size -= 1;
if let (Some(key), Some(value)) = (weak_key.view(), weak_value.view()) {
@@ -102,7 +95,7 @@
#[derive(Debug)]
/// An iterator that consumes the values of a weak hash map, leaving it empty.
pub struct Drain<'a, K: 'a, V: 'a> {
- base: ::std::slice::IterMut<'a, Bucket<K, V>>,
+ base: slice::IterMut<'a, Bucket<K, V>>,
size: usize,
}
@@ -110,7 +103,7 @@
type Item = (K::Strong, V::Strong);
fn next(&mut self) -> Option<Self::Item> {
- while let Some(bucket) = self.base.next() {
+ for bucket in &mut self.base {
if let Some((weak_key, weak_value, _)) = bucket.take() {
self.size -= 1;
if let (Some(key), Some(value)) = (weak_key.view(), weak_value.view()) {
@@ -129,7 +122,7 @@
impl<'a, K, V> Drop for Drain<'a, K, V> {
fn drop(&mut self) {
- while let Some(option) = self.base.next() {
+ for option in &mut self.base {
*option = None;
}
}
@@ -137,7 +130,7 @@
/// An iterator that consumes the values of a weak hash map, leaving it empty.
pub struct IntoIter<K, V> {
- base: ::std::vec::IntoIter<Bucket<K, V>>,
+ base: vec::IntoIter<Bucket<K, V>>,
size: usize,
}
@@ -145,12 +138,10 @@
type Item = (K::Strong, V::Strong);
fn next(&mut self) -> Option<Self::Item> {
- while let Some(bucket) = self.base.next() {
- if let Some((weak_key, weak_value, _)) = bucket {
- self.size -= 1;
- if let (Some(key), Some(value)) = (weak_key.view(), weak_value.view()) {
- return Some((key, value));
- }
+ for (weak_key, weak_value, _) in (&mut self.base).flatten() {
+ self.size -= 1;
+ if let (Some(key), Some(value)) = (weak_key.view(), weak_value.view()) {
+ return Some((key, value));
}
}
@@ -165,11 +156,15 @@
impl<K: WeakKey, V: WeakElement> WeakWeakHashMap<K, V, RandomState>
{
/// Creates an empty `WeakWeakHashMap`.
+ ///
+ /// *O*(1) time
pub fn new() -> Self {
Self::with_capacity(DEFAULT_INITIAL_CAPACITY)
}
/// Creates an empty `WeakWeakHashMap` with the given capacity.
+ ///
+ /// *O*(*n*) time
pub fn with_capacity(capacity: usize) -> Self {
Self::with_capacity_and_hasher(capacity, Default::default())
}
@@ -177,11 +172,15 @@
impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
/// Creates an empty `WeakWeakHashMap` with the given capacity and hasher.
+ ///
+ /// *O*(*n*) time
pub fn with_hasher(hash_builder: S) -> Self {
Self::with_capacity_and_hasher(DEFAULT_INITIAL_CAPACITY, hash_builder)
}
/// Creates an empty `WeakWeakHashMap` with the given capacity and hasher.
+ ///
+ /// *O*(*n*) time
pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
WeakWeakHashMap {
hash_builder,
@@ -193,11 +192,15 @@
}
/// Returns a reference to the map's `BuildHasher`.
+ ///
+ /// *O*(1) time
pub fn hasher(&self) -> &S {
&self.hash_builder
}
/// Returns the number of elements the map can hold without reallocating.
+ ///
+ /// *O*(1) time
pub fn capacity(&self) -> usize {
self.inner.capacity()
}
@@ -220,17 +223,23 @@
}
/// Removes all mappings whose keys have expired.
+ ///
+ /// *O*(*n*) time
pub fn remove_expired(&mut self) {
self.retain(|_, _| true)
}
/// Reserves room for additional elements.
+ ///
+ /// *O*(*n*) time
pub fn reserve(&mut self, additional_capacity: usize) {
let new_capacity = additional_capacity + self.capacity();
self.resize(new_capacity);
}
/// Shrinks the capacity to the minimum allowed to hold the current number of elements.
+ ///
+ /// *O*(*n*) time
pub fn shrink_to_fit(&mut self) {
self.remove_expired();
let new_capacity = (self.len() as f32 / COLLECT_LOAD_FACTOR).ceil() as usize;
@@ -238,6 +247,8 @@
}
/// Returns an over-approximation of the number of elements.
+ ///
+ /// *O*(1) time
pub fn len(&self) -> usize {
self.inner.len
}
@@ -246,6 +257,8 @@
///
/// Note that this may return false even if all keys in the map have
/// expired, if they haven't been collected yet.
+ ///
+ /// *O*(1) time
pub fn is_empty(&self) -> bool {
self.len() == 0
}
@@ -253,6 +266,8 @@
/// The proportion of buckets that are used.
///
/// This is an over-approximation because of expired keys.
+ ///
+ /// *O*(1) time
pub fn load_factor(&self) -> f32 {
(self.len() as f32 + 1.0) / self.capacity() as f32
}
@@ -272,6 +287,10 @@
}
/// Gets the requested entry.
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn entry(&mut self, key: K::Strong) -> Entry<K, V> {
self.maybe_adjust_size();
self.entry_no_grow(key)
@@ -279,7 +298,7 @@
fn entry_no_grow(&mut self, key: K::Strong) -> Entry<K, V> {
let mut inner = {
- let hash_code = K::with_key(&key, |k| self.hash(k));
+ let hash_code = self.hash(&key, K::hash);
InnerEntry {
pos: self.which_bucket(hash_code),
map: &mut self.inner,
@@ -308,6 +327,8 @@
}
/// Removes all associations from the map.
+ ///
+ /// *O*(*n*) time
pub fn clear(&mut self) {
self.drain();
}
@@ -318,14 +339,14 @@
{
if self.capacity() == 0 { return None; }
- let hash_code = self.hash(key);
+ let hash_code = self.hash(key, Q::hash);
let mut pos = self.which_bucket(hash_code);
for dist in 0 .. self.capacity() {
if let Some((ref w_key, ref w_value, b_hash_code)) = self.inner.buckets[pos] {
if b_hash_code == hash_code {
if let (Some(b_key), Some(b_value)) = (w_key.view(), w_value.view()) {
- if K::with_key(&b_key, |k| k.borrow() == key) {
+ if K::equals(&b_key, key) {
return Some((pos, b_key, b_value));
}
}
@@ -347,6 +368,8 @@
}
/// Returns a reference to the value corresponding to the key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn get<Q>(&self, key: &Q) -> Option<V::Strong>
where Q: ?Sized + Hash + Eq,
K::Key: Borrow<Q>
@@ -355,6 +378,8 @@
}
/// Returns the strong reference to the key, if present.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn get_key<Q>(&self, key: &Q) -> Option<K::Strong>
where Q: ?Sized + Hash + Eq,
K::Key: Borrow<Q>
@@ -363,6 +388,8 @@
}
/// Returns strong references to both the key and the value, if present.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn get_both<Q>(&self, key: &Q) -> Option<(K::Strong, V::Strong)>
where Q: ?Sized + Hash + Eq,
K::Key: Borrow<Q>
@@ -371,6 +398,8 @@
}
/// Returns true if the map contains the specified key.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn contains_key<Q>(&self, key: &Q) -> bool
where Q: ?Sized + Hash + Eq,
K::Key: Borrow<Q>
@@ -381,6 +410,8 @@
/// Unconditionally inserts the value, returning the old value if already present.
///
/// Unlike `std::collections::HashMap`, this replaces the key even if occupied.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn insert(&mut self, key: K::Strong, value: V::Strong) -> Option<V::Strong> {
match self.entry(key) {
Entry::Occupied(mut occupied) => {
@@ -394,6 +425,8 @@
}
/// Removes the entry with the given key, if it exists, and returns the value.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn remove<Q>(&mut self, key: &Q) -> Option<V::Strong>
where Q: ?Sized + Hash + Eq,
K::Key: Borrow<Q>
@@ -409,6 +442,8 @@
/// Removes all mappings not satisfying the given predicate.
///
/// Also removes any expired mappings.
+ ///
+ /// *O*(*n*) time
pub fn retain<F>(&mut self, mut f: F)
where F: FnMut(K::Strong, V::Strong) -> bool
{
@@ -432,6 +467,10 @@
///
/// In particular, all the keys of `self` must be in `other` and the values must compare
/// `true` with `value_equal`.
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn is_submap_with<F, S1, V1>(&self, other: &WeakWeakHashMap<K, V1, S1>,
mut value_equal: F) -> bool
where V1: WeakElement,
@@ -452,6 +491,10 @@
}
/// Is `self` a submap of `other`?
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn is_submap<V1, S1>(&self, other: &WeakWeakHashMap<K, V1, S1>) -> bool
where V1: WeakElement,
V::Strong: PartialEq<V1::Strong>,
@@ -461,6 +504,10 @@
}
/// Are the keys of `self` a subset of the keys of `other`?
+ ///
+ /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+ /// `self.capacity()` and *q* is the length of the probe sequences
+ /// in `other`)
pub fn domain_is_subset<V1, S1>(&self, other: &WeakWeakHashMap<K, V1, S1>) -> bool
where V1: WeakElement,
S1: BuildHasher
@@ -468,12 +515,11 @@
self.is_submap_with(other, |_, _| true)
}
- fn hash<Q>(&self, key: &Q) -> HashCode
- where Q: ?Sized + Hash,
- K::Key: Borrow<Q>
+ fn hash<Q, H>(&self, key: Q, hash: H) -> HashCode
+ where H: FnOnce(Q, &mut S::Hasher)
{
- let mut hasher = self.hash_builder.build_hasher();
- key.hash(&mut hasher);
+ let hasher = &mut self.hash_builder.build_hasher();
+ hash(key, hasher);
HashCode(hasher.finish())
}
}
@@ -501,7 +547,7 @@
}
}
-impl<K, V, S> ::std::iter::FromIterator<(K::Strong, V::Strong)> for WeakWeakHashMap<K, V, S>
+impl<K, V, S> iter::FromIterator<(K::Strong, V::Strong)> for WeakWeakHashMap<K, V, S>
where K: WeakKey,
V: WeakElement,
S: BuildHasher + Default
@@ -538,7 +584,7 @@
Some(bucket) => {
if bucket.2 == self.hash_code {
if let (Some(key), Some(value)) = (bucket.0.view(), bucket.1.view()) {
- if K::with_key(&self.key, |k1| K::with_key(&key, |k2| k1 == k2)) {
+ if K::with_key(&self.key, |k| K::equals(&key, k)) {
return BucketStatus::MatchesKey(value);
}
}
@@ -557,6 +603,8 @@
/// Ensures a value is in the entry by inserting a default value
/// if empty, and returns a mutable reference to the value in the
/// entry.
+ ///
+ /// *O*(1) time
pub fn or_insert(self, default: V::Strong) -> V::Strong {
self.or_insert_with(|| default)
}
@@ -564,6 +612,8 @@
/// Ensures a value is in the entry by inserting the result of the
/// default function if empty, and returns a mutable reference to
/// the value in the entry.
+ ///
+ /// *O*(1) time
pub fn or_insert_with<F: FnOnce() -> V::Strong>(self, default: F) -> V::Strong {
match self {
Entry::Occupied(occupied) => occupied.get_strong(),
@@ -572,6 +622,8 @@
}
/// Returns a reference to this entry's key.
+ ///
+ /// *O*(1) time
pub fn key(&self) -> &K::Strong {
match *self {
Entry::Occupied(ref occupied) => occupied.key(),
@@ -582,11 +634,15 @@
impl<'a, K: WeakKey, V: WeakElement> OccupiedEntry<'a, K, V> {
/// Gets a reference to the key held by the entry.
+ ///
+ /// *O*(1) time
pub fn key(&self) -> &K::Strong {
&self.inner.key
}
/// Takes ownership of the key and value from the map.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn remove_entry(self) -> (K::Strong, V::Strong) {
let (_, w_value, _) = self.inner.map.buckets[self.inner.pos].take().unwrap();
let value = w_value.view().unwrap();
@@ -595,22 +651,30 @@
}
/// Gets a reference to the value in the entry.
+ ///
+ /// *O*(1) time
pub fn get(&self) -> &V::Strong {
&self.value
}
/// Gets a clone of the reference to the value in the entry.
+ ///
+ /// *O*(1) time
pub fn get_strong(&self) -> V::Strong {
V::clone(&self.value)
}
/// Replaces the value in the entry with the given value.
+ ///
+ /// *O*(1) time
pub fn insert(&mut self, value: V::Strong) -> V::Strong {
self.inner.map.buckets[self.inner.pos].as_mut().unwrap().1 = V::new(&value);
mem::replace(&mut self.value, value)
}
/// Removes the entry, returning the value.
+ ///
+ /// expected *O*(1) time; worst-case *O*(*p*) time
pub fn remove(self) -> V::Strong {
self.remove_entry().1
}
@@ -619,16 +683,22 @@
impl<'a, K: WeakKey, V: WeakElement> VacantEntry<'a, K, V> {
/// Gets a reference to the key that would be used when inserting a
/// value through the `VacantEntry`.
+ ///
+ /// *O*(1) time
pub fn key(&self) -> &K::Strong {
&self.inner.key
}
/// Returns ownership of the key.
+ ///
+ /// *O*(1) time
pub fn into_key(self) -> K::Strong {
self.inner.key
}
/// Inserts the key and value into the map, returning the same value.
+ ///
+ /// *O*(1) time
pub fn insert(self, value: V::Strong) -> V::Strong {
let old_bucket = mem::replace(
&mut self.inner.map.buckets[self.inner.pos],
@@ -853,6 +923,9 @@
type Item = (K::Strong, V::Strong);
type IntoIter = IntoIter<K, V>;
+ /// Creates an owning iterator from `self`.
+ ///
+ /// *O*(1) time (and *O*(*n*) time to dispose of the result)
fn into_iter(self) -> Self::IntoIter {
IntoIter {
size: self.inner.len,
@@ -865,6 +938,9 @@
type Item = (K::Strong, V::Strong);
type IntoIter = Iter<'a, K, V>;
+ /// Creates a borrowing iterator from `self`.
+ ///
+ /// *O*(1) time
fn into_iter(self) -> Self::IntoIter {
Iter {
base: self.inner.buckets.iter(),
@@ -875,21 +951,29 @@
impl<K: WeakElement, V: WeakElement, S> WeakWeakHashMap<K, V, S> {
/// Gets an iterator over the keys and values.
+ ///
+ /// *O*(1) time
pub fn iter(&self) -> Iter<K, V> {
self.into_iter()
}
/// Gets an iterator over the keys.
+ ///
+ /// *O*(1) time
pub fn keys(&self) -> Keys<K, V> {
Keys(self.iter())
}
/// Gets an iterator over the values.
+ ///
+ /// *O*(1) time
pub fn values(&self) -> Values<K, V> {
Values(self.iter())
}
/// Gets a draining iterator, which removes all the values but retains the storage.
+ ///
+ /// *O*(1) time (and *O*(*n*) time to dispose of the result)
pub fn drain(&mut self) -> Drain<K, V> {
let old_len = self.inner.len;
self.inner.len = 0;
diff --git a/tests/weak_key_hash_map.rs b/tests/weak_key_hash_map.rs
index fe18890..5d50764 100644
--- a/tests/weak_key_hash_map.rs
+++ b/tests/weak_key_hash_map.rs
@@ -3,7 +3,6 @@
use std::hash::Hash;
use std::rc::{Rc, Weak};
-use rand::Rng;
use quickcheck::{Arbitrary, Gen, quickcheck};
use weak_table::WeakKeyHashMap;
@@ -138,22 +137,22 @@
}
impl<K: Arbitrary, V: Arbitrary> Arbitrary for Cmd<K, V> {
- fn arbitrary<G: Gen>(g: &mut G) -> Self {
- let choice = g.gen_range(0, 100);
+ fn arbitrary(g: &mut Gen) -> Self {
+ let choice = u8::arbitrary(g);
- match choice {
- 00..=39 => Insert(K::arbitrary(g), V::arbitrary(g)),
- 40..=49 => Reinsert(usize::arbitrary(g), V::arbitrary(g)),
- 50..=69 => RemoveInserted(usize::arbitrary(g)),
- 70..=79 => RemoveOther(K::arbitrary(g)),
- 80..=99 => ForgetInserted(usize::arbitrary(g)),
+ match choice % 10 {
+ 0..=3 => Insert(K::arbitrary(g), V::arbitrary(g)),
+ 4 => Reinsert(usize::arbitrary(g), V::arbitrary(g)),
+ 5..=6 => RemoveInserted(usize::arbitrary(g)),
+ 7 => RemoveOther(K::arbitrary(g)),
+ 8..=9 => ForgetInserted(usize::arbitrary(g)),
_ => unreachable!(),
}
}
}
impl<K: Arbitrary, V: Arbitrary> Arbitrary for Script<K, V> {
- fn arbitrary<G: Gen>(g: &mut G) -> Self {
+ fn arbitrary(g: &mut Gen) -> Self {
Script(Vec::<Cmd<K, V>>::arbitrary(g))
}