Error in hashmap.c

[sgraham]

I just discovered a bug in hashmap.c, which I found quite surprising as I'd been using it for quite a while and on some pretty large codebases!

I think the logic for TOMBSTONE is incorrect which can manifest with #undef when used by the preprocessor.

In particular:

• assume two keys A and B are inserted
• further assume A probes 10 elements, and B probes 5 elements.
• then, B is deleted, so its key is marked with a TOMBSTONE
• if A is then re-put: during probing, the TOMBSTONE from B's deletion will be found (https://github.com/rui314/chibicc/blob/main/hashmap.c#L92 ), and so there will be a duplicate of A added as the later entry will not be found.
• During a later rehash() this will eventually assert(), but in the interim, incorrect values would be retrieved.

I think the only easy solution is to never re-use TOMBSTONEs when doing a get_or_insert_entry().

I put the test data that discovered this at https://github.com/rui314/chibicc/pull/134 for reference (run ./chibicc -hashmap-test).

[rui314]

Ah, I see the problem. That's indeed a bug, and it's hard to believe I haven't noticed before. Thank you for pointing it out!

[fuhsnn]

Actually, you have! #53

[sgraham]

Oops, I should have done some more searching first I guess!