Repository: tokio-rs/tokio
File: tokio/src/util/sharded_list.rs (Rust)

Code before:

use crate::loom::sync::{Mutex, MutexGuard};
use std::sync::atomic::AtomicUsize;

use super::linked_list::{Link, LinkedList};

/// An intrusive  linked list supporting high concurrent updates.
///
/// It currently relies on `LinkedList`, so it is the caller's
/// responsibility to ensure the list is empty before dropping it.
///
/// Note: Due to its inner sharded design, the order of node cannot be guaranteed.
pub(crate) struct ShardedList<L, T> {
    lists: Box<[Mutex<LinkedList<L, T>>]>,
    count: AtomicUsize,
    shard_mask: usize,
}

/// Defines the id of a node in a linked list, different ids cause inner list nodes
/// to be scattered in different mutexs.
///
/// # Safety
///
/// Implementations must guarantee that `Target` types are pinned in memory. In
/// other words, when a node is inserted, the value will not be moved as long as
/// it is stored in the list.
pub(crate) unsafe trait ShardedListItem: Link {
    // The returned id is used to pick which list this item should go into.
    unsafe fn get_shared_id(target: NonNull<Self::Target>) -> usize;
}

impl<L, T> ShardedList<L, T> {
    /// Creates a new and empty sharded linked list under specified size
    pub(crate) fn new(sharded_size: usize) -> Self {
        // Find power-of-two sizes best matching arguments
        let mut size = 1;
        while size < sharded_size {
            size <<= 1;
        }
        let shard_mask = size - 1;

        let mut lists = Vec::with_capacity(size as usize);
        for _ in 0..size {
            lists.push(Mutex::new(LinkedList::<L, T>::new()))
        }
        Self {
            lists: lists.into_boxed_slice(),
            count: AtomicUsize::new(0),
            shard_mask,
        }
    }

Review comment (suggestion):
You don't need this, because anything that implements this trait also implements `Link`, so they promised to follow these rules when implementing `Link`. It's not necessary to require the same thing twice.

However, you do require one other thing:
```suggestion
/// Implementations must guarantee that the id of an item does not change from
/// call to call.
```


Code after:
use crate::loom::sync::{Mutex, MutexGuard};
use std::sync::atomic::AtomicUsize;

use super::linked_list::{Link, LinkedList};

/// An intrusive linked list supporting highly concurrent updates.
///
/// It currently relies on `LinkedList`, so it is the caller's
/// responsibility to ensure the list is empty before dropping it.
///
/// Note: Due to its inner sharded design, the order of nodes cannot be guaranteed.
pub(crate) struct ShardedList<L, T> {
    lists: Box<[Mutex<LinkedList<L, T>>]>,
    count: AtomicUsize,
    shard_mask: usize,
}

/// Determines which linked list an item should be stored in.
///
/// # Safety
///
/// Implementations must guarantee that the id of an item does not change from
/// call to call.
pub(crate) unsafe trait ShardedListItem: Link {
    /// # Safety
    /// The provided pointer must point at a valid list item.
    unsafe fn get_shard_id(target: NonNull<Self::Target>) -> usize;
}

impl<L, T> ShardedList<L, T> {
    /// Creates a new and empty sharded linked list with the specified size.
    pub(crate) fn new(sharded_size: usize) -> Self {
        assert!(sharded_size.is_power_of_two());

        let shard_mask = sharded_size - 1;
        let mut lists = Vec::with_capacity(sharded_size);
        for _ in 0..sharded_size {
            lists.push(Mutex::new(LinkedList::<L, T>::new()))
        }
        Self {
            lists: lists.into_boxed_slice(),
            count: AtomicUsize::new(0),
            shard_mask,
        }
    }
}

/// Used to get the lock of shard.
pub(crate) struct ShardGuard<'a, L, T> {
    lock: MutexGuard<'a, LinkedList<L, T>>,
    count: &'a AtomicUsize,