Bug: IndexMap fails to insert more than u16::MAX keys.

[ValouBambou]

I ran into this bug when inserting a lot of keys in an IndexMap, and it turns out that when my keys are bigger than an u16 they are not inserted properly. Here is a minimal reproducible code.

use heapless::FnvIndexMap;

fn main() {
    const N: usize = 1 << 17;
    let mut map = FnvIndexMap::<u32, usize, N>::new();
    for i in 1..(0xffff + 3) {
        let block = i;
        let idx = i as usize - 1;
        map.insert(block, idx).unwrap();
        assert!(map.contains_key(&block), "{}", i);
    }
}

I have no idea on why this happens. Does anyone have an idea ?
EDIT: the issue is not the values but the number of keys to insert shifting the start and end of the loop leads to the same bug
EDIT 2: the bug is present in the 0.8.0 version but fixed in 0.9.0 and on the latest commit on master.
EDIT 3: the bug is not fixed in any versions

[ValouBambou]

I see that the new release fixing this bug is not published to creates.io is this intentional ?
EDIT: I saw #568 and understand why the 0.9.0 release is not ready to ship. So I will close this. But maybe doing a 0.8.1 release with fixes including this one could be nice.

[ValouBambou]

I noticed that the code path with exit if dist is too long in find

heapless/src/index_map.rs

Line 186 in 6b17767

return None;

is taken but removing the hole if statement doesn't solve the issue, so I guess there is more to it. I've not figured out how the algorithm works in details, maybe replacing the hash value with u32 is enough, but I've not tried. Even if it worked, we should probably rethink it with a LenT type to avoid increasing the size from u16 to u32 when it's not necessary.

[ValouBambou]

I tried in a fork to replace u16 by u32 for the hash and pos, and it seems to work. So I guess it is possible to make a smarter system based on the size of the const N:usize like it is done in Vec.

Also, even if this is too much work there is a quick fix solution, that doesn't solve the problem but at least warn people about the issue would be to add an assert!(CAPACITY < (1 << 16)) in this line

heapless/src/index_map.rs

Line 735 in 6b17767

assert!(N.is_power_of_two());