ss: remove linear component from node search.
authorLoïc Prieur-Drevon <loic.prieurdrevon@gmail.com>
Fri, 9 Dec 2016 18:34:04 +0000 (13:34 -0500)
committerAlexandre Montplaisir <alexmonthy@efficios.com>
Thu, 15 Dec 2016 01:26:28 +0000 (20:26 -0500)
commit3996feb913440110b0ab7fb9b0f9e6ccf94888cf
treeca8e1b26eb6711262055bbe749249b5c9871a492
parent7c7fe5e97a181c8a8b5bcbf74e60a173c1db46c7
ss: remove linear component from node search.

Before, nodes had their intervals only sorted by end times,
which meant finding the first interval which started later
than time t implied a binary search for any interval ending
at time t, then a linear iteration to the first interval
ending before (inclusively) t.
We remove this component by ordering intervals by end times
then by start times, so that the binary search can directly
return the first interval ending before (inclusively) t.

Change-Id: I3e4fd02880d56360fc082023c08b92f8a6e4350e
Signed-off-by: Loïc Prieur-Drevon <loic.prieurdrevon@gmail.com>
Reviewed-on: https://git.eclipse.org/r/86865
Reviewed-by: Matthew Khouzam <matthew.khouzam@ericsson.com>
Reviewed-by: Hudson CI
Reviewed-by: Alexandre Montplaisir <alexmonthy@efficios.com>
Tested-by: Alexandre Montplaisir <alexmonthy@efficios.com>
statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTInterval.java
statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java
This page took 0.026143 seconds and 5 git commands to generate.