mycelium_experimental/

map.rs

use std::fmt;
use std::mem::ManuallyDrop;
use std::ptr;

use crate::base::{self};
use epoch;

/// A map based on a lock-free skip list.
pub struct SkipMap {
    inner: base::SkipList,
}

impl SkipMap {
    /// Returns a new, empty map.
    pub fn new() -> SkipMap {
        SkipMap {
            inner: base::SkipList::new(epoch::default_collector().clone()),
        }
    }

    /// Returns `true` if the map is empty.
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }

    /// Returns the number of entries in the map.
    ///
    /// If the map is being concurrently modified, consider the returned number just an
    /// approximation without any guarantees.
    pub fn len(&self) -> usize {
        self.inner.len()
    }
}

/*
impl SkipMap
{
    /// Returns the entry with the smallest key.
    pub fn front(&self) -> Option<Entry> {
        let guard = &epoch::pin();
        try_pin_loop(move || self.inner.front(guard)).map(Entry::new)
    }

    /// Returns the entry with the largest key.
    pub fn back(&self) -> Option<Entry> {
        let guard = &epoch::pin();
        try_pin_loop(move || self.inner.back(guard)).map(Entry::new)
    }

    /// Returns `true` if the map contains a value for the specified key.
    pub fn contains_key<Q>(&self, key: [u8; 16]) -> bool
        where
            Q: Ord + ?Sized,
    {
        let guard = &epoch::pin();
        self.inner.contains_key(key, guard)
    }

    /// Returns an entry with the specified `key`.
    pub fn get<Q>(&self, key: [u8;16]) -> Option<Entry>
        where
            Q: Ord + ?Sized,
    {
        let guard = &epoch::pin();
        try_pin_loop(|| self.inner.get(key, guard)).map(Entry::new)
    }

    /// Returns an `Entry` pointing to the lowest element whose key is above
    /// the given bound. If no such element is found then `None` is
    /// returned.
    pub fn lower_bound<'a>(&'a self, bound: Bound<[u8;16]>) -> Option<Entry>
    {
        let guard = &epoch::pin();
        try_pin_loop(|| self.inner.lower_bound(bound, guard)).map(Entry::new)
    }

    /// Returns an `Entry` pointing to the highest element whose key is below
    /// the given bound. If no such element is found then `None` is
    /// returned.
    pub fn upper_bound<'a>(&'a self, bound: Bound<[u8;16]>) -> Option<Entry>
    {
        let guard = &epoch::pin();
        try_pin_loop(|| self.inner.upper_bound(bound, guard)).map(Entry::new)
    }

    /// Finds an entry with the specified key, or inserts a new `key`-`value` pair if none exist.
    pub fn get_or_insert(&self, key: [u8;16], value: Vec<u8>) -> Entry {
        let guard = &epoch::pin();
        Entry::new(self.inner.get_or_insert(key, value, guard))
    }

    /// Returns an iterator over all entries in the map.
    pub fn iter(&self) -> Iter {
        Iter {
            inner: self.inner.ref_iter(),
        }
    }

    /*
    /// Returns an iterator over a subset of entries in the skip list.
    pub fn range(
        &self,
        range: ([u8;16], [u8;16]),
    ) -> Range
    {
        Range {
            inner: self.inner.ref_range(range),
        }
    }
    */
}
*/

/*
impl SkipMap
{
    /// Inserts a `key`-`value` pair into the map and returns the new entry.
    ///
    /// If there is an existing entry with this key, it will be removed before inserting the new
    /// one.
    pub fn insert(&self, key: [u8;16], value: Vec<u8>) -> Entry {
        let guard = &epoch::pin();
        Entry::new(self.inner.insert(key, value, guard))
    }

    /// Removes an entry with the specified `key` from the map and returns it.
    pub fn remove(&self, key: [u8;16]) -> Option<Entry>
    {
        let guard = &epoch::pin();
        self.inner.remove(key, guard).map(Entry::new)
    }

    /// Removes an entry from the front of the map.
    pub fn pop_front(&self) -> Option<Entry> {
        let guard = &epoch::pin();
        self.inner.pop_front(guard).map(Entry::new)
    }

    /// Removes an entry from the back of the map.
    pub fn pop_back(&self) -> Option<Entry> {
        let guard = &epoch::pin();
        self.inner.pop_back(guard).map(Entry::new)
    }

    /// Iterates over the map and removes every entry.
    pub fn clear(&self) {
        let guard = &mut epoch::pin();
        self.inner.clear(guard);
    }
}

impl Default for SkipMap {
    fn default() -> SkipMap {
        SkipMap::new()
    }
}

impl fmt::Debug for SkipMap
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.pad("SkipMap { .. }")
    }
}
*/

impl IntoIterator for SkipMap {
    type Item = ([u8;16], Vec<u8>);
    type IntoIter = IntoIter;

    fn into_iter(self) -> IntoIter {
        IntoIter {
            inner: self.inner.into_iter(),
        }
    }
}

