lfsll/
lib.rs

1#![feature(alloc)]
2
3use std::ptr::null_mut;
4use std::sync::atomic::{AtomicPtr, Ordering};
5use std::boxed;
6use std::default::Default;
7use std::iter::IntoIterator;
8
9struct ListElement<T> {
10	next: AtomicPtr<ListElement<T>>,
11	it: T,
12}
13
14pub struct ListIter<'a, T: 'a> {
15	next: &'a AtomicPtr<ListElement<T>>,
16}
17
18pub struct List<T> {
19	head: AtomicPtr<ListElement<T>>,
20}
21
22unsafe impl<T> Sync for List<T> where T: Send {}
23unsafe impl<T> Send for List<T> where T: Send {}
24
25unsafe impl<T> Sync for ListElement<T> where T: Send {}
26unsafe impl<T> Send for ListElement<T> where T: Send {}
27
28impl<T> List<T> {
29	pub fn new() -> List<T> {
30		List { head: AtomicPtr::new(null_mut()) }
31	}
32
33	pub fn iter<'a>(&'a self) -> ListIter<'a, T> {
34		return ListIter { next: &self.head };
35	}
36
37	pub fn prepend(&self, it: T) {
38		unsafe {
39			let next = boxed::into_raw(Box::new(ListElement {
40				it: it,
41				next: AtomicPtr::new(null_mut()),
42			}));
43
44			loop {
45				let head_snapshot = self.head.load(Ordering::Acquire);
46				(*next).next.store(head_snapshot, Ordering::Release);
47				let old_val = self.head.compare_and_swap(
48					head_snapshot,
49					next,
50					Ordering::Release);
51				if old_val == head_snapshot {
52					return
53				}
54			}
55		}
56	}
57}
58
59impl<T: PartialEq> List<T> {
60	pub fn remove(&self, it: T) -> bool {
61		let mut ptr = &self.head;
62		loop {
63			let before = ptr.load(Ordering::Acquire);
64			if before == null_mut() {
65				return false
66			}
67
68			unsafe {
69				if (*before).it == it {
70					let after = (*before).next.load(Ordering::Acquire);
71					let old_val = ptr.compare_and_swap(
72						before,
73						after,
74						Ordering::Release);
75					if old_val == before {
76						Box::from_raw(before); // release memory
77						return true;
78					}
79				} else {
80					ptr = &(*before).next;
81				}
82			}
83		}
84	}
85}
86
87impl<T> Drop for List<T> {
88	fn drop(&mut self) {
89		let mut tail = self.head.swap(null_mut(), Ordering::Release);
90		while tail != null_mut() {
91			let recl = unsafe { Box::from_raw(tail) };
92			tail = recl.next.load(Ordering::Acquire);
93		}
94	}
95}
96
97impl<'a, T> IntoIterator for &'a List<T> {
98    type Item = &'a T;
99    type IntoIter = ListIter<'a, T>;
100
101    fn into_iter(self) -> Self::IntoIter {
102    	self.iter()
103    }
104}
105
106impl<'a, T> Iterator for ListIter<'a, T> {
107	type Item = &'a T;
108	fn next(&mut self) -> Option<&'a T> {
109		let n = self.next.load(Ordering::Acquire);
110		if n == null_mut() {
111			return None;
112		} else {
113			unsafe {
114				self.next = &(*n).next;
115				return Some(&(*n).it);
116			}
117		}
118	}
119}
120
121impl<T> Default for List<T> {
122    fn default() -> List<T> {
123        List::new()
124    }
125}
lfsll/lib.rs

lfsll/
lib.rs
