Investigate augmenting `RawTable` directly about linked-hash-map HOT 6 CLOSED

As in you want upstream to expose RawTable?

from linked-hash-map.

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

from linked-hash-map.

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.

from linked-hash-map.

Forking std's impl seems more viable, honestly.

from linked-hash-map.

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

CC @carllerche.

from linked-hash-map.

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

from linked-hash-map.