aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/lib.rs604
-rw-r--r--src/serde.rs91
2 files changed, 633 insertions, 62 deletions
diff --git a/src/lib.rs b/src/lib.rs
index a3638ca..6b433af 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,6 +1,6 @@
-#![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))]
+#![warn(missing_docs, missing_debug_implementations)]
+#![cfg_attr(test, warn(unreachable_pub))]
+#![cfg_attr(not(feature = "std"), no_std)]
//! Pre-allocated storage for a uniform data type.
//!
@@ -102,10 +102,26 @@
//!
//! [`Slab::with_capacity`]: struct.Slab.html#with_capacity
-use std::iter::IntoIterator;
-use std::ops;
+#[cfg(not(feature = "std"))]
+extern crate alloc;
+#[cfg(feature = "std")]
+extern crate core;
+
+#[cfg(feature = "serde")]
+mod serde;
+
+#[cfg(not(feature = "std"))]
+use alloc::vec::Vec;
+
+#[cfg(not(feature = "std"))]
+use alloc::vec;
+
+use core::iter::FromIterator;
+
+use core::{fmt, mem, ops, slice};
+
+#[cfg(feature = "std")]
use std::vec;
-use std::{fmt, mem};
/// Pre-allocated storage for a uniform data type
///
@@ -159,15 +175,21 @@ pub struct VacantEntry<'a, T: 'a> {
key: usize,
}
+/// A consuming iterator over the values stored in a `Slab`
+pub struct IntoIter<T> {
+ entries: vec::IntoIter<Entry<T>>,
+ curr: usize,
+}
+
/// An iterator over the values stored in the `Slab`
pub struct Iter<'a, T: 'a> {
- entries: std::slice::Iter<'a, Entry<T>>,
+ entries: 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>>,
+ entries: slice::IterMut<'a, Entry<T>>,
curr: usize,
}
@@ -274,7 +296,7 @@ impl<T> Slab<T> {
if self.capacity() - self.len >= additional {
return;
}
- let need_add = self.len + additional - self.entries.len();
+ let need_add = additional - (self.entries.len() - self.len);
self.entries.reserve(need_add);
}
@@ -308,16 +330,19 @@ impl<T> Slab<T> {
if self.capacity() - self.len >= additional {
return;
}
- let need_add = self.len + additional - self.entries.len();
+ let need_add = additional - (self.entries.len() - self.len);
self.entries.reserve_exact(need_add);
}
- /// Shrink the capacity of the slab as much as possible.
+ /// Shrink the capacity of the slab as much as possible without invalidating keys.
///
- /// 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.
+ /// Because values cannot be moved to a different index, the slab cannot
+ /// shrink past any stored values.
+ /// It will drop down as close as possible to the length but the allocator may
+ /// still inform the underlying vector that there is space for a few more elements.
+ ///
+ /// This function can take O(n) time even when the capacity cannot be reduced
+ /// or the allocation is shrunk in place. Repeated calls run in O(1) though.
///
/// # Examples
///
@@ -329,33 +354,171 @@ impl<T> Slab<T> {
/// slab.insert(i);
/// }
///
- /// assert_eq!(slab.capacity(), 10);
/// slab.shrink_to_fit();
- /// assert!(slab.capacity() >= 3);
+ /// assert!(slab.capacity() >= 3 && slab.capacity() < 10);
/// ```
///
- /// In this case, even though two values are removed, the slab cannot shrink
- /// past the last value.
+ /// The slab cannot shrink past the last present value even if previous
+ /// values are removed:
///
/// ```
/// # use slab::*;
/// let mut slab = Slab::with_capacity(10);
///
- /// for i in 0..3 {
+ /// for i in 0..4 {
/// slab.insert(i);
/// }
///
/// slab.remove(0);
- /// slab.remove(1);
+ /// slab.remove(3);
///
- /// assert_eq!(slab.capacity(), 10);
/// slab.shrink_to_fit();
- /// assert!(slab.capacity() >= 3);
+ /// assert!(slab.capacity() >= 3 && slab.capacity() < 10);
/// ```
pub fn shrink_to_fit(&mut self) {
+ // Remove all vacant entries after the last occupied one, so that
+ // the capacity can be reduced to what is actually needed.
+ // If the slab is empty the vector can simply be cleared, but that
+ // optimization would not affect time complexity when T: Drop.
+ let len_before = self.entries.len();
+ while let Some(&Entry::Vacant(_)) = self.entries.last() {
+ self.entries.pop();
+ }
+
+ // Removing entries breaks the list of vacant entries,
+ // so it must be repaired
+ if self.entries.len() != len_before {
+ // Some vacant entries were removed, so the list now likely¹
+ // either contains references to the removed entries, or has an
+ // invalid end marker. Fix this by recreating the list.
+ self.recreate_vacant_list();
+ // ¹: If the removed entries formed the tail of the list, with the
+ // most recently popped entry being the head of them, (so that its
+ // index is now the end marker) the list is still valid.
+ // Checking for that unlikely scenario of this infrequently called
+ // is not worth the code complexity.
+ }
+
self.entries.shrink_to_fit();
}
+ /// Iterate through all entries to recreate and repair the vacant list.
+ /// self.len must be correct and is not modified.
+ fn recreate_vacant_list(&mut self) {
+ self.next = self.entries.len();
+ // We can stop once we've found all vacant entries
+ let mut remaining_vacant = self.entries.len() - self.len;
+ // Iterate in reverse order so that lower keys are at the start of
+ // the vacant list. This way future shrinks are more likely to be
+ // able to remove vacant entries.
+ for (i, entry) in self.entries.iter_mut().enumerate().rev() {
+ if remaining_vacant == 0 {
+ break;
+ }
+ if let Entry::Vacant(ref mut next) = *entry {
+ *next = self.next;
+ self.next = i;
+ remaining_vacant -= 1;
+ }
+ }
+ }
+
+ /// Reduce the capacity as much as possible, changing the key for elements when necessary.
+ ///
+ /// To allow updating references to the elements which must be moved to a new key,
+ /// this function takes a closure which is called before moving each element.
+ /// The second and third parameters to the closure are the current key and
+ /// new key respectively.
+ /// In case changing the key for one element turns out not to be possible,
+ /// the move can be cancelled by returning `false` from the closure.
+ /// In that case no further attempts at relocating elements is made.
+ /// If the closure unwinds, the slab will be left in a consistent state,
+ /// but the value that the closure panicked on might be removed.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use slab::*;
+ ///
+ /// let mut slab = Slab::with_capacity(10);
+ /// let a = slab.insert('a');
+ /// slab.insert('b');
+ /// slab.insert('c');
+ /// slab.remove(a);
+ /// slab.compact(|&mut value, from, to| {
+ /// assert_eq!((value, from, to), ('c', 2, 0));
+ /// true
+ /// });
+ /// assert!(slab.capacity() >= 2 && slab.capacity() < 10);
+ /// ```
+ ///
+ /// The value is not moved when the closure returns `Err`:
+ ///
+ /// ```
+ /// # use slab::*;
+ ///
+ /// let mut slab = Slab::with_capacity(100);
+ /// let a = slab.insert('a');
+ /// let b = slab.insert('b');
+ /// slab.remove(a);
+ /// slab.compact(|&mut value, from, to| false);
+ /// assert_eq!(slab.iter().next(), Some((b, &'b')));
+ /// ```
+ pub fn compact<F>(&mut self, mut rekey: F)
+ where
+ F: FnMut(&mut T, usize, usize) -> bool,
+ {
+ // If the closure unwinds, we need to restore a valid list of vacant entries
+ struct CleanupGuard<'a, T: 'a> {
+ slab: &'a mut Slab<T>,
+ decrement: bool,
+ }
+ impl<'a, T: 'a> Drop for CleanupGuard<'a, T> {
+ fn drop(&mut self) {
+ if self.decrement {
+ // Value was popped and not pushed back on
+ self.slab.len -= 1;
+ }
+ self.slab.recreate_vacant_list();
+ }
+ }
+ let mut guard = CleanupGuard {
+ slab: self,
+ decrement: true,
+ };
+
+ let mut occupied_until = 0;
+ // While there are vacant entries
+ while guard.slab.entries.len() > guard.slab.len {
+ // Find a value that needs to be moved,
+ // by popping entries until we find an occopied one.
+ // (entries cannot be empty because 0 is not greater than anything)
+ if let Some(Entry::Occupied(mut value)) = guard.slab.entries.pop() {
+ // Found one, now find a vacant entry to move it to
+ while let Some(&Entry::Occupied(_)) = guard.slab.entries.get(occupied_until) {
+ occupied_until += 1;
+ }
+ // Let the caller try to update references to the key
+ if !rekey(&mut value, guard.slab.entries.len(), occupied_until) {
+ // Changing the key failed, so push the entry back on at its old index.
+ guard.slab.entries.push(Entry::Occupied(value));
+ guard.decrement = false;
+ guard.slab.entries.shrink_to_fit();
+ return;
+ // Guard drop handles cleanup
+ }
+ // Put the value in its new spot
+ guard.slab.entries[occupied_until] = Entry::Occupied(value);
+ // ... and mark it as occupied (this is optional)
+ occupied_until += 1;
+ }
+ }
+ guard.slab.next = guard.slab.len;
+ guard.slab.entries.shrink_to_fit();
+ // Normal cleanup is not necessary
+ mem::forget(guard);
+ }
+
/// Clear the slab of all values.
///
/// # Examples
@@ -520,11 +683,62 @@ impl<T> Slab<T> {
}
}
+ /// Return two mutable references to the values associated with the two
+ /// given keys simultaneously.
+ ///
+ /// If any one of the given keys is not associated with a value, then `None`
+ /// is returned.
+ ///
+ /// This function can be used to get two mutable references out of one slab,
+ /// so that you can manipulate both of them at the same time, eg. swap them.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use slab::*;
+ /// use std::mem;
+ ///
+ /// let mut slab = Slab::new();
+ /// let key1 = slab.insert(1);
+ /// let key2 = slab.insert(2);
+ /// let (value1, value2) = slab.get2_mut(key1, key2).unwrap();
+ /// mem::swap(value1, value2);
+ /// assert_eq!(slab[key1], 2);
+ /// assert_eq!(slab[key2], 1);
+ /// ```
+ pub fn get2_mut(&mut self, key1: usize, key2: usize) -> Option<(&mut T, &mut T)> {
+ assert!(key1 != key2);
+
+ let (entry1, entry2);
+
+ if key1 > key2 {
+ let (slice1, slice2) = self.entries.split_at_mut(key1);
+ entry1 = slice2.get_mut(0);
+ entry2 = slice1.get_mut(key2);
+ } else {
+ let (slice1, slice2) = self.entries.split_at_mut(key2);
+ entry1 = slice1.get_mut(key1);
+ entry2 = slice2.get_mut(0);
+ }
+
+ match (entry1, entry2) {
+ (
+ Some(&mut Entry::Occupied(ref mut val1)),
+ Some(&mut Entry::Occupied(ref mut val2)),
+ ) => Some((val1, val2)),
+ _ => None,
+ }
+ }
+
/// Return a reference to the value associated with the given key without
/// performing bounds checking.
///
/// This function should be used with care.
///
+ /// # Safety
+ ///
+ /// The key must be within bounds.
+ ///
/// # Examples
///
/// ```
@@ -548,6 +762,10 @@ impl<T> Slab<T> {
///
/// This function should be used with care.
///
+ /// # Safety
+ ///
+ /// The key must be within bounds.
+ ///
/// # Examples
///
/// ```
@@ -569,6 +787,93 @@ impl<T> Slab<T> {
}
}
+ /// Return two mutable references to the values associated with the two
+ /// given keys simultaneously without performing bounds checking and safety
+ /// condition checking.
+ ///
+ /// This function should be used with care.
+ ///
+ /// # Safety
+ ///
+ /// - Both keys must be within bounds.
+ /// - The condition `key1 != key2` must hold.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use slab::*;
+ /// use std::mem;
+ ///
+ /// let mut slab = Slab::new();
+ /// let key1 = slab.insert(1);
+ /// let key2 = slab.insert(2);
+ /// let (value1, value2) = unsafe { slab.get2_unchecked_mut(key1, key2) };
+ /// mem::swap(value1, value2);
+ /// assert_eq!(slab[key1], 2);
+ /// assert_eq!(slab[key2], 1);
+ /// ```
+ pub unsafe fn get2_unchecked_mut(&mut self, key1: usize, key2: usize) -> (&mut T, &mut T) {
+ let ptr1 = self.entries.get_unchecked_mut(key1) as *mut Entry<T>;
+ let ptr2 = self.entries.get_unchecked_mut(key2) as *mut Entry<T>;
+ match (&mut *ptr1, &mut *ptr2) {
+ (&mut Entry::Occupied(ref mut val1), &mut Entry::Occupied(ref mut val2)) => {
+ (val1, val2)
+ }
+ _ => unreachable!(),
+ }
+ }
+
+ /// Get the key for an element in the slab.
+ ///
+ /// The reference must point to an element owned by the slab.
+ /// Otherwise this function will panic.
+ /// This is a constant-time operation because the key can be calculated
+ /// from the reference with pointer arithmetic.
+ ///
+ /// # Panics
+ ///
+ /// This function will panic if the reference does not point to an element
+ /// of the slab.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use slab::*;
+ ///
+ /// let mut slab = Slab::new();
+ /// let key = slab.insert(String::from("foo"));
+ /// let value = &slab[key];
+ /// assert_eq!(slab.key_of(value), key);
+ /// ```
+ ///
+ /// Values are not compared, so passing a reference to a different locaton
+ /// will result in a panic:
+ ///
+ /// ```should_panic
+ /// # use slab::*;
+ ///
+ /// let mut slab = Slab::new();
+ /// let key = slab.insert(0);
+ /// let bad = &0;
+ /// slab.key_of(bad); // this will panic
+ /// unreachable!();
+ /// ```
+ pub fn key_of(&self, present_element: &T) -> usize {
+ let element_ptr = present_element as *const T as usize;
+ let base_ptr = self.entries.as_ptr() as usize;
+ // Use wrapping subtraction in case the reference is bad
+ let byte_offset = element_ptr.wrapping_sub(base_ptr);
+ // The division rounds away any offset of T inside Entry
+ // The size of Entry<T> is never zero even if T is due to Vacant(usize)
+ let key = byte_offset / mem::size_of::<Entry<T>>();
+ // Prevent returning unspecified (but out of bounds) values
+ if key >= self.entries.len() {
+ panic!("The reference points to a value outside this slab");
+ }
+ // The reference cannot point to a vacant entry, because then it would not be valid
+ key
+ }
+
/// 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
@@ -632,14 +937,11 @@ impl<T> Slab<T> {
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;
- }
+ self.next = match self.entries.get(key) {
+ Some(&Entry::Vacant(next)) => next,
_ => unreachable!(),
- }
+ };
+ self.entries[key] = Entry::Occupied(val);
}
}
@@ -664,21 +966,23 @@ impl<T> Slab<T> {
/// 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");
+ if let Some(entry) = self.entries.get_mut(key) {
+ // Swap the entry at the provided value
+ let prev = mem::replace(entry, Entry::Vacant(self.next));
+
+ match prev {
+ Entry::Occupied(val) => {
+ self.len -= 1;
+ self.next = key;
+ return val;
+ }
+ _ => {
+ // Woops, the entry is actually vacant, restore the state
+ *entry = prev;
+ }
}
}
+ panic!("invalid key");
}
/// Return `true` if a value is associated with the given key.
@@ -697,13 +1001,10 @@ impl<T> Slab<T> {
/// 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)
+ match self.entries.get(key) {
+ Some(&Entry::Occupied(_)) => true,
+ _ => false,
+ }
}
/// Retain only the elements specified by the predicate.
@@ -784,8 +1085,8 @@ 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,
+ match self.entries.get(key) {
+ Some(&Entry::Occupied(ref v)) => v,
_ => panic!("invalid key"),
}
}
@@ -793,13 +1094,25 @@ impl<T> ops::Index<usize> for Slab<T> {
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,
+ match self.entries.get_mut(key) {
+ Some(&mut Entry::Occupied(ref mut v)) => v,
_ => panic!("invalid key"),
}
}
}
+impl<T> IntoIterator for Slab<T> {
+ type Item = (usize, T);
+ type IntoIter = IntoIter<T>;
+
+ fn into_iter(self) -> IntoIter<T> {
+ IntoIter {
+ entries: self.entries.into_iter(),
+ curr: 0,
+ }
+ }
+}
+
impl<'a, T> IntoIterator for &'a Slab<T> {
type Item = (usize, &'a T);
type IntoIter = Iter<'a, T>;
@@ -818,17 +1131,98 @@ impl<'a, T> IntoIterator for &'a mut Slab<T> {
}
}
+/// Create a slab from an iterator of key-value pairs.
+///
+/// If the iterator produces duplicate keys, the previous value is replaced with the later one.
+/// The keys does not need to be sorted beforehand, and this function always
+/// takes O(n) time.
+/// Note that the returned slab will use space proportional to the largest key,
+/// so don't use `Slab` with untrusted keys.
+///
+/// # Examples
+///
+/// ```
+/// # use slab::*;
+///
+/// let vec = vec![(2,'a'), (6,'b'), (7,'c')];
+/// let slab = vec.into_iter().collect::<Slab<char>>();
+/// assert_eq!(slab.len(), 3);
+/// assert!(slab.capacity() >= 8);
+/// assert_eq!(slab[2], 'a');
+/// ```
+///
+/// With duplicate and unsorted keys:
+///
+/// ```
+/// # use slab::*;
+///
+/// let vec = vec![(20,'a'), (10,'b'), (11,'c'), (10,'d')];
+/// let slab = vec.into_iter().collect::<Slab<char>>();
+/// assert_eq!(slab.len(), 3);
+/// assert_eq!(slab[10], 'd');
+/// ```
+impl<T> FromIterator<(usize, T)> for Slab<T> {
+ fn from_iter<I>(iterable: I) -> Self
+ where
+ I: IntoIterator<Item = (usize, T)>,
+ {
+ let iterator = iterable.into_iter();
+ let mut slab = Self::with_capacity(iterator.size_hint().0);
+
+ let mut vacant_list_broken = false;
+ for (key, value) in iterator {
+ if key < slab.entries.len() {
+ // iterator is not sorted, might need to recreate vacant list
+ if let Entry::Vacant(_) = slab.entries[key] {
+ vacant_list_broken = true;
+ slab.len += 1;
+ }
+ // if an element with this key already exists, replace it.
+ // This is consisent with HashMap and BtreeMap
+ slab.entries[key] = Entry::Occupied(value);
+ } else {
+ // insert holes as necessary
+ while slab.entries.len() < key {
+ // add the entry to the start of the vacant list
+ let next = slab.next;
+ slab.next = slab.entries.len();
+ slab.entries.push(Entry::Vacant(next));
+ }
+ slab.entries.push(Entry::Occupied(value));
+ slab.len += 1;
+ }
+ }
+ if slab.len == slab.entries.len() {
+ // no vacant enries, so next might not have been updated
+ slab.next = slab.entries.len();
+ } else if vacant_list_broken {
+ slab.recreate_vacant_list();
+ }
+ slab
+ }
+}
+
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()
- )
+ fmt.debug_struct("Slab")
+ .field("len", &self.len)
+ .field("cap", &self.capacity())
+ .finish()
+ }
+}
+
+impl<T> fmt::Debug for IntoIter<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()
}
}
@@ -890,8 +1284,8 @@ impl<'a, T> VacantEntry<'a, T> {
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,
+ match self.slab.entries.get_mut(self.key) {
+ Some(&mut Entry::Occupied(ref mut v)) => v,
_ => unreachable!(),
}
}
@@ -922,6 +1316,42 @@ impl<'a, T> VacantEntry<'a, T> {
}
}
+// ===== IntoIter =====
+
+impl<T> Iterator for IntoIter<T> {
+ type Item = (usize, T);
+
+ fn next(&mut self) -> Option<(usize, T)> {
+ while let Some(entry) = self.entries.next() {
+ let curr = self.curr;
+ self.curr += 1;
+
+ if let Entry::Occupied(v) = entry {
+ return Some((curr, v));
+ }
+ }
+
+ None
+ }
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (0, Some(self.entries.len()))
+ }
+}
+
+impl<T> DoubleEndedIterator for IntoIter<T> {
+ fn next_back(&mut self) -> Option<(usize, T)> {
+ while let Some(entry) = self.entries.next_back() {
+ if let Entry::Occupied(v) = entry {
+ let key = self.curr + self.entries.len();
+ return Some((key, v));
+ }
+ }
+
+ None
+ }
+}
+
// ===== Iter =====
impl<'a, T> Iterator for Iter<'a, T> {
@@ -939,6 +1369,23 @@ impl<'a, T> Iterator for Iter<'a, T> {
None
}
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (0, Some(self.entries.len()))
+ }
+}
+
+impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
+ fn next_back(&mut self) -> Option<(usize, &'a T)> {
+ while let Some(entry) = self.entries.next_back() {
+ if let Entry::Occupied(ref v) = *entry {
+ let key = self.curr + self.entries.len();
+ return Some((key, v));
+ }
+ }
+
+ None
+ }
}
// ===== IterMut =====
@@ -958,6 +1405,23 @@ impl<'a, T> Iterator for IterMut<'a, T> {
None
}
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (0, Some(self.entries.len()))
+ }
+}
+
+impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
+ fn next_back(&mut self) -> Option<(usize, &'a mut T)> {
+ while let Some(entry) = self.entries.next_back() {
+ if let Entry::Occupied(ref mut v) = *entry {
+ let key = self.curr + self.entries.len();
+ return Some((key, v));
+ }
+ }
+
+ None
+ }
}
// ===== Drain =====
@@ -974,4 +1438,20 @@ impl<'a, T> Iterator for Drain<'a, T> {
None
}
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (0, Some(self.0.len()))
+ }
+}
+
+impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
+ fn next_back(&mut self) -> Option<T> {
+ while let Some(entry) = self.0.next_back() {
+ if let Entry::Occupied(v) = entry {
+ return Some(v);
+ }
+ }
+
+ None
+ }
}
diff --git a/src/serde.rs b/src/serde.rs
new file mode 100644
index 0000000..4fb18e9
--- /dev/null
+++ b/src/serde.rs
@@ -0,0 +1,91 @@
+extern crate serde;
+
+use core::fmt;
+use core::marker::PhantomData;
+
+use self::serde::de::{Deserialize, Deserializer, MapAccess, Visitor};
+use self::serde::ser::{Serialize, SerializeMap, Serializer};
+
+use super::{Entry, Slab};
+
+impl<T> Serialize for Slab<T>
+where
+ T: Serialize,
+{
+ fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+ where
+ S: Serializer,
+ {
+ let mut map_serializer = serializer.serialize_map(Some(self.len()))?;
+ for (key, value) in self {
+ map_serializer.serialize_key(&key)?;
+ map_serializer.serialize_value(value)?;
+ }
+ map_serializer.end()
+ }
+}
+
+struct SlabVisitor<T>(PhantomData<T>);
+
+impl<'de, T> Visitor<'de> for SlabVisitor<T>
+where
+ T: Deserialize<'de>,
+{
+ type Value = Slab<T>;
+
+ fn expecting(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+ write!(fmt, "a map")
+ }
+
+ fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
+ where
+ A: MapAccess<'de>,
+ {
+ let mut slab = Slab::with_capacity(map.size_hint().unwrap_or(0));
+
+ // same as FromIterator impl
+ let mut vacant_list_broken = false;
+ while let Some((key, value)) = map.next_entry()? {
+ if key < slab.entries.len() {
+ // iterator is not sorted, might need to recreate vacant list
+ if let Entry::Vacant(_) = slab.entries[key] {
+ vacant_list_broken = true;
+ slab.len += 1;
+ }
+ // if an element with this key already exists, replace it.
+ // This is consisent with HashMap and BtreeMap
+ slab.entries[key] = Entry::Occupied(value);
+ } else {
+ // insert holes as necessary
+ while slab.entries.len() < key {
+ // add the entry to the start of the vacant list
+ let next = slab.next;
+ slab.next = slab.entries.len();
+ slab.entries.push(Entry::Vacant(next));
+ }
+ slab.entries.push(Entry::Occupied(value));
+ slab.len += 1;
+ }
+ }
+ if slab.len == slab.entries.len() {
+ // no vacant enries, so next might not have been updated
+ slab.next = slab.entries.len();
+ } else if vacant_list_broken {
+ slab.recreate_vacant_list();
+ }
+
+ Ok(slab)
+ }
+}
+
+impl<'de, T> Deserialize<'de> for Slab<T>
+where
+ T: Deserialize<'de>,
+{
+ fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+ where
+ D: Deserializer<'de>,
+ {
+ deserializer.deserialize_map(SlabVisitor(PhantomData))
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-02 05:01:21 +0000