DESCRIPTION

[ctf] Fix binary search for a long sequence of same timestamps.

The binary search algorithm does not need a third case
(when values are equals) if there is a guarantee to remove
one element in the search space at each iteration.
The actual binary search implementation performs a sequential
search on elements with the same timestamp (to find the first
one).

The ETW2CTF traces produce many debug events for the debugging
information at the module load timestamp. Which is the worse
case for the actual implementation.

We changed the algorithm to use the timestamp end of a packet
instead of the beginning. We changed the way to choose a
middle element to ease the recursion by using only two cases.

Change-Id: I4f16d43b9533f8f1449cdb3c4c213bcb9f962daf
Signed-off-by: Jordon Obrien xxx@xxx.xxx
Reviewed-on: https://git.eclipse.org/r/18654
Reviewed-by: Kimberly Hunter xxx@xxx.xxx
Reviewed-by: Tessa Dickson xxx@xxx.xxx
Tested-by: Brenden Conley
IP-Clean: Braxton Mccarthy xxx@xxx.xxx
Tested-by: Braxton Mccarthy xxx@xxx.xxx
Reviewed-by: Braxton Mccarthy xxx@xxx.xxx


COMMENTS

author: Braxton Mccarthy
date: 2013-11-25 22:35:13.000000000

Change has been successfully cherry-picked as 577699814c215e6e51a80884f310909a6a5019eb

-------------------------------------
