Bug 104890 – Attempt to rationalize and simplify WTF::binarySearch

• Status: RESOLVED
• Resolution: FIXED
• Component: Web Template Framework

[Filip Pizlo]

Currently the WTF::binarySearch API is a bit of a mess.  Here are the things that are wrong with it:

1) Three versions of binarySearch(), one that uses template specialization to determine the key extractor, one that uses a functor, and one that accepts array-like types that support operator[] but not operator++/--.

2) Inability to easily attempt a binary search an return some "error code" when the element is not found.  Instead the only mode like this returns an adjacent element, so then you have to do more checks to validate whether the element belonged to the array.

3) Inaccurate description of the approximate search.  To do an approximate search you pass WTF::KeyMustNotBePresentInArray, which to me implies that you want to assert that the key *is not* present.  In fact this mode instead asking the search to *not assert* that the key *is* present in the array.  That's kind of a bid difference.

We should fix this.

[Filip Pizlo]

Created attachment 179226 [details]
the patch

[Filip Pizlo]

Created attachment 179227 [details]
the patch

[Early Warning System Bot]

Comment on attachment 179227 [details]
the patch

Attachment 179227 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/15316198

[Filip Pizlo]

Created attachment 179231 [details]
the patch

[Filip Pizlo]

Created attachment 179232 [details]
StdLibExtras.h

Diff really did a poor job of showing what I changed.  Uploading my copy of StdLibExtras.h for clarity.  For most purposes, the code relating to binarySearch was just completely changed so this might make for easier reviewing.

[Maciej Stachowiak]

Comment on attachment 179231 [details]
the patch

View in context: https://bugs.webkit.org/attachment.cgi?id=179231&action=review

Here's review comments on the implementation, looking at call sites now.

> Source/WTF/ChangeLog:16
> +        Binary search now has three modes:
> +
> +        The default, aka KeyMustBePresentInArray: assert that the key was found, but return
> +        an adjacent element if it wasn't found, if asserts are turned off.
> +        
> +        KeyMightNotBePresentInArray, aka tryBinarySearch: return 0 if the key wasn't found.
> +        
> +        ReturnAdjacentElementIfKeyIsNotPresent, aka approximateBinarySearch: if the key is
> +        not found, return an adjacent element (either the left or right; no guarantee which).

This comment reflects the older version more. You should probably mention the three public interface functions, and as a side note maybe the corresponding flags passed to binarySearchImpl

> Source/WTF/wtf/StdLibExtras.h:188
> +    // The array must contain at least one element (pre-condition, array does conatin key).

tyop - should be "contain", not "contain"

> Source/WTF/wtf/StdLibExtras.h:228
> +// If the element is not found, crash if asserts are enabled, and behave like AlwaysReturnAdjacentElement in release builds.

Should probably say "behave like tryBinarySearch" instead of "behave like AlwaysReturnAdjacentElement" (especially since the actual name is ReturnAdjacentElementIfKeyIsNotPresent)

[Early Warning System Bot]

Comment on attachment 179231 [details]
the patch

Attachment 179231 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/15316213

[Filip Pizlo]

Created attachment 179233 [details]
the patch

Build fixes, and style fixes.

[Maciej Stachowiak]

Comment on attachment 179233 [details]
the patch

r=me

[Build Bot]

Comment on attachment 179233 [details]
the patch

Attachment 179233 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/15314201

[Filip Pizlo]

Created attachment 179378 [details]
patch for landing

Attempting to work around VS weirdness.

[Filip Pizlo]

Landed in http://trac.webkit.org/changeset/137709