cs431_homework/list_set/
fine_grained.rs

1use std::cmp::Ordering::*;
2use std::sync::{Mutex, MutexGuard};
3use std::{mem, ptr};
4
5use crate::ConcurrentSet;
6
7#[derive(Debug)]
8struct Node<T> {
9    data: T,
10    next: Mutex<*mut Node<T>>,
11}
12
13/// Concurrent sorted singly linked list using fine-grained lock-coupling.
14#[derive(Debug)]
15pub struct FineGrainedListSet<T> {
16    head: Mutex<*mut Node<T>>,
17}
18
19unsafe impl<T: Send> Send for FineGrainedListSet<T> {}
20unsafe impl<T: Send> Sync for FineGrainedListSet<T> {}
21
22/// Reference to the `next` field of previous node which points to the current node.
23///
24/// For example, given the following linked list:
25///
26/// ```text
27/// head -> 1 -> 2 -> 3 -> null
28/// ```
29///
30/// If `cursor` is currently at node 2, then `cursor.0` should be the `MutexGuard` obtained from the
31/// `next` of node 1. In particular, `cursor.0.as_ref().unwrap()` creates a shared reference to node
32/// 2.
33struct Cursor<'l, T>(MutexGuard<'l, *mut Node<T>>);
34
35impl<T> Node<T> {
36    fn new(data: T, next: *mut Self) -> *mut Self {
37        Box::into_raw(Box::new(Self {
38            data,
39            next: Mutex::new(next),
40        }))
41    }
42}
43
44impl<T: Ord> Cursor<'_, T> {
45    /// Moves the cursor to the position of key in the sorted list.
46    /// Returns whether the value was found.
47    fn find(&mut self, key: &T) -> bool {
48        todo!()
49    }
50}
51
52impl<T> FineGrainedListSet<T> {
53    /// Creates a new list.
54    pub fn new() -> Self {
55        Self {
56            head: Mutex::new(ptr::null_mut()),
57        }
58    }
59}
60
61impl<T: Ord> FineGrainedListSet<T> {
62    fn find(&self, key: &T) -> (bool, Cursor<'_, T>) {
63        todo!()
64    }
65}
66
67impl<T: Ord> ConcurrentSet<T> for FineGrainedListSet<T> {
68    fn contains(&self, key: &T) -> bool {
69        self.find(key).0
70    }
71
72    fn insert(&self, key: T) -> bool {
73        todo!()
74    }
75
76    fn remove(&self, key: &T) -> bool {
77        todo!()
78    }
79}
80
81#[derive(Debug)]
82pub struct Iter<'l, T> {
83    cursor: MutexGuard<'l, *mut Node<T>>,
84}
85
86impl<T> FineGrainedListSet<T> {
87    /// An iterator visiting all elements.
88    pub fn iter(&self) -> Iter<'_, T> {
89        Iter {
90            cursor: self.head.lock().unwrap(),
91        }
92    }
93}
94
95impl<'l, T> Iterator for Iter<'l, T> {
96    type Item = &'l T;
97
98    fn next(&mut self) -> Option<Self::Item> {
99        todo!()
100    }
101}
102
103impl<T> Drop for FineGrainedListSet<T> {
104    fn drop(&mut self) {
105        todo!()
106    }
107}
108
109impl<T> Default for FineGrainedListSet<T> {
110    fn default() -> Self {
111        Self::new()
112    }
113}
cs431_homework/list_set/fine_grained.rs

cs431_homework/list_set/
fine_grained.rs