/*
impl<'a> IntoIterator for &'a SkipMap
{
    type Item = Entry<'a>;
    type IntoIter = Iter<'a>;

    fn into_iter(self) -> Iter<'a> {
        self.iter()
    }
}
*/

/*
impl FromIterator<([u8;16], Vec<u8>)> for SkipMap
{
    fn from_iter<I>(iter: I) -> SkipMap
        where
            I: IntoIterator<Item = ([u8;16], Vec<u8>)>,
    {
        let s = SkipMap::new();
        for (k, v) in iter {
            s.get_or_insert(k, v);
        }
        s
    }
}
*/

/// A reference-counted entry in a map.
pub struct Entry<'a> {
    inner: ManuallyDrop<base::RefEntry<'a>>,
}

impl<'a> Entry<'a> {
    fn new(inner: base::RefEntry) -> Entry {
        Entry { inner: ManuallyDrop::new(inner) }
    }

    /// Returns a reference to the key.
    pub fn key(&self) -> [u8;16] {
        self.inner.key()
    }

    /// Returns a reference to the value.
    pub fn value(&self) -> &Vec<u8> {
        self.inner.value()
    }

    /// Returns `true` if the entry is removed from the map.
    pub fn is_removed(&self) -> bool {
        self.inner.is_removed()
    }
}

impl<'a> Drop for Entry<'a>
{
    fn drop(&mut self) {
        unsafe {
            ManuallyDrop::into_inner(ptr::read(&mut self.inner))
                .release_with_pin(|| epoch::pin());
        }
    }
}

impl<'a> Entry<'a>
{
    /// Moves to the next entry in the map.
    pub fn move_next(&mut self) -> bool {
        let guard = &epoch::pin();
        self.inner.move_next(guard)
    }

    /// Moves to the previous entry in the map.
    pub fn move_prev(&mut self) -> bool {
        let guard = &epoch::pin();
        self.inner.move_prev(guard)
    }

    /// Returns the next entry in the map.
    pub fn next(&self) -> Option<Entry> {
        let guard = &epoch::pin();
        self.inner.next(guard).map(Entry::new)
    }

    /// Returns the previous entry in the map.
    pub fn prev(&self) -> Option<Entry> {
        let guard = &epoch::pin();
        self.inner.prev(guard).map(Entry::new)
    }
}

impl<'a> Entry<'a>
{
    /// Removes the entry from the map.
    ///
    /// Returns `true` if this call removed the entry and `false` if it was already removed.
    pub fn remove(&self) -> bool {
        let guard = &epoch::pin();
        self.inner.remove(guard)
    }
}

impl<'a> Clone for Entry<'a> {
    fn clone(&self) -> Entry<'a> {
        Entry {
            inner: self.inner.clone(),
        }
    }
}

impl<'a> fmt::Debug for Entry<'a>
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.debug_tuple("Entry")
            .field(&self.key())
            .field(self.value())
            .finish()
    }
}

/// An owning iterator over the entries of a `SkipMap`.
pub struct IntoIter {
    inner: base::IntoIter,
}

impl Iterator for IntoIter {
    type Item = ([u8;16], Vec<u8>);

    fn next(&mut self) -> Option<([u8;16], Vec<u8>)> {
        self.inner.next()
    }
}

impl fmt::Debug for IntoIter {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.pad("IntoIter { .. }")
    }
}

/// An iterator over the entries of a `SkipMap`.
#[allow(dead_code)]
pub struct Iter<'a> {
    inner: base::RefIter<'a>,
}
/*
impl<'a> Iterator for Iter<'a>
{
    type Item = Entry<'a>;

    fn next(&mut self) -> Option<Entry<'a>> {
        let guard = &epoch::pin();
        self.inner.next(guard).map(Entry::new)
    }
}

impl<'a> DoubleEndedIterator for Iter<'a>
{
    fn next_back(&mut self) -> Option<Entry<'a>> {
        let guard = &epoch::pin();
        self.inner.next_back(guard).map(Entry::new)
    }
}
*/

impl<'a> fmt::Debug for Iter<'a> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.pad("Iter { .. }")
    }
}

/*
/// An iterator over the entries of a `SkipMap`.
pub struct Range<'a>
{
    pub(crate) inner: base::RefRange<'a>,
}
*/
/*
impl<'a> Iterator for Range<'a>
{
    type Item = Entry<'a>;

    fn next(&mut self) -> Option<Entry<'a>> {
        let guard = &epoch::pin();
        self.inner.next(guard).map(Entry::new)
    }
}

impl<'a> DoubleEndedIterator for Range<'a>
{
    fn next_back(&mut self) -> Option<Entry<'a>> {
        let guard = &epoch::pin();
        self.inner.next_back(guard).map(Entry::new)
    }
}

impl<'a> fmt::Debug for Range<'a>
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.debug_struct("Range")
            .field("range", &self.inner.range)
            .field("head", &self.inner.head)
            .field("tail", &self.inner.tail)
            .finish()
    }
}
*/