[Webkit-unassigned] [Bug 174715] Add a data structure for fixed sets of data that can switch its implementation strategy based on the input

bugzilla-daemon at webkit.org bugzilla-daemon at webkit.org
Sat Jul 22 11:55:04 PDT 2017


--- Comment #6 from Sam Weinig <sam at webkit.org> ---
Created attachment 316206

  --> https://bugs.webkit.org/attachment.cgi?id=316206&action=review

FixedSet Proof of Concept

I played with this idea a little this morning and got a simple proof of concept done that works with integers. It will need more work to generalize it, but that's why it's a proof of concept.

The way it works is you do something like:

    static constexpr auto set = makeFixedSet<unsigned>( 5, 4, 1, 2, 3 );

If chooses the data structure to use based on how many arguments are passed to makeFixedSet. For a single argument, it uses a FixedSetSingle. For 4 or less, it uses a FixedSetLinearSearchArray. And for 5 and more, it uses FixedSetBinarySearchArray.

The input does not need to be pre-sorted, as the FixedSetBinarySearchArray does a constexpr sort of the contents.

I left out a HashTable or Perfect Hash variant from this proof of concept, but once additional types are added, I don't think adding those will be too much trouble (famous last words).

You are receiving this mail because:
You are the assignee for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-unassigned/attachments/20170722/35010ea2/attachment.html>

More information about the webkit-unassigned mailing list