diff options
Diffstat (limited to 'third_party/rust/fallible_collections')
18 files changed, 7650 insertions, 0 deletions
diff --git a/third_party/rust/fallible_collections/.cargo-checksum.json b/third_party/rust/fallible_collections/.cargo-checksum.json new file mode 100644 index 0000000000..7e41b87cf9 --- /dev/null +++ b/third_party/rust/fallible_collections/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"8ecacb7ad2f59391ae3247157c01c6d6508095f53ba466c3e3b554891b3e941f","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"0621878e61f0d0fda054bcbe02df75192c28bde1ecc8289cbd86aeba2dd72720","README.md":"5b817b980bb39f4bee82913daf9d1ef39d1cb9e790b85ab000f735a962ce596d","src/arc.rs":"3cf237ae0acb5b058a57b633170f079024455271e9420e5a9244bafbdeb90b1c","src/boxed.rs":"1f19ad48ab3a1f41cca3756f3fdbc22e97f50a9121511222afcfe1859faf50fa","src/btree.rs":"b83820fc2a00e2e34127b3037abde8b945f0ca2785f3def725787e6813c3d3e0","src/btree/map.rs":"557ce3ff2d02c425adcb2b4ac53b6b6607c25c535aee8ffa4f12bf773fbcd763","src/btree/node.rs":"d943949b8938b5888245d6560efd386c6ae78d23fc3a7a0cc5b06f4da8f4c1c1","src/btree/search.rs":"ae78f73f3e56ea277b0a02cc39454447b75e12a6c817ecfee00065b3ddbfff67","src/btree/set.rs":"607f0db0b189c39b41824fbbf6fd8d9c5fdf85cc40f4437b13152e7b86d2979f","src/format.rs":"5142970f6ac1fe66f667ee2565af786802e93e6728ec3a1b82ffaa9f6a6b5bce","src/hashmap.rs":"1b9bf03fd2f2d9412ea2dad6963e1d37d51662e7091424bfcdc44a502f4e64bc","src/lib.rs":"652532126fdc2a81a927d23e4e4ad810911ee5d398f35f82650b5b4ec9fc5576","src/rc.rs":"f327a0adcfd2b1e225913ae716deb96777ca562985ac64e3b83550111f809864","src/try_clone.rs":"725130e0ddacde1ff7c976de62fbe45d01c67412af395aa41cac4bcfb85f6a5f","src/vec.rs":"27369a12a66deff0fe3fc57eae0f3a639e98b968d92e10eff9d4b7af8354a9d4"},"package":"3f57ccc32870366ae684be48b32a1a2e196f98a42a9b4361fe77e13fd4a34755"}
\ No newline at end of file diff --git a/third_party/rust/fallible_collections/Cargo.toml b/third_party/rust/fallible_collections/Cargo.toml new file mode 100644 index 0000000000..27a8221a17 --- /dev/null +++ b/third_party/rust/fallible_collections/Cargo.toml @@ -0,0 +1,33 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# 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. +# +# 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 = "fallible_collections" +version = "0.4.6" +authors = ["vcombey <vcombey@student.42.fr>"] +description = "a crate which adds fallible allocation api to std collections" +readme = "README.md" +keywords = [ + "fallible", + "collections", +] +license = "MIT/Apache-2.0" +repository = "https://github.com/vcombey/fallible_collections.git" + +[dependencies.hashbrown] +version = "0.12.1" + +[features] +rust_1_57 = [] +std = [] +std_io = ["std"] +unstable = [] diff --git a/third_party/rust/fallible_collections/LICENSE-APACHE b/third_party/rust/fallible_collections/LICENSE-APACHE new file mode 100644 index 0000000000..16fe87b06e --- /dev/null +++ b/third_party/rust/fallible_collections/LICENSE-APACHE @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + +TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + +1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + +2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + +3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + +4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + +5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + +6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + +7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + +8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + +9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + +END OF TERMS AND CONDITIONS + +APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + +Copyright [yyyy] [name of copyright owner] + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. diff --git a/third_party/rust/fallible_collections/LICENSE-MIT b/third_party/rust/fallible_collections/LICENSE-MIT new file mode 100644 index 0000000000..25597d5838 --- /dev/null +++ b/third_party/rust/fallible_collections/LICENSE-MIT @@ -0,0 +1,25 @@ +Copyright (c) 2010 The Rust Project Developers + +Permission is hereby granted, free of charge, to any +person obtaining a copy of this software and associated +documentation files (the "Software"), to deal in the +Software without restriction, including without +limitation the rights to use, copy, modify, merge, +publish, distribute, sublicense, and/or sell copies of +the Software, and to permit persons to whom the Software +is furnished to do so, subject to the following +conditions: + +The above copyright notice and this permission notice +shall be included in all copies or substantial portions +of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF +ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED +TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A +PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT +SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION +OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR +IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/third_party/rust/fallible_collections/README.md b/third_party/rust/fallible_collections/README.md new file mode 100644 index 0000000000..b34825903d --- /dev/null +++ b/third_party/rust/fallible_collections/README.md @@ -0,0 +1,77 @@ +Fallible Collections.rs +============== + +Implement api on rust collection wich returns a result when an allocation error occurs. +This is inspired a lot by [RFC 2116](https://github.com/rust-lang/rfcs/blob/master/text/2116-alloc-me-maybe.md). + +The api currently propose a fallible interface for Vec, Box, Arc, Btree and Rc, +a TryClone trait wich is implemented for primitive rust traits and a fallible format macro. + +You can use this with try_clone_derive crate wich derive TryClone for your own types. + +# Getting Started + +[fallible collections is available on crates.io](https://crates.io/crates/fallible_collections). +It is recommended to look there for the newest released version, as well as links to the newest builds of the docs. + +At the point of the last update of this README, the latest published version could be used like this: + +Add the following dependency to your Cargo manifest... +Add feature std and rust_1_57 to use the stabilized try_reserve api and the std HashMap type. + +```toml +[dependencies] +fallible_collections = "0.4" + +# or +fallible_collections = { version = "0.4", features = ["std", "rust_1_57"] } +``` + +...and see the [docs](https://docs.rs/fallible_collections) for how to use it. + +# Example + +Exemple of using the FallibleBox interface. +```rust +use fallible_collections::FallibleBox; + +fn main() { + // this crate an Ordinary box but return an error on allocation failure + let mut a = <Box<_> as FallibleBox<_>>::try_new(5).unwrap(); + let mut b = Box::new(5); + + assert_eq!(a, b); + *a = 3; + assert_eq!(*a, 3); +} +``` + +Exemple of using the FallibleVec interface. +```rust +use fallible_collections::FallibleVec; + +fn main() { + // this crate an Ordinary Vec<Vec<u8>> but return an error on allocation failure + let a: Vec<Vec<u8>> = try_vec![try_vec![42; 10].unwrap(); 100].unwrap(); + let b: Vec<Vec<u8>> = vec![vec![42; 10]; 100]; + assert_eq!(a, b); + assert_eq!(a.try_clone().unwrap(), a); + ... +} +``` + +## License + +Licensed under either of + + * Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0) + * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT) + +at your option. + +### Contribution + +Unless you explicitly state otherwise, any contribution intentionally submitted +for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any +additional terms or conditions. + diff --git a/third_party/rust/fallible_collections/src/arc.rs b/third_party/rust/fallible_collections/src/arc.rs new file mode 100644 index 0000000000..282b8e5555 --- /dev/null +++ b/third_party/rust/fallible_collections/src/arc.rs @@ -0,0 +1,52 @@ +//! Implement a Fallible Arc +use super::FallibleBox; +use super::TryClone; + +use crate::TryReserveError; +use alloc::boxed::Box; +use alloc::sync::Arc; + +/// trait to implement Fallible Arc +#[deprecated( + since = "0.3.1", + note = "⚠️️️this function is not completely fallible, it can panic !, see [issue](https://github.com/vcombey/fallible_collections/issues/13). help wanted" +)] +pub trait FallibleArc<T> { + /// try creating a new Arc, returning a Result<Box<T>, + /// TryReserveError> if allocation failed + fn try_new(t: T) -> Result<Self, TryReserveError> + where + Self: Sized; +} + +#[allow(deprecated)] +impl<T> FallibleArc<T> for Arc<T> { + fn try_new(t: T) -> Result<Self, TryReserveError> { + // doesn't work as the inner variable of arc are also stocked in the box + + let b = <Box<T> as FallibleBox<T>>::try_new(t)?; + Ok(Arc::from(b)) + } +} + +/// Just a TryClone boilerplate for Arc +impl<T: ?Sized> TryClone for Arc<T> { + fn try_clone(&self) -> Result<Self, TryReserveError> { + Ok(self.clone()) + } +} + +#[cfg(test)] +mod test { + #[test] + fn fallible_rc() { + use std::sync::Arc; + + let mut x = Arc::new(3); + *Arc::get_mut(&mut x).unwrap() = 4; + assert_eq!(*x, 4); + + let _y = Arc::clone(&x); + assert!(Arc::get_mut(&mut x).is_none()); + } +} diff --git a/third_party/rust/fallible_collections/src/boxed.rs b/third_party/rust/fallible_collections/src/boxed.rs new file mode 100644 index 0000000000..6040754716 --- /dev/null +++ b/third_party/rust/fallible_collections/src/boxed.rs @@ -0,0 +1,151 @@ +//! Implement Fallible Box +use super::TryClone; +use crate::TryReserveError; +use alloc::alloc::Layout; +use alloc::boxed::Box; +use core::borrow::Borrow; +use core::ops::Deref; +use core::ptr::NonNull; + +/// trait to implement Fallible Box +pub trait FallibleBox<T> { + /// try creating a new box, returning a Result<Box<T>, + /// TryReserveError> if allocation failed + fn try_new(t: T) -> Result<Self, TryReserveError> + where + Self: Sized; +} +/// TryBox is a thin wrapper around alloc::boxed::Box to provide support for +/// fallible allocation. +/// +/// See the crate documentation for more. +pub struct TryBox<T> { + inner: Box<T>, +} + +impl<T> TryBox<T> { + #[inline] + pub fn try_new(t: T) -> Result<Self, TryReserveError> { + Ok(Self { + inner: <Box<T> as FallibleBox<T>>::try_new(t)?, + }) + } + + #[inline(always)] + pub fn into_raw(b: TryBox<T>) -> *mut T { + Box::into_raw(b.inner) + } + + /// # Safety + /// + /// See std::boxed::from_raw + #[inline(always)] + pub unsafe fn from_raw(raw: *mut T) -> Self { + Self { + inner: Box::from_raw(raw), + } + } +} + +impl<T: TryClone> TryClone for TryBox<T> { + fn try_clone(&self) -> Result<Self, TryReserveError> { + let clone: T = (*self.inner).try_clone()?; + Self::try_new(clone) + } +} + +impl<T> Deref for TryBox<T> { + type Target = T; + + #[inline(always)] + fn deref(&self) -> &T { + self.inner.deref() + } +} + +fn alloc(layout: Layout) -> Result<NonNull<u8>, TryReserveError> { + #[cfg(feature = "unstable")] // requires allocator_api + { + use core::alloc::Allocator; + alloc::alloc::Global + .allocate(layout) + .map_err(|_e| TryReserveError::AllocError { + layout, + #[cfg(not(feature = "rust_1_57"))] + non_exhaustive: (), + }) + .map(|v| v.cast()) + } + #[cfg(not(feature = "unstable"))] + { + match layout.size() { + 0 => { + // Required for alloc safety + // See https://doc.rust-lang.org/stable/std/alloc/trait.GlobalAlloc.html#safety-1 + Ok(NonNull::dangling()) + } + 1..=core::usize::MAX => { + let ptr = unsafe { alloc::alloc::alloc(layout) }; + core::ptr::NonNull::new(ptr).ok_or(TryReserveError::AllocError { layout }) + } + _ => unreachable!("size must be non-negative"), + } + } +} + +impl<T> FallibleBox<T> for Box<T> { + fn try_new(t: T) -> Result<Self, TryReserveError> { + let layout = Layout::for_value(&t); + let ptr = alloc(layout)?.as_ptr() as *mut T; + unsafe { + core::ptr::write(ptr, t); + Ok(Box::from_raw(ptr)) + } + } +} + +impl<T: TryClone> TryClone for Box<T> { + #[inline] + fn try_clone(&self) -> Result<Self, TryReserveError> { + <Self as FallibleBox<T>>::try_new(Borrow::<T>::borrow(self).try_clone()?) + } +} + +#[cfg(test)] +mod tests { + use super::*; + #[test] + fn boxed() { + let mut v = <Box<_> as FallibleBox<_>>::try_new(5).unwrap(); + assert_eq!(*v, 5); + *v = 3; + assert_eq!(*v, 3); + } + // #[test] + // fn big_alloc() { + // let layout = Layout::from_size_align(1_000_000_000_000, 8).unwrap(); + // let ptr = unsafe { alloc::alloc::alloc(layout) }; + // assert!(ptr.is_null()); + // } + + #[test] + fn trybox_zst() { + let b = <Box<_> as FallibleBox<_>>::try_new(()).expect("ok"); + assert_eq!(b, Box::new(())); + } + + struct NonCopyType; + + #[test] + fn trybox_deref() { + let try_box: TryBox<NonCopyType> = TryBox::try_new(NonCopyType {}).unwrap(); + let _derefed: &NonCopyType = try_box.deref(); + } + + #[test] + fn trybox_as_deref() { + let try_box_option: Option<TryBox<NonCopyType>> = + Some(TryBox::try_new(NonCopyType).unwrap()); + let _ref_option: Option<&NonCopyType> = try_box_option.as_deref(); + } +} diff --git a/third_party/rust/fallible_collections/src/btree.rs b/third_party/rust/fallible_collections/src/btree.rs new file mode 100644 index 0000000000..63d8c6bcf5 --- /dev/null +++ b/third_party/rust/fallible_collections/src/btree.rs @@ -0,0 +1,20 @@ +//! Implement Fallible Btree, As there is no try_reserve methods on btree, I add no choice but to fork the std implementation and change return types. +//! Currently this functionality is only available when building this crate with nightly and the `unstable` feature. +pub mod map; +pub use map::BTreeMap; + +pub mod set; +pub use set::BTreeSet; + +mod node; +mod search; +use crate::TryReserveError; + +#[doc(hidden)] +trait Recover<Q: ?Sized> { + type Key; + + fn get(&self, key: &Q) -> Option<&Self::Key>; + fn take(&mut self, key: &Q) -> Option<Self::Key>; + fn replace(&mut self, key: Self::Key) -> Result<Option<Self::Key>, TryReserveError>; +} diff --git a/third_party/rust/fallible_collections/src/btree/map.rs b/third_party/rust/fallible_collections/src/btree/map.rs new file mode 100644 index 0000000000..3a69a6679f --- /dev/null +++ b/third_party/rust/fallible_collections/src/btree/map.rs @@ -0,0 +1,2684 @@ +use crate::TryReserveError; +use core::borrow::Borrow; +use core::cmp::Ordering; +use core::fmt::Debug; +use core::hash::{Hash, Hasher}; +use core::iter::{FromIterator, FusedIterator, Peekable}; +use core::marker::PhantomData; +use core::ops::Bound::{Excluded, Included, Unbounded}; +use core::ops::{Index, RangeBounds}; +use core::{fmt, intrinsics, mem, ptr}; + +use super::node::{self, marker, ForceResult::*, Handle, InsertResult::*, NodeRef}; +use super::search::{self, SearchResult::*}; + +use Entry::*; +use UnderflowResult::*; + +/// A map based on a B-Tree. +/// +/// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing +/// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal +/// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of +/// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this +/// is done is *very* inefficient for modern computer architectures. In particular, every element +/// is stored in its own individually heap-allocated node. This means that every single insertion +/// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these +/// are both notably expensive things to do in practice, we are forced to at very least reconsider +/// the BST strategy. +/// +/// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing +/// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in +/// searches. However, this does mean that searches will have to do *more* comparisons on average. +/// The precise number of comparisons depends on the node search strategy used. For optimal cache +/// efficiency, one could search the nodes linearly. For optimal comparisons, one could search +/// the node using binary search. As a compromise, one could also perform a linear search +/// that initially only checks every i<sup>th</sup> element for some choice of i. +/// +/// Currently, our implementation simply performs naive linear search. This provides excellent +/// performance on *small* nodes of elements which are cheap to compare. However in the future we +/// would like to further explore choosing the optimal search strategy based on the choice of B, +/// and possibly other factors. Using linear search, searching for a random element is expected +/// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice, +/// however, performance is excellent. +/// +/// It is a logic error for a key to be modified in such a way that the key's ordering relative to +/// any other key, as determined by the [`Ord`] trait, changes while it is in the map. This is +/// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code. +/// +/// [`Ord`]: ../../std/cmp/trait.Ord.html +/// [`Cell`]: ../../std/cell/struct.Cell.html +/// [`RefCell`]: ../../std/cell/struct.RefCell.html +/// +/// # Examples +/// +/// ``` +/// use std::collections::BTreeMap; +/// +/// // type inference lets us omit an explicit type signature (which +/// // would be `BTreeMap<&str, &str>` in this example). +/// let mut movie_reviews = BTreeMap::new(); +/// +/// // review some movies. +/// movie_reviews.insert("Office Space", "Deals with real issues in the workplace."); +/// movie_reviews.insert("Pulp Fiction", "Masterpiece."); +/// movie_reviews.insert("The Godfather", "Very enjoyable."); +/// movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot."); +/// +/// // check for a specific one. +/// if !movie_reviews.contains_key("Les Misérables") { +/// println!("We've got {} reviews, but Les Misérables ain't one.", +/// movie_reviews.len()); +/// } +/// +/// // oops, this review has a lot of spelling mistakes, let's delete it. +/// movie_reviews.remove("The Blues Brothers"); +/// +/// // look up the values associated with some keys. +/// let to_find = ["Up!", "Office Space"]; +/// for book in &to_find { +/// match movie_reviews.get(book) { +/// Some(review) => println!("{}: {}", book, review), +/// None => println!("{} is unreviewed.", book) +/// } +/// } +/// +/// // Look up the value for a key (will panic if the key is not found). +/// println!("Movie review: {}", movie_reviews["Office Space"]); +/// +/// // iterate over everything. +/// for (movie, review) in &movie_reviews { +/// println!("{}: \"{}\"", movie, review); +/// } +/// ``` +/// +/// `BTreeMap` also implements an [`Entry API`](#method.entry), which allows +/// for more complex methods of getting, setting, updating and removing keys and +/// their values: +/// +/// ``` +/// use std::collections::BTreeMap; +/// +/// // type inference lets us omit an explicit type signature (which +/// // would be `BTreeMap<&str, u8>` in this example). +/// let mut player_stats = BTreeMap::new(); +/// +/// fn random_stat_buff() -> u8 { +/// // could actually return some random value here - let's just return +/// // some fixed value for now +/// 42 +/// } +/// +/// // insert a key only if it doesn't already exist +/// player_stats.entry("health").or_insert(100); +/// +/// // insert a key using a function that provides a new value only if it +/// // doesn't already exist +/// player_stats.entry("defence").or_insert_with(random_stat_buff); +/// +/// // update a key, guarding against the key possibly not being set +/// let stat = player_stats.entry("attack").or_insert(100); +/// *stat += random_stat_buff(); +/// ``` + +pub struct BTreeMap<K, V> { + root: node::Root<K, V>, + length: usize, +} + +unsafe impl<#[may_dangle] K, #[may_dangle] V> Drop for BTreeMap<K, V> { + fn drop(&mut self) { + unsafe { + drop(ptr::read(self).into_iter()); + } + } +} + +use crate::TryClone; + +impl<K: TryClone, V: TryClone> TryClone for BTreeMap<K, V> { + fn try_clone(&self) -> Result<BTreeMap<K, V>, TryReserveError> { + fn clone_subtree<'a, K: TryClone, V: TryClone>( + node: node::NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>, + ) -> Result<BTreeMap<K, V>, TryReserveError> + where + K: 'a, + V: 'a, + { + match node.force() { + Leaf(leaf) => { + let mut out_tree = BTreeMap { + root: node::Root::new_leaf()?, + length: 0, + }; + + { + let mut out_node = match out_tree.root.as_mut().force() { + Leaf(leaf) => leaf, + Internal(_) => unreachable!(), + }; + + let mut in_edge = leaf.first_edge(); + while let Ok(kv) = in_edge.right_kv() { + let (k, v) = kv.into_kv(); + in_edge = kv.right_edge(); + + out_node.push(k.try_clone()?, v.try_clone()?); + out_tree.length += 1; + } + } + + Ok(out_tree) + } + Internal(internal) => { + let mut out_tree = clone_subtree(internal.first_edge().descend())?; + + { + let mut out_node = out_tree.root.push_level()?; + let mut in_edge = internal.first_edge(); + while let Ok(kv) = in_edge.right_kv() { + let (k, v) = kv.into_kv(); + in_edge = kv.right_edge(); + + let k = (*k).try_clone()?; + let v = (*v).try_clone()?; + let subtree = clone_subtree(in_edge.descend())?; + + // We can't destructure subtree directly + // because BTreeMap implements Drop + let (subroot, sublength) = unsafe { + let root = ptr::read(&subtree.root); + let length = subtree.length; + mem::forget(subtree); + (root, length) + }; + + out_node.push(k, v, subroot); + out_tree.length += 1 + sublength; + } + } + + Ok(out_tree) + } + } + } + + if self.len() == 0 { + // Ideally we'd call `BTreeMap::new` here, but that has the `K: + // Ord` constraint, which this method lacks. + Ok(BTreeMap { + root: node::Root::shared_empty_root(), + length: 0, + }) + } else { + clone_subtree(self.root.as_ref()) + } + } +} + +impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> { + fn clone(&self) -> BTreeMap<K, V> { + fn clone_subtree<'a, K: Clone, V: Clone>( + node: node::NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>, + ) -> BTreeMap<K, V> + where + K: 'a, + V: 'a, + { + match node.force() { + Leaf(leaf) => { + let mut out_tree = BTreeMap { + root: node::Root::new_leaf().expect("Out of Mem"), + length: 0, + }; + + { + let mut out_node = match out_tree.root.as_mut().force() { + Leaf(leaf) => leaf, + Internal(_) => unreachable!(), + }; + + let mut in_edge = leaf.first_edge(); + while let Ok(kv) = in_edge.right_kv() { + let (k, v) = kv.into_kv(); + in_edge = kv.right_edge(); + + out_node.push(k.clone(), v.clone()); + out_tree.length += 1; + } + } + + out_tree + } + Internal(internal) => { + let mut out_tree = clone_subtree(internal.first_edge().descend()); + + { + let mut out_node = out_tree.root.push_level().expect("Out of Mem"); + let mut in_edge = internal.first_edge(); + while let Ok(kv) = in_edge.right_kv() { + let (k, v) = kv.into_kv(); + in_edge = kv.right_edge(); + + let k = (*k).clone(); + let v = (*v).clone(); + let subtree = clone_subtree(in_edge.descend()); + + // We can't destructure subtree directly + // because BTreeMap implements Drop + let (subroot, sublength) = unsafe { + let root = ptr::read(&subtree.root); + let length = subtree.length; + mem::forget(subtree); + (root, length) + }; + + out_node.push(k, v, subroot); + out_tree.length += 1 + sublength; + } + } + + out_tree + } + } + } + + if self.len() == 0 { + // Ideally we'd call `BTreeMap::new` here, but that has the `K: + // Ord` constraint, which this method lacks. + BTreeMap { + root: node::Root::shared_empty_root(), + length: 0, + } + } else { + clone_subtree(self.root.as_ref()) + } + } +} + +impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()> +where + K: Borrow<Q> + Ord, + Q: Ord, +{ + type Key = K; + + fn get(&self, key: &Q) -> Option<&K> { + match search::search_tree(self.root.as_ref(), key) { + Found(handle) => Some(handle.into_kv().0), + GoDown(_) => None, + } + } + + fn take(&mut self, key: &Q) -> Option<K> { + match search::search_tree(self.root.as_mut(), key) { + Found(handle) => Some( + OccupiedEntry { + handle, + length: &mut self.length, + _marker: PhantomData, + } + .remove_kv() + .0, + ), + GoDown(_) => None, + } + } + + fn replace(&mut self, key: K) -> Result<Option<K>, TryReserveError> { + self.ensure_root_is_owned()?; + match search::search_tree::<marker::Mut<'_>, K, (), K>(self.root.as_mut(), &key) { + Found(handle) => Ok(Some(mem::replace(handle.into_kv_mut().0, key))), + GoDown(handle) => { + VacantEntry { + key, + handle, + length: &mut self.length, + _marker: PhantomData, + } + .try_insert(())?; + Ok(None) + } + } + } +} + +/// An iterator over the entries of a `BTreeMap`. +/// +/// This `struct` is created by the [`iter`] method on [`BTreeMap`]. See its +/// documentation for more. +/// +/// [`iter`]: struct.BTreeMap.html#method.iter +/// [`BTreeMap`]: struct.BTreeMap.html + +pub struct Iter<'a, K: 'a, V: 'a> { + range: Range<'a, K, V>, + length: usize, +} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +/// A mutable iterator over the entries of a `BTreeMap`. +/// +/// This `struct` is created by the [`iter_mut`] method on [`BTreeMap`]. See its +/// documentation for more. +/// +/// [`iter_mut`]: struct.BTreeMap.html#method.iter_mut +/// [`BTreeMap`]: struct.BTreeMap.html + +#[derive(Debug)] +pub struct IterMut<'a, K: 'a, V: 'a> { + range: RangeMut<'a, K, V>, + length: usize, +} + +/// An owning iterator over the entries of a `BTreeMap`. +/// +/// This `struct` is created by the [`into_iter`] method on [`BTreeMap`][`BTreeMap`] +/// (provided by the `IntoIterator` trait). See its documentation for more. +/// +/// [`into_iter`]: struct.BTreeMap.html#method.into_iter +/// [`BTreeMap`]: struct.BTreeMap.html + +pub struct IntoIter<K, V> { + front: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>, + back: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>, + length: usize, +} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let range = Range { + front: self.front.reborrow(), + back: self.back.reborrow(), + }; + f.debug_list().entries(range).finish() + } +} + +/// An iterator over the keys of a `BTreeMap`. +/// +/// This `struct` is created by the [`keys`] method on [`BTreeMap`]. See its +/// documentation for more. +/// +/// [`keys`]: struct.BTreeMap.html#method.keys +/// [`BTreeMap`]: struct.BTreeMap.html + +pub struct Keys<'a, K: 'a, V: 'a> { + inner: Iter<'a, K, V>, +} + +impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +/// An iterator over the values of a `BTreeMap`. +/// +/// This `struct` is created by the [`values`] method on [`BTreeMap`]. See its +/// documentation for more. +/// +/// [`values`]: struct.BTreeMap.html#method.values +/// [`BTreeMap`]: struct.BTreeMap.html + +pub struct Values<'a, K: 'a, V: 'a> { + inner: Iter<'a, K, V>, +} + +impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +/// A mutable iterator over the values of a `BTreeMap`. +/// +/// This `struct` is created by the [`values_mut`] method on [`BTreeMap`]. See its +/// documentation for more. +/// +/// [`values_mut`]: struct.BTreeMap.html#method.values_mut +/// [`BTreeMap`]: struct.BTreeMap.html + +#[derive(Debug)] +pub struct ValuesMut<'a, K: 'a, V: 'a> { + inner: IterMut<'a, K, V>, +} + +/// An iterator over a sub-range of entries in a `BTreeMap`. +/// +/// This `struct` is created by the [`range`] method on [`BTreeMap`]. See its +/// documentation for more. +/// +/// [`range`]: struct.BTreeMap.html#method.range +/// [`BTreeMap`]: struct.BTreeMap.html + +pub struct Range<'a, K: 'a, V: 'a> { + front: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>, + back: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>, +} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Range<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + +/// A mutable iterator over a sub-range of entries in a `BTreeMap`. +/// +/// This `struct` is created by the [`range_mut`] method on [`BTreeMap`]. See its +/// documentation for more. +/// +/// [`range_mut`]: struct.BTreeMap.html#method.range_mut +/// [`BTreeMap`]: struct.BTreeMap.html + +pub struct RangeMut<'a, K: 'a, V: 'a> { + front: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, + back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, + + // Be invariant in `K` and `V` + _marker: PhantomData<&'a mut (K, V)>, +} + +impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for RangeMut<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let range = Range { + front: self.front.reborrow(), + back: self.back.reborrow(), + }; + f.debug_list().entries(range).finish() + } +} + +/// A view into a single entry in a map, which may either be vacant or occupied. +/// +/// This `enum` is constructed from the [`entry`] method on [`BTreeMap`]. +/// +/// [`BTreeMap`]: struct.BTreeMap.html +/// [`entry`]: struct.BTreeMap.html#method.entry + +pub enum Entry<'a, K: 'a, V: 'a> { + /// A vacant entry. + Vacant(VacantEntry<'a, K, V>), + + /// An occupied entry. + Occupied(OccupiedEntry<'a, K, V>), +} + +impl<K: Debug + Ord, V: Debug> Debug for Entry<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match *self { + Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(), + Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(), + } + } +} + +/// A view into a vacant entry in a `BTreeMap`. +/// It is part of the [`Entry`] enum. +/// +/// [`Entry`]: enum.Entry.html + +pub struct VacantEntry<'a, K: 'a, V: 'a> { + key: K, + handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, + length: &'a mut usize, + + // Be invariant in `K` and `V` + _marker: PhantomData<&'a mut (K, V)>, +} + +impl<K: Debug + Ord, V> Debug for VacantEntry<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("VacantEntry").field(self.key()).finish() + } +} + +/// A view into an occupied entry in a `BTreeMap`. +/// It is part of the [`Entry`] enum. +/// +/// [`Entry`]: enum.Entry.html + +pub struct OccupiedEntry<'a, K: 'a, V: 'a> { + handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>, + + length: &'a mut usize, + + // Be invariant in `K` and `V` + _marker: PhantomData<&'a mut (K, V)>, +} + +impl<K: Debug + Ord, V: Debug> Debug for OccupiedEntry<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("OccupiedEntry") + .field("key", self.key()) + .field("value", self.get()) + .finish() + } +} + +// An iterator for merging two sorted sequences into one +struct MergeIter<K, V, I: Iterator<Item = (K, V)>> { + left: Peekable<I>, + right: Peekable<I>, +} + +impl<K: Ord, V> BTreeMap<K, V> { + /// Makes a new empty BTreeMap with a reasonable choice for B. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// + /// // entries can now be inserted into the empty map + /// map.insert(1, "a"); + /// ``` + + pub fn new() -> BTreeMap<K, V> { + BTreeMap { + root: node::Root::shared_empty_root(), + length: 0, + } + } + + /// Clears the map, removing all values. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "a"); + /// a.clear(); + /// assert!(a.is_empty()); + /// ``` + + pub fn clear(&mut self) { + *self = BTreeMap::new(); + } + + /// Returns a reference to the value corresponding to the key. + /// + /// The key may be any borrowed form of the map's key type, but the ordering + /// on the borrowed form *must* match the ordering on the key type. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// map.insert(1, "a"); + /// assert_eq!(map.get(&1), Some(&"a")); + /// assert_eq!(map.get(&2), None); + /// ``` + + pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> + where + K: Borrow<Q>, + Q: Ord, + { + match search::search_tree(self.root.as_ref(), key) { + Found(handle) => Some(handle.into_kv().1), + GoDown(_) => None, + } + } + + /// Returns the key-value pair corresponding to the supplied key. + /// + /// The supplied key may be any borrowed form of the map's key type, but the ordering + /// on the borrowed form *must* match the ordering on the key type. + /// + /// # Examples + /// + /// ``` + /// #![feature(map_get_key_value)] + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// map.insert(1, "a"); + /// assert_eq!(map.get_key_value(&1), Some((&1, &"a"))); + /// assert_eq!(map.get_key_value(&2), None); + /// ``` + pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)> + where + K: Borrow<Q>, + Q: Ord, + { + match search::search_tree(self.root.as_ref(), k) { + Found(handle) => Some(handle.into_kv()), + GoDown(_) => None, + } + } + + /// Returns `true` if the map contains a value for the specified key. + /// + /// The key may be any borrowed form of the map's key type, but the ordering + /// on the borrowed form *must* match the ordering on the key type. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// map.insert(1, "a"); + /// assert_eq!(map.contains_key(&1), true); + /// assert_eq!(map.contains_key(&2), false); + /// ``` + + #[inline] + pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool + where + K: Borrow<Q>, + Q: Ord, + { + self.get(key).is_some() + } + + /// Returns a mutable reference to the value corresponding to the key. + /// + /// The key may be any borrowed form of the map's key type, but the ordering + /// on the borrowed form *must* match the ordering on the key type. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// map.insert(1, "a"); + /// if let Some(x) = map.get_mut(&1) { + /// *x = "b"; + /// } + /// assert_eq!(map[&1], "b"); + /// ``` + // See `get` for implementation notes, this is basically a copy-paste with mut's added + + pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> + where + K: Borrow<Q>, + Q: Ord, + { + match search::search_tree(self.root.as_mut(), key) { + Found(handle) => Some(handle.into_kv_mut().1), + GoDown(_) => None, + } + } + + /// Inserts a key-value pair into the map. + /// + /// If the map did not have this key present, `None` is returned. + /// + /// If the map did have this key present, the value is updated, and the old + /// value is returned. The key is not updated, though; this matters for + /// types that can be `==` without being identical. See the [module-level + /// documentation] for more. + /// + /// [module-level documentation]: index.html#insert-and-complex-keys + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// assert_eq!(map.insert(37, "a"), None); + /// assert_eq!(map.is_empty(), false); + /// + /// map.insert(37, "b"); + /// assert_eq!(map.insert(37, "c"), Some("b")); + /// assert_eq!(map[&37], "c"); + /// ``` + + pub fn try_insert(&mut self, key: K, value: V) -> Result<Option<V>, TryReserveError> { + match self.try_entry(key)? { + Occupied(mut entry) => Ok(Some(entry.insert(value))), + Vacant(entry) => { + entry.try_insert(value)?; + Ok(None) + } + } + } + + /// Removes a key from the map, returning the value at the key if the key + /// was previously in the map. + /// + /// The key may be any borrowed form of the map's key type, but the ordering + /// on the borrowed form *must* match the ordering on the key type. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// map.insert(1, "a"); + /// assert_eq!(map.remove(&1), Some("a")); + /// assert_eq!(map.remove(&1), None); + /// ``` + + pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> + where + K: Borrow<Q>, + Q: Ord, + { + match search::search_tree(self.root.as_mut(), key) { + Found(handle) => Some( + OccupiedEntry { + handle, + length: &mut self.length, + _marker: PhantomData, + } + .remove(), + ), + GoDown(_) => None, + } + } + + /// Moves all elements from `other` into `Self`, leaving `other` empty. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "a"); + /// a.insert(2, "b"); + /// a.insert(3, "c"); + /// + /// let mut b = BTreeMap::new(); + /// b.insert(3, "d"); + /// b.insert(4, "e"); + /// b.insert(5, "f"); + /// + /// a.append(&mut b); + /// + /// assert_eq!(a.len(), 5); + /// assert_eq!(b.len(), 0); + /// + /// assert_eq!(a[&1], "a"); + /// assert_eq!(a[&2], "b"); + /// assert_eq!(a[&3], "d"); + /// assert_eq!(a[&4], "e"); + /// assert_eq!(a[&5], "f"); + /// ``` + + pub fn append(&mut self, other: &mut Self) { + // Do we have to append anything at all? + if other.len() == 0 { + return; + } + + // We can just swap `self` and `other` if `self` is empty. + if self.len() == 0 { + mem::swap(self, other); + return; + } + + // First, we merge `self` and `other` into a sorted sequence in linear time. + let self_iter = mem::replace(self, BTreeMap::new()).into_iter(); + let other_iter = mem::replace(other, BTreeMap::new()).into_iter(); + let iter = MergeIter { + left: self_iter.peekable(), + right: other_iter.peekable(), + }; + + // Second, we build a tree from the sorted sequence in linear time. + self.from_sorted_iter(iter); + self.fix_right_edge(); + } + + /// Constructs a double-ended iterator over a sub-range of elements in the map. + /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will + /// yield elements from min (inclusive) to max (exclusive). + /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example + /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive + /// range from 4 to 10. + /// + /// # Panics + /// + /// Panics if range `start > end`. + /// Panics if range `start == end` and both bounds are `Excluded`. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// use std::ops::Bound::Included; + /// + /// let mut map = BTreeMap::new(); + /// map.insert(3, "a"); + /// map.insert(5, "b"); + /// map.insert(8, "c"); + /// for (&key, &value) in map.range((Included(&4), Included(&8))) { + /// println!("{}: {}", key, value); + /// } + /// assert_eq!(Some((&5, &"b")), map.range(4..).next()); + /// ``` + + pub fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V> + where + T: Ord, + K: Borrow<T>, + R: RangeBounds<T>, + { + let root1 = self.root.as_ref(); + let root2 = self.root.as_ref(); + let (f, b) = range_search(root1, root2, range); + + Range { front: f, back: b } + } + + /// Constructs a mutable double-ended iterator over a sub-range of elements in the map. + /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will + /// yield elements from min (inclusive) to max (exclusive). + /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example + /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive + /// range from 4 to 10. + /// + /// # Panics + /// + /// Panics if range `start > end`. + /// Panics if range `start == end` and both bounds are `Excluded`. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"] + /// .iter() + /// .map(|&s| (s, 0)) + /// .collect(); + /// for (_, balance) in map.range_mut("B".."Cheryl") { + /// *balance += 100; + /// } + /// for (name, balance) in &map { + /// println!("{} => {}", name, balance); + /// } + /// ``` + + pub fn range_mut<T: ?Sized, R>(&mut self, range: R) -> RangeMut<'_, K, V> + where + T: Ord, + K: Borrow<T>, + R: RangeBounds<T>, + { + let root1 = self.root.as_mut(); + let root2 = unsafe { ptr::read(&root1) }; + let (f, b) = range_search(root1, root2, range); + + RangeMut { + front: f, + back: b, + _marker: PhantomData, + } + } + + /// Gets the given key's corresponding entry in the map for in-place manipulation. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut count: BTreeMap<&str, usize> = BTreeMap::new(); + /// + /// // count the number of occurrences of letters in the vec + /// for x in vec!["a","b","a","c","a","b"] { + /// *count.entry(x).or_insert(0) += 1; + /// } + /// + /// assert_eq!(count["a"], 3); + /// ``` + + pub fn try_entry(&mut self, key: K) -> Result<Entry<'_, K, V>, TryReserveError> { + // FIXME(@porglezomp) Avoid allocating if we don't insert + self.ensure_root_is_owned()?; + Ok(match search::search_tree(self.root.as_mut(), &key) { + Found(handle) => Occupied(OccupiedEntry { + handle, + length: &mut self.length, + _marker: PhantomData, + }), + GoDown(handle) => Vacant(VacantEntry { + key, + handle, + length: &mut self.length, + _marker: PhantomData, + }), + }) + } + + fn from_sorted_iter<I: Iterator<Item = (K, V)>>(&mut self, iter: I) { + self.ensure_root_is_owned().expect("Out Of Mem"); + let mut cur_node = last_leaf_edge(self.root.as_mut()).into_node(); + // Iterate through all key-value pairs, pushing them into nodes at the right level. + for (key, value) in iter { + // Try to push key-value pair into the current leaf node. + if cur_node.len() < node::CAPACITY { + cur_node.push(key, value); + } else { + // No space left, go up and push there. + let mut open_node; + let mut test_node = cur_node.forget_type(); + loop { + match test_node.ascend() { + Ok(parent) => { + let parent = parent.into_node(); + if parent.len() < node::CAPACITY { + // Found a node with space left, push here. + open_node = parent; + break; + } else { + // Go up again. + test_node = parent.forget_type(); + } + } + Err(node) => { + // We are at the top, create a new root node and push there. + open_node = node.into_root_mut().push_level().expect("Out of Mem"); + break; + } + } + } + + // Push key-value pair and new right subtree. + let tree_height = open_node.height() - 1; + let mut right_tree = node::Root::new_leaf().expect("Out of Mem"); + for _ in 0..tree_height { + right_tree.push_level().expect("Out of Mem"); + } + open_node.push(key, value, right_tree); + + // Go down to the right-most leaf again. + cur_node = last_leaf_edge(open_node.forget_type()).into_node(); + } + + self.length += 1; + } + } + + fn fix_right_edge(&mut self) { + // Handle underfull nodes, start from the top. + let mut cur_node = self.root.as_mut(); + while let Internal(internal) = cur_node.force() { + // Check if right-most child is underfull. + let mut last_edge = internal.last_edge(); + let right_child_len = last_edge.reborrow().descend().len(); + if right_child_len < node::MIN_LEN { + // We need to steal. + let mut last_kv = match last_edge.left_kv() { + Ok(left) => left, + Err(_) => unreachable!(), + }; + last_kv.bulk_steal_left(node::MIN_LEN - right_child_len); + last_edge = last_kv.right_edge(); + } + + // Go further down. + cur_node = last_edge.descend(); + } + } + + /// Splits the collection into two at the given key. Returns everything after the given key, + /// including the key. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "a"); + /// a.insert(2, "b"); + /// a.insert(3, "c"); + /// a.insert(17, "d"); + /// a.insert(41, "e"); + /// + /// let b = a.split_off(&3); + /// + /// assert_eq!(a.len(), 2); + /// assert_eq!(b.len(), 3); + /// + /// assert_eq!(a[&1], "a"); + /// assert_eq!(a[&2], "b"); + /// + /// assert_eq!(b[&3], "c"); + /// assert_eq!(b[&17], "d"); + /// assert_eq!(b[&41], "e"); + /// ``` + + pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Result<Self, TryReserveError> + where + K: Borrow<Q>, + { + if self.is_empty() { + return Ok(Self::new()); + } + + let total_num = self.len(); + + let mut right = Self::new(); + right.root = node::Root::new_leaf()?; + for _ in 0..(self.root.as_ref().height()) { + right.root.push_level()?; + } + + { + let mut left_node = self.root.as_mut(); + let mut right_node = right.root.as_mut(); + + loop { + let mut split_edge = match search::search_node(left_node, key) { + // key is going to the right tree + Found(handle) => handle.left_edge(), + GoDown(handle) => handle, + }; + + split_edge.move_suffix(&mut right_node); + + match (split_edge.force(), right_node.force()) { + (Internal(edge), Internal(node)) => { + left_node = edge.descend(); + right_node = node.first_edge().descend(); + } + (Leaf(_), Leaf(_)) => { + break; + } + _ => { + unreachable!(); + } + } + } + } + + self.fix_right_border(); + right.fix_left_border(); + + if self.root.as_ref().height() < right.root.as_ref().height() { + self.recalc_length(); + right.length = total_num - self.len(); + } else { + right.recalc_length(); + self.length = total_num - right.len(); + } + + Ok(right) + } + + /// Calculates the number of elements if it is incorrect. + fn recalc_length(&mut self) { + fn dfs<'a, K, V>(node: NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>) -> usize + where + K: 'a, + V: 'a, + { + let mut res = node.len(); + + if let Internal(node) = node.force() { + let mut edge = node.first_edge(); + loop { + res += dfs(edge.reborrow().descend()); + match edge.right_kv() { + Ok(right_kv) => { + edge = right_kv.right_edge(); + } + Err(_) => { + break; + } + } + } + } + + res + } + + self.length = dfs(self.root.as_ref()); + } + + /// Removes empty levels on the top. + fn fix_top(&mut self) { + loop { + { + let node = self.root.as_ref(); + if node.height() == 0 || node.len() > 0 { + break; + } + } + self.root.pop_level(); + } + } + + fn fix_right_border(&mut self) { + self.fix_top(); + + { + let mut cur_node = self.root.as_mut(); + + while let Internal(node) = cur_node.force() { + let mut last_kv = node.last_kv(); + + if last_kv.can_merge() { + cur_node = last_kv.merge().descend(); + } else { + let right_len = last_kv.reborrow().right_edge().descend().len(); + // `MINLEN + 1` to avoid readjust if merge happens on the next level. + if right_len < node::MIN_LEN + 1 { + last_kv.bulk_steal_left(node::MIN_LEN + 1 - right_len); + } + cur_node = last_kv.right_edge().descend(); + } + } + } + + self.fix_top(); + } + + /// The symmetric clone of `fix_right_border`. + fn fix_left_border(&mut self) { + self.fix_top(); + + { + let mut cur_node = self.root.as_mut(); + + while let Internal(node) = cur_node.force() { + let mut first_kv = node.first_kv(); + + if first_kv.can_merge() { + cur_node = first_kv.merge().descend(); + } else { + let left_len = first_kv.reborrow().left_edge().descend().len(); + if left_len < node::MIN_LEN + 1 { + first_kv.bulk_steal_right(node::MIN_LEN + 1 - left_len); + } + cur_node = first_kv.left_edge().descend(); + } + } + } + + self.fix_top(); + } + + /// If the root node is the shared root node, allocate our own node. + fn ensure_root_is_owned(&mut self) -> Result<(), TryReserveError> { + if self.root.is_shared_root() { + self.root = node::Root::new_leaf()?; + } + Ok(()) + } +} + +impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> { + type Item = (&'a K, &'a V); + type IntoIter = Iter<'a, K, V>; + + fn into_iter(self) -> Iter<'a, K, V> { + self.iter() + } +} + +impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> { + type Item = (&'a K, &'a V); + + #[inline] + fn next(&mut self) -> Option<(&'a K, &'a V)> { + if self.length == 0 { + None + } else { + self.length -= 1; + unsafe { Some(self.range.next_unchecked()) } + } + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + (self.length, Some(self.length)) + } +} + +impl<K, V> FusedIterator for Iter<'_, K, V> {} + +impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> { + fn next_back(&mut self) -> Option<(&'a K, &'a V)> { + if self.length == 0 { + None + } else { + self.length -= 1; + unsafe { Some(self.range.next_back_unchecked()) } + } + } +} + +impl<K, V> ExactSizeIterator for Iter<'_, K, V> { + #[inline(always)] + fn len(&self) -> usize { + self.length + } +} + +impl<K, V> Clone for Iter<'_, K, V> { + fn clone(&self) -> Self { + Iter { + range: self.range.clone(), + length: self.length, + } + } +} + +impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut BTreeMap<K, V> { + type Item = (&'a K, &'a mut V); + type IntoIter = IterMut<'a, K, V>; + + #[inline(always)] + fn into_iter(self) -> IterMut<'a, K, V> { + self.iter_mut() + } +} + +impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> { + type Item = (&'a K, &'a mut V); + + #[inline] + fn next(&mut self) -> Option<(&'a K, &'a mut V)> { + if self.length == 0 { + None + } else { + self.length -= 1; + unsafe { Some(self.range.next_unchecked()) } + } + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + (self.length, Some(self.length)) + } +} + +impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> { + fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { + if self.length == 0 { + None + } else { + self.length -= 1; + unsafe { Some(self.range.next_back_unchecked()) } + } + } +} + +impl<K, V> ExactSizeIterator for IterMut<'_, K, V> { + #[inline(always)] + fn len(&self) -> usize { + self.length + } +} + +impl<K, V> FusedIterator for IterMut<'_, K, V> {} + +impl<K, V> IntoIterator for BTreeMap<K, V> { + type Item = (K, V); + type IntoIter = IntoIter<K, V>; + + fn into_iter(self) -> IntoIter<K, V> { + let root1 = unsafe { ptr::read(&self.root).into_ref() }; + let root2 = unsafe { ptr::read(&self.root).into_ref() }; + let len = self.length; + mem::forget(self); + + IntoIter { + front: first_leaf_edge(root1), + back: last_leaf_edge(root2), + length: len, + } + } +} + +impl<K, V> Drop for IntoIter<K, V> { + fn drop(&mut self) { + self.for_each(drop); + unsafe { + let leaf_node = ptr::read(&self.front).into_node(); + if leaf_node.is_shared_root() { + return; + } + + if let Some(first_parent) = leaf_node.deallocate_and_ascend() { + let mut cur_node = first_parent.into_node(); + while let Some(parent) = cur_node.deallocate_and_ascend() { + cur_node = parent.into_node() + } + } + } + } +} + +impl<K, V> Iterator for IntoIter<K, V> { + type Item = (K, V); + + fn next(&mut self) -> Option<(K, V)> { + if self.length == 0 { + return None; + } else { + self.length -= 1; + } + + let handle = unsafe { ptr::read(&self.front) }; + + let mut cur_handle = match handle.right_kv() { + Ok(kv) => { + let k = unsafe { ptr::read(kv.reborrow().into_kv().0) }; + let v = unsafe { ptr::read(kv.reborrow().into_kv().1) }; + self.front = kv.right_edge(); + return Some((k, v)); + } + Err(last_edge) => unsafe { + unwrap_unchecked(last_edge.into_node().deallocate_and_ascend()) + }, + }; + + loop { + match cur_handle.right_kv() { + Ok(kv) => { + let k = unsafe { ptr::read(kv.reborrow().into_kv().0) }; + let v = unsafe { ptr::read(kv.reborrow().into_kv().1) }; + self.front = first_leaf_edge(kv.right_edge().descend()); + return Some((k, v)); + } + Err(last_edge) => unsafe { + cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend()); + }, + } + } + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + (self.length, Some(self.length)) + } +} + +impl<K, V> DoubleEndedIterator for IntoIter<K, V> { + fn next_back(&mut self) -> Option<(K, V)> { + if self.length == 0 { + return None; + } else { + self.length -= 1; + } + + let handle = unsafe { ptr::read(&self.back) }; + + let mut cur_handle = match handle.left_kv() { + Ok(kv) => { + let k = unsafe { ptr::read(kv.reborrow().into_kv().0) }; + let v = unsafe { ptr::read(kv.reborrow().into_kv().1) }; + self.back = kv.left_edge(); + return Some((k, v)); + } + Err(last_edge) => unsafe { + unwrap_unchecked(last_edge.into_node().deallocate_and_ascend()) + }, + }; + + loop { + match cur_handle.left_kv() { + Ok(kv) => { + let k = unsafe { ptr::read(kv.reborrow().into_kv().0) }; + let v = unsafe { ptr::read(kv.reborrow().into_kv().1) }; + self.back = last_leaf_edge(kv.left_edge().descend()); + return Some((k, v)); + } + Err(last_edge) => unsafe { + cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend()); + }, + } + } + } +} + +impl<K, V> ExactSizeIterator for IntoIter<K, V> { + #[inline(always)] + fn len(&self) -> usize { + self.length + } +} + +impl<K, V> FusedIterator for IntoIter<K, V> {} + +impl<'a, K, V> Iterator for Keys<'a, K, V> { + type Item = &'a K; + + #[inline] + fn next(&mut self) -> Option<&'a K> { + self.inner.next().map(|(k, _)| k) + } + + #[inline(always)] + fn size_hint(&self) -> (usize, Option<usize>) { + self.inner.size_hint() + } +} + +impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> { + #[inline] + fn next_back(&mut self) -> Option<&'a K> { + self.inner.next_back().map(|(k, _)| k) + } +} + +impl<K, V> ExactSizeIterator for Keys<'_, K, V> { + #[inline(always)] + fn len(&self) -> usize { + self.inner.len() + } +} + +impl<K, V> FusedIterator for Keys<'_, K, V> {} + +impl<K, V> Clone for Keys<'_, K, V> { + #[inline(always)] + fn clone(&self) -> Self { + Keys { + inner: self.inner.clone(), + } + } +} + +impl<'a, K, V> Iterator for Values<'a, K, V> { + type Item = &'a V; + + #[inline] + fn next(&mut self) -> Option<&'a V> { + self.inner.next().map(|(_, v)| v) + } + + #[inline(always)] + fn size_hint(&self) -> (usize, Option<usize>) { + self.inner.size_hint() + } +} + +impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> { + #[inline] + fn next_back(&mut self) -> Option<&'a V> { + self.inner.next_back().map(|(_, v)| v) + } +} + +impl<K, V> ExactSizeIterator for Values<'_, K, V> { + #[inline(always)] + fn len(&self) -> usize { + self.inner.len() + } +} + +impl<K, V> FusedIterator for Values<'_, K, V> {} + +impl<K, V> Clone for Values<'_, K, V> { + #[inline(always)] + fn clone(&self) -> Self { + Values { + inner: self.inner.clone(), + } + } +} + +impl<'a, K, V> Iterator for Range<'a, K, V> { + type Item = (&'a K, &'a V); + + #[inline] + fn next(&mut self) -> Option<(&'a K, &'a V)> { + if self.front == self.back { + None + } else { + unsafe { Some(self.next_unchecked()) } + } + } +} + +impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { + type Item = &'a mut V; + + #[inline] + fn next(&mut self) -> Option<&'a mut V> { + self.inner.next().map(|(_, v)| v) + } + + #[inline(always)] + fn size_hint(&self) -> (usize, Option<usize>) { + self.inner.size_hint() + } +} + +impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> { + #[inline] + fn next_back(&mut self) -> Option<&'a mut V> { + self.inner.next_back().map(|(_, v)| v) + } +} + +impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> { + #[inline(always)] + fn len(&self) -> usize { + self.inner.len() + } +} + +impl<K, V> FusedIterator for ValuesMut<'_, K, V> {} + +impl<'a, K, V> Range<'a, K, V> { + unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) { + let handle = self.front; + + let mut cur_handle = match handle.right_kv() { + Ok(kv) => { + let ret = kv.into_kv(); + self.front = kv.right_edge(); + return ret; + } + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + unwrap_unchecked(next_level) + } + }; + + loop { + match cur_handle.right_kv() { + Ok(kv) => { + let ret = kv.into_kv(); + self.front = first_leaf_edge(kv.right_edge().descend()); + return ret; + } + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + cur_handle = unwrap_unchecked(next_level); + } + } + } + } +} + +impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> { + #[inline] + fn next_back(&mut self) -> Option<(&'a K, &'a V)> { + if self.front == self.back { + None + } else { + unsafe { Some(self.next_back_unchecked()) } + } + } +} + +impl<'a, K, V> Range<'a, K, V> { + unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) { + let handle = self.back; + + let mut cur_handle = match handle.left_kv() { + Ok(kv) => { + let ret = kv.into_kv(); + self.back = kv.left_edge(); + return ret; + } + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + unwrap_unchecked(next_level) + } + }; + + loop { + match cur_handle.left_kv() { + Ok(kv) => { + let ret = kv.into_kv(); + self.back = last_leaf_edge(kv.left_edge().descend()); + return ret; + } + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + cur_handle = unwrap_unchecked(next_level); + } + } + } + } +} + +impl<K, V> FusedIterator for Range<'_, K, V> {} + +impl<K, V> Clone for Range<'_, K, V> { + #[inline] + fn clone(&self) -> Self { + Range { + front: self.front, + back: self.back, + } + } +} + +impl<'a, K, V> Iterator for RangeMut<'a, K, V> { + type Item = (&'a K, &'a mut V); + + #[inline] + fn next(&mut self) -> Option<(&'a K, &'a mut V)> { + if self.front == self.back { + None + } else { + unsafe { Some(self.next_unchecked()) } + } + } +} + +impl<'a, K, V> RangeMut<'a, K, V> { + unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) { + let handle = ptr::read(&self.front); + + let mut cur_handle = match handle.right_kv() { + Ok(kv) => { + self.front = ptr::read(&kv).right_edge(); + // Doing the descend invalidates the references returned by `into_kv_mut`, + // so we have to do this last. + let (k, v) = kv.into_kv_mut(); + return (k, v); // coerce k from `&mut K` to `&K` + } + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + unwrap_unchecked(next_level) + } + }; + + loop { + match cur_handle.right_kv() { + Ok(kv) => { + self.front = first_leaf_edge(ptr::read(&kv).right_edge().descend()); + // Doing the descend invalidates the references returned by `into_kv_mut`, + // so we have to do this last. + let (k, v) = kv.into_kv_mut(); + return (k, v); // coerce k from `&mut K` to `&K` + } + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + cur_handle = unwrap_unchecked(next_level); + } + } + } + } +} + +impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> { + #[inline] + fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { + if self.front == self.back { + None + } else { + unsafe { Some(self.next_back_unchecked()) } + } + } +} + +impl<K, V> FusedIterator for RangeMut<'_, K, V> {} + +impl<'a, K, V> RangeMut<'a, K, V> { + unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) { + let handle = ptr::read(&self.back); + + let mut cur_handle = match handle.left_kv() { + Ok(kv) => { + self.back = ptr::read(&kv).left_edge(); + // Doing the descend invalidates the references returned by `into_kv_mut`, + // so we have to do this last. + let (k, v) = kv.into_kv_mut(); + return (k, v); // coerce k from `&mut K` to `&K` + } + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + unwrap_unchecked(next_level) + } + }; + + loop { + match cur_handle.left_kv() { + Ok(kv) => { + self.back = last_leaf_edge(ptr::read(&kv).left_edge().descend()); + // Doing the descend invalidates the references returned by `into_kv_mut`, + // so we have to do this last. + let (k, v) = kv.into_kv_mut(); + return (k, v); // coerce k from `&mut K` to `&K` + } + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + cur_handle = unwrap_unchecked(next_level); + } + } + } + } +} + +impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> { + #[inline] + fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> BTreeMap<K, V> { + let mut map = BTreeMap::new(); + map.extend(iter); + map + } +} + +impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> { + #[inline] + fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) { + iter.into_iter().for_each(move |(k, v)| { + self.try_insert(k, v).expect("Out of Mem"); + }); + } +} + +impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> { + #[inline] + fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) { + self.extend(iter.into_iter().map(|(&key, &value)| (key, value))); + } +} + +impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> { + fn hash<H: Hasher>(&self, state: &mut H) { + for elt in self { + elt.hash(state); + } + } +} + +impl<K: Ord, V> Default for BTreeMap<K, V> { + /// Creates an empty `BTreeMap<K, V>`. + #[inline(always)] + fn default() -> BTreeMap<K, V> { + BTreeMap::new() + } +} + +impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> { + fn eq(&self, other: &BTreeMap<K, V>) -> bool { + self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b) + } +} + +impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {} + +impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> { + #[inline] + fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> { + self.iter().partial_cmp(other.iter()) + } +} + +impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> { + #[inline] + fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering { + self.iter().cmp(other.iter()) + } +} + +impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_map().entries(self.iter()).finish() + } +} + +impl<K: Ord, Q: ?Sized, V> Index<&Q> for BTreeMap<K, V> +where + K: Borrow<Q>, + Q: Ord, +{ + type Output = V; + + /// Returns a reference to the value corresponding to the supplied key. + /// + /// # Panics + /// + /// Panics if the key is not present in the `BTreeMap`. + #[inline] + fn index(&self, key: &Q) -> &V { + self.get(key).expect("no entry found for key") + } +} + +fn first_leaf_edge<BorrowType, K, V>( + mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>, +) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> { + loop { + match node.force() { + Leaf(leaf) => return leaf.first_edge(), + Internal(internal) => { + node = internal.first_edge().descend(); + } + } + } +} + +fn last_leaf_edge<BorrowType, K, V>( + mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>, +) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> { + loop { + match node.force() { + Leaf(leaf) => return leaf.last_edge(), + Internal(internal) => { + node = internal.last_edge().descend(); + } + } + } +} + +fn range_search<BorrowType, K, V, Q: ?Sized, R: RangeBounds<Q>>( + root1: NodeRef<BorrowType, K, V, marker::LeafOrInternal>, + root2: NodeRef<BorrowType, K, V, marker::LeafOrInternal>, + range: R, +) -> ( + Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>, + Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>, +) +where + Q: Ord, + K: Borrow<Q>, +{ + match (range.start_bound(), range.end_bound()) { + (Excluded(s), Excluded(e)) if s == e => { + panic!("range start and end are equal and excluded in BTreeMap") + } + (Included(s), Included(e)) + | (Included(s), Excluded(e)) + | (Excluded(s), Included(e)) + | (Excluded(s), Excluded(e)) + if s > e => + { + panic!("range start is greater than range end in BTreeMap") + } + _ => {} + }; + + let mut min_node = root1; + let mut max_node = root2; + let mut min_found = false; + let mut max_found = false; + let mut diverged = false; + + loop { + let min_edge = match (min_found, range.start_bound()) { + (false, Included(key)) => match search::search_linear(&min_node, key) { + (i, true) => { + min_found = true; + i + } + (i, false) => i, + }, + (false, Excluded(key)) => match search::search_linear(&min_node, key) { + (i, true) => { + min_found = true; + i + 1 + } + (i, false) => i, + }, + (_, Unbounded) => 0, + (true, Included(_)) => min_node.keys().len(), + (true, Excluded(_)) => 0, + }; + + let max_edge = match (max_found, range.end_bound()) { + (false, Included(key)) => match search::search_linear(&max_node, key) { + (i, true) => { + max_found = true; + i + 1 + } + (i, false) => i, + }, + (false, Excluded(key)) => match search::search_linear(&max_node, key) { + (i, true) => { + max_found = true; + i + } + (i, false) => i, + }, + (_, Unbounded) => max_node.keys().len(), + (true, Included(_)) => 0, + (true, Excluded(_)) => max_node.keys().len(), + }; + + if !diverged { + if max_edge < min_edge { + panic!("Ord is ill-defined in BTreeMap range") + } + if min_edge != max_edge { + diverged = true; + } + } + + let front = Handle::new_edge(min_node, min_edge); + let back = Handle::new_edge(max_node, max_edge); + match (front.force(), back.force()) { + (Leaf(f), Leaf(b)) => { + return (f, b); + } + (Internal(min_int), Internal(max_int)) => { + min_node = min_int.descend(); + max_node = max_int.descend(); + } + _ => unreachable!("BTreeMap has different depths"), + }; + } +} + +#[inline(always)] +unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T { + val.unwrap_or_else(|| { + if cfg!(debug_assertions) { + panic!("'unchecked' unwrap on None in BTreeMap"); + } else { + intrinsics::unreachable(); + } + }) +} + +impl<K, V> BTreeMap<K, V> { + /// Gets an iterator over the entries of the map, sorted by key. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// map.insert(3, "c"); + /// map.insert(2, "b"); + /// map.insert(1, "a"); + /// + /// for (key, value) in map.iter() { + /// println!("{}: {}", key, value); + /// } + /// + /// let (first_key, first_value) = map.iter().next().unwrap(); + /// assert_eq!((*first_key, *first_value), (1, "a")); + /// ``` + + pub fn iter(&self) -> Iter<'_, K, V> { + Iter { + range: Range { + front: first_leaf_edge(self.root.as_ref()), + back: last_leaf_edge(self.root.as_ref()), + }, + length: self.length, + } + } + + /// Gets a mutable iterator over the entries of the map, sorted by key. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// map.insert("a", 1); + /// map.insert("b", 2); + /// map.insert("c", 3); + /// + /// // add 10 to the value if the key isn't "a" + /// for (key, value) in map.iter_mut() { + /// if key != &"a" { + /// *value += 10; + /// } + /// } + /// ``` + + pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { + let root1 = self.root.as_mut(); + let root2 = unsafe { ptr::read(&root1) }; + IterMut { + range: RangeMut { + front: first_leaf_edge(root1), + back: last_leaf_edge(root2), + _marker: PhantomData, + }, + length: self.length, + } + } + + /// Gets an iterator over the keys of the map, in sorted order. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(2, "b"); + /// a.insert(1, "a"); + /// + /// let keys: Vec<_> = a.keys().cloned().collect(); + /// assert_eq!(keys, [1, 2]); + /// ``` + + #[inline(always)] + pub fn keys<'a>(&'a self) -> Keys<'a, K, V> { + Keys { inner: self.iter() } + } + + /// Gets an iterator over the values of the map, in order by key. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, "hello"); + /// a.insert(2, "goodbye"); + /// + /// let values: Vec<&str> = a.values().cloned().collect(); + /// assert_eq!(values, ["hello", "goodbye"]); + /// ``` + + #[inline(always)] + pub fn values<'a>(&'a self) -> Values<'a, K, V> { + Values { inner: self.iter() } + } + + /// Gets a mutable iterator over the values of the map, in order by key. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1, String::from("hello")); + /// a.insert(2, String::from("goodbye")); + /// + /// for value in a.values_mut() { + /// value.push_str("!"); + /// } + /// + /// let values: Vec<String> = a.values().cloned().collect(); + /// assert_eq!(values, [String::from("hello!"), + /// String::from("goodbye!")]); + /// ``` + + #[inline(always)] + pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> { + ValuesMut { + inner: self.iter_mut(), + } + } + + /// Returns the number of elements in the map. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// assert_eq!(a.len(), 0); + /// a.insert(1, "a"); + /// assert_eq!(a.len(), 1); + /// ``` + + #[inline(always)] + pub fn len(&self) -> usize { + self.length + } + + /// Returns `true` if the map contains no elements. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// assert!(a.is_empty()); + /// a.insert(1, "a"); + /// assert!(!a.is_empty()); + /// ``` + + #[inline(always)] + pub fn is_empty(&self) -> bool { + self.len() == 0 + } +} + +impl<'a, K: Ord, V> Entry<'a, K, V> { + /// Ensures a value is in the entry by inserting the default if empty, and returns + /// a mutable reference to the value in the entry. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); + /// map.entry("poneyland").or_insert(12); + /// + /// assert_eq!(map["poneyland"], 12); + /// ``` + + pub fn or_try_insert(self, default: V) -> Result<&'a mut V, TryReserveError> { + match self { + Occupied(entry) => Ok(entry.into_mut()), + Vacant(entry) => entry.try_insert(default), + } + } + + /// 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. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map: BTreeMap<&str, String> = BTreeMap::new(); + /// let s = "hoho".to_string(); + /// + /// map.entry("poneyland").or_insert_with(|| s); + /// + /// assert_eq!(map["poneyland"], "hoho".to_string()); + /// ``` + + pub fn or_try_insert_with<F: FnOnce() -> V>( + self, + default: F, + ) -> Result<&'a mut V, TryReserveError> { + match self { + Occupied(entry) => Ok(entry.into_mut()), + Vacant(entry) => entry.try_insert(default()), + } + } + + /// Returns a reference to this entry's key. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); + /// assert_eq!(map.entry("poneyland").key(), &"poneyland"); + /// ``` + + #[inline] + pub fn key(&self) -> &K { + match *self { + Occupied(ref entry) => entry.key(), + Vacant(ref entry) => entry.key(), + } + } + + /// Provides in-place mutable access to an occupied entry before any + /// potential inserts into the map. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); + /// + /// map.entry("poneyland") + /// .and_modify(|e| { *e += 1 }) + /// .or_insert(42); + /// assert_eq!(map["poneyland"], 42); + /// + /// map.entry("poneyland") + /// .and_modify(|e| { *e += 1 }) + /// .or_insert(42); + /// assert_eq!(map["poneyland"], 43); + /// ``` + + pub fn and_modify<F>(self, f: F) -> Self + where + F: FnOnce(&mut V), + { + match self { + Occupied(mut entry) => { + f(entry.get_mut()); + Occupied(entry) + } + Vacant(entry) => Vacant(entry), + } + } +} + +impl<'a, K: Ord, V: Default> Entry<'a, K, V> { + /// Ensures a value is in the entry by inserting the default value if empty, + /// and returns a mutable reference to the value in the entry. + /// + /// # Examples + /// + /// ``` + /// # fn main() { + /// use std::collections::BTreeMap; + /// + /// let mut map: BTreeMap<&str, Option<usize>> = BTreeMap::new(); + /// map.entry("poneyland").or_default(); + /// + /// assert_eq!(map["poneyland"], None); + /// # } + /// ``` + pub fn or_default(self) -> Result<&'a mut V, TryReserveError> { + match self { + Occupied(entry) => Ok(entry.into_mut()), + Vacant(entry) => entry.try_insert(Default::default()), + } + } +} + +impl<'a, K: Ord, V> VacantEntry<'a, K, V> { + /// Gets a reference to the key that would be used when inserting a value + /// through the VacantEntry. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); + /// assert_eq!(map.entry("poneyland").key(), &"poneyland"); + /// ``` + + #[inline(always)] + pub fn key(&self) -> &K { + &self.key + } + + /// Take ownership of the key. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// use std::collections::btree_map::Entry; + /// + /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); + /// + /// if let Entry::Vacant(v) = map.entry("poneyland") { + /// v.into_key(); + /// } + /// ``` + #[inline(always)] + pub fn into_key(self) -> K { + self.key + } + + /// Sets the value of the entry with the `VacantEntry`'s key, + /// and returns a mutable reference to it. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut count: BTreeMap<&str, usize> = BTreeMap::new(); + /// + /// // count the number of occurrences of letters in the vec + /// for x in vec!["a","b","a","c","a","b"] { + /// *count.entry(x).or_insert(0) += 1; + /// } + /// + /// assert_eq!(count["a"], 3); + /// ``` + + pub fn try_insert(self, value: V) -> Result<&'a mut V, TryReserveError> { + *self.length += 1; + + let out_ptr; + + let mut ins_k; + let mut ins_v; + let mut ins_edge; + + let mut cur_parent = match self.handle.insert(self.key, value)? { + (Fit(handle), _) => return Ok(handle.into_kv_mut().1), + (Split(left, k, v, right), ptr) => { + ins_k = k; + ins_v = v; + ins_edge = right; + out_ptr = ptr; + left.ascend().map_err(|n| n.into_root_mut()) + } + }; + + loop { + match cur_parent { + Ok(parent) => match parent.insert(ins_k, ins_v, ins_edge)? { + Fit(_) => return Ok(unsafe { &mut *out_ptr }), + Split(left, k, v, right) => { + ins_k = k; + ins_v = v; + ins_edge = right; + cur_parent = left.ascend().map_err(|n| n.into_root_mut()); + } + }, + Err(root) => { + root.push_level()?.push(ins_k, ins_v, ins_edge); + return Ok(unsafe { &mut *out_ptr }); + } + } + } + } +} + +impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> { + /// Gets a reference to the key in the entry. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); + /// map.entry("poneyland").or_insert(12); + /// assert_eq!(map.entry("poneyland").key(), &"poneyland"); + /// ``` + + #[inline] + pub fn key(&self) -> &K { + self.handle.reborrow().into_kv().0 + } + + /// Take ownership of the key and value from the map. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// use std::collections::btree_map::Entry; + /// + /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); + /// map.entry("poneyland").or_insert(12); + /// + /// if let Entry::Occupied(o) = map.entry("poneyland") { + /// // We delete the entry from the map. + /// o.remove_entry(); + /// } + /// + /// // If now try to get the value, it will panic: + /// // println!("{}", map["poneyland"]); + /// ``` + + #[inline] + pub fn remove_entry(self) -> (K, V) { + self.remove_kv() + } + + /// Gets a reference to the value in the entry. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// use std::collections::btree_map::Entry; + /// + /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); + /// map.entry("poneyland").or_insert(12); + /// + /// if let Entry::Occupied(o) = map.entry("poneyland") { + /// assert_eq!(o.get(), &12); + /// } + /// ``` + + #[inline] + pub fn get(&self) -> &V { + self.handle.reborrow().into_kv().1 + } + + /// Gets a mutable reference to the value in the entry. + /// + /// If you need a reference to the `OccupiedEntry` that may outlive the + /// destruction of the `Entry` value, see [`into_mut`]. + /// + /// [`into_mut`]: #method.into_mut + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// use std::collections::btree_map::Entry; + /// + /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); + /// map.entry("poneyland").or_insert(12); + /// + /// assert_eq!(map["poneyland"], 12); + /// if let Entry::Occupied(mut o) = map.entry("poneyland") { + /// *o.get_mut() += 10; + /// assert_eq!(*o.get(), 22); + /// + /// // We can use the same Entry multiple times. + /// *o.get_mut() += 2; + /// } + /// assert_eq!(map["poneyland"], 24); + /// ``` + #[inline] + pub fn get_mut(&mut self) -> &mut V { + self.handle.kv_mut().1 + } + + /// Converts the entry into a mutable reference to its value. + /// + /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`]. + /// + /// [`get_mut`]: #method.get_mut + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// use std::collections::btree_map::Entry; + /// + /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); + /// map.entry("poneyland").or_insert(12); + /// + /// assert_eq!(map["poneyland"], 12); + /// if let Entry::Occupied(o) = map.entry("poneyland") { + /// *o.into_mut() += 10; + /// } + /// assert_eq!(map["poneyland"], 22); + /// ``` + #[inline] + pub fn into_mut(self) -> &'a mut V { + self.handle.into_kv_mut().1 + } + + /// Sets the value of the entry with the `OccupiedEntry`'s key, + /// and returns the entry's old value. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// use std::collections::btree_map::Entry; + /// + /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); + /// map.entry("poneyland").or_insert(12); + /// + /// if let Entry::Occupied(mut o) = map.entry("poneyland") { + /// assert_eq!(o.insert(15), 12); + /// } + /// assert_eq!(map["poneyland"], 15); + /// ``` + #[inline] + pub fn insert(&mut self, value: V) -> V { + mem::replace(self.get_mut(), value) + } + + /// Takes the value of the entry out of the map, and returns it. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// use std::collections::btree_map::Entry; + /// + /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); + /// map.entry("poneyland").or_insert(12); + /// + /// if let Entry::Occupied(o) = map.entry("poneyland") { + /// assert_eq!(o.remove(), 12); + /// } + /// // If we try to get "poneyland"'s value, it'll panic: + /// // println!("{}", map["poneyland"]); + /// ``` + #[inline] + pub fn remove(self) -> V { + self.remove_kv().1 + } + + fn remove_kv(self) -> (K, V) { + *self.length -= 1; + + let (small_leaf, old_key, old_val) = match self.handle.force() { + Leaf(leaf) => { + let (hole, old_key, old_val) = leaf.remove(); + (hole.into_node(), old_key, old_val) + } + Internal(mut internal) => { + let key_loc = internal.kv_mut().0 as *mut K; + let val_loc = internal.kv_mut().1 as *mut V; + + let to_remove = first_leaf_edge(internal.right_edge().descend()) + .right_kv() + .ok(); + let to_remove = unsafe { unwrap_unchecked(to_remove) }; + + let (hole, key, val) = to_remove.remove(); + + let old_key = unsafe { mem::replace(&mut *key_loc, key) }; + let old_val = unsafe { mem::replace(&mut *val_loc, val) }; + + (hole.into_node(), old_key, old_val) + } + }; + + // Handle underflow + let mut cur_node = small_leaf.forget_type(); + while cur_node.len() < node::CAPACITY / 2 { + match handle_underfull_node(cur_node) { + AtRoot => break, + EmptyParent(_) => unreachable!(), + Merged(parent) => { + if parent.len() == 0 { + // We must be at the root + parent.into_root_mut().pop_level(); + break; + } else { + cur_node = parent.forget_type(); + } + } + Stole(_) => break, + } + } + + (old_key, old_val) + } +} + +enum UnderflowResult<'a, K, V> { + AtRoot, + EmptyParent(NodeRef<marker::Mut<'a>, K, V, marker::Internal>), + Merged(NodeRef<marker::Mut<'a>, K, V, marker::Internal>), + Stole(NodeRef<marker::Mut<'a>, K, V, marker::Internal>), +} + +fn handle_underfull_node<'a, K, V>( + node: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, +) -> UnderflowResult<'a, K, V> { + let parent = if let Ok(parent) = node.ascend() { + parent + } else { + return AtRoot; + }; + + let (is_left, mut handle) = match parent.left_kv() { + Ok(left) => (true, left), + Err(parent) => match parent.right_kv() { + Ok(right) => (false, right), + Err(parent) => { + return EmptyParent(parent.into_node()); + } + }, + }; + + if handle.can_merge() { + Merged(handle.merge().into_node()) + } else { + if is_left { + handle.steal_left(); + } else { + handle.steal_right(); + } + Stole(handle.into_node()) + } +} + +impl<K: Ord, V, I: Iterator<Item = (K, V)>> Iterator for MergeIter<K, V, I> { + type Item = (K, V); + + fn next(&mut self) -> Option<(K, V)> { + let res = match (self.left.peek(), self.right.peek()) { + (Some(&(ref left_key, _)), Some(&(ref right_key, _))) => left_key.cmp(right_key), + (Some(_), None) => Ordering::Less, + (None, Some(_)) => Ordering::Greater, + (None, None) => return None, + }; + + // Check which elements comes first and only advance the corresponding iterator. + // If two keys are equal, take the value from `right`. + match res { + Ordering::Less => self.left.next(), + Ordering::Greater => self.right.next(), + Ordering::Equal => { + self.left.next(); + self.right.next() + } + } + } +} diff --git a/third_party/rust/fallible_collections/src/btree/node.rs b/third_party/rust/fallible_collections/src/btree/node.rs new file mode 100644 index 0000000000..249aeb6598 --- /dev/null +++ b/third_party/rust/fallible_collections/src/btree/node.rs @@ -0,0 +1,1676 @@ +// This is an attempt at an implementation following the ideal +// +// ``` +// struct BTreeMap<K, V> { +// height: usize, +// root: Option<Box<Node<K, V, height>>> +// } +// +// struct Node<K, V, height: usize> { +// keys: [K; 2 * B - 1], +// vals: [V; 2 * B - 1], +// edges: if height > 0 { +// [Box<Node<K, V, height - 1>>; 2 * B] +// } else { () }, +// parent: *const Node<K, V, height + 1>, +// parent_idx: u16, +// len: u16, +// } +// ``` +// +// Since Rust doesn't actually have dependent types and polymorphic recursion, +// we make do with lots of unsafety. + +// A major goal of this module is to avoid complexity by treating the tree as a generic (if +// weirdly shaped) container and avoiding dealing with most of the B-Tree invariants. As such, +// this module doesn't care whether the entries are sorted, which nodes can be underfull, or +// even what underfull means. However, we do rely on a few invariants: +// +// - Trees must have uniform depth/height. This means that every path down to a leaf from a +// given node has exactly the same length. +// - A node of length `n` has `n` keys, `n` values, and (in an internal node) `n + 1` edges. +// This implies that even an empty internal node has at least one edge. + +use core::marker::PhantomData; +use core::mem::{self, MaybeUninit}; +use core::ptr::{self, NonNull, Unique}; +use core::slice; + +use crate::boxed::FallibleBox; +use crate::TryReserveError; +use alloc::alloc::{Allocator, Global, Layout}; +use alloc::boxed::Box; + +const B: usize = 6; +pub const MIN_LEN: usize = B - 1; +pub const CAPACITY: usize = 2 * B - 1; + +/// The underlying representation of leaf nodes. Note that it is often unsafe to actually store +/// these, since only the first `len` keys and values are assumed to be initialized. As such, +/// these should always be put behind pointers, and specifically behind `BoxedNode` in the owned +/// case. +/// +/// We have a separate type for the header and rely on it matching the prefix of `LeafNode`, in +/// order to statically allocate a single dummy node to avoid allocations. This struct is +/// `repr(C)` to prevent them from being reordered. `LeafNode` does not just contain a +/// `NodeHeader` because we do not want unnecessary padding between `len` and the keys. +/// Crucially, `NodeHeader` can be safely transmuted to different K and V. (This is exploited +/// by `as_header`.) +/// See `into_key_slice` for an explanation of K2. K2 cannot be safely transmuted around +/// because the size of `NodeHeader` depends on its alignment! +#[repr(C)] +struct NodeHeader<K, V, K2 = ()> { + /// We use `*const` as opposed to `*mut` so as to be covariant in `K` and `V`. + /// This either points to an actual node or is null. + parent: *const InternalNode<K, V>, + + /// This node's index into the parent node's `edges` array. + /// `*node.parent.edges[node.parent_idx]` should be the same thing as `node`. + /// This is only guaranteed to be initialized when `parent` is non-null. + parent_idx: MaybeUninit<u16>, + + /// The number of keys and values this node stores. + /// + /// This next to `parent_idx` to encourage the compiler to join `len` and + /// `parent_idx` into the same 32-bit word, reducing space overhead. + len: u16, + + /// See `into_key_slice`. + keys_start: [K2; 0], +} +#[repr(C)] +struct LeafNode<K, V> { + /// We use `*const` as opposed to `*mut` so as to be covariant in `K` and `V`. + /// This either points to an actual node or is null. + parent: *const InternalNode<K, V>, + + /// This node's index into the parent node's `edges` array. + /// `*node.parent.edges[node.parent_idx]` should be the same thing as `node`. + /// This is only guaranteed to be initialized when `parent` is non-null. + parent_idx: MaybeUninit<u16>, + + /// The number of keys and values this node stores. + /// + /// This next to `parent_idx` to encourage the compiler to join `len` and + /// `parent_idx` into the same 32-bit word, reducing space overhead. + len: u16, + + /// The arrays storing the actual data of the node. Only the first `len` elements of each + /// array are initialized and valid. + keys: [MaybeUninit<K>; CAPACITY], + vals: [MaybeUninit<V>; CAPACITY], +} + +impl<K, V> LeafNode<K, V> { + /// Creates a new `LeafNode`. Unsafe because all nodes should really be hidden behind + /// `BoxedNode`, preventing accidental dropping of uninitialized keys and values. + unsafe fn new() -> Self { + LeafNode { + // As a general policy, we leave fields uninitialized if they can be, as this should + // be both slightly faster and easier to track in Valgrind. + keys: MaybeUninit::uninit_array::<CAPACITY>(), + vals: MaybeUninit::uninit_array::<CAPACITY>(), + parent: ptr::null(), + parent_idx: MaybeUninit::uninit(), + len: 0, + } + } +} + +impl<K, V> NodeHeader<K, V> { + fn is_shared_root(&self) -> bool { + ptr::eq(self, &EMPTY_ROOT_NODE as *const _ as *const _) + } +} + +// We need to implement Sync here in order to make a static instance. +unsafe impl Sync for NodeHeader<(), ()> {} + +// An empty node used as a placeholder for the root node, to avoid allocations. +// We use just a header in order to save space, since no operation on an empty tree will +// ever take a pointer past the first key. +static EMPTY_ROOT_NODE: NodeHeader<(), ()> = NodeHeader { + parent: ptr::null(), + parent_idx: MaybeUninit::uninit(), + len: 0, + keys_start: [], +}; + +/// The underlying representation of internal nodes. As with `LeafNode`s, these should be hidden +/// behind `BoxedNode`s to prevent dropping uninitialized keys and values. Any pointer to an +/// `InternalNode` can be directly casted to a pointer to the underlying `LeafNode` portion of the +/// node, allowing code to act on leaf and internal nodes generically without having to even check +/// which of the two a pointer is pointing at. This property is enabled by the use of `repr(C)`. +#[repr(C)] +struct InternalNode<K, V> { + data: LeafNode<K, V>, + + /// The pointers to the children of this node. `len + 1` of these are considered + /// initialized and valid. + edges: [MaybeUninit<BoxedNode<K, V>>; 2 * B], +} + +impl<K, V> InternalNode<K, V> { + /// Creates a new `InternalNode`. + /// + /// This is unsafe for two reasons. First, it returns an `InternalNode` by value, risking + /// dropping of uninitialized fields. Second, an invariant of internal nodes is that `len + 1` + /// edges are initialized and valid, meaning that even when the node is empty (having a + /// `len` of 0), there must be one initialized and valid edge. This function does not set up + /// such an edge. + unsafe fn new() -> Self { + InternalNode { + data: LeafNode::new(), + edges: MaybeUninit::uninit_array::<{ 2 * B }>(), + } + } +} + +/// An owned pointer to a node. This basically is either `Box<LeafNode<K, V>>` or +/// `Box<InternalNode<K, V>>`. However, it contains no information as to which of the two types +/// of nodes is actually behind the box, and, partially due to this lack of information, has no +/// destructor. +struct BoxedNode<K, V> { + ptr: Unique<LeafNode<K, V>>, +} + +impl<K, V> BoxedNode<K, V> { + fn from_leaf(node: Box<LeafNode<K, V>>) -> Self { + let (ptr, _g) = Box::into_unique(node); + BoxedNode { ptr: ptr } + } + + fn from_internal(node: Box<InternalNode<K, V>>) -> Self { + unsafe { + BoxedNode { + ptr: Unique::new_unchecked(Box::into_raw(node) as *mut LeafNode<K, V>), + } + } + } + + unsafe fn from_ptr(ptr: NonNull<LeafNode<K, V>>) -> Self { + BoxedNode { + ptr: Unique::new_unchecked(ptr.as_ptr()), + } + } + + fn as_ptr(&self) -> NonNull<LeafNode<K, V>> { + NonNull::from(self.ptr) + } +} + +/// An owned tree. Note that despite being owned, this does not have a destructor, +/// and must be cleaned up manually. +pub struct Root<K, V> { + node: BoxedNode<K, V>, + height: usize, +} + +unsafe impl<K: Sync, V: Sync> Sync for Root<K, V> {} +unsafe impl<K: Send, V: Send> Send for Root<K, V> {} + +impl<K, V> Root<K, V> { + pub fn is_shared_root(&self) -> bool { + self.as_ref().is_shared_root() + } + + pub fn shared_empty_root() -> Self { + Root { + node: unsafe { + BoxedNode::from_ptr(NonNull::new_unchecked( + &EMPTY_ROOT_NODE as *const _ as *const LeafNode<K, V> as *mut _, + )) + }, + height: 0, + } + } + + pub fn new_leaf() -> Result<Self, TryReserveError> { + Ok(Root { + node: BoxedNode::from_leaf(<Box<_> as FallibleBox<_>>::try_new(unsafe { + LeafNode::new() + })?), + height: 0, + }) + } + + pub fn as_ref(&self) -> NodeRef<marker::Immut<'_>, K, V, marker::LeafOrInternal> { + NodeRef { + height: self.height, + node: self.node.as_ptr(), + root: self as *const _ as *mut _, + _marker: PhantomData, + } + } + + pub fn as_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::LeafOrInternal> { + NodeRef { + height: self.height, + node: self.node.as_ptr(), + root: self as *mut _, + _marker: PhantomData, + } + } + + pub fn into_ref(self) -> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> { + NodeRef { + height: self.height, + node: self.node.as_ptr(), + root: ptr::null_mut(), // FIXME: Is there anything better to do here? + _marker: PhantomData, + } + } + + /// Adds a new internal node with a single edge, pointing to the previous root, and make that + /// new node the root. This increases the height by 1 and is the opposite of `pop_level`. + pub fn push_level( + &mut self, + ) -> Result<NodeRef<marker::Mut<'_>, K, V, marker::Internal>, TryReserveError> { + debug_assert!(!self.is_shared_root()); + let mut new_node = <Box<_> as FallibleBox<_>>::try_new(unsafe { InternalNode::new() })?; + new_node.edges[0].write(unsafe { BoxedNode::from_ptr(self.node.as_ptr()) }); + + self.node = BoxedNode::from_internal(new_node); + self.height += 1; + + let mut ret = NodeRef { + height: self.height, + node: self.node.as_ptr(), + root: self as *mut _, + _marker: PhantomData, + }; + + unsafe { + ret.reborrow_mut().first_edge().correct_parent_link(); + } + + Ok(ret) + } + + /// Removes the root node, using its first child as the new root. This cannot be called when + /// the tree consists only of a leaf node. As it is intended only to be called when the root + /// has only one edge, no cleanup is done on any of the other children are elements of the root. + /// This decreases the height by 1 and is the opposite of `push_level`. + pub fn pop_level(&mut self) { + debug_assert!(self.height > 0); + + let top = self.node.ptr; + + self.node = unsafe { + BoxedNode::from_ptr( + self.as_mut() + .cast_unchecked::<marker::Internal>() + .first_edge() + .descend() + .node, + ) + }; + self.height -= 1; + unsafe { + (*self.as_mut().as_leaf_mut()).parent = ptr::null(); + } + + unsafe { + Global.deallocate( + NonNull::from(top).cast(), + Layout::new::<InternalNode<K, V>>(), + ); + } + } +} + +// N.B. `NodeRef` is always covariant in `K` and `V`, even when the `BorrowType` +// is `Mut`. This is technically wrong, but cannot result in any unsafety due to +// internal use of `NodeRef` because we stay completely generic over `K` and `V`. +// However, whenever a public type wraps `NodeRef`, make sure that it has the +// correct variance. +/// A reference to a node. +/// +/// This type has a number of parameters that controls how it acts: +/// - `BorrowType`: This can be `Immut<'a>` or `Mut<'a>` for some `'a` or `Owned`. +/// When this is `Immut<'a>`, the `NodeRef` acts roughly like `&'a Node`, +/// when this is `Mut<'a>`, the `NodeRef` acts roughly like `&'a mut Node`, +/// and when this is `Owned`, the `NodeRef` acts roughly like `Box<Node>`. +/// - `K` and `V`: These control what types of things are stored in the nodes. +/// - `Type`: This can be `Leaf`, `Internal`, or `LeafOrInternal`. When this is +/// `Leaf`, the `NodeRef` points to a leaf node, when this is `Internal` the +/// `NodeRef` points to an internal node, and when this is `LeafOrInternal` the +/// `NodeRef` could be pointing to either type of node. +/// Note that in case of a leaf node, this might still be the shared root! Only turn +/// this into a `LeafNode` reference if you know it is not a root! Shared references +/// must be dereferencable *for the entire size of their pointee*, so `&InternalNode` +/// pointing to the shared root is UB. +/// Turning this into a `NodeHeader` is always safe. +pub struct NodeRef<BorrowType, K, V, Type> { + height: usize, + node: NonNull<LeafNode<K, V>>, + // This is null unless the borrow type is `Mut` + root: *const Root<K, V>, + _marker: PhantomData<(BorrowType, Type)>, +} + +impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<marker::Immut<'a>, K, V, Type> {} +impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> { + fn clone(&self) -> Self { + *self + } +} + +unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync for NodeRef<BorrowType, K, V, Type> {} + +unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send for NodeRef<marker::Immut<'a>, K, V, Type> {} +unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::Mut<'a>, K, V, Type> {} +unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {} + +impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> { + fn as_internal(&self) -> &InternalNode<K, V> { + unsafe { &*(self.node.as_ptr() as *mut InternalNode<K, V>) } + } +} + +impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { + fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> { + unsafe { &mut *(self.node.as_ptr() as *mut InternalNode<K, V>) } + } +} + +impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> { + /// Finds the length of the node. This is the number of keys or values. In an + /// internal node, the number of edges is `len() + 1`. + pub fn len(&self) -> usize { + self.as_header().len as usize + } + + /// Returns the height of this node in the whole tree. Zero height denotes the + /// leaf level. + pub fn height(&self) -> usize { + self.height + } + + /// Removes any static information about whether this node is a `Leaf` or an + /// `Internal` node. + pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { + NodeRef { + height: self.height, + node: self.node, + root: self.root, + _marker: PhantomData, + } + } + + /// Temporarily takes out another, immutable reference to the same node. + fn reborrow<'a>(&'a self) -> NodeRef<marker::Immut<'a>, K, V, Type> { + NodeRef { + height: self.height, + node: self.node, + root: self.root, + _marker: PhantomData, + } + } + + /// Assert that this is indeed a proper leaf node, and not the shared root. + unsafe fn as_leaf(&self) -> &LeafNode<K, V> { + self.node.as_ref() + } + + fn as_header(&self) -> &NodeHeader<K, V> { + unsafe { &*(self.node.as_ptr() as *const NodeHeader<K, V>) } + } + + pub fn is_shared_root(&self) -> bool { + self.as_header().is_shared_root() + } + + pub fn keys(&self) -> &[K] { + self.reborrow().into_key_slice() + } + + fn vals(&self) -> &[V] { + self.reborrow().into_val_slice() + } + + /// Finds the parent of the current node. Returns `Ok(handle)` if the current + /// node actually has a parent, where `handle` points to the edge of the parent + /// that points to the current node. Returns `Err(self)` if the current node has + /// no parent, giving back the original `NodeRef`. + /// + /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should + /// both, upon success, do nothing. + pub fn ascend( + self, + ) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> { + let parent_as_leaf = self.as_header().parent as *const LeafNode<K, V>; + if let Some(non_zero) = NonNull::new(parent_as_leaf as *mut _) { + Ok(Handle { + node: NodeRef { + height: self.height + 1, + node: non_zero, + root: self.root, + _marker: PhantomData, + }, + idx: unsafe { usize::from(*self.as_header().parent_idx.as_ptr()) }, + _marker: PhantomData, + }) + } else { + Err(self) + } + } + + pub fn first_edge(self) -> Handle<Self, marker::Edge> { + Handle::new_edge(self, 0) + } + + pub fn last_edge(self) -> Handle<Self, marker::Edge> { + let len = self.len(); + Handle::new_edge(self, len) + } + + /// Note that `self` must be nonempty. + pub fn first_kv(self) -> Handle<Self, marker::KV> { + debug_assert!(self.len() > 0); + Handle::new_kv(self, 0) + } + + /// Note that `self` must be nonempty. + pub fn last_kv(self) -> Handle<Self, marker::KV> { + let len = self.len(); + debug_assert!(len > 0); + Handle::new_kv(self, len - 1) + } +} + +impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> { + /// Similar to `ascend`, gets a reference to a node's parent node, but also + /// deallocate the current node in the process. This is unsafe because the + /// current node will still be accessible despite being deallocated. + pub unsafe fn deallocate_and_ascend( + self, + ) -> Option<Handle<NodeRef<marker::Owned, K, V, marker::Internal>, marker::Edge>> { + debug_assert!(!self.is_shared_root()); + let node = self.node; + let ret = self.ascend().ok(); + Global.deallocate(node.cast(), Layout::new::<LeafNode<K, V>>()); + ret + } +} + +impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> { + /// Similar to `ascend`, gets a reference to a node's parent node, but also + /// deallocate the current node in the process. This is unsafe because the + /// current node will still be accessible despite being deallocated. + pub unsafe fn deallocate_and_ascend( + self, + ) -> Option<Handle<NodeRef<marker::Owned, K, V, marker::Internal>, marker::Edge>> { + let node = self.node; + let ret = self.ascend().ok(); + Global.deallocate(node.cast(), Layout::new::<InternalNode<K, V>>()); + ret + } +} + +impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> { + /// Unsafely asserts to the compiler some static information about whether this + /// node is a `Leaf`. + unsafe fn cast_unchecked<NewType>(&mut self) -> NodeRef<marker::Mut<'_>, K, V, NewType> { + NodeRef { + height: self.height, + node: self.node, + root: self.root, + _marker: PhantomData, + } + } + + /// Temporarily takes out another, mutable reference to the same node. Beware, as + /// this method is very dangerous, doubly so since it may not immediately appear + /// dangerous. + /// + /// Because mutable pointers can roam anywhere around the tree and can even (through + /// `into_root_mut`) mess with the root of the tree, the result of `reborrow_mut` + /// can easily be used to make the original mutable pointer dangling, or, in the case + /// of a reborrowed handle, out of bounds. + // FIXME(@gereeter) consider adding yet another type parameter to `NodeRef` that restricts + // the use of `ascend` and `into_root_mut` on reborrowed pointers, preventing this unsafety. + unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> { + NodeRef { + height: self.height, + node: self.node, + root: self.root, + _marker: PhantomData, + } + } + + /// Returns a raw ptr to avoid asserting exclusive access to the entire node. + fn as_leaf_mut(&mut self) -> *mut LeafNode<K, V> { + // We are mutable, so we cannot be the root, so accessing this as a leaf is okay. + self.node.as_ptr() + } + + fn keys_mut(&mut self) -> &mut [K] { + unsafe { self.reborrow_mut().into_key_slice_mut() } + } + + fn vals_mut(&mut self) -> &mut [V] { + unsafe { self.reborrow_mut().into_val_slice_mut() } + } +} + +impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> { + fn into_key_slice(self) -> &'a [K] { + // We have to be careful here because we might be pointing to the shared root. + // In that case, we must not create an `&LeafNode`. We could just return + // an empty slice whenever the length is 0 (this includes the shared root), + // but we want to avoid that run-time check. + // Instead, we create a slice pointing into the node whenever possible. + // We can sometimes do this even for the shared root, as the slice will be + // empty. We cannot *always* do this because if the type is too highly + // aligned, the offset of `keys` in a "full node" might be outside the bounds + // of the header! So we do an alignment check first, that will be + // evaluated at compile-time, and only do any run-time check in the rare case + // that the alignment is very big. + if mem::align_of::<K>() > mem::align_of::<LeafNode<(), ()>>() && self.is_shared_root() { + &[] + } else { + // Thanks to the alignment check above, we know that `keys` will be + // in-bounds of some allocation even if this is the shared root! + // (We might be one-past-the-end, but that is allowed by LLVM.) + // Getting the pointer is tricky though. `NodeHeader` does not have a `keys` + // field because we want its size to not depend on the alignment of `K` + // (needed becuase `as_header` should be safe). We cannot call `as_leaf` + // because we might be the shared root. + // For this reason, `NodeHeader` has this `K2` parameter (that's usually `()` + // and hence just adds a size-0-align-1 field, not affecting layout). + // We know that we can transmute `NodeHeader<K, V, ()>` to `NodeHeader<K, V, K>` + // because we did the alignment check above, and hence `NodeHeader<K, V, K>` + // is not bigger than `NodeHeader<K, V, ()>`! Then we can use `NodeHeader<K, V, K>` + // to compute the pointer where the keys start. + // This entire hack will become unnecessary once + // <https://github.com/rust-lang/rfcs/pull/2582> lands, then we can just take a raw + // pointer to the `keys` field of `*const InternalNode<K, V>`. + + // This is a non-debug-assert because it can be completely compile-time evaluated. + assert!(mem::size_of::<NodeHeader<K, V>>() == mem::size_of::<NodeHeader<K, V, K>>()); + let header = self.as_header() as *const _ as *const NodeHeader<K, V, K>; + let keys = unsafe { &(*header).keys_start as *const _ as *const K }; + unsafe { slice::from_raw_parts(keys, self.len()) } + } + } + + fn into_val_slice(self) -> &'a [V] { + debug_assert!(!self.is_shared_root()); + // We cannot be the root, so `as_leaf` is okay + unsafe { + slice::from_raw_parts(MaybeUninit::slice_as_ptr(&self.as_leaf().vals), self.len()) + } + } + + fn into_slices(self) -> (&'a [K], &'a [V]) { + let k = unsafe { ptr::read(&self) }; + (k.into_key_slice(), self.into_val_slice()) + } +} + +impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> { + /// Gets a mutable reference to the root itself. This is useful primarily when the + /// height of the tree needs to be adjusted. Never call this on a reborrowed pointer. + pub fn into_root_mut(self) -> &'a mut Root<K, V> { + unsafe { &mut *(self.root as *mut Root<K, V>) } + } + + fn into_key_slice_mut(mut self) -> &'a mut [K] { + // Same as for `into_key_slice` above, we try to avoid a run-time check + // (the alignment comparison will usually be performed at compile-time). + if mem::align_of::<K>() > mem::align_of::<LeafNode<(), ()>>() && self.is_shared_root() { + &mut [] + } else { + unsafe { + slice::from_raw_parts_mut( + MaybeUninit::slice_as_mut_ptr(&mut (*self.as_leaf_mut()).keys), + self.len(), + ) + } + } + } + + fn into_val_slice_mut(mut self) -> &'a mut [V] { + debug_assert!(!self.is_shared_root()); + unsafe { + slice::from_raw_parts_mut( + MaybeUninit::slice_as_mut_ptr(&mut (*self.as_leaf_mut()).vals), + self.len(), + ) + } + } + + fn into_slices_mut(mut self) -> (&'a mut [K], &'a mut [V]) { + debug_assert!(!self.is_shared_root()); + // We cannot use the getters here, because calling the second one + // invalidates the reference returned by the first. + // More precisely, it is the call to `len` that is the culprit, + // because that creates a shared reference to the header, which *can* + // overlap with the keys (and even the values, for ZST keys). + unsafe { + let len = self.len(); + let leaf = self.as_leaf_mut(); + let keys = + slice::from_raw_parts_mut(MaybeUninit::slice_as_mut_ptr(&mut (*leaf).keys), len); + let vals = + slice::from_raw_parts_mut(MaybeUninit::slice_as_mut_ptr(&mut (*leaf).vals), len); + (keys, vals) + } + } +} + +impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> { + /// Adds a key/value pair the end of the node. + pub fn push(&mut self, key: K, val: V) { + // Necessary for correctness, but this is an internal module + debug_assert!(self.len() < CAPACITY); + debug_assert!(!self.is_shared_root()); + + let idx = self.len(); + + unsafe { + ptr::write(self.keys_mut().get_unchecked_mut(idx), key); + ptr::write(self.vals_mut().get_unchecked_mut(idx), val); + + (*self.as_leaf_mut()).len += 1; + } + } + + /// Adds a key/value pair to the beginning of the node. + pub fn push_front(&mut self, key: K, val: V) { + // Necessary for correctness, but this is an internal module + debug_assert!(self.len() < CAPACITY); + debug_assert!(!self.is_shared_root()); + + unsafe { + slice_insert(self.keys_mut(), 0, key); + slice_insert(self.vals_mut(), 0, val); + + (*self.as_leaf_mut()).len += 1; + } + } +} + +impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { + /// Adds a key/value pair and an edge to go to the right of that pair to + /// the end of the node. + pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) { + // Necessary for correctness, but this is an internal module + debug_assert!(edge.height == self.height - 1); + debug_assert!(self.len() < CAPACITY); + + let idx = self.len(); + + unsafe { + ptr::write(self.keys_mut().get_unchecked_mut(idx), key); + ptr::write(self.vals_mut().get_unchecked_mut(idx), val); + self.as_internal_mut() + .edges + .get_unchecked_mut(idx + 1) + .write(edge.node); + + (*self.as_leaf_mut()).len += 1; + + Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link(); + } + } + + fn correct_childrens_parent_links(&mut self, first: usize, after_last: usize) { + for i in first..after_last { + Handle::new_edge(unsafe { self.reborrow_mut() }, i).correct_parent_link(); + } + } + + fn correct_all_childrens_parent_links(&mut self) { + let len = self.len(); + self.correct_childrens_parent_links(0, len + 1); + } + + /// Adds a key/value pair and an edge to go to the left of that pair to + /// the beginning of the node. + pub fn push_front(&mut self, key: K, val: V, edge: Root<K, V>) { + // Necessary for correctness, but this is an internal module + debug_assert!(edge.height == self.height - 1); + debug_assert!(self.len() < CAPACITY); + + unsafe { + slice_insert(self.keys_mut(), 0, key); + slice_insert(self.vals_mut(), 0, val); + slice_insert( + slice::from_raw_parts_mut( + MaybeUninit::slice_as_mut_ptr(&mut self.as_internal_mut().edges), + self.len() + 1, + ), + 0, + edge.node, + ); + + (*self.as_leaf_mut()).len += 1; + + self.correct_all_childrens_parent_links(); + } + } +} + +impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> { + /// Removes a key/value pair from the end of this node. If this is an internal node, + /// also removes the edge that was to the right of that pair. + pub fn pop(&mut self) -> (K, V, Option<Root<K, V>>) { + // Necessary for correctness, but this is an internal module + debug_assert!(self.len() > 0); + + let idx = self.len() - 1; + + unsafe { + let key = ptr::read(self.keys().get_unchecked(idx)); + let val = ptr::read(self.vals().get_unchecked(idx)); + let edge = match self.reborrow_mut().force() { + ForceResult::Leaf(_) => None, + ForceResult::Internal(internal) => { + let edge = + ptr::read(internal.as_internal().edges.get_unchecked(idx + 1).as_ptr()); + let mut new_root = Root { + node: edge, + height: internal.height - 1, + }; + (*new_root.as_mut().as_leaf_mut()).parent = ptr::null(); + Some(new_root) + } + }; + + (*self.as_leaf_mut()).len -= 1; + (key, val, edge) + } + } + + /// Removes a key/value pair from the beginning of this node. If this is an internal node, + /// also removes the edge that was to the left of that pair. + pub fn pop_front(&mut self) -> (K, V, Option<Root<K, V>>) { + // Necessary for correctness, but this is an internal module + debug_assert!(self.len() > 0); + + let old_len = self.len(); + + unsafe { + let key = slice_remove(self.keys_mut(), 0); + let val = slice_remove(self.vals_mut(), 0); + let edge = match self.reborrow_mut().force() { + ForceResult::Leaf(_) => None, + ForceResult::Internal(mut internal) => { + let edge = slice_remove( + slice::from_raw_parts_mut( + MaybeUninit::slice_as_mut_ptr(&mut internal.as_internal_mut().edges), + old_len + 1, + ), + 0, + ); + + let mut new_root = Root { + node: edge, + height: internal.height - 1, + }; + (*new_root.as_mut().as_leaf_mut()).parent = ptr::null(); + + for i in 0..old_len { + Handle::new_edge(internal.reborrow_mut(), i).correct_parent_link(); + } + + Some(new_root) + } + }; + + (*self.as_leaf_mut()).len -= 1; + + (key, val, edge) + } + } + + fn into_kv_pointers_mut(mut self) -> (*mut K, *mut V) { + (self.keys_mut().as_mut_ptr(), self.vals_mut().as_mut_ptr()) + } +} + +impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { + /// Checks whether a node is an `Internal` node or a `Leaf` node. + pub fn force( + self, + ) -> ForceResult< + NodeRef<BorrowType, K, V, marker::Leaf>, + NodeRef<BorrowType, K, V, marker::Internal>, + > { + if self.height == 0 { + ForceResult::Leaf(NodeRef { + height: self.height, + node: self.node, + root: self.root, + _marker: PhantomData, + }) + } else { + ForceResult::Internal(NodeRef { + height: self.height, + node: self.node, + root: self.root, + _marker: PhantomData, + }) + } + } +} + +/// A reference to a specific key/value pair or edge within a node. The `Node` parameter +/// must be a `NodeRef`, while the `Type` can either be `KV` (signifying a handle on a key/value +/// pair) or `Edge` (signifying a handle on an edge). +/// +/// Note that even `Leaf` nodes can have `Edge` handles. Instead of representing a pointer to +/// a child node, these represent the spaces where child pointers would go between the key/value +/// pairs. For example, in a node with length 2, there would be 3 possible edge locations - one +/// to the left of the node, one between the two pairs, and one at the right of the node. +pub struct Handle<Node, Type> { + node: Node, + idx: usize, + _marker: PhantomData<Type>, +} + +impl<Node: Copy, Type> Copy for Handle<Node, Type> {} +// We don't need the full generality of `#[derive(Clone)]`, as the only time `Node` will be +// `Clone`able is when it is an immutable reference and therefore `Copy`. +impl<Node: Copy, Type> Clone for Handle<Node, Type> { + fn clone(&self) -> Self { + *self + } +} + +impl<Node, Type> Handle<Node, Type> { + /// Retrieves the node that contains the edge of key/value pair this handle points to. + pub fn into_node(self) -> Node { + self.node + } +} + +impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> { + /// Creates a new handle to a key/value pair in `node`. `idx` must be less than `node.len()`. + pub fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self { + // Necessary for correctness, but in a private module + debug_assert!(idx < node.len()); + + Handle { + node, + idx, + _marker: PhantomData, + } + } + + pub fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> { + Handle::new_edge(self.node, self.idx) + } + + pub fn right_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> { + Handle::new_edge(self.node, self.idx + 1) + } +} + +impl<BorrowType, K, V, NodeType, HandleType> PartialEq + for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> +{ + fn eq(&self, other: &Self) -> bool { + self.node.node == other.node.node && self.idx == other.idx + } +} + +impl<BorrowType, K, V, NodeType, HandleType> + Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> +{ + /// Temporarily takes out another, immutable handle on the same location. + pub fn reborrow(&self) -> Handle<NodeRef<marker::Immut<'_>, K, V, NodeType>, HandleType> { + // We can't use Handle::new_kv or Handle::new_edge because we don't know our type + Handle { + node: self.node.reborrow(), + idx: self.idx, + _marker: PhantomData, + } + } +} + +impl<'a, K, V, NodeType, HandleType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> { + /// Temporarily takes out another, mutable handle on the same location. Beware, as + /// this method is very dangerous, doubly so since it may not immediately appear + /// dangerous. + /// + /// Because mutable pointers can roam anywhere around the tree and can even (through + /// `into_root_mut`) mess with the root of the tree, the result of `reborrow_mut` + /// can easily be used to make the original mutable pointer dangling, or, in the case + /// of a reborrowed handle, out of bounds. + // FIXME(@gereeter) consider adding yet another type parameter to `NodeRef` that restricts + // the use of `ascend` and `into_root_mut` on reborrowed pointers, preventing this unsafety. + pub unsafe fn reborrow_mut( + &mut self, + ) -> Handle<NodeRef<marker::Mut<'_>, K, V, NodeType>, HandleType> { + // We can't use Handle::new_kv or Handle::new_edge because we don't know our type + Handle { + node: self.node.reborrow_mut(), + idx: self.idx, + _marker: PhantomData, + } + } +} + +impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> { + /// Creates a new handle to an edge in `node`. `idx` must be less than or equal to + /// `node.len()`. + pub fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self { + // Necessary for correctness, but in a private module + debug_assert!(idx <= node.len()); + + Handle { + node, + idx, + _marker: PhantomData, + } + } + + pub fn left_kv(self) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> { + if self.idx > 0 { + Ok(Handle::new_kv(self.node, self.idx - 1)) + } else { + Err(self) + } + } + + pub fn right_kv(self) -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> { + if self.idx < self.node.len() { + Ok(Handle::new_kv(self.node, self.idx)) + } else { + Err(self) + } + } +} + +impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> { + /// Inserts a new key/value pair between the key/value pairs to the right and left of + /// this edge. This method assumes that there is enough space in the node for the new + /// pair to fit. + /// + /// The returned pointer points to the inserted value. + fn insert_fit(&mut self, key: K, val: V) -> *mut V { + // Necessary for correctness, but in a private module + debug_assert!(self.node.len() < CAPACITY); + debug_assert!(!self.node.is_shared_root()); + + unsafe { + slice_insert(self.node.keys_mut(), self.idx, key); + slice_insert(self.node.vals_mut(), self.idx, val); + + (*self.node.as_leaf_mut()).len += 1; + + self.node.vals_mut().get_unchecked_mut(self.idx) + } + } + + /// Inserts a new key/value pair between the key/value pairs to the right and left of + /// this edge. This method splits the node if there isn't enough room. + /// + /// The returned pointer points to the inserted value. + pub fn insert( + mut self, + key: K, + val: V, + ) -> Result<(InsertResult<'a, K, V, marker::Leaf>, *mut V), TryReserveError> { + if self.node.len() < CAPACITY { + let ptr = self.insert_fit(key, val); + Ok((InsertResult::Fit(Handle::new_kv(self.node, self.idx)), ptr)) + } else { + let middle = Handle::new_kv(self.node, B); + let (mut left, k, v, mut right) = middle.split()?; + let ptr = if self.idx <= B { + unsafe { Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val) } + } else { + unsafe { + Handle::new_edge( + right.as_mut().cast_unchecked::<marker::Leaf>(), + self.idx - (B + 1), + ) + .insert_fit(key, val) + } + }; + Ok((InsertResult::Split(left, k, v, right), ptr)) + } + } +} + +impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> { + /// Fixes the parent pointer and index in the child node below this edge. This is useful + /// when the ordering of edges has been changed, such as in the various `insert` methods. + fn correct_parent_link(mut self) { + let idx = self.idx as u16; + let ptr = self.node.as_internal_mut() as *mut _; + let mut child = self.descend(); + unsafe { + (*child.as_leaf_mut()).parent = ptr; + (*child.as_leaf_mut()).parent_idx.write(idx); + } + } + + /// Unsafely asserts to the compiler some static information about whether the underlying + /// node of this handle is a `Leaf`. + unsafe fn cast_unchecked<NewType>( + &mut self, + ) -> Handle<NodeRef<marker::Mut<'_>, K, V, NewType>, marker::Edge> { + Handle::new_edge(self.node.cast_unchecked(), self.idx) + } + + /// Inserts a new key/value pair and an edge that will go to the right of that new pair + /// between this edge and the key/value pair to the right of this edge. This method assumes + /// that there is enough space in the node for the new pair to fit. + fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) { + // Necessary for correctness, but in an internal module + debug_assert!(self.node.len() < CAPACITY); + debug_assert!(edge.height == self.node.height - 1); + + unsafe { + // This cast is a lie, but it allows us to reuse the key/value insertion logic. + self.cast_unchecked::<marker::Leaf>().insert_fit(key, val); + + slice_insert( + slice::from_raw_parts_mut( + MaybeUninit::slice_as_mut_ptr(&mut self.node.as_internal_mut().edges), + self.node.len(), + ), + self.idx + 1, + edge.node, + ); + + for i in (self.idx + 1)..(self.node.len() + 1) { + Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link(); + } + } + } + + /// Inserts a new key/value pair and an edge that will go to the right of that new pair + /// between this edge and the key/value pair to the right of this edge. This method splits + /// the node if there isn't enough room. + pub fn insert( + mut self, + key: K, + val: V, + edge: Root<K, V>, + ) -> Result<InsertResult<'a, K, V, marker::Internal>, TryReserveError> { + // Necessary for correctness, but this is an internal module + debug_assert!(edge.height == self.node.height - 1); + + if self.node.len() < CAPACITY { + self.insert_fit(key, val, edge); + Ok(InsertResult::Fit(Handle::new_kv(self.node, self.idx))) + } else { + let middle = Handle::new_kv(self.node, B); + let (mut left, k, v, mut right) = middle.split()?; + if self.idx <= B { + unsafe { + Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val, edge); + } + } else { + unsafe { + Handle::new_edge( + right.as_mut().cast_unchecked::<marker::Internal>(), + self.idx - (B + 1), + ) + .insert_fit(key, val, edge); + } + } + Ok(InsertResult::Split(left, k, v, right)) + } + } +} + +impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> { + /// Finds the node pointed to by this edge. + /// + /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should + /// both, upon success, do nothing. + pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { + NodeRef { + height: self.node.height - 1, + node: unsafe { + (&*self + .node + .as_internal() + .edges + .get_unchecked(self.idx) + .as_ptr()) + .as_ptr() + }, + root: self.node.root, + _marker: PhantomData, + } + } +} + +impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> { + pub fn into_kv(self) -> (&'a K, &'a V) { + let (keys, vals) = self.node.into_slices(); + unsafe { (keys.get_unchecked(self.idx), vals.get_unchecked(self.idx)) } + } +} + +impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> { + pub fn into_kv_mut(self) -> (&'a mut K, &'a mut V) { + let (keys, vals) = self.node.into_slices_mut(); + unsafe { + ( + keys.get_unchecked_mut(self.idx), + vals.get_unchecked_mut(self.idx), + ) + } + } +} + +impl<'a, K, V, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> { + pub fn kv_mut(&mut self) -> (&mut K, &mut V) { + unsafe { + let (keys, vals) = self.node.reborrow_mut().into_slices_mut(); + ( + keys.get_unchecked_mut(self.idx), + vals.get_unchecked_mut(self.idx), + ) + } + } +} + +impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> { + /// Splits the underlying node into three parts: + /// + /// - The node is truncated to only contain the key/value pairs to the right of + /// this handle. + /// - The key and value pointed to by this handle and extracted. + /// - All the key/value pairs to the right of this handle are put into a newly + /// allocated node. + pub fn split( + mut self, + ) -> Result< + ( + NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, + K, + V, + Root<K, V>, + ), + TryReserveError, + > { + debug_assert!(!self.node.is_shared_root()); + unsafe { + let mut new_node = <Box<_> as FallibleBox<_>>::try_new(LeafNode::new())?; + + let k = ptr::read(self.node.keys().get_unchecked(self.idx)); + let v = ptr::read(self.node.vals().get_unchecked(self.idx)); + + let new_len = self.node.len() - self.idx - 1; + + ptr::copy_nonoverlapping( + self.node.keys().as_ptr().add(self.idx + 1), + new_node.keys.as_mut_ptr() as *mut K, + new_len, + ); + ptr::copy_nonoverlapping( + self.node.vals().as_ptr().add(self.idx + 1), + new_node.vals.as_mut_ptr() as *mut V, + new_len, + ); + + (*self.node.as_leaf_mut()).len = self.idx as u16; + new_node.len = new_len as u16; + + Ok(( + self.node, + k, + v, + Root { + node: BoxedNode::from_leaf(new_node), + height: 0, + }, + )) + } + } + + /// Removes the key/value pair pointed to by this handle, returning the edge between the + /// now adjacent key/value pairs to the left and right of this handle. + pub fn remove( + mut self, + ) -> ( + Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, + K, + V, + ) { + debug_assert!(!self.node.is_shared_root()); + unsafe { + let k = slice_remove(self.node.keys_mut(), self.idx); + let v = slice_remove(self.node.vals_mut(), self.idx); + (*self.node.as_leaf_mut()).len -= 1; + (self.left_edge(), k, v) + } + } +} + +impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> { + /// Splits the underlying node into three parts: + /// + /// - The node is truncated to only contain the edges and key/value pairs to the + /// right of this handle. + /// - The key and value pointed to by this handle and extracted. + /// - All the edges and key/value pairs to the right of this handle are put into + /// a newly allocated node. + pub fn split( + mut self, + ) -> Result< + ( + NodeRef<marker::Mut<'a>, K, V, marker::Internal>, + K, + V, + Root<K, V>, + ), + TryReserveError, + > { + unsafe { + let mut new_node = <Box<_> as FallibleBox<_>>::try_new(InternalNode::new())?; + + let k = ptr::read(self.node.keys().get_unchecked(self.idx)); + let v = ptr::read(self.node.vals().get_unchecked(self.idx)); + + let height = self.node.height; + let new_len = self.node.len() - self.idx - 1; + + ptr::copy_nonoverlapping( + self.node.keys().as_ptr().add(self.idx + 1), + new_node.data.keys.as_mut_ptr() as *mut K, + new_len, + ); + ptr::copy_nonoverlapping( + self.node.vals().as_ptr().add(self.idx + 1), + new_node.data.vals.as_mut_ptr() as *mut V, + new_len, + ); + ptr::copy_nonoverlapping( + self.node.as_internal().edges.as_ptr().add(self.idx + 1), + new_node.edges.as_mut_ptr(), + new_len + 1, + ); + + (*self.node.as_leaf_mut()).len = self.idx as u16; + new_node.data.len = new_len as u16; + + let mut new_root = Root { + node: BoxedNode::from_internal(new_node), + height, + }; + + for i in 0..(new_len + 1) { + Handle::new_edge(new_root.as_mut().cast_unchecked(), i).correct_parent_link(); + } + + Ok((self.node, k, v, new_root)) + } + } + + /// Returns `true` if it is valid to call `.merge()`, i.e., whether there is enough room in + /// a node to hold the combination of the nodes to the left and right of this handle along + /// with the key/value pair at this handle. + pub fn can_merge(&self) -> bool { + (self.reborrow().left_edge().descend().len() + + self.reborrow().right_edge().descend().len() + + 1) + <= CAPACITY + } + + /// Combines the node immediately to the left of this handle, the key/value pair pointed + /// to by this handle, and the node immediately to the right of this handle into one new + /// child of the underlying node, returning an edge referencing that new child. + /// + /// Assumes that this edge `.can_merge()`. + pub fn merge( + mut self, + ) -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> { + let self1 = unsafe { ptr::read(&self) }; + let self2 = unsafe { ptr::read(&self) }; + let mut left_node = self1.left_edge().descend(); + let left_len = left_node.len(); + let mut right_node = self2.right_edge().descend(); + let right_len = right_node.len(); + + // necessary for correctness, but in a private module + debug_assert!(left_len + right_len + 1 <= CAPACITY); + + unsafe { + ptr::write( + left_node.keys_mut().get_unchecked_mut(left_len), + slice_remove(self.node.keys_mut(), self.idx), + ); + ptr::copy_nonoverlapping( + right_node.keys().as_ptr(), + left_node.keys_mut().as_mut_ptr().add(left_len + 1), + right_len, + ); + ptr::write( + left_node.vals_mut().get_unchecked_mut(left_len), + slice_remove(self.node.vals_mut(), self.idx), + ); + ptr::copy_nonoverlapping( + right_node.vals().as_ptr(), + left_node.vals_mut().as_mut_ptr().add(left_len + 1), + right_len, + ); + + slice_remove(&mut self.node.as_internal_mut().edges, self.idx + 1); + for i in self.idx + 1..self.node.len() { + Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link(); + } + (*self.node.as_leaf_mut()).len -= 1; + + (*left_node.as_leaf_mut()).len += right_len as u16 + 1; + + if self.node.height > 1 { + ptr::copy_nonoverlapping( + right_node.cast_unchecked().as_internal().edges.as_ptr(), + left_node + .cast_unchecked() + .as_internal_mut() + .edges + .as_mut_ptr() + .add(left_len + 1), + right_len + 1, + ); + + for i in left_len + 1..left_len + right_len + 2 { + Handle::new_edge(left_node.cast_unchecked().reborrow_mut(), i) + .correct_parent_link(); + } + + Global.deallocate(right_node.node.cast(), Layout::new::<InternalNode<K, V>>()); + } else { + Global.deallocate(right_node.node.cast(), Layout::new::<LeafNode<K, V>>()); + } + + Handle::new_edge(self.node, self.idx) + } + } + + /// This removes a key/value pair from the left child and replaces it with the key/value pair + /// pointed to by this handle while pushing the old key/value pair of this handle into the right + /// child. + pub fn steal_left(&mut self) { + unsafe { + let (k, v, edge) = self.reborrow_mut().left_edge().descend().pop(); + + let k = mem::replace(self.reborrow_mut().into_kv_mut().0, k); + let v = mem::replace(self.reborrow_mut().into_kv_mut().1, v); + + match self.reborrow_mut().right_edge().descend().force() { + ForceResult::Leaf(mut leaf) => leaf.push_front(k, v), + ForceResult::Internal(mut internal) => internal.push_front(k, v, edge.unwrap()), + } + } + } + + /// This removes a key/value pair from the right child and replaces it with the key/value pair + /// pointed to by this handle while pushing the old key/value pair of this handle into the left + /// child. + pub fn steal_right(&mut self) { + unsafe { + let (k, v, edge) = self.reborrow_mut().right_edge().descend().pop_front(); + + let k = mem::replace(self.reborrow_mut().into_kv_mut().0, k); + let v = mem::replace(self.reborrow_mut().into_kv_mut().1, v); + + match self.reborrow_mut().left_edge().descend().force() { + ForceResult::Leaf(mut leaf) => leaf.push(k, v), + ForceResult::Internal(mut internal) => internal.push(k, v, edge.unwrap()), + } + } + } + + /// This does stealing similar to `steal_left` but steals multiple elements at once. + pub fn bulk_steal_left(&mut self, count: usize) { + unsafe { + let mut left_node = ptr::read(self).left_edge().descend(); + let left_len = left_node.len(); + let mut right_node = ptr::read(self).right_edge().descend(); + let right_len = right_node.len(); + + // Make sure that we may steal safely. + debug_assert!(right_len + count <= CAPACITY); + debug_assert!(left_len >= count); + + let new_left_len = left_len - count; + + // Move data. + { + let left_kv = left_node.reborrow_mut().into_kv_pointers_mut(); + let right_kv = right_node.reborrow_mut().into_kv_pointers_mut(); + let parent_kv = { + let kv = self.reborrow_mut().into_kv_mut(); + (kv.0 as *mut K, kv.1 as *mut V) + }; + + // Make room for stolen elements in the right child. + ptr::copy(right_kv.0, right_kv.0.add(count), right_len); + ptr::copy(right_kv.1, right_kv.1.add(count), right_len); + + // Move elements from the left child to the right one. + move_kv(left_kv, new_left_len + 1, right_kv, 0, count - 1); + + // Move parent's key/value pair to the right child. + move_kv(parent_kv, 0, right_kv, count - 1, 1); + + // Move the left-most stolen pair to the parent. + move_kv(left_kv, new_left_len, parent_kv, 0, 1); + } + + (*left_node.reborrow_mut().as_leaf_mut()).len -= count as u16; + (*right_node.reborrow_mut().as_leaf_mut()).len += count as u16; + + match (left_node.force(), right_node.force()) { + (ForceResult::Internal(left), ForceResult::Internal(mut right)) => { + // Make room for stolen edges. + let right_edges = right.reborrow_mut().as_internal_mut().edges.as_mut_ptr(); + ptr::copy(right_edges, right_edges.add(count), right_len + 1); + right.correct_childrens_parent_links(count, count + right_len + 1); + + move_edges(left, new_left_len + 1, right, 0, count); + } + (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {} + _ => { + unreachable!(); + } + } + } + } + + /// The symmetric clone of `bulk_steal_left`. + pub fn bulk_steal_right(&mut self, count: usize) { + unsafe { + let mut left_node = ptr::read(self).left_edge().descend(); + let left_len = left_node.len(); + let mut right_node = ptr::read(self).right_edge().descend(); + let right_len = right_node.len(); + + // Make sure that we may steal safely. + debug_assert!(left_len + count <= CAPACITY); + debug_assert!(right_len >= count); + + let new_right_len = right_len - count; + + // Move data. + { + let left_kv = left_node.reborrow_mut().into_kv_pointers_mut(); + let right_kv = right_node.reborrow_mut().into_kv_pointers_mut(); + let parent_kv = { + let kv = self.reborrow_mut().into_kv_mut(); + (kv.0 as *mut K, kv.1 as *mut V) + }; + + // Move parent's key/value pair to the left child. + move_kv(parent_kv, 0, left_kv, left_len, 1); + + // Move elements from the right child to the left one. + move_kv(right_kv, 0, left_kv, left_len + 1, count - 1); + + // Move the right-most stolen pair to the parent. + move_kv(right_kv, count - 1, parent_kv, 0, 1); + + // Fix right indexing + ptr::copy(right_kv.0.add(count), right_kv.0, new_right_len); + ptr::copy(right_kv.1.add(count), right_kv.1, new_right_len); + } + + (*left_node.reborrow_mut().as_leaf_mut()).len += count as u16; + (*right_node.reborrow_mut().as_leaf_mut()).len -= count as u16; + + match (left_node.force(), right_node.force()) { + (ForceResult::Internal(left), ForceResult::Internal(mut right)) => { + move_edges(right.reborrow_mut(), 0, left, left_len + 1, count); + + // Fix right indexing. + let right_edges = right.reborrow_mut().as_internal_mut().edges.as_mut_ptr(); + ptr::copy(right_edges.add(count), right_edges, new_right_len + 1); + right.correct_childrens_parent_links(0, new_right_len + 1); + } + (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {} + _ => { + unreachable!(); + } + } + } + } +} + +unsafe fn move_kv<K, V>( + source: (*mut K, *mut V), + source_offset: usize, + dest: (*mut K, *mut V), + dest_offset: usize, + count: usize, +) { + ptr::copy_nonoverlapping(source.0.add(source_offset), dest.0.add(dest_offset), count); + ptr::copy_nonoverlapping(source.1.add(source_offset), dest.1.add(dest_offset), count); +} + +// Source and destination must have the same height. +unsafe fn move_edges<K, V>( + mut source: NodeRef<marker::Mut<'_>, K, V, marker::Internal>, + source_offset: usize, + mut dest: NodeRef<marker::Mut<'_>, K, V, marker::Internal>, + dest_offset: usize, + count: usize, +) { + let source_ptr = source.as_internal_mut().edges.as_mut_ptr(); + let dest_ptr = dest.as_internal_mut().edges.as_mut_ptr(); + ptr::copy_nonoverlapping( + source_ptr.add(source_offset), + dest_ptr.add(dest_offset), + count, + ); + dest.correct_childrens_parent_links(dest_offset, dest_offset + count); +} + +impl<BorrowType, K, V, HandleType> + Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType> +{ + /// Checks whether the underlying node is an `Internal` node or a `Leaf` node. + pub fn force( + self, + ) -> ForceResult< + Handle<NodeRef<BorrowType, K, V, marker::Leaf>, HandleType>, + Handle<NodeRef<BorrowType, K, V, marker::Internal>, HandleType>, + > { + match self.node.force() { + ForceResult::Leaf(node) => ForceResult::Leaf(Handle { + node, + idx: self.idx, + _marker: PhantomData, + }), + ForceResult::Internal(node) => ForceResult::Internal(Handle { + node, + idx: self.idx, + _marker: PhantomData, + }), + } + } +} + +impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::Edge> { + /// Move the suffix after `self` from one node to another one. `right` must be empty. + /// The first edge of `right` remains unchanged. + pub fn move_suffix( + &mut self, + right: &mut NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, + ) { + unsafe { + let left_new_len = self.idx; + let mut left_node = self.reborrow_mut().into_node(); + + let right_new_len = left_node.len() - left_new_len; + let mut right_node = right.reborrow_mut(); + + debug_assert!(right_node.len() == 0); + debug_assert!(left_node.height == right_node.height); + + let left_kv = left_node.reborrow_mut().into_kv_pointers_mut(); + let right_kv = right_node.reborrow_mut().into_kv_pointers_mut(); + + move_kv(left_kv, left_new_len, right_kv, 0, right_new_len); + + (*left_node.reborrow_mut().as_leaf_mut()).len = left_new_len as u16; + (*right_node.reborrow_mut().as_leaf_mut()).len = right_new_len as u16; + + match (left_node.force(), right_node.force()) { + (ForceResult::Internal(left), ForceResult::Internal(right)) => { + move_edges(left, left_new_len + 1, right, 1, right_new_len); + } + (ForceResult::Leaf(_), ForceResult::Leaf(_)) => {} + _ => { + unreachable!(); + } + } + } + } +} + +pub enum ForceResult<Leaf, Internal> { + Leaf(Leaf), + Internal(Internal), +} + +pub enum InsertResult<'a, K, V, Type> { + Fit(Handle<NodeRef<marker::Mut<'a>, K, V, Type>, marker::KV>), + Split(NodeRef<marker::Mut<'a>, K, V, Type>, K, V, Root<K, V>), +} + +pub mod marker { + use core::marker::PhantomData; + + pub enum Leaf {} + pub enum Internal {} + pub enum LeafOrInternal {} + + pub enum Owned {} + pub struct Immut<'a>(PhantomData<&'a ()>); + pub struct Mut<'a>(PhantomData<&'a mut ()>); + + pub enum KV {} + pub enum Edge {} +} + +unsafe fn slice_insert<T>(slice: &mut [T], idx: usize, val: T) { + ptr::copy( + slice.as_ptr().add(idx), + slice.as_mut_ptr().add(idx + 1), + slice.len() - idx, + ); + ptr::write(slice.get_unchecked_mut(idx), val); +} + +unsafe fn slice_remove<T>(slice: &mut [T], idx: usize) -> T { + let ret = ptr::read(slice.get_unchecked(idx)); + ptr::copy( + slice.as_ptr().add(idx + 1), + slice.as_mut_ptr().add(idx), + slice.len() - idx - 1, + ); + ret +} diff --git a/third_party/rust/fallible_collections/src/btree/search.rs b/third_party/rust/fallible_collections/src/btree/search.rs new file mode 100644 index 0000000000..0031fdc29c --- /dev/null +++ b/third_party/rust/fallible_collections/src/btree/search.rs @@ -0,0 +1,66 @@ +use core::borrow::Borrow; + +use core::cmp::Ordering; + +use super::node::{marker, ForceResult::*, Handle, NodeRef}; + +use SearchResult::*; + +pub enum SearchResult<BorrowType, K, V, FoundType, GoDownType> { + Found(Handle<NodeRef<BorrowType, K, V, FoundType>, marker::KV>), + GoDown(Handle<NodeRef<BorrowType, K, V, GoDownType>, marker::Edge>), +} + +pub fn search_tree<BorrowType, K, V, Q: ?Sized>( + mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>, + key: &Q, +) -> SearchResult<BorrowType, K, V, marker::LeafOrInternal, marker::Leaf> +where + Q: Ord, + K: Borrow<Q>, +{ + loop { + match search_node(node, key) { + Found(handle) => return Found(handle), + GoDown(handle) => match handle.force() { + Leaf(leaf) => return GoDown(leaf), + Internal(internal) => { + node = internal.descend(); + continue; + } + }, + } + } +} + +pub fn search_node<BorrowType, K, V, Type, Q: ?Sized>( + node: NodeRef<BorrowType, K, V, Type>, + key: &Q, +) -> SearchResult<BorrowType, K, V, Type, Type> +where + Q: Ord, + K: Borrow<Q>, +{ + match search_linear(&node, key) { + (idx, true) => Found(Handle::new_kv(node, idx)), + (idx, false) => SearchResult::GoDown(Handle::new_edge(node, idx)), + } +} + +pub fn search_linear<BorrowType, K, V, Type, Q: ?Sized>( + node: &NodeRef<BorrowType, K, V, Type>, + key: &Q, +) -> (usize, bool) +where + Q: Ord, + K: Borrow<Q>, +{ + for (i, k) in node.keys().iter().enumerate() { + match key.cmp(k.borrow()) { + Ordering::Greater => {} + Ordering::Equal => return (i, true), + Ordering::Less => return (i, false), + } + } + (node.keys().len(), false) +} diff --git a/third_party/rust/fallible_collections/src/btree/set.rs b/third_party/rust/fallible_collections/src/btree/set.rs new file mode 100644 index 0000000000..c6112ee6cd --- /dev/null +++ b/third_party/rust/fallible_collections/src/btree/set.rs @@ -0,0 +1,1346 @@ +// This is pretty much entirely stolen from TreeSet, since BTreeMap has an identical interface +// to TreeMap + +use crate::TryReserveError; +use core::borrow::Borrow; +use core::cmp::max; +use core::cmp::Ordering::{self, Equal, Greater, Less}; +use core::fmt::{self, Debug}; +use core::iter::{FromIterator, FusedIterator, Peekable}; +use core::ops::{BitAnd, BitOr, BitXor, RangeBounds, Sub}; + +use super::map::{self, BTreeMap, Keys}; +use super::Recover; + +// FIXME(conventions): implement bounded iterators + +/// A set based on a B-Tree. +/// +/// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance +/// benefits and drawbacks. +/// +/// It is a logic error for an item to be modified in such a way that the item's ordering relative +/// to any other item, as determined by the [`Ord`] trait, changes while it is in the set. This is +/// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code. +/// +/// [`BTreeMap`]: struct.BTreeMap.html +/// [`Ord`]: ../../std/cmp/trait.Ord.html +/// [`Cell`]: ../../std/cell/struct.Cell.html +/// [`RefCell`]: ../../std/cell/struct.RefCell.html +/// +/// # Examples +/// +/// ``` +/// use std::collections::BTreeSet; +/// +/// // Type inference lets us omit an explicit type signature (which +/// // would be `BTreeSet<&str>` in this example). +/// let mut books = BTreeSet::new(); +/// +/// // Add some books. +/// books.insert("A Dance With Dragons"); +/// books.insert("To Kill a Mockingbird"); +/// books.insert("The Odyssey"); +/// books.insert("The Great Gatsby"); +/// +/// // Check for a specific one. +/// if !books.contains("The Winds of Winter") { +/// println!("We have {} books, but The Winds of Winter ain't one.", +/// books.len()); +/// } +/// +/// // Remove a book. +/// books.remove("The Odyssey"); +/// +/// // Iterate over everything. +/// for book in &books { +/// println!("{}", book); +/// } +/// ``` +#[derive(Clone, Hash, PartialEq, Eq, Ord, PartialOrd)] + +pub struct BTreeSet<T> { + map: BTreeMap<T, ()>, +} + +/// An iterator over the items of a `BTreeSet`. +/// +/// This `struct` is created by the [`iter`] method on [`BTreeSet`]. +/// See its documentation for more. +/// +/// [`BTreeSet`]: struct.BTreeSet.html +/// [`iter`]: struct.BTreeSet.html#method.iter + +pub struct Iter<'a, T: 'a> { + iter: Keys<'a, T, ()>, +} + +impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("Iter").field(&self.iter.clone()).finish() + } +} + +/// An owning iterator over the items of a `BTreeSet`. +/// +/// This `struct` is created by the [`into_iter`] method on [`BTreeSet`][`BTreeSet`] +/// (provided by the `IntoIterator` trait). See its documentation for more. +/// +/// [`BTreeSet`]: struct.BTreeSet.html +/// [`into_iter`]: struct.BTreeSet.html#method.into_iter + +#[derive(Debug)] +pub struct IntoIter<T> { + iter: map::IntoIter<T, ()>, +} + +/// An iterator over a sub-range of items in a `BTreeSet`. +/// +/// This `struct` is created by the [`range`] method on [`BTreeSet`]. +/// See its documentation for more. +/// +/// [`BTreeSet`]: struct.BTreeSet.html +/// [`range`]: struct.BTreeSet.html#method.range +#[derive(Debug)] + +pub struct Range<'a, T: 'a> { + iter: map::Range<'a, T, ()>, +} + +/// A lazy iterator producing elements in the difference of `BTreeSet`s. +/// +/// This `struct` is created by the [`difference`] method on [`BTreeSet`]. +/// See its documentation for more. +/// +/// [`BTreeSet`]: struct.BTreeSet.html +/// [`difference`]: struct.BTreeSet.html#method.difference + +pub struct Difference<'a, T: 'a> { + inner: DifferenceInner<'a, T>, +} +enum DifferenceInner<'a, T: 'a> { + Stitch { + self_iter: Iter<'a, T>, + other_iter: Peekable<Iter<'a, T>>, + }, + Search { + self_iter: Iter<'a, T>, + other_set: &'a BTreeSet<T>, + }, +} + +impl<T: fmt::Debug> fmt::Debug for Difference<'_, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match &self.inner { + DifferenceInner::Stitch { + self_iter, + other_iter, + } => f + .debug_tuple("Difference") + .field(&self_iter) + .field(&other_iter) + .finish(), + DifferenceInner::Search { + self_iter, + other_set: _, + } => f.debug_tuple("Difference").field(&self_iter).finish(), + } + } +} + +/// A lazy iterator producing elements in the symmetric difference of `BTreeSet`s. +/// +/// This `struct` is created by the [`symmetric_difference`] method on +/// [`BTreeSet`]. See its documentation for more. +/// +/// [`BTreeSet`]: struct.BTreeSet.html +/// [`symmetric_difference`]: struct.BTreeSet.html#method.symmetric_difference + +pub struct SymmetricDifference<'a, T: 'a> { + a: Peekable<Iter<'a, T>>, + b: Peekable<Iter<'a, T>>, +} + +impl<T: fmt::Debug> fmt::Debug for SymmetricDifference<'_, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("SymmetricDifference") + .field(&self.a) + .field(&self.b) + .finish() + } +} + +/// A lazy iterator producing elements in the intersection of `BTreeSet`s. +/// +/// This `struct` is created by the [`intersection`] method on [`BTreeSet`]. +/// See its documentation for more. +/// +/// [`BTreeSet`]: struct.BTreeSet.html +/// [`intersection`]: struct.BTreeSet.html#method.intersection + +pub struct Intersection<'a, T: 'a> { + inner: IntersectionInner<'a, T>, +} +enum IntersectionInner<'a, T: 'a> { + Stitch { + small_iter: Iter<'a, T>, // for size_hint, should be the smaller of the sets + other_iter: Iter<'a, T>, + }, + Search { + small_iter: Iter<'a, T>, + large_set: &'a BTreeSet<T>, + }, +} + +impl<T: fmt::Debug> fmt::Debug for Intersection<'_, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match &self.inner { + IntersectionInner::Stitch { + small_iter, + other_iter, + } => f + .debug_tuple("Intersection") + .field(&small_iter) + .field(&other_iter) + .finish(), + IntersectionInner::Search { + small_iter, + large_set: _, + } => f.debug_tuple("Intersection").field(&small_iter).finish(), + } + } +} + +/// A lazy iterator producing elements in the union of `BTreeSet`s. +/// +/// This `struct` is created by the [`union`] method on [`BTreeSet`]. +/// See its documentation for more. +/// +/// [`BTreeSet`]: struct.BTreeSet.html +/// [`union`]: struct.BTreeSet.html#method.union + +pub struct Union<'a, T: 'a> { + a: Peekable<Iter<'a, T>>, + b: Peekable<Iter<'a, T>>, +} + +impl<T: fmt::Debug> fmt::Debug for Union<'_, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("Union") + .field(&self.a) + .field(&self.b) + .finish() + } +} + +// This constant is used by functions that compare two sets. +// It estimates the relative size at which searching performs better +// than iterating, based on the benchmarks in +// https://github.com/ssomers/rust_bench_btreeset_intersection; +// It's used to divide rather than multiply sizes, to rule out overflow, +// and it's a power of two to make that division cheap. +const ITER_PERFORMANCE_TIPPING_SIZE_DIFF: usize = 16; + +impl<T: Ord> BTreeSet<T> { + /// Makes a new `BTreeSet` with a reasonable choice of B. + /// + /// # Examples + /// + /// ``` + /// # #![allow(unused_mut)] + /// use std::collections::BTreeSet; + /// + /// let mut set: BTreeSet<i32> = BTreeSet::new(); + /// ``` + + #[inline] + pub fn new() -> BTreeSet<T> { + BTreeSet { + map: BTreeMap::new(), + } + } + + /// Constructs a double-ended iterator over a sub-range of elements in the set. + /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will + /// yield elements from min (inclusive) to max (exclusive). + /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example + /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive + /// range from 4 to 10. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// use std::ops::Bound::Included; + /// + /// let mut set = BTreeSet::new(); + /// set.insert(3); + /// set.insert(5); + /// set.insert(8); + /// for &elem in set.range((Included(&4), Included(&8))) { + /// println!("{}", elem); + /// } + /// assert_eq!(Some(&5), set.range(4..).next()); + /// ``` + + #[inline] + pub fn range<K: ?Sized, R>(&self, range: R) -> Range<'_, T> + where + K: Ord, + T: Borrow<K>, + R: RangeBounds<K>, + { + Range { + iter: self.map.range(range), + } + } + + /// Visits the values representing the difference, + /// i.e., the values that are in `self` but not in `other`, + /// in ascending order. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut a = BTreeSet::new(); + /// a.insert(1); + /// a.insert(2); + /// + /// let mut b = BTreeSet::new(); + /// b.insert(2); + /// b.insert(3); + /// + /// let diff: Vec<_> = a.difference(&b).cloned().collect(); + /// assert_eq!(diff, [1]); + /// ``` + + pub fn difference<'a>(&'a self, other: &'a BTreeSet<T>) -> Difference<'a, T> { + if self.len() > other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF { + // Self is bigger than or not much smaller than other set. + // Iterate both sets jointly, spotting matches along the way. + Difference { + inner: DifferenceInner::Stitch { + self_iter: self.iter(), + other_iter: other.iter().peekable(), + }, + } + } else { + // Self is much smaller than other set, or both sets are empty. + // Iterate the small set, searching for matches in the large set. + Difference { + inner: DifferenceInner::Search { + self_iter: self.iter(), + other_set: other, + }, + } + } + } + + /// Visits the values representing the symmetric difference, + /// i.e., the values that are in `self` or in `other` but not in both, + /// in ascending order. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut a = BTreeSet::new(); + /// a.insert(1); + /// a.insert(2); + /// + /// let mut b = BTreeSet::new(); + /// b.insert(2); + /// b.insert(3); + /// + /// let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect(); + /// assert_eq!(sym_diff, [1, 3]); + /// ``` + + #[inline] + pub fn symmetric_difference<'a>( + &'a self, + other: &'a BTreeSet<T>, + ) -> SymmetricDifference<'a, T> { + SymmetricDifference { + a: self.iter().peekable(), + b: other.iter().peekable(), + } + } + + /// Visits the values representing the intersection, + /// i.e., the values that are both in `self` and `other`, + /// in ascending order. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut a = BTreeSet::new(); + /// a.insert(1); + /// a.insert(2); + /// + /// let mut b = BTreeSet::new(); + /// b.insert(2); + /// b.insert(3); + /// + /// let intersection: Vec<_> = a.intersection(&b).cloned().collect(); + /// assert_eq!(intersection, [2]); + /// ``` + + pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T>) -> Intersection<'a, T> { + let (small, other) = if self.len() <= other.len() { + (self, other) + } else { + (other, self) + }; + if small.len() > other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF { + // Small set is not much smaller than other set. + // Iterate both sets jointly, spotting matches along the way. + Intersection { + inner: IntersectionInner::Stitch { + small_iter: small.iter(), + other_iter: other.iter(), + }, + } + } else { + // Big difference in number of elements, or both sets are empty. + // Iterate the small set, searching for matches in the large set. + Intersection { + inner: IntersectionInner::Search { + small_iter: small.iter(), + large_set: other, + }, + } + } + } + + /// Visits the values representing the union, + /// i.e., all the values in `self` or `other`, without duplicates, + /// in ascending order. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut a = BTreeSet::new(); + /// a.insert(1); + /// + /// let mut b = BTreeSet::new(); + /// b.insert(2); + /// + /// let union: Vec<_> = a.union(&b).cloned().collect(); + /// assert_eq!(union, [1, 2]); + /// ``` + + #[inline] + pub fn union<'a>(&'a self, other: &'a BTreeSet<T>) -> Union<'a, T> { + Union { + a: self.iter().peekable(), + b: other.iter().peekable(), + } + } + + /// Clears the set, removing all values. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut v = BTreeSet::new(); + /// v.insert(1); + /// v.clear(); + /// assert!(v.is_empty()); + /// ``` + + #[inline(always)] + pub fn clear(&mut self) { + self.map.clear() + } + + /// Returns `true` if the set contains a value. + /// + /// The value may be any borrowed form of the set's value type, + /// but the ordering on the borrowed form *must* match the + /// ordering on the value type. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect(); + /// assert_eq!(set.contains(&1), true); + /// assert_eq!(set.contains(&4), false); + /// ``` + + #[inline(always)] + pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool + where + T: Borrow<Q>, + Q: Ord, + { + self.map.contains_key(value) + } + + /// Returns a reference to the value in the set, if any, that is equal to the given value. + /// + /// The value may be any borrowed form of the set's value type, + /// but the ordering on the borrowed form *must* match the + /// ordering on the value type. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect(); + /// assert_eq!(set.get(&2), Some(&2)); + /// assert_eq!(set.get(&4), None); + /// ``` + + #[inline(always)] + pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T> + where + T: Borrow<Q>, + Q: Ord, + { + Recover::get(&self.map, value) + } + + /// Returns `true` if `self` has no elements in common with `other`. + /// This is equivalent to checking for an empty intersection. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let a: BTreeSet<_> = [1, 2, 3].iter().cloned().collect(); + /// let mut b = BTreeSet::new(); + /// + /// assert_eq!(a.is_disjoint(&b), true); + /// b.insert(4); + /// assert_eq!(a.is_disjoint(&b), true); + /// b.insert(1); + /// assert_eq!(a.is_disjoint(&b), false); + /// ``` + + #[inline] + pub fn is_disjoint(&self, other: &BTreeSet<T>) -> bool { + self.intersection(other).next().is_none() + } + + /// Returns `true` if the set is a subset of another, + /// i.e., `other` contains at least all the values in `self`. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let sup: BTreeSet<_> = [1, 2, 3].iter().cloned().collect(); + /// let mut set = BTreeSet::new(); + /// + /// assert_eq!(set.is_subset(&sup), true); + /// set.insert(2); + /// assert_eq!(set.is_subset(&sup), true); + /// set.insert(4); + /// assert_eq!(set.is_subset(&sup), false); + /// ``` + + pub fn is_subset(&self, other: &BTreeSet<T>) -> bool { + // Same result as self.difference(other).next().is_none() + // but the 3 paths below are faster (in order: hugely, 20%, 5%). + if self.len() > other.len() { + false + } else if self.len() > other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF { + // Self is not much smaller than other set. + // Stolen from TreeMap + let mut x = self.iter(); + let mut y = other.iter(); + let mut a = x.next(); + let mut b = y.next(); + while a.is_some() { + if b.is_none() { + return false; + } + + let a1 = a.unwrap(); + let b1 = b.unwrap(); + + match b1.cmp(a1) { + Less => (), + Greater => return false, + Equal => a = x.next(), + } + + b = y.next(); + } + true + } else { + // Big difference in number of elements, or both sets are empty. + // Iterate the small set, searching for matches in the large set. + for next in self { + if !other.contains(next) { + return false; + } + } + true + } + } + + /// Returns `true` if the set is a superset of another, + /// i.e., `self` contains at least all the values in `other`. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let sub: BTreeSet<_> = [1, 2].iter().cloned().collect(); + /// let mut set = BTreeSet::new(); + /// + /// assert_eq!(set.is_superset(&sub), false); + /// + /// set.insert(0); + /// set.insert(1); + /// assert_eq!(set.is_superset(&sub), false); + /// + /// set.insert(2); + /// assert_eq!(set.is_superset(&sub), true); + /// ``` + + #[inline(always)] + pub fn is_superset(&self, other: &BTreeSet<T>) -> bool { + other.is_subset(self) + } + + /// Adds a value to the set. + /// + /// If the set did not have this value present, `true` is returned. + /// + /// If the set did have this value present, `false` is returned, and the + /// entry is not updated. See the [module-level documentation] for more. + /// + /// [module-level documentation]: index.html#insert-and-complex-keys + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut set = BTreeSet::new(); + /// + /// assert_eq!(set.insert(2), true); + /// assert_eq!(set.insert(2), false); + /// assert_eq!(set.len(), 1); + /// ``` + + #[inline] + pub fn try_insert(&mut self, value: T) -> Result<bool, TryReserveError> { + Ok(self.map.try_insert(value, ())?.is_none()) + } + + /// Adds a value to the set, replacing the existing value, if any, that is equal to the given + /// one. Returns the replaced value. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut set = BTreeSet::new(); + /// set.insert(Vec::<i32>::new()); + /// + /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0); + /// set.replace(Vec::with_capacity(10)); + /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10); + /// ``` + + #[inline] + pub fn replace(&mut self, value: T) -> Result<Option<T>, TryReserveError> { + Ok(Recover::replace(&mut self.map, value)?) + } + + /// Removes a value from the set. Returns whether the value was + /// present in the set. + /// + /// The value may be any borrowed form of the set's value type, + /// but the ordering on the borrowed form *must* match the + /// ordering on the value type. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut set = BTreeSet::new(); + /// + /// set.insert(2); + /// assert_eq!(set.remove(&2), true); + /// assert_eq!(set.remove(&2), false); + /// ``` + + #[inline(always)] + pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool + where + T: Borrow<Q>, + Q: Ord, + { + self.map.remove(value).is_some() + } + + /// Removes and returns the value in the set, if any, that is equal to the given one. + /// + /// The value may be any borrowed form of the set's value type, + /// but the ordering on the borrowed form *must* match the + /// ordering on the value type. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect(); + /// assert_eq!(set.take(&2), Some(2)); + /// assert_eq!(set.take(&2), None); + /// ``` + + #[inline(always)] + pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> + where + T: Borrow<Q>, + Q: Ord, + { + Recover::take(&mut self.map, value) + } + + /// Moves all elements from `other` into `Self`, leaving `other` empty. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut a = BTreeSet::new(); + /// a.insert(1); + /// a.insert(2); + /// a.insert(3); + /// + /// let mut b = BTreeSet::new(); + /// b.insert(3); + /// b.insert(4); + /// b.insert(5); + /// + /// a.append(&mut b); + /// + /// assert_eq!(a.len(), 5); + /// assert_eq!(b.len(), 0); + /// + /// assert!(a.contains(&1)); + /// assert!(a.contains(&2)); + /// assert!(a.contains(&3)); + /// assert!(a.contains(&4)); + /// assert!(a.contains(&5)); + /// ``` + + #[inline(always)] + pub fn append(&mut self, other: &mut Self) { + self.map.append(&mut other.map); + } + + /// Splits the collection into two at the given key. Returns everything after the given key, + /// including the key. + /// + /// # Examples + /// + /// Basic usage: + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut a = BTreeSet::new(); + /// a.insert(1); + /// a.insert(2); + /// a.insert(3); + /// a.insert(17); + /// a.insert(41); + /// + /// let b = a.split_off(&3); + /// + /// assert_eq!(a.len(), 2); + /// assert_eq!(b.len(), 3); + /// + /// assert!(a.contains(&1)); + /// assert!(a.contains(&2)); + /// + /// assert!(b.contains(&3)); + /// assert!(b.contains(&17)); + /// assert!(b.contains(&41)); + /// ``` + + #[inline] + pub fn try_split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Result<Self, TryReserveError> + where + T: Borrow<Q>, + { + Ok(BTreeSet { + map: self.map.split_off(key)?, + }) + } +} + +impl<T> BTreeSet<T> { + /// Gets an iterator that visits the values in the `BTreeSet` in ascending order. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let set: BTreeSet<usize> = [1, 2, 3].iter().cloned().collect(); + /// let mut set_iter = set.iter(); + /// assert_eq!(set_iter.next(), Some(&1)); + /// assert_eq!(set_iter.next(), Some(&2)); + /// assert_eq!(set_iter.next(), Some(&3)); + /// assert_eq!(set_iter.next(), None); + /// ``` + /// + /// Values returned by the iterator are returned in ascending order: + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let set: BTreeSet<usize> = [3, 1, 2].iter().cloned().collect(); + /// let mut set_iter = set.iter(); + /// assert_eq!(set_iter.next(), Some(&1)); + /// assert_eq!(set_iter.next(), Some(&2)); + /// assert_eq!(set_iter.next(), Some(&3)); + /// assert_eq!(set_iter.next(), None); + /// ``` + + #[inline(always)] + pub fn iter(&self) -> Iter<'_, T> { + Iter { + iter: self.map.keys(), + } + } + + /// Returns the number of elements in the set. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut v = BTreeSet::new(); + /// assert_eq!(v.len(), 0); + /// v.insert(1); + /// assert_eq!(v.len(), 1); + /// ``` + + #[inline(always)] + pub fn len(&self) -> usize { + self.map.len() + } + + /// Returns `true` if the set contains no elements. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut v = BTreeSet::new(); + /// assert!(v.is_empty()); + /// v.insert(1); + /// assert!(!v.is_empty()); + /// ``` + + #[inline(always)] + pub fn is_empty(&self) -> bool { + self.len() == 0 + } +} + +impl<T: Ord> FromIterator<T> for BTreeSet<T> { + #[inline] + fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BTreeSet<T> { + let mut set = BTreeSet::new(); + set.extend(iter); + set + } +} + +impl<T> IntoIterator for BTreeSet<T> { + type Item = T; + type IntoIter = IntoIter<T>; + + /// Gets an iterator for moving out the `BTreeSet`'s contents. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let set: BTreeSet<usize> = [1, 2, 3, 4].iter().cloned().collect(); + /// + /// let v: Vec<_> = set.into_iter().collect(); + /// assert_eq!(v, [1, 2, 3, 4]); + /// ``` + #[inline(always)] + fn into_iter(self) -> IntoIter<T> { + IntoIter { + iter: self.map.into_iter(), + } + } +} + +impl<'a, T> IntoIterator for &'a BTreeSet<T> { + type Item = &'a T; + type IntoIter = Iter<'a, T>; + + #[inline(always)] + fn into_iter(self) -> Iter<'a, T> { + self.iter() + } +} + +impl<T: Ord> Extend<T> for BTreeSet<T> { + #[inline] + fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) { + iter.into_iter().for_each(move |elem| { + self.try_insert(elem).expect("Out of Mem"); + }); + } +} + +impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BTreeSet<T> { + #[inline] + fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { + self.extend(iter.into_iter().cloned()); + } +} + +impl<T: Ord> Default for BTreeSet<T> { + /// Makes an empty `BTreeSet<T>` with a reasonable choice of B. + #[inline(always)] + fn default() -> BTreeSet<T> { + BTreeSet::new() + } +} + +impl<T: Ord + Clone> Sub<&BTreeSet<T>> for &BTreeSet<T> { + type Output = BTreeSet<T>; + + /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect(); + /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect(); + /// + /// let result = &a - &b; + /// let result_vec: Vec<_> = result.into_iter().collect(); + /// assert_eq!(result_vec, [1, 2]); + /// ``` + fn sub(self, rhs: &BTreeSet<T>) -> BTreeSet<T> { + self.difference(rhs).cloned().collect() + } +} + +impl<T: Ord + Clone> BitXor<&BTreeSet<T>> for &BTreeSet<T> { + type Output = BTreeSet<T>; + + /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect(); + /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect(); + /// + /// let result = &a ^ &b; + /// let result_vec: Vec<_> = result.into_iter().collect(); + /// assert_eq!(result_vec, [1, 4]); + /// ``` + fn bitxor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> { + self.symmetric_difference(rhs).cloned().collect() + } +} + +impl<T: Ord + Clone> BitAnd<&BTreeSet<T>> for &BTreeSet<T> { + type Output = BTreeSet<T>; + + /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect(); + /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect(); + /// + /// let result = &a & &b; + /// let result_vec: Vec<_> = result.into_iter().collect(); + /// assert_eq!(result_vec, [2, 3]); + /// ``` + fn bitand(self, rhs: &BTreeSet<T>) -> BTreeSet<T> { + self.intersection(rhs).cloned().collect() + } +} + +impl<T: Ord + Clone> BitOr<&BTreeSet<T>> for &BTreeSet<T> { + type Output = BTreeSet<T>; + + /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect(); + /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect(); + /// + /// let result = &a | &b; + /// let result_vec: Vec<_> = result.into_iter().collect(); + /// assert_eq!(result_vec, [1, 2, 3, 4, 5]); + /// ``` + fn bitor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> { + self.union(rhs).cloned().collect() + } +} + +impl<T: Debug> Debug for BTreeSet<T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_set().entries(self.iter()).finish() + } +} + +impl<T> Clone for Iter<'_, T> { + #[inline(always)] + fn clone(&self) -> Self { + Iter { + iter: self.iter.clone(), + } + } +} + +impl<'a, T> Iterator for Iter<'a, T> { + type Item = &'a T; + + #[inline(always)] + fn next(&mut self) -> Option<&'a T> { + self.iter.next() + } + + #[inline(always)] + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<'a, T> DoubleEndedIterator for Iter<'a, T> { + #[inline(always)] + fn next_back(&mut self) -> Option<&'a T> { + self.iter.next_back() + } +} + +impl<T> ExactSizeIterator for Iter<'_, T> { + #[inline(always)] + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<T> FusedIterator for Iter<'_, T> {} + +impl<T> Iterator for IntoIter<T> { + type Item = T; + + #[inline] + fn next(&mut self) -> Option<T> { + self.iter.next().map(|(k, _)| k) + } + + #[inline(always)] + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<T> DoubleEndedIterator for IntoIter<T> { + #[inline] + fn next_back(&mut self) -> Option<T> { + self.iter.next_back().map(|(k, _)| k) + } +} + +impl<T> ExactSizeIterator for IntoIter<T> { + #[inline(always)] + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<T> FusedIterator for IntoIter<T> {} + +impl<T> Clone for Range<'_, T> { + #[inline(always)] + fn clone(&self) -> Self { + Range { + iter: self.iter.clone(), + } + } +} + +impl<'a, T> Iterator for Range<'a, T> { + type Item = &'a T; + + #[inline] + fn next(&mut self) -> Option<&'a T> { + self.iter.next().map(|(k, _)| k) + } +} + +impl<'a, T> DoubleEndedIterator for Range<'a, T> { + #[inline] + fn next_back(&mut self) -> Option<&'a T> { + self.iter.next_back().map(|(k, _)| k) + } +} + +impl<T> FusedIterator for Range<'_, T> {} + +/// Compares `x` and `y`, but return `short` if x is None and `long` if y is None +fn cmp_opt<T: Ord>(x: Option<&T>, y: Option<&T>, short: Ordering, long: Ordering) -> Ordering { + match (x, y) { + (None, _) => short, + (_, None) => long, + (Some(x1), Some(y1)) => x1.cmp(y1), + } +} + +impl<T> Clone for Difference<'_, T> { + fn clone(&self) -> Self { + Difference { + inner: match &self.inner { + DifferenceInner::Stitch { + self_iter, + other_iter, + } => DifferenceInner::Stitch { + self_iter: self_iter.clone(), + other_iter: other_iter.clone(), + }, + DifferenceInner::Search { + self_iter, + other_set, + } => DifferenceInner::Search { + self_iter: self_iter.clone(), + other_set, + }, + }, + } + } +} + +impl<'a, T: Ord> Iterator for Difference<'a, T> { + type Item = &'a T; + + fn next(&mut self) -> Option<&'a T> { + match &mut self.inner { + DifferenceInner::Stitch { + self_iter, + other_iter, + } => { + let mut self_next = self_iter.next()?; + loop { + match other_iter + .peek() + .map_or(Less, |other_next| Ord::cmp(self_next, other_next)) + { + Less => return Some(self_next), + Equal => { + self_next = self_iter.next()?; + other_iter.next(); + } + Greater => { + other_iter.next(); + } + } + } + } + DifferenceInner::Search { + self_iter, + other_set, + } => loop { + let self_next = self_iter.next()?; + if !other_set.contains(&self_next) { + return Some(self_next); + } + }, + } + } + + fn size_hint(&self) -> (usize, Option<usize>) { + let (self_len, other_len) = match &self.inner { + DifferenceInner::Stitch { + self_iter, + other_iter, + } => (self_iter.len(), other_iter.len()), + DifferenceInner::Search { + self_iter, + other_set, + } => (self_iter.len(), other_set.len()), + }; + (self_len.saturating_sub(other_len), Some(self_len)) + } +} + +impl<T: Ord> FusedIterator for Difference<'_, T> {} + +impl<T> Clone for SymmetricDifference<'_, T> { + fn clone(&self) -> Self { + SymmetricDifference { + a: self.a.clone(), + b: self.b.clone(), + } + } +} + +impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> { + type Item = &'a T; + + fn next(&mut self) -> Option<&'a T> { + loop { + match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) { + Less => return self.a.next(), + Equal => { + self.a.next(); + self.b.next(); + } + Greater => return self.b.next(), + } + } + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + (0, Some(self.a.len() + self.b.len())) + } +} + +impl<T: Ord> FusedIterator for SymmetricDifference<'_, T> {} + +impl<T> Clone for Intersection<'_, T> { + fn clone(&self) -> Self { + Intersection { + inner: match &self.inner { + IntersectionInner::Stitch { + small_iter, + other_iter, + } => IntersectionInner::Stitch { + small_iter: small_iter.clone(), + other_iter: other_iter.clone(), + }, + IntersectionInner::Search { + small_iter, + large_set, + } => IntersectionInner::Search { + small_iter: small_iter.clone(), + large_set, + }, + }, + } + } +} + +impl<'a, T: Ord> Iterator for Intersection<'a, T> { + type Item = &'a T; + + fn next(&mut self) -> Option<&'a T> { + match &mut self.inner { + IntersectionInner::Stitch { + small_iter, + other_iter, + } => { + let mut small_next = small_iter.next()?; + let mut other_next = other_iter.next()?; + loop { + match Ord::cmp(small_next, other_next) { + Less => small_next = small_iter.next()?, + Greater => other_next = other_iter.next()?, + Equal => return Some(small_next), + } + } + } + IntersectionInner::Search { + small_iter, + large_set, + } => loop { + let small_next = small_iter.next()?; + if large_set.contains(&small_next) { + return Some(small_next); + } + }, + } + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + let min_len = match &self.inner { + IntersectionInner::Stitch { small_iter, .. } => small_iter.len(), + IntersectionInner::Search { small_iter, .. } => small_iter.len(), + }; + (0, Some(min_len)) + } +} + +impl<T: Ord> FusedIterator for Intersection<'_, T> {} + +impl<T> Clone for Union<'_, T> { + #[inline] + fn clone(&self) -> Self { + Union { + a: self.a.clone(), + b: self.b.clone(), + } + } +} + +impl<'a, T: Ord> Iterator for Union<'a, T> { + type Item = &'a T; + + fn next(&mut self) -> Option<&'a T> { + match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) { + Less => self.a.next(), + Equal => { + self.b.next(); + self.a.next() + } + Greater => self.b.next(), + } + } + + fn size_hint(&self) -> (usize, Option<usize>) { + let a_len = self.a.len(); + let b_len = self.b.len(); + (max(a_len, b_len), Some(a_len + b_len)) + } +} + +impl<T: Ord> FusedIterator for Union<'_, T> {} diff --git a/third_party/rust/fallible_collections/src/format.rs b/third_party/rust/fallible_collections/src/format.rs new file mode 100644 index 0000000000..47a5fb9082 --- /dev/null +++ b/third_party/rust/fallible_collections/src/format.rs @@ -0,0 +1,46 @@ +//! A try_format! macro replacing format! +use super::FallibleVec; +use crate::TryReserveError; +use alloc::fmt::{Arguments, Write}; +use alloc::string::String; + +/// Take a max capacity a try allocating a string with it. +/// +/// # Warning: +/// +/// the max capacity must be > to the formating of the +/// arguments. If writing the argument on the string exceed the +/// capacity, no error is return and an allocation can occurs which +/// can lead to a panic +pub fn try_format(max_capacity: usize, args: Arguments<'_>) -> Result<String, TryReserveError> { + let v = FallibleVec::try_with_capacity(max_capacity)?; + let mut s = String::from_utf8(v).expect("wtf an empty vec should be valid utf8"); + s.write_fmt(args) + .expect("a formatting trait implementation returned an error"); + Ok(s) +} + +#[macro_export] +/// Take a max capacity a try allocating a string with it. +/// +/// # Warning: +/// +/// the max capacity must be > to the formating of the +/// arguments. If writing the argument on the string exceed the +/// capacity, no error is return and an allocation can occurs which +/// can lead to a panic +macro_rules! tryformat { + ($max_capacity:tt, $($arg:tt)*) => ( + $crate::format::try_format($max_capacity, format_args!($($arg)*)) + ) +} + +#[cfg(test)] +mod tests { + #[test] + fn format() { + assert_eq!(tryformat!(1, "1").unwrap(), format!("1")); + assert_eq!(tryformat!(1, "{}", 1).unwrap(), format!("{}", 1)); + assert_eq!(tryformat!(3, "{}", 123).unwrap(), format!("{}", 123)); + } +} diff --git a/third_party/rust/fallible_collections/src/hashmap.rs b/third_party/rust/fallible_collections/src/hashmap.rs new file mode 100644 index 0000000000..b55361e7a7 --- /dev/null +++ b/third_party/rust/fallible_collections/src/hashmap.rs @@ -0,0 +1,139 @@ +//! Implement Fallible HashMap +use super::TryClone; +use crate::TryReserveError; +use core::borrow::Borrow; +use core::default::Default; +use core::fmt::Debug; +use core::hash::Hash; + +#[cfg(not(all(feature = "std", feature = "rust_1_57")))] +type HashMap<K, V> = hashbrown::hash_map::HashMap<K, V>; + +#[cfg(all(feature = "std", feature = "rust_1_57"))] +type HashMap<K, V> = std::collections::HashMap<K, V>; + +#[cfg(not(all(feature = "std", feature = "rust_1_57")))] +use hashbrown::hash_map::{Iter, IntoIter}; + +#[cfg(all(feature = "std", feature = "rust_1_57"))] +use std::collections::hash_map::{Iter, IntoIter}; + +pub struct TryHashMap<K, V> { + inner: HashMap<K, V>, +} + +impl<K, V> Default for TryHashMap<K, V> { + #[inline(always)] + fn default() -> Self { + Self { + inner: Default::default(), + } + } +} + +impl<K: Debug, V: Debug> Debug for TryHashMap<K, V> { + #[inline] + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { + self.inner.fmt(f) + } +} + +impl<K, V> TryHashMap<K, V> +where + K: Eq + Hash, +{ + #[inline] + pub fn with_capacity(capacity: usize) -> Result<Self, TryReserveError> { + let mut map = Self { + inner: HashMap::new(), + }; + map.reserve(capacity)?; + Ok(map) + } + + #[inline(always)] + pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> + where + K: Borrow<Q>, + Q: Hash + Eq, + { + self.inner.get(k) + } + + #[inline] + pub fn insert(&mut self, k: K, v: V) -> Result<Option<V>, TryReserveError> { + self.reserve(if self.inner.capacity() == 0 { 4 } else { 1 })?; + Ok(self.inner.insert(k, v)) + } + + #[inline(always)] + pub fn iter(&self) -> Iter<'_, K, V> { + self.inner.iter() + } + + #[inline(always)] + pub fn len(&self) -> usize { + self.inner.len() + } + + #[inline(always)] + pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V> + where + K: Borrow<Q>, + Q: Hash + Eq, + { + self.inner.remove(k) + } + + #[inline(always)] + fn reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { + #[cfg(not(all(feature = "std", feature = "rust_1_57")))] + { + self.inner.try_reserve(additional) + } + + #[cfg(all(feature = "std", feature = "rust_1_57"))] + { + self.inner.try_reserve(additional).map_err(|_| { + crate::make_try_reserve_error(self.len(), additional, + core::mem::size_of::<K>() + core::mem::size_of::<V>(), + core::mem::align_of::<K>().max(core::mem::align_of::<V>()), + ) + }) + } + } +} + +impl<K, V> IntoIterator for TryHashMap<K, V> { + type Item = (K, V); + type IntoIter = IntoIter<K, V>; + + #[inline(always)] + fn into_iter(self) -> Self::IntoIter { + self.inner.into_iter() + } +} + +impl<K, V> TryClone for TryHashMap<K, V> +where + K: Eq + Hash + TryClone, + V: TryClone, +{ + fn try_clone(&self) -> Result<Self, TryReserveError> { + let mut clone = Self::with_capacity(self.inner.len())?; + + for (key, value) in self.inner.iter() { + clone.insert(key.try_clone()?, value.try_clone()?)?; + } + + Ok(clone) + } +} + +#[test] +fn tryhashmap_oom() { + match TryHashMap::<char, char>::default().reserve(core::usize::MAX) { + Ok(_) => panic!("it should be OOM"), + _ => (), + } +} diff --git a/third_party/rust/fallible_collections/src/lib.rs b/third_party/rust/fallible_collections/src/lib.rs new file mode 100644 index 0000000000..45dcd48d17 --- /dev/null +++ b/third_party/rust/fallible_collections/src/lib.rs @@ -0,0 +1,91 @@ +//! impl Fallible collections on allocation errors, quite as describe +//! in [RFC 2116](https://github.com/rust-lang/rfcs/blob/master/text/2116-alloc-me-maybe.md) +//! This was used in the turbofish OS hobby project to mitigate the +//! the lack of faillible allocation in rust. +//! +//! The `Try*` types in this module are thin wrappers around the stdlib types to add +//! support for fallible allocation. The API differences from the stdlib types ensure +//! that all operations which allocate return a `Result`. For the most part, this simply +//! means adding a `Result` return value to functions which return nothing or a +//! non-`Result` value. However, these types implement some traits whose API cannot +//! communicate failure, but which do require allocation, so it is important that these +//! wrapper types do not implement these traits. +//! +//! Specifically, these types must not implement any of the following traits: +//! - Clone +//! - Extend +//! - From +//! - FromIterator +//! +//! This list may not be exhaustive. Exercise caution when implementing +//! any new traits to ensure they won't potentially allocate in a way that +//! can't return a Result to indicate allocation failure. + +#![cfg_attr(not(test), no_std)] +#![cfg_attr(all(feature = "unstable", not(feature = "rust_1_57")), feature(try_reserve))] +#![cfg_attr(feature = "unstable", feature(min_specialization))] +#![cfg_attr(feature = "unstable", feature(allocator_api))] +#![cfg_attr(feature = "unstable", feature(dropck_eyepatch))] +#![cfg_attr(feature = "unstable", feature(ptr_internals))] +#![cfg_attr(feature = "unstable", feature(core_intrinsics))] +#![cfg_attr(all(feature = "unstable", not(feature = "rust_1_57")), feature(maybe_uninit_ref))] +#![cfg_attr(feature = "unstable", feature(maybe_uninit_slice))] +#![cfg_attr(feature = "unstable", feature(maybe_uninit_extra))] +#![cfg_attr(feature = "unstable", feature(maybe_uninit_uninit_array))] +extern crate alloc; +#[cfg(feature = "std")] +extern crate std; + +pub mod boxed; +pub use boxed::*; +#[macro_use] +pub mod vec; +pub use vec::*; +pub mod rc; +pub use rc::*; +pub mod arc; +pub use arc::*; +#[cfg(feature = "unstable")] +pub mod btree; +#[cfg(not(feature = "unstable"))] +pub mod hashmap; +#[cfg(not(feature = "unstable"))] +pub use hashmap::*; +#[macro_use] +pub mod format; +pub mod try_clone; + +#[cfg(all(feature = "unstable", not(feature = "rust_1_57")))] +pub use alloc::collections::TryReserveError; +#[cfg(not(all(feature = "unstable", not(feature = "rust_1_57"))))] +pub use hashbrown::TryReserveError; + +#[cfg(feature = "std_io")] +pub use vec::std_io::*; + +/// trait for trying to clone an elem, return an error instead of +/// panic if allocation failed +/// # Examples +/// +/// ``` +/// use fallible_collections::TryClone; +/// let mut vec = vec![42, 100]; +/// assert_eq!(vec.try_clone().unwrap(), vec) +/// ``` +pub trait TryClone { + /// try clone method, (Self must be sized because of Result + /// constraint) + fn try_clone(&self) -> Result<Self, TryReserveError> + where + Self: core::marker::Sized; +} + +#[cfg(feature = "rust_1_57")] +fn make_try_reserve_error(len: usize, additional: usize, elem_size: usize, align: usize) -> hashbrown::TryReserveError { + if let Some(size) = len.checked_add(additional).and_then(|l| l.checked_mul(elem_size)) { + if let Ok(layout) = alloc::alloc::Layout::from_size_align(size, align) { + return TryReserveError::AllocError { layout } + } + } + TryReserveError::CapacityOverflow +} diff --git a/third_party/rust/fallible_collections/src/rc.rs b/third_party/rust/fallible_collections/src/rc.rs new file mode 100644 index 0000000000..4fc16dc2af --- /dev/null +++ b/third_party/rust/fallible_collections/src/rc.rs @@ -0,0 +1,35 @@ +//! Implement a Fallible Rc +use super::FallibleBox; +use crate::TryReserveError; +use alloc::boxed::Box; +use alloc::rc::Rc; +/// trait to implement Fallible Rc +pub trait FallibleRc<T> { + /// try creating a new Rc, returning a Result<Box<T>, + /// TryReserveError> if allocation failed + fn try_new(t: T) -> Result<Self, TryReserveError> + where + Self: Sized; +} + +impl<T> FallibleRc<T> for Rc<T> { + fn try_new(t: T) -> Result<Self, TryReserveError> { + let b = <Box<T> as FallibleBox<T>>::try_new(t)?; + Ok(Rc::from(b)) + } +} + +#[cfg(test)] +mod test { + #[test] + fn fallible_rc() { + use std::rc::Rc; + + let mut x = Rc::new(3); + *Rc::get_mut(&mut x).unwrap() = 4; + assert_eq!(*x, 4); + + let _y = Rc::clone(&x); + assert!(Rc::get_mut(&mut x).is_none()); + } +} diff --git a/third_party/rust/fallible_collections/src/try_clone.rs b/third_party/rust/fallible_collections/src/try_clone.rs new file mode 100644 index 0000000000..a8ff0442b4 --- /dev/null +++ b/third_party/rust/fallible_collections/src/try_clone.rs @@ -0,0 +1,39 @@ +//! this module implements try clone for primitive rust types + +use super::TryClone; +use crate::TryReserveError; + +macro_rules! impl_try_clone { + ($($e: ty),*) => { + $(impl TryClone for $e { + #[inline(always)] + fn try_clone(&self) -> Result<Self, TryReserveError> + where + Self: core::marker::Sized, + { + Ok(*self) + } + } + )* + } +} + +impl_try_clone!(u8, u16, u32, u64, i8, i16, i32, i64, usize, isize, bool); + +impl<T: TryClone> TryClone for Option<T> { + #[inline] + fn try_clone(&self) -> Result<Self, TryReserveError> { + Ok(match self { + Some(t) => Some(t.try_clone()?), + None => None, + }) + } +} +// impl<T: Copy> TryClone for T { +// fn try_clone(&self) -> Result<Self, TryReserveError> +// where +// Self: core::marker::Sized, +// { +// Ok(*self) +// } +// } diff --git a/third_party/rust/fallible_collections/src/vec.rs b/third_party/rust/fallible_collections/src/vec.rs new file mode 100644 index 0000000000..6197b5b5d6 --- /dev/null +++ b/third_party/rust/fallible_collections/src/vec.rs @@ -0,0 +1,968 @@ +//! Implement Fallible Vec +use super::TryClone; +use crate::TryReserveError; +#[allow(unused_imports)] +use alloc::alloc::{alloc, realloc, Layout}; +use alloc::vec::Vec; +use core::convert::TryInto as _; + +#[cfg(feature = "unstable")] +#[macro_export] +/// macro trying to create a vec, return a +/// Result<Vec<T>,TryReserveError> +macro_rules! try_vec { + ($elem:expr; $n:expr) => ( + $crate::vec::try_from_elem($elem, $n) + ); + ($($x:expr),*) => ( + match <alloc::boxed::Box<_> as $crate::boxed::FallibleBox<_>>::try_new([$($x),*]) { + Err(e) => Err(e), + Ok(b) => Ok(<[_]>::into_vec(b)), + } + ); + ($($x:expr,)*) => ($crate::try_vec![$($x),*]) +} + +/// trait implementing all fallible methods on vec +pub trait FallibleVec<T> { + /// see reserve + fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>; + /// see push + fn try_push(&mut self, elem: T) -> Result<(), TryReserveError>; + /// try push and give back ownership in case of error + fn try_push_give_back(&mut self, elem: T) -> Result<(), (T, TryReserveError)>; + /// see with capacity, (Self must be sized by the constraint of Result) + fn try_with_capacity(capacity: usize) -> Result<Self, TryReserveError> + where + Self: core::marker::Sized; + /// see insert + fn try_insert(&mut self, index: usize, element: T) -> Result<(), (T, TryReserveError)>; + /// see append + fn try_append(&mut self, other: &mut Self) -> Result<(), TryReserveError>; + /// see resize, only works when the `value` implements Copy, otherwise, look at try_resize_no_copy + fn try_resize(&mut self, new_len: usize, value: T) -> Result<(), TryReserveError> + where + T: Copy + Clone; + fn try_resize_with<F>(&mut self, new_len: usize, f: F) -> Result<(), TryReserveError> + where + F: FnMut() -> T; + /// resize the vec by trying to clone the value repeatingly + fn try_resize_no_copy(&mut self, new_len: usize, value: T) -> Result<(), TryReserveError> + where + T: TryClone; + /// see resize, only works when the `value` implements Copy, otherwise, look at try_extend_from_slice_no_copy + fn try_extend_from_slice(&mut self, other: &[T]) -> Result<(), TryReserveError> + where + T: Copy + Clone; + /// extend the vec by trying to clone the value in `other` + fn try_extend_from_slice_no_copy(&mut self, other: &[T]) -> Result<(), TryReserveError> + where + T: TryClone; +} + +/// TryVec is a thin wrapper around alloc::vec::Vec to provide support for +/// fallible allocation. +/// +/// See the crate documentation for more. +#[derive(PartialEq)] +pub struct TryVec<T> { + inner: Vec<T>, +} + +impl<T> Default for TryVec<T> { + #[inline(always)] + fn default() -> Self { + Self { + inner: Default::default(), + } + } +} + +impl<T: core::fmt::Debug> core::fmt::Debug for TryVec<T> { + #[inline] + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { + self.inner.fmt(f) + } +} + +impl<T> TryVec<T> { + #[inline(always)] + pub fn new() -> Self { + Self { inner: Vec::new() } + } + + #[inline] + pub fn with_capacity(capacity: usize) -> Result<Self, TryReserveError> { + Ok(Self { + inner: FallibleVec::try_with_capacity(capacity)?, + }) + } + + #[inline(always)] + pub fn append(&mut self, other: &mut Self) -> Result<(), TryReserveError> { + FallibleVec::try_append(&mut self.inner, &mut other.inner) + } + + #[inline(always)] + pub fn as_mut_slice(&mut self) -> &mut [T] { + self + } + + #[inline(always)] + pub fn as_slice(&self) -> &[T] { + self + } + + #[inline(always)] + pub fn clear(&mut self) { + self.inner.clear() + } + + #[cfg(test)] + pub fn into_inner(self) -> Vec<T> { + self.inner + } + + #[inline(always)] + pub fn is_empty(&self) -> bool { + self.inner.is_empty() + } + + #[inline(always)] + pub fn iter_mut(&mut self) -> IterMut<T> { + IterMut { + inner: self.inner.iter_mut(), + } + } + + #[inline(always)] + pub fn iter(&self) -> Iter<T> { + Iter { + inner: self.inner.iter(), + } + } + + #[inline(always)] + pub fn pop(&mut self) -> Option<T> { + self.inner.pop() + } + + #[inline(always)] + pub fn push(&mut self, value: T) -> Result<(), TryReserveError> { + FallibleVec::try_push(&mut self.inner, value) + } + + #[inline(always)] + pub fn reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { + FallibleVec::try_reserve(&mut self.inner, additional) + } + + #[inline(always)] + pub fn resize_with<F>(&mut self, new_len: usize, f: F) -> Result<(), TryReserveError> + where + F: FnMut() -> T, + { + FallibleVec::try_resize_with(&mut self.inner, new_len, f) + } +} + +impl<T: TryClone> TryClone for TryVec<T> { + #[inline] + fn try_clone(&self) -> Result<Self, TryReserveError> { + self.as_slice().try_into() + } +} + +impl<T: TryClone> TryVec<TryVec<T>> { + pub fn concat(&self) -> Result<TryVec<T>, TryReserveError> { + let size = self.iter().map(|v| v.inner.len()).sum(); + let mut result = TryVec::with_capacity(size)?; + for v in self.iter() { + result.inner.try_extend_from_slice_no_copy(&v.inner)?; + } + Ok(result) + } +} + +impl<T: TryClone> TryVec<T> { + #[inline(always)] + pub fn extend_from_slice(&mut self, other: &[T]) -> Result<(), TryReserveError> { + self.inner.try_extend_from_slice_no_copy(other) + } +} + +impl<T> IntoIterator for TryVec<T> { + type Item = T; + type IntoIter = alloc::vec::IntoIter<T>; + + #[inline(always)] + fn into_iter(self) -> Self::IntoIter { + self.inner.into_iter() + } +} + +impl<'a, T> IntoIterator for &'a TryVec<T> { + type Item = &'a T; + type IntoIter = alloc::slice::Iter<'a, T>; + + #[inline(always)] + fn into_iter(self) -> Self::IntoIter { + self.inner.iter() + } +} + +#[cfg(feature = "std_io")] +pub mod std_io { + use super::*; + use std::io::{self, Read, Take, Write}; + + pub trait TryRead { + fn try_read_to_end(&mut self, buf: &mut TryVec<u8>) -> io::Result<usize>; + + #[inline] + fn read_into_try_vec(&mut self) -> io::Result<TryVec<u8>> { + let mut buf = TryVec::new(); + self.try_read_to_end(&mut buf)?; + Ok(buf) + } + } + + impl<T: Read> TryRead for Take<T> { + /// This function reserves the upper limit of what `src` can generate before + /// reading all bytes until EOF in this source, placing them into `buf`. If the + /// allocation is unsuccessful, or reading from the source generates an error + /// before reaching EOF, this will return an error. Otherwise, it will return + /// the number of bytes read. + /// + /// Since `Take::limit()` may return a value greater than the number of bytes + /// which can be read from the source, it's possible this function may fail + /// in the allocation phase even though allocating the number of bytes available + /// to read would have succeeded. In general, it is assumed that the callers + /// have accurate knowledge of the number of bytes of interest and have created + /// `src` accordingly. + #[inline] + fn try_read_to_end(&mut self, buf: &mut TryVec<u8>) -> io::Result<usize> { + try_read_up_to(self, self.limit(), buf) + } + } + + /// Read up to `limit` bytes from `src`, placing them into `buf` and returning the + /// number of bytes read. Space for `limit` additional bytes is reserved in `buf`, so + /// this function will return an error if the allocation fails. + pub fn try_read_up_to<R: Read>( + src: &mut R, + limit: u64, + buf: &mut TryVec<u8>, + ) -> io::Result<usize> { + let additional = limit + .try_into() + .map_err(|e| io::Error::new(io::ErrorKind::Other, e))?; + buf.reserve(additional) + .map_err(|_| io::Error::new(io::ErrorKind::Other, "reserve allocation failed"))?; + let bytes_read = src.take(limit).read_to_end(&mut buf.inner)?; + Ok(bytes_read) + } + + impl Write for TryVec<u8> { + fn write(&mut self, buf: &[u8]) -> io::Result<usize> { + self.extend_from_slice(buf) + .map_err(|_| io::Error::new(io::ErrorKind::Other, "extend_from_slice failed"))?; + Ok(buf.len()) + } + + #[inline(always)] + fn flush(&mut self) -> io::Result<()> { + Ok(()) + } + } + + #[cfg(test)] + mod tests { + use super::*; + + #[test] + fn try_read_to_end() { + let mut src = b"1234567890".take(5); + let mut buf = TryVec::new(); + src.try_read_to_end(&mut buf).unwrap(); + assert_eq!(buf.len(), 5); + assert_eq!(buf, b"12345".as_ref()); + } + + #[test] + fn read_into_try_vec() { + let mut src = b"1234567890".take(5); + let buf = src.read_into_try_vec().unwrap(); + assert_eq!(buf.len(), 5); + assert_eq!(buf, b"12345".as_ref()); + } + + #[test] + fn read_into_try_vec_oom() { + let mut src = b"1234567890".take(core::usize::MAX.try_into().expect("usize < u64")); + assert!(src.read_into_try_vec().is_err()); + } + + #[test] + fn try_read_up_to() { + let src = b"1234567890"; + let mut buf = TryVec::new(); + super::try_read_up_to(&mut src.as_ref(), 5, &mut buf).unwrap(); + assert_eq!(buf.len(), 5); + assert_eq!(buf, b"12345".as_ref()); + } + + #[test] + fn try_read_up_to_oom() { + let src = b"1234567890"; + let mut buf = TryVec::new(); + let limit = core::usize::MAX.try_into().expect("usize < u64"); + let res = super::try_read_up_to(&mut src.as_ref(), limit, &mut buf); + assert!(res.is_err()); + } + } +} + +impl<T: PartialEq> PartialEq<Vec<T>> for TryVec<T> { + #[inline(always)] + fn eq(&self, other: &Vec<T>) -> bool { + self.inner.eq(other) + } +} + +impl<'a, T: PartialEq> PartialEq<&'a [T]> for TryVec<T> { + #[inline(always)] + fn eq(&self, other: &&[T]) -> bool { + self.inner.eq(other) + } +} + +impl PartialEq<&str> for TryVec<u8> { + #[inline] + fn eq(&self, other: &&str) -> bool { + self.as_slice() == other.as_bytes() + } +} + +impl core::convert::AsRef<[u8]> for TryVec<u8> { + #[inline(always)] + fn as_ref(&self) -> &[u8] { + self.inner.as_ref() + } +} + +impl<T> core::convert::From<Vec<T>> for TryVec<T> { + #[inline(always)] + fn from(value: Vec<T>) -> Self { + Self { inner: value } + } +} + +impl<T: TryClone> core::convert::TryFrom<&[T]> for TryVec<T> { + type Error = TryReserveError; + + #[inline] + fn try_from(value: &[T]) -> Result<Self, Self::Error> { + let mut v = Self::new(); + v.inner.try_extend_from_slice_no_copy(value)?; + Ok(v) + } +} + +impl core::convert::TryFrom<&str> for TryVec<u8> { + type Error = TryReserveError; + + #[inline] + fn try_from(value: &str) -> Result<Self, Self::Error> { + let mut v = Self::new(); + v.extend_from_slice(value.as_bytes())?; + Ok(v) + } +} + +impl<T> core::ops::Deref for TryVec<T> { + type Target = [T]; + + #[inline(always)] + fn deref(&self) -> &[T] { + self.inner.deref() + } +} + +impl<T> core::ops::DerefMut for TryVec<T> { + fn deref_mut(&mut self) -> &mut [T] { + self.inner.deref_mut() + } +} + +pub struct Iter<'a, T> { + inner: alloc::slice::Iter<'a, T>, +} + +impl<'a, T> Iterator for Iter<'a, T> { + type Item = &'a T; + + #[inline(always)] + fn next(&mut self) -> Option<Self::Item> { + self.inner.next() + } + + #[inline(always)] + fn size_hint(&self) -> (usize, Option<usize>) { + self.inner.size_hint() + } +} + +pub struct IterMut<'a, T> { + inner: alloc::slice::IterMut<'a, T>, +} + +impl<'a, T> Iterator for IterMut<'a, T> { + type Item = &'a mut T; + + #[inline(always)] + fn next(&mut self) -> Option<Self::Item> { + self.inner.next() + } + + #[inline(always)] + fn size_hint(&self) -> (usize, Option<usize>) { + self.inner.size_hint() + } +} + +/// Grow capacity exponentially +#[cold] +fn vec_try_reserve_for_growth<T>(v: &mut Vec<T>, additional: usize) -> Result<(), TryReserveError> { + // saturating, because can't use CapacityOverflow here if rust_1_57 flag is enabled + FallibleVec::try_reserve(v, additional.max(v.capacity().saturating_mul(2) - v.len())) +} + +fn needs_to_grow<T>(v: &Vec<T>, len: usize) -> bool { + v.len().checked_add(len).map_or(true, |needed| needed > v.capacity()) +} + +#[cfg(not(any(feature = "unstable", feature = "rust_1_57")))] +fn vec_try_reserve<T>(v: &mut Vec<T>, additional: usize) -> Result<(), TryReserveError> { + let available = v.capacity().checked_sub(v.len()).expect("capacity >= len"); + if additional > available { + let increase = additional + .checked_sub(available) + .expect("additional > available"); + let new_cap = v + .capacity() + .checked_add(increase) + .ok_or(TryReserveError::CapacityOverflow)?; + vec_try_extend(v, new_cap)?; + debug_assert!(v.capacity() == new_cap); + } + + Ok(()) +} + +#[cfg(not(any(feature = "unstable", feature = "rust_1_57")))] +fn vec_try_extend<T>(v: &mut Vec<T>, new_cap: usize) -> Result<(), TryReserveError> { + let old_len = v.len(); + let old_cap: usize = v.capacity(); + + if old_cap >= new_cap { + return Ok(()); + } + + let elem_size = core::mem::size_of::<T>(); + let new_alloc_size = new_cap + .checked_mul(elem_size) + .filter(|size| *size <= isize::MAX as usize) + .ok_or(TryReserveError::CapacityOverflow)?; + + // required for alloc safety + // See https://doc.rust-lang.org/stable/std/alloc/trait.GlobalAlloc.html#safety-1 + // Should be unreachable given prior `old_cap >= new_cap` check. + assert!(new_alloc_size > 0); + + let align = core::mem::align_of::<T>(); + + let (new_ptr, layout) = { + if old_cap == 0 { + let layout = Layout::from_size_align(new_alloc_size, align).expect("Invalid layout"); + let new_ptr = unsafe { alloc(layout) }; + (new_ptr, layout) + } else { + let old_alloc_size = old_cap + .checked_mul(elem_size) + .ok_or(TryReserveError::CapacityOverflow)?; + let layout = Layout::from_size_align(old_alloc_size, align).expect("Invalid layout"); + let new_ptr = unsafe { realloc(v.as_mut_ptr() as *mut u8, layout, new_alloc_size) }; + (new_ptr, layout) + } + }; + + if new_ptr.is_null() { + return Err(TryReserveError::AllocError { layout }); + } + + let new_vec = unsafe { Vec::from_raw_parts(new_ptr.cast(), old_len, new_cap) }; + + core::mem::forget(core::mem::replace(v, new_vec)); + Ok(()) +} + +impl<T> FallibleVec<T> for Vec<T> { + #[inline(always)] + fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { + #[cfg(all(feature = "unstable", not(feature = "rust_1_57")))] + { + self.try_reserve(additional) + } + + #[cfg(not(feature = "rust_1_57"))] + { + vec_try_reserve(self, additional) + } + + #[cfg(feature = "rust_1_57")] + { + // TryReserveError is an opaque type in 1.57 + self.try_reserve(additional).map_err(|_| { + crate::make_try_reserve_error(self.len(), additional, core::mem::size_of::<T>(), core::mem::align_of::<T>()) + }) + } + } + + #[inline] + fn try_push(&mut self, elem: T) -> Result<(), TryReserveError> { + if self.len() == self.capacity() { + vec_try_reserve_for_growth(self, 1)?; + } + Ok(self.push(elem)) + } + + #[inline] + fn try_push_give_back(&mut self, elem: T) -> Result<(), (T, TryReserveError)> { + if self.len() == self.capacity() { + if let Err(e) = vec_try_reserve_for_growth(self, 1) { + return Err((elem, e)); + } + } + Ok(self.push(elem)) + } + + #[inline] + fn try_with_capacity(capacity: usize) -> Result<Self, TryReserveError> + where + Self: core::marker::Sized, + { + let mut n = Self::new(); + FallibleVec::try_reserve(&mut n, capacity)?; + Ok(n) + } + + #[inline] + fn try_insert(&mut self, index: usize, element: T) -> Result<(), (T, TryReserveError)> { + if self.len() == self.capacity() { + if let Err(e) = vec_try_reserve_for_growth(self, 1) { + return Err((element, e)); + } + } + Ok(self.insert(index, element)) + } + #[inline] + fn try_append(&mut self, other: &mut Self) -> Result<(), TryReserveError> { + FallibleVec::try_reserve(self, other.len())?; + Ok(self.append(other)) + } + fn try_resize(&mut self, new_len: usize, value: T) -> Result<(), TryReserveError> + where + T: Copy + Clone, + { + let len = self.len(); + if new_len > len { + FallibleVec::try_reserve(self, new_len - len)?; + } + Ok(self.resize(new_len, value)) + } + fn try_resize_with<F>(&mut self, new_len: usize, f: F) -> Result<(), TryReserveError> + where + F: FnMut() -> T, + { + let len = self.len(); + if new_len > len { + FallibleVec::try_reserve(self, new_len - len)?; + } + Ok(self.resize_with(new_len, f)) + } + fn try_resize_no_copy(&mut self, new_len: usize, value: T) -> Result<(), TryReserveError> + where + T: TryClone, + { + let len = self.len(); + + if new_len > len { + self.try_extend_with(new_len - len, TryExtendElement(value)) + } else { + Ok(self.truncate(new_len)) + } + } + #[inline] + fn try_extend_from_slice(&mut self, other: &[T]) -> Result<(), TryReserveError> + where + T: Clone, + { + if needs_to_grow(self, other.len()) { + vec_try_reserve_for_growth(self, other.len())?; + } + Ok(self.extend_from_slice(other)) + } + fn try_extend_from_slice_no_copy(&mut self, other: &[T]) -> Result<(), TryReserveError> + where + T: TryClone, + { + if needs_to_grow(self, other.len()) { + vec_try_reserve_for_growth(self, other.len())?; + } + let mut len = self.len(); + let mut iterator = other.iter(); + while let Some(element) = iterator.next() { + unsafe { + core::ptr::write(self.get_unchecked_mut(len), element.try_clone()?); + // NB can't overflow since we would have had to alloc the address space + len += 1; + self.set_len(len); + } + } + Ok(()) + } +} + +trait ExtendWith<T> { + fn next(&mut self) -> Result<T, TryReserveError>; + fn last(self) -> T; +} + +struct TryExtendElement<T: TryClone>(T); +impl<T: TryClone> ExtendWith<T> for TryExtendElement<T> { + #[inline(always)] + fn next(&mut self) -> Result<T, TryReserveError> { + self.0.try_clone() + } + #[inline(always)] + fn last(self) -> T { + self.0 + } +} + +trait TryExtend<T> { + fn try_extend_with<E: ExtendWith<T>>( + &mut self, + n: usize, + value: E, + ) -> Result<(), TryReserveError>; +} + +impl<T> TryExtend<T> for Vec<T> { + /// Extend the vector by `n` values, using the given generator. + fn try_extend_with<E: ExtendWith<T>>( + &mut self, + n: usize, + mut value: E, + ) -> Result<(), TryReserveError> { + if needs_to_grow(self, n) { + vec_try_reserve_for_growth(self, n)?; + } + + unsafe { + let mut ptr = self.as_mut_ptr().add(self.len()); + + let mut local_len = self.len(); + // Write all elements except the last one + for _ in 1..n { + core::ptr::write(ptr, value.next()?); + ptr = ptr.offset(1); + // Increment the length in every step in case next() panics + local_len += 1; + self.set_len(local_len); + } + + if n > 0 { + // We can write the last element directly without cloning needlessly + core::ptr::write(ptr, value.last()); + local_len += 1; + self.set_len(local_len); + } + + // len set by scope guard + } + Ok(()) + } +} + +trait Truncate { + fn truncate(&mut self, len: usize); +} + +impl<T> Truncate for Vec<T> { + fn truncate(&mut self, len: usize) { + let current_len = self.len(); + unsafe { + let mut ptr = self.as_mut_ptr().add(current_len); + // Set the final length at the end, keeping in mind that + // dropping an element might panic. Works around a missed + // optimization, as seen in the following issue: + // https://github.com/rust-lang/rust/issues/51802 + let mut local_len = self.len(); + + // drop any extra elements + for _ in len..current_len { + ptr = ptr.offset(-1); + core::ptr::drop_in_place(ptr); + local_len -= 1; + self.set_len(local_len); + } + } + } +} + +/// try creating a vec from an `elem` cloned `n` times, see std::from_elem +#[cfg(feature = "unstable")] +pub fn try_from_elem<T: TryClone>(elem: T, n: usize) -> Result<Vec<T>, TryReserveError> { + <T as SpecFromElem>::try_from_elem(elem, n) +} + +// Specialization trait used for Vec::from_elem +#[cfg(feature = "unstable")] +trait SpecFromElem: Sized { + fn try_from_elem(elem: Self, n: usize) -> Result<Vec<Self>, TryReserveError>; +} + +#[cfg(feature = "unstable")] +impl<T: TryClone> SpecFromElem for T { + default fn try_from_elem(elem: Self, n: usize) -> Result<Vec<T>, TryReserveError> { + let mut v = Vec::new(); + v.try_resize_no_copy(n, elem)?; + Ok(v) + } +} + +#[cfg(feature = "unstable")] +impl SpecFromElem for u8 { + #[inline] + fn try_from_elem(elem: u8, n: usize) -> Result<Vec<u8>, TryReserveError> { + unsafe { + let mut v: Vec<u8> = FallibleVec::try_with_capacity(n)?; + core::ptr::write_bytes(v.as_mut_ptr(), elem, n); + v.set_len(n); + Ok(v) + } + } +} + +impl<T: TryClone> TryClone for Vec<T> { + #[inline] + fn try_clone(&self) -> Result<Self, TryReserveError> + where + Self: core::marker::Sized, + { + let mut v = Vec::new(); + v.try_extend_from_slice_no_copy(self)?; + Ok(v) + } +} + +pub trait TryFromIterator<I>: Sized { + fn try_from_iterator<T: IntoIterator<Item = I>>(iterator: T) -> Result<Self, TryReserveError>; +} + +impl<I> TryFromIterator<I> for Vec<I> { + fn try_from_iterator<T: IntoIterator<Item = I>>(iterator: T) -> Result<Self, TryReserveError> + where + T: IntoIterator<Item = I>, + { + let mut new = Self::new(); + for i in iterator { + new.try_push(i)?; + } + Ok(new) + } +} + +pub trait TryCollect<I> { + fn try_collect<C: TryFromIterator<I>>(self) -> Result<C, TryReserveError>; +} + +impl<I, T> TryCollect<I> for T +where + T: IntoIterator<Item = I>, +{ + #[inline(always)] + fn try_collect<C: TryFromIterator<I>>(self) -> Result<C, TryReserveError> { + C::try_from_iterator(self) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + #[cfg(feature = "unstable")] + fn vec() { + // let v: Vec<u8> = from_elem(1, 10); + let v: Vec<Vec<u8>> = try_vec![try_vec![42; 10].unwrap(); 100].unwrap(); + println!("{:?}", v); + let v2 = try_vec![0, 1, 2]; + println!("{:?}", v2); + assert_eq!(2 + 2, 4); + } + + #[test] + fn try_clone_vec() { + // let v: Vec<u8> = from_elem(1, 10); + let v = vec![42; 100]; + assert_eq!(v.try_clone().unwrap(), v); + } + + #[test] + fn try_clone_oom() { + let layout = Layout::new::<u8>(); + let v = + unsafe { Vec::<u8>::from_raw_parts(alloc(layout), core::isize::MAX as usize, core::isize::MAX as usize) }; + assert!(v.try_clone().is_err()); + } + + #[test] + fn tryvec_try_clone_oom() { + let layout = Layout::new::<u8>(); + let inner = + unsafe { Vec::<u8>::from_raw_parts(alloc(layout), core::isize::MAX as usize, core::isize::MAX as usize) }; + let tv = TryVec { inner }; + assert!(tv.try_clone().is_err()); + } + + // #[test] + // fn try_out_of_mem() { + // let v = try_vec![42_u8; 1000000000]; + // assert_eq!(v.try_clone().unwrap(), v); + // } + + #[test] + fn oom() { + let mut vec: Vec<char> = Vec::new(); + match FallibleVec::try_reserve(&mut vec, core::usize::MAX / std::mem::size_of::<char>()) { + Ok(_) => panic!("it should be OOM"), + _ => (), + } + match FallibleVec::try_reserve(&mut vec, core::usize::MAX) { + Ok(_) => panic!("it should be OOM"), + _ => (), + } + } + + #[test] + fn tryvec_oom() { + let mut vec: TryVec<char> = TryVec::new(); + match vec.reserve(core::usize::MAX / std::mem::size_of::<char>()) { + Ok(_) => panic!("it should be OOM"), + _ => (), + } + match vec.reserve(core::usize::MAX) { + Ok(_) => panic!("it should be OOM"), + _ => (), + } + } + + #[test] + fn try_reserve() { + let mut vec: Vec<_> = vec![1]; + let additional_room = vec.capacity() - vec.len(); + let additional = additional_room + 1; + let old_cap = vec.capacity(); + FallibleVec::try_reserve(&mut vec, additional).unwrap(); + assert!(vec.capacity() > old_cap); + } + + #[test] + fn tryvec_reserve() { + let mut vec: TryVec<_> = vec![1].into(); + let old_cap = vec.inner.capacity(); + let new_cap = old_cap + 1; + vec.reserve(new_cap).unwrap(); + assert!(vec.inner.capacity() >= new_cap); + } + + #[test] + fn try_reserve_idempotent() { + let mut vec: Vec<_> = vec![1]; + let additional_room = vec.capacity() - vec.len(); + let additional = additional_room + 1; + FallibleVec::try_reserve(&mut vec, additional).unwrap(); + let cap_after_reserve = vec.capacity(); + FallibleVec::try_reserve(&mut vec, additional).unwrap(); + assert_eq!(vec.capacity(), cap_after_reserve); + } + + #[test] + fn tryvec_reserve_idempotent() { + let mut vec: TryVec<_> = vec![1].into(); + let old_cap = vec.inner.capacity(); + let new_cap = old_cap + 1; + vec.reserve(new_cap).unwrap(); + let cap_after_reserve = vec.inner.capacity(); + vec.reserve(new_cap).unwrap(); + assert_eq!(cap_after_reserve, vec.inner.capacity()); + } + + #[test] + fn capacity_overflow() { + let mut vec: Vec<_> = vec![1]; + match FallibleVec::try_reserve(&mut vec, core::usize::MAX) { + Ok(_) => panic!("capacity calculation should overflow"), + _ => (), + } + } + + #[test] + fn tryvec_capacity_overflow() { + let mut vec: TryVec<_> = vec![1].into(); + match vec.reserve(core::usize::MAX) { + Ok(_) => panic!("capacity calculation should overflow"), + _ => (), + } + } + + #[test] + fn extend_from_slice() { + let mut vec: Vec<u8> = b"foo".as_ref().into(); + vec.shrink_to_fit(); + vec.reserve(5); + assert_eq!(8, vec.capacity()); + vec.try_extend_from_slice(b"bar").unwrap(); + assert_eq!(vec, b"foobar".as_ref()); + vec.try_extend_from_slice(b"1").unwrap(); + assert_eq!(vec, b"foobar1".as_ref()); + assert_eq!(8, vec.capacity()); + vec.try_extend_from_slice(b"11").unwrap(); + assert_eq!(16, vec.capacity()); + } + + #[test] + fn tryvec_extend_from_slice() { + let mut vec: TryVec<u8> = b"foo".as_ref().try_into().unwrap(); + vec.extend_from_slice(b"bar").unwrap(); + assert_eq!(vec, b"foobar".as_ref()); + } + + #[test] + #[cfg(not(any(feature = "unstable", feature = "rust_1_57")))] + fn try_extend_zst() { + let mut vec: Vec<()> = Vec::new(); + assert_eq!(vec.capacity(), core::usize::MAX); + assert!(vec_try_extend(&mut vec, 10).is_ok()); + assert!(vec_try_extend(&mut vec, core::usize::MAX).is_ok()); + } + + #[test] + fn try_reserve_zst() { + let mut vec: Vec<()> = Vec::new(); + assert!(FallibleVec::try_reserve(&mut vec, core::usize::MAX).is_ok()); + } +} |