Skip to content

ArrayHashMap: support all operations that ArrayList support #7391

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.

Sign up for GitHub

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

Jump to bottom
Closed
andrewrk opened this issue Dec 11, 2020 · 2 comments · Fixed by #7622
Closed

ArrayHashMap: support all operations that ArrayList support #7391

andrewrk opened this issue Dec 11, 2020 · 2 comments · Fixed by #7622
Labels
enhancement Solving this issue will likely involve adding new logic or components to the codebase. proposal This issue suggests modifications. If it also has the "accepted" label then it is planned. standard library This issue involves writing Zig code for the standard library.
Milestone
0.8.0

Comments

@andrewrk
Copy link
Member

andrewrk commented Dec 11, 2020 •
edited
Loading

This proposal is to treat ArrayHashMap as a data structure that can act both as an ArrayList and as a HashMap.

Here are some improvements I want to see:

  • getOrPut related functions should additionally return the entry index.
  • remove should be changed to swapRemove, and orderedRemove should be introduced. Both of these operations are present in ArrayList and match what will be happening to the Hash Map's inner ArrayList.
  • You should be able to directly modify the entries field which is an ArrayList. This causes all the methods which rely on the index data to become illegal to call, until you call reIndex() which then makes everything work again.
  • Introduce fromOwnedArrayList which takes ownership of an ArrayList as the entries field and calls reIndex()
  • Introduce shrinkRetainingCapacity which does the same thing as in ArrayList but maintains the hash map index.
  • Introduce shrinkAndFree which maps to ArrayList.shrink (and we should rename ArrayList.shrink to shrinkAndFree as well)
  • Introduce pop.

This use case comes from updating the Cache API files field to be an ArrayHashMap instead of an ArrayList:

zig/src/Cache.zig

Line 178 in f7d6006

files: std.ArrayListUnmanaged(File) = .{},

@andrewrk andrewrk added enhancement Solving this issue will likely involve adding new logic or components to the codebase. standard library This issue involves writing Zig code for the standard library. proposal This issue suggests modifications. If it also has the "accepted" label then it is planned. labels Dec 11, 2020
@andrewrk andrewrk added this to the 0.9.0 milestone Dec 11, 2020
@SpexGuy SpexGuy mentioned this issue Dec 11, 2020
Closed
andrewrk added a commit that referenced this issue Dec 11, 2020
@andrewrk
stage2: store Cache files in a map data structure
cfa0227 
Cache now stores files as an StringArrayListHashMap instead of an
ArrayList. The key is the resolved file path, to avoid adding the same
file multiple times into the cache system when it is depended on
multiple times. This avoids re-hashing file contents that have already
been inserted into the cache.

This was an attempt to fix #7308, but it is solving a different problem.
I do think it is worth considering this improvement regardless. On the
other hand, it might be duplicated effort since the layer of code above
this one probably wants to do its own de-duplication as well.

This implementation would be much nicer with #7391.
@andrewrk andrewrk mentioned this issue Dec 11, 2020
Closed
@daurnimator
Copy link
Contributor

This sounds a lot like the http_headers data structure that we had. https://github.com/ziglang/std-lib-orphanage/blob/2c36a7894c689ecbaf63d5f489bb0c68773410c4/std/http_headers.zig#L9-L17

@tetsuo-cpp
Copy link
Contributor

I'm going to give this a try.

@tetsuo-cpp tetsuo-cpp mentioned this issue Dec 31, 2020
Merged
@andrewrk andrewrk mentioned this issue Jan 5, 2021
Closed
@andrewrk andrewrk modified the milestones: 0.9.0, 0.8.0 Jan 7, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement Solving this issue will likely involve adding new logic or components to the codebase. proposal This issue suggests modifications. If it also has the "accepted" label then it is planned. standard library This issue involves writing Zig code for the standard library.
Projects
None yet
Milestone
0.8.0
Development

Successfully merging a pull request may close this issue.

std: Support equivalent ArrayList operations in ArrayHashMap tetsuo-cpp/zig
3 participants
@andrewrk @daurnimator @tetsuo-cpp