contain-rs / linked-hash-map Goto Github PK

View Code? Open in Web Editor NEW

168.0 168.0 60.0 770 KB

A HashMap wrapper that holds key-value pairs in insertion order

Home Page: https://contain-rs.github.io/linked-hash-map/linked_hash_map/

License: Apache License 2.0

Rust 100.00%

linked-hash-map's People

Contributors

Stargazers

Watchers

linked-hash-map's Issues

upgrade to serde 1.0

As far as I know, this library is the primary mechanism for using sorted hashmaps in serde. As such it is a bottleneck for my serialization needs.

I can submit a PR, but I wanted to make sure you are around to merge it.

Track value instead of insertion order

Hey 👋

It would be cool if we could track not only the insertion order but also a value. For example I want the table ordered by a value within the map. Do you think this will be possible?

failed to unpack package `linked-hash-map v0.0.8

unable to get packages from source

Caused by:
  failed to unpack package `linked-hash-map v0.0.8 (registry file:///nix/store/lpjrc66ba8hyhl3v515d6wvxpv18bcp7-rustRegistry-2016-02-19-e33126f)`

Caused by:
  No such file or directory (os error 2)

rust-lang/cargo#2326 (comment)

Why back needs mutable reference?

I do not understand why back is pub fn back(&mut self) - it does compile and run all tests OK if back just uses shared reference e.g. pub fn back(& self).

Deprecate this crate in favor of indexmap?

Just saw this post by @bluss announcing indexmap 1.0.

Since linked-hash-map and indexmap seem to solve similar problems, and indexmap is more actively maintained, while linked-hash-map is in maintenance mode, it might be a good idea to officially deprecate this crate.

Not sure if @bluss agrees but indexmap seems like a good candidate for inclusion in the contain-rs orga, too.

Release 0.1.0

The current scheme of 0.0.x means we cannot release backwards-compatible changes. Cargo considers 0.0.x and 0.0.(x+1) to be incompatible.

Rename `LinkedHashMapEntry` to `Node`

feature "clippy" broken ( breaks build with --all-features )

I'm possibly misunderstanding, but I'm not sure how this feature (added in #53 ) is supposed to work.

 cargo +1.31.0 build --verbose --all-features
       Fresh serde v1.0.101                                                                                                                                  
       Fresh heapsize v0.4.2                                                                                                                                 
       Fresh serde_test v1.0.101                                                                                                                             
   Compiling linked-hash-map v0.5.2 (/home/kent/.cpanm/work/1570519221.32279/linked-hash-map-0.5.2)                                                          
     Running `rustc --crate-name linked_hash_map src/lib.rs --color always --crate-type lib --emit=dep-info,link -C debuginfo=2 --cfg 'feature="clippy"' --cfg 'feature="heapsize"' --cfg 'feature="heapsize_impl"' --cfg 'feature="nightly"' --cfg 'feature="serde"' --cfg 'feature="serde_impl"' --cfg 'feature="serde_test"' -C metadata=2cc050c6537ad532 -C extra-filename=-2cc050c6537ad532 --out-dir /home/kent/.cpanm/work/1570519221.32279/linked-hash-map-0.5.2/target/debug/deps -C incremental=/home/kent/.cpanm/work/1570519221.32279/linked-hash-map-0.5.2/target/debug/incremental -L dependency=/home/kent/.cpanm/work/1570519221.32279/linked-hash-map-0.5.2/target/debug/deps --extern heapsize=/home/kent/.cpanm/work/1570519221.32279/linked-hash-map-0.5.2/target/debug/deps/libheapsize-fe64547ac0565350.rlib --extern serde=/home/kent/.cpanm/work/1570519221.32279/linked-hash-map-0.5.2/target/debug/deps/libserde-eb5162ba86123336.rlib --extern serde_test=/home/kent/.cpanm/work/1570519221.32279/linked-hash-map-0.5.2/target/debug/deps/libserde_test-d043bfc3189a3bc2.rlib`
error[E0463]: can't find crate for `clippy`                                                                                                                  
  --> src/lib.rs:34:40                                                                                                                                       
   |                                                                                                                                                         
34 | #![cfg_attr(feature = "clippy", plugin(clippy))]                                                                                                        
   |                                        ^^^^^^ can't find crate                                                                                          
                                                                                                                                                             
error: aborting due to previous error                                                                                                                        
                                                                                                                                                             
For more information about this error, try `rustc --explain E0463`.                                                                                          
error: Could not compile `linked-hash-map`.                                                                                                                  

Caused by:
  process didn't exit successfully: `rustc --crate-name linked_hash_map src/lib.rs --color always --crate-type lib --emit=dep-info,link -C debuginfo=2 --cfg 'feature="clippy"' --cfg 'feature="heapsize"' --cfg 'feature="heapsize_impl"' --cfg 'feature="nightly"' --cfg 'feature="serde"' --cfg 'feature="serde_impl"' --cfg 'feature="serde_test"' -C metadata=2cc050c6537ad532 -C extra-filename=-2cc050c6537ad532 --out-dir /home/kent/.cpanm/work/1570519221.32279/linked-hash-map-0.5.2/target/debug/deps -C incremental=/home/kent/.cpanm/work/1570519221.32279/linked-hash-map-0.5.2/target/debug/incremental -L dependency=/home/kent/.cpanm/work/1570519221.32279/linked-hash-map-0.5.2/target/debug/deps --extern heapsize=/home/kent/.cpanm/work/1570519221.32279/linked-hash-map-0.5.2/target/debug/deps/libheapsize-fe64547ac0565350.rlib --extern serde=/home/kent/.cpanm/work/1570519221.32279/linked-hash-map-0.5.2/target/debug/deps/libserde-eb5162ba86123336.rlib --extern serde_test=/home/kent/.cpanm/work/1570519221.32279/linked-hash-map-0.5.2/target/debug/deps/libserde_test-d043bfc3189a3bc2.rlib` (exit code: 1)

Investigate augmenting `RawTable` directly

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.

stack overflow at map.into_iter.clone()

Here is my test code according to your test sample:
fn main(){
let map = LinkedHashMap::<&str, i32>::new();
let mut iter = map.into_iter();
println!("{:?}",iter.next());
let mut clone = iter.clone();//error:stack overflow
println!("{:?}",clone.next());
}

Is this correct?
Did you have the same error in your test sample?
thank you for watching my issue and looking forward your reply.

Add a `LinkedHashSet`

Lifetime issue with linked_hash_map iter_mut where there is none with hash_map iter_mut

The following code works without issue: https://is.gd/BIFxdX

However, when I comment out the hash_map usage and uncomment the linked_hash_map code - which is verbatim the same AFAICT- it can't resolve the lifetime of iter_mut

`LinkedHashMap<K, V>` is invariant in `K` and `V`

This is due to the use of *mut LinkedHashMapEntry<K, V> in its definition.

serde macros fail

#[derive(Clone, Serialize, Deserialize)]
pub struct Headers {
    data: LinkedHashMap<String, Vec<u8>>,
}

fails to compile with

error[E0277]: the trait bound `linked_hash_map::LinkedHashMap<std::string::String, std::vec::Vec<u8>>: serde::Serialize` is not satisfied
  --> src/proto/mod.rs:39:17
   |
39 | #[derive(Clone, Serialize, Deserialize)]
   |                 ^^^^^^^^^ the trait `serde::Serialize` is not implemented for `linked_hash_map::LinkedHashMap<std::string::String, std::vec::Vec<u8>>`
   |
   = note: required by `serde::ser::SerializeStruct::serialize_field`

error[E0277]: the trait bound `linked_hash_map::LinkedHashMap<std::string::String, std::vec::Vec<u8>>: serde::Deserialize` is not satisfied
  --> src/proto/mod.rs:39:28
   |
39 | #[derive(Clone, Serialize, Deserialize)]
   |                            ^^^^^^^^^^^ the trait `serde::Deserialize` is not implemented for `linked_hash_map::LinkedHashMap<std::string::String, std::vec::Vec<u8>>`
   |
   = note: required by `serde::de::SeqVisitor::visit`

error[E0277]: the trait bound `linked_hash_map::LinkedHashMap<std::string::String, std::vec::Vec<u8>>: serde::Deserialize` is not satisfied
  --> src/proto/mod.rs:39:28
   |
39 | #[derive(Clone, Serialize, Deserialize)]
   |                            ^^^^^^^^^^^ the trait `serde::Deserialize` is not implemented for `linked_hash_map::LinkedHashMap<std::string::String, std::vec::Vec<u8>>`
   |
   = note: required by `serde::de::MapVisitor::visit_value`

According to

https://dabo.guru/rust/screeps-api/serde/trait.Deserialize.html

String and Vec<u8> both have those methods implemented.

The serde implementation is enabled:

linked-hash-map = { version = "0.5", features = ["serde_impl"] }

Publish to crates

Could you please publish the current version? 0.0.10 is missing pub mod serde;

Implement `SerializeAs<_>` trait

This trait not being implemented forces users to use a normal HashMap in places where many would seriously prefer to use a linked one. An example of this can be seen below

The dataset here has keys that change on every request, and not being able to iterate through it sequentially is a massive pain

Document structs

Iter
IterMut
Keys
Values

Build failed with the latest nightly rustc

Compiling linked-hash-map v0.0.6
/root/.cargo/registry/src/github.com-121aea75f9ef2ce2/linked-hash-map-0.0.6/src/lib.rs:31:1: 31:28 error: #[feature] may not be used on the stable release channel
/root/.cargo/registry/src/github.com-121aea75f9ef2ce2/linked-hash-map-0.0.6/src/lib.rs:31 #![feature(hashmap_hasher)]
^~~~~~~~~~~~~~~~~~~~~~~~~~~
/root/.cargo/registry/src/github.com-121aea75f9ef2ce2/linked-hash-map-0.0.6/src/lib.rs:32:1: 32:21 error: #[feature] may not be used on the stable release channel
/root/.cargo/registry/src/github.com-121aea75f9ef2ce2/linked-hash-map-0.0.6/src/lib.rs:32 #![feature(box_raw)]
^~~~~~~~~~~~~~~~~~~~
/root/.cargo/registry/src/github.com-121aea75f9ef2ce2/linked-hash-map-0.0.6/src/lib.rs:33:1: 33:24 error: #[feature] may not be used on the stable release channel
/root/.cargo/registry/src/github.com-121aea75f9ef2ce2/linked-hash-map-0.0.6/src/lib.rs:33 #![feature(iter_order)]
^~~~~~~~~~~~~~~~~~~~~~~
error: aborting due to 3 previous errors

Release using serde 0.8.0

Please release a version using serde 0.8.0 so we can fix serde-rs/json#135

Return removed value in pop_front

The method name of pop_front is misleading since it does not return the removed value. Changing this would also make the method more useful.

Add `Entry` API

Implement `Clone` for fully parameterized `LinkedHashMap<K, V, S>`

HashMap doesn't expose its hash state, so we cannot clone fully parameterized LinkedHashMaps without cloning the original map and clearing it.

Memory leak with LinkedHashMap::insert

fn main() {
    let mut map = LinkedHashMap::new();

    for i in 0..=u32::max_value() {
        map.insert(i, [0; u16::max_value() as usize]);
    }

    drop(map);
}

Running heaptrack on the resulting binary, you manage to leak 6GB pretty easily:

Inserting a existing key will change the order of keys

Description:

Inserting a exising key will change the order of keys.

let mut map = LinkedHashMap::new();
map.insert("a",0);
map.insert("b",1);
map.insert("c",2);

Now, the order of the keys is "a", "b" and "c".
Then we update the value of "b" by insert method:

map.insert("b",0);

The order of the keys changes to "a", "c" and "b".
Intutively, I think the the behavior of map.insert("b",0); should be equivalent to map["b"] = 0; except the way they handle exceptions.
Is this a feature or a bug?

Implement `Extend<(&K, &V)> where K: Copy, V: Copy`

Missing or_default method

Hi,
I've had to replace a HashMap with a LinkedHashMap and my code broke where I was using map.entry(key).or_default().

That's a pretty common method for grouping things together using a Vec for example.

Would be a nice addition to this lib.

Invalid link for documentation.

Hello.
This link doesn't work.
https://github.com/contain-rs/linked-hash-map/blob/master/Cargo.toml#L14

Why don't you use docs.rs?

miri test failure

Bug report

Description

I've tested this crate with miri and faced the following error.

     Running target/x86_64-unknown-linux-gnu/debug/deps/test-cd7afc96213a7352

running 19 tests
test entries_insert ... ok
test test_borrow ... error: Undefined Behavior: type validation failed: encountered uninitialized reference
   --> /home/kogia-sima/PG/Rust/3rdparty/linked-hash-map/src/lib.rs:114:21
    |
114 |     let Node { key, value, .. } = *Box::from_raw(the_box);
    |                     ^^^^^ type validation failed: encountered uninitialized reference
    |
    = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
    = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information

    = note: inside `linked_hash_map::drop_empty_node::<test_borrow::Foo, &str>` at /home/kogia-sima/PG/Rust/3rdparty/linked-hash-map/src/lib.rs:114:21
    = note: inside `<linked_hash_map::LinkedHashMap<test_borrow::Foo, &str> as std::ops::Drop>::drop` at /home/kogia-sima/PG/Rust/3rdparty/linked-hash-map/src/lib.rs:809:17
    = note: inside `std::intrinsics::drop_in_place::<linked_hash_map::LinkedHashMap<test_borrow::Foo, &str>> - shim(Some(linked_hash_map::LinkedHashMap<test_borrow::Foo, &str>))` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:179:1
note: inside `test_borrow` at tests/test.rs:414:1
   --> tests/test.rs:414:1
    |
414 | }
    | ^
note: inside closure at tests/test.rs:373:1
   --> tests/test.rs:373:1
    |
373 | / fn test_borrow() {
374 | |     #[derive(PartialEq, Eq, Hash)] struct Foo(Bar);
375 | |     #[derive(PartialEq, Eq, Hash)] struct Bar(i32);
376 | |
...   |
413 | |     assert_eq!(map.remove(&Foo(Bar(2))), None);
414 | | }
    | |_^
    = note: inside `<[closure@tests/test.rs:373:1: 414:2] as std::ops::FnOnce<()>>::call_once - shim` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `test::__rust_begin_short_backtrace::<fn()>` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:516:5
    = note: inside closure at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:507:30
    = note: inside `<[closure@test::run_test::{closure#2}] as std::ops::FnOnce<()>>::call_once - shim(vtable)` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send> as std::ops::FnOnce<()>>::call_once` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:1328:9
    = note: inside `<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>> as std::ops::FnOnce<()>>::call_once` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:322:9
    = note: inside `std::panicking::try::do_call::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>, ()>` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:379:40
    = note: inside `std::panicking::try::<(), std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>>` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:343:19
    = note: inside `std::panic::catch_unwind::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>, ()>` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:396:14
    = note: inside `test::run_test_in_process` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:538:18
    = note: inside closure at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:449:39
    = note: inside `test::run_test::run_test_inner` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:474:13
    = note: inside `test::run_test` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:504:28
    = note: inside `test::run_tests::<[closure@test::run_tests_console::{closure#2}]>` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:283:13
    = note: inside `test::run_tests_console` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/console.rs:289:5
    = note: inside `test::test_main` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:121:15
    = note: inside `test::test_main_static` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:140:5
    = note: inside `main`
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:125:18
    = note: inside closure at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:66:18
    = note: inside `std::ops::function::impls::<impl std::ops::FnOnce<()> for &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>::call_once` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:259:13
    = note: inside `std::panicking::try::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:379:40
    = note: inside `std::panicking::try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:343:19
    = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:396:14
    = note: inside `std::rt::lang_start_internal` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:51:25
    = note: inside `std::rt::lang_start::<()>` at /home/kogia-sima/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:65:5
    = note: this error originates in an attribute macro (in Nightly builds, run with -Z macro-backtrace for more info)

error: aborting due to previous error

error: test failed, to rerun pass '--test test'

Environment

software	version
OS	Lubuntu 20.04.1 LTS
rustc	rustc 1.50.0-nightly (f76ecd066 2020-12-15)
target	x86_64-unknown-linux-gnu
linked-hash-map	0.5.3

Consider make it build with stable rustc

Currently it rely on these 3 unstable features:

#![feature(hashmap_hasher)]
#![feature(box_raw)]
#![feature(iter_order)]

Could it be replaced by some stable features to make it build with stable rustc.

Build failed with the latest nightly rustc

Build log

   Compiling linked-hash-map v0.0.7
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:112:28: 112:42 error: no associated item named `with_map` found for type `LinkedHashMap<K, V>` in the current scope
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:112     pub fn new() -> Self { Self::with_map(HashMap::new()) }
                                                                                                                               ^~~~~~~~~~~~~~
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:112:28: 112:42 note: the method `with_map` exists but the following trait bounds were not satisfied: `std::collections::hash::map::RandomState : core::hash::HashState`
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:116:9: 116:23 error: no associated item named `with_map` found for type `LinkedHashMap<K, V>` in the current scope
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:116         Self::with_map(HashMap::with_capacity(capacity))
                                                                                                            ^~~~~~~~~~~~~~
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:116:9: 116:23 note: the method `with_map` exists but the following trait bounds were not satisfied: `std::collections::hash::map::RandomState : core::hash::HashState`
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:621:14: 621:18 error: no method named `iter` found for type `&LinkedHashMap<K, V>` in the current scope
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:621         self.iter().map(|(k, v)| (k.clone(), v.clone())).collect()
                                                                                                                 ^~~~
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:621:14: 621:18 note: the method `iter` exists but the following trait bounds were not satisfied: `std::collections::hash::map::RandomState : core::hash::HashState`, `std::collections::hash::map::RandomState : core::hash::HashState`
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:621:14: 621:18 help: items from
�
traits can only be used if the trait is implemented and in scope; the following trait defines an item `iter`, perhaps you need to implement it:
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:621:14: 621:18 help: candidate #1: `core::slice::SliceExt`
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:621:35: 621:44 error: the type of this value must be known in this context
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:621         self.iter().map(|(k, v)| (k.clone(), v.clone())).collect()
                                                                                                                                      ^~~~~~~~~
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:621:46: 621:55 error: the type of this value must be known in this context
/home/zonyitoo/.cargo/registry/src/github.com-88ac128001ac3a9a/linked-hash-map-0.0.7/src/lib.rs:621         self.iter().map(|(k, v)| (k.clone(), v.clone())).collect()
                                                                                                                                                 ^~~~~~~~~

Building lru-cache, which depends on linked-hash-map v0.0.7.

Avoid allocating uninitialized memory for list head

Implement `append`

This can reuse the Boxes from the other map.

Add tests for drop

These should ensure that each key and each value is dropped exactly one time in various scenarios.

Change return type of `get_refresh` from `Option<&V>` to `Option<&mut V>`

Audit the sentinel node for Unsafe Code Guidelines Violations

As discussed in #96, LinkedHashMap is some very old code that uses some old patterns that the UCG really doesn't like.

Use a safer abstraction than `*mut LinkedHashMapEntry<K, V>`

Add a consuming in-order iterator

Fix doctests

dashes vs underscores is causing trouble

Maintained alternative: https://github.com/kyren/hashlink

Could be linked from the README.md. Clickable: https://github.com/kyren/hashlink.

Maps with the same entries but different orders do not compare equal

It's unclear if this is intentional, but if it is it should be clearly documented.

Implement `drain`

Rename `_hash_state` methods

with_hash_state should become with_hasher and with_capacity_and_hash_state should become with_capacity_and_hasher.

Investigate contiguous ordered map implementation

There is a PyPy blog post explaining their ordered, contiguous dictionaries. This means they'll be a lot faster than a linked implementation; PyPy even found it was competitive with their prior unordered implementation.

In essence you replace the linked list with a mostly compact vector, on the basis that insertions only add to the end and deletions are dealt with using occasional recompacting.

An implementation where sparse_array is a HashMap<KeyRef<K>, usize> would work, though it duplicates the information in the key and value. LinkedHashMap does too, so that's not much of a showstopper, though it is unfortunate.

Add values_mut

This method is missing.

Remove PartialEq::ne implementation

The build is currently failing with this error:

error: re-implementing `PartialEq::ne` is unnecessary
   --> src/lib.rs:686:5
    |
686 |       fn ne(&self, other: &Self) -> bool {
    |  _____^ starting here...
687 | |         self.len() != other.len() || self.iter().ne(other)
688 | |     }
    | |_____^ ...ending here
    |
note: lint level defined here
   --> src/lib.rs:35:38
    |
35  | #![cfg_attr(feature = "clippy", deny(clippy))]
    |                                      ^^^^^^
    = help: for further information visit https://github.com/Manishearth/rust-clippy/wiki#partialeq_ne_impl

crates.io not updated

Hey,

Could you publish the current version of this repo please ? Lru-cache needs it and it can't build right now. Thanks !

Remove `IndexMut` impl

For the reasoning, see rust-lang/rust#23448.