cs431_homework/list_set/
optimistic_fine_grained.rs

1use std::cmp::Ordering::*;
2use std::mem::{self, ManuallyDrop};
3use std::sync::atomic::Ordering::*;
4
5use crossbeam_epoch::{Atomic, Guard, Owned, Shared, pin};
6use cs431::lock::seqlock::{ReadGuard, SeqLock};
7
8use crate::ConcurrentSet;
9
10#[derive(Debug)]
11struct Node<T> {
12    data: T,
13    next: SeqLock<Atomic<Node<T>>>,
14}
15
16/// Concurrent sorted singly linked list using fine-grained optimistic locking.
17#[derive(Debug)]
18pub struct OptimisticFineGrainedListSet<T> {
19    head: SeqLock<Atomic<Node<T>>>,
20}
21
22unsafe impl<T: Send> Send for OptimisticFineGrainedListSet<T> {}
23unsafe impl<T: Sync> Sync for OptimisticFineGrainedListSet<T> {}
24
25#[derive(Debug)]
26struct Cursor<'g, T> {
27    // Reference to the `next` field of previous node which points to the current node.
28    prev: ReadGuard<'g, Atomic<Node<T>>>,
29    curr: Shared<'g, Node<T>>,
30}
31
32impl<T> Node<T> {
33    fn new(data: T, next: Shared<'_, Self>) -> Owned<Self> {
34        Owned::new(Self {
35            data,
36            next: SeqLock::new(next.into()),
37        })
38    }
39}
40
41impl<'g, T: Ord> Cursor<'g, T> {
42    /// Moves the cursor to the position of key in the sorted list.
43    /// Returns whether the value was found.
44    ///
45    /// Return `Err(())` if the cursor cannot move.
46    fn find(&mut self, key: &T, guard: &'g Guard) -> Result<bool, ()> {
47        todo!()
48    }
49}
50
51impl<T> OptimisticFineGrainedListSet<T> {
52    /// Creates a new list.
53    pub fn new() -> Self {
54        Self {
55            head: SeqLock::new(Atomic::null()),
56        }
57    }
58
59    fn head<'g>(&'g self, guard: &'g Guard) -> Cursor<'g, T> {
60        let prev = unsafe { self.head.read_lock() };
61        let curr = prev.load(Acquire, guard);
62        Cursor { prev, curr }
63    }
64}
65
66impl<T: Ord> OptimisticFineGrainedListSet<T> {
67    fn find<'g>(&'g self, key: &T, guard: &'g Guard) -> Result<(bool, Cursor<'g, T>), ()> {
68        todo!()
69    }
70}
71
72impl<T: Ord> ConcurrentSet<T> for OptimisticFineGrainedListSet<T> {
73    fn contains(&self, key: &T) -> bool {
74        todo!()
75    }
76
77    fn insert(&self, key: T) -> bool {
78        todo!()
79    }
80
81    fn remove(&self, key: &T) -> bool {
82        todo!()
83    }
84}
85
86#[derive(Debug)]
87pub struct Iter<'g, T> {
88    // Can be dropped without validation, because the only way to use cursor.curr is next().
89    cursor: ManuallyDrop<Cursor<'g, T>>,
90    guard: &'g Guard,
91}
92
93impl<T> OptimisticFineGrainedListSet<T> {
94    /// An iterator visiting all elements. `next()` returns `Some(Err(()))` when validation fails.
95    /// In that case, the user must restart the iteration.
96    pub fn iter<'g>(&'g self, guard: &'g Guard) -> Iter<'g, T> {
97        Iter {
98            cursor: ManuallyDrop::new(self.head(guard)),
99            guard,
100        }
101    }
102}
103
104impl<'g, T> Iterator for Iter<'g, T> {
105    type Item = Result<&'g T, ()>;
106
107    fn next(&mut self) -> Option<Self::Item> {
108        todo!()
109    }
110}
111
112impl<T> Drop for OptimisticFineGrainedListSet<T> {
113    fn drop(&mut self) {
114        todo!()
115    }
116}
117
118impl<T> Default for OptimisticFineGrainedListSet<T> {
119    fn default() -> Self {
120        Self::new()
121    }
122}
cs431_homework/list_set/optimistic_fine_grained.rs

cs431_homework/list_set/
optimistic_fine_grained.rs
