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.
Created attachment 179226 [details] the patch
Created attachment 179227 [details] the patch
Comment on attachment 179227 [details] the patch Attachment 179227 [details] did not pass qt-ews (qt): Output: http://queues.webkit.org/results/15316198
Created attachment 179231 [details] the patch
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.
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)
Comment on attachment 179231 [details] the patch Attachment 179231 [details] did not pass qt-ews (qt): Output: http://queues.webkit.org/results/15316213
Created attachment 179233 [details] the patch Build fixes, and style fixes.
Comment on attachment 179233 [details] the patch r=me
Comment on attachment 179233 [details] the patch Attachment 179233 [details] did not pass win-ews (win): Output: http://queues.webkit.org/results/15314201
Created attachment 179378 [details] patch for landing Attempting to work around VS weirdness.
Landed in http://trac.webkit.org/changeset/137709