crossbeam-rs / crossbeam-skiplist Goto Github PK

As a first step, I'm thinking we should publicly expose base::SkipList and present it as the 'advanced' skip list implementation targeted at expert users who want to use the skip list in no_std, control garbage collection more precisely, pass Guards to methods, squeeze out every ounce of performance, and so on.

Secondly, in no_std we don't have access to epoch::pin() so one should use Handle::pin() instead and pass a guard to methods that work with the SkipList.

When passing a guard to a skip list method, we must make sure that the guard belongs to the same Collector the skip list is using. In other words, every method taking a &Guard should have a check at the beginning like in the following snippet:

fn insert(&self, key: K, value: V, guard: &Guard) {
    assert!(
        self.collector == guard.collector(),
        "the guard doesn't belong to this collector used by this skip list",
    );

    // ...
}

In order to be able to make such checks, we'll have to first implement fn Guard::collector(&self) -> &Collector in crossbeam-epoch.

In addition to that, SkipList would probably need a similar method returning a reference to its own Collector.

With such an interface, I envision the skip list might be used like this:

let s = SkipList::new();
let handle = s.collector().handle();

let guard = &handle.pin();
s.insert("foo", 42, guard);

@Amanieu What do you think about all this - would this interface work for you? Any better ideas for supporting no_std?

A more general alternative to the existing search function.

#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
pub enum Bound<T> {
    /// An inclusive bound.
    Included(T),
    /// An exclusive bound.
    Excluded(T),
    /// An infinite endpoint. Indicates that there is no bound in this direction.
    Unbounded,
}

impl<K, V> SkipMap<K, V>
where
    K: Ord,
{
    /// 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<Q>(&self, bound: Bound<&Q>) -> Option<Entry<K, V>>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {}

    /// 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<Q>(&self, bound: Bound<&Q>) -> Option<Entry<K, V>>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {}
}

One of the questions raised in the RFC discussion was whether we should rename Entry to Cursor (suggested by @Amanieu).

I'm slightly leaning towards Entry, but don't feel strongly about it. Any other opinions?