Investigate augmenting RawTable directly

[apasel422]

This crate wraps HashMap to provide ordered iteration with very little additional code, but its approach is essentially a hack and requires additional heap allocation in order to work. We should consider augmenting RawTable with a type parameter in order to implement this more efficiently. Normal HashMaps would use () internally for this parameter, while LinkedHashMap would use a struct Link { next: usize, prev: usize }.

CC @gankro.

[Gankra]

As in you want upstream to expose RawTable?

[apasel422]

More like having std itself provide LinkedHashMap instead of hacking on top of it as this crate currently does.

[apasel422]

What I want to do here is define RawTable as:

struct RawTable<K, V, A = ()> {
    capacity: usize,
    size: usize,
    hashes: Unique<u64>, // dynamic allocation of `cap` `u64`s | `cap` `K`s | `cap` `V`s | `cap` `A`s
    aug: A, // used to store the head/tail indices for the linked version
    marker: marker::PhantomData<(K, V)>,
}

and then

struct Link {
    next: usize,
    prev: usize,
}

pub struct LinkedHashMap<K, V> {
    table: RawTable<K, V, Link>,
    ...
}

This will let us remove the extra key/value indirection in the current impl along with the dummy node, though the performance implications remain to be determined.

[Gankra]

Forking std's impl seems more viable, honestly.

[apasel422]

I think we should look into this, even if it involves maintaining an internal copy of RawTable for the time being.

CC @carllerche.

[carllerche]

To follow up, I extracted the hash table as a standalone library that runs on stable Rust. https://github.com/carllerche/hash-table