Struct SplitOrderedList

pub struct SplitOrderedList<V> {
    list: List<usize, MaybeUninit<V>>,
    buckets: GrowableArray<Node<usize, MaybeUninit<V>>>,
    size: AtomicUsize,
    count: AtomicUsize,
}

Lock-free map from usize in range [0, 2^63-1] to V.

NOTE: We don’t care about hashing in this homework for simplicity.

Fields

list: List<usize, MaybeUninit<V>>

Lock-free list sorted by recursive-split order.

Use MaybeUninit::uninit() when creating sentinel nodes.

buckets: GrowableArray<Node<usize, MaybeUninit<V>>>

Array of pointers to the buckets.

size: AtomicUsize

Number of buckets.

count: AtomicUsize

Number of items.

Implementations

impl<V> SplitOrderedList<V>

const LOAD_FACTOR: usize = 2usize

size is doubled when count > size * LOAD_FACTOR.

pub fn new() -> Self

Creates a new split ordered list.

fn lookup_bucket<'s>( &'s self, index: usize, guard: &'s Guard, ) -> Cursor<'s, usize, MaybeUninit<V>>

Creates a cursor and moves it to the bucket for the given index. If the bucket doesn’t exist, recursively initializes the buckets.

fn find<'s>( &'s self, key: &usize, guard: &'s Guard, ) -> (usize, bool, Cursor<'s, usize, MaybeUninit<V>>)

Moves the bucket cursor returned from lookup_bucket to the position of the given key. Returns (size, found, cursor)

fn assert_valid_key(key: usize)

Trait Implementations

impl<V> ConcurrentMap<usize, V> for SplitOrderedList<V>

fn lookup<'a>(&'a self, key: &usize, guard: &'a Guard) -> Option<&'a V>

Lookups the given key to get the reference to its value.

fn insert(&self, key: usize, value: V, guard: &Guard) -> Result<(), V>

Inserts a key-value pair.

fn delete<'a>(&'a self, key: &usize, guard: &'a Guard) -> Result<&'a V, ()>

Deletes the given key and returns a reference to its value.

impl<V: Debug> Debug for SplitOrderedList<V>

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

Formats the value using the given formatter.

impl<V> Default for SplitOrderedList<V>

fn default() -> Self

Returns the “default value” for a type.