Use linked hash map for broken alternative service queue.

net/http/http_server_properties_impl.cc

Index: net/http/http_server_properties_impl.cc
diff --git a/net/http/http_server_properties_impl.cc b/net/http/http_server_properties_impl.cc
index 525ae641c09767a4f0356411b68cf963d5a58f00..bc8cdccdec3eff0c78cdc0ed366948634edaed6e 100644
--- a/net/http/http_server_properties_impl.cc
+++ b/net/http/http_server_properties_impl.cc
@@ -320,12 +320,20 @@ void HttpServerPropertiesImpl::SetBrokenAlternateProtocol(
   it->second.is_broken = true;
   const AlternativeService alternative_service(alternate.protocol,
                                                server.host(), alternate.port);
-  int count = ++broken_alternate_protocol_map_[alternative_service];
+  int count = ++recently_broken_alternative_services_[alternative_service];
   base::TimeDelta delay =
       base::TimeDelta::FromSeconds(kBrokenAlternateProtocolDelaySecs);
   base::TimeTicks when = base::TimeTicks::Now() + delay * (1 << (count - 1));
-  broken_alternate_protocol_list_.push_back(
-      BrokenAlternateProtocolEntryWithTime(alternative_service, when));
+  auto result = broken_alternative_services_.insert(
+      std::make_pair(alternative_service, when));
+  // If alternative service is already in expiration queue,

[Ryan Hamilton, 2015/03/09 19:48:27]

Since checking membership is constant time, how 'bout we just check to see if
it's already in the map and then just return, instead of adding and then
removing?

[Bence, 2015/03/09 21:24:35]

Done.

+  // then remove it, and enqueue with new expiration time.
+  if (!result.second) {
+    broken_alternative_services_.erase(result.first);
+    ignore_result(broken_alternative_services_.insert(
+        std::make_pair(alternative_service, when)));
+    return;
+  }
 
   // Do not leave this host as canonical so that we don't infer the other
   // hosts are also broken without testing them first.
@@ -333,7 +341,7 @@ void HttpServerPropertiesImpl::SetBrokenAlternateProtocol(
 
   // If this is the only entry in the list, schedule an expiration task.
   // Otherwise it will be rescheduled automatically when the pending task runs.
-  if (broken_alternate_protocol_list_.size() == 1) {
+  if (broken_alternative_services_.size() == 1) {
     ScheduleBrokenAlternateProtocolMappingsExpiration();
   }
 }
@@ -345,7 +353,8 @@ bool HttpServerPropertiesImpl::WasAlternateProtocolRecentlyBroken(
     return false;
   const AlternativeService alternative_service(
       alternate_protocol.protocol, server.host(), alternate_protocol.port);
-  return ContainsKey(broken_alternate_protocol_map_, alternative_service);
+  return ContainsKey(recently_broken_alternative_services_,
+                     alternative_service);
 }
 
 void HttpServerPropertiesImpl::ConfirmAlternateProtocol(
@@ -355,7 +364,7 @@ void HttpServerPropertiesImpl::ConfirmAlternateProtocol(
     return;
   const AlternativeService alternative_service(
       alternate_protocol.protocol, server.host(), alternate_protocol.port);
-  broken_alternate_protocol_map_.erase(alternative_service);
+  recently_broken_alternative_services_.erase(alternative_service);
 }
 
 void HttpServerPropertiesImpl::ClearAlternateProtocol(
@@ -504,29 +513,28 @@ void HttpServerPropertiesImpl::RemoveCanonicalHost(
 
 void HttpServerPropertiesImpl::ExpireBrokenAlternateProtocolMappings() {
   base::TimeTicks now = base::TimeTicks::Now();
-  while (!broken_alternate_protocol_list_.empty()) {
-    BrokenAlternateProtocolEntryWithTime entry_with_time =
-        broken_alternate_protocol_list_.front();
-    if (now < entry_with_time.when) {
+  while (!broken_alternative_services_.empty()) {
+    BrokenAlternativeServices::iterator it =
+        broken_alternative_services_.begin();
+    if (now < it->second) {
       break;
     }
 
-    const AlternativeService& alternative_service =
-        entry_with_time.alternative_service;
+    const AlternativeService& alternative_service = it->first;
     ClearAlternateProtocol(
         HostPortPair(alternative_service.host, alternative_service.port));
-    broken_alternate_protocol_list_.pop_front();
+    broken_alternative_services_.erase(it);
   }
   ScheduleBrokenAlternateProtocolMappingsExpiration();
 }
 
 void
 HttpServerPropertiesImpl::ScheduleBrokenAlternateProtocolMappingsExpiration() {
-  if (broken_alternate_protocol_list_.empty()) {
+  if (broken_alternative_services_.empty()) {
     return;
   }
   base::TimeTicks now = base::TimeTicks::Now();
-  base::TimeTicks when = broken_alternate_protocol_list_.front().when;
+  base::TimeTicks when = broken_alternative_services_.front().second;
   base::TimeDelta delay = when > now ? when - now : base::TimeDelta();
   base::MessageLoop::current()->PostDelayedTask(
       FROM_HERE,