diff options
author | mental <m3nta1@yahoo.com> | 2020-09-02 20:37:13 +0100 |
---|---|---|
committer | GitHub <noreply@github.com> | 2020-09-02 12:37:13 -0700 |
commit | c9f5bc29158a6f3a786e9d67df8da31524e8a9c3 (patch) | |
tree | 5a5036435833cf80b2bd81165e89a5c57795e9cc | |
parent | 5cdb6f8fd6be35f971d8ef7ea8984f4d01965620 (diff) |
util: add `const fn` support for internal `LinkedList`. (#2805)
-rw-r--r-- | tokio/src/runtime/basic_scheduler.rs | 4 | ||||
-rw-r--r-- | tokio/src/runtime/tests/task.rs | 4 | ||||
-rw-r--r-- | tokio/src/runtime/thread_pool/worker.rs | 4 | ||||
-rw-r--r-- | tokio/src/sync/batch_semaphore.rs | 2 | ||||
-rw-r--r-- | tokio/src/sync/broadcast.rs | 2 | ||||
-rw-r--r-- | tokio/src/sync/notify.rs | 6 | ||||
-rw-r--r-- | tokio/src/task/local.rs | 4 | ||||
-rw-r--r-- | tokio/src/util/linked_list.rs | 102 |
8 files changed, 73 insertions, 55 deletions
diff --git a/tokio/src/runtime/basic_scheduler.rs b/tokio/src/runtime/basic_scheduler.rs index 48cff709..7bf8b445 100644 --- a/tokio/src/runtime/basic_scheduler.rs +++ b/tokio/src/runtime/basic_scheduler.rs @@ -1,7 +1,7 @@ use crate::park::{Park, Unpark}; use crate::runtime; use crate::runtime::task::{self, JoinHandle, Schedule, Task}; -use crate::util::linked_list::LinkedList; +use crate::util::linked_list::{Link, LinkedList}; use crate::util::{waker_ref, Wake}; use std::cell::RefCell; @@ -42,7 +42,7 @@ pub(crate) struct Spawner { struct Tasks { /// Collection of all active tasks spawned onto this executor. - owned: LinkedList<Task<Arc<Shared>>>, + owned: LinkedList<Task<Arc<Shared>>, <Task<Arc<Shared>> as Link>::Target>, /// Local run queue. /// diff --git a/tokio/src/runtime/tests/task.rs b/tokio/src/runtime/tests/task.rs index 82315a04..a34526f3 100644 --- a/tokio/src/runtime/tests/task.rs +++ b/tokio/src/runtime/tests/task.rs @@ -1,5 +1,5 @@ use crate::runtime::task::{self, Schedule, Task}; -use crate::util::linked_list::LinkedList; +use crate::util::linked_list::{Link, LinkedList}; use crate::util::TryLock; use std::collections::VecDeque; @@ -72,7 +72,7 @@ struct Inner { struct Core { queue: VecDeque<task::Notified<Runtime>>, - tasks: LinkedList<Task<Runtime>>, + tasks: LinkedList<Task<Runtime>, <Task<Runtime> as Link>::Target>, } static CURRENT: TryLock<Option<Runtime>> = TryLock::new(None); diff --git a/tokio/src/runtime/thread_pool/worker.rs b/tokio/src/runtime/thread_pool/worker.rs index ac052854..10e973f6 100644 --- a/tokio/src/runtime/thread_pool/worker.rs +++ b/tokio/src/runtime/thread_pool/worker.rs @@ -12,7 +12,7 @@ use crate::runtime; use crate::runtime::park::{Parker, Unparker}; use crate::runtime::thread_pool::{AtomicCell, Idle}; use crate::runtime::{queue, task}; -use crate::util::linked_list::LinkedList; +use crate::util::linked_list::{Link, LinkedList}; use crate::util::FastRand; use std::cell::RefCell; @@ -53,7 +53,7 @@ struct Core { is_shutdown: bool, /// Tasks owned by the core - tasks: LinkedList<Task>, + tasks: LinkedList<Task, <Task as Link>::Target>, /// Parker /// diff --git a/tokio/src/sync/batch_semaphore.rs b/tokio/src/sync/batch_semaphore.rs index aad6c6f1..c48a911c 100644 --- a/tokio/src/sync/batch_semaphore.rs +++ b/tokio/src/sync/batch_semaphore.rs @@ -36,7 +36,7 @@ pub(crate) struct Semaphore { } struct Waitlist { - queue: LinkedList<Waiter>, + queue: LinkedList<Waiter, <Waiter as linked_list::Link>::Target>, closed: bool, } diff --git a/tokio/src/sync/broadcast.rs b/tokio/src/sync/broadcast.rs index a64774ec..9b3de530 100644 --- a/tokio/src/sync/broadcast.rs +++ b/tokio/src/sync/broadcast.rs @@ -273,7 +273,7 @@ struct Tail { closed: bool, /// Receivers waiting for a value - waiters: LinkedList<Waiter>, + waiters: LinkedList<Waiter, <Waiter as linked_list::Link>::Target>, } /// Slot in the buffer diff --git a/tokio/src/sync/notify.rs b/tokio/src/sync/notify.rs index 84a94823..def704f2 100644 --- a/tokio/src/sync/notify.rs +++ b/tokio/src/sync/notify.rs @@ -10,6 +10,8 @@ use std::ptr::NonNull; use std::sync::atomic::Ordering::SeqCst; use std::task::{Context, Poll, Waker}; +type WaitList = LinkedList<Waiter, <Waiter as linked_list::Link>::Target>; + /// Notify a single task to wake up. /// /// `Notify` provides a basic mechanism to notify a single task of an event. @@ -101,7 +103,7 @@ use std::task::{Context, Poll, Waker}; #[derive(Debug)] pub struct Notify { state: AtomicU8, - waiters: Mutex<LinkedList<Waiter>>, + waiters: Mutex<WaitList>, } #[derive(Debug)] @@ -285,7 +287,7 @@ impl Default for Notify { } } -fn notify_locked(waiters: &mut LinkedList<Waiter>, state: &AtomicU8, curr: u8) -> Option<Waker> { +fn notify_locked(waiters: &mut WaitList, state: &AtomicU8, curr: u8) -> Option<Waker> { loop { match curr { EMPTY | NOTIFIED => { diff --git a/tokio/src/task/local.rs b/tokio/src/task/local.rs index a56453df..1d7b99d5 100644 --- a/tokio/src/task/local.rs +++ b/tokio/src/task/local.rs @@ -1,7 +1,7 @@ //! Runs `!Send` futures on the current thread. use crate::runtime::task::{self, JoinHandle, Task}; use crate::sync::AtomicWaker; -use crate::util::linked_list::LinkedList; +use crate::util::linked_list::{Link, LinkedList}; use std::cell::{Cell, RefCell}; use std::collections::VecDeque; @@ -132,7 +132,7 @@ struct Context { struct Tasks { /// Collection of all active tasks spawned onto this executor. - owned: LinkedList<Task<Arc<Shared>>>, + owned: LinkedList<Task<Arc<Shared>>, <Task<Arc<Shared>> as Link>::Target>, /// Local run queue sender and receiver. queue: VecDeque<task::Notified<Arc<Shared>>>, diff --git a/tokio/src/util/linked_list.rs b/tokio/src/util/linked_list.rs index aa3ce771..e6d6c588 100644 --- a/tokio/src/util/linked_list.rs +++ b/tokio/src/util/linked_list.rs @@ -5,6 +5,7 @@ //! specified node is actually contained by the list. use core::fmt; +use core::marker::PhantomData; use core::mem::ManuallyDrop; use core::ptr::NonNull; @@ -12,16 +13,19 @@ use core::ptr::NonNull; /// /// Currently, the list is not emptied on drop. It is the caller's /// responsibility to ensure the list is empty before dropping it. -pub(crate) struct LinkedList<T: Link> { +pub(crate) struct LinkedList<L, T> { /// Linked list head - head: Option<NonNull<T::Target>>, + head: Option<NonNull<T>>, /// Linked list tail - tail: Option<NonNull<T::Target>>, + tail: Option<NonNull<T>>, + + /// Node type marker. + _marker: PhantomData<*const L>, } -unsafe impl<T: Link> Send for LinkedList<T> where T::Target: Send {} -unsafe impl<T: Link> Sync for LinkedList<T> where T::Target: Sync {} +unsafe impl<L: Link> Send for LinkedList<L, L::Target> where L::Target: Send {} +unsafe impl<L: Link> Sync for LinkedList<L, L::Target> where L::Target: Sync {} /// Defines how a type is tracked within a linked list. /// @@ -66,27 +70,31 @@ unsafe impl<T: Sync> Sync for Pointers<T> {} // ===== impl LinkedList ===== -impl<T: Link> LinkedList<T> { - /// Creates an empty linked list - pub(crate) fn new() -> LinkedList<T> { +impl<L, T> LinkedList<L, T> { + /// Creates an empty linked list. + #[allow(dead_code)] // NOTE: This will get removed with: https://github.com/tokio-rs/tokio/pull/2790 + pub(crate) const fn new() -> LinkedList<L, T> { LinkedList { head: None, tail: None, + _marker: PhantomData, } } +} +impl<L: Link> LinkedList<L, L::Target> { /// Adds an element first in the list. - pub(crate) fn push_front(&mut self, val: T::Handle) { + pub(crate) fn push_front(&mut self, val: L::Handle) { // The value should not be dropped, it is being inserted into the list let val = ManuallyDrop::new(val); - let ptr = T::as_raw(&*val); + let ptr = L::as_raw(&*val); assert_ne!(self.head, Some(ptr)); unsafe { - T::pointers(ptr).as_mut().next = self.head; - T::pointers(ptr).as_mut().prev = None; + L::pointers(ptr).as_mut().next = self.head; + L::pointers(ptr).as_mut().prev = None; if let Some(head) = self.head { - T::pointers(head).as_mut().prev = Some(ptr); + L::pointers(head).as_mut().prev = Some(ptr); } self.head = Some(ptr); @@ -99,21 +107,21 @@ impl<T: Link> LinkedList<T> { /// Removes the last element from a list and returns it, or None if it is /// empty. - pub(crate) fn pop_back(&mut self) -> Option<T::Handle> { + pub(crate) fn pop_back(&mut self) -> Option<L::Handle> { unsafe { let last = self.tail?; - self.tail = T::pointers(last).as_ref().prev; + self.tail = L::pointers(last).as_ref().prev; - if let Some(prev) = T::pointers(last).as_ref().prev { - T::pointers(prev).as_mut().next = None; + if let Some(prev) = L::pointers(last).as_ref().prev { + L::pointers(prev).as_mut().next = None; } else { self.head = None } - T::pointers(last).as_mut().prev = None; - T::pointers(last).as_mut().next = None; + L::pointers(last).as_mut().prev = None; + L::pointers(last).as_mut().next = None; - Some(T::from_raw(last)) + Some(L::from_raw(last)) } } @@ -133,38 +141,38 @@ impl<T: Link> LinkedList<T> { /// /// The caller **must** ensure that `node` is currently contained by /// `self` or not contained by any other list. - pub(crate) unsafe fn remove(&mut self, node: NonNull<T::Target>) -> Option<T::Handle> { - if let Some(prev) = T::pointers(node).as_ref().prev { - debug_assert_eq!(T::pointers(prev).as_ref().next, Some(node)); - T::pointers(prev).as_mut().next = T::pointers(node).as_ref().next; + pub(crate) unsafe fn remove(&mut self, node: NonNull<L::Target>) -> Option<L::Handle> { + if let Some(prev) = L::pointers(node).as_ref().prev { + debug_assert_eq!(L::pointers(prev).as_ref().next, Some(node)); + L::pointers(prev).as_mut().next = L::pointers(node).as_ref().next; } else { if self.head != Some(node) { return None; } - self.head = T::pointers(node).as_ref().next; + self.head = L::pointers(node).as_ref().next; } - if let Some(next) = T::pointers(node).as_ref().next { - debug_assert_eq!(T::pointers(next).as_ref().prev, Some(node)); - T::pointers(next).as_mut().prev = T::pointers(node).as_ref().prev; + if let Some(next) = L::pointers(node).as_ref().next { + debug_assert_eq!(L::pointers(next).as_ref().prev, Some(node)); + L::pointers(next).as_mut().prev = L::pointers(node).as_ref().prev; } else { // This might be the last item in the list if self.tail != Some(node) { return None; } - self.tail = T::pointers(node).as_ref().prev; + self.tail = L::pointers(node).as_ref().prev; } - T::pointers(node).as_mut().next = None; - T::pointers(node).as_mut().prev = None; + L::pointers(node).as_mut().next = None; + L::pointers(node).as_mut().prev = None; - Some(T::from_raw(node)) + Some(L::from_raw(node)) } } -impl<T: Link> fmt::Debug for LinkedList<T> { +impl<L: Link> fmt::Debug for LinkedList<L, L::Target> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_struct("LinkedList") .field("head", &self.head) @@ -174,8 +182,8 @@ impl<T: Link> fmt::Debug for LinkedList<T> { } cfg_sync! { - impl<T: Link> LinkedList<T> { - pub(crate) fn last(&self) -> Option<&T::Target> { + impl<L: Link> LinkedList<L, L::Target> { + pub(crate) fn last(&self) -> Option<&L::Target> { let tail = self.tail.as_ref()?; unsafe { Some(&*tail.as_ptr()) @@ -192,8 +200,8 @@ cfg_rt_threaded! { _p: core::marker::PhantomData<&'a T>, } - impl<T: Link> LinkedList<T> { - pub(crate) fn iter(&self) -> Iter<'_, T> { + impl<L: Link> LinkedList<L, L::Target> { + pub(crate) fn iter(&self) -> Iter<'_, L> { Iter { curr: self.head, _p: core::marker::PhantomData, @@ -277,7 +285,7 @@ mod tests { r.as_ref().get_ref().into() } - fn collect_list(list: &mut LinkedList<&'_ Entry>) -> Vec<i32> { + fn collect_list(list: &mut LinkedList<&'_ Entry, <&'_ Entry as Link>::Target>) -> Vec<i32> { let mut ret = vec![]; while let Some(entry) = list.pop_back() { @@ -287,7 +295,10 @@ mod tests { ret } - fn push_all<'a>(list: &mut LinkedList<&'a Entry>, entries: &[Pin<&'a Entry>]) { + fn push_all<'a>( + list: &mut LinkedList<&'a Entry, <&'_ Entry as Link>::Target>, + entries: &[Pin<&'a Entry>], + ) { for entry in entries.iter() { list.push_front(*entry); } @@ -308,6 +319,11 @@ mod tests { } #[test] + fn const_new() { + const _: LinkedList<&Entry, <&Entry as Link>::Target> = LinkedList::new(); + } + + #[test] fn push_and_drain() { let a = entry(5); let b = entry(7); @@ -332,7 +348,7 @@ mod tests { let a = entry(5); let b = entry(7); - let mut list = LinkedList::<&Entry>::new(); + let mut list = LinkedList::<&Entry, <&Entry as Link>::Target>::new(); list.push_front(a.as_ref()); @@ -489,7 +505,7 @@ mod tests { unsafe { // Remove missing - let mut list = LinkedList::<&Entry>::new(); + let mut list = LinkedList::<&Entry, <&Entry as Link>::Target>::new(); list.push_front(b.as_ref()); list.push_front(a.as_ref()); @@ -503,7 +519,7 @@ mod tests { let a = entry(5); let b = entry(7); - let mut list = LinkedList::<&Entry>::new(); + let mut list = LinkedList::<&Entry, <&Entry as Link>::Target>::new(); assert_eq!(0, list.iter().count()); @@ -543,7 +559,7 @@ mod tests { }) .collect::<Vec<_>>(); - let mut ll = LinkedList::<&Entry>::new(); + let mut ll = LinkedList::<&Entry, <&Entry as Link>::Target>::new(); let mut reference = VecDeque::new(); let entries: Vec<_> = (0..ops.len()).map(|i| entry(i as i32)).collect(); |