Use linked hash map for broken alternative service queue.

net/http/http_server_properties_impl.cc

 // Copyright (c) 2012 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 "net/http/http_server_properties_impl.h"
 
 #include "base/bind.h"
 #include "base/logging.h"
 #include "base/memory/scoped_ptr.h"
 #include "base/message_loop/message_loop.h"
@@ skipping 302 matching lines @@
       return;
     }
     // This server's alternate protocol information is coming from a canonical
     // server. Add an entry in the map for this server explicitly so that
     // it can be marked as broken.
     it = alternate_protocol_map_.Put(server, alternate);
   }
   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.
   RemoveCanonicalHost(server);
 
   // 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();
   }
 }
 
 bool HttpServerPropertiesImpl::WasAlternateProtocolRecentlyBroken(
     const HostPortPair& server) {
   const AlternateProtocolInfo alternate_protocol = GetAlternateProtocol(server);
   if (alternate_protocol.protocol == UNINITIALIZED_ALTERNATE_PROTOCOL)
     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(
     const HostPortPair& server) {
   const AlternateProtocolInfo alternate_protocol = GetAlternateProtocol(server);
   if (alternate_protocol.protocol == UNINITIALIZED_ALTERNATE_PROTOCOL)
     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(
     const HostPortPair& server) {
   AlternateProtocolMap::iterator it = alternate_protocol_map_.Peek(server);
   if (it != alternate_protocol_map_.end())
     alternate_protocol_map_.Erase(it);
 
   RemoveCanonicalHost(server);
 }
@@ skipping 128 matching lines @@
     return;
 
   if (!canonical->second.Equals(server))
     return;
 
   canonical_host_to_origin_map_.erase(canonical->first);
 }
 
 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,
       base::Bind(
           &HttpServerPropertiesImpl::ExpireBrokenAlternateProtocolMappings,
           weak_ptr_factory_.GetWeakPtr()),
       delay);
 }
 
 }  // namespace net