Struct dakv_skiplist::SkipList

pub struct SkipList<R, C, A> where
    R: RandomGenerator,
    C: BaseComparator,
    A: Arena,  { /* fields omitted */ }

Implementations

impl<R, C, A> SkipList<R, C, A> where
    R: RandomGenerator,
    C: BaseComparator,
    A: Arena, 

pub fn new(rnd: R, cmp: C, arena: A) -> Self

pub fn len(&self) -> usize

Returns the number of elements in the skiplist.

Examples

use dakv_skiplist::{SkipList, Random, ArenaImpl, DefaultComparator};

let mut sl = SkipList::new(
    Random::new(0xdead_beef),
    DefaultComparator::default (),
    ArenaImpl::new(),
);
assert_eq!(sl.len(), 0);

sl.insert(vec![1u8]);
assert_eq!(sl.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the skiplist is empty.

Examples

use dakv_skiplist::{SkipList, Random, ArenaImpl, DefaultComparator};

let mut sl = SkipList::new(
    Random::new(0xdead_beef),
    DefaultComparator::default (),
    ArenaImpl::new(),
);
assert!(sl.is_empty());

sl.insert(vec![1u8]);
assert_eq!(sl.is_empty(), false);

pub fn memory_size(&self) -> usize

pub fn remain_bytes(&self) -> usize

pub fn get_max_height(&self) -> usize

pub fn set_max_height(&mut self, h: usize)

pub fn clear(&mut self)

Clear every single node and reset the head node.

Examples

use dakv_skiplist::{SkipList, Random, ArenaImpl, DefaultComparator};

let mut sl = SkipList::new(
    Random::new(0xdead_beef),
    DefaultComparator::default (),
    ArenaImpl::new(),
);
sl.insert(vec![1u8]);
sl.clear();
assert_eq!(sl.is_empty(), true);

pub fn find(&self, key: &[u8], prev: &mut Vec<*mut Node>) -> *mut Node

Look for the node greater than or equal to key

Safety

todo doc

pub fn insert(&mut self, key: impl Into<Bytes>)

1. Find the node greater than or equal to the key and return the mutable reference
2. Randomly generate level
3. Create new node
4. Insert and set forwards

pub fn contains(&mut self, key: &[u8]) -> bool

pub fn get_head(&self) -> &Node

pub fn find_less_than(&self, key: &[u8]) -> *const Node

pub fn find_last(&self) -> *const Node

Trait Implementations

impl<R: Clone, C: Clone, A: Clone> Clone for SkipList<R, C, A> where
    R: RandomGenerator,
    C: BaseComparator,
    A: Arena, 

fn clone(&self) -> SkipList<R, C, A>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<R, C, A> Display for SkipList<R, C, A> where
    R: RandomGenerator,
    C: BaseComparator,
    A: Arena, 

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<R, C, A, T> Extend<T> for SkipList<R, C, A> where
    T: Into<u8>,
    R: RandomGenerator,
    C: BaseComparator,
    A: Arena, 

fn extend<I: IntoIterator<Item = T>>(&mut self, iterable: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a, R, C, A> IntoIterator for &'a SkipList<R, C, A> where
    R: RandomGenerator,
    C: BaseComparator,
    A: Arena, 

type Item = &'a Node

The type of the elements being iterated over.

type IntoIter = Iter<'a>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a>

Creates an iterator from a value.