im-rc - cargo Package Compare versions

Comparing version 14.0.0 to 14.1.0

proptest-regressions/ord/set.txt

+# Seeds for failure cases proptest has generated in the past. It is
+# automatically read and these particular cases re-run before any
+# novel cases are generated.
+#
+# It is recommended to check this file in to source control so that
+# everyone who runs the test benefits from these saved cases.
+cc d2977c225bfd8d461dea19c554cae04a48f9155854b53118264fb27b2dab49cb # shrinks to max = 1

proptest-regressions/tests/ordset.txt

+# Seeds for failure cases proptest has generated in the past. It is
+# automatically read and these particular cases re-run before any
+# novel cases are generated.
+#
+# It is recommended to check this file in to source control so that
+# everyone who runs the test benefits from these saved cases.
+cc ad212dea44eb83bbfd86396a2e0f9460ecb93f6b1a2644bc700ffc317638a37a # shrinks to actions = let mut set = OrdSet::new(); set.insert(0); let expected = vec![0]; assert_eq!(OrdSet::from(expected), set); 

src/fakepool.rs

+// This Source Code Form is subject to the terms of the Mozilla Public
+// License, v. 2.0. If a copy of the MPL was not distributed with this
+// file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+#![allow(dead_code)]
+
+use std::marker::PhantomData;
+use std::ops::Deref;
+use std::rc::Rc as RRc;
+use std::sync::Arc as RArc;
+
+use crate::nodes::chunk::Chunk;
+
+pub trait PoolDefault: Default {}
+pub trait PoolClone: Clone {}
+
+impl<A> PoolDefault for Chunk<A> {}
+impl<A> PoolClone for Chunk<A> where A: Clone {}
+
+pub struct Pool<A>(PhantomData<A>);
+
+impl<A> Pool<A> {
+    pub fn new(_size: usize) -> Self {
+        Pool(PhantomData)
+    }
+
+    pub fn get_pool_size(&self) -> usize {
+        0
+    }
+
+    pub fn fill(&self) {}
+}
+
+impl<A> Clone for Pool<A> {
+    fn clone(&self) -> Self {
+        Self::new(0)
+    }
+}
+
+// Rc
+
+#[derive(Default)]
+pub struct Rc<A>(RRc<A>);
+
+impl<A> Rc<A> {
+    #[inline(always)]
+    pub fn default(_pool: &Pool<A>) -> Self
+    where
+        A: PoolDefault,
+    {
+        Self(Default::default())
+    }
+
+    #[inline(always)]
+    pub fn new(_pool: &Pool<A>, value: A) -> Self {
+        Rc(RRc::new(value))
+    }
+
+    #[inline(always)]
+    pub fn clone_from(_pool: &Pool<A>, value: &A) -> Self
+    where
+        A: PoolClone,
+    {
+        Rc(RRc::new(value.clone()))
+    }
+
+    #[inline(always)]
+    pub fn make_mut<'a>(_pool: &Pool<A>, this: &'a mut Self) -> &'a mut A
+    where
+        A: PoolClone,
+    {
+        RRc::make_mut(&mut this.0)
+    }
+
+    #[inline(always)]
+    pub fn ptr_eq(left: &Self, right: &Self) -> bool {
+        RRc::ptr_eq(&left.0, &right.0)
+    }
+
+    pub fn unwrap_or_clone(this: Self) -> A
+    where
+        A: PoolClone,
+    {
+        RRc::try_unwrap(this.0).unwrap_or_else(|r| (*r).clone())
+    }
+}
+
+impl<A> Clone for Rc<A> {
+    #[inline(always)]
+    fn clone(&self) -> Self {
+        Rc(self.0.clone())
+    }
+}
+
+impl<A> Deref for Rc<A> {
+    type Target = A;
+    #[inline(always)]
+    fn deref(&self) -> &Self::Target {
+        self.0.deref()
+    }
+}
+
+impl<A> PartialEq for Rc<A>
+where
+    A: PartialEq,
+{
+    #[inline(always)]
+    fn eq(&self, other: &Self) -> bool {
+        **self == **other
+    }
+}
+
+impl<A> Eq for Rc<A> where A: Eq {}
+
+impl<A> std::fmt::Debug for Rc<A>
+where
+    A: std::fmt::Debug,
+{
+    #[inline(always)]
+    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
+        self.0.fmt(f)
+    }
+}
+
+// Arc
+
+#[derive(Default)]
+pub struct Arc<A>(RArc<A>);
+
+impl<A> Arc<A> {
+    #[inline(always)]
+    pub fn default(_pool: &Pool<A>) -> Self
+    where
+        A: PoolDefault,
+    {
+        Self(Default::default())
+    }
+
+    #[inline(always)]
+    pub fn new(_pool: &Pool<A>, value: A) -> Self {
+        Self(RArc::new(value))
+    }
+
+    #[inline(always)]
+    pub fn clone_from(_pool: &Pool<A>, value: &A) -> Self
+    where
+        A: PoolClone,
+    {
+        Self(RArc::new(value.clone()))
+    }
+
+    #[inline(always)]
+    pub fn make_mut<'a>(_pool: &Pool<A>, this: &'a mut Self) -> &'a mut A
+    where
+        A: PoolClone,
+    {
+        RArc::make_mut(&mut this.0)
+    }
+
+    #[inline(always)]
+    pub fn ptr_eq(left: &Self, right: &Self) -> bool {
+        RArc::ptr_eq(&left.0, &right.0)
+    }
+
+    pub fn unwrap_or_clone(this: Self) -> A
+    where
+        A: PoolClone,
+    {
+        RArc::try_unwrap(this.0).unwrap_or_else(|r| (*r).clone())
+    }
+}
+
+impl<A> Clone for Arc<A> {
+    #[inline(always)]
+    fn clone(&self) -> Self {
+        Self(self.0.clone())
+    }
+}
+
+impl<A> Deref for Arc<A> {
+    type Target = A;
+    #[inline(always)]
+    fn deref(&self) -> &Self::Target {
+        self.0.deref()
+    }
+}
+
+impl<A> PartialEq for Arc<A>
+where
+    A: PartialEq,
+{
+    #[inline(always)]
+    fn eq(&self, other: &Self) -> bool {
+        **self == **other
+    }
+}
+
+impl<A> Eq for Arc<A> where A: Eq {}
+
+impl<A> std::fmt::Debug for Arc<A>
+where
+    A: std::fmt::Debug,
+{
+    #[inline(always)]
+    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
+        self.0.fmt(f)
+    }
+}

src/vector/pool.rs

+// This Source Code Form is subject to the terms of the Mozilla Public
+// License, v. 2.0. If a copy of the MPL was not distributed with this
+// file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+use crate::config::POOL_SIZE;
+use crate::nodes::chunk::Chunk;
+use crate::nodes::rrb::Node;
+use crate::util::Pool;
+
+/// A memory pool for `Vector`.
+pub struct RRBPool<A> {
+    pub(crate) node_pool: Pool<Chunk<Node<A>>>,
+    pub(crate) value_pool: Pool<Chunk<A>>,
+    pub(crate) size_pool: Pool<Chunk<usize>>,
+}
+
+impl<A> RRBPool<A> {
+    /// Create a new memory pool with the given size.
+    pub fn new(size: usize) -> Self {
+        Self::with_sizes(size, size, size)
+    }
+
+    /// Create a new memory pool with the given sizes for each subpool.
+    pub fn with_sizes(
+        node_pool_size: usize,
+        leaf_pool_size: usize,
+        size_table_pool_size: usize,
+    ) -> Self {
+        Self {
+            node_pool: Pool::new(node_pool_size),
+            value_pool: Pool::new(leaf_pool_size),
+            size_pool: Pool::new(size_table_pool_size),
+        }
+    }
+
+    /// Fill the memory pool with preallocated chunks.
+    pub fn fill(&self) {
+        self.node_pool.fill();
+        self.value_pool.fill();
+        self.size_pool.fill();
+    }
+
+    /// Get the size of the node subpool.
+    pub fn node_pool_size(&self) -> usize {
+        self.node_pool.get_pool_size()
+    }
+
+    /// Get the size of the leaf node subpool.
+    pub fn leaf_pool_size(&self) -> usize {
+        self.value_pool.get_pool_size()
+    }
+
+    /// Get the size of the size table subpool.
+    pub fn size_table_pool_size(&self) -> usize {
+        self.size_pool.get_pool_size()
+    }
+}
+
+impl<A> Default for RRBPool<A> {
+    /// Construct a pool with a reasonable default pool size.
+    fn default() -> Self {
+        Self::new(POOL_SIZE)
+    }
+}
+
+impl<A> Clone for RRBPool<A> {
+    fn clone(&self) -> Self {
+        Self {
+            node_pool: self.node_pool.clone(),
+            value_pool: self.value_pool.clone(),
+            size_pool: self.size_pool.clone(),
+        }
+    }
+}

build.rs

@@ -17,5 +17,7 @@ // This Source Code Form is subject to the terms of the Mozilla Public
     match pkgname.as_str() {
-        "im" => if !test_rc {
-            println!("cargo:rustc-cfg=threadsafe")
-        },
+        "im" => {
+            if !test_rc {
+                println!("cargo:rustc-cfg=threadsafe")
+            }
+        }
         "im-rc" => {}
@@ -22,0 +24,0 @@ _ => panic!("unexpected package name!"),

Cargo.toml

@@ -16,3 +16,3 @@ # THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
 name = "im-rc"
-version = "14.0.0"
+version = "14.1.0"
 authors = ["Bodil Stokke <[e-mail]>"]
@@ -28,2 +28,4 @@ build = "./build.rs"
 repository = "https://github.com/bodil/im-rs"
+[package.metadata.docs.rs]
+all-features = true
 
@@ -53,2 +55,6 @@ [lib]
 
+[dependencies.refpool]
+version = "0.2.2"
+optional = true
+
 [dependencies.serde]
@@ -59,3 +65,3 @@ version = "1.0"
 [dependencies.sized-chunks]
-version = "0.5.0"
+version = "0.5.1"
 
@@ -62,0 +68,0 @@ [dependencies.typenum]

CHANGELOG.md

@@ -9,2 +9,16 @@ # Changelog
 
+## [14.1.0] - 2019-12-16
+
+### Added
+
+- If you enable the `pool` feature flag, im now supports constructing data types
+  using [`refpool`](https://crates.io/crates/refpool) to speed up chunk
+  allocation. The performance boost will vary between use cases and operating
+  systems, but generally at least a 10% speedup can be expected when
+  constructing a data type from an iterator, and the more complex an operation
+  is, the more likely it is to benefit from being able to quickly reallocate
+  chunks. Note that in order to use this feature, you have to construct your
+  data types using the `with_pool(&pool)` constructor, it's not enough just to
+  enable the feature flag.
+
 ## [14.0.0] - 2019-11-19
@@ -11,0 +25,0 @@

src/config.rs

@@ -16,1 +16,6 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 pub type HashLevelSize = U5;
+
+/// The size of per-instance memory pools if the `pool` feature is enabled.
+/// This is set to 0, meaning you have to opt in to using a pool by constructing
+/// with eg. `Vector::with_pool(pool)` even if the `pool` feature is enabled.
+pub const POOL_SIZE: usize = 0;

src/hash/set.rs

@@ -38,3 +38,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 use crate::ordset::OrdSet;
-use crate::util::Ref;
+use crate::util::{Pool, PoolRef, Ref};
 
@@ -76,2 +76,4 @@ /// Construct a set from a sequence of values.
 
+def_pool!(HashSetPool<A>, Node<Value<A>>);
+
 /// An unordered set.
@@ -97,3 +99,4 @@ ///
     hasher: Ref<S>,
-    root: Ref<Node<Value<A>>>,
+    pool: HashSetPool<A>,
+    root: PoolRef<Node<Value<A>>>,
     size: usize,
@@ -135,2 +138,14 @@ }
     }
+
+    /// Construct an empty set using a specific memory pool.
+    #[cfg(feature = "pool")]
+    #[must_use]
+    pub fn with_pool(pool: &HashSetPool<A>) -> Self {
+        Self {
+            pool: pool.clone(),
+            hasher: Default::default(),
+            size: 0,
+            root: PoolRef::default(&pool.0),
+        }
+    }
 }
@@ -150,6 +165,4 @@
     /// # use std::sync::Arc;
-    /// # fn main() {
     /// let set = HashSet::unit(123);
     /// assert!(set.contains(&123));
-    /// # }
     /// ```
@@ -173,3 +186,2 @@ #[inline]
     /// # use im::hashset::HashSet;
-    /// # fn main() {
     /// assert!(
