Improving Entry API to get the keys back when they are unused

Issue by matthieu-m
Saturday Jan 17, 2015 at 15:09 GMT

For earlier discussion, see https://github.com/rust-lang/rust/issues/21298

This issue was labelled with: A-collections in the Rust repository

First of all, I would like to congratulate Gankro on the Entry API, it really simplified the interface of associative containers.

If I had one nit, however, it is that the entry methods available always consume the key.

Now, said key is taken by value so of course it is consumed, and the key is actually inserted in the container via the call to VacantEntry::insert, so it seems reasonable. However, in the case the key slot in the container is already occupied, and we get an OccupiedEntry as a result, there seems to be little reason not to return the key to the user.

For completeness, one could actually also improve VacantEntry so that is possible for it to hand over the key it had consumed, although why would one use the Entry API for look-up without any wish to insert is for now a mystery to me.

The main benefit of returning the un-consumed key is allowing reusing it. When the key is a simple integer, this has little appeal, however when the key owns heap-allocated memory (such as String) then the ability to re-use the buffer rather than continuously allocating/deallocating seems like a huge boon.

I prototyped the idea of an improved Occupied below, the modification is simple, and casual perusal of http://doc.rust-lang.org/src/std/collections/hash/map.rs.html#1150-1195 seems to show that simply modifying the lines 1175-1177 to:

return Occupied(OccupiedEntry{ elem: bucket, }, k); // Note the ", k"

would be the only change to HashMap implementation; likewise the entry change at lines 1366-1371 is simple enough:

pub enum Entry<'a, K: 'a, V: 'a> {
    /// An occupied Entry, and the unconsumed key
    Occupied(OccupiedEntry<'a, K, V>, K), // Note the ", K"
    /// A vacant Entry
    Vacant(VacantEntry<'a, K, V>),
}

I suspect, but have not verified, that other associative containers would likely be as easily modified. And of course, it would impact all consumers...

The example below show cases achieving buffer re-use through such an improved API, note how easy it is.

#![allow(unstable)]

use std::default::Default;

struct OccupiedEntry<K, V>;

struct VacantEntry<K, V> {
    entry: K,
}

enum Entry<K, V> {
    Occupied(OccupiedEntry<K, V>, K), // Simply add one more element to Occupied.
    Vacant(VacantEntry<K, V>),
}

impl<K, V> Entry<K, V> {
    fn new(key: K, really: bool) -> Entry<K, V> {
        if really {
            Entry::Occupied(OccupiedEntry, key)
        } else {
            Entry::Vacant(VacantEntry{entry: key})
        }
    }
}

fn main() {
    let mut acc: Vec<String> = vec!();

    let mut word: String = Default::default();
    for i in "Lorem iipsum and all that".split_str(" ") {
        word.clear();
        word.push_str(i);

        word = match Entry::<String, i32>::new(word, i.len() % 2 == 0) {
            Entry::Occupied(_, key) => { key }
            Entry::Vacant(v) => { acc.push(v.entry); Default::default() }
        };

        println!("{}\t{}", word, i);
    }

    println!("{:?}", acc);
}

Start with the earlier discussion in issue 21298 and the referenced std/collections/hash/map.rs Entry implementation. Compare the proposed Occupied and Vacant API shapes with the other associative containers mentioned in the issue, including the impact on consumers. Done means reaching an agreed API design and defining the RFC scope, since no settled implementation is identified.