From 93d924b9bab5b33fa2d3af0a2695e55dfa43f228 Mon Sep 17 00:00:00 2001 From: Joel Galenson Date: Thu, 2 Dec 2021 07:49:17 -0800 Subject: Refresh Android.bp, cargo2android.json, TEST_MAPPING. Test: None Change-Id: I69ac0a230f61572380bb9954a807617dbdba1eb5 --- Android.bp | 5 ++++- cargo2android.json | 4 ++++ 2 files changed, 8 insertions(+), 1 deletion(-) create mode 100644 cargo2android.json diff --git a/Android.bp b/Android.bp index 33c19f1..c5216d4 100644 --- a/Android.bp +++ b/Android.bp @@ -1,4 +1,5 @@ -// This file is generated by cargo2android.py --device --run --dependencies. +// This file is generated by cargo2android.py --config cargo2android.json. +// Do not modify this file as changes will be overridden on upgrade. package { default_applicable_licenses: ["external_rust_crates_weak-table_license"], @@ -21,6 +22,8 @@ rust_library { name: "libweak_table", host_supported: true, crate_name: "weak_table", + cargo_env_compat: true, + cargo_pkg_version: "0.3.0", srcs: ["src/lib.rs"], edition: "2018", } diff --git a/cargo2android.json b/cargo2android.json new file mode 100644 index 0000000..bf78496 --- /dev/null +++ b/cargo2android.json @@ -0,0 +1,4 @@ +{ + "device": true, + "run": true +} \ No newline at end of file -- cgit v1.2.3 From 77e4bb9dcdecc19a1ac92de757dc3cb065afb594 Mon Sep 17 00:00:00 2001 From: David LeGare Date: Wed, 2 Mar 2022 16:21:23 +0000 Subject: Update weak-table to 0.3.2 Test: cd external/rust/crates && atest --host -c Change-Id: I9aa0464a12ee3690359baabf03ca883b6240f556 --- .cargo_vcs_info.json | 2 +- .github/dependabot.yml | 8 ++ .github/workflows/ci.yml | 71 ++++++++++++++++ .travis.yml | 23 ------ Android.bp | 6 +- CHANGELOG.md | 89 ++++++++++++++++++++ Cargo.toml | 28 ++++--- Cargo.toml.orig | 15 +++- METADATA | 14 ++-- README.md | 16 +++- release.toml | 20 ++++- src/by_ptr.rs | 2 +- src/compat.rs | 56 +++++++++++++ src/lib.rs | 35 +++++++- src/ptr_weak_hash_set.rs | 54 ++++++++++-- src/ptr_weak_key_hash_map.rs | 91 +++++++++++++++++--- src/ptr_weak_weak_hash_map.rs | 82 +++++++++++++++--- src/traits.rs | 20 ++++- src/util.rs | 2 + src/weak_hash_set.rs | 56 +++++++++++-- src/weak_key_hash_map.rs | 188 ++++++++++++++++++++++++++++++++---------- src/weak_value_hash_map.rs | 119 +++++++++++++++++++++----- src/weak_weak_hash_map.rs | 142 ++++++++++++++++++++++++------- tests/weak_key_hash_map.rs | 21 +++-- 24 files changed, 968 insertions(+), 192 deletions(-) create mode 100644 .github/dependabot.yml create mode 100644 .github/workflows/ci.yml delete mode 100644 .travis.yml create mode 100644 CHANGELOG.md create mode 100644 src/compat.rs 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 @@ rust_library { 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 + ``). + +## [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` + +### Improved +- documentation + +## [0.1.1] - 2018-03-05 + +Initial release. + +[Next Release]: +[0.3.2]: +[0.3.1]: +[0.2.4]: +[0.2.3]: +[0.2.2]: +[0.2.1]: +[0.2.0]: +[0.1.3]: +[0.1.2]: +[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 "] 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 "] 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 @@ third_party { } 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 -[![Build Status](https://travis-ci.org/tov/weak-table-rs.svg?branch=master)](https://travis-ci.org/tov/weak-table-rs) +[![Build Status](https://github.com/tov/weak-table-rs/actions/workflows/ci.yml/badge.svg)](https://github.com/tov/weak-table-rs/actions) [![Crates.io](https://img.shields.io/crates/v/weak-table.svg?maxAge=2592000)](https://crates.io/crates/weak-table) [![License: MIT](https://img.shields.io/badge/license-MIT-blue.svg)](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\\]: " +replace = '''[Next Release]: +[{{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 ptr_weak_weak_hash_map; 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 @@ impl PtrWeakHashSet 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 @@ impl PtrWeakHashSet 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 @@ impl PtrWeakHashSet /// /// 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 @@ impl PtrWeakHashSet /// 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 @@ impl PtrWeakHashSet /// Removes all mappings not satisfying the given predicate. /// /// Also removes any expired mappings. + /// + /// *O*(*n*) time pub fn retain(&mut self, mut f: F) where F: FnMut(T::Strong) -> bool { @@ -116,6 +146,10 @@ impl PtrWeakHashSet } /// 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(&self, other: &PtrWeakHashSet) -> bool where S1: BuildHasher { @@ -172,11 +206,15 @@ impl PtrWeakHashSet where T::Strong: Deref { /// Gets an iterator over the keys and values. + /// + /// *O*(1) time pub fn iter(&self) -> Iter { 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 { Drain(self.0.drain()) } @@ -239,6 +277,9 @@ impl IntoIterator for PtrWeakHashSet { type Item = T::Strong; type IntoIter = IntoIter; + /// 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 @@ impl<'a, T: WeakElement, S> IntoIterator for &'a PtrWeakHashSet 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 @@ impl PtrWeakKeyHashMap 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 @@ impl PtrWeakKeyHashMap 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 @@ impl PtrWeakKeyHashMap /// /// 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 @@ impl PtrWeakKeyHashMap /// 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, 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 { 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 { self.0.remove(&(key.deref() as *const _)) } @@ -124,6 +158,8 @@ impl PtrWeakKeyHashMap /// Removes all mappings not satisfying the given predicate. /// /// Also removes any expired mappings. + /// + /// *O*(*n*) time pub fn retain(&mut self, f: F) where F: FnMut(K::Strong, &mut V) -> bool { @@ -134,6 +170,10 @@ impl PtrWeakKeyHashMap /// /// 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(&self, other: &PtrWeakKeyHashMap, value_equal: F) -> bool where F: FnMut(&V, &V1) -> bool, S1: BuildHasher @@ -142,6 +182,10 @@ impl PtrWeakKeyHashMap } /// 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(&self, other: &PtrWeakKeyHashMap) -> bool where V: PartialEq, S1: BuildHasher @@ -150,6 +194,10 @@ impl PtrWeakKeyHashMap } /// 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(&self, other: &PtrWeakKeyHashMap) -> bool where S1: BuildHasher { @@ -161,31 +209,43 @@ impl PtrWeakKeyHashMap where K::Strong: Deref { /// Gets an iterator over the keys and values. + /// + /// *O*(1) time pub fn iter(&self) -> Iter, V> { self.0.iter() } /// Gets an iterator over the keys. + /// + /// *O*(1) time pub fn keys(&self) -> Keys, V> { self.0.keys() } /// Gets an iterator over the values. + /// + /// *O*(1) time pub fn values(&self) -> Values, V> { self.0.values() } /// Gets an iterator over the keys and mutable values. + /// + /// *O*(1) time pub fn iter_mut(&mut self) -> IterMut, V> { self.0.iter_mut() } /// Gets an iterator over the mutable values. + /// + /// *O*(1) time pub fn values_mut(&mut self) -> ValuesMut, 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, V> { self.0.drain() } @@ -283,6 +343,9 @@ impl IntoIterator for PtrWeakKeyHashMap { type Item = (K::Strong, V); type IntoIter = IntoIter, 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 @@ impl<'a, K: WeakElement, V, S> IntoIterator for &'a PtrWeakKeyHashMap { type Item = (K::Strong, &'a V); type IntoIter = Iter<'a, ByPtr, V>; + /// Creates a borrowing iterator from `self`. + /// + /// *O*(1) time fn into_iter(self) -> Self::IntoIter { (&self.0).into_iter() } @@ -301,17 +367,22 @@ impl<'a, K: WeakElement, V, S> IntoIterator for &'a mut PtrWeakKeyHashMap, 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, 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 @@ impl PtrWeakWeakHashMap 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 @@ impl PtrWeakWeakHashMap 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 @@ impl PtrWeakWeakHashMap bool { self.0.is_empty() } @@ -82,37 +100,51 @@ impl PtrWeakWeakHashMap 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, 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 { 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 { 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 { self.0.remove(&(key.deref() as *const _)) } @@ -120,6 +152,8 @@ impl PtrWeakWeakHashMap(&mut self, f: F) where F: FnMut(K::Strong, V::Strong) -> bool { @@ -130,6 +164,10 @@ impl PtrWeakWeakHashMap(&self, other: &PtrWeakWeakHashMap, value_equal: F) -> bool where F: FnMut(V::Strong, V1::Strong) -> bool, V1: WeakElement, @@ -139,6 +177,10 @@ impl PtrWeakWeakHashMap(&self, other: &PtrWeakWeakHashMap) -> bool where V1: WeakElement, V::Strong: PartialEq, @@ -148,6 +190,10 @@ impl PtrWeakWeakHashMap(&self, other: &PtrWeakWeakHashMap) -> bool where V1: WeakElement, S1: BuildHasher @@ -160,21 +206,29 @@ impl PtrWeakWeakHashMap where K::Strong: Deref { /// Gets an iterator over the keys and values. + /// + /// *O*(1) time pub fn iter(&self) -> Iter, V> { self.0.iter() } /// Gets an iterator over the keys. + /// + /// *O*(1) time pub fn keys(&self) -> Keys, V> { self.0.keys() } /// Gets an iterator over the values. + /// + /// *O*(1) time pub fn values(&self) -> Values, 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, V> { self.0.drain() } @@ -245,6 +299,9 @@ impl IntoIterator for PtrWeakWeakHashMap, 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 @@ impl<'a, K: WeakElement, V: WeakElement, S> IntoIterator for &'a PtrWeakWeakHash type Item = (K::Strong, V::Strong); type IntoIter = Iter<'a, ByPtr, 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>) { // 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 @@ pub trait WeakKey : WeakElement { /// strong pointer. fn with_key(view: &Self::Strong, f: F) -> R where F: FnOnce(&Self::Key) -> R; + + /// Hashes the key `view` into the given `Hasher`. + fn hash(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(view: &Self::Strong, key: &Q) -> bool + where Q: ?Sized + Eq, + Self::Key: Borrow + { + Self::with_key(view, |k| k.borrow() == key) + } } impl WeakElement for rc::Weak { @@ -94,7 +106,7 @@ impl WeakKey for rc::Weak { fn with_key(view: &Self::Strong, f: F) -> R where F: FnOnce(&Self::Key) -> R { - f(&view) + f(view) } } @@ -121,7 +133,7 @@ impl WeakKey for sync::Weak fn with_key(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(size: usize) -> Box<[Option]> { 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 @@ pub use super::WeakHashSet; impl WeakHashSet { /// 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 WeakHashSet { impl WeakHashSet { /// 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 @@ impl WeakHashSet { /// /// 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 @@ impl WeakHashSet { /// 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 @@ impl WeakHashSet { // 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(&self, key: &Q) -> bool where Q: ?Sized + Eq + Hash, T::Key: Borrow @@ -112,6 +136,8 @@ impl WeakHashSet { /// /// assert!(Rc::ptr_eq( &a, &also_a )); /// ``` + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn get(&self, key: &Q) -> Option where Q: ?Sized + Eq + Hash, T::Key: Borrow @@ -121,11 +147,15 @@ impl WeakHashSet { /// 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: &Q) -> bool where Q: ?Sized + Eq + Hash, T::Key: Borrow @@ -136,6 +166,8 @@ impl WeakHashSet { /// Removes all mappings not satisfying the given predicate. /// /// Also removes any expired mappings. + /// + /// *O*(*n*) time pub fn retain(&mut self, mut f: F) where F: FnMut(T::Strong) -> bool { @@ -143,6 +175,10 @@ impl WeakHashSet { } /// 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(&self, other: &WeakHashSet) -> bool where S1: BuildHasher { @@ -197,11 +233,15 @@ impl<'a, T: WeakElement> Iterator for Drain<'a, T> { impl WeakHashSet { /// Gets an iterator over the keys and values. + /// + /// *O*(1) time pub fn iter(&self) -> Iter { 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 { Drain(self.0.drain()) } @@ -255,6 +295,9 @@ impl IntoIterator for WeakHashSet { type Item = T::Strong; type IntoIter = IntoIter; + /// 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 @@ impl<'a, T: WeakKey, S> IntoIterator for &'a WeakHashSet { 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 @@ struct InnerEntry<'a, K: 'a + WeakKey, V: 'a> { /// 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>, + base: slice::Iter<'a, Bucket>, size: usize, } @@ -44,7 +37,7 @@ impl<'a, K: WeakElement, V> Iterator for Iter<'a, K, V> { type Item = (K::Strong, &'a V); fn next(&mut self) -> Option { - 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 @@ impl<'a, K: WeakElement, V> Iterator for Iter<'a, K, V> { #[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>, + base: slice::IterMut<'a, Bucket>, size: usize, } @@ -72,7 +65,7 @@ impl<'a, K: WeakElement, V> Iterator for IterMut<'a, K, V> { type Item = (K::Strong, &'a mut V); fn next(&mut self) -> Option { - 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 @@ impl<'a, K: WeakElement, V> Iterator for ValuesMut<'a, K, V> { #[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>, + base: slice::IterMut<'a, Bucket>, size: usize, } @@ -148,7 +141,7 @@ impl<'a, K: WeakElement, V> Iterator for Drain<'a, K, V> { type Item = (K::Strong, V); fn next(&mut self) -> Option { - 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: WeakElement, V> Iterator for Drain<'a, K, V> { 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 @@ impl<'a, K, V> Drop for Drain<'a, K, V> { /// An iterator that consumes the values of a weak hash map, leaving it empty. pub struct IntoIter { - base: ::std::vec::IntoIter>, + base: vec::IntoIter>, size: usize, } @@ -183,12 +176,10 @@ impl Iterator for IntoIter { type Item = (K::Strong, V); fn next(&mut self) -> Option { - 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 Iterator for IntoIter { impl WeakKeyHashMap { /// 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 WeakKeyHashMap impl WeakKeyHashMap { /// 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 @@ impl WeakKeyHashMap } /// 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 @@ impl WeakKeyHashMap } /// 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 @@ impl WeakKeyHashMap } /// Returns an over-approximation of the number of elements. + /// + /// *O*(1) time pub fn len(&self) -> usize { self.inner.len } @@ -285,6 +296,8 @@ impl WeakKeyHashMap /// /// 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 @@ impl WeakKeyHashMap /// 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 @@ impl WeakKeyHashMap } /// Gets the requested entry. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn entry(&mut self, key: K::Strong) -> Entry { self.maybe_adjust_size(); self.entry_no_grow(key) @@ -318,7 +335,7 @@ impl WeakKeyHashMap fn entry_no_grow(&mut self, key: K::Strong) -> Entry { 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 @@ impl WeakKeyHashMap } /// Removes all associations from the map. + /// + /// *O*(*n*) time pub fn clear(&mut self) { self.drain(); } @@ -357,14 +376,14 @@ impl WeakKeyHashMap { 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 @@ impl WeakKeyHashMap } /// Returns a reference to the value corresponding to the key. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn get(&self, key: &Q) -> Option<&V> where Q: ?Sized + Hash + Eq, K::Key: Borrow @@ -395,6 +416,8 @@ impl WeakKeyHashMap } /// Returns true if the map contains the specified key. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn contains_key(&self, key: &Q) -> bool where Q: ?Sized + Hash + Eq, K::Key: Borrow @@ -403,6 +426,8 @@ impl WeakKeyHashMap } /// Returns a strong reference to the key, if found. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn get_key(&self, key: &Q) -> Option where Q: ?Sized + Hash + Eq, K::Key: Borrow @@ -411,6 +436,8 @@ impl WeakKeyHashMap } /// 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(&self, key: &Q) -> Option<(K::Strong, &V)> where Q: ?Sized + Hash + Eq, K::Key: Borrow @@ -420,6 +447,8 @@ impl WeakKeyHashMap } /// 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: &Q) -> Option<&mut V> where Q: ?Sized + Hash + Eq, K::Key: Borrow @@ -430,6 +459,8 @@ impl WeakKeyHashMap /// 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(&mut self, key: &Q) -> Option<(K::Strong, &mut V)> where Q: ?Sized + Hash + Eq, K::Key: Borrow @@ -441,6 +472,8 @@ impl WeakKeyHashMap /// 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 { match self.entry(key) { Entry::Occupied(mut occupied) => { @@ -454,6 +487,8 @@ impl WeakKeyHashMap } /// 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: &Q) -> Option where Q: ?Sized + Hash + Eq, K::Key: Borrow @@ -471,6 +506,8 @@ impl WeakKeyHashMap /// Removes all mappings not satisfying the given predicate. /// /// Also removes any expired mappings. + /// + /// *O*(*n*) time pub fn retain(&mut self, mut f: F) where F: FnMut(K::Strong, &mut V) -> bool { @@ -490,18 +527,24 @@ impl WeakKeyHashMap } } - /// 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(&self, other: &WeakKeyHashMap, - 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 @@ impl WeakKeyHashMap } /// 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(&self, other: &WeakKeyHashMap) -> bool where V: PartialEq, S1: BuildHasher @@ -521,18 +568,21 @@ impl WeakKeyHashMap } /// 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(&self, other: &WeakKeyHashMap) -> bool where S1: BuildHasher { self.is_submap_with(other, |_, _| true) } - fn hash(&self, key: &Q) -> HashCode - where Q: ?Sized + Hash, - K::Key: Borrow + fn hash(&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 Default for WeakKeyHashMap ::std::ops::Index<&'a Q> for WeakKeyHashMap +impl<'a, K, V, S, Q> ops::Index<&'a Q> for WeakKeyHashMap where K: WeakKey, K::Key: Borrow, S: BuildHasher, @@ -569,7 +619,7 @@ impl<'a, K, V, S, Q> ::std::ops::Index<&'a Q> for WeakKeyHashMap } } -impl<'a, K, V, S, Q> ::std::ops::IndexMut<&'a Q> for WeakKeyHashMap +impl<'a, K, V, S, Q> ops::IndexMut<&'a Q> for WeakKeyHashMap where K: WeakKey, K::Key: Borrow, S: BuildHasher, @@ -580,7 +630,7 @@ impl<'a, K, V, S, Q> ::std::ops::IndexMut<&'a Q> for WeakKeyHashMap } } -impl ::std::iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap +impl iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap where K: WeakKey, S: BuildHasher + Default { @@ -591,7 +641,7 @@ impl ::std::iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap ::std::iter::Extend<(K::Strong, V)> for WeakKeyHashMap +impl iter::Extend<(K::Strong, V)> for WeakKeyHashMap where K: WeakKey, S: BuildHasher { @@ -602,7 +652,7 @@ impl ::std::iter::Extend<(K::Strong, V)> for WeakKeyHashMap } } -impl<'a, K, V, S> ::std::iter::Extend<(&'a K::Strong, &'a V)> for WeakKeyHashMap +impl<'a, K, V, S> iter::Extend<(&'a K::Strong, &'a V)> for WeakKeyHashMap where K: 'a + WeakKey, K::Strong: Clone, V: 'a + Clone, @@ -628,7 +678,7 @@ impl<'a, K: WeakKey, V> InnerEntry<'a, K, V> { 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 @@ impl<'a, K: WeakKey, V> Entry<'a, K, V> { /// 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 @@ impl<'a, K: WeakKey, V> Entry<'a, K, V> { /// 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 V>(self, default: F) -> &'a mut V { match self { Entry::Occupied(occupied) => occupied.into_mut(), @@ -662,6 +716,8 @@ impl<'a, K: WeakKey, V> Entry<'a, K, V> { } /// 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> Entry<'a, K, V> { 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 @@ impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> { } /// 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 @@ impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> { } /// 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> OccupiedEntry<'a, K, V> { 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 @@ impl IntoIterator for WeakKeyHashMap { type Item = (K::Strong, V); type IntoIter = IntoIter; + /// 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 @@ impl<'a, K: WeakElement, V, S> IntoIterator for &'a WeakKeyHashMap { 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 @@ impl<'a, K: WeakElement, V, S> IntoIterator for &'a mut WeakKeyHashMap 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<'a, K: WeakElement, V, S> IntoIterator for &'a mut WeakKeyHashMap impl WeakKeyHashMap { /// Gets an iterator over the keys and values. + /// + /// *O*(1) time pub fn iter(&self) -> Iter { self.into_iter() } /// Gets an iterator over the keys. + /// + /// *O*(1) time pub fn keys(&self) -> Keys { Keys(self.iter()) } /// Gets an iterator over the values. + /// + /// *O*(1) time pub fn values(&self) -> Values { Values(self.iter()) } /// Gets an iterator over the keys and mutable values. + /// + /// *O*(1) time pub fn iter_mut(&mut self) -> IterMut { self.into_iter() } /// Gets an iterator over the mutable values. + /// + /// *O*(1) time pub fn values_mut(&mut self) -> ValuesMut { 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 { let old_len = self.inner.len; self.inner.len = 0; @@ -1004,8 +1101,13 @@ impl WeakKeyHashMap { } #[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 @@ mod tests { assert_eq!( map.len(), 0 ); assert!( !map.contains_key("five") ); - let five: Rc = Rc::from("five".to_string()); + let five: Rc = 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 @@ struct InnerEntry<'a, K: 'a, V: 'a + WeakElement> { /// 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>, + base: slice::Iter<'a, Bucket>, size: usize, } @@ -49,7 +42,7 @@ impl<'a, K, V: WeakElement> Iterator for Iter<'a, K, V> { type Item = (&'a K, V::Strong); fn next(&mut self) -> Option { - 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 @@ impl<'a, K, V: WeakElement> Iterator for Values<'a, K, V> { #[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>, + base: slice::IterMut<'a, Bucket>, size: usize, } @@ -109,7 +102,7 @@ impl<'a, K, V: WeakElement> Iterator for Drain<'a, K, V> { type Item = (K, V::Strong); fn next(&mut self) -> Option { - 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: WeakElement> Iterator for Drain<'a, K, V> { 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 @@ impl<'a, K, V> Drop for Drain<'a, K, V> { /// An iterator that consumes the values of a weak hash map, leaving it empty. pub struct IntoIter { - base: ::std::vec::IntoIter>, + base: vec::IntoIter>, size: usize, } @@ -144,12 +137,10 @@ impl Iterator for IntoIter { type Item = (K, V::Strong); fn next(&mut self) -> Option { - 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 Iterator for IntoIter { impl WeakValueHashMap { /// 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 WeakValueHashMap impl WeakValueHashMap { /// 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 @@ impl WeakValueHashMap } /// 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 @@ impl WeakValueHashMap } /// 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 @@ impl WeakValueHashMap } /// Returns an over-approximation of the number of elements. + /// + /// *O*(1) time pub fn len(&self) -> usize { self.inner.len } @@ -246,6 +257,8 @@ impl WeakValueHashMap /// /// 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 @@ impl WeakValueHashMap /// 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 @@ impl WeakValueHashMap } /// Gets the requested entry. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn entry(&mut self, key: K) -> Entry { self.maybe_adjust_size(); self.entry_no_grow(key) @@ -309,6 +326,8 @@ impl WeakValueHashMap } /// Removes all associations from the map. + /// + /// *O*(*n*) time pub fn clear(&mut self) { self.drain(); } @@ -348,6 +367,8 @@ impl WeakValueHashMap } /// Returns a reference to the value corresponding to the key. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn get(&self, key: &Q) -> Option where Q: ?Sized + Hash + Eq, K: Borrow @@ -356,6 +377,8 @@ impl WeakValueHashMap } /// Returns true if the map contains the specified key. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn contains_key(&self, key: &Q) -> bool where Q: ?Sized + Hash + Eq, K: Borrow @@ -366,6 +389,8 @@ impl WeakValueHashMap /// 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 { match self.entry(key) { Entry::Occupied(mut occupied) => { @@ -379,6 +404,8 @@ impl WeakValueHashMap } /// 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: &Q) -> Option where Q: ?Sized + Hash + Eq, K: Borrow @@ -394,6 +421,8 @@ impl WeakValueHashMap /// Removes all mappings not satisfying the given predicate. /// /// Also removes any expired mappings. + /// + /// *O*(*n*) time pub fn retain(&mut self, mut f: F) where F: FnMut(&K, V::Strong) -> bool { @@ -417,6 +446,10 @@ impl WeakValueHashMap /// /// 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(&self, other: &WeakValueHashMap, mut value_equal: F) -> bool where V1: WeakElement, @@ -437,6 +470,10 @@ impl WeakValueHashMap } /// 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(&self, other: &WeakValueHashMap) -> bool where V1: WeakElement, V::Strong: PartialEq, @@ -446,6 +483,10 @@ impl WeakValueHashMap } /// 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(&self, other: &WeakValueHashMap) -> bool where V1: WeakElement, S1: BuildHasher @@ -486,7 +527,7 @@ impl Default for WeakVal } } -impl ::std::iter::FromIterator<(K, V::Strong)> for WeakValueHashMap +impl iter::FromIterator<(K, V::Strong)> for WeakValueHashMap where K: Eq + Hash, V: WeakElement, S: BuildHasher + Default @@ -554,12 +595,16 @@ impl<'a, K: Eq + Hash, V: WeakElement> InnerEntry<'a, K, V> { 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 V::Strong>(self, default: F) -> V::Strong { match self { Entry::Occupied(occupied) => occupied.get_strong(), @@ -568,6 +613,8 @@ impl<'a, K, V: WeakElement> Entry<'a, K, V> { } /// 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> Entry<'a, K, V> { 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 @@ impl<'a, K, V: WeakElement> OccupiedEntry<'a, K, V> { } /// 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> OccupiedEntry<'a, K, V> { 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 @@ impl IntoIterator for WeakValueHashMap { type Item = (K, V::Strong); type IntoIter = IntoIter; + /// 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 @@ impl<'a, K, V: WeakElement, S> IntoIterator for &'a WeakValueHashMap { 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<'a, K, V: WeakElement, S> IntoIterator for &'a WeakValueHashMap { impl WeakValueHashMap { /// Gets an iterator over the keys and values. + /// + /// *O*(1) time pub fn iter(&self) -> Iter { self.into_iter() } /// Gets an iterator over the keys. + /// + /// *O*(1) time pub fn keys(&self) -> Keys { Keys(self.iter()) } /// Gets an iterator over the values. + /// + /// *O*(1) time pub fn values(&self) -> Values { 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 { 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 @@ struct InnerEntry<'a, K: 'a + WeakKey, V: 'a> { /// 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>, + base: slice::Iter<'a, Bucket>, size: usize, } @@ -50,7 +43,7 @@ impl<'a, K: WeakElement, V: WeakElement> Iterator for Iter<'a, K, V> { type Item = (K::Strong, V::Strong); fn next(&mut self) -> Option { - 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 @@ impl<'a, K: WeakElement, V: WeakElement> Iterator for Values<'a, K, V> { #[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>, + base: slice::IterMut<'a, Bucket>, size: usize, } @@ -110,7 +103,7 @@ impl<'a, K: WeakElement, V: WeakElement> Iterator for Drain<'a, K, V> { type Item = (K::Strong, V::Strong); fn next(&mut self) -> Option { - 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: WeakElement, V: WeakElement> Iterator for Drain<'a, K, V> { 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 @@ impl<'a, K, V> Drop for Drain<'a, K, V> { /// An iterator that consumes the values of a weak hash map, leaving it empty. pub struct IntoIter { - base: ::std::vec::IntoIter>, + base: vec::IntoIter>, size: usize, } @@ -145,12 +138,10 @@ impl Iterator for IntoIter { type Item = (K::Strong, V::Strong); fn next(&mut self) -> Option { - 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 Iterator for IntoIter { impl WeakWeakHashMap { /// 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 WeakWeakHashMap impl WeakWeakHashMap { /// 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 @@ impl WeakWeakHashMap { } /// 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 @@ impl WeakWeakHashMap { } /// 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 @@ impl WeakWeakHashMap { } /// Returns an over-approximation of the number of elements. + /// + /// *O*(1) time pub fn len(&self) -> usize { self.inner.len } @@ -246,6 +257,8 @@ impl WeakWeakHashMap { /// /// 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 @@ impl WeakWeakHashMap { /// 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 @@ impl WeakWeakHashMap { } /// 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 { self.maybe_adjust_size(); self.entry_no_grow(key) @@ -279,7 +298,7 @@ impl WeakWeakHashMap { fn entry_no_grow(&mut self, key: K::Strong) -> Entry { 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 @@ impl WeakWeakHashMap { } /// Removes all associations from the map. + /// + /// *O*(*n*) time pub fn clear(&mut self) { self.drain(); } @@ -318,14 +339,14 @@ impl WeakWeakHashMap { { 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 @@ impl WeakWeakHashMap { } /// Returns a reference to the value corresponding to the key. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn get(&self, key: &Q) -> Option where Q: ?Sized + Hash + Eq, K::Key: Borrow @@ -355,6 +378,8 @@ impl WeakWeakHashMap { } /// Returns the strong reference to the key, if present. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn get_key(&self, key: &Q) -> Option where Q: ?Sized + Hash + Eq, K::Key: Borrow @@ -363,6 +388,8 @@ impl WeakWeakHashMap { } /// 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(&self, key: &Q) -> Option<(K::Strong, V::Strong)> where Q: ?Sized + Hash + Eq, K::Key: Borrow @@ -371,6 +398,8 @@ impl WeakWeakHashMap { } /// Returns true if the map contains the specified key. + /// + /// expected *O*(1) time; worst-case *O*(*p*) time pub fn contains_key(&self, key: &Q) -> bool where Q: ?Sized + Hash + Eq, K::Key: Borrow @@ -381,6 +410,8 @@ impl WeakWeakHashMap { /// 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 { match self.entry(key) { Entry::Occupied(mut occupied) => { @@ -394,6 +425,8 @@ impl WeakWeakHashMap { } /// 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: &Q) -> Option where Q: ?Sized + Hash + Eq, K::Key: Borrow @@ -409,6 +442,8 @@ impl WeakWeakHashMap { /// Removes all mappings not satisfying the given predicate. /// /// Also removes any expired mappings. + /// + /// *O*(*n*) time pub fn retain(&mut self, mut f: F) where F: FnMut(K::Strong, V::Strong) -> bool { @@ -432,6 +467,10 @@ impl WeakWeakHashMap { /// /// 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(&self, other: &WeakWeakHashMap, mut value_equal: F) -> bool where V1: WeakElement, @@ -452,6 +491,10 @@ impl WeakWeakHashMap { } /// 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(&self, other: &WeakWeakHashMap) -> bool where V1: WeakElement, V::Strong: PartialEq, @@ -461,6 +504,10 @@ impl WeakWeakHashMap { } /// 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(&self, other: &WeakWeakHashMap) -> bool where V1: WeakElement, S1: BuildHasher @@ -468,12 +515,11 @@ impl WeakWeakHashMap { self.is_submap_with(other, |_, _| true) } - fn hash(&self, key: &Q) -> HashCode - where Q: ?Sized + Hash, - K::Key: Borrow + fn hash(&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 Default for WeakWeakH } } -impl ::std::iter::FromIterator<(K::Strong, V::Strong)> for WeakWeakHashMap +impl iter::FromIterator<(K::Strong, V::Strong)> for WeakWeakHashMap where K: WeakKey, V: WeakElement, S: BuildHasher + Default @@ -538,7 +584,7 @@ impl<'a, K: WeakKey, V: WeakElement> InnerEntry<'a, K, V> { 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 @@ impl<'a, K: WeakKey, V: WeakElement> Entry<'a, K, V> { /// 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 @@ impl<'a, K: WeakKey, V: WeakElement> Entry<'a, K, V> { /// 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 V::Strong>(self, default: F) -> V::Strong { match self { Entry::Occupied(occupied) => occupied.get_strong(), @@ -572,6 +622,8 @@ impl<'a, K: WeakKey, V: WeakElement> Entry<'a, K, V> { } /// 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> Entry<'a, K, V> { 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 @@ impl<'a, K: WeakKey, V: WeakElement> OccupiedEntry<'a, K, V> { } /// 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> OccupiedEntry<'a, K, V> { 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 @@ impl IntoIterator for WeakWeakHashMap; + /// 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 @@ impl<'a, K: WeakElement, V: WeakElement, S> IntoIterator for &'a WeakWeakHashMap 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<'a, K: WeakElement, V: WeakElement, S> IntoIterator for &'a WeakWeakHashMap impl WeakWeakHashMap { /// Gets an iterator over the keys and values. + /// + /// *O*(1) time pub fn iter(&self) -> Iter { self.into_iter() } /// Gets an iterator over the keys. + /// + /// *O*(1) time pub fn keys(&self) -> Keys { Keys(self.iter()) } /// Gets an iterator over the values. + /// + /// *O*(1) time pub fn values(&self) -> Values { 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 { 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::fmt::Debug; 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 Tester } impl Arbitrary for Cmd { - fn arbitrary(g: &mut G) -> Self { - let choice = g.gen_range(0, 100); - - 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)), + fn arbitrary(g: &mut Gen) -> Self { + let choice = u8::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 Arbitrary for Script { - fn arbitrary(g: &mut G) -> Self { + fn arbitrary(g: &mut Gen) -> Self { Script(Vec::>::arbitrary(g)) } -- cgit v1.2.3