Add non-host functionality to the previews blacklist

components/previews/core/previews_black_list_item.cc

Index: components/previews/core/previews_black_list_item.cc
diff --git a/components/previews/core/previews_black_list_item.cc b/components/previews/core/previews_black_list_item.cc
index 9fd3286772ca7497406a48351b8cb89bc7fae591..8c8465ea87a07ef1572c6d35b574946167bfbb8c 100644
--- a/components/previews/core/previews_black_list_item.cc
+++ b/components/previews/core/previews_black_list_item.cc
@@ -7,48 +7,70 @@
 #include <algorithm>
 
 #include "components/previews/core/previews_opt_out_store.h"
 
 namespace previews {
 
 PreviewsBlackListItem::OptOutRecord::OptOutRecord(base::Time entry_time,
                                                   bool opt_out)
     : entry_time(entry_time), opt_out(opt_out) {}
 
+PreviewsBlackListItem::OptOutRecord& PreviewsBlackListItem::OptOutRecord::
+operator=(const OptOutRecord&) = default;
+
+PreviewsBlackListItem::OptOutRecord::~OptOutRecord() {}
+
 PreviewsBlackListItem::PreviewsBlackListItem(
     size_t stored_history_length,
     int opt_out_black_list_threshold,
     base::TimeDelta black_list_duration)
     : max_stored_history_length_(stored_history_length),
       opt_out_black_list_threshold_(opt_out_black_list_threshold),
       max_black_list_duration_(black_list_duration),
       total_opt_out_(0) {}
 
 PreviewsBlackListItem::~PreviewsBlackListItem() {}
 
 void PreviewsBlackListItem::AddPreviewNavigation(bool opt_out,
                                                  base::Time entry_time) {
   DCHECK_LE(opt_out_records_.size(), max_stored_history_length_);
+  // It is typically expected that entries will come through with entry time
+  // later or earlier than the existing entries. Therefore, compare front
+  // and back first.
+  if (opt_out_records_.size() == 0 ||

[tbansal1, 2016/10/21 22:56:26]

s/opt_out_records_.size() == 0/opt_out_records_.empty()/

[RyanSturm, 2016/10/24 22:24:40]

Done.

+      entry_time < opt_out_records_.front().entry_time) {
+    if (opt_out_records_.size() == max_stored_history_length_) {
+      // Adding here would be pointless, as it will be removed afterward.

[tbansal1, 2016/10/21 22:56:26]

This is a bit confusing. May be it is simpler to just add it to the queue, and
then take it out later.

[RyanSturm, 2016/10/24 22:24:40]

Done.

+      return;
+    }
+    opt_out_records_.emplace_front(entry_time, opt_out);
+  } else if (entry_time >= opt_out_records_.back().entry_time) {
+    opt_out_records_.emplace_back(entry_time, opt_out);
+  } else {
+    // If the new time falls somewhere in between, binary search and linearly
+    // insert the new entry.
+    auto iter = std::lower_bound(
+        opt_out_records_.begin(), opt_out_records_.end(), entry_time,
+        [](const OptOutRecord& item, base::Time entry_time) {
+          // Prefer the new entry over the existing entry if this is a tie.
+          return item.entry_time <= entry_time;
+        });

[tbansal1, 2016/10/21 22:56:26]

Add a DCHECK that previous entry is smaller than the new entry.

You may also want to override comparator operator (<) in the struct. That might
make this more readable.

[RyanSturm, 2016/10/24 22:24:40]

Done.

+    OptOutRecord opt_out_record(entry_time, opt_out);
+    opt_out_records_.insert(iter, opt_out_record);
+  }
+
   if (opt_out && (!most_recent_opt_out_time_ ||
                   entry_time > most_recent_opt_out_time_.value())) {
     most_recent_opt_out_time_ = entry_time;
   }
   total_opt_out_ += opt_out ? 1 : 0;
 
-  // Find insert postion to keep the list sorted. Typically, this will be at the
-  // end of the list, but for systems with clocks that are not non-decreasing
-  // with time, this may not be the end. Linearly search from end to begin.
-  auto iter = opt_out_records_.rbegin();
-  while (iter != opt_out_records_.rend() && iter->entry_time > entry_time)
-    iter++;
-  opt_out_records_.emplace(iter.base(), entry_time, opt_out);
-
   // Remove the oldest entry if the size exceeds the history size.
   if (opt_out_records_.size() > max_stored_history_length_) {
     total_opt_out_ -= opt_out_records_.front().opt_out ? 1 : 0;
     opt_out_records_.pop_front();
   }
   DCHECK_LE(opt_out_records_.size(), max_stored_history_length_);
 }
 
 bool PreviewsBlackListItem::IsBlackListed(base::Time now) const {
   DCHECK_LE(opt_out_records_.size(), max_stored_history_length_);