-
Notifications
You must be signed in to change notification settings - Fork 881
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Error in hashmap.c #135
Comments
sgraham
added a commit
to sgraham/dyibicc
that referenced
this issue
Oct 30, 2023
Reported upstream at rui314/chibicc#135 TOMBSTONE entries cannot be reused, or subsequent probes can be incorrect.
sgraham
added a commit
to sgraham/dyibicc
that referenced
this issue
Oct 30, 2023
Reported upstream at rui314/chibicc#135 TOMBSTONE entries cannot be reused, or subsequent probes can be incorrect.
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! |
Actually, you have! #53 |
Oops, I should have done some more searching first I guess! |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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:
delete
d, so its key is marked with aTOMBSTONE
put
: during probing, theTOMBSTONE
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.rehash()
this will eventuallyassert()
, but in the interim, incorrect values would be retrieved.I think the only easy solution is to never re-use
TOMBSTONE
s when doing aget_or_insert_entry()
.I put the test data that discovered this at #134 for reference (run
./chibicc -hashmap-test
).The text was updated successfully, but these errors were encountered: