#![warn(missing_docs)]
use std::mem;
#[cfg(all(doctest, not(loom)))]
#[doc = include_str!("../README.md")]
struct ReadmeExamples;
#[cfg(loom)]
use loom::sync::Mutex;
#[cfg(loom)]
use loom::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
#[cfg(not(loom))]
use std::sync::Mutex;
#[cfg(not(loom))]
use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
use std::sync::Arc;
pub type MergeFn<T> = Arc<dyn Fn(&mut T, &T) + Send + Sync>;
#[repr(align(64))]
struct Node<T> {
sons: Mutex<Vec<Arc<Node<T>>>>,
handles: AtomicUsize,
dead: AtomicBool,
data: Mutex<T>,
dirty: AtomicBool, subtree_dirty: Arc<AtomicBool>,
ancestor_flags: Vec<Arc<AtomicBool>>,
identity: Arc<T>,
merge: MergeFn<T>,
}
pub struct Mergex<T> {
node: Arc<Node<T>>,
}
impl<T> Clone for Mergex<T> {
fn clone(&self) -> Self {
self.node.handles.fetch_add(1, Ordering::Relaxed);
Mergex {
node: Arc::clone(&self.node),
}
}
}
impl<T> Drop for Mergex<T> {
fn drop(&mut self) {
if self.node.handles.fetch_sub(1, Ordering::AcqRel) == 1 {
self.node.dead.store(true, Ordering::Release);
}
}
}
impl<T: std::fmt::Debug> std::fmt::Debug for Mergex<T> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let sons: Vec<Mergex<T>> = self
.node
.sons
.lock()
.unwrap()
.iter()
.map(|n| Mergex { node: Arc::clone(n) })
.collect();
f.debug_struct("Mergex")
.field("data", &*self.node.data.lock().unwrap())
.field("dirty", &self.node.dirty.load(Ordering::Acquire))
.field("sons", &sons)
.finish()
}
}
impl<T: Clone> Mergex<T> {
pub fn new(data: T, identity: T, merge: impl Fn(&mut T, &T) + Send + Sync + 'static) -> Self {
Mergex {
node: Arc::new(Node {
sons: Mutex::new(vec![]),
handles: AtomicUsize::new(1),
dead: AtomicBool::new(false),
data: Mutex::new(data),
dirty: AtomicBool::new(false),
subtree_dirty: Arc::new(AtomicBool::new(false)),
ancestor_flags: vec![],
identity: Arc::new(identity),
merge: Arc::new(merge),
}),
}
}
pub fn copy(&self) -> Self {
let son = Arc::new(Node {
sons: Mutex::new(vec![]),
handles: AtomicUsize::new(1),
dead: AtomicBool::new(false),
data: Mutex::new((*self.node.identity).clone()),
dirty: AtomicBool::new(false),
subtree_dirty: Arc::new(AtomicBool::new(false)),
ancestor_flags: {
let mut f = Vec::with_capacity(self.node.ancestor_flags.len() + 1);
f.push(Arc::clone(&self.node.subtree_dirty));
f.extend(self.node.ancestor_flags.iter().cloned());
f
},
identity: Arc::clone(&self.node.identity),
merge: Arc::clone(&self.node.merge),
});
self.node.sons.lock().unwrap().push(Arc::clone(&son));
Mergex { node: son }
}
pub fn set(&self, data: T) {
self.update(|slot| *slot = data);
}
pub fn update(&self, f: impl FnOnce(&mut T)) {
let mut guard = self.node.data.lock().unwrap();
f(&mut guard);
let was_dirty = self.node.dirty.load(Ordering::Relaxed);
self.node.dirty.store(true, Ordering::Release);
drop(guard);
if !was_dirty {
self.node.mark_ancestors();
}
}
pub fn get_threaded(&self) -> T {
self.node.data.lock().unwrap().clone()
}
pub fn get(&self) -> T {
self.node.merge_sons();
self.get_threaded()
}
pub fn check_children(&self) -> bool {
self.node.check_children()
}
pub fn check_dirty_bit(&self) -> bool {
self.node.dirty.load(Ordering::Acquire)
}
}
impl<T: Clone> Node<T> {
fn mark_ancestors(&self) {
for flag in &self.ancestor_flags {
if flag.swap(true, Ordering::AcqRel) {
return;
}
}
}
fn merge_sons(&self) -> bool {
if !self.subtree_dirty.swap(false, Ordering::AcqRel) {
return false;
}
let mut changed = false;
let mut spent: Vec<Arc<Node<T>>> = Vec::new();
for son in self.snapshot_sons() {
let son_changed = son.merge_sons();
if !son.dirty.load(Ordering::Acquire) && !son_changed {
if son.is_spent() {
spent.push(son);
}
continue;
}
let son_data = {
let mut guard = son.data.lock().unwrap();
son.dirty.store(false, Ordering::Release);
mem::replace(&mut *guard, (*son.identity).clone())
};
(self.merge)(&mut self.data.lock().unwrap(), &son_data);
changed = true;
if son.is_spent() {
spent.push(son);
}
}
if !spent.is_empty() {
self.reap(&spent);
}
changed
}
fn is_spent(&self) -> bool {
self.dead.load(Ordering::Acquire)
&& self.handles.load(Ordering::Acquire) == 0
&& !self.dirty.load(Ordering::Acquire)
&& self.sons.lock().unwrap().is_empty()
}
fn reap(&self, spent: &[Arc<Node<T>>]) {
const LINEAR: usize = 8;
let marks: Vec<*const Node<T>> = if spent.len() > LINEAR {
let mut m: Vec<*const Node<T>> = spent.iter().map(Arc::as_ptr).collect();
m.sort_unstable();
m
} else {
Vec::new()
};
let is_marked = |s: &Arc<Node<T>>| {
if spent.len() > LINEAR {
marks.binary_search(&Arc::as_ptr(s)).is_ok()
} else {
spent.iter().any(|d| Arc::ptr_eq(s, d))
}
};
let mut sons = self.sons.lock().unwrap();
sons.retain(|s| {
if !is_marked(s) {
return true;
}
s.handles.load(Ordering::Acquire) != 0 || s.dirty.load(Ordering::Acquire)
});
}
fn check_children(&self) -> bool {
if !self.subtree_dirty.load(Ordering::Acquire) {
return false;
}
self.snapshot_sons()
.iter()
.any(|s| s.dirty.load(Ordering::Acquire) || s.check_children())
}
fn snapshot_sons(&self) -> Vec<Arc<Node<T>>> {
self.sons.lock().unwrap().to_vec()
}
}
#[cfg(all(test, not(loom)))]
mod tests {
use super::*;
use std::thread;
fn sum() -> Mergex<i32> {
Mergex::new(7, 0, |father: &mut i32, son: &i32| *father += *son)
}
#[test]
fn thread_updates_reach_the_root() {
let root = sum();
let t1 = root.copy();
let t2 = root.copy();
let a = thread::spawn(move || t1.set(10));
let b = thread::spawn(move || t2.set(20));
a.join().unwrap();
b.join().unwrap();
assert!(root.check_children());
assert_eq!(root.get(), 37); assert!(!root.check_children()); }
#[test]
fn grandsons_merge_bottom_up() {
let root = sum();
let son = root.copy();
let grandson = son.copy();
grandson.set(5);
assert!(root.check_children()); assert_eq!(root.get(), 12); }
#[test]
fn sons_created_inside_a_thread_register() {
let root = sum();
let t1 = root.copy();
thread::spawn(move || {
let grandson = t1.copy();
grandson.set(1000);
})
.join()
.unwrap();
assert_eq!(root.get(), 1007); }
#[test]
fn dropping_the_root_strands_the_son() {
let son = {
let root = sum();
let son = root.copy();
son.set(3); son
};
assert_eq!(son.get_threaded(), 3);
}
#[test]
fn a_dropped_handle_still_delivers_its_write() {
let root = sum();
{
let worker = root.copy();
worker.set(5);
}
assert_eq!(root.get(), 12); }
#[test]
fn a_spent_son_is_unlinked_by_the_next_merge() {
let root = sum();
{
let worker = root.copy();
worker.set(5);
}
assert_eq!(root.node.sons.lock().unwrap().len(), 1);
assert_eq!(root.get(), 12); assert_eq!(root.node.sons.lock().unwrap().len(), 0);
}
#[test]
fn a_live_son_is_never_unlinked() {
let root = sum();
let worker = root.copy();
worker.set(5);
assert_eq!(root.get(), 12);
assert_eq!(root.node.sons.lock().unwrap().len(), 1);
worker.set(2);
assert_eq!(root.get(), 14); }
#[test]
fn a_dead_son_holding_a_live_grandson_stays() {
let root = sum();
let grandson = {
let son = root.copy();
son.copy()
}; grandson.set(9);
assert_eq!(root.get(), 16); assert_eq!(root.node.sons.lock().unwrap().len(), 1); }
#[test]
fn a_pool_of_short_lived_workers_does_not_grow_the_son_list() {
let root = Mergex::new(0i64, 0, |f: &mut i64, s: &i64| *f += *s);
for i in 1..=100 {
let w = root.copy();
w.set(i);
drop(w);
root.get(); }
assert_eq!(root.get(), (1..=100).sum::<i64>());
assert_eq!(root.node.sons.lock().unwrap().len(), 0);
}
#[test]
fn many_threads_registering_and_setting_at_once() {
let root = Mergex::new(0i64, 0, |father: &mut i64, son: &i64| *father += *son);
let handles: Vec<_> = (1..=50)
.map(|i| {
let r = root.clone(); thread::spawn(move || r.copy().set(i))
})
.collect();
for h in handles {
h.join().unwrap();
}
assert_eq!(root.get(), (1..=50).sum::<i64>()); }
#[test]
fn merging_is_idempotent() {
let root = sum();
root.copy().set(10);
assert_eq!(root.get(), 17);
assert_eq!(root.get(), 17); }
#[test]
fn a_read_does_not_replay_an_earlier_delta() {
let root = sum();
let son = root.copy();
son.update(|x| *x += 1);
assert_eq!(root.get(), 8);
son.update(|x| *x += 1);
assert_eq!(root.get(), 9); son.update(|x| *x += 1);
assert_eq!(root.get(), 10);
}
#[test]
fn folding_resets_the_son_to_the_identity() {
let root = sum();
let son = root.copy();
assert_eq!(son.get_threaded(), 0); son.set(5);
assert_eq!(root.get(), 12);
assert_eq!(son.get_threaded(), 0); }
#[test]
fn an_intermediate_node_is_reset_too() {
let root = sum();
let son = root.copy();
let grandson = son.copy();
grandson.set(4);
assert_eq!(root.get(), 11);
assert_eq!(son.get_threaded(), 0); assert_eq!(grandson.get_threaded(), 0);
grandson.set(4);
assert_eq!(root.get(), 15); }
}