Remove ScopedVector from ui/events/.

ui/events/gesture_detection/motion_event_buffer.cc

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "ui/events/gesture_detection/motion_event_buffer.h"
 
 #include <stddef.h>
 
+#include <algorithm>
+#include <iterator>
 #include <utility>
 
 #include "base/trace_event/trace_event.h"
 #include "ui/events/gesture_detection/motion_event_generic.h"
 
 namespace ui {
 namespace {
 
 // Latency added during resampling. A few milliseconds doesn't hurt much but
 // reduces the impact of mispredicted touch positions.
 const int kResampleLatencyMs = 5;
 
 // Minimum time difference between consecutive samples before attempting to
 // resample.
 const int kResampleMinDeltaMs = 2;
 
 // Maximum time to predict forward from the last known state, to avoid
 // predicting too far into the future.  This time is further bounded by 50% of
 // the last time delta.
 const int kResampleMaxPredictionMs = 8;
 
-typedef ScopedVector<MotionEventGeneric> MotionEventVector;
+using MotionEventVector = std::vector<std::unique_ptr<MotionEventGeneric>>;
 
 float Lerp(float a, float b, float alpha) {
   return a + alpha * (b - a);
 }
 
 bool CanAddSample(const MotionEvent& event0, const MotionEvent& event1) {
   DCHECK_EQ(event0.GetAction(), MotionEvent::ACTION_MOVE);
   if (event1.GetAction() != MotionEvent::ACTION_MOVE)
     return false;
 
@@ skipping 11 matching lines @@
   }
 
   return true;
 }
 
 bool ShouldResampleTool(MotionEvent::ToolType tool) {
   return tool == MotionEvent::TOOL_TYPE_UNKNOWN ||
          tool == MotionEvent::TOOL_TYPE_FINGER;
 }
 
-size_t CountSamplesNoLaterThan(const MotionEventVector& batch,
-                               base::TimeTicks time) {
-  size_t count = 0;
-  while (count < batch.size() && batch[count]->GetEventTime() <= time)
-    ++count;
-  return count;
-}
-
+// Splits a chunk of events from the front of the provided |batch| and returns
+// it. Requires that |batch| is sorted.
 MotionEventVector ConsumeSamplesNoLaterThan(MotionEventVector* batch,
                                             base::TimeTicks time) {
   DCHECK(batch);
-  size_t count = CountSamplesNoLaterThan(*batch, time);
-  DCHECK_GE(batch->size(), count);
-  if (count == 0)
-    return MotionEventVector();
-
-  if (count == batch->size())
-    return std::move(*batch);
-
-  // TODO(jdduke): Use a ScopedDeque to work around this mess.
-  MotionEventVector unconsumed_batch;
-  unconsumed_batch.insert(
-      unconsumed_batch.begin(), batch->begin() + count, batch->end());
-  batch->weak_erase(batch->begin() + count, batch->end());
-
-  unconsumed_batch.swap(*batch);
-  DCHECK_GE(unconsumed_batch.size(), 1U);
-  return unconsumed_batch;
+  auto first_kept_event = std::partition_point(

[Avi (use Gerrit), 2017/01/14 00:49:42]

Note that the queue is sorted by time, which means that we can use utility
functions that assume partitions. This means that this lookup is a binary search
rather than the linear search we were using before.

+      batch->begin(), batch->end(),
+      [time](const std::unique_ptr<MotionEventGeneric>& event) {
+        return event->GetEventTime() <= time;
+      });
+  MotionEventVector result(std::make_move_iterator(batch->begin()),
+                           std::make_move_iterator(first_kept_event));
+  batch->erase(batch->begin(), first_kept_event);
+  return result;
 }
 
 // Linearly interpolate the pointer position between two MotionEvent samples.
 // Only pointers of finger or unknown type will be resampled.
 PointerProperties ResamplePointer(const MotionEvent& event0,
                                   const MotionEvent& event1,
                                   size_t event0_pointer_index,
                                   size_t event1_pointer_index,
                                   float alpha) {
   DCHECK_EQ(event0.GetPointerId(event0_pointer_index),
@@ skipping 51 matching lines @@
 
   DCHECK(event);
   event->set_button_state(event0.GetButtonState());
   return event;
 }
 
 // Synthesize a compound MotionEventGeneric event from a sequence of events.
 // Events must be in non-decreasing (time) order.
 std::unique_ptr<MotionEventGeneric> ConsumeSamples(MotionEventVector events) {
   DCHECK(!events.empty());
-  std::unique_ptr<MotionEventGeneric> event(events.back());
-  for (size_t i = 0; i + 1 < events.size(); ++i)
-    event->PushHistoricalEvent(std::unique_ptr<MotionEvent>(events[i]));
-  events.weak_clear();
+  std::unique_ptr<MotionEventGeneric> event = std::move(events.back());
+  events.pop_back();
+  for (auto& historic_event : events)
+    event->PushHistoricalEvent(std::move(historic_event));
   return event;
 }
 
 // Consume a series of event samples, attempting to synthesize a new, synthetic
 // event if the samples and sample time meet certain interpolation/extrapolation
 // conditions. If such conditions are met, the provided samples will be added
 // to the synthetic event's history, otherwise, the samples will be used to
 // generate a basic, compound event.
 // TODO(jdduke): Revisit resampling to handle cases where alternating frames
 // are resampled or resampling is otherwise inconsistent, e.g., a 90hz input
 // and 60hz frame signal could phase-align such that even frames yield an
 // extrapolated event and odd frames are not resampled, crbug.com/399381.
 std::unique_ptr<MotionEventGeneric> ConsumeSamplesAndTryResampling(
     base::TimeTicks resample_time,
     MotionEventVector events,
     const MotionEvent* next) {
   const ui::MotionEvent* event0 = nullptr;
   const ui::MotionEvent* event1 = nullptr;
   if (next) {
     DCHECK(resample_time < next->GetEventTime());
     // Interpolate between current sample and future sample.
-    event0 = events.back();
+    event0 = events.back().get();
     event1 = next;
   } else if (events.size() >= 2) {
     // Extrapolate future sample using current sample and past sample.
-    event0 = events[events.size() - 2];
-    event1 = events[events.size() - 1];
+    event0 = events[events.size() - 2].get();
+    event1 = events[events.size() - 1].get();
 
     const base::TimeTicks time1 = event1->GetEventTime();
     base::TimeTicks max_predict =
         time1 +
         std::min((event1->GetEventTime() - event0->GetEventTime()) / 2,
                  base::TimeDelta::FromMilliseconds(kResampleMaxPredictionMs));
     if (resample_time > max_predict) {
       TRACE_EVENT_INSTANT2("input",
                            "MotionEventBuffer::TryResample prediction adjust",
                            TRACE_EVENT_SCOPE_THREAD,
@@ skipping 19 matching lines @@
     TRACE_EVENT_INSTANT1("input",
                          "MotionEventBuffer::TryResample failure",
                          TRACE_EVENT_SCOPE_THREAD,
                          "event_delta_too_small(ms)",
                          delta.InMilliseconds());
     return ConsumeSamples(std::move(events));
   }
 
   std::unique_ptr<MotionEventGeneric> resampled_event =
       ResampleMotionEvent(*event0, *event1, resample_time);
-  for (size_t i = 0; i < events.size(); ++i)
-    resampled_event->PushHistoricalEvent(
-        std::unique_ptr<MotionEvent>(events[i]));
-  events.weak_clear();
+  for (auto& historic_event : events)
+    resampled_event->PushHistoricalEvent(std::move(historic_event));
   return resampled_event;
 }
 
 }  // namespace
 
 MotionEventBuffer::MotionEventBuffer(MotionEventBufferClient* client,
                                      bool enable_resampling)
     : client_(client), resample_(enable_resampling) {
 }
 
@@ skipping 21 matching lines @@
 
   std::unique_ptr<MotionEventGeneric> clone =
       MotionEventGeneric::CloneEvent(event);
   if (buffered_events_.empty()) {
     buffered_events_.push_back(std::move(clone));
     client_->SetNeedsFlush();
     return;
   }
 
   if (CanAddSample(*buffered_events_.front(), *clone)) {
+    // Ensure that buffered_events_ is ordered.
     DCHECK(buffered_events_.back()->GetEventTime() <= clone->GetEventTime());
   } else {
     FlushWithoutResampling(std::move(buffered_events_));
   }
 
   buffered_events_.push_back(std::move(clone));
   // No need to request another flush as the first event will have requested it.
 }
 
 void MotionEventBuffer::Flush(base::TimeTicks frame_time) {
   if (buffered_events_.empty())
     return;
 
   // Shifting the sample time back slightly minimizes the potential for
   // misprediction when extrapolating events.
   if (resample_)
     frame_time -= base::TimeDelta::FromMilliseconds(kResampleLatencyMs);
 
   // TODO(jdduke): Use a persistent MotionEventVector vector for temporary
   // storage.
-  MotionEventVector events(
-      ConsumeSamplesNoLaterThan(&buffered_events_, frame_time));
+  MotionEventVector events =
+      ConsumeSamplesNoLaterThan(&buffered_events_, frame_time);
   if (events.empty()) {
     DCHECK(!buffered_events_.empty());
     client_->SetNeedsFlush();
     return;
   }
 
   if (!resample_ || (events.size() == 1 && buffered_events_.empty())) {
     FlushWithoutResampling(std::move(events));
     if (!buffered_events_.empty())
       client_->SetNeedsFlush();
     return;
   }
 
   FlushWithResampling(std::move(events), frame_time);
 }
 
 void MotionEventBuffer::FlushWithResampling(MotionEventVector events,
                                             base::TimeTicks resample_time) {
   DCHECK(!events.empty());
   base::TimeTicks original_event_time = events.back()->GetEventTime();
   const MotionEvent* next_event =
-      !buffered_events_.empty() ? buffered_events_.front() : nullptr;
+      !buffered_events_.empty() ? buffered_events_.front().get() : nullptr;
 
   std::unique_ptr<MotionEventGeneric> resampled_event =
       ConsumeSamplesAndTryResampling(resample_time, std::move(events),
                                      next_event);
   DCHECK(resampled_event);
 
   // Log the extrapolated event time, guarding against subsequently queued
   // events that might have an earlier timestamp.
   if (!next_event && resampled_event->GetEventTime() > original_event_time) {
     last_extrapolated_event_time_ = resampled_event->GetEventTime();
   } else {
     last_extrapolated_event_time_ = base::TimeTicks();
   }
 
   client_->ForwardMotionEvent(*resampled_event);
   if (!buffered_events_.empty())
     client_->SetNeedsFlush();
 }
 
 void MotionEventBuffer::FlushWithoutResampling(MotionEventVector events) {
   last_extrapolated_event_time_ = base::TimeTicks();
   if (events.empty())
     return;
 
   client_->ForwardMotionEvent(*ConsumeSamples(std::move(events)));
 }
 
 }  // namespace ui