cs431_homework/hash_table/
split_ordered_list.rs

1//! Split-ordered linked list.
2
3use core::mem::{self, MaybeUninit};
4use core::sync::atomic::AtomicUsize;
5use core::sync::atomic::Ordering::*;
6
7use crossbeam_epoch::{Guard, Owned};
8use cs431::lockfree::list::{Cursor, List, Node};
9
10use super::growable_array::GrowableArray;
11use crate::ConcurrentMap;
12
13/// Lock-free map from `usize` in range \[0, 2^63-1\] to `V`.
14///
15/// NOTE: We don't care about hashing in this homework for simplicity.
16#[derive(Debug)]
17pub struct SplitOrderedList<V> {
18    /// Lock-free list sorted by recursive-split order.
19    ///
20    /// Use `MaybeUninit::uninit()` when creating sentinel nodes.
21    list: List<usize, MaybeUninit<V>>,
22    /// Array of pointers to the buckets.
23    buckets: GrowableArray<Node<usize, MaybeUninit<V>>>,
24    /// Number of buckets.
25    size: AtomicUsize,
26    /// Number of items.
27    count: AtomicUsize,
28}
29
30impl<V> Default for SplitOrderedList<V> {
31    fn default() -> Self {
32        Self::new()
33    }
34}
35
36impl<V> SplitOrderedList<V> {
37    /// `size` is doubled when `count > size * LOAD_FACTOR`.
38    const LOAD_FACTOR: usize = 2;
39
40    /// Creates a new split ordered list.
41    pub fn new() -> Self {
42        Self {
43            list: List::new(),
44            buckets: GrowableArray::new(),
45            size: AtomicUsize::new(2),
46            count: AtomicUsize::new(0),
47        }
48    }
49
50    /// Creates a cursor and moves it to the bucket for the given index.  If the bucket doesn't
51    /// exist, recursively initializes the buckets.
52    fn lookup_bucket<'s>(
53        &'s self,
54        index: usize,
55        guard: &'s Guard,
56    ) -> Cursor<'s, usize, MaybeUninit<V>> {
57        todo!()
58    }
59
60    /// Moves the bucket cursor returned from `lookup_bucket` to the position of the given key.
61    /// Returns `(size, found, cursor)`
62    fn find<'s>(
63        &'s self,
64        key: &usize,
65        guard: &'s Guard,
66    ) -> (usize, bool, Cursor<'s, usize, MaybeUninit<V>>) {
67        todo!()
68    }
69
70    fn assert_valid_key(key: usize) {
71        assert!(key.leading_zeros() != 0);
72    }
73}
74
75impl<V> ConcurrentMap<usize, V> for SplitOrderedList<V> {
76    fn lookup<'a>(&'a self, key: &usize, guard: &'a Guard) -> Option<&'a V> {
77        Self::assert_valid_key(*key);
78
79        todo!()
80    }
81
82    fn insert(&self, key: usize, value: V, guard: &Guard) -> Result<(), V> {
83        Self::assert_valid_key(key);
84
85        todo!()
86    }
87
88    fn delete<'a>(&'a self, key: &usize, guard: &'a Guard) -> Result<&'a V, ()> {
89        Self::assert_valid_key(*key);
90
91        todo!()
92    }
93}
cs431_homework/hash_table/split_ordered_list.rs

cs431_homework/hash_table/
split_ordered_list.rs
