Use linked hash map for broken alternative service queue.

net/http/http_server_properties_impl.h

 // 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.
 
 #ifndef NET_HTTP_HTTP_SERVER_PROPERTIES_IMPL_H_
 #define NET_HTTP_HTTP_SERVER_PROPERTIES_IMPL_H_
 
 #include <deque>
 #include <map>
 #include <set>
 #include <string>
 #include <vector>
 
 #include "base/basictypes.h"
 #include "base/containers/hash_tables.h"
 #include "base/gtest_prod_util.h"
 #include "base/threading/non_thread_safe.h"
 #include "base/values.h"
 #include "net/base/host_port_pair.h"
+#include "net/base/linked_hash_map.h"
 #include "net/base/net_export.h"
 #include "net/http/http_server_properties.h"
 
 namespace base {
 class ListValue;
 }
 
+namespace BASE_HASH_NAMESPACE {
+
+template <>
+struct hash<net::AlternativeService> {
+  size_t operator()(const net::AlternativeService& entry) const {
+    return entry.protocol ^ hash<std::string>()(entry.host) ^ entry.port;
+  }
+};
+
+}  // namespace BASE_HASH_NAMESPACE
+
 namespace net {
 
 // The implementation for setting/retrieving the HTTP server properties.
 class NET_EXPORT HttpServerPropertiesImpl
     : public HttpServerProperties,
       NON_EXPORTED_BASE(public base::NonThreadSafe) {
  public:
   HttpServerPropertiesImpl();
   ~HttpServerPropertiesImpl() override;
 
@@ skipping 73 matching lines @@
   const ServerNetworkStatsMap& server_network_stats_map() const override;
 
  private:
   // |spdy_servers_map_| has flattened representation of servers (host, port)
   // that either support or not support SPDY protocol.
   typedef base::MRUCache<std::string, bool> SpdyServerHostPortMap;
   typedef std::map<HostPortPair, HostPortPair> CanonicalHostMap;
   typedef std::vector<std::string> CanonicalSufficList;
   typedef std::set<HostPortPair> Http11ServerHostPortSet;
 
-  // Broken alternative service with expiration time.
-  struct BrokenAlternateProtocolEntryWithTime {
-    BrokenAlternateProtocolEntryWithTime(
-        const AlternativeService& alternative_service,
-        base::TimeTicks when)
-        : alternative_service(alternative_service), when(when) {}
-
-    AlternativeService alternative_service;
-    base::TimeTicks when;
-  };
-  // Deque of BrokenAlternateProtocolEntryWithTime items, ordered by expiration
-  // time.
-  typedef std::deque<BrokenAlternateProtocolEntryWithTime>
-      BrokenAlternateProtocolList;
-  // Map from (server, alternate protocol and port) to the number of
-  // times that alternate protocol has been marked broken for that server.
-  typedef std::map<AlternativeService, int> BrokenAlternateProtocolMap;
+  // Linked hash map from AlternativeService to expiration time.  This container
+  // is a queue with O(1) enqueue and dequeue, and a hash_map with O(1) lookup
+  // at the same time.
+  typedef linked_hash_map<AlternativeService, base::TimeTicks>
+      BrokenAlternativeServices;
+  // Map to the number of times each alternative service has been marked broken.
+  typedef std::map<AlternativeService, int> RecentlyBrokenAlternativeServices;
 
   // Return the iterator for |server|, or for its canonical host, or end.
   AlternateProtocolMap::const_iterator GetAlternateProtocolIterator(
       const HostPortPair& server);
 
   // Return the canonical host for |server|, or end if none exists.
   CanonicalHostMap::const_iterator GetCanonicalHost(HostPortPair server) const;
 
   void RemoveCanonicalHost(const HostPortPair& server);
   void ExpireBrokenAlternateProtocolMappings();
   void ScheduleBrokenAlternateProtocolMappingsExpiration();
 
   SpdyServerHostPortMap spdy_servers_map_;
   Http11ServerHostPortSet http11_servers_;
 
   AlternateProtocolMap alternate_protocol_map_;
-  BrokenAlternateProtocolList broken_alternate_protocol_list_;
-  BrokenAlternateProtocolMap broken_alternate_protocol_map_;
+  BrokenAlternativeServices broken_alternative_services_;
+  // Class invariant:  Every alternative service in broken_alternative_services_
+  // must also be in recently_broken_alternative_services_.
+  RecentlyBrokenAlternativeServices recently_broken_alternative_services_;
 
   IPAddressNumber last_quic_address_;
   SpdySettingsMap spdy_settings_map_;
   ServerNetworkStatsMap server_network_stats_map_;
   // Contains a map of servers which could share the same alternate protocol.
   // Map from a Canonical host/port (host is some postfix of host names) to an
   // actual origin, which has a plausible alternate protocol mapping.
   CanonicalHostMap canonical_host_to_origin_map_;
   // Contains list of suffixes (for exmaple ".c.youtube.com",
   // ".googlevideo.com", ".googleusercontent.com") of canonical hostnames.
   CanonicalSufficList canonical_suffixes_;
 
   double alternate_protocol_probability_threshold_;
 
   base::WeakPtrFactory<HttpServerPropertiesImpl> weak_ptr_factory_;
 
   DISALLOW_COPY_AND_ASSIGN(HttpServerPropertiesImpl);
 };
 
 }  // namespace net
 
 #endif  // NET_HTTP_HTTP_SERVER_PROPERTIES_IMPL_H_