Optimize phishing page term feature extraction.

base/memory/mru_cache.h

 // Copyright (c) 2011 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.
 
 // This file contains a template for a Most Recently Used cache that allows
 // constant-time access to items using a key, but easy identification of the
 // least-recently-used items for removal.  Each key can only be associated with
 // one payload item at a time.
 //
 // The key object will be stored twice, so it should support efficient copying.
 //
 // NOTE: While all operations are O(1), this code is written for
 // legibility rather than optimality. If future profiling identifies this as
 // a bottleneck, there is room for smaller values of 1 in the O(1). :]
 
 #ifndef BASE_MEMORY_MRU_CACHE_H_
 #define BASE_MEMORY_MRU_CACHE_H_
 #pragma once
 
 #include <list>
 #include <map>
 #include <utility>
 
 #include "base/basictypes.h"
 #include "base/logging.h"
+#include "base/hash_tables.h"

[Brian Ryner, 2011/08/08 22:08:00]

Keep these in alphabetical order?

[Garrett Casto, 2011/08/08 23:19:51]

Done.

 
 namespace base {
 
 // MRUCacheBase ----------------------------------------------------------------
 
+// This template is used to standardize map type containers that can be used
+// by MRUCacheBase. This level of indirection is necessary because of the way
+// that template template params and default template params interact.
+template <class KeyType, class ValueType>
+struct MRUCacheStandardMap {
+  typedef std::map<KeyType, ValueType> Type;
+};
+
 // Base class for the MRU cache specializations defined below.
 // The deletor will get called on all payloads that are being removed or
 // replaced.
-template <class KeyType, class PayloadType, class DeletorType>
+template <class KeyType, class PayloadType, class DeletorType,
+          template <typename, typename> class MapType = MRUCacheStandardMap>
 class MRUCacheBase {
  public:
   // The payload of the list. This maintains a copy of the key so we can
   // efficiently delete things given an element of the list.
   typedef std::pair<KeyType, PayloadType> value_type;
 
  private:
   typedef std::list<value_type> PayloadList;
-  typedef std::map<KeyType, typename PayloadList::iterator> KeyIndex;
+  typedef typename MapType<KeyType,
+                           typename PayloadList::iterator>::Type KeyIndex;
 
  public:
   typedef typename PayloadList::size_type size_type;
 
   typedef typename PayloadList::iterator iterator;
   typedef typename PayloadList::const_iterator const_iterator;
   typedef typename PayloadList::reverse_iterator reverse_iterator;
   typedef typename PayloadList::const_reverse_iterator const_reverse_iterator;
 
   enum { NO_AUTO_EVICT = 0 };
@@ skipping 197 matching lines @@
   explicit OwningMRUCache(typename ParentType::size_type max_size)
       : ParentType(max_size) {
   }
   virtual ~OwningMRUCache() {
   }
 
  private:
   DISALLOW_COPY_AND_ASSIGN(OwningMRUCache);
 };
 
+// HashingMRUCache ------------------------------------------------------------
+
+template <class KeyType, class ValueType>
+struct MRUCacheHashMap {
+  typedef base::hash_map<KeyType, ValueType> Type;
+};
+
+// This class is similar to MRUCache, except that it uses base::hash_map as
+// the map type instead of std::map. Note that you your KeyType must be hashable

[Brian Ryner, 2011/08/08 22:08:00]

extra "you"

[Garrett Casto, 2011/08/08 23:19:51]

Done.

+// to use this cache.
+template <class KeyType, class PayloadType>
+class HashingMRUCache : public MRUCacheBase<KeyType,
+                                            PayloadType,
+                                            MRUCacheNullDeletor<PayloadType>,
+                                            MRUCacheHashMap> {
+ private:
+  typedef MRUCacheBase<KeyType, PayloadType,
+                       MRUCacheNullDeletor<PayloadType>,
+                       MRUCacheHashMap> ParentType;
+
+ public:
+  // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT.
+  explicit HashingMRUCache(typename ParentType::size_type max_size)
+      : ParentType(max_size) {
+  }
+  virtual ~HashingMRUCache() {
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HashingMRUCache);
+};
+
 }  // namespace base
 
 #endif  // BASE_MEMORY_MRU_CACHE_H_