Prevent interleaving calls to HashMap.removeAssertDiscard() / HashMap.putAssumeCapacity() from causing the hashmap to run out of memory

[lithdew]

The test passes for ArrayHashMap and otherwise causes an integer overflow on the available number of Entry's that may be reclaimed.

Test [1/1] test "HashMapUnmanaged.removeAssertDiscard() / HashMapUnmanaged.putAssumeCapac... integer overflow
/home/kenta/Desktop/zig/lib/std/hash_map.zig:621:32: 0x20b69b in std.hash_map.HashMapUnmanaged(usize,usize,std.hash_map.getAutoHashFn(usize).hash,std.hash_map.getAutoEqlFn(usize).eql,80).getOrPutAssumeCapacity (test)
                self.available -= 1;
                               ^
/home/kenta/Desktop/zig/lib/std/hash_map.zig:475:52: 0x207064 in std.hash_map.HashMapUnmanaged(usize,usize,std.hash_map.getAutoHashFn(usize).hash,std.hash_map.getAutoEqlFn(usize).eql,80).putAssumeCapacity (test)
            const gop = self.getOrPutAssumeCapacity(key);
                                                   ^
/home/kenta/Desktop/sleepy/test.zig:17:30: 0x2068c5 in test "HashMapUnmanaged.removeAssertDiscard() / HashMapUnmanaged.putAssumeCapacity()" (test)
        map.putAssumeCapacity(i, 0);

const std = @import("std");
const testing = std.testing;

test "HashMapUnmanaged.removeAssertDiscard() / HashMapUnmanaged.putAssumeCapacity()" {
    const allocator = testing.allocator;

    var map: std.AutoHashMapUnmanaged(usize, usize) = .{};
    defer map.deinit(allocator);

    try map.ensureCapacity(allocator, 10);

    var i: usize = 0;
    while (i < 20) : (i += 1) {
        if (i >= 10) {
            map.removeAssertDiscard(i - 10);
        }
        map.putAssumeCapacity(i, 0);
    }
}

[Sahnvour]

I think this is expected behaviour, and that may expose a flaw in the design or the API (depending on your point of view).
Having deleted items leaving tombstones means that they still participate in the load of the hashmap, hence available is not incremented. Some of your deleted elements may not be reused directly when inserting new ones, so available is decremented in those cases, and eventually drops below 0.

To phrase it another way, tombstones play a role in wether a call to putAssumeCapacity is legal or not.

[jorangreef]

@Sahnvour I believe it's possible for tombstones to be replaced when inserting on the linear probing path? They're only needed when removing to avoid breaking an existing linear probe path (by putting an empty pothole in it) depended on by another linear probe path. However, it's safe to later replace them with other values because that leaves the other linear probe path still intact.

I think that would be the right fix (i.e. don't conflate tombstones and free slots, but resize only when there are no free slots remaining) for these issues and make the API less surprising, especially for embedded use cases where static allocation is required.

[andrewrk]

Landed in in ef0566d.