@@ -181,3 +193,2 @@ ///   !hashset![1, 2, 3].is_empty()
     /// );
-    /// # }
     /// ```
@@ -199,5 +210,3 @@ #[inline]
     /// # use im::hashset::HashSet;
-    /// # fn main() {
     /// assert_eq!(3, hashset![1, 2, 3].len());
-    /// # }
     /// ```
@@ -210,2 +219,11 @@ #[inline]
 
+    /// Get a reference to the memory pool used by this set.
+    ///
+    /// Note that if you didn't specifically construct it with a pool, you'll
+    /// get back a reference to a pool of size 0.
+    #[cfg(feature = "pool")]
+    pub fn pool(&self) -> &HashSetPool<A> {
+        &self.pool
+    }
+
     /// Construct an empty hash set using the provided hasher.
@@ -218,5 +236,8 @@ #[inline]
     {
+        let pool = HashSetPool::default();
+        let root = PoolRef::default(&pool.0);
         HashSet {
             size: 0,
-            root: Ref::new(Node::new()),
+            pool,
+            root,
             hasher: From::from(hasher),
@@ -226,2 +247,19 @@ }
 
+    /// Construct an empty hash set using the provided memory pool and hasher.
+    #[cfg(feature = "pool")]
+    #[inline]
+    #[must_use]
+    pub fn with_pool_hasher<RS>(pool: &HashSetPool<A>, hasher: RS) -> Self
+    where
+        Ref<S>: From<RS>,
+    {
+        let root = PoolRef::default(&pool.0);
+        HashSet {
+            size: 0,
+            pool: pool.clone(),
+            root,
+            hasher: From::from(hasher),
+        }
+    }
+
     /// Get a reference to the set's [`BuildHasher`][BuildHasher].
@@ -242,5 +280,8 @@ ///
     {
+        let pool = HashSetPool::default();
+        let root = PoolRef::default(&pool.0);
         HashSet {
             size: 0,
-            root: Ref::new(Node::new()),
+            pool,
+            root,
             hasher: self.hasher.clone(),
@@ -262,11 +303,9 @@ }
     /// # use im::HashSet;
-    /// # fn main() {
     /// let mut set = hashset![1, 2, 3];
     /// set.clear();
     /// assert!(set.is_empty());
-    /// # }
     /// ```
     pub fn clear(&mut self) {
         if !self.is_empty() {
-            self.root = Default::default();
+            self.root = PoolRef::default(&self.pool.0);
             self.size = 0;
@@ -367,5 +406,5 @@ }
     pub fn iter_mut(&mut self) -> IterMut<'_, A> {
-        let root = Ref::make_mut(&mut self.root);
+        let root = PoolRef::make_mut(&self.pool.0, &mut self.root);
         IterMut {
-            it: NodeIterMut::new(root, self.size),
+            it: NodeIterMut::new(&self.pool.0, root, self.size),
         }
@@ -380,4 +419,4 @@ }
         let hash = hash_key(&*self.hasher, &a);
-        let root = Ref::make_mut(&mut self.root);
-        match root.insert(hash, 0, Value(a)) {
+        let root = PoolRef::make_mut(&self.pool.0, &mut self.root);
+        match root.insert(&self.pool.0, hash, 0, Value(a)) {
             None => {
@@ -399,4 +438,4 @@ self.size += 1;
     {
-        let root = Ref::make_mut(&mut self.root);
-        let result = root.remove(hash_key(&*self.hasher, a), 0, a);
+        let root = PoolRef::make_mut(&self.pool.0, &mut self.root);
+        let result = root.remove(&self.pool.0, hash_key(&*self.hasher, a), 0, a);
         if result.is_some() {
@@ -419,3 +458,2 @@ self.size -= 1;
     /// # use std::sync::Arc;
-    /// # fn main() {
     /// let set = hashset![123];
@@ -426,3 +464,2 @@ /// assert_eq!(
     /// );
-    /// # }
     /// ```
@@ -464,5 +501,5 @@ #[must_use]
         let old_root = self.root.clone();
-        let root = Ref::make_mut(&mut self.root);
+        let root = PoolRef::make_mut(&self.pool.0, &mut self.root);
         for (value, hash) in NodeIter::new(&old_root, self.size) {
-            if !f(value) && root.remove(hash, 0, value).is_some() {
+            if !f(value) && root.remove(&self.pool.0, hash, 0, value).is_some() {
                 self.size -= 1;
@@ -482,3 +519,2 @@ }
     /// # use im::hashset::HashSet;
-    /// # fn main() {
     /// let set1 = hashset!{1, 2};
@@ -488,3 +524,2 @@ /// let set2 = hashset!{2, 3};
     /// assert_eq!(expected, set1.union(set2));
-    /// # }
     /// ```
@@ -523,3 +558,2 @@ #[must_use]
     /// # use im::hashset::HashSet;
-    /// # fn main() {
     /// let set1 = hashset!{1, 2};
@@ -529,3 +563,2 @@ /// let set2 = hashset!{2, 3};
     /// assert_eq!(expected, set1.difference(set2));
-    /// # }
     /// ```
@@ -548,3 +581,2 @@ ///
     /// # use im::hashset::HashSet;
-    /// # fn main() {
     /// let set1 = hashset!{1, 2};
@@ -554,3 +586,2 @@ /// let set2 = hashset!{2, 3};
     /// assert_eq!(expected, set1.symmetric_difference(set2));
-    /// # }
     /// ```
@@ -577,3 +608,2 @@ #[must_use]
     /// # use im::ordset::OrdSet;
-    /// # fn main() {
     /// let set1 = ordset!{1, 2};
@@ -583,3 +613,2 @@ /// let set2 = ordset!{2, 3};
     /// assert_eq!(expected, set1.relative_complement(set2));
-    /// # }
     /// ```
@@ -603,3 +632,2 @@ #[must_use]
     /// # use im::hashset::HashSet;
-    /// # fn main() {
     /// let set1 = hashset!{1, 2};
@@ -609,3 +637,2 @@ /// let set2 = hashset!{2, 3};
     /// assert_eq!(expected, set1.intersection(set2));
-    /// # }
     /// ```
@@ -633,2 +660,3 @@ #[must_use]
             hasher: self.hasher.clone(),
+            pool: self.pool.clone(),
             root: self.root.clone(),
@@ -707,5 +735,8 @@ size: self.size,
     fn default() -> Self {
+        let pool = HashSetPool::default();
+        let root = PoolRef::default(&pool.0);
         HashSet {
             hasher: Ref::<S>::default(),
-            root: Ref::new(Node::new()),
+            pool,
+            root,
             size: 0,
@@ -950,3 +981,3 @@ }
         ConsumingIter {
-            it: NodeDrain::new(self.root, self.size),
+            it: NodeDrain::new(&self.pool.0, self.root, self.size),
         }
@@ -1070,2 +1101,3 @@ }
 pub mod proptest {
+    //! Proptest strategies.
     use super::*;
@@ -1072,0 +1104,0 @@ use ::proptest::strategy::{BoxedStrategy, Strategy, ValueTree};

src/iter.rs

@@ -21,3 +21,2 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 /// # use std::iter::FromIterator;
-/// # fn main() {
 /// // Create an infinite stream of numbers, starting at 0.
@@ -29,3 +28,2 @@ /// let mut it = unfold(0, |i| Some((i, i + 1)));
 /// assert_eq!(numbers, vector![0, 1, 2, 3, 4]);
-/// # }
 /// ```
@@ -35,3 +33,2 @@ ///
 /// [std::option::Option::None]: https://doc.rust-lang.org/std/option/enum.Option.html#variant.None
-#[must_use]
 pub fn unfold<F, S, A>(value: S, f: F) -> impl Iterator<Item = A>
@@ -38,0 +35,0 @@ where

src/lib.rs

@@ -50,3 +50,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 //! even have to think about what data structure to use in any given
-//! situation, until the point where you need to start worring about
+//! situation, until the point where you need to start worrying about
 //! optimisation - which, in practice, often never comes. Beyond the
@@ -307,6 +307,7 @@ //! shape of your data (ie. whether to use a list or a map), it should
 //! | ------- | ----------- |
+//! | [`pool`](https://crates.io/crates/refpool) | Constructors and pool types for [`refpool`](https://crates.io/crates/refpool) memory pools (recommended only for `im-rc`) |
 //! | [`proptest`](https://crates.io/crates/proptest) | Strategies for all `im` datatypes under a `proptest` namespace, eg. `im::vector::proptest::vector()` |
-//! | [`quickcheck`](https://crates.io/crates/quickcheck) | `Arbitrary` implementations for all `im` datatypes (not available in `im-rc`) |
-//! | [`rayon`](https://crates.io/crates/rayon) | parallel iterator implementations for `Vector` (not available in `im-rc`) |
-//! | [`serde`](https://crates.io/crates/serde) | `Serialize` and `Deserialize` implementations for all `im` datatypes |
+//! | [`quickcheck`](https://crates.io/crates/quickcheck) | [`Arbitrary`](https://docs.rs/quickcheck/latest/quickcheck/trait.Arbitrary.html) implementations for all `im` datatypes (not available in `im-rc`) |
+//! | [`rayon`](https://crates.io/crates/rayon) | parallel iterator implementations for [`Vector`][vector::Vector] (not available in `im-rc`) |
+//! | [`serde`](https://crates.io/crates/serde) | [`Serialize`](https://docs.rs/serde/latest/serde/trait.Serialize.html) and [`Deserialize`](https://docs.rs/serde/latest/serde/trait.Deserialize.html) implementations for all `im` datatypes |
 //!
@@ -349,2 +350,4 @@ //! [std::collections]: https://doc.rust-lang.org/std/collections/index.html
 mod sync;
+
+#[macro_use]
 mod util;
@@ -368,4 +371,8 @@
 #[cfg(any(test, feature = "serde"))]
+#[doc(hidden)]
 pub mod ser;
 
+#[cfg(not(feature = "pool"))]
+mod fakepool;
+
 pub use crate::hashmap::HashMap;
@@ -372,0 +379,0 @@ pub use crate::hashset::HashSet;

src/nodes/btree.rs

@@ -14,3 +14,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 use crate::config::OrdChunkSize as NodeSize;
-use crate::util::{clone_ref, Ref};
+use crate::util::{Pool, PoolClone, PoolDefault, PoolRef};
 
@@ -43,5 +43,36 @@ use self::Insert::*;
     keys: Chunk<A, NodeSize>,
-    children: Chunk<Option<Ref<Node<A>>>, Add1<NodeSize>>,
+    children: Chunk<Option<PoolRef<Node<A>>>, Add1<NodeSize>>,
 }
 
+#[cfg(feature = "pool")]
+#[allow(unsafe_code)]
+unsafe fn cast_uninit<A>(target: &mut A) -> &mut mem::MaybeUninit<A> {
+    &mut *(target as *mut A as *mut mem::MaybeUninit<A>)
+}
+
+#[allow(unsafe_code)]
+impl<A> PoolDefault for Node<A> {
+    #[cfg(feature = "pool")]
+    unsafe fn default_uninit(target: &mut mem::MaybeUninit<Self>) {
+        let ptr: *mut Self = target.as_mut_ptr();
+        Chunk::default_uninit(cast_uninit(&mut (*ptr).keys));
+        Chunk::default_uninit(cast_uninit(&mut (*ptr).children));
+        (*ptr).children.push_back(None);
+    }
+}
+
+#[allow(unsafe_code)]
+impl<A> PoolClone for Node<A>
+where
+    A: Clone,
+{
+    #[cfg(feature = "pool")]
+    unsafe fn clone_uninit(&self, target: &mut mem::MaybeUninit<Self>) {
+        self.keys
+            .clone_uninit(cast_uninit(&mut (*target.as_mut_ptr()).keys));
+        self.children
+            .clone_uninit(cast_uninit(&mut (*target.as_mut_ptr()).children));
+    }
+}
+
 pub enum Insert<A> {
@@ -128,6 +159,9 @@ Added,
     #[inline]
-    pub fn new_from_split(left: Node<A>, median: A, right: Node<A>) -> Self {
+    pub fn new_from_split(pool: &Pool<Node<A>>, left: Node<A>, median: A, right: Node<A>) -> Self {
         Node {
             keys: Chunk::unit(median),
-            children: Chunk::pair(Some(Ref::from(left)), Some(Ref::from(right))),
+            children: Chunk::pair(
+                Some(PoolRef::new(pool, left)),
+                Some(PoolRef::new(pool, right)),
+            ),
         }
@@ -184,3 +218,3 @@ }
 
-    pub fn lookup_mut<BK>(&mut self, key: &BK) -> Option<&mut A>
+    pub fn lookup_mut<BK>(&mut self, pool: &Pool<Node<A>>, key: &BK) -> Option<&mut A>
     where
@@ -202,4 +236,4 @@ A: Clone,
                 Some(ref mut child_ref) => {
-                    let child = Ref::make_mut(child_ref);
-                    child.lookup_mut(key)
+                    let child = PoolRef::make_mut(pool, child_ref);
+                    child.lookup_mut(pool, key)
                 }
@@ -330,2 +364,3 @@ },
         &mut self,
+        pool: &Pool<Node<A>>,
         value: A,
@@ -335,4 +370,4 @@ ins_left: Option<Node<A>>,
     ) -> Insert<A> {
-        let left_child = ins_left.map(Ref::from);
-        let right_child = ins_right.map(Ref::from);
+        let left_child = ins_left.map(|node| PoolRef::new(pool, node));
+        let right_child = ins_right.map(|node| PoolRef::new(pool, node));
         let index = A::search_value(&self.keys, &value).unwrap_err();
@@ -344,42 +379,46 @@ let mut left_keys;
         let median;
-        if index < MEDIAN {
-            self.children[index] = left_child;
+        match index.cmp(&MEDIAN) {
+            Ordering::Less => {
+                self.children[index] = left_child;
 
-            left_keys = Chunk::from_front(&mut self.keys, index);
-            left_keys.push_back(value);
-            left_keys.drain_from_front(&mut self.keys, MEDIAN - index - 1);
+                left_keys = Chunk::from_front(&mut self.keys, index);
+                left_keys.push_back(value);
+                left_keys.drain_from_front(&mut self.keys, MEDIAN - index - 1);
 
-            left_children = Chunk::from_front(&mut self.children, index + 1);
-            left_children.push_back(right_child);
-            left_children.drain_from_front(&mut self.children, MEDIAN - index - 1);
+                left_children = Chunk::from_front(&mut self.children, index + 1);
+                left_children.push_back(right_child);
+                left_children.drain_from_front(&mut self.children, MEDIAN - index - 1);
 
-            median = self.keys.pop_front();
+                median = self.keys.pop_front();
 
-            right_keys = Chunk::drain_from(&mut self.keys);
-            right_children = Chunk::drain_from(&mut self.children);
-        } else if index > MEDIAN {
-            self.children[index] = left_child;
+                right_keys = Chunk::drain_from(&mut self.keys);
+                right_children = Chunk::drain_from(&mut self.children);
+            }
+            Ordering::Greater => {
+                self.children[index] = left_child;
 
-            left_keys = Chunk::from_front(&mut self.keys, MEDIAN);
-            left_children = Chunk::from_front(&mut self.children, MEDIAN + 1);
+                left_keys = Chunk::from_front(&mut self.keys, MEDIAN);
+                left_children = Chunk::from_front(&mut self.children, MEDIAN + 1);
 
-            median = self.keys.pop_front();
+                median = self.keys.pop_front();
 
-            right_keys = Chunk::from_front(&mut self.keys, index - MEDIAN - 1);
-            right_keys.push_back(value);
-            right_keys.append(&mut self.keys);
+                right_keys = Chunk::from_front(&mut self.keys, index - MEDIAN - 1);
+                right_keys.push_back(value);
+                right_keys.append(&mut self.keys);
 
-            right_children = Chunk::from_front(&mut self.children, index - MEDIAN);
-            right_children.push_back(right_child);
-            right_children.append(&mut self.children);
-        } else {
-            left_keys = Chunk::from_front(&mut self.keys, MEDIAN);
-            left_children = Chunk::from_front(&mut self.children, MEDIAN);
-            left_children.push_back(left_child);
+                right_children = Chunk::from_front(&mut self.children, index - MEDIAN);
+                right_children.push_back(right_child);
+                right_children.append(&mut self.children);
+            }
+            Ordering::Equal => {
+                left_keys = Chunk::from_front(&mut self.keys, MEDIAN);
+                left_children = Chunk::from_front(&mut self.children, MEDIAN);
+                left_children.push_back(left_child);
 
-            median = value;
+                median = value;
 
-            right_keys = Chunk::drain_from(&mut self.keys);
-            right_children = Chunk::drain_from(&mut self.children);
-            right_children[0] = right_child;
+                right_keys = Chunk::drain_from(&mut self.keys);
+                right_children = Chunk::drain_from(&mut self.children);
+                right_children[0] = right_child;
+            }
         }
@@ -414,3 +453,3 @@
 
-    fn pop_min(&mut self) -> (A, Option<Ref<Node<A>>>) {
+    fn pop_min(&mut self) -> (A, Option<PoolRef<Node<A>>>) {
         let value = self.keys.pop_front();
@@ -421,3 +460,3 @@ let child = self.children.pop_front();
 
-    fn pop_max(&mut self) -> (A, Option<Ref<Node<A>>>) {
+    fn pop_max(&mut self) -> (A, Option<PoolRef<Node<A>>>) {
         let value = self.keys.pop_back();
@@ -428,3 +467,3 @@ let child = self.children.pop_back();
 
-    fn push_min(&mut self, child: Option<Ref<Node<A>>>, value: A) {
+    fn push_min(&mut self, child: Option<PoolRef<Node<A>>>, value: A) {
         self.keys.push_front(value);
@@ -434,3 +473,3 @@ self.children.push_front(child);
 
-    fn push_max(&mut self, child: Option<Ref<Node<A>>>, value: A) {
+    fn push_max(&mut self, child: Option<PoolRef<Node<A>>>, value: A) {
         self.keys.push_back(value);
@@ -440,3 +479,3 @@ self.children.push_back(child);
 
-    pub fn insert(&mut self, value: A) -> Insert<A>
+    pub fn insert(&mut self, pool: &Pool<Node<A>>, value: A) -> Insert<A>
     where
@@ -463,4 +502,4 @@ A: Clone,
                     Some(ref mut child_ref) => {
-                        let child = Ref::make_mut(child_ref);
-                        match child.insert(value.clone()) {
+                        let child = PoolRef::make_mut(pool, child_ref);
+                        match child.insert(pool, value.clone()) {
                             Insert::Added => AddedAction,
@@ -489,5 +528,6 @@ Insert::Replaced(value) => ReplacedAction(value),
                         if has_room {
-                            self.children[index] = Some(Ref::from(left));
+                            self.children[index] = Some(PoolRef::new(pool, left));
                             self.keys.insert(index, median);
-                            self.children.insert(index + 1, Some(Ref::from(right)));
+                            self.children
+                                .insert(index + 1, Some(PoolRef::new(pool, right)));
                             return Insert::Added;
@@ -501,6 +541,6 @@ } else {
         };
-        self.split(median, left, right)
+        self.split(pool, median, left, right)
     }
 
-    pub fn remove<BK>(&mut self, key: &BK) -> Remove<A>
+    pub fn remove<BK>(&mut self, pool: &Pool<Node<A>>, key: &BK) -> Remove<A>
     where
@@ -512,6 +552,11 @@ A: Clone,
         let index = A::search_key(&self.keys, key);
-        self.remove_index(index, key)
+        self.remove_index(pool, index, key)
     }
 
-    fn remove_index<BK>(&mut self, index: Result<usize, usize>, key: &BK) -> Remove<A>
+    fn remove_index<BK>(
+        &mut self,
+        pool: &Pool<Node<A>>,
+        index: Result<usize, usize>,
+        key: &BK,
+    ) -> Remove<A>
     where
@@ -594,4 +639,4 @@ A: Clone,
                 if let Some(&mut Some(ref mut child_ref)) = children.get_mut(child_index) {
-                    let child = Ref::make_mut(child_ref);
-                    match child.remove_index(Ok(target_index), key) {
+                    let child = PoolRef::make_mut(pool, child_ref);
+                    match child.remove_index(pool, Ok(target_index), key) {
                         Remove::NoChange => unreachable!(),
@@ -610,3 +655,3 @@ Remove::Removed(pulled_value) => {
                 if let Some(new_child) = update {
-                    children[child_index] = Some(Ref::from(new_child));
+                    children[child_index] = Some(PoolRef::new(pool, new_child));
                 }
@@ -619,4 +664,8 @@ Remove::Removed(value)
                 let value = self.keys.remove(index);
-                let mut merged_child = Node::merge(value, clone_ref(left), clone_ref(right));
-                let (removed, new_child) = match merged_child.remove(key) {
+                let mut merged_child = Node::merge(
+                    value,
+                    PoolRef::unwrap_or_clone(left),
+                    PoolRef::unwrap_or_clone(right),
+                );
+                let (removed, new_child) = match merged_child.remove(pool, key) {
                     Remove::NoChange => unreachable!(),
@@ -630,3 +679,3 @@ Remove::Removed(removed) => (removed, merged_child),
                 } else {
-                    self.children[index] = Some(Ref::from(new_child));
+                    self.children[index] = Some(PoolRef::new(pool, new_child));
                     Remove::Removed(removed)
@@ -648,4 +697,4 @@ }
                         });
-                    let left = Ref::make_mut(children.next().unwrap());
-                    let child = Ref::make_mut(children.next().unwrap());
+                    let left = PoolRef::make_mut(pool, children.next().unwrap());
+                    let child = PoolRef::make_mut(pool, children.next().unwrap());
                     // Prepare the rebalanced node.
@@ -656,3 +705,3 @@ child.push_min(
                     );
-                    match child.remove(key) {
+                    match child.remove(pool, key) {
                         Remove::NoChange => {
@@ -679,3 +728,3 @@ // Key wasn't there, we need to revert the steal.
                 if let Some(new_child) = update {
-                    self.children[index] = Some(Ref::from(new_child));
+                    self.children[index] = Some(PoolRef::new(pool, new_child));
                 }
@@ -697,7 +746,7 @@ Remove::Removed(out_value)
                         });
-                    let child = Ref::make_mut(children.next().unwrap());
-                    let right = Ref::make_mut(children.next().unwrap());
+                    let child = PoolRef::make_mut(pool, children.next().unwrap());
+                    let right = PoolRef::make_mut(pool, children.next().unwrap());
                     // Prepare the rebalanced node.
                     child.push_max(right.children[0].clone(), self.keys[index].clone());
-                    match child.remove(key) {
+                    match child.remove(pool, key) {
                         Remove::NoChange => {
@@ -724,3 +773,3 @@ // Key wasn't there, we need to revert the steal.
                 if let Some(new_child) = update {
-                    self.children[index] = Some(Ref::from(new_child));
+                    self.children[index] = Some(PoolRef::new(pool, new_child));
                 }
@@ -739,6 +788,10 @@ Remove::Removed(out_value)
                 let middle = self.keys.remove(index);
-                let mut merged = Node::merge(middle, clone_ref(left), clone_ref(right));
+                let mut merged = Node::merge(
+                    middle,
+                    PoolRef::unwrap_or_clone(left),
+                    PoolRef::unwrap_or_clone(right),
+                );
                 let update;
                 let out_value;
-                match merged.remove(key) {
+                match merged.remove(pool, key) {
                     Remove::NoChange => {
@@ -762,3 +815,3 @@ panic!("nodes::btree::Node::remove: caught an absent key too late while merging");
                 }
-                self.children[index] = Some(Ref::from(update));
+                self.children[index] = Some(PoolRef::new(pool, update));
                 Remove::Removed(out_value)
@@ -770,4 +823,4 @@ }
                 if let Some(&mut Some(ref mut child_ref)) = self.children.get_mut(index) {
-                    let child = Ref::make_mut(child_ref);
-                    match child.remove(key) {
+                    let child = PoolRef::make_mut(pool, child_ref);
+                    match child.remove(pool, key) {
                         Remove::NoChange => return Remove::NoChange,
@@ -786,3 +839,3 @@ Remove::Removed(value) => {
                 if let Some(new_child) = update {
-                    self.children[index] = Some(Ref::from(new_child));
+                    self.children[index] = Some(PoolRef::new(pool, new_child));
                 }
@@ -1003,5 +1056,5 @@ Remove::Removed(out_value)
 
-    fn push_node(stack: &mut Vec<ConsumingIterItem<A>>, maybe_node: Option<Ref<Node<A>>>) {
+    fn push_node(stack: &mut Vec<ConsumingIterItem<A>>, maybe_node: Option<PoolRef<Node<A>>>) {
         if let Some(node) = maybe_node {
-            stack.push(ConsumingIterItem::Consider(clone_ref(node)))
+            stack.push(ConsumingIterItem::Consider(PoolRef::unwrap_or_clone(node)))
         }
@@ -1022,6 +1075,6 @@ }
 
-    fn push_node_back(&mut self, maybe_node: Option<Ref<Node<A>>>) {
+    fn push_node_back(&mut self, maybe_node: Option<PoolRef<Node<A>>>) {
         if let Some(node) = maybe_node {
             self.back_stack
-                .push(ConsumingIterItem::Consider(clone_ref(node)))
+                .push(ConsumingIterItem::Consider(PoolRef::unwrap_or_clone(node)))
         }
@@ -1143,3 +1196,3 @@ }
 
-    fn push_node(stack: &mut Vec<IterItem<'a, A>>, maybe_node: &'a Option<Ref<Node<A>>>) {
+    fn push_node(stack: &mut Vec<IterItem<'a, A>>, maybe_node: &'a Option<PoolRef<Node<A>>>) {
         if let Some(ref node) = *maybe_node {
@@ -1146,0 +1199,0 @@ stack.push(IterItem::Consider(&node))

src/nodes/hamt.rs

@@ -17,3 +17,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 use crate::config::HashLevelSize;
-use crate::util::{clone_ref, Ref};
+use crate::util::{clone_ref, Pool, PoolClone, PoolDefault, PoolRef, Ref};
 
@@ -49,2 +49,33 @@ pub type HashWidth = <U2 as Pow<HashLevelSize>>::Output;
 
+#[allow(unsafe_code)]
+impl<A> PoolDefault for Node<A> {
+    #[cfg(feature = "pool")]
+    unsafe fn default_uninit(target: &mut mem::MaybeUninit<Self>) {
+        SparseChunk::default_uninit(
+            target
+                .as_mut_ptr()
+                .cast::<mem::MaybeUninit<SparseChunk<Entry<A>, HashWidth>>>()
+                .as_mut()
+                .unwrap(),
+        )
+    }
+}
+
+#[allow(unsafe_code)]
+impl<A> PoolClone for Node<A>
+where
+    A: Clone,
+{
+    #[cfg(feature = "pool")]
+    unsafe fn clone_uninit(&self, target: &mut mem::MaybeUninit<Self>) {
+        self.data.clone_uninit(
+            target
+                .as_mut_ptr()
+                .cast::<mem::MaybeUninit<SparseChunk<Entry<A>, HashWidth>>>()
+                .as_mut()
+                .unwrap(),
+        )
+    }
+}
+
 #[derive(Clone)]
@@ -59,3 +90,3 @@ pub struct CollisionNode<A> {
     Collision(Ref<CollisionNode<A>>),
-    Node(Ref<Node<A>>),
+    Node(PoolRef<Node<A>>),
 }
@@ -87,7 +118,5 @@
     }
-}
 
-impl<A> From<Node<A>> for Entry<A> {
-    fn from(node: Node<A>) -> Self {
-        Entry::Node(Ref::new(node))
+    fn from_node(pool: &Pool<Node<A>>, node: Node<A>) -> Self {
+        Entry::Node(PoolRef::new(pool, node))
     }
@@ -136,5 +165,5 @@ }
     #[inline]
-    pub fn single_child(index: usize, node: Self) -> Self {
+    pub fn single_child(pool: &Pool<Node<A>>, index: usize, node: Self) -> Self {
         Node {
-            data: SparseChunk::unit(index, Entry::from(node)),
+            data: SparseChunk::unit(index, Entry::from_node(pool, node)),
         }
@@ -149,3 +178,10 @@ }
 impl<A: HashValue> Node<A> {
-    fn merge_values(value1: A, hash1: HashBits, value2: A, hash2: HashBits, shift: usize) -> Self {
+    fn merge_values(
+        pool: &Pool<Node<A>>,
+        value1: A,
+        hash1: HashBits,
+        value2: A,
+        hash2: HashBits,
+        shift: usize,
+    ) -> Self {
         let index1 = mask(hash1, shift) as usize;
@@ -169,4 +205,4 @@ let index2 = mask(hash2, shift) as usize;
             // Pass the values down a level.
-            let node = Node::merge_values(value1, hash1, value2, hash2, shift + HASH_SHIFT);
-            Node::single_child(index1, node)
+            let node = Node::merge_values(pool, value1, hash1, value2, hash2, shift + HASH_SHIFT);
+            Node::single_child(pool, index1, node)
         }
@@ -198,3 +234,9 @@ }
 
-    pub fn get_mut<BK>(&mut self, hash: HashBits, shift: usize, key: &BK) -> Option<&mut A>
+    pub fn get_mut<BK>(
+        &mut self,
+        pool: &Pool<Node<A>>,
+        hash: HashBits,
+        shift: usize,
+        key: &BK,
+    ) -> Option<&mut A>
     where
@@ -220,4 +262,4 @@ A: Clone,
                 Entry::Node(ref mut child_ref) => {
-                    let child = Ref::make_mut(child_ref);
-                    child.get_mut(hash, shift + HASH_SHIFT, key)
+                    let child = PoolRef::make_mut(pool, child_ref);
+                    child.get_mut(pool, hash, shift + HASH_SHIFT, key)
                 }
@@ -230,3 +272,9 @@ }
 
-    pub fn insert(&mut self, hash: HashBits, shift: usize, value: A) -> Option<A>
+    pub fn insert(
+        &mut self,
+        pool: &Pool<Node<A>>,
+        hash: HashBits,
+        shift: usize,
+        value: A,
+    ) -> Option<A>
     where
@@ -257,4 +305,4 @@ A: Clone,
                     // Child node
-                    let child = Ref::make_mut(child_ref);
-                    return child.insert(hash, shift + HASH_SHIFT, value);
+                    let child = PoolRef::make_mut(pool, child_ref);
+                    return child.insert(pool, hash, shift + HASH_SHIFT, value);
                 }
@@ -276,7 +324,13 @@ }
                 } else if let Entry::Value(old_value, old_hash) = old_entry {
-                    let node =
-                        Node::merge_values(old_value, old_hash, value, hash, shift + HASH_SHIFT);
+                    let node = Node::merge_values(
+                        pool,
+                        old_value,
+                        old_hash,
+                        value,
+                        hash,
+                        shift + HASH_SHIFT,
+                    );
                     #[allow(unsafe_code)]
                     unsafe {
-                        ptr::write(entry, Entry::from(node))
+                        ptr::write(entry, Entry::from_node(pool, node))
                     };
@@ -297,3 +351,9 @@ } else {
 
-    pub fn remove<BK>(&mut self, hash: HashBits, shift: usize, key: &BK) -> Option<A>
+    pub fn remove<BK>(
+        &mut self,
+        pool: &Pool<Node<A>>,
+        hash: HashBits,
+        shift: usize,
+        key: &BK,
+    ) -> Option<A>
     where
@@ -325,4 +385,4 @@ A: Clone,
                 Entry::Node(ref mut child_ref) => {
-                    let child = Ref::make_mut(child_ref);
-                    match child.remove(hash, shift + HASH_SHIFT, key) {
+                    let child = PoolRef::make_mut(pool, child_ref);
+                    match child.remove(pool, hash, shift + HASH_SHIFT, key) {
                         None => {
@@ -516,2 +576,3 @@ return None;
     count: usize,
+    pool: Pool<Node<A>>,
     stack: Vec<ChunkIterMut<'a, Entry<A>, HashWidth>>,
@@ -526,5 +587,6 @@ current: ChunkIterMut<'a, Entry<A>, HashWidth>,
 {
-    pub fn new(root: &'a mut Node<A>, size: usize) -> Self {
+    pub fn new(pool: &Pool<Node<A>>, root: &'a mut Node<A>, size: usize) -> Self {
         IterMut {
             count: size,
+            pool: pool.clone(),
             stack: Vec::with_capacity((HASH_WIDTH / HASH_SHIFT) + 1),
@@ -566,3 +628,3 @@ current: root.data.iter_mut(),
             Some(Entry::Node(child_ref)) => {
-                let child = Ref::make_mut(child_ref);
+                let child = PoolRef::make_mut(&self.pool, child_ref);
                 let current = mem::replace(&mut self.current, child.data.iter_mut());
@@ -603,4 +665,5 @@ self.stack.push(current);
     count: usize,
-    stack: Vec<Ref<Node<A>>>,
-    current: Ref<Node<A>>,
+    pool: Pool<Node<A>>,
+    stack: Vec<PoolRef<Node<A>>>,
+    current: PoolRef<Node<A>>,
     collision: Option<CollisionNode<A>>,
@@ -613,5 +676,6 @@ }
 {
-    pub fn new(root: Ref<Node<A>>, size: usize) -> Self {
+    pub fn new(pool: &Pool<Node<A>>, root: PoolRef<Node<A>>, size: usize) -> Self {
         Drain {
             count: size,
+            pool: pool.clone(),
             stack: vec![],
@@ -644,3 +708,3 @@ current: root,
         }
-        match Ref::make_mut(&mut self.current).data.pop() {
+        match PoolRef::make_mut(&self.pool, &mut self.current).data.pop() {
             Some(Entry::Value(value, hash)) => {
@@ -647,0 +711,0 @@ self.count -= 1;

src/nodes/rrb.rs

@@ -11,5 +11,6 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 use crate::util::{
-    clone_ref, Ref,
+    Pool, PoolRef,
     Side::{self, Left, Right},
 };
+use crate::vector::RRBPool;
 
@@ -23,3 +24,3 @@ use self::Entry::*;
     Size(usize),
-    Table(Ref<Chunk<usize>>),
+    Table(PoolRef<Chunk<usize>>),
 }
@@ -51,3 +52,3 @@
 
-    fn table_from_size(level: usize, size: usize) -> Self {
+    fn table_from_size(pool: &Pool<Chunk<usize>>, level: usize, size: usize) -> Self {
         let mut chunk = Chunk::new();
@@ -65,6 +66,6 @@ let mut remaining = size;
         }
-        Size::Table(Ref::new(chunk))
+        Size::Table(PoolRef::new(pool, chunk))
     }
 
-    fn push(&mut self, side: Side, level: usize, value: usize) {
+    fn push(&mut self, pool: &Pool<Chunk<usize>>, side: Side, level: usize, value: usize) {
         let size = match self {
@@ -79,3 +80,3 @@ Size::Size(ref mut size) => match side {
             Size::Table(ref mut size_ref) => {
-                let size_table = Ref::make_mut(size_ref);
+                let size_table = PoolRef::make_mut(pool, size_ref);
                 debug_assert!(size_table.len() < NODE_SIZE);
@@ -97,7 +98,7 @@ match side {
         };
-        *self = Size::table_from_size(level, size);
-        self.push(side, level, value);
+        *self = Size::table_from_size(pool, level, size);
+        self.push(pool, side, level, value);
     }
 
-    fn pop(&mut self, side: Side, level: usize, value: usize) {
+    fn pop(&mut self, pool: &Pool<Chunk<usize>>, side: Side, level: usize, value: usize) {
         let size = match self {
@@ -112,3 +113,3 @@ Size::Size(ref mut size) => match side {
             Size::Table(ref mut size_ref) => {
-                let size_table = Ref::make_mut(size_ref);
+                let size_table = PoolRef::make_mut(pool, size_ref);
                 match side {
@@ -131,11 +132,11 @@ Left => {
         };
-        *self = Size::table_from_size(level, size);
-        self.pop(side, level, value);
+        *self = Size::table_from_size(pool, level, size);
+        self.pop(pool, side, level, value);
     }
 
-    fn update(&mut self, index: usize, level: usize, value: isize) {
+    fn update(&mut self, pool: &Pool<Chunk<usize>>, index: usize, level: usize, value: isize) {
         let size = match self {
             Size::Size(ref size) => *size,
             Size::Table(ref mut size_ref) => {
-                let size_table = Ref::make_mut(size_ref);
+                let size_table = PoolRef::make_mut(pool, size_ref);
                 for entry in size_table.iter_mut().skip(index) {
@@ -147,4 +148,4 @@ *entry = (*entry as isize + value) as usize;
         };
-        *self = Size::table_from_size(level, size);
-        self.update(index, level, value);
+        *self = Size::table_from_size(pool, level, size);
+        self.update(pool, index, level, value);
     }
@@ -171,4 +172,4 @@ }
 enum Entry<A> {
-    Nodes(Size, Ref<Chunk<Ref<Node<A>>>>),
-    Values(Ref<Chunk<A>>),
+    Nodes(Size, PoolRef<Chunk<Node<A>>>),
+    Values(PoolRef<Chunk<A>>),
     Empty,
@@ -196,10 +197,2 @@ }
 
-    fn is_empty(&self) -> bool {
-        match self {
-            Nodes(_, ref nodes) => nodes.is_empty(),
-            Values(ref values) => values.is_empty(),
-            Empty => true,
-        }
-    }
-
     fn is_full(&self) -> bool {
@@ -220,3 +213,3 @@ match self {
 
-    fn unwrap_nodes(&self) -> &Chunk<Ref<Node<A>>> {
+    fn unwrap_nodes(&self) -> &Chunk<Node<A>> {
         match self {
@@ -228,5 +221,5 @@ Nodes(_, ref nodes) => nodes,
 
-    fn unwrap_values_mut(&mut self) -> &mut Chunk<A> {
+    fn unwrap_values_mut(&mut self, pool: &RRBPool<A>) -> &mut Chunk<A> {
         match self {
-            Values(ref mut values) => Ref::make_mut(values),
+            Values(ref mut values) => PoolRef::make_mut(&pool.value_pool, values),
             _ => panic!("rrb::Entry::unwrap_values_mut: expected values, found nodes"),
@@ -236,5 +229,5 @@ }
 
-    fn unwrap_nodes_mut(&mut self) -> &mut Chunk<Ref<Node<A>>> {
+    fn unwrap_nodes_mut(&mut self, pool: &RRBPool<A>) -> &mut Chunk<Node<A>> {
         match self {
-            Nodes(_, ref mut nodes) => Ref::make_mut(nodes),
+            Nodes(_, ref mut nodes) => PoolRef::make_mut(&pool.node_pool, nodes),
             _ => panic!("rrb::Entry::unwrap_nodes_mut: expected nodes, found values"),
@@ -246,3 +239,3 @@ }
         match self {
-            Values(values) => clone_ref(values),
+            Values(values) => PoolRef::unwrap_or_clone(values),
             _ => panic!("rrb::Entry::values: expected values, found nodes"),
@@ -252,5 +245,5 @@ }
 
-    fn nodes(self) -> Chunk<Ref<Node<A>>> {
+    fn nodes(self) -> Chunk<Node<A>> {
         match self {
-            Nodes(_, nodes) => clone_ref(nodes),
+            Nodes(_, nodes) => PoolRef::unwrap_or_clone(nodes),
             _ => panic!("rrb::Entry::nodes: expected nodes, found values"),
@@ -293,3 +286,3 @@ }
 
-    pub fn parent(level: usize, children: Chunk<Ref<Self>>) -> Self {
+    pub fn parent(pool: &RRBPool<A>, level: usize, children: Chunk<Self>) -> Self {
         let size = {
@@ -306,5 +299,5 @@ let mut size = Size::Size(0);
                         {
-                            size = Size::table_from_size(level, size.size());
+                            size = Size::table_from_size(&pool.size_pool, level, size.size());
                         }
-                        size.push(Right, level, child.len())
+                        size.push(&pool.size_pool, Right, level, child.len())
                     }
@@ -316,3 +309,3 @@ }
         Node {
-            children: Nodes(size, Ref::from(children)),
+            children: Nodes(size, PoolRef::new(&pool.node_pool, children)),
         }
@@ -325,10 +318,10 @@ }
 
-    pub fn from_chunk(level: usize, chunk: Ref<Chunk<A>>) -> Self {
+    pub fn from_chunk(pool: &RRBPool<A>, level: usize, chunk: PoolRef<Chunk<A>>) -> Self {
         let node = Node {
             children: Values(chunk),
         };
-        node.elevate(level)
+        node.elevate(pool, level)
     }
 
-    pub fn single_parent(node: Ref<Self>) -> Self {
+    pub fn single_parent(pool: &RRBPool<A>, node: Self) -> Self {
         let size = if node.is_dense() {
@@ -338,11 +331,11 @@ Size::Size(node.len())
             let size_table = Chunk::unit(node.len());
-            Size::Table(Ref::from(size_table))
+            Size::Table(PoolRef::new(&pool.size_pool, size_table))
         };
-        let children = Chunk::unit(node);
+        let children = PoolRef::new(&pool.node_pool, Chunk::unit(node));
         Node {
-            children: Nodes(size, Ref::from(children)),
+            children: Nodes(size, children),
         }
     }
 
-    pub fn join_dense(left: Ref<Self>, right: Ref<Self>) -> Self {
+    pub fn join_dense(pool: &RRBPool<A>, left: Self, right: Self) -> Self {
         let left_len = left.len();
@@ -352,4 +345,4 @@ let right_len = right.len();
             children: {
-                let children = Chunk::pair(left, right);
-                Nodes(Size::Size(left_len + right_len), Ref::from(children))
+                let children = PoolRef::new(&pool.node_pool, Chunk::pair(left, right));
+                Nodes(Size::Size(left_len + right_len), children)
             },
@@ -359,5 +352,5 @@ }
 
-    pub fn elevate(self, level_increment: usize) -> Self {
+    pub fn elevate(self, pool: &RRBPool<A>, level_increment: usize) -> Self {
         if level_increment > 0 {
-            Self::single_parent(Ref::from(self.elevate(level_increment - 1)))
+            Self::single_parent(pool, self.elevate(pool, level_increment - 1))
         } else {
@@ -368,3 +361,3 @@ self
 
-    pub fn join_branches(self, right: Self, level: usize) -> Self {
+    pub fn join_branches(self, pool: &RRBPool<A>, right: Self, level: usize) -> Self {
         let left_len = self.len();
@@ -376,8 +369,8 @@ let right_len = right.len();
             let size_table = Chunk::pair(left_len, left_len + right_len);
-            Size::Table(Ref::from(size_table))
+            Size::Table(PoolRef::new(&pool.size_pool, size_table))
         };
         Node {
             children: {
-                let children = Chunk::pair(Ref::from(self), Ref::from(right));
-                Nodes(size, Ref::from(children))
+                let children = Chunk::pair(self, right);
+                Nodes(size, PoolRef::new(&pool.node_pool, children))
             },
@@ -397,3 +390,3 @@ }
     pub fn is_empty(&self) -> bool {
-        self.children.is_empty()
+        self.len() == 0
     }
@@ -413,3 +406,3 @@
 
-    pub fn first_child(&self) -> &Ref<Self> {
+    pub fn first_child(&self) -> &Self {
         self.children.unwrap_nodes().first().unwrap()
@@ -445,5 +438,5 @@ }
     #[inline]
-    fn push_size(&mut self, side: Side, level: usize, value: usize) {
+    fn push_size(&mut self, pool: &RRBPool<A>, side: Side, level: usize, value: usize) {
         if let Entry::Nodes(ref mut size, _) = self.children {
-            size.push(side, level, value)
+            size.push(&pool.size_pool, side, level, value)
         }
@@ -453,5 +446,5 @@ }
     #[inline]
-    fn pop_size(&mut self, side: Side, level: usize, value: usize) {
+    fn pop_size(&mut self, pool: &RRBPool<A>, side: Side, level: usize, value: usize) {
         if let Entry::Nodes(ref mut size, _) = self.children {
-            size.pop(side, level, value)
+            size.pop(&pool.size_pool, side, level, value)
         }
@@ -461,5 +454,5 @@ }
     #[inline]
-    fn update_size(&mut self, index: usize, level: usize, value: isize) {
+    fn update_size(&mut self, pool: &RRBPool<A>, index: usize, level: usize, value: isize) {
         if let Entry::Nodes(ref mut size, _) = self.children {
-            size.update(index, level, value)
+            size.update(&pool.size_pool, index, level, value)
         }
@@ -509,10 +502,10 @@ }
 
-    pub fn index_mut(&mut self, level: usize, index: usize) -> &mut A {
+    pub fn index_mut(&mut self, pool: &RRBPool<A>, level: usize, index: usize) -> &mut A {
         if level == 0 {
-            &mut self.children.unwrap_values_mut()[index]
+            &mut self.children.unwrap_values_mut(pool)[index]
         } else {
             let target_idx = self.index_in(level, index).unwrap();
             let offset = index - self.size_up_to(level, target_idx);
-            let child = Ref::make_mut(&mut self.children.unwrap_nodes_mut()[target_idx]);
-            child.index_mut(level - 1, offset)
+            let child = &mut self.children.unwrap_nodes_mut(pool)[target_idx];
+            child.index_mut(pool, level - 1, offset)
         }
@@ -537,3 +530,3 @@ }
             let children = self.children.unwrap_nodes();
-            let child = &*children[target_idx];
+            let child = &children[target_idx];
             child.lookup_chunk(level - 1, child_base, index - offset)
@@ -545,2 +538,3 @@ }
         &mut self,
+        pool: &RRBPool<A>,
         level: usize,
@@ -553,3 +547,3 @@ base: usize,
                 base..(base + self.children.len()),
-                self.children.unwrap_values_mut() as *mut Chunk<A>,
+                self.children.unwrap_values_mut(pool) as *mut Chunk<A>,
             )
@@ -560,10 +554,10 @@ } else {
             let child_base = base + offset;
-            let children = self.children.unwrap_nodes_mut();
-            let child = Ref::make_mut(&mut children[target_idx]);
-            child.lookup_chunk_mut(level - 1, child_base, index - offset)
+            let children = self.children.unwrap_nodes_mut(pool);
+            let child = &mut children[target_idx];
+            child.lookup_chunk_mut(pool, level - 1, child_base, index - offset)
         }
     }
 
-    fn push_child_node(&mut self, side: Side, child: Ref<Node<A>>) {
-        let children = self.children.unwrap_nodes_mut();
+    fn push_child_node(&mut self, pool: &RRBPool<A>, side: Side, child: Node<A>) {
+        let children = self.children.unwrap_nodes_mut(pool);
         match side {
@@ -575,4 +569,4 @@ Left => children.push_front(child),
 
-    fn pop_child_node(&mut self, side: Side) -> Ref<Node<A>> {
-        let children = self.children.unwrap_nodes_mut();
+    fn pop_child_node(&mut self, pool: &RRBPool<A>, side: Side) -> Node<A> {
+        let children = self.children.unwrap_nodes_mut(pool);
         match side {
@@ -586,6 +580,7 @@ Left => children.pop_front(),
         &mut self,
+        pool: &RRBPool<A>,
         level: usize,
         side: Side,
-        mut chunk: Ref<Chunk<A>>,
-    ) -> PushResult<Ref<Chunk<A>>> {
+        mut chunk: PoolRef<Chunk<A>>,
+    ) -> PushResult<PoolRef<Chunk<A>>> {
         if chunk.is_empty() {
@@ -597,9 +592,9 @@ return PushResult::Done;
             if self.children.is_empty_node() {
-                self.push_size(side, level, chunk.len());
+                self.push_size(pool, side, level, chunk.len());
                 self.children = Values(chunk);
                 PushResult::Done
             } else {
-                let values = self.children.unwrap_values_mut();
+                let values = self.children.unwrap_values_mut(pool);
                 if values.len() + chunk.len() <= NODE_SIZE {
-                    let chunk = Ref::make_mut(&mut chunk);
+                    let chunk = PoolRef::make_mut(&pool.value_pool, &mut chunk);
                     match side {
@@ -623,10 +618,12 @@ Side::Left => {
                     if let Entry::Nodes(ref mut size, ref mut children) = self.children {
-                        let rightmost = Ref::make_mut(Ref::make_mut(children).last_mut().unwrap());
+                        let rightmost = PoolRef::make_mut(&pool.node_pool, children)
+                            .last_mut()
+                            .unwrap();
                         let old_size = rightmost.len();
-                        let chunk = Ref::make_mut(&mut chunk);
-                        let values = rightmost.children.unwrap_values_mut();
+                        let chunk = PoolRef::make_mut(&pool.value_pool, &mut chunk);
+                        let values = rightmost.children.unwrap_values_mut(pool);
                         let to_drain = chunk.len().min(NODE_SIZE - values.len());
                         values.drain_from_front(chunk, to_drain);
-                        size.pop(Side::Right, level, old_size);
-                        size.push(Side::Right, level, values.len());
+                        size.pop(&pool.size_pool, Side::Right, level, old_size);
+                        size.push(&pool.size_pool, Side::Right, level, values.len());
                         to_drain
@@ -639,10 +636,12 @@ } else {
                     if let Entry::Nodes(ref mut size, ref mut children) = self.children {
-                        let leftmost = Ref::make_mut(Ref::make_mut(children).first_mut().unwrap());
+                        let leftmost = PoolRef::make_mut(&pool.node_pool, children)
+                            .first_mut()
+                            .unwrap();
                         let old_size = leftmost.len();
-                        let chunk = Ref::make_mut(&mut chunk);
-                        let values = leftmost.children.unwrap_values_mut();
+                        let chunk = PoolRef::make_mut(&pool.value_pool, &mut chunk);
+                        let values = leftmost.children.unwrap_values_mut(pool);
                         let to_drain = chunk.len().min(NODE_SIZE - values.len());
                         values.drain_from_back(chunk, to_drain);
-                        size.pop(Side::Left, level, old_size);
-                        size.push(Side::Left, level, values.len());
+                        size.pop(&pool.size_pool, Side::Left, level, old_size);
+                        size.push(&pool.size_pool, Side::Left, level, values.len());
                         to_drain
@@ -664,8 +663,8 @@ } else {
                             if let Size::Size(value) = *size {
-                                *size = Size::table_from_size(level, value);
+                                *size = Size::table_from_size(&pool.size_pool, level, value);
                             }
                         }
                     }
-                    self.push_size(side, level, chunk.len());
-                    self.push_child_node(side, Ref::new(Node::from_chunk(0, chunk)));
+                    self.push_size(pool, side, level, chunk.len());
+                    self.push_child_node(pool, side, Node::from_chunk(pool, 0, chunk));
                 }
@@ -681,5 +680,5 @@ PushResult::Done
             let new_child = {
-                let children = self.children.unwrap_nodes_mut();
-                let child = Ref::make_mut(&mut children[index]);
-                match child.push_chunk(level - 1, side, chunk) {
+                let children = self.children.unwrap_nodes_mut(pool);
+                let child = &mut children[index];
+                match child.push_chunk(pool, level - 1, side, chunk) {
                     PushResult::Done => None,
@@ -694,3 +693,3 @@ PushResult::Full(chunk, num_drained) => {
                                 Entry::Nodes(Size::Table(ref mut sizes), _) => {
-                                    let sizes = Ref::make_mut(sizes);
+                                    let sizes = PoolRef::make_mut(&pool.size_pool, sizes);
                                     sizes[index] += num_drained;
@@ -704,3 +703,3 @@ }
                             Left => {
-                                self.update_size(0, level, num_drained as isize);
+                                self.update_size(pool, 0, level, num_drained as isize);
                             }
@@ -711,3 +710,3 @@ }
                         } else {
-                            Some(Node::from_chunk(level - 1, chunk))
+                            Some(Node::from_chunk(pool, level - 1, chunk))
                         }
@@ -719,3 +718,3 @@ }
                 None => {
-                    self.update_size(index, level, chunk_size as isize);
+                    self.update_size(pool, index, level, chunk_size as isize);
                     PushResult::Done
@@ -727,8 +726,8 @@ }
                             if let Size::Size(value) = *size {
-                                *size = Size::table_from_size(level, value);
+                                *size = Size::table_from_size(&pool.size_pool, level, value);
                             }
                         }
                     }
-                    self.push_size(side, level, child.len());
-                    self.push_child_node(side, Ref::from(child));
+                    self.push_size(pool, side, level, child.len());
+                    self.push_child_node(pool, side, child);
                     PushResult::Done
@@ -740,3 +739,8 @@ }
 
-    pub fn pop_chunk(&mut self, level: usize, side: Side) -> PopResult<Ref<Chunk<A>>> {
+    pub fn pop_chunk(
+        &mut self,
+        pool: &RRBPool<A>,
+        level: usize,
+        side: Side,
+    ) -> PopResult<PoolRef<Chunk<A>>> {
         if self.is_empty() {
@@ -753,4 +757,4 @@ return PopResult::Empty;
         } else if level == 1 {
-            let child_node = self.pop_child_node(side);
-            self.pop_size(side, level, child_node.len());
+            let child_node = self.pop_child_node(pool, side);
+            self.pop_size(pool, side, level, child_node.len());
             let chunk = match child_node.children {
@@ -773,5 +777,5 @@ Values(ref chunk) => chunk.clone(),
             let chunk = {
-                let children = self.children.unwrap_nodes_mut();
-                let child = Ref::make_mut(&mut children[index]);
-                match child.pop_chunk(level - 1, side) {
+                let children = self.children.unwrap_nodes_mut(pool);
+                let child = &mut children[index];
+                match child.pop_chunk(pool, level - 1, side) {
                     PopResult::Empty => return PopResult::Empty,
@@ -786,4 +790,4 @@ PopResult::Done(chunk) => chunk,
             if drained {
-                self.pop_size(side, level, chunk.len());
-                self.pop_child_node(side);
+                self.pop_size(pool, side, level, chunk.len());
+                self.pop_child_node(pool, side);
                 if self.is_empty() {
@@ -795,3 +799,3 @@ PopResult::Drained(chunk)
             } else {
-                self.update_size(index, level, -(chunk.len() as isize));
+                self.update_size(pool, index, level, -(chunk.len() as isize));
                 PopResult::Done(chunk)
@@ -802,3 +806,9 @@ }
 
-    pub fn split(&mut self, level: usize, drop_side: Side, index: usize) -> SplitResult {
+    pub fn split(
+        &mut self,
+        pool: &RRBPool<A>,
+        level: usize,
+        drop_side: Side,
+        index: usize,
+    ) -> SplitResult {
         if index == 0 && drop_side == Side::Left {
@@ -824,3 +834,3 @@ // Dropped nothing
             }
-            let children = self.children.unwrap_values_mut();
+            let children = self.children.unwrap_values_mut(pool);
             match drop_side {
@@ -838,3 +848,3 @@ Side::Left => children.drop_left(index),
                 if let Entry::Nodes(ref mut size, ref mut children) = self.children {
-                    (size, Ref::make_mut(children))
+                    (size, PoolRef::make_mut(&pool.node_pool, children))
                 } else {
@@ -844,4 +854,4 @@ unreachable!()
             let child_gone = 0 == {
-                let child_node = Ref::make_mut(&mut children[target_idx]);
-                match child_node.split(level - 1, drop_side, index - size_up_to) {
+                let child_node = &mut children[target_idx];
+                match child_node.split(pool, level - 1, drop_side, index - size_up_to) {
                     SplitResult::OutOfBounds => return SplitResult::OutOfBounds,
@@ -860,6 +870,6 @@ SplitResult::Dropped(amount) => dropped = amount,
                     if let Size::Size(value) = *size {
-                        *size = Size::table_from_size(level, value);
+                        *size = Size::table_from_size(&pool.size_pool, level, value);
                     }
                     let size_table = if let Size::Table(ref mut size_ref) = size {
-                        Ref::make_mut(size_ref)
+                        PoolRef::make_mut(&pool.size_pool, size_ref)
                     } else {
@@ -906,3 +916,3 @@ unreachable!()
                         Size::Table(ref mut size_ref) => {
-                            let size_table = Ref::make_mut(size_ref);
+                            let size_table = PoolRef::make_mut(&pool.size_pool, size_ref);
                             let dropped_size =
@@ -927,16 +937,14 @@ size_table[size_table.len() - 1] - size_table[target_idx];
 
-    fn merge_leaves(mut left: Ref<Self>, mut right: Ref<Self>) -> Self {
+    fn merge_leaves(pool: &RRBPool<A>, mut left: Self, mut right: Self) -> Self {
         if left.children.is_empty_node() {
             // Left is empty, just use right
-            Self::single_parent(right)
+            Self::single_parent(pool, right)
         } else if right.children.is_empty_node() {
             // Right is empty, just use left
-            Self::single_parent(left)
+            Self::single_parent(pool, left)
         } else {
             {
-                let left_node = Ref::make_mut(&mut left);
-                let right_node = Ref::make_mut(&mut right);
-                let left_vals = left_node.children.unwrap_values_mut();
+                let left_vals = left.children.unwrap_values_mut(pool);
                 let left_len = left_vals.len();
-                let right_vals = right_node.children.unwrap_values_mut();
+                let right_vals = right.children.unwrap_values_mut(pool);
                 let right_len = right_vals.len();
@@ -951,5 +959,5 @@ if left_len + right_len <= NODE_SIZE {
             if right.is_empty() {
-                Self::single_parent(left)
+                Self::single_parent(pool, left)
             } else {
-                Self::join_dense(left, right)
+                Self::join_dense(pool, left, right)
             }
@@ -959,6 +967,12 @@ }
 
-    fn merge_rebalance(level: usize, left: Ref<Self>, middle: Self, right: Ref<Self>) -> Self {
-        let left_nodes = clone_ref(left).children.nodes().into_iter();
+    fn merge_rebalance(
+        pool: &RRBPool<A>,
+        level: usize,
+        left: Self,
+        middle: Self,
+        right: Self,
+    ) -> Self {
+        let left_nodes = left.children.nodes().into_iter();
         let middle_nodes = middle.children.nodes().into_iter();
-        let right_nodes = clone_ref(right).children.nodes().into_iter();
+        let right_nodes = right.children.nodes().into_iter();
         let mut subtree_still_balanced = true;
@@ -980,13 +994,13 @@ let mut next_leaf = Chunk::new();
 
-            let child = clone_ref(subtree);
             if level == 1 {
-                for value in child.children.values() {
+                for value in subtree.children.values() {
                     next_leaf.push_back(value);
                     if next_leaf.is_full() {
-                        let new_node = Node::from_chunk(0, Ref::from(next_leaf));
-                        next_subtree.push_back(Ref::from(new_node));
+                        let new_node =
+                            Node::from_chunk(pool, 0, PoolRef::new(&pool.value_pool, next_leaf));
+                        next_subtree.push_back(new_node);
                         next_leaf = Chunk::new();
                         if next_subtree.is_full() {
-                            let new_subtree = Node::parent(level, next_subtree);
-                            root.push_back(Ref::from(new_subtree));
+                            let new_subtree = Node::parent(pool, level, next_subtree);
+                            root.push_back(new_subtree);
                             next_subtree = Chunk::new();
@@ -997,11 +1011,11 @@ }
             } else {
-                for node in child.children.nodes() {
+                for node in subtree.children.nodes() {
                     next_node.push_back(node);
                     if next_node.is_full() {
-                        let new_node = Node::parent(level - 1, next_node);
-                        next_subtree.push_back(Ref::from(new_node));
+                        let new_node = Node::parent(pool, level - 1, next_node);
+                        next_subtree.push_back(new_node);
                         next_node = Chunk::new();
                         if next_subtree.is_full() {
-                            let new_subtree = Node::parent(level, next_subtree);
-                            root.push_back(Ref::from(new_subtree));
+                            let new_subtree = Node::parent(pool, level, next_subtree);
+                            root.push_back(new_subtree);
                             next_subtree = Chunk::new();
@@ -1014,19 +1028,19 @@ }
         if !next_leaf.is_empty() {
-            let new_node = Node::from_chunk(0, Ref::from(next_leaf));
-            next_subtree.push_back(Ref::from(new_node));
+            let new_node = Node::from_chunk(pool, 0, PoolRef::new(&pool.value_pool, next_leaf));
+            next_subtree.push_back(new_node);
         }
         if !next_node.is_empty() {
-            let new_node = Node::parent(level - 1, next_node);
-            next_subtree.push_back(Ref::from(new_node));
+            let new_node = Node::parent(pool, level - 1, next_node);
+            next_subtree.push_back(new_node);
         }
         if !next_subtree.is_empty() {
-            let new_subtree = Node::parent(level, next_subtree);
-            root.push_back(Ref::from(new_subtree));
+            let new_subtree = Node::parent(pool, level, next_subtree);
+            root.push_back(new_subtree);
         }
-        Node::parent(level + 1, root)
+        Node::parent(pool, level + 1, root)
     }
 
-    pub fn merge(mut left: Ref<Self>, mut right: Ref<Self>, level: usize) -> Self {
+    pub fn merge(pool: &RRBPool<A>, mut left: Self, mut right: Self, level: usize) -> Self {
         if level == 0 {
-            Self::merge_leaves(left, right)
+            Self::merge_leaves(pool, left, right)
         } else {
@@ -1037,11 +1051,9 @@ let merged = {
                     // no need for a middle at level 1
-                    Node::parent(0, Chunk::new())
+                    Node::parent(pool, 0, Chunk::new())
                 } else {
-                    let left_node = Ref::make_mut(&mut left);
-                    let right_node = Ref::make_mut(&mut right);
                     let left_last =
-                        if let Entry::Nodes(ref mut size, ref mut children) = left_node.children {
-                            let node = Ref::make_mut(children).pop_back();
-                            if node.len() > 0 {
-                                size.pop(Side::Right, level, node.len());
+                        if let Entry::Nodes(ref mut size, ref mut children) = left.children {
+                            let node = PoolRef::make_mut(&pool.node_pool, children).pop_back();
+                            if !node.is_empty() {
+                                size.pop(&pool.size_pool, Side::Right, level, node.len());
                             }
@@ -1053,6 +1065,6 @@ node
                     let right_first =
-                        if let Entry::Nodes(ref mut size, ref mut children) = right_node.children {
-                            let node = Ref::make_mut(children).pop_front();
-                            if node.len() > 0 {
-                                size.pop(Side::Left, level, node.len());
+                        if let Entry::Nodes(ref mut size, ref mut children) = right.children {
+                            let node = PoolRef::make_mut(&pool.node_pool, children).pop_front();
+                            if !node.is_empty() {
+                                size.pop(&pool.size_pool, Side::Left, level, node.len());
                             }
@@ -1063,6 +1075,6 @@ node
                         };
-                    Self::merge(left_last, right_first, level - 1)
+                    Self::merge(pool, left_last, right_first, level - 1)
                 }
             };
-            Self::merge_rebalance(level, left, merged, right)
+            Self::merge_rebalance(pool, level, left, merged, right)
         }
@@ -1159,2 +1171,3 @@ }
 pub struct ConsumingIter<A> {
+    pool: RRBPool<A>,
     root: Node<A>,
@@ -1168,4 +1181,5 @@ level: usize,
 impl<A: Clone> ConsumingIter<A> {
-    pub fn new(root: Node<A>, level: usize) -> Self {
+    pub fn new(pool: RRBPool<A>, root: Node<A>, level: usize) -> Self {
         ConsumingIter {
+            pool,
             remaining: root.len(),
@@ -1193,5 +1207,5 @@ root,
         }
-        match self.root.pop_chunk(self.level, Side::Left) {
-            PopResult::Done(chunk) => self.front_chunk = Some(clone_ref(chunk)),
-            PopResult::Drained(chunk) => self.front_chunk = Some(clone_ref(chunk)),
+        match self.root.pop_chunk(&self.pool, self.level, Side::Left) {
+            PopResult::Done(chunk) => self.front_chunk = Some(PoolRef::unwrap_or_clone(chunk)),
+            PopResult::Drained(chunk) => self.front_chunk = Some(PoolRef::unwrap_or_clone(chunk)),
             PopResult::Empty => {
@@ -1227,5 +1241,5 @@ if let Some(ref mut chunk) = self.back_chunk {
         }
-        match self.root.pop_chunk(self.level, Side::Left) {
-            PopResult::Done(chunk) => self.front_chunk = Some(clone_ref(chunk)),
-            PopResult::Drained(chunk) => self.front_chunk = Some(clone_ref(chunk)),
+        match self.root.pop_chunk(&self.pool, self.level, Side::Left) {
+            PopResult::Done(chunk) => self.front_chunk = Some(PoolRef::unwrap_or_clone(chunk)),
+            PopResult::Drained(chunk) => self.front_chunk = Some(PoolRef::unwrap_or_clone(chunk)),
             PopResult::Empty => {
@@ -1232,0 +1246,0 @@ if let Some(ref mut chunk) = self.front_chunk {

src/ord/set.rs

@@ -35,3 +35,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 use crate::util::linear_search_by;
-use crate::util::Ref;
+use crate::util::{Pool, PoolRef};
 
@@ -160,2 +160,4 @@ pub use crate::nodes::btree::DiffItem;
 
+def_pool!(OrdSetPool<A>, Node<Value<A>>);
+
 /// An ordered set.
@@ -177,3 +179,4 @@ ///
     size: usize,
-    root: Ref<Node<Value<A>>>,
+    pool: OrdSetPool<A>,
+    root: PoolRef<Node<Value<A>>>,
 }
@@ -185,8 +188,23 @@
     pub fn new() -> Self {
+        let pool = OrdSetPool::default();
+        let root = PoolRef::default(&pool.0);
         OrdSet {
             size: 0,
-            root: Ref::from(Node::new()),
+            pool,
+            root,
         }
     }
 
+    /// Construct an empty set using a specific memory pool.
+    #[cfg(feature = "pool")]
+    #[must_use]
+    pub fn with_pool(pool: &OrdSetPool<A>) -> Self {
+        let root = PoolRef::default(&pool.0);
+        OrdSet {
+            size: 0,
+            pool: pool.clone(),
+            root,
+        }
+    }
+
     /// Construct a set with a single value.
@@ -199,6 +217,4 @@ ///
     /// # use im::ordset::OrdSet;
-    /// # fn main() {
     /// let set = OrdSet::unit(123);
     /// assert!(set.contains(&123));
-    /// # }
     /// ```
@@ -208,5 +224,8 @@ #[inline]
     pub fn unit(a: A) -> Self {
+        let pool = OrdSetPool::default();
+        let root = PoolRef::new(&pool.0, Node::unit(Value(a)));
         OrdSet {
             size: 1,
-            root: Ref::from(Node::unit(Value(a))),
+            pool,
+            root,
         }
@@ -224,3 +243,2 @@ }
     /// # use im::ordset::OrdSet;
-    /// # fn main() {
     /// assert!(
@@ -232,3 +250,2 @@ ///   !ordset![1, 2, 3].is_empty()
     /// );
-    /// # }
     /// ```
@@ -250,5 +267,3 @@ #[inline]
     /// # use im::ordset::OrdSet;
-    /// # fn main() {
     /// assert_eq!(3, ordset![1, 2, 3].len());
-    /// # }
     /// ```
@@ -261,2 +276,11 @@ #[inline]
 
+    /// Get a reference to the memory pool used by this set.
+    ///
+    /// Note that if you didn't specifically construct it with a pool, you'll
+    /// get back a reference to a pool of size 0.
+    #[cfg(feature = "pool")]
+    pub fn pool(&self) -> &OrdSetPool<A> {
+        &self.pool
+    }
+
     /// Discard all elements from the set.
@@ -274,11 +298,9 @@ ///
     /// # use im::OrdSet;
-    /// # fn main() {
     /// let mut set = ordset![1, 2, 3];
     /// set.clear();
     /// assert!(set.is_empty());
-    /// # }
     /// ```
     pub fn clear(&mut self) {
         if !self.is_empty() {
-            self.root = Default::default();
+            self.root = PoolRef::default(&self.pool.0);
             self.size = 0;
@@ -361,7 +383,5 @@ }
     /// # use im::ordset::OrdSet;
-    /// # fn main() {
     /// let mut set = ordset!{1, 2, 3};
     /// assert!(set.contains(&1));
     /// assert!(!set.contains(&4));
-    /// # }
     /// ```
@@ -421,3 +441,2 @@ #[inline]
     /// # use im::ordset::OrdSet;
-    /// # fn main() {
     /// let mut set = ordset!{};
@@ -430,3 +449,2 @@ /// set.insert(123);
     /// );
-    /// # }
     /// ```
@@ -436,4 +454,4 @@ #[inline]
         let new_root = {
-            let root = Ref::make_mut(&mut self.root);
-            match root.insert(Value(a)) {
+            let root = PoolRef::make_mut(&self.pool.0, &mut self.root);
+            match root.insert(&self.pool.0, Value(a)) {
                 Insert::Replaced(Value(old_value)) => return Some(old_value),
@@ -444,6 +462,7 @@ Insert::Added => {
                 }
-                Insert::Update(root) => Ref::from(root),
-                Insert::Split(left, median, right) => {
-                    Ref::from(Node::new_from_split(left, median, right))
-                }
+                Insert::Update(root) => PoolRef::new(&self.pool.0, root),
+                Insert::Split(left, median, right) => PoolRef::new(
+                    &self.pool.0,
+                    Node::new_from_split(&self.pool.0, left, median, right),
+                ),
             }
@@ -466,5 +485,5 @@ };
         let (new_root, removed_value) = {
-            let root = Ref::make_mut(&mut self.root);
-            match root.remove(a) {
-                Remove::Update(value, root) => (Ref::from(root), Some(value.0)),
+            let root = PoolRef::make_mut(&self.pool.0, &mut self.root);
+            match root.remove(&self.pool.0, a) {
+                Remove::Update(value, root) => (PoolRef::new(&self.pool.0, root), Some(value.0)),
                 Remove::Removed(value) => {
@@ -518,3 +537,2 @@ self.size -= 1;
     /// # use im::ordset::OrdSet;
-    /// # fn main() {
     /// let set = ordset![456];
@@ -525,3 +543,2 @@ /// assert_eq!(
     /// );
-    /// # }
     /// ```
@@ -583,3 +600,2 @@ #[must_use]
     /// # use im::ordset::OrdSet;
-    /// # fn main() {
     /// let set1 = ordset!{1, 2};
@@ -589,3 +605,2 @@ /// let set2 = ordset!{2, 3};
     /// assert_eq!(expected, set1.union(set2));
-    /// # }
     /// ```
@@ -623,3 +638,2 @@ #[must_use]
     /// # use im::ordset::OrdSet;
-    /// # fn main() {
     /// let set1 = ordset!{1, 2};
@@ -629,3 +643,2 @@ /// let set2 = ordset!{2, 3};
     /// assert_eq!(expected, set1.difference(set2));
-    /// # }
     /// ```
@@ -648,3 +661,2 @@ ///
     /// # use im::ordset::OrdSet;
-    /// # fn main() {
     /// let set1 = ordset!{1, 2};
@@ -654,3 +666,2 @@ /// let set2 = ordset!{2, 3};
     /// assert_eq!(expected, set1.symmetric_difference(set2));
-    /// # }
     /// ```
@@ -677,3 +688,2 @@ #[must_use]
     /// # use im::ordset::OrdSet;
-    /// # fn main() {
     /// let set1 = ordset!{1, 2};
@@ -683,3 +693,2 @@ /// let set2 = ordset!{2, 3};
     /// assert_eq!(expected, set1.relative_complement(set2));
-    /// # }
     /// ```
@@ -703,3 +712,2 @@ #[must_use]
     /// # use im::ordset::OrdSet;
-    /// # fn main() {
     /// let set1 = ordset!{1, 2};
@@ -709,3 +717,2 @@ /// let set2 = ordset!{2, 3};
     /// assert_eq!(expected, set1.intersection(set2));
-    /// # }
     /// ```
@@ -799,2 +806,3 @@ #[must_use]
             size: self.size,
+            pool: self.pool.clone(),
             root: self.root.clone(),
@@ -807,3 +815,3 @@ }
     fn eq(&self, other: &Self) -> bool {
-        Ref::ptr_eq(&self.root, &other.root)
+        PoolRef::ptr_eq(&self.root, &other.root)
             || (self.len() == other.len() && self.diff(other).next().is_none())
@@ -1155,2 +1163,3 @@ }
 pub mod proptest {
+    //! Proptest strategies.
     use super::*;
@@ -1157,0 +1166,0 @@ use ::proptest::strategy::{BoxedStrategy, Strategy, ValueTree};

src/util.rs

@@ -11,11 +11,34 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 
+#[cfg(feature = "pool")]
+pub use refpool::{PoolClone, PoolDefault};
+
 // The `Ref` type is an alias for either `Rc` or `Arc`, user's choice.
+
+// `Arc` without refpool
+#[cfg(all(threadsafe, not(feature = "pool")))]
+pub use crate::fakepool::{Arc as PoolRef, Pool, PoolClone, PoolDefault};
+
+// `Arc` with refpool
+#[cfg(all(threadsafe, feature = "pool"))]
+pub type PoolRef<A> = refpool::PoolRef<A, refpool::PoolSync>;
+#[cfg(all(threadsafe, feature = "pool"))]
+pub type Pool<A> = refpool::Pool<A, refpool::PoolSync>;
+
+// `Ref` == `Arc` when threadsafe
 #[cfg(threadsafe)]
-use std::sync::Arc;
-#[cfg(threadsafe)]
-pub type Ref<A> = Arc<A>;
+pub type Ref<A> = std::sync::Arc<A>;
+
+// `Rc` without refpool
+#[cfg(all(not(threadsafe), not(feature = "pool")))]
+pub use crate::fakepool::{Pool, PoolClone, PoolDefault, Rc as PoolRef};
+
+// `Rc` with refpool
+#[cfg(all(not(threadsafe), feature = "pool"))]
+pub type PoolRef<A> = refpool::PoolRef<A, refpool::PoolUnsync>;
+#[cfg(all(not(threadsafe), feature = "pool"))]
+pub type Pool<A> = refpool::Pool<A, refpool::PoolUnsync>;
+
+// `Ref` == `Rc` when not threadsafe
 #[cfg(not(threadsafe))]
-use std::rc::Rc;
-#[cfg(not(threadsafe))]
-pub type Ref<A> = Rc<A>;
+pub type Ref<A> = std::rc::Rc<A>;
 
@@ -91,1 +114,37 @@ pub fn clone_ref<A>(r: Ref<A>) -> A
 }
+
+macro_rules! def_pool {
+    ($name:ident<$($arg:tt),*>, $pooltype:ty) => {
+        /// A memory pool for the appropriate node type.
+        pub struct $name<$($arg,)*>(Pool<$pooltype>);
+
+        impl<$($arg,)*> $name<$($arg,)*> {
+            /// Create a new pool with the given size.
+            pub fn new(size: usize) -> Self {
+                Self(Pool::new(size))
+            }
+
+            /// Fill the pool with preallocated chunks.
+            pub fn fill(&self) {
+                self.0.fill();
+            }
+
+            ///Get the current size of the pool.
+            pub fn pool_size(&self) -> usize {
+                self.0.get_pool_size()
+            }
+        }
+
+        impl<$($arg,)*> Default for $name<$($arg,)*> {
+            fn default() -> Self {
+                Self::new($crate::config::POOL_SIZE)
+            }
+        }
+
+        impl<$($arg,)*> Clone for $name<$($arg,)*> {
+            fn clone(&self) -> Self {
+                Self(self.0.clone())
+            }
+        }
+    };
+}

src/vector/focus.rs

@@ -12,4 +12,4 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 use crate::sync::Lock;
-use crate::util::{to_range, Ref};
-use crate::vector::{Iter, IterMut, Vector, RRB};
+use crate::util::{to_range, PoolRef, Ref};
+use crate::vector::{Iter, IterMut, RRBPool, Vector, RRB};
 
@@ -57,3 +57,2 @@ /// Focused indexing over a [`Vector`][Vector].
 /// # use std::iter::FromIterator;
-/// # fn main() {
 /// let mut vec: Vector<i64> = Vector::from_iter(0..1000);
@@ -79,3 +78,2 @@ ///
 /// assert_eq!(499500, sum);
-/// # }
 /// ```
@@ -106,5 +104,5 @@ ///
         match vector {
-            Vector::Inline(chunk) => Focus::Single(chunk),
-            Vector::Single(chunk) => Focus::Single(chunk),
-            Vector::Full(tree) => Focus::Full(TreeFocus::new(tree)),
+            Vector::Inline(_, chunk) => Focus::Single(chunk),
+            Vector::Single(_, chunk) => Focus::Single(chunk),
+            Vector::Full(_, tree) => Focus::Full(TreeFocus::new(tree)),
         }
@@ -173,3 +171,2 @@ }
     /// # use std::iter::FromIterator;
-    /// # fn main() {
     /// let vec = Vector::from_iter(0..1000);
@@ -179,3 +176,2 @@ /// let narrowed = vec.focus().narrow(100..200);
     /// assert_eq!(Vector::from_iter(100..200), narrowed_vec);
-    /// # }
     /// ```
@@ -217,3 +213,2 @@ ///
     /// # use std::iter::FromIterator;
-    /// # fn main() {
     /// let vec = Vector::from_iter(0..1000);
@@ -225,3 +220,2 @@ /// let (left, right) = vec.focus().split_at(500);
     /// assert_eq!(Vector::from_iter(500..1000), right_vec);
-    /// # }
     /// ```
@@ -433,3 +427,2 @@ ///
 /// # use std::iter::FromIterator;
-/// # fn main() {
 /// let mut vec = Vector::from_iter(0..1000);
@@ -443,3 +436,2 @@ /// let focus1 = vec.focus_mut();
 /// assert_eq!(Some(&0), focus1.get(0));
-/// # }
 /// ```
@@ -454,3 +446,2 @@ ///
 /// # use std::iter::FromIterator;
-/// # fn main() {
 /// let mut vec = Vector::from_iter(0..1000);
@@ -461,3 +452,2 @@ /// let focus = vec.focus_mut();
 /// assert_eq!(Some(&500), right.get(0));
-/// # }
 /// ```
@@ -472,3 +462,2 @@ ///
 /// # use std::iter::FromIterator;
-/// # fn main() {
 /// let mut vec = Vector::from_iter(0..1000);
@@ -483,3 +472,2 @@ /// let (left, right) = {
 /// assert_eq!(Some(&0), left.get(0));
-/// # }
 /// ```
@@ -493,5 +481,5 @@ ///
     #[doc(hidden)]
-    Single(&'a mut [A]),
+    Single(RRBPool<A>, &'a mut [A]),
     #[doc(hidden)]
-    Full(TreeFocusMut<'a, A>),
+    Full(RRBPool<A>, TreeFocusMut<'a, A>),
 }
@@ -506,5 +494,8 @@
         match vector {
-            Vector::Inline(chunk) => FocusMut::Single(chunk),
-            Vector::Single(chunk) => FocusMut::Single(Ref::make_mut(chunk).as_mut_slice()),
-            Vector::Full(tree) => FocusMut::Full(TreeFocusMut::new(tree)),
+            Vector::Inline(pool, chunk) => FocusMut::Single(pool.clone(), chunk),
+            Vector::Single(pool, chunk) => FocusMut::Single(
+                pool.clone(),
+                PoolRef::make_mut(&pool.value_pool, chunk).as_mut_slice(),
+            ),
+            Vector::Full(pool, tree) => FocusMut::Full(pool.clone(), TreeFocusMut::new(tree)),
         }
@@ -516,4 +507,4 @@ }
         match self {
-            FocusMut::Single(chunk) => chunk.len(),
-            FocusMut::Full(tree) => tree.len(),
+            FocusMut::Single(_, chunk) => chunk.len(),
+            FocusMut::Full(_, tree) => tree.len(),
         }
@@ -535,4 +526,4 @@ }
         match self {
-            FocusMut::Single(chunk) => chunk.get_mut(index),
-            FocusMut::Full(tree) => tree.get(index),
+            FocusMut::Single(_, chunk) => chunk.get_mut(index),
+            FocusMut::Full(pool, tree) => tree.get(pool, index),
         }
@@ -592,7 +583,5 @@ }
     /// # use std::iter::FromIterator;
-    /// # fn main() {
     /// let mut vec = vector![1, 2, 3, 4, 5];
     /// vec.focus_mut().pair(1, 3, |a, b| *a += *b);
     /// assert_eq!(vector![1, 6, 3, 4, 5], vec);
-    /// # }
     /// ```
@@ -625,7 +614,5 @@ #[allow(unsafe_code)]
     /// # use std::iter::FromIterator;
-    /// # fn main() {
     /// let mut vec = vector![1, 2, 3, 4, 5];
     /// vec.focus_mut().triplet(0, 2, 4, |a, b, c| *a += *b + *c);
     /// assert_eq!(vector![9, 2, 3, 4, 5], vec);
-    /// # }
     /// ```
@@ -656,5 +643,5 @@ #[allow(unsafe_code)]
         match self {
-            FocusMut::Single(chunk) => (0..len, chunk),
-            FocusMut::Full(tree) => {
-                let (range, chunk) = tree.get_chunk(index);
+            FocusMut::Single(_, chunk) => (0..len, chunk),
+            FocusMut::Full(pool, tree) => {
+                let (range, chunk) = tree.get_chunk(pool, index);
                 (range, chunk)
@@ -678,3 +665,2 @@ }
     /// # use std::iter::FromIterator;
-    /// # fn main() {
     /// let mut vec = Vector::from_iter(0..1000);
@@ -684,3 +670,2 @@ /// let narrowed = vec.focus_mut().narrow(100..200);
     /// assert_eq!(Vector::from_iter(100..200), narrowed_vec);
-    /// # }
     /// ```
@@ -699,4 +684,4 @@ ///
         match self {
-            FocusMut::Single(chunk) => FocusMut::Single(&mut chunk[r]),
-            FocusMut::Full(tree) => FocusMut::Full(tree.narrow(r)),
+            FocusMut::Single(pool, chunk) => FocusMut::Single(pool, &mut chunk[r]),
+            FocusMut::Full(pool, tree) => FocusMut::Full(pool, tree.narrow(r)),
         }
@@ -723,3 +708,2 @@ }
     /// # use std::iter::FromIterator;
-    /// # fn main() {
     /// let mut vec = Vector::from_iter(0..1000);
@@ -738,3 +722,2 @@ /// {
     /// assert_eq!(expected, vec);
-    /// # }
     /// ```
@@ -744,2 +727,3 @@ ///
     /// [Vector::split_at]: enum.Vector.html#method.split_at
+    #[allow(clippy::redundant_clone)]
     pub fn split_at(self, index: usize) -> (Self, Self) {
@@ -750,9 +734,15 @@ if index > self.len() {
         match self {
-            FocusMut::Single(chunk) => {
+            FocusMut::Single(pool, chunk) => {
                 let (left, right) = chunk.split_at_mut(index);
-                (FocusMut::Single(left), FocusMut::Single(right))
+                (
+                    FocusMut::Single(pool.clone(), left),
+                    FocusMut::Single(pool, right),
+                )
             }
-            FocusMut::Full(tree) => {
+            FocusMut::Full(pool, tree) => {
                 let (left, right) = tree.split_at(index);
-                (FocusMut::Full(left), FocusMut::Full(right))
+                (
+                    FocusMut::Full(pool.clone(), left),
+                    FocusMut::Full(pool, right),
+                )
             }
@@ -765,4 +755,4 @@ }
         match self {
-            FocusMut::Single(chunk) => Focus::Single(chunk),
-            FocusMut::Full(mut tree) => Focus::Full(TreeFocus {
+            FocusMut::Single(_, chunk) => Focus::Single(chunk),
+            FocusMut::Full(_, mut tree) => Focus::Full(TreeFocus {
                 tree: {
@@ -875,3 +865,3 @@ let t = tree.tree.lock().unwrap();
 
-    fn set_focus(&mut self, index: usize) {
+    fn set_focus(&mut self, pool: &RRBPool<A>, index: usize) {
         let mut tree = self
@@ -885,8 +875,12 @@ .tree
                 self.target_range = 0..outer_len;
-                self.target_ptr
-                    .store(Ref::make_mut(&mut tree.outer_f), Ordering::Relaxed);
+                self.target_ptr.store(
+                    PoolRef::make_mut(&pool.value_pool, &mut tree.outer_f),
+                    Ordering::Relaxed,
+                );
             } else {
                 self.target_range = outer_len..self.middle_range.start;
-                self.target_ptr
-                    .store(Ref::make_mut(&mut tree.inner_f), Ordering::Relaxed);
+                self.target_ptr.store(
+                    PoolRef::make_mut(&pool.value_pool, &mut tree.inner_f),
+                    Ordering::Relaxed,
+                );
             }
@@ -897,8 +891,12 @@ } else if index >= self.middle_range.end {
                 self.target_range = self.middle_range.end..outer_start;
-                self.target_ptr
-                    .store(Ref::make_mut(&mut tree.inner_b), Ordering::Relaxed);
+                self.target_ptr.store(
+                    PoolRef::make_mut(&pool.value_pool, &mut tree.inner_b),
+                    Ordering::Relaxed,
+                );
             } else {
                 self.target_range = outer_start..tree.length;
-                self.target_ptr
-                    .store(Ref::make_mut(&mut tree.outer_b), Ordering::Relaxed);
+                self.target_ptr.store(
+                    PoolRef::make_mut(&pool.value_pool, &mut tree.outer_b),
+                    Ordering::Relaxed,
+                );
             }
@@ -909,3 +907,3 @@ } else {
             let middle = Ref::make_mut(&mut tree.middle);
-            let (range, ptr) = middle.lookup_chunk_mut(level, 0, tree_index);
+            let (range, ptr) = middle.lookup_chunk_mut(pool, level, 0, tree_index);
             self.target_range =
@@ -922,3 +920,3 @@ (range.start + self.middle_range.start)..(range.end + self.middle_range.start);
 
-    pub fn get(&mut self, index: usize) -> Option<&mut A> {
+    pub fn get(&mut self, pool: &RRBPool<A>, index: usize) -> Option<&mut A> {
         if index >= self.len() {
@@ -929,3 +927,3 @@ return None;
         if !contains(&self.target_range, &phys_index) {
-            self.set_focus(phys_index);
+            self.set_focus(pool, phys_index);
         }
@@ -936,6 +934,6 @@ let target_phys_index = phys_index - self.target_range.start;
 
-    pub fn get_chunk(&mut self, index: usize) -> (Range<usize>, &mut [A]) {
+    pub fn get_chunk(&mut self, pool: &RRBPool<A>, index: usize) -> (Range<usize>, &mut [A]) {
         let phys_index = self.physical_index(index);
         if !contains(&self.target_range, &phys_index) {
-            self.set_focus(phys_index);
+            self.set_focus(pool, phys_index);
         }
@@ -942,0 +940,0 @@ let mut left = 0;

No alert changes

No metric changes