Import managed 0.8.0 crate am: e4b5ebd616 am: 90b5fa2880 am: 6a71495997 am: 7084400949

Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/managed/+/1629961

MUST ONLY BE SUBMITTED BY AUTOMERGER

Change-Id: I0b45587cb5a5e44587250ce8d290169cb4563949

18 files changed, 2029 insertions, 0 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
new file mode 100644
index 0000000..8c2a0dd
--- /dev/null
+++ b/.cargo_vcs_info.json
@@ -0,0 +1,5 @@
+{
+  "git": {
+    "sha1": "eb8a2624bb210c42ef6e644b92b083e1309c7f77"
+  }
+}
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..2cbb12a
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,4 @@
+target
+Cargo.lock
+*.gcno
+*.gcda
diff --git a/.travis.yml b/.travis.yml
new file mode 100644
index 0000000..d636d88
--- /dev/null
+++ b/.travis.yml
@@ -0,0 +1,27 @@
+language: rust
+matrix:
+  include:
+    - rust: stable
+      env: FEATURES=''
+    - rust: stable
+      env: FEATURES='std'
+    - rust: nightly
+      env: FEATURES=''
+    - rust: nightly
+      env: FEATURES='std'
+    - rust: nightly
+      env: FEATURES='alloc'
+    - rust: nightly
+      env: FEATURES='map'
+    - rust: nightly
+      env: FEATURES='map alloc'
+    - rust: nightly
+      env: FEATURES='map std'
+script:
+   - cargo build --no-default-features --features "$FEATURES"
+notifications:
+  irc:
+    channels:
+      - "chat.freenode.net#m-labs"
+    use_notice: true
+    skip_join: true
diff --git a/Android.bp b/Android.bp
new file mode 100644
index 0000000..2ce4a1b
--- /dev/null
+++ b/Android.bp
@@ -0,0 +1,48 @@
+// This file is generated by cargo2android.py --run --device --tests --dependencies --no-subdir.
+// Do not modify this file as changes will be overridden on upgrade.
+
+rust_library {
+    name: "libmanaged",
+    host_supported: true,
+    crate_name: "managed",
+    srcs: ["src/lib.rs"],
+    edition: "2015",
+    apex_available: [
+        "//apex_available:platform",
+        "com.android.virt",
+    ],
+    features: [
+        "default",
+        "std",
+    ],
+}
+
+rust_defaults {
+    name: "managed_defaults",
+    crate_name: "managed",
+    srcs: ["src/lib.rs"],
+    test_suites: ["general-tests"],
+    auto_gen_config: true,
+    edition: "2015",
+    features: [
+        "default",
+        "std",
+    ],
+    flags: [
+        "-C debug-assertions=on",
+        "-C opt-level=1",
+    ],
+}
+
+rust_test_host {
+    name: "managed_host_test_src_lib",
+    defaults: ["managed_defaults"],
+    test_options: {
+        unit_test: true,
+    },
+}
+
+rust_test {
+    name: "managed_device_test_src_lib",
+    defaults: ["managed_defaults"],
+}
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..b0d87d6
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,33 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# When uploading crates to the registry Cargo will automatically
+# "normalize" Cargo.toml files for maximal compatibility
+# with all versions of Cargo and also rewrite `path` dependencies
+# to registry (e.g., crates.io) dependencies
+#
+# If you believe there's an error in this file please file an
+# issue against the rust-lang/cargo repository. If you're
+# editing this file be aware that the upstream Cargo.toml
+# will likely look very different (and much more reasonable)
+
+[package]
+name = "managed"
+version = "0.8.0"
+authors = ["whitequark <whitequark@whitequark.org>"]
+description = "An interface for logically owning objects, whether or not heap allocation is available."
+homepage = "https://github.com/m-labs/rust-managed"
+documentation = "https://docs.rs/managed/"
+readme = "README.md"
+keywords = ["ownership"]
+categories = ["embedded"]
+license = "0BSD"
+repository = "https://github.com/m-labs/rust-managed.git"
+[profile.test]
+opt-level = 1
+codegen-units = 1
+
+[features]
+alloc = []
+default = ["std"]
+map = []
+std = []
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
new file mode 100644
index 0000000..f649a2f
--- /dev/null
+++ b/Cargo.toml.orig
@@ -0,0 +1,23 @@
+[package]
+name = "managed"
+version = "0.8.0"
+authors = ["whitequark <whitequark@whitequark.org>"]
+description = "An interface for logically owning objects, whether or not heap allocation is available."
+documentation = "https://docs.rs/managed/"
+homepage = "https://github.com/m-labs/rust-managed"
+repository = "https://github.com/m-labs/rust-managed.git"
+readme = "README.md"
+keywords = ["ownership"]
+categories = ["embedded"]
+license = "0BSD"
+
+[features]
+std = []
+alloc = []
+default = ["std"]
+# Unstable features
+map = []
+
+[profile.test]
+opt-level = 1
+codegen-units = 1
diff --git a/LICENSE b/LICENSE
new file mode 120000
index 0000000..26f20b7
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1 @@
+LICENSE-0BSD.txt
\ No newline at end of file
diff --git a/LICENSE-0BSD.txt b/LICENSE-0BSD.txt
new file mode 100644
index 0000000..dbf1d91
--- /dev/null
+++ b/LICENSE-0BSD.txt
@@ -0,0 +1,12 @@
+Copyright (C) 2017 whitequark@whitequark.org
+
+Permission to use, copy, modify, and/or distribute this software for
+any purpose with or without fee is hereby granted.
+
+THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
+AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
+OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
diff --git a/METADATA b/METADATA
new file mode 100644
index 0000000..5fafde8
--- /dev/null
+++ b/METADATA
@@ -0,0 +1,19 @@
+name: "managed"
+description: "An interface for logically owning objects, whether or not heap allocation is available."
+third_party {
+  url {
+    type: HOMEPAGE
+    value: "https://crates.io/crates/managed"
+  }
+  url {
+    type: ARCHIVE
+    value: "https://static.crates.io/crates/managed/managed-0.8.0.crate"
+  }
+  version: "0.8.0"
+  license_type: UNENCUMBERED
+  last_upgrade_date {
+    year: 2021
+    month: 2
+    day: 28
+  }
+}
diff --git a/MODULE_LICENSE_0BSD b/MODULE_LICENSE_0BSD
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/MODULE_LICENSE_0BSD
diff --git a/OWNERS b/OWNERS
new file mode 100644
index 0000000..46fc303
--- /dev/null
+++ b/OWNERS
@@ -0,0 +1 @@
+include platform/prebuilts/rust:/OWNERS
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..007ec20
--- /dev/null
+++ b/README.md
@@ -0,0 +1,125 @@
+Managed
+=======
+
+_managed_ is a library that provides a way to logically own objects, whether or not
+heap allocation is available. It works with rustc 1.26 or later.
+
+Motivation
+----------
+
+The _managed_ library exists at the intersection of three concepts: _heap-less environments_,
+_collections_ and _generic code_. Consider this struct representing a network interface:
+
+```rust
+pub struct Interface<'a, 'b: 'a,
+    DeviceT:        Device,
+    ProtocolAddrsT: BorrowMut<[IpAddress]>,
+    SocketsT:       BorrowMut<[Socket<'a, 'b>]>
+> {
+    device:         DeviceT,
+    hardware_addr:  EthernetAddress,
+    protocol_addrs: ProtocolAddrsT,
+    sockets:        SocketsT,
+    phantom:        PhantomData<Socket<'a, 'b>>
+}
+```
+
+There are three things the struct `Interface` is parameterized over:
+  * an object implementing the trait `DeviceT`, which it owns;
+  * a slice of `IPAddress`es, which it either owns or borrows mutably;
+  * a slice of `Socket`s, which it either owns or borrows mutably, and which further either
+    own or borrow some memory.
+
+The motivation for using `BorrowMut` is that in environments with heap, the struct ought to
+own a `Vec`; on the other hand, without heap there is neither `Vec` nor `Box`, and it is only
+possible to use a `&mut`. Both of these implement BorrowMut.
+
+Note that owning a `BorrowMut` in this way does not hide the concrete type inside `BorrowMut`;
+if the slice is backed by a `Vec` then the `Vec` may still be resized by external code,
+although not the implementation of `Interface`.
+
+In isolation, this struct is easy to use. However, when combined with another codebase, perhaps
+embedded in a scheduler, problems arise. The type parameters have to go somewhere! There
+are two choices:
+  * either the type parameters, whole lot of them, infect the scheduler and push ownership
+    even higher in the call stack (self-mutably-borrowing structs are not usable in safe Rust,
+    so the scheduler could not easily own the slices);
+  * or the interface is owned as a boxed trait object, excluding heap-less systems.
+
+Clearly, both options are unsatisfying. Enter _managed_!
+
+Installation
+------------
+
+To use the _managed_ library in your project, add the following to `Cargo.toml`:
+
+```toml
+[dependencies]
+managed = "0.6"
+```
+
+The default configuration assumes a hosted environment, for ease of evaluation.
+You probably want to disable default features and configure them one by one:
+
+```toml
+[dependencies]
+managed = { version = "...", default-features = false, features = ["..."] }
+```
+
+### Feature `std`
+
+The `std` feature enables use of `Box`, `Vec`, and `BTreeMap` through a dependency
+on the `std` crate.
+
+### Feature `alloc`
+
+The `alloc` feature enables use of `Box`, `Vec`, and `BTreeMap` through a dependency
+on the `alloc` crate. It requires the use of nightly rustc.
+
+### Feature `map`
+
+The `map` feature, disabled by default, enables the `ManagedMap` enum.
+Its interface is not stable yet and is subject to change.
+It also requires the use of rustc 1.28 or later.
+
+Usage
+-----
+
+_managed_ is an interoperability crate: it does not include complex functionality but rather
+defines an interface that may be used by many downstream crates. It includes three enums:
+
+```rust
+pub enum Managed<'a, T: 'a + ?Sized> {
+    Borrowed(&'a mut T),
+    #[cfg(/* Box available */)]
+    Owned(Box<T>),
+}
+
+pub enum ManagedSlice<'a, T: 'a> {
+    Borrow(&'a mut [T]),
+    #[cfg(/* Vec available */)]
+    Owned(Vec<T>)
+}
+
+// The implementation of ManagedMap is not yet stable, beware!
+pub enum ManagedMap<'a, K: Hash + 'a, V: 'a> {
+    Borrowed(&'a mut [Option<(K, V)>]),
+    #[cfg(/* BTreeMap available */)]
+    Owned(BTreeMap<K, V>)
+}
+```
+
+The `Managed` and `ManagedSlice` enums have the `From` implementations from the corresponding
+types, and `Deref`/`DerefMut` implementations to the type `T`, as well as other helper methods,
+and `ManagedMap` is implemented using either a B-tree map or a sorted slice of key-value pairs.
+
+See the [full documentation][doc] for details.
+
+[doc]: https://docs.rs/managed/
+
+License
+-------
+
+_managed_ is distributed under the terms of 0-clause BSD license.
+
+See [LICENSE-0BSD](LICENSE-0BSD.txt) for details.
diff --git a/coverage.sh b/coverage.sh
new file mode 100755
index 0000000..03e3796
--- /dev/null
+++ b/coverage.sh
@@ -0,0 +1,17 @@
+#!/bin/bash -e
+
+cargo rustc --features map -- --test -C link-dead-code -Z profile -Z no-landing-pads
+
+LCOVOPTS=(
+  --gcov-tool llvm-gcov
+  --rc lcov_branch_coverage=1
+  --rc lcov_excl_line=assert
+)
+lcov "${LCOVOPTS[@]}" --capture --directory . --base-directory . \
+  -o target/coverage/raw.lcov
+lcov "${LCOVOPTS[@]}" --extract target/coverage/raw.lcov "$(pwd)/*" \
+  -o target/coverage/raw_crate.lcov
+
+genhtml --branch-coverage --demangle-cpp --legend \
+  -o target/coverage/ \
+  target/coverage/raw_crate.lcov
diff --git a/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..9f75f8c
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1,27 @@
+#![no_std]
+
+//! A library that provides a way to logically own objects, whether or not
+//! heap allocation is available.
+
+#[cfg(feature = "std")]
+extern crate std;
+#[cfg(all(feature = "alloc", not(feature = "std")))]
+extern crate alloc;
+
+mod object;
+mod slice;
+mod slotmap;
+#[cfg(feature = "map")]
+mod map;
+
+pub use object::Managed;
+pub use slice::ManagedSlice;
+pub use slotmap::{
+    Key as SlotKey,
+    Slot as SlotIndex,
+    SlotMap,
+};
+#[cfg(feature = "map")]
+pub use map::{ManagedMap,
+              Iter as ManagedMapIter,
+              IterMut as ManagedMapIterMut};
diff --git a/src/map.rs b/src/map.rs
new file mode 100644
index 0000000..4071230
--- /dev/null
+++ b/src/map.rs
@@ -0,0 +1,1007 @@
+use core::mem;
+use core::fmt;
+use core::slice;
+use core::borrow::Borrow;
+use core::ops::{Bound, RangeBounds};
+
+#[cfg(feature = "std")]
+use std::collections::BTreeMap;
+#[cfg(feature = "std")]
+use std::collections::btree_map::{Iter as BTreeIter, IterMut as BTreeIterMut,
+                                  Range as BTreeRange};
+#[cfg(all(feature = "alloc", not(feature = "std")))]
+use alloc::collections::btree_map::BTreeMap;
+#[cfg(all(feature = "alloc", not(feature = "std")))]
+use alloc::collections::btree_map::{Iter as BTreeIter, IterMut as BTreeIterMut,
+                                    Range as BTreeRange};
+
+/// A managed map.
+///
+/// This enum can be used to represent exclusive access to maps.
+/// In Rust, exclusive access to an object is obtained by either owning the object,
+/// or owning a mutable pointer to the object; hence, "managed".
+///
+/// The purpose of this enum is providing good ergonomics with `std` present while making
+/// it possible to avoid having a heap at all (which of course means that `std` is not present).
+/// To achieve this, the variants other than `Borrow` are only available when the corresponding
+/// feature is opted in.
+///
+/// Unlike [Managed](enum.Managed.html) and [ManagedSlice](enum.ManagedSlice.html),
+/// the managed map is implemented using a B-tree map when allocation is available,
+/// and a sorted slice of key-value pairs when it is not. Thus, algorithmic complexity
+/// of operations on it depends on the kind of map.
+///
+/// A function that requires a managed object should be generic over an `Into<ManagedMap<'a, T>>`
+/// argument; then, it will be possible to pass either a `Vec<T>`, or a `&'a mut [T]`
+/// without any conversion at the call site.
+///
+/// See also [Managed](enum.Managed.html).
+pub enum ManagedMap<'a, K: 'a, V: 'a> {
+    /// Borrowed variant.
+    Borrowed(&'a mut [Option<(K, V)>]),
+    /// Owned variant, only available with the `std` or `alloc` feature enabled.
+    #[cfg(any(feature = "std", feature = "alloc"))]
+    Owned(BTreeMap<K, V>)
+}
+
+impl<'a, K: 'a, V: 'a> fmt::Debug for ManagedMap<'a, K, V>
+        where K: fmt::Debug, V: fmt::Debug {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match self {
+            &ManagedMap::Borrowed(ref x) => write!(f, "Borrowed({:?})", x),
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &ManagedMap::Owned(ref x)    => write!(f, "Owned({:?})", x)
+        }
+    }
+}
+
+impl<'a, K: 'a, V: 'a> From<&'a mut [Option<(K, V)>]> for ManagedMap<'a, K, V> {
+    fn from(value: &'a mut [Option<(K, V)>]) -> Self {
+        ManagedMap::Borrowed(value)
+    }
+}
+
+#[cfg(any(feature = "std", feature = "alloc"))]
+impl<'a, K: 'a, V: 'a> From<BTreeMap<K, V>> for ManagedMap<'a, K, V> {
+    fn from(value: BTreeMap<K, V>) -> Self {
+        ManagedMap::Owned(value)
+    }
+}
+
+/// Like `Option`, but with `Some` values sorting first.
+#[derive(PartialEq, Eq, PartialOrd, Ord)]
+enum RevOption<T> {
+    Some(T),
+    None
+}
+
+impl<T> From<Option<T>> for RevOption<T> {
+    fn from(other: Option<T>) -> Self {
+        match other {
+            Some(x) => RevOption::Some(x),
+            None => RevOption::None
+        }
+    }
+}
+
+impl<T> Into<Option<T>> for RevOption<T> {
+    fn into(self) -> Option<T> {
+        match self {
+            RevOption::Some(x) => Some(x),
+            RevOption::None => None
+        }
+    }
+}
+
+#[derive(Debug, Clone)]
+enum RangeInner<'a, K: 'a, V: 'a> {
+    /// Borrowed variant.
+    Borrowed { slice: &'a [Option<(K, V)>], begin: usize, end: usize },
+    /// Owned variant, only available with the `std` or `alloc` feature enabled.
+    #[cfg(any(feature = "std", feature = "alloc"))]
+    Owned(BTreeRange<'a, K, V>),
+}
+
+#[derive(Debug, Clone)]
+pub struct Range<'a, K: 'a, V: 'a>(RangeInner<'a, K, V>);
+
+impl<'a, K: 'a, V: 'a> Iterator for Range<'a, K, V> {
+    type Item = (&'a K, &'a V);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        match self.0 {
+            RangeInner::Borrowed { ref slice, ref mut begin, ref end } => {
+                *begin += 1;
+                if *begin-1 >= *end {
+                    None
+                } else {
+                    match slice[*begin-1] {
+                        None => None,
+                        Some((ref k, ref v)) => Some((k, v))
+                    }
+                }
+            },
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            RangeInner::Owned(ref mut range) => range.next(),
+        }
+    }
+}
+
+impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Range<'a, K, V> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        match self.0 {
+            RangeInner::Borrowed { ref slice, ref begin, ref mut end } => {
+                if *begin >= *end {
+                    None
+                } else {
+                    *end -= 1;
+                    match slice[*end] {
+                        None => None,
+                        Some((ref k, ref v)) => Some((k, v))
+                    }
+                }
+            },
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            RangeInner::Owned(ref mut range) => range.next_back(),
+        }
+    }
+}
+
+fn binary_search_by_key_range<'a, K, V, Q: 'a, R>(slice: &[Option<(K, V)>], range: R) -> Result<(usize, usize), ()>
+    where K: Ord + Borrow<Q>, Q: Ord + ?Sized, R: RangeBounds<Q>
+{
+    if slice.len() == 0 {
+        return Err(())
+    }
+    let (mut left, mut right) = (0, slice.len() - 1);
+
+    macro_rules! key {
+        ( $e:expr) => { $e.as_ref().map(|&(ref key, _)| key.borrow()) }
+    }
+
+    // We cannot use slice.binary_search_by_key instead of each of the
+    // two loops here, because we need the left-most match (for begin) and
+    // the right-most match (for end), and the stdlib does not provide
+    // any of these guarantees.
+
+    // Find the beginning
+    let begin;
+    if let Bound::Unbounded = range.start_bound() {
+        begin = 0;
+    } else {
+        macro_rules! is_before_range {
+            ( $item: expr) => {
+                match &range.start_bound() {
+                    Bound::Included(ref key_begin) => $item < Some(key_begin.borrow()),
+                    Bound::Excluded(ref key_begin) => $item <= Some(key_begin.borrow()),
+                    Bound::Unbounded => unreachable!()
+                }
+            }
+        };
+        while left < right {
+            let middle = left + (right - left) / 2;
+            if is_before_range!(key!(slice[middle])) {
+                left = middle + 1;
+            } else if middle > 0 && !is_before_range!(key!(slice[middle - 1])) {
+                right = middle - 1;
+            } else {
+                left = middle;
+                break
+            }
+        }
+        if left == slice.len() || is_before_range!(key!(slice[left])) {
+            return Err(())
+        }
+        begin = left
+    };
+
+    // Find the ending
+    let end;
+    if let Bound::Unbounded = range.end_bound() {
+        end = slice.len()
+    } else {
+        macro_rules! is_after_range {
+            ( $item:expr ) => {
+                match &range.end_bound() {
+                    Bound::Included(ref key_end) => $item > Some(key_end.borrow()),
+                    Bound::Excluded(ref key_end) => $item >= Some(key_end.borrow()),
+                    Bound::Unbounded => unreachable!()
+                }
+            }
+        };
+        right = slice.len(); // no need to reset left
+        while left < right {
+            let middle = left + (right - left + 1) / 2;
+            if is_after_range!(key!(slice[middle - 1])) {
+                right = middle - 1;
+            } else if middle < slice.len() && !is_after_range!(key!(slice[middle])) {
+                left = middle + 1;
+            } else {
+                right = middle;
+                break
+            }
+        }
+        if right == 0 || is_after_range!(key!(slice[right - 1])) {
+            return Err(())
+        }
+        end = right
+    };
+
+    Ok((begin, end))
+}
+
+fn binary_search_by_key<K, V, Q>(slice: &[Option<(K, V)>], key: &Q) -> Result<usize, usize>
+    where K: Ord + Borrow<Q>, Q: Ord + ?Sized
+{
+    slice.binary_search_by_key(&RevOption::Some(key), |entry| {
+        entry.as_ref().map(|&(ref key, _)| key.borrow()).into()
+    })
+}
+
+fn pair_by_key<'a, K, Q, V>(slice: &'a [Option<(K, V)>], key: &Q) ->
+                           Result<&'a (K, V), usize>
+    where K: Ord + Borrow<Q>, Q: Ord + ?Sized
+{
+    binary_search_by_key(slice, key).map(move |idx| slice[idx].as_ref().unwrap())
+}
+
+fn pair_mut_by_key<'a, K, Q, V>(slice: &'a mut [Option<(K, V)>], key: &Q) ->
+                               Result<&'a mut (K, V), usize>
+    where K: Ord + Borrow<Q>, Q: Ord + ?Sized
+{
+    binary_search_by_key(slice, key).map(move |idx| slice[idx].as_mut().unwrap())
+}
+
+impl<'a, K: Ord + 'a, V: 'a> ManagedMap<'a, K, V> {
+    pub fn clear(&mut self) {
+        match self {
+            &mut ManagedMap::Borrowed(ref mut pairs) => {
+                for item in pairs.iter_mut() {
+                    *item = None
+                }
+            },
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &mut ManagedMap::Owned(ref mut map) => map.clear()
+        }
+    }
+
+    pub fn get<Q>(&self, key: &Q) -> Option<&V>
+        where K: Borrow<Q>, Q: Ord + ?Sized
+    {
+        match self {
+            &ManagedMap::Borrowed(ref pairs) => {
+                match pair_by_key(pairs, key.borrow()) {
+                    Ok(&(_, ref value)) => Some(value),
+                    Err(_) => None
+                }
+            },
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &ManagedMap::Owned(ref map) => map.get(key)
+        }
+    }
+
+    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
+        where K: Borrow<Q>, Q: Ord + ?Sized
+    {
+        match self {
+            &mut ManagedMap::Borrowed(ref mut pairs) => {
+                match pair_mut_by_key(pairs, key.borrow()) {
+                    Ok(&mut (_, ref mut value)) => Some(value),
+                    Err(_) => None
+                }
+            },
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &mut ManagedMap::Owned(ref mut map) => map.get_mut(key)
+        }
+    }
+
+    pub fn range<'b, 'c, Q: 'c, R>(&'b self, range: R) -> Range<'a, K, V>
+            where K: Borrow<Q>, Q: Ord + ?Sized, R: RangeBounds<Q>, 'b: 'a
+    {
+        match self {
+            &ManagedMap::Borrowed(ref pairs) => {
+                match binary_search_by_key_range(&pairs[0..self.len()], range) {
+                    Ok((begin, end)) => Range(RangeInner::Borrowed {
+                        slice: &pairs[begin..end], begin: 0, end: end-begin }),
+                    Err(()) => Range(RangeInner::Borrowed {
+                        slice: &[], begin: 0, end: 0 }),
+                }
+            },
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &ManagedMap::Owned(ref map) => {
+                Range(RangeInner::Owned(map.range(range)))
+            },
+        }
+    }
+
+    pub fn insert(&mut self, key: K, new_value: V) -> Result<Option<V>, (K, V)> {
+        match self {
+            &mut ManagedMap::Borrowed(ref mut pairs) if pairs.len() < 1 =>
+                Err((key, new_value)), // no space at all
+            &mut ManagedMap::Borrowed(ref mut pairs) => {
+                match binary_search_by_key(pairs, &key) {
+                    Err(_) if pairs[pairs.len() - 1].is_some() =>
+                        Err((key, new_value)), // full
+                    Err(idx) => {
+                        let rotate_by = pairs.len() - idx - 1;
+                        pairs[idx..].rotate_left(rotate_by);
+                        assert!(pairs[idx].is_none(), "broken invariant");
+                        pairs[idx] = Some((key, new_value));
+                        Ok(None)
+                    }
+                    Ok(idx) => {
+                        let mut swap_pair = Some((key, new_value));
+                        mem::swap(&mut pairs[idx], &mut swap_pair);
+                        let (_key, value) = swap_pair.expect("broken invariant");
+                        Ok(Some(value))
+                    }
+                }
+            },
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &mut ManagedMap::Owned(ref mut map) => Ok(map.insert(key, new_value))
+        }
+    }
+
+    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
+        where K: Borrow<Q>, Q: Ord + ?Sized
+    {
+        match self {
+            &mut ManagedMap::Borrowed(ref mut pairs) => {
+                match binary_search_by_key(pairs, key) {
+                    Ok(idx) => {
+                        let (_key, value) = pairs[idx].take().expect("broken invariant");
+                        pairs[idx..].rotate_left(1);
+                        Some(value)
+                    }
+                    Err(_) => None
+                }
+            },
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &mut ManagedMap::Owned(ref mut map) => map.remove(key)
+        }
+    }
+
+    /// ManagedMap contains no elements?
+    pub fn is_empty(&self) -> bool {
+        match self {
+            &ManagedMap::Borrowed(ref pairs) =>
+                pairs.iter().all(|item| item.is_none()),
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &ManagedMap::Owned(ref map) =>
+                map.is_empty()
+        }
+    }
+
+    /// Returns the number of elements in the ManagedMap.
+    pub fn len(&self) -> usize {
+        match self {
+            &ManagedMap::Borrowed(ref pairs) =>
+                pairs.iter()
+                .take_while(|item| item.is_some())
+                .count(),
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &ManagedMap::Owned(ref map) =>
+                map.len()
+        }
+    }
+
+    pub fn iter(&self) -> Iter<K, V> {
+        match self {
+            &ManagedMap::Borrowed(ref pairs) =>
+                Iter::Borrowed(pairs.iter()),
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &ManagedMap::Owned(ref map) =>
+                Iter::Owned(map.iter()),
+        }
+    }
+
+    pub fn iter_mut(&mut self) -> IterMut<K, V> {
+        match self {
+            &mut ManagedMap::Borrowed(ref mut pairs) =>
+                IterMut::Borrowed(pairs.iter_mut()),
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &mut ManagedMap::Owned(ref mut map) =>
+                IterMut::Owned(map.iter_mut()),
+        }
+    }
+}
+
+pub enum Iter<'a, K: 'a, V: 'a> {
+    /// Borrowed variant.
+    Borrowed(slice::Iter<'a, Option<(K, V)>>),
+    /// Owned variant, only available with the `std` or `alloc` feature enabled.
+    #[cfg(any(feature = "std", feature = "alloc"))]
+    Owned(BTreeIter<'a, K, V>),
+}
+
+impl<'a, K: Ord + 'a, V: 'a> Iterator for Iter<'a, K, V> {
+    type Item = (&'a K, &'a V);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        match self {
+            &mut Iter::Borrowed(ref mut iter) =>
+                match iter.next() {
+                    Some(&Some((ref k, ref v))) => Some((&k, &v)),
+                    Some(&None) => None,
+                    None => None,
+                },
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &mut Iter::Owned(ref mut iter) =>
+                iter.next(),
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        match self {
+            &Iter::Borrowed(ref iter) => {
+                let len = iter.clone()
+                    .take_while(|item| item.is_some())
+                    .count();
+                (len, Some(len))
+            },
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &Iter::Owned(ref iter) =>
+                iter.size_hint(),
+        }
+    }
+}
+
+pub enum IterMut<'a, K: 'a, V: 'a> {
+    /// Borrowed variant.
+    Borrowed(slice::IterMut<'a, Option<(K, V)>>),
+    /// Owned variant, only available with the `std` or `alloc` feature enabled.
+    #[cfg(any(feature = "std", feature = "alloc"))]
+    Owned(BTreeIterMut<'a, K, V>),
+}
+
+impl<'a, K: Ord + 'a, V: 'a> Iterator for IterMut<'a, K, V> {
+    type Item = (&'a K, &'a mut V);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        match self {
+            &mut IterMut::Borrowed(ref mut iter) =>
+                match iter.next() {
+                    Some(&mut Some((ref k, ref mut v))) => Some((&k, v)),
+                    Some(&mut None) => None,
+                    None => None,
+                },
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &mut IterMut::Owned(ref mut iter) =>
+                iter.next(),
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        match self {
+            &IterMut::Borrowed(ref iter) => {
+                let (_, upper) = iter.size_hint();
+                (0, upper)
+            },
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &IterMut::Owned(ref iter) =>
+                iter.size_hint(),
+        }
+    }
+}
+
+// LCOV_EXCL_START
+#[cfg(test)]
+mod test {
+    use super::ManagedMap;
+    use core::ops::Bound::*;
+
+    fn all_pairs_empty() -> [Option<(&'static str, u32)>; 4] {
+        [None; 4]
+    }
+
+    fn one_pair_full() -> [Option<(&'static str, u32)>; 4] {
+        [Some(("a", 1)), None, None, None]
+    }
+
+    fn all_pairs_full() -> [Option<(&'static str, u32)>; 4] {
+        [Some(("a", 1)), Some(("b", 2)), Some(("c", 3)), Some(("d", 4))]
+    }
+
+    fn unwrap<'a, K, V>(map: &'a ManagedMap<'a, K, V>) -> &'a [Option<(K, V)>] {
+        match map {
+            &ManagedMap::Borrowed(ref map) => map,
+            _ => unreachable!()
+        }
+    }
+
+    #[test]
+    fn test_clear() {
+        let mut pairs = all_pairs_full();
+        let mut map = ManagedMap::Borrowed(&mut pairs);
+        map.clear();
+        assert!(map.is_empty());
+        assert_eq!(map.len(), 0);
+        assert_eq!(unwrap(&map), all_pairs_empty());
+    }
+
+    #[test]
+    fn test_get_some() {
+        let mut pairs = all_pairs_full();
+        let map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.len(), 4);
+        assert_eq!(map.get("a"), Some(&1));
+        assert_eq!(map.get("b"), Some(&2));
+        assert_eq!(map.get("c"), Some(&3));
+        assert_eq!(map.get("d"), Some(&4));
+    }
+
+    #[test]
+    fn test_get_some_one_pair() {
+        let mut pairs = one_pair_full();
+        let map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.len(), 1);
+        assert_eq!(map.get("a"), Some(&1));
+    }
+
+    #[test]
+    fn test_get_none_full() {
+        let mut pairs = all_pairs_full();
+        let map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.len(), 4);
+        assert!(!map.is_empty());
+        assert_eq!(map.get("q"), None);
+        assert_eq!(map.get("0"), None);
+    }
+
+    #[test]
+    fn test_get_none() {
+        let mut pairs = one_pair_full();
+        let map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.len(), 1);
+        assert!(!map.is_empty());
+        assert_eq!(map.get("0"), None);
+        assert_eq!(map.get("q"), None);
+    }
+
+    #[test]
+    fn test_get_none_empty() {
+        let mut pairs = all_pairs_empty();
+        let map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.len(), 0);
+        assert!(map.is_empty());
+        assert_eq!(map.get("q"), None);
+    }
+
+    #[test]
+    fn test_range_full_unbounded() {
+        let mut pairs = all_pairs_full();
+        let map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.len(), 4);
+
+        let mut range = map.range("a"..);
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), Some((&"d", &4)));
+        assert_eq!(range.next(), None);
+        assert_eq!(range.next_back(), None);
+
+        let mut range = map.range("a"..);
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next_back(), Some((&"d", &4)));
+        assert_eq!(range.next_back(), Some((&"c", &3)));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next_back(), None);
+        assert_eq!(range.next(), None);
+
+        let mut range = map.range("b"..);
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), Some((&"d", &4)));
+        assert_eq!(range.next(), None);
+        assert_eq!(range.next_back(), None);
+
+        let mut range = map.range("d"..);
+        assert_eq!(range.next(), Some((&"d", &4)));
+        assert_eq!(range.next(), None);
+        assert_eq!(range.next_back(), None);
+
+        let mut range = map.range(.."e");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), Some((&"d", &4)));
+        assert_eq!(range.next(), None);
+        assert_eq!(range.next_back(), None);
+
+        let mut range = map.range(.."d");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), None);
+        assert_eq!(range.next_back(), None);
+
+        let mut range = map.range(.."b");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), None);
+        assert_eq!(range.next_back(), None);
+
+        let mut range = map.range(.."a");
+        assert_eq!(range.next(), None);
+        assert_eq!(range.next_back(), None);
+
+        let mut range = map.range::<&str, _>(..);
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), Some((&"d", &4)));
+        assert_eq!(range.next(), None);
+        assert_eq!(range.next_back(), None);
+    }
+
+    #[test]
+    fn test_range_full_exclude_left() {
+        let mut pairs = all_pairs_full();
+        let map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.len(), 4);
+
+        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("a")));
+        assert_eq!(range.next(), None);
+        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("b")));
+        assert_eq!(range.next(), None);
+        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("c")));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("d")));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("e")));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), Some((&"d", &4)));
+        assert_eq!(range.next(), None);
+    }
+
+    #[test]
+    fn test_range_full_include_right() {
+        let mut pairs = all_pairs_full();
+        let map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.len(), 4);
+
+        let mut range = map.range::<&str, _>((Included("b"), Included("a")));
+        assert_eq!(range.next(), None);
+        let mut range = map.range::<&str, _>((Included("b"), Included("b")));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range::<&str, _>((Included("b"), Included("c")));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range::<&str, _>((Included("b"), Included("d")));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), Some((&"d", &4)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range::<&str, _>((Included("b"), Included("e")));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), Some((&"d", &4)));
+        assert_eq!(range.next(), None);
+
+        let mut range = map.range::<&str, _>((Included("b"), Included("a")));
+        assert_eq!(range.next_back(), None);
+        let mut range = map.range::<&str, _>((Included("b"), Included("b")));
+        assert_eq!(range.next_back(), Some((&"b", &2)));
+        assert_eq!(range.next_back(), None);
+        let mut range = map.range::<&str, _>((Included("b"), Included("c")));
+        assert_eq!(range.next_back(), Some((&"c", &3)));
+        assert_eq!(range.next_back(), Some((&"b", &2)));
+        assert_eq!(range.next_back(), None);
+        let mut range = map.range::<&str, _>((Included("b"), Included("d")));
+        assert_eq!(range.next_back(), Some((&"d", &4)));
+        assert_eq!(range.next_back(), Some((&"c", &3)));
+        assert_eq!(range.next_back(), Some((&"b", &2)));
+        assert_eq!(range.next_back(), None);
+        let mut range = map.range::<&str, _>((Included("b"), Included("e")));
+        assert_eq!(range.next_back(), Some((&"d", &4)));
+        assert_eq!(range.next_back(), Some((&"c", &3)));
+        assert_eq!(range.next_back(), Some((&"b", &2)));
+        assert_eq!(range.next_back(), None);
+    }
+
+    #[test]
+    fn test_range_full() {
+        let mut pairs = all_pairs_full();
+        let map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.len(), 4);
+
+        let mut range = map.range("0".."a");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("0".."b");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range("0".."c");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range("0".."d");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range("0".."e");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), Some((&"d", &4)));
+        assert_eq!(range.next(), None);
+
+        let mut range = map.range("a".."a");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("a".."b");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range("a".."c");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range("a".."d");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range("a".."e");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), Some((&"d", &4)));
+        assert_eq!(range.next(), None);
+
+        let mut range = map.range("b".."a");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("b".."b");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("b".."c");
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range("b".."d");
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range("b".."e");
+        assert_eq!(range.next(), Some((&"b", &2)));
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), Some((&"d", &4)));
+        assert_eq!(range.next(), None);
+
+        let mut range = map.range("c".."a");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("c".."b");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("c".."c");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("c".."d");
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range("c".."e");
+        assert_eq!(range.next(), Some((&"c", &3)));
+        assert_eq!(range.next(), Some((&"d", &4)));
+        assert_eq!(range.next(), None);
+
+        let mut range = map.range("d".."a");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("d".."b");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("d".."c");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("d".."d");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("d".."e");
+        assert_eq!(range.next(), Some((&"d", &4)));
+        assert_eq!(range.next(), None);
+
+        let mut range = map.range("e".."a");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("e".."b");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("e".."c");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("e".."d");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("e".."e");
+        assert_eq!(range.next(), None);
+    }
+
+    #[test]
+    fn test_range_one_pair() {
+        let mut pairs = one_pair_full();
+        let map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.len(), 1);
+
+        let mut range = map.range("0".."a");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("0".."b");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range("0".."c");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), None);
+
+        let mut range = map.range("a".."a");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("a".."b");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), None);
+        let mut range = map.range("a".."c");
+        assert_eq!(range.next(), Some((&"a", &1)));
+        assert_eq!(range.next(), None);
+
+        let mut range = map.range("b".."a");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("b".."b");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("b".."c");
+        assert_eq!(range.next(), None);
+    }
+
+    #[test]
+    fn test_range_empty() {
+        let mut pairs = all_pairs_empty();
+        let map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.len(), 0);
+
+        let mut range = map.range("b".."a");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("b".."b");
+        assert_eq!(range.next(), None);
+        let mut range = map.range("b".."c");
+        assert_eq!(range.next(), None);
+    }
+
+    #[test]
+    fn test_get_mut_some() {
+        let mut pairs = all_pairs_full();
+        let mut map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.len(), 4);
+        assert!(!map.is_empty());
+        assert_eq!(map.get_mut("a"), Some(&mut 1));
+        assert_eq!(map.get_mut("b"), Some(&mut 2));
+        assert_eq!(map.get_mut("c"), Some(&mut 3));
+        assert_eq!(map.get_mut("d"), Some(&mut 4));
+    }
+
+    #[test]
+    fn test_get_mut_none() {
+        let mut pairs = one_pair_full();
+        let mut map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.get_mut("q"), None);
+    }
+
+    #[test]
+    fn test_insert_empty() {
+        let mut pairs = all_pairs_empty();
+        let mut map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.len(), 0);
+        assert!(map.is_empty());
+
+        assert_eq!(map.insert("a", 1), Ok(None));
+        assert_eq!(map.len(), 1);
+        assert!(!map.is_empty());
+        assert_eq!(unwrap(&map),       [Some(("a", 1)), None, None, None]);
+    }
+
+    #[test]
+    fn test_insert_replace() {
+        let mut pairs = all_pairs_empty();
+        let mut map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.insert("a", 1), Ok(None));
+        assert_eq!(map.insert("a", 2), Ok(Some(1)));
+        assert_eq!(map.len(), 1);
+        assert!(!map.is_empty());
+        assert_eq!(unwrap(&map),       [Some(("a", 2)), None, None, None]);
+    }
+
+    #[test]
+    fn test_insert_full() {
+        let mut pairs = all_pairs_full();
+        let mut map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.insert("q", 1), Err(("q", 1)));
+        assert_eq!(map.len(), 4);
+        assert_eq!(unwrap(&map),       all_pairs_full());
+    }
+
+    #[test]
+    fn test_insert_one() {
+        let mut pairs = one_pair_full();
+        let mut map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.insert("b", 2), Ok(None));
+        assert_eq!(unwrap(&map),       [Some(("a", 1)), Some(("b", 2)), None, None]);
+    }
+
+    #[test]
+    fn test_insert_shift() {
+        let mut pairs = one_pair_full();
+        let mut map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.insert("c", 3), Ok(None));
+        assert_eq!(map.insert("b", 2), Ok(None));
+        assert_eq!(unwrap(&map),       [Some(("a", 1)), Some(("b", 2)), Some(("c", 3)), None]);
+    }
+
+    #[test]
+    fn test_insert_no_space() {
+        // Zero-sized backing store
+        let mut map = ManagedMap::Borrowed(&mut []);
+        assert_eq!(map.insert("a", 1), Err(("a", 1)));
+    }
+
+    #[test]
+    fn test_remove_nonexistent() {
+        let mut pairs = one_pair_full();
+        let mut map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.remove("b"), None);
+        assert_eq!(map.len(), 1);
+    }
+
+    #[test]
+    fn test_remove_one() {
+        let mut pairs = all_pairs_full();
+        let mut map = ManagedMap::Borrowed(&mut pairs);
+        assert_eq!(map.remove("a"), Some(1));
+        assert_eq!(map.len(), 3);
+        assert_eq!(unwrap(&map),    [Some(("b", 2)), Some(("c", 3)), Some(("d", 4)), None]);
+    }
+
+    #[test]
+    fn test_iter_none() {
+        let mut pairs = all_pairs_empty();
+        let map = ManagedMap::Borrowed(&mut pairs);
+        let mut iter = map.iter();
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+        assert_eq!(iter.next(), None);
+    }
+
+    #[test]
+    fn test_iter_one() {
+        let mut pairs = one_pair_full();
+        let map = ManagedMap::Borrowed(&mut pairs);
+        let mut iter = map.iter();
+        assert_eq!(iter.size_hint(), (1, Some(1)));
+        assert_eq!(iter.next(), Some((&"a", &1)));
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+        assert_eq!(iter.next(), None);
+    }
+
+    #[test]
+    fn test_iter_full() {
+        let mut pairs = all_pairs_full();
+        let map = ManagedMap::Borrowed(&mut pairs);
+        let mut iter = map.iter();
+        assert_eq!(iter.size_hint(), (4, Some(4)));
+        assert_eq!(iter.next(), Some((&"a", &1)));
+        assert_eq!(iter.next(), Some((&"b", &2)));
+        assert_eq!(iter.next(), Some((&"c", &3)));
+        assert_eq!(iter.next(), Some((&"d", &4)));
+        assert_eq!(iter.next(), None);
+    }
+
+    #[test]
+    fn test_iter_mut_full() {
+        let mut pairs = all_pairs_full();
+        let mut map = ManagedMap::Borrowed(&mut pairs);
+
+        {
+            let mut iter = map.iter_mut();
+            assert_eq!(iter.size_hint(), (0, Some(4)));
+            for (_k, mut v) in &mut iter {
+                *v += 1;
+            }
+            assert_eq!(iter.size_hint(), (0, Some(0)));
+            // Scope for `iter` ends here so that it can be borrowed
+            // again with the following `iter`.
+        }
+        {
+            let mut iter = map.iter();
+            assert_eq!(iter.next(), Some((&"a", &2)));
+            assert_eq!(iter.next(), Some((&"b", &3)));
+            assert_eq!(iter.next(), Some((&"c", &4)));
+            assert_eq!(iter.next(), Some((&"d", &5)));
+            assert_eq!(iter.next(), None);
+        }
+    }
+}
diff --git a/src/object.rs b/src/object.rs
new file mode 100644
index 0000000..f7ab153
--- /dev/null
+++ b/src/object.rs
@@ -0,0 +1,90 @@
+use core::ops::{Deref, DerefMut};
+use core::fmt;
+
+#[cfg(feature = "std")]
+use std::boxed::Box;
+#[cfg(all(feature = "alloc", not(feature = "std")))]
+use alloc::boxed::Box;
+#[cfg(feature = "std")]
+use std::vec::Vec;
+#[cfg(all(feature = "alloc", not(feature = "std")))]
+use alloc::vec::Vec;
+
+/// A managed object.
+///
+/// This enum can be used to represent exclusive access to objects. In Rust, exclusive access
+/// to an object is obtained by either owning the object, or owning a mutable pointer
+/// to the object; hence, "managed".
+///
+/// The purpose of this enum is providing good ergonomics with `std` present while making
+/// it possible to avoid having a heap at all (which of course means that `std` is not present).
+/// To achieve this, the variants other than `Borrow` are only available when the corresponding
+/// feature is opted in.
+///
+/// A function that requires a managed object should be generic over an `Into<Managed<'a, T>>`
+/// argument; then, it will be possible to pass either a `Box<T>`, `Vec<T>`, or a `&'a mut T`
+/// without any conversion at the call site.
+///
+/// Note that a `Vec<T>` converted into an `Into<Managed<'a, [T]>>` gets transformed
+/// into a boxed slice, and can no longer be resized. See also
+/// [ManagedSlice](enum.ManagedSlice.html), which does not have this drawback.
+pub enum Managed<'a, T: 'a + ?Sized> {
+    /// Borrowed variant.
+    Borrowed(&'a mut T),
+    /// Owned variant, only available with the `std` or `alloc` feature enabled.
+    #[cfg(any(feature = "std", feature = "alloc"))]
+    Owned(Box<T>)
+}
+
+impl<'a, T: 'a + ?Sized> fmt::Debug for Managed<'a, T>
+        where T: fmt::Debug {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match self {
+            &Managed::Borrowed(ref x) => write!(f, "Borrowed({:?})", x),
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &Managed::Owned(ref x)    => write!(f, "Owned({:?})", x)
+        }
+    }
+}
+
+impl<'a, T: 'a + ?Sized> From<&'a mut T> for Managed<'a, T> {
+    fn from(value: &'a mut T) -> Self {
+        Managed::Borrowed(value)
+    }
+}
+
+#[cfg(any(feature = "std", feature = "alloc"))]
+impl<'a, T: ?Sized + 'a> From<Box<T>> for Managed<'a, T> {
+    fn from(value: Box<T>) -> Self {
+        Managed::Owned(value)
+    }
+}
+
+#[cfg(any(feature = "std", feature = "alloc"))]
+impl<'a, T: 'a> From<Vec<T>> for Managed<'a, [T]> {
+    fn from(value: Vec<T>) -> Self {
+        Managed::Owned(value.into_boxed_slice())
+    }
+}
+
+impl<'a, T: 'a + ?Sized> Deref for Managed<'a, T> {
+    type Target = T;
+
+    fn deref(&self) -> &Self::Target {
+        match self {
+            &Managed::Borrowed(ref value) => value,
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &Managed::Owned(ref value) => value
+        }
+    }
+}
+
+impl<'a, T: 'a + ?Sized> DerefMut for Managed<'a, T> {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        match self {
+            &mut Managed::Borrowed(ref mut value) => value,
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &mut Managed::Owned(ref mut value) => value
+        }
+    }
+}
diff --git a/src/slice.rs b/src/slice.rs
new file mode 100644
index 0000000..b25948d
--- /dev/null
+++ b/src/slice.rs
@@ -0,0 +1,100 @@
+use core::ops::{Deref, DerefMut};
+use core::fmt;
+
+#[cfg(feature = "std")]
+use std::boxed::Box;
+#[cfg(all(feature = "alloc", not(feature = "std")))]
+use alloc::boxed::Box;
+#[cfg(feature = "std")]
+use std::vec::Vec;
+#[cfg(all(feature = "alloc", not(feature = "std")))]
+use alloc::vec::Vec;
+
+/// A managed slice.
+///
+/// This enum can be used to represent exclusive access to slices of objects.
+/// In Rust, exclusive access to an object is obtained by either owning the object,
+/// or owning a mutable pointer to the object; hence, "managed".
+///
+/// The purpose of this enum is providing good ergonomics with `std` present while making
+/// it possible to avoid having a heap at all (which of course means that `std` is not present).
+/// To achieve this, the variants other than `Borrowed` are only available when the corresponding
+/// feature is opted in.
+///
+/// A function that requires a managed object should be generic over an `Into<ManagedSlice<'a, T>>`
+/// argument; then, it will be possible to pass either a `Vec<T>`, or a `&'a mut [T]`
+/// without any conversion at the call site.
+///
+/// See also [Managed](enum.Managed.html).
+pub enum ManagedSlice<'a, T: 'a> {
+    /// Borrowed variant.
+    Borrowed(&'a mut [T]),
+    /// Owned variant, only available with the `std` or `alloc` feature enabled.
+    #[cfg(any(feature = "std", feature = "alloc"))]
+    Owned(Vec<T>)
+}
+
+impl<'a, T: 'a> fmt::Debug for ManagedSlice<'a, T>
+        where T: fmt::Debug {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match self {
+            &ManagedSlice::Borrowed(ref x) => write!(f, "Borrowed({:?})", x),
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &ManagedSlice::Owned(ref x)    => write!(f, "Owned({:?})", x)
+        }
+    }
+}
+
+impl<'a, T: 'a> From<&'a mut [T]> for ManagedSlice<'a, T> {
+    fn from(value: &'a mut [T]) -> Self {
+        ManagedSlice::Borrowed(value)
+    }
+}
+
+macro_rules! from_unboxed_slice {
+    ($n:expr) => (
+        impl<'a, T> From<[T; $n]> for ManagedSlice<'a, T> {
+            #[inline]
+            fn from(value: [T; $n]) -> Self {
+                ManagedSlice::Owned((Box::new(value) as Box<[T]>).into_vec())
+            }
+        }
+    );
+    ($n:expr, $( $r:expr ),*) => (
+        from_unboxed_slice!($n);
+        from_unboxed_slice!($( $r ),*);
+    )
+}
+
+#[cfg(any(feature = "std", feature = "alloc"))]
+from_unboxed_slice!(0,  1,   2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15,
+                    16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31);
+
+#[cfg(any(feature = "std", feature = "alloc"))]
+impl<'a, T: 'a> From<Vec<T>> for ManagedSlice<'a, T> {
+    fn from(value: Vec<T>) -> Self {
+        ManagedSlice::Owned(value)
+    }
+}
+
+impl<'a, T: 'a> Deref for ManagedSlice<'a, T> {
+    type Target = [T];
+
+    fn deref(&self) -> &Self::Target {
+        match self {
+            &ManagedSlice::Borrowed(ref value) => value,
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &ManagedSlice::Owned(ref value) => value
+        }
+    }
+}
+
+impl<'a, T: 'a> DerefMut for ManagedSlice<'a, T> {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        match self {
+            &mut ManagedSlice::Borrowed(ref mut value) => value,
+            #[cfg(any(feature = "std", feature = "alloc"))]
+            &mut ManagedSlice::Owned(ref mut value) => value
+        }
+    }
+}
diff --git a/src/slotmap.rs b/src/slotmap.rs
new file mode 100644
index 0000000..d2b2759
--- /dev/null
+++ b/src/slotmap.rs
@@ -0,0 +1,490 @@
+//! A slotmap, a vector-like container with unique keys instead of indices.
+//!
+//! See the documentation of [`SlotMap`] for details.
+//!
+//! [`SlotMap`]: struct.SlotMap.html
+use super::{ManagedSlice as Slice};
+
+/// Provides links between slots and elements.
+///
+/// The benefit of separating this struct from the elements is that it is unconditionally `Copy`
+/// and `Default`. It also provides better locality for both the indices and the elements which
+/// could help with iteration or very large structs.
+#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
+pub struct Slot {
+    /// The id of this slot.
+    ///
+    /// If the given out index mismatches the `generation_id` then the element was removed already
+    /// and we can return `None` on lookup.
+    ///
+    /// If the slot is currently unused we will instead provide the index to the previous slot in
+    /// the slot-free-list.
+    generation_id: GenerationOrFreelink,
+}
+
+/// Provides a slotmap based on external memory.
+///
+/// A slotmap provides a `Vec`-like interface where each entry is associated with a stable
+/// index-like key. Lookup with the key will detect if an entry has been removed but does not
+/// require a lifetime relation. Compared to other slotmap implementations this does not internally
+/// allocate any memory on its own but only relies on the [`Slice`] arguments in the constructor.
+///
+/// [`Slice`]: ../enum.Slice.html
+///
+/// ## Usage
+///
+/// The important aspect is that the slotmap does not create the storage of its own elements, it
+/// merely manages one given to it at construction time.
+///
+/// ```
+/// # use managed::{ManagedSlice, SlotMap, SlotIndex};
+///
+/// let mut elements = [0usize; 1024];
+/// let mut slots = [SlotIndex::default(); 1024];
+///
+/// let mut map = SlotMap::new(
+///     ManagedSlice::Borrowed(&mut elements[..]),
+///     ManagedSlice::Borrowed(&mut slots[..]));
+/// let index = map.insert(42).unwrap();
+/// assert_eq!(map.get(index).cloned(), Some(42));
+/// ```
+pub struct SlotMap<'a, T> {
+    /// The slice where elements are placed.
+    /// All of them are initialized at all times but not all are logically part of the map.
+    elements: Slice<'a, T>,
+    /// The logical list of used slots.
+    /// Note that a slot is never remove from this list but instead used to track the generation_id
+    /// and the link in the free list.
+    slots: Partial<'a, Slot>,
+    /// The source of generation ids.
+    /// Generation ids are a positive, non-zero value.
+    generation: Generation,
+    /// An index to the top element of the free list.
+    /// Refers to the one-past-the-end index of `slots` if there are no elements.
+    free_top: usize,
+    /// An abstraction around computing wrapped indices in the free list.
+    indices: IndexComputer,
+}
+
+/// A backing slice tracking an index how far it is logically initialized.
+struct Partial<'a, T> {
+    slice: Slice<'a, T>,
+    next_idx: usize,
+}
+
+/// An index into a slotmap.
+///
+/// The index remains valid until the entry is removed. If accessing the slotmap with the index
+/// again after the entry was removed will fail, even if the index where the element was previously
+/// stored has been reused for another element.
+#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
+pub struct Key {
+    idx: usize,
+    generation: Generation,
+}
+
+#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
+struct GenerationOrFreelink(isize);
+
+/// Newtype wrapper around the index of a free slot.
+#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
+struct FreeIndex(usize);
+
+/// The generation counter.
+///
+/// Has a strictly positive value.
+#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
+struct Generation(isize);
+
+/// Offset of a freelist entry to the next entry.
+///
+/// Has a negative or zero value. Represents the negative of the offset to the next element in the
+/// free list, wrapping around at the capacity.
+/// The base for the offset is the *next* element for two reasons:
+/// * Offset of `0` points to the natural successor.
+/// * Offset of `len` would point to the element itself and should not occur.
+#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
+struct Offset(isize);
+
+/// Links FreeIndex and Offset.
+struct IndexComputer(usize);
+
+impl<T> SlotMap<'_, T> {
+    /// Retrieve a value by index.
+    pub fn get(&self, index: Key) -> Option<&T> {
+        let slot_generation = self.slots
+            .get(index.idx)?
+            .generation_id
+            .generation().ok()?;
+
+        if slot_generation != index.generation {
+            return None;
+        }
+
+        self.elements.get(index.idx)
+    }
+
+    /// Retrieve a mutable value by index.
+    pub fn get_mut(&mut self, index: Key) -> Option<&mut T> {
+        let slot_generation = self.slots
+            .get(index.idx)?
+            .generation_id
+            .generation().ok()?;
+
+        if slot_generation != index.generation {
+            return None;
+        }
+
+        self.elements.get_mut(index.idx)
+    }
+
+    /// Reserve a new entry.
+    ///
+    /// In case of success, the returned key refers to the entry until it is removed. The entry
+    /// itself is not initialized with any particular value but instead retains the value it had in
+    /// the backing slice. It is only logically placed into the slot map.
+    pub fn reserve(&mut self) -> Option<(Key, &mut T)> {
+        let index = self.next_free_slot()?;
+        let slot = self.slots.get_mut(index.0).unwrap();
+        let element = &mut self.elements[index.0];
+
+        let offset = slot.generation_id
+            .free_link()
+            .expect("Free link should be free");
+        slot.generation_id = self.generation.into();
+        let key = Key {
+            idx: index.0,
+            generation: self.generation,
+        };
+
+        self.free_top = self.indices.free_list_next(index, offset);
+        self.generation.advance();
+        Some((key, element))
+    }
+
+    /// Try to insert a value into the map.
+    ///
+    /// This will fail if there is not enough space. Sugar wrapper around `reserve` for inserting
+    /// values. Note that on success, an old value stored in the backing slice will be overwritten.
+    /// Use `reserve` directly if it is vital that no old value is dropped.
+    pub fn insert(&mut self, value: T) -> Option<Key> {
+        // Insertion must work but we don't care about the value.
+        let (index, element) = self.reserve()?;
+        *element = value;
+        Some(index)
+    }
+
+    /// Remove an element.
+    ///
+    /// If successful, return a mutable reference to the removed element so that the caller can
+    /// swap it with a logically empty value. Returns `None` if the provided index did not refer to
+    /// an element that could be freed.
+    pub fn remove(&mut self, index: Key) -> Option<&mut T> {
+        if self.get(index).is_none() {
+            return None
+        }
+
+        // The slot can be freed.
+        let free = FreeIndex(index.idx);
+        let slot = self.slots.get_mut(index.idx).unwrap();
+        assert!(slot.generation_id.generation().is_ok());
+
+        let offset = self.indices.free_list_offset(free, self.free_top);
+        slot.generation_id = offset.into();
+        self.free_top = index.idx;
+
+        Some(&mut self.elements[index.idx])
+    }
+
+    /// Get the next free slot.
+    fn next_free_slot(&mut self) -> Option<FreeIndex> {
+        // If free_top is one-past-the-end marker one of those is going to fail. Note that this
+        // also means extracting one of these statements out of the function may change the
+        // semantics if `elements.len() != slots.len()`.
+
+        // Ensure the index refers to an element within the slice or try to allocate a new slot
+        // wherein we can fit the element.
+        let free = match self.slots.get_mut(self.free_top) {
+            // There is a free element in our free list.
+            Some(_) => {
+                // Ensure that there is also a real element there.
+                let _= self.elements.get_mut(self.free_top)?;
+                FreeIndex(self.free_top)
+            },
+            // Need to try an get a new element from the slot slice.
+            None => { // Try to get the next one
+                // Will not actually wrap if pushing is successful.
+                let new_index = self.slots.len();
+                // Ensure there is an element where we want to push to.
+                let _ = self.elements.get_mut(new_index)?;
+
+                let free_slot = self.slots.try_reserve()?;
+                let free_index = FreeIndex(new_index);
+                // New top is the new one-past-the-end.
+                let new_top = new_index.checked_add(1).unwrap();
+
+                let offset = self.indices.free_list_offset(free_index, new_top);
+                free_slot.generation_id = offset.into();
+                self.free_top = free_index.0;
+
+                free_index
+            }
+        };
+
+
+        // index refers to elements within the slices
+        Some(free)
+    }
+}
+
+impl<'a, T> SlotMap<'a, T> {
+    /// Create a slot map.
+    ///
+    /// The capacity is the minimum of the capacity of the element and slot slices.
+    pub fn new(elements: Slice<'a, T>, slots: Slice<'a, Slot>) -> Self {
+        let capacity = elements.len().min(slots.len());
+        SlotMap {
+            elements,
+            slots: Partial {
+                slice: slots,
+                next_idx: 0,
+            },
+            generation: Generation::default(),
+            free_top: 0,
+            indices: IndexComputer::from_capacity(capacity),
+        }
+    }
+}
+
+impl<'a, T> Partial<'a, T> {
+    fn get(&self, idx: usize) -> Option<&T> {
+        if idx >= self.next_idx {
+            None
+        } else {
+            Some(&self.slice[idx])
+        }
+    }
+
+    fn get_mut(&mut self, idx: usize) -> Option<&mut T> {
+        if idx >= self.next_idx {
+            None
+        } else {
+            Some(&mut self.slice[idx])
+        }
+    }
+
+    fn len(&self) -> usize {
+        self.next_idx
+    }
+
+    fn try_reserve(&mut self) -> Option<&mut T> {
+        if self.next_idx == self.slice.len() {
+            None
+        } else {
+            let idx = self.next_idx;
+            self.next_idx += 1;
+            Some(&mut self.slice[idx])
+        }
+    }
+}
+
+impl GenerationOrFreelink {
+    pub(crate) fn free_link(self) -> Result<Offset, Generation> {
+        if self.0 > 0 {
+            Err(Generation(self.0))
+        } else {
+            Ok(Offset(self.0))
+        }
+    }
+
+    pub(crate) fn generation(self) -> Result<Generation, Offset> {
+        match self.free_link() {
+            Ok(offset) => Err(offset),
+            Err(generation) => Ok(generation),
+        }
+    }
+}
+
+impl IndexComputer {
+    pub(crate) fn from_capacity(capacity: usize) -> Self {
+        assert!(capacity < isize::max_value() as usize);
+        IndexComputer(capacity)
+    }
+
+    /// Get the next free list entry.
+    /// This applies the offset to the base index, wrapping around if required.
+    ///
+    /// This is the reverse of `free_list_offset`.
+    fn free_list_next(&self, FreeIndex(base): FreeIndex, offset: Offset)
+        -> usize
+    {
+        let capacity = self.0;
+        let offset = offset.int_offset();
+
+        assert!(base < capacity);
+        assert!(offset <= capacity);
+        let base = base + 1;
+
+        if capacity - offset >= base {
+            offset + base // Fine within the range
+        } else {
+            // Mathematically, capacity < offset + base < 2*capacity
+            // Wrap once, mod (capacity + 1), result again in range
+            offset
+                .wrapping_add(base)
+                .wrapping_sub(capacity + 1)
+        }
+    }
+
+    /// Get the offset difference between the index and the next element.
+    /// Computes a potentially wrapping positive offset where zero is the element following the
+    /// base.
+    ///
+    /// This is the reverse of `free_list_next`.
+    fn free_list_offset(&self, FreeIndex(base): FreeIndex, to: usize)
+        -> Offset
+    {
+        let capacity = self.0;
+
+        assert!(base != to, "Cant offset element to itself");
+        assert!(base < capacity, "Should never have to offset the end-of-list marker");
+        assert!(to <= capacity, "Can only offset to the end-of-list marker");
+        let base = base + 1;
+
+        Offset::from_int_offset(if base <= to {
+            to - base
+        } else {
+            // Wrap once, mod (capacity + 1), result again in range
+            to
+                .wrapping_add(capacity + 1)
+                .wrapping_sub(base)
+        })
+    }
+}
+
+impl Generation {
+    pub(crate) fn advance(&mut self) {
+        assert!(self.0 > 0);
+        self.0 = self.0.wrapping_add(1).max(1)
+    }
+}
+
+impl Offset {
+    pub(crate) fn from_int_offset(offset: usize) -> Self {
+        assert!(offset < isize::max_value() as usize);
+        Offset((offset as isize).checked_neg().unwrap())
+    }
+
+    pub(crate) fn int_offset(self) -> usize {
+        self.0.checked_neg().unwrap() as usize
+    }
+}
+
+impl Default for Generation {
+    fn default() -> Self {
+        Generation(1)
+    }
+}
+
+impl From<Generation> for GenerationOrFreelink {
+    fn from(gen: Generation) -> GenerationOrFreelink {
+        GenerationOrFreelink(gen.0)
+    }
+}
+
+impl From<Offset> for GenerationOrFreelink {
+    fn from(offset: Offset) -> GenerationOrFreelink {
+        GenerationOrFreelink(offset.0)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::slice::ManagedSlice as Slice;
+
+    #[test]
+    fn simple() {
+        let mut elements = [0u32; 2];
+        let mut slots = [Slot::default(); 2];
+
+        let mut map = SlotMap::new(
+            Slice::Borrowed(&mut elements[..]),
+            Slice::Borrowed(&mut slots[..]));
+        let key42 = map.insert(42).unwrap();
+        let keylo = map.insert('K' as _).unwrap();
+
+        assert_eq!(map.insert(0x9999), None);
+        assert_eq!(map.get(key42).cloned(), Some(42));
+        assert_eq!(map.get(keylo).cloned(), Some('K' as _));
+
+        assert!(map.remove(key42).is_some());
+        assert_eq!(map.get(key42), None);
+
+        let lastkey = map.insert(0x9999).unwrap();
+        assert_eq!(map.get(lastkey).cloned(), Some(0x9999));
+
+        *map.remove(keylo).unwrap() = 0;
+        assert_eq!(map.get(lastkey).cloned(), Some(0x9999));
+        assert!(map.remove(lastkey).is_some());
+    }
+
+    #[test]
+    fn retained() {
+        let mut elements = [0u32; 1];
+        let mut slots = [Slot::default(); 1];
+
+        let mut map = SlotMap::new(
+            Slice::Borrowed(&mut elements[..]),
+            Slice::Borrowed(&mut slots[..]));
+        let key = map.insert(0xde).unwrap();
+        map.remove(key).unwrap();
+        assert_eq!(map.get(key), None);
+
+        let new_key = map.insert(0xad).unwrap();
+
+        assert_eq!(map.get(key), None);
+        assert_eq!(map.get(new_key).cloned(), Some(0xad));
+
+        assert_eq!(map.remove(key), None);
+        map.remove(new_key).unwrap();
+
+        assert_eq!(map.get(key), None);
+        assert_eq!(map.get(new_key), None);
+    }
+
+    #[test]
+    fn non_simple_free_list() {
+        // Check the free list implementation
+        let mut elements = [0u32; 3];
+        let mut slots = [Slot::default(); 3];
+
+        let mut map = SlotMap::new(
+            Slice::Borrowed(&mut elements[..]),
+            Slice::Borrowed(&mut slots[..]));
+
+        let key0 = map.insert(0).unwrap();
+        let key1 = map.insert(1).unwrap();
+        let key2 = map.insert(2).unwrap();
+
+        *map.remove(key1).unwrap() = 0xF;
+        assert_eq!(map.free_top, 1);
+        assert_eq!(map.get(key0).cloned(), Some(0));
+        assert_eq!(map.get(key2).cloned(), Some(2));
+
+        *map.remove(key2).unwrap() = 0xF;
+        assert_eq!(map.free_top, 2);
+        assert_eq!(map.get(key0).cloned(), Some(0));
+
+        *map.remove(key0).unwrap() = 0xF;
+        assert_eq!(map.free_top, 0);
+
+        let key0 = map.insert(0).unwrap();
+        assert_eq!(map.free_top, 2);
+        let key1 = map.insert(1).unwrap();
+        let key2 = map.insert(2).unwrap();
+        assert_eq!(map.get(key0).cloned(), Some(0));
+        assert_eq!(map.get(key1).cloned(), Some(1));
+        assert_eq!(map.get(key2).cloned(), Some(2));
+    }
+}