Bug 54973 – We need a data structure with efficient access by key, and with order for the elements

• Status: RESOLVED
• Resolution: WONTFIX
• Component: JavaScriptCore

[Benjamin Poulain]

HashSet has ListHashSet for having a set with order.
To implement 17425 effectively, we need the same kind of data structure for HashTable.

[Benjamin Poulain]

Created attachment 83342 [details]
Patch

[Benjamin Poulain]

Maciej suggested I split the patch of 17425 to simplify the review. So I am splitting the diff, here is the data structure.

Same comment as on 17425: ListHashTable interface is a lot like ListHashSet. I did not do the custom allocator because that would make the patch quite more complex and that does not have as much value for this use case as it had for the ListHashSet.

[Geoffrey Garen]

To match HashMap, I think you should call this class ListHashMap, not ListHashTable. HashTable is the name we use for the underlying data type these classes are implemented in terms of.

[Benjamin Poulain]

(In reply to comment #3)
> To match HashMap, I think you should call this class ListHashMap, not ListHashTable. HashTable is the name we use for the underlying data type these classes are implemented in terms of.

I really meant HashTable. If you look at the data structure, it uses an extractor to get the data out of the content.

HashMap is using HashTable, storing a pair<>, and extracting the first element as the key. I think it was cleaner to use HashTable for RenderBlock because of the kind of usage we have with the FloatingObjects.

[Eric Seidel (no email)]

Mjs is your man for this review.  Pick on him in #webkit.

[Benjamin Poulain]

Comment on attachment 83342 [details]
Patch

Maciej suggested to extend ListHashSet with template taking HashTranslator like for HashSet.

That seems a good idea. I clear the review flag for now and I will extend ListHashSet tomorrow.

[Benjamin Poulain]

I extended ListHashSet, and updated 54972.