Skip to content

Instantly share code, notes, and snippets.

@roman
Created August 18, 2019 21:46
Show Gist options
  • Save roman/583c597f2cf48d9145a54dea7aa6cefa to your computer and use it in GitHub Desktop.
Save roman/583c597f2cf48d9145a54dea7aa6cefa to your computer and use it in GitHub Desktop.
Fun exercise of implementing Haskell's MVar in Rust
use std::sync::{Condvar, Mutex};
pub struct MVar<T> {
locked_value: Mutex<Option<T>>,
empty_cond: Condvar,
full_cond: Condvar,
}
// Methods of MVar that need the Clone type constraint
impl<T> MVar<T>
where
T: Clone,
{
// read will return a clone of the current value of the MVar if there is
// any, otherwise it will block until one value is put by a different
// thread.
pub fn read(&self) -> T {
let mut m_value = self.locked_value.lock().unwrap();
loop {
// NOTE: m_value is really a smart pointer (MutexGuard), it
// automatically lifts the inner Option type functions, this piece
// of code was *very* confusing without knowing this behavior.
match m_value.take() {
None => {
// The MVar is empty, I have to stop the thread until I get
// a notification that says that the MVar was filled
m_value = self.full_cond.wait(m_value).unwrap();
}
Some(value) => {
// The MVar is full, lets clone the existing value and return
// it to the caller, this MVar still contains the inner value
// Because take mutates the inner Option into
*m_value = Some(value.clone());
return value;
}
}
}
}
}
// Methods of MVar that need no type constraint
impl<T> MVar<T> {
// empty creates a MVar that does not contain any value, because of this,
// it will block on read or take calls if unmodified.
pub fn empty() -> MVar<T> {
return MVar {
locked_value: Mutex::new(None),
empty_cond: Condvar::new(),
full_cond: Condvar::new(),
};
}
// new creates a MVar that contains an initialized value, because of this,
// it will block on put calls if unmodified.
pub fn new(value: T) -> MVar<T> {
return MVar {
locked_value: Mutex::new(Some(value)),
empty_cond: Condvar::new(),
full_cond: Condvar::new(),
};
}
// put sets a value to this MVar, if there is already a value present, it
// will wait/block until another thread takes the value out.
pub fn put(&self, new_value: T) {
let mut m_value = self.locked_value.lock().unwrap();
loop {
match *m_value {
None => {
// The MVar is empty, modify the reference to have a value
// present
*m_value = Some(new_value);
// then notify one of the threads that was waiting for this
// value to be full
self.full_cond.notify_one();
return;
}
_ => {
m_value = self.empty_cond.wait(m_value).unwrap();
}
}
}
}
// put gets a value from this MVar, if there is no value present, it will
// wait/block until another thread puts a value in.
pub fn take(&self) -> T {
let mut m_value = self.locked_value.lock().unwrap();
loop {
// NOTE: m_value is really a smart pointer (MutexGuard), it
// automatically lifts the inner Option type functions, this piece
// of code was *very* confusing without knowing this behavior.
match m_value.take() {
None => {
// No value present, lets wait till it is full
m_value = self.full_cond.wait(m_value).unwrap();
}
Some(value) => {
// The lifted `take` call automatically sets the
// `m_value` pointed value to None, so no need to modify the
// `m_value` smart pointer directly to make the MVar "empty"
// Notify one of the threads that is waiting for the MVar to
// be empty
self.empty_cond.notify_one();
return value;
}
}
}
}
}
mod test {
use crate::MVar;
use std::sync::Arc;
use std::thread;
#[test]
fn test_take_blocks() {
let m0 = Arc::new(MVar::<i32>::empty());
let m = m0.clone();
let h1 = thread::spawn(move || {
m0.put(42);
});
let h2 = thread::spawn(move || {
// this will block if h1 has not executed
let value = m.take();
assert_eq!(42, value)
});
// if we reverse the order of these join calls bellow, the test will
// never succeed
let _ = h1.join();
let _ = h2.join();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment