Import 'slab' rust crate version 0.4.2

Bug: b/151760391
Test: m crosvm.experimental
Change-Id: Ifdc5a0fdd0b226050d45ea80a6e60d9295e65ba1

13 files changed, 1439 insertions, 0 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
new file mode 100644
index 0000000..11ad1ab
--- /dev/null
+++ b/.cargo_vcs_info.json
@@ -0,0 +1,5 @@
+{
+  "git": {
+    "sha1": "e6b8676a1526f9eed997c9f4db82386ba33e007c"
+  }
+}
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..b235e4d
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+*.swp
+target
+Cargo.lock
diff --git a/Android.bp b/Android.bp
new file mode 100644
index 0000000..f22b235
--- /dev/null
+++ b/Android.bp
@@ -0,0 +1,8 @@
+// This file is generated by cargo2android.py.
+
+rust_library_host_rlib {
+    name: "libslab",
+    crate_name: "slab",
+    srcs: ["src/lib.rs"],
+    edition: "2015",
+}
diff --git a/CHANGELOG.md b/CHANGELOG.md
new file mode 100644
index 0000000..9a222b4
--- /dev/null
+++ b/CHANGELOG.md
@@ -0,0 +1,8 @@
+# 0.4.2 (January 11, 2019)
+
+* Add `Slab::drain` (#56).
+
+# 0.4.1 (July 15, 2018)
+
+* Improve `reserve` and `reserve_exact` (#37).
+* Implement `Default` for `Slab` (#43).
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..9e9fc42
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,24 @@
+# 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 = "slab"
+version = "0.4.2"
+authors = ["Carl Lerche <me@carllerche.com>"]
+description = "Pre-allocated storage for a uniform data type"
+homepage = "https://github.com/carllerche/slab"
+documentation = "https://docs.rs/slab/0.4.2/slab/"
+readme = "README.md"
+keywords = ["slab", "allocator"]
+categories = ["memory-management", "data-structures"]
+license = "MIT"
+repository = "https://github.com/carllerche/slab"
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
new file mode 100644
index 0000000..88da41f
--- /dev/null
+++ b/Cargo.toml.orig
@@ -0,0 +1,22 @@
+[package]
+
+name = "slab"
+# When releasing to crates.io:
+# - Update version number
+#   - lib.rs: html_root_url.
+#   - README.md
+# - Update CHANGELOG.md
+# - Update doc URL.
+#   - Cargo.toml
+#   - README.md
+# - Create git tag
+version = "0.4.2"
+license = "MIT"
+authors = ["Carl Lerche <me@carllerche.com>"]
+description = "Pre-allocated storage for a uniform data type"
+documentation = "https://docs.rs/slab/0.4.2/slab/"
+homepage = "https://github.com/carllerche/slab"
+repository = "https://github.com/carllerche/slab"
+readme = "README.md"
+keywords = ["slab", "allocator"]
+categories = ["memory-management", "data-structures"]
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..819ce21
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,25 @@
+Copyright (c) 2019 Carl Lerche
+
+Permission is hereby granted, free of charge, to any
+person obtaining a copy of this software and associated
+documentation files (the "Software"), to deal in the
+Software without restriction, including without
+limitation the rights to use, copy, modify, merge,
+publish, distribute, sublicense, and/or sell copies of
+the Software, and to permit persons to whom the Software
+is furnished to do so, subject to the following
+conditions:
+
+The above copyright notice and this permission notice
+shall be included in all copies or substantial portions
+of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
+ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
+TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
+PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
+SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+DEALINGS IN THE SOFTWARE.
diff --git a/METADATA b/METADATA
new file mode 100644
index 0000000..394b0dd
--- /dev/null
+++ b/METADATA
@@ -0,0 +1,17 @@
+name: "slab"
+description:
+    "Pre-allocated storage for a uniform data type"
+
+third_party {
+  url {
+    type: HOMEPAGE
+    value: "https://crates.io/crates/slab"
+  }
+  url {
+    type: GIT
+    value: "https://github.com/carllerche/slab"
+  }
+  version: "v0.4.2"
+  last_upgrade_date { year: 2020 month: 3 day: 17 }
+  license_type: NOTICE
+}
diff --git a/MODULE_LICENSE_MIT b/MODULE_LICENSE_MIT
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/MODULE_LICENSE_MIT
diff --git a/NOTICE b/NOTICE
new file mode 120000
index 0000000..7a694c9
--- /dev/null
+++ b/NOTICE
@@ -0,0 +1 @@
+LICENSE
\ No newline at end of file
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..2609ffb
--- /dev/null
+++ b/README.md
@@ -0,0 +1,48 @@
+# Slab
+
+Pre-allocated storage for a uniform data type.
+
+[![Crates.io](https://img.shields.io/crates/v/slab.svg?maxAge=2592000)](https://crates.io/crates/slab)
+[![Build Status](https://travis-ci.org/carllerche/slab.svg?branch=master)](https://travis-ci.org/carllerche/slab)
+
+[Documentation](https://docs.rs/slab/0.4.2/slab/)
+
+## Usage
+
+To use `slab`, first add this to your `Cargo.toml`:
+
+```toml
+[dependencies]
+slab = "0.4.2"
+```
+
+Next, add this to your crate:
+
+```rust
+extern crate slab;
+
+use slab::Slab;
+
+let mut slab = Slab::new();
+
+let hello = slab.insert("hello");
+let world = slab.insert("world");
+
+assert_eq!(slab[hello], "hello");
+assert_eq!(slab[world], "world");
+
+slab[world] = "earth";
+assert_eq!(slab[world], "earth");
+```
+
+See [documentation](https://docs.rs/slab) for more details.
+
+## License
+
+This project is licensed under the [MIT license](LICENSE).
+
+### Contribution
+
+Unless you explicitly state otherwise, any contribution intentionally submitted
+for inclusion in `slab` by you, shall be licensed as MIT, without any additional
+terms or conditions.
diff --git a/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..a3638ca
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1,977 @@
+#![doc(html_root_url = "https://docs.rs/slab/0.4.2")]
+#![deny(warnings, missing_docs, missing_debug_implementations)]
+#![cfg_attr(test, deny(warnings, unreachable_pub))]
+
+//! Pre-allocated storage for a uniform data type.
+//!
+//! `Slab` provides pre-allocated storage for a single data type. If many values
+//! of a single type are being allocated, it can be more efficient to
+//! pre-allocate the necessary storage. Since the size of the type is uniform,
+//! memory fragmentation can be avoided. Storing, clearing, and lookup
+//! operations become very cheap.
+//!
+//! While `Slab` may look like other Rust collections, it is not intended to be
+//! used as a general purpose collection. The primary difference between `Slab`
+//! and `Vec` is that `Slab` returns the key when storing the value.
+//!
+//! It is important to note that keys may be reused. In other words, once a
+//! value associated with a given key is removed from a slab, that key may be
+//! returned from future calls to `insert`.
+//!
+//! # Examples
+//!
+//! Basic storing and retrieval.
+//!
+//! ```
+//! # use slab::*;
+//! let mut slab = Slab::new();
+//!
+//! let hello = slab.insert("hello");
+//! let world = slab.insert("world");
+//!
+//! assert_eq!(slab[hello], "hello");
+//! assert_eq!(slab[world], "world");
+//!
+//! slab[world] = "earth";
+//! assert_eq!(slab[world], "earth");
+//! ```
+//!
+//! Sometimes it is useful to be able to associate the key with the value being
+//! inserted in the slab. This can be done with the `vacant_entry` API as such:
+//!
+//! ```
+//! # use slab::*;
+//! let mut slab = Slab::new();
+//!
+//! let hello = {
+//!     let entry = slab.vacant_entry();
+//!     let key = entry.key();
+//!
+//!     entry.insert((key, "hello"));
+//!     key
+//! };
+//!
+//! assert_eq!(hello, slab[hello].0);
+//! assert_eq!("hello", slab[hello].1);
+//! ```
+//!
+//! It is generally a good idea to specify the desired capacity of a slab at
+//! creation time. Note that `Slab` will grow the internal capacity when
+//! attempting to insert a new value once the existing capacity has been reached.
+//! To avoid this, add a check.
+//!
+//! ```
+//! # use slab::*;
+//! let mut slab = Slab::with_capacity(1024);
+//!
+//! // ... use the slab
+//!
+//! if slab.len() == slab.capacity() {
+//!     panic!("slab full");
+//! }
+//!
+//! slab.insert("the slab is not at capacity yet");
+//! ```
+//!
+//! # Capacity and reallocation
+//!
+//! The capacity of a slab is the amount of space allocated for any future
+//! values that will be inserted in the slab. This is not to be confused with
+//! the *length* of the slab, which specifies the number of actual values
+//! currently being inserted. If a slab's length is equal to its capacity, the
+//! next value inserted into the slab will require growing the slab by
+//! reallocating.
+//!
+//! For example, a slab with capacity 10 and length 0 would be an empty slab
+//! with space for 10 more stored values. Storing 10 or fewer elements into the
+//! slab will not change its capacity or cause reallocation to occur. However,
+//! if the slab length is increased to 11 (due to another `insert`), it will
+//! have to reallocate, which can be slow. For this reason, it is recommended to
+//! use [`Slab::with_capacity`] whenever possible to specify how many values the
+//! slab is expected to store.
+//!
+//! # Implementation
+//!
+//! `Slab` is backed by a `Vec` of slots. Each slot is either occupied or
+//! vacant. `Slab` maintains a stack of vacant slots using a linked list. To
+//! find a vacant slot, the stack is popped. When a slot is released, it is
+//! pushed onto the stack.
+//!
+//! If there are no more available slots in the stack, then `Vec::reserve(1)` is
+//! called and a new slot is created.
+//!
+//! [`Slab::with_capacity`]: struct.Slab.html#with_capacity
+
+use std::iter::IntoIterator;
+use std::ops;
+use std::vec;
+use std::{fmt, mem};
+
+/// Pre-allocated storage for a uniform data type
+///
+/// See the [module documentation] for more details.
+///
+/// [module documentation]: index.html
+#[derive(Clone)]
+pub struct Slab<T> {
+    // Chunk of memory
+    entries: Vec<Entry<T>>,
+
+    // Number of Filled elements currently in the slab
+    len: usize,
+
+    // Offset of the next available slot in the slab. Set to the slab's
+    // capacity when the slab is full.
+    next: usize,
+}
+
+impl<T> Default for Slab<T> {
+    fn default() -> Self {
+        Slab::new()
+    }
+}
+
+/// A handle to a vacant entry in a `Slab`.
+///
+/// `VacantEntry` allows constructing values with the key that they will be
+/// assigned to.
+///
+/// # Examples
+///
+/// ```
+/// # use slab::*;
+/// let mut slab = Slab::new();
+///
+/// let hello = {
+///     let entry = slab.vacant_entry();
+///     let key = entry.key();
+///
+///     entry.insert((key, "hello"));
+///     key
+/// };
+///
+/// assert_eq!(hello, slab[hello].0);
+/// assert_eq!("hello", slab[hello].1);
+/// ```
+#[derive(Debug)]
+pub struct VacantEntry<'a, T: 'a> {
+    slab: &'a mut Slab<T>,
+    key: usize,
+}
+
+/// An iterator over the values stored in the `Slab`
+pub struct Iter<'a, T: 'a> {
+    entries: std::slice::Iter<'a, Entry<T>>,
+    curr: usize,
+}
+
+/// A mutable iterator over the values stored in the `Slab`
+pub struct IterMut<'a, T: 'a> {
+    entries: std::slice::IterMut<'a, Entry<T>>,
+    curr: usize,
+}
+
+/// A draining iterator for `Slab`
+pub struct Drain<'a, T: 'a>(vec::Drain<'a, Entry<T>>);
+
+#[derive(Clone)]
+enum Entry<T> {
+    Vacant(usize),
+    Occupied(T),
+}
+
+impl<T> Slab<T> {
+    /// Construct a new, empty `Slab`.
+    ///
+    /// The function does not allocate and the returned slab will have no
+    /// capacity until `insert` is called or capacity is explicitly reserved.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let slab: Slab<i32> = Slab::new();
+    /// ```
+    pub fn new() -> Slab<T> {
+        Slab::with_capacity(0)
+    }
+
+    /// Construct a new, empty `Slab` with the specified capacity.
+    ///
+    /// The returned slab will be able to store exactly `capacity` without
+    /// reallocating. If `capacity` is 0, the slab will not allocate.
+    ///
+    /// It is important to note that this function does not specify the *length*
+    /// of the returned slab, but only the capacity. For an explanation of the
+    /// difference between length and capacity, see [Capacity and
+    /// reallocation](index.html#capacity-and-reallocation).
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::with_capacity(10);
+    ///
+    /// // The slab contains no values, even though it has capacity for more
+    /// assert_eq!(slab.len(), 0);
+    ///
+    /// // These are all done without reallocating...
+    /// for i in 0..10 {
+    ///     slab.insert(i);
+    /// }
+    ///
+    /// // ...but this may make the slab reallocate
+    /// slab.insert(11);
+    /// ```
+    pub fn with_capacity(capacity: usize) -> Slab<T> {
+        Slab {
+            entries: Vec::with_capacity(capacity),
+            next: 0,
+            len: 0,
+        }
+    }
+
+    /// Return the number of values the slab can store without reallocating.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let slab: Slab<i32> = Slab::with_capacity(10);
+    /// assert_eq!(slab.capacity(), 10);
+    /// ```
+    pub fn capacity(&self) -> usize {
+        self.entries.capacity()
+    }
+
+    /// Reserve capacity for at least `additional` more values to be stored
+    /// without allocating.
+    ///
+    /// `reserve` does nothing if the slab already has sufficient capacity for
+    /// `additional` more values. If more capacity is required, a new segment of
+    /// memory will be allocated and all existing values will be copied into it.
+    /// As such, if the slab is already very large, a call to `reserve` can end
+    /// up being expensive.
+    ///
+    /// The slab may reserve more than `additional` extra space in order to
+    /// avoid frequent reallocations. Use `reserve_exact` instead to guarantee
+    /// that only the requested space is allocated.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the new capacity overflows `usize`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    /// slab.insert("hello");
+    /// slab.reserve(10);
+    /// assert!(slab.capacity() >= 11);
+    /// ```
+    pub fn reserve(&mut self, additional: usize) {
+        if self.capacity() - self.len >= additional {
+            return;
+        }
+        let need_add = self.len + additional - self.entries.len();
+        self.entries.reserve(need_add);
+    }
+
+    /// Reserve the minimum capacity required to store exactly `additional`
+    /// more values.
+    ///
+    /// `reserve_exact` does nothing if the slab already has sufficient capacity
+    /// for `additional` more valus. If more capacity is required, a new segment
+    /// of memory will be allocated and all existing values will be copied into
+    /// it.  As such, if the slab is already very large, a call to `reserve` can
+    /// end up being expensive.
+    ///
+    /// Note that the allocator may give the slab more space than it requests.
+    /// Therefore capacity can not be relied upon to be precisely minimal.
+    /// Prefer `reserve` if future insertions are expected.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the new capacity overflows `usize`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    /// slab.insert("hello");
+    /// slab.reserve_exact(10);
+    /// assert!(slab.capacity() >= 11);
+    /// ```
+    pub fn reserve_exact(&mut self, additional: usize) {
+        if self.capacity() - self.len >= additional {
+            return;
+        }
+        let need_add = self.len + additional - self.entries.len();
+        self.entries.reserve_exact(need_add);
+    }
+
+    /// Shrink the capacity of the slab as much as possible.
+    ///
+    /// It will drop down as close as possible to the length but the allocator
+    /// may still inform the vector that there is space for a few more elements.
+    /// Also, since values are not moved, the slab cannot shrink past any stored
+    /// values.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::with_capacity(10);
+    ///
+    /// for i in 0..3 {
+    ///     slab.insert(i);
+    /// }
+    ///
+    /// assert_eq!(slab.capacity(), 10);
+    /// slab.shrink_to_fit();
+    /// assert!(slab.capacity() >= 3);
+    /// ```
+    ///
+    /// In this case, even though two values are removed, the slab cannot shrink
+    /// past the last value.
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::with_capacity(10);
+    ///
+    /// for i in 0..3 {
+    ///     slab.insert(i);
+    /// }
+    ///
+    /// slab.remove(0);
+    /// slab.remove(1);
+    ///
+    /// assert_eq!(slab.capacity(), 10);
+    /// slab.shrink_to_fit();
+    /// assert!(slab.capacity() >= 3);
+    /// ```
+    pub fn shrink_to_fit(&mut self) {
+        self.entries.shrink_to_fit();
+    }
+
+    /// Clear the slab of all values.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    ///
+    /// for i in 0..3 {
+    ///     slab.insert(i);
+    /// }
+    ///
+    /// slab.clear();
+    /// assert!(slab.is_empty());
+    /// ```
+    pub fn clear(&mut self) {
+        self.entries.clear();
+        self.len = 0;
+        self.next = 0;
+    }
+
+    /// Return the number of stored values.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    ///
+    /// for i in 0..3 {
+    ///     slab.insert(i);
+    /// }
+    ///
+    /// assert_eq!(3, slab.len());
+    /// ```
+    pub fn len(&self) -> usize {
+        self.len
+    }
+
+    /// Return `true` if there are no values stored in the slab.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    /// assert!(slab.is_empty());
+    ///
+    /// slab.insert(1);
+    /// assert!(!slab.is_empty());
+    /// ```
+    pub fn is_empty(&self) -> bool {
+        self.len == 0
+    }
+
+    /// Return an iterator over the slab.
+    ///
+    /// This function should generally be **avoided** as it is not efficient.
+    /// Iterators must iterate over every slot in the slab even if it is
+    /// vacant. As such, a slab with a capacity of 1 million but only one
+    /// stored value must still iterate the million slots.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    ///
+    /// for i in 0..3 {
+    ///     slab.insert(i);
+    /// }
+    ///
+    /// let mut iterator = slab.iter();
+    ///
+    /// assert_eq!(iterator.next(), Some((0, &0)));
+    /// assert_eq!(iterator.next(), Some((1, &1)));
+    /// assert_eq!(iterator.next(), Some((2, &2)));
+    /// assert_eq!(iterator.next(), None);
+    /// ```
+    pub fn iter(&self) -> Iter<T> {
+        Iter {
+            entries: self.entries.iter(),
+            curr: 0,
+        }
+    }
+
+    /// Return an iterator that allows modifying each value.
+    ///
+    /// This function should generally be **avoided** as it is not efficient.
+    /// Iterators must iterate over every slot in the slab even if it is
+    /// vacant. As such, a slab with a capacity of 1 million but only one
+    /// stored value must still iterate the million slots.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    ///
+    /// let key1 = slab.insert(0);
+    /// let key2 = slab.insert(1);
+    ///
+    /// for (key, val) in slab.iter_mut() {
+    ///     if key == key1 {
+    ///         *val += 2;
+    ///     }
+    /// }
+    ///
+    /// assert_eq!(slab[key1], 2);
+    /// assert_eq!(slab[key2], 1);
+    /// ```
+    pub fn iter_mut(&mut self) -> IterMut<T> {
+        IterMut {
+            entries: self.entries.iter_mut(),
+            curr: 0,
+        }
+    }
+
+    /// Return a reference to the value associated with the given key.
+    ///
+    /// If the given key is not associated with a value, then `None` is
+    /// returned.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    /// let key = slab.insert("hello");
+    ///
+    /// assert_eq!(slab.get(key), Some(&"hello"));
+    /// assert_eq!(slab.get(123), None);
+    /// ```
+    pub fn get(&self, key: usize) -> Option<&T> {
+        match self.entries.get(key) {
+            Some(&Entry::Occupied(ref val)) => Some(val),
+            _ => None,
+        }
+    }
+
+    /// Return a mutable reference to the value associated with the given key.
+    ///
+    /// If the given key is not associated with a value, then `None` is
+    /// returned.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    /// let key = slab.insert("hello");
+    ///
+    /// *slab.get_mut(key).unwrap() = "world";
+    ///
+    /// assert_eq!(slab[key], "world");
+    /// assert_eq!(slab.get_mut(123), None);
+    /// ```
+    pub fn get_mut(&mut self, key: usize) -> Option<&mut T> {
+        match self.entries.get_mut(key) {
+            Some(&mut Entry::Occupied(ref mut val)) => Some(val),
+            _ => None,
+        }
+    }
+
+    /// Return a reference to the value associated with the given key without
+    /// performing bounds checking.
+    ///
+    /// This function should be used with care.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    /// let key = slab.insert(2);
+    ///
+    /// unsafe {
+    ///     assert_eq!(slab.get_unchecked(key), &2);
+    /// }
+    /// ```
+    pub unsafe fn get_unchecked(&self, key: usize) -> &T {
+        match *self.entries.get_unchecked(key) {
+            Entry::Occupied(ref val) => val,
+            _ => unreachable!(),
+        }
+    }
+
+    /// Return a mutable reference to the value associated with the given key
+    /// without performing bounds checking.
+    ///
+    /// This function should be used with care.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    /// let key = slab.insert(2);
+    ///
+    /// unsafe {
+    ///     let val = slab.get_unchecked_mut(key);
+    ///     *val = 13;
+    /// }
+    ///
+    /// assert_eq!(slab[key], 13);
+    /// ```
+    pub unsafe fn get_unchecked_mut(&mut self, key: usize) -> &mut T {
+        match *self.entries.get_unchecked_mut(key) {
+            Entry::Occupied(ref mut val) => val,
+            _ => unreachable!(),
+        }
+    }
+
+    /// Insert a value in the slab, returning key assigned to the value.
+    ///
+    /// The returned key can later be used to retrieve or remove the value using indexed
+    /// lookup and `remove`. Additional capacity is allocated if needed. See
+    /// [Capacity and reallocation](index.html#capacity-and-reallocation).
+    ///
+    /// # Panics
+    ///
+    /// Panics if the number of elements in the vector overflows a `usize`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    /// let key = slab.insert("hello");
+    /// assert_eq!(slab[key], "hello");
+    /// ```
+    pub fn insert(&mut self, val: T) -> usize {
+        let key = self.next;
+
+        self.insert_at(key, val);
+
+        key
+    }
+
+    /// Return a handle to a vacant entry allowing for further manipulation.
+    ///
+    /// This function is useful when creating values that must contain their
+    /// slab key. The returned `VacantEntry` reserves a slot in the slab and is
+    /// able to query the associated key.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    ///
+    /// let hello = {
+    ///     let entry = slab.vacant_entry();
+    ///     let key = entry.key();
+    ///
+    ///     entry.insert((key, "hello"));
+    ///     key
+    /// };
+    ///
+    /// assert_eq!(hello, slab[hello].0);
+    /// assert_eq!("hello", slab[hello].1);
+    /// ```
+    pub fn vacant_entry(&mut self) -> VacantEntry<T> {
+        VacantEntry {
+            key: self.next,
+            slab: self,
+        }
+    }
+
+    fn insert_at(&mut self, key: usize, val: T) {
+        self.len += 1;
+
+        if key == self.entries.len() {
+            self.entries.push(Entry::Occupied(val));
+            self.next = key + 1;
+        } else {
+            let prev = mem::replace(&mut self.entries[key], Entry::Occupied(val));
+
+            match prev {
+                Entry::Vacant(next) => {
+                    self.next = next;
+                }
+                _ => unreachable!(),
+            }
+        }
+    }
+
+    /// Remove and return the value associated with the given key.
+    ///
+    /// The key is then released and may be associated with future stored
+    /// values.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `key` is not associated with a value.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    ///
+    /// let hello = slab.insert("hello");
+    ///
+    /// assert_eq!(slab.remove(hello), "hello");
+    /// assert!(!slab.contains(hello));
+    /// ```
+    pub fn remove(&mut self, key: usize) -> T {
+        // Swap the entry at the provided value
+        let prev = mem::replace(&mut self.entries[key], Entry::Vacant(self.next));
+
+        match prev {
+            Entry::Occupied(val) => {
+                self.len -= 1;
+                self.next = key;
+                val
+            }
+            _ => {
+                // Woops, the entry is actually vacant, restore the state
+                self.entries[key] = prev;
+                panic!("invalid key");
+            }
+        }
+    }
+
+    /// Return `true` if a value is associated with the given key.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    ///
+    /// let hello = slab.insert("hello");
+    /// assert!(slab.contains(hello));
+    ///
+    /// slab.remove(hello);
+    ///
+    /// assert!(!slab.contains(hello));
+    /// ```
+    pub fn contains(&self, key: usize) -> bool {
+        self.entries
+            .get(key)
+            .map(|e| match *e {
+                Entry::Occupied(_) => true,
+                _ => false,
+            })
+            .unwrap_or(false)
+    }
+
+    /// Retain only the elements specified by the predicate.
+    ///
+    /// In other words, remove all elements `e` such that `f(usize, &mut e)`
+    /// returns false. This method operates in place and preserves the key
+    /// associated with the retained values.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    ///
+    /// let k1 = slab.insert(0);
+    /// let k2 = slab.insert(1);
+    /// let k3 = slab.insert(2);
+    ///
+    /// slab.retain(|key, val| key == k1 || *val == 1);
+    ///
+    /// assert!(slab.contains(k1));
+    /// assert!(slab.contains(k2));
+    /// assert!(!slab.contains(k3));
+    ///
+    /// assert_eq!(2, slab.len());
+    /// ```
+    pub fn retain<F>(&mut self, mut f: F)
+    where
+        F: FnMut(usize, &mut T) -> bool,
+    {
+        for i in 0..self.entries.len() {
+            let keep = match self.entries[i] {
+                Entry::Occupied(ref mut v) => f(i, v),
+                _ => true,
+            };
+
+            if !keep {
+                self.remove(i);
+            }
+        }
+    }
+
+    /// Return a draining iterator that removes all elements from the slab and
+    /// yields the removed items.
+    ///
+    /// Note: Elements are removed even if the iterator is only partially
+    /// consumed or not consumed at all.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    ///
+    /// let _ = slab.insert(0);
+    /// let _ = slab.insert(1);
+    /// let _ = slab.insert(2);
+    ///
+    /// {
+    ///     let mut drain = slab.drain();
+    ///
+    ///     assert_eq!(Some(0), drain.next());
+    ///     assert_eq!(Some(1), drain.next());
+    ///     assert_eq!(Some(2), drain.next());
+    ///     assert_eq!(None, drain.next());
+    /// }
+    ///
+    /// assert!(slab.is_empty());
+    /// ```
+    pub fn drain(&mut self) -> Drain<T> {
+        self.len = 0;
+        self.next = 0;
+        Drain(self.entries.drain(..))
+    }
+}
+
+impl<T> ops::Index<usize> for Slab<T> {
+    type Output = T;
+
+    fn index(&self, key: usize) -> &T {
+        match self.entries[key] {
+            Entry::Occupied(ref v) => v,
+            _ => panic!("invalid key"),
+        }
+    }
+}
+
+impl<T> ops::IndexMut<usize> for Slab<T> {
+    fn index_mut(&mut self, key: usize) -> &mut T {
+        match self.entries[key] {
+            Entry::Occupied(ref mut v) => v,
+            _ => panic!("invalid key"),
+        }
+    }
+}
+
+impl<'a, T> IntoIterator for &'a Slab<T> {
+    type Item = (usize, &'a T);
+    type IntoIter = Iter<'a, T>;
+
+    fn into_iter(self) -> Iter<'a, T> {
+        self.iter()
+    }
+}
+
+impl<'a, T> IntoIterator for &'a mut Slab<T> {
+    type Item = (usize, &'a mut T);
+    type IntoIter = IterMut<'a, T>;
+
+    fn into_iter(self) -> IterMut<'a, T> {
+        self.iter_mut()
+    }
+}
+
+impl<T> fmt::Debug for Slab<T>
+where
+    T: fmt::Debug,
+{
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        write!(
+            fmt,
+            "Slab {{ len: {}, cap: {} }}",
+            self.len,
+            self.capacity()
+        )
+    }
+}
+
+impl<'a, T: 'a> fmt::Debug for Iter<'a, T>
+where
+    T: fmt::Debug,
+{
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        fmt.debug_struct("Iter")
+            .field("curr", &self.curr)
+            .field("remaining", &self.entries.len())
+            .finish()
+    }
+}
+
+impl<'a, T: 'a> fmt::Debug for IterMut<'a, T>
+where
+    T: fmt::Debug,
+{
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        fmt.debug_struct("IterMut")
+            .field("curr", &self.curr)
+            .field("remaining", &self.entries.len())
+            .finish()
+    }
+}
+
+impl<'a, T: 'a> fmt::Debug for Drain<'a, T> {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        fmt.debug_struct("Drain").finish()
+    }
+}
+
+// ===== VacantEntry =====
+
+impl<'a, T> VacantEntry<'a, T> {
+    /// Insert a value in the entry, returning a mutable reference to the value.
+    ///
+    /// To get the key associated with the value, use `key` prior to calling
+    /// `insert`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    ///
+    /// let hello = {
+    ///     let entry = slab.vacant_entry();
+    ///     let key = entry.key();
+    ///
+    ///     entry.insert((key, "hello"));
+    ///     key
+    /// };
+    ///
+    /// assert_eq!(hello, slab[hello].0);
+    /// assert_eq!("hello", slab[hello].1);
+    /// ```
+    pub fn insert(self, val: T) -> &'a mut T {
+        self.slab.insert_at(self.key, val);
+
+        match self.slab.entries[self.key] {
+            Entry::Occupied(ref mut v) => v,
+            _ => unreachable!(),
+        }
+    }
+
+    /// Return the key associated with this entry.
+    ///
+    /// A value stored in this entry will be associated with this key.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    ///
+    /// let hello = {
+    ///     let entry = slab.vacant_entry();
+    ///     let key = entry.key();
+    ///
+    ///     entry.insert((key, "hello"));
+    ///     key
+    /// };
+    ///
+    /// assert_eq!(hello, slab[hello].0);
+    /// assert_eq!("hello", slab[hello].1);
+    /// ```
+    pub fn key(&self) -> usize {
+        self.key
+    }
+}
+
+// ===== Iter =====
+
+impl<'a, T> Iterator for Iter<'a, T> {
+    type Item = (usize, &'a T);
+
+    fn next(&mut self) -> Option<(usize, &'a T)> {
+        while let Some(entry) = self.entries.next() {
+            let curr = self.curr;
+            self.curr += 1;
+
+            if let Entry::Occupied(ref v) = *entry {
+                return Some((curr, v));
+            }
+        }
+
+        None
+    }
+}
+
+// ===== IterMut =====
+
+impl<'a, T> Iterator for IterMut<'a, T> {
+    type Item = (usize, &'a mut T);
+
+    fn next(&mut self) -> Option<(usize, &'a mut T)> {
+        while let Some(entry) = self.entries.next() {
+            let curr = self.curr;
+            self.curr += 1;
+
+            if let Entry::Occupied(ref mut v) = *entry {
+                return Some((curr, v));
+            }
+        }
+
+        None
+    }
+}
+
+// ===== Drain =====
+
+impl<'a, T> Iterator for Drain<'a, T> {
+    type Item = T;
+
+    fn next(&mut self) -> Option<T> {
+        while let Some(entry) = self.0.next() {
+            if let Entry::Occupied(v) = entry {
+                return Some(v);
+            }
+        }
+
+        None
+    }
+}
diff --git a/tests/slab.rs b/tests/slab.rs
new file mode 100644
index 0000000..5203c95
--- /dev/null
+++ b/tests/slab.rs
@@ -0,0 +1,301 @@
+extern crate slab;
+
+use slab::*;
+
+#[test]
+fn insert_get_remove_one() {
+    let mut slab = Slab::new();
+    assert!(slab.is_empty());
+
+    let key = slab.insert(10);
+
+    assert_eq!(slab[key], 10);
+    assert_eq!(slab.get(key), Some(&10));
+    assert!(!slab.is_empty());
+    assert!(slab.contains(key));
+
+    assert_eq!(slab.remove(key), 10);
+    assert!(!slab.contains(key));
+    assert!(slab.get(key).is_none());
+}
+
+#[test]
+fn insert_get_many() {
+    let mut slab = Slab::with_capacity(10);
+
+    for i in 0..10 {
+        let key = slab.insert(i + 10);
+        assert_eq!(slab[key], i + 10);
+    }
+
+    assert_eq!(slab.capacity(), 10);
+
+    // Storing another one grows the slab
+    let key = slab.insert(20);
+    assert_eq!(slab[key], 20);
+
+    // Capacity grows by 2x
+    assert_eq!(slab.capacity(), 20);
+}
+
+#[test]
+fn insert_get_remove_many() {
+    let mut slab = Slab::with_capacity(10);
+    let mut keys = vec![];
+
+    for i in 0..10 {
+        for j in 0..10 {
+            let val = (i * 10) + j;
+
+            let key = slab.insert(val);
+            keys.push((key, val));
+            assert_eq!(slab[key], val);
+        }
+
+        for (key, val) in keys.drain(..) {
+            assert_eq!(val, slab.remove(key));
+        }
+    }
+
+    assert_eq!(10, slab.capacity());
+}
+
+#[test]
+fn insert_with_vacant_entry() {
+    let mut slab = Slab::with_capacity(1);
+    let key;
+
+    {
+        let entry = slab.vacant_entry();
+        key = entry.key();
+        entry.insert(123);
+    }
+
+    assert_eq!(123, slab[key]);
+}
+
+#[test]
+fn get_vacant_entry_without_using() {
+    let mut slab = Slab::<usize>::with_capacity(1);
+    let key = slab.vacant_entry().key();
+    assert_eq!(key, slab.vacant_entry().key());
+}
+
+#[test]
+#[should_panic]
+fn invalid_get_panics() {
+    let slab = Slab::<usize>::with_capacity(1);
+    slab[0];
+}
+
+#[test]
+#[should_panic]
+fn double_remove_panics() {
+    let mut slab = Slab::<usize>::with_capacity(1);
+    let key = slab.insert(123);
+    slab.remove(key);
+    slab.remove(key);
+}
+
+#[test]
+#[should_panic]
+fn invalid_remove_panics() {
+    let mut slab = Slab::<usize>::with_capacity(1);
+    slab.remove(0);
+}
+
+#[test]
+fn slab_get_mut() {
+    let mut slab = Slab::new();
+    let key = slab.insert(1);
+
+    slab[key] = 2;
+    assert_eq!(slab[key], 2);
+
+    *slab.get_mut(key).unwrap() = 3;
+    assert_eq!(slab[key], 3);
+}
+
+#[test]
+fn reserve_does_not_allocate_if_available() {
+    let mut slab = Slab::with_capacity(10);
+    let mut keys = vec![];
+
+    for i in 0..6 {
+        keys.push(slab.insert(i));
+    }
+
+    for key in 0..4 {
+        slab.remove(key);
+    }
+
+    assert!(slab.capacity() - slab.len() == 8);
+
+    slab.reserve(8);
+    assert_eq!(10, slab.capacity());
+}
+
+#[test]
+fn reserve_exact_does_not_allocate_if_available() {
+    let mut slab = Slab::with_capacity(10);
+    let mut keys = vec![];
+
+    for i in 0..6 {
+        keys.push(slab.insert(i));
+    }
+
+    for key in 0..4 {
+        slab.remove(key);
+    }
+
+    assert!(slab.capacity() - slab.len() == 8);
+
+    slab.reserve(8);
+    assert_eq!(10, slab.capacity());
+}
+
+#[test]
+fn retain() {
+    let mut slab = Slab::with_capacity(2);
+
+    let key1 = slab.insert(0);
+    let key2 = slab.insert(1);
+
+    slab.retain(|key, x| {
+        assert_eq!(key, *x);
+        *x % 2 == 0
+    });
+
+    assert_eq!(slab.len(), 1);
+    assert_eq!(slab[key1], 0);
+    assert!(!slab.contains(key2));
+
+    // Ensure consistency is retained
+    let key = slab.insert(123);
+    assert_eq!(key, key2);
+
+    assert_eq!(2, slab.len());
+    assert_eq!(2, slab.capacity());
+
+    // Inserting another element grows
+    let key = slab.insert(345);
+    assert_eq!(key, 2);
+
+    assert_eq!(4, slab.capacity());
+}
+
+#[test]
+fn iter() {
+    let mut slab = Slab::new();
+
+    for i in 0..4 {
+        slab.insert(i);
+    }
+
+    let vals: Vec<_> = slab
+        .iter()
+        .enumerate()
+        .map(|(i, (key, val))| {
+            assert_eq!(i, key);
+            *val
+        })
+        .collect();
+    assert_eq!(vals, vec![0, 1, 2, 3]);
+
+    slab.remove(1);
+
+    let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
+    assert_eq!(vals, vec![0, 2, 3]);
+}
+
+#[test]
+fn iter_mut() {
+    let mut slab = Slab::new();
+
+    for i in 0..4 {
+        slab.insert(i);
+    }
+
+    for (i, (key, e)) in slab.iter_mut().enumerate() {
+        assert_eq!(i, key);
+        *e = *e + 1;
+    }
+
+    let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
+    assert_eq!(vals, vec![1, 2, 3, 4]);
+
+    slab.remove(2);
+
+    for (_, e) in slab.iter_mut() {
+        *e = *e + 1;
+    }
+
+    let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
+    assert_eq!(vals, vec![2, 3, 5]);
+}
+
+#[test]
+fn clear() {
+    let mut slab = Slab::new();
+
+    for i in 0..4 {
+        slab.insert(i);
+    }
+
+    // clear full
+    slab.clear();
+
+    let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
+    assert!(vals.is_empty());
+
+    assert_eq!(0, slab.len());
+    assert_eq!(4, slab.capacity());
+
+    for i in 0..2 {
+        slab.insert(i);
+    }
+
+    let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
+    assert_eq!(vals, vec![0, 1]);
+
+    // clear half-filled
+    slab.clear();
+
+    let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
+    assert!(vals.is_empty());
+}
+
+#[test]
+fn fully_consumed_drain() {
+    let mut slab = Slab::new();
+
+    for i in 0..3 {
+        slab.insert(i);
+    }
+
+    {
+        let mut drain = slab.drain();
+        assert_eq!(Some(0), drain.next());
+        assert_eq!(Some(1), drain.next());
+        assert_eq!(Some(2), drain.next());
+        assert_eq!(None, drain.next());
+    }
+
+    assert!(slab.is_empty());
+}
+
+#[test]
+fn partially_consumed_drain() {
+    let mut slab = Slab::new();
+
+    for i in 0..3 {
+        slab.insert(i);
+    }
+
+    {
+        let mut drain = slab.drain();
+        assert_eq!(Some(0), drain.next());
+    }
+
+    assert!(slab.is_empty())
+}