Skip to content
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

Review and improve HashMap's handling of an empty table #53853

Closed
RalfJung opened this issue Aug 31, 2018 · 3 comments
Closed

Review and improve HashMap's handling of an empty table #53853

RalfJung opened this issue Aug 31, 2018 · 3 comments
Labels
A-collections Area: std::collections. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@RalfJung
Copy link
Member

In #53804, I fixed the most immediate problem arising from how HashMap handles the empty table, but @gnzlbg still (rightly) sees more problems. We still use 1 instead of NonNull::dangling() as value for EMPTY, and ptr() even tests equality with EMPTY to return NULL instead. We can't really use non-NULL pointers as sentinel values like that, and NULL is often a worse choice than an aligned dangling pointer because the latter are at least valid for zero-sized operations.

See here for @gnzlbg's suggestions.

@jonas-schievink jonas-schievink added A-collections Area: std::collections. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. labels Jan 27, 2019
@Mark-Simulacrum
Copy link
Member

I'm going to close this issue since our hash maps are now a thin wrapper around hashbrown which hopefully doesn't suffer from these issues; if it does, this should be refiled upstream. A cursory examination didn't find any obvious problems for sentinel use of dangling or so.

@gnzlbg
Copy link
Contributor

gnzlbg commented Dec 24, 2019

Yes none of this applies to the new hashbrown impl. cc @Amanieu in case they want to re-read the comments and any of that rings a bell, but I haven't see anything like that in hashbrown.

@Amanieu
Copy link
Member

Amanieu commented Dec 24, 2019

I agree, I don't think any of this applies to hashbrown.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-collections Area: std::collections. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests

5 participants