Add LinkedList::{retain,retain_mut}

[TennyZhuang]

Proposal

Problem statement

It would be convenient if LinkedList had retain/retain_mut methods just like many other collections. We can migrate between different collections easily.

Motivating examples or use cases

When implementing MVCC transactions in database, it's very common to store the active transactions as a list. They'll be garbage collected by a monotonic version.

txn.version > gc_versionlet mut active_txns = LinkedList::new();;
let mut gc_version = 0;
// ...

while gc_triggerer.next() {
    active_txns.retain(|&txn| txn.version > gc_version);
}

In fact, there are similar use cases like other collections.

Solution sketch

pub struct LinkedList;

impl LinkedList {
    pub fn retain_mut<F>(&mut self, mut f: F)
    where
        F: FnMut(&mut T) -> bool;

    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> bool;
}

Alternatives

Links and related work

• Vec::retain
• Vec::retain_mut

[Amanieu]

We discussed this in the libs-api meeting today. We're happy to add this, but with only a single retain method which accepts &mut T. The split between retain and retain_mut was to correct a mistake: retain was stabilized early on with a &T signature and changing it would have broken many crates.