Enforce maximum number of entries in FtpAuthCache.

TEST=Covered by net_unittests.
BUG=none

Review URL: http://codereview.chromium.org/165167

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@23094 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 83 insertions, 27 deletions

diff --git a/net/ftp/ftp_auth_cache.cc b/net/ftp/ftp_auth_cache.cc
index 007f167..def516d 100644
--- a/net/ftp/ftp_auth_cache.cc
+++ b/net/ftp/ftp_auth_cache.cc
@@ -4,31 +4,51 @@
 
 #include "net/ftp/ftp_auth_cache.h"
 
-#include "base/string_util.h"
+#include "base/logging.h"
 #include "googleurl/src/gurl.h"
 
 namespace net {
 
+// static
+const size_t FtpAuthCache::kMaxEntries = 10;
+
 AuthData* FtpAuthCache::Lookup(const GURL& origin) {
-  AuthCacheMap::iterator iter = cache_.find(MakeKey(origin));
-  return (iter == cache_.end()) ? NULL : iter->second;
+  Entry* entry = LookupByOrigin(origin);
+  return (entry ? entry->auth_data : NULL);
 }
 
-void FtpAuthCache::Add(const GURL& origin, AuthData* value) {
-  cache_[MakeKey(origin)] = value;
-
-  // TODO(eroman): enforce a maximum number of entries.
+void FtpAuthCache::Add(const GURL& origin, AuthData* auth_data) {
+  DCHECK(origin.SchemeIs("ftp"));
+  DCHECK_EQ(origin.GetOrigin(), origin);
+
+  Entry* entry = LookupByOrigin(origin);
+  if (entry) {
+    entry->auth_data = auth_data;
+  } else {
+    entries_.push_front(Entry(origin, auth_data));
+
+    // Prevent unbound memory growth of the cache.
+    if (entries_.size() > kMaxEntries)
+      entries_.pop_back();
+  }
 }
 
 void FtpAuthCache::Remove(const GURL& origin) {
-  cache_.erase(MakeKey(origin));
+  for (EntryList::iterator it = entries_.begin(); it != entries_.end(); ++it) {
+    if (it->origin == origin) {
+      entries_.erase(it);
+      DCHECK(!LookupByOrigin(origin));
+      return;
+    }
+  }
 }
 
-// static
-FtpAuthCache::AuthCacheKey FtpAuthCache::MakeKey(const GURL& origin) {
-  DCHECK(origin.SchemeIs("ftp"));
-  DCHECK(origin.GetOrigin() == origin);
-  return origin.spec();
+FtpAuthCache::Entry* FtpAuthCache::LookupByOrigin(const GURL& origin) {
+  for (EntryList::iterator it = entries_.begin(); it != entries_.end(); ++it) {
+    if (it->origin == origin)
+      return &(*it);
+  }
+  return NULL;
 }
 
 }  // namespace net
diff --git a/net/ftp/ftp_auth_cache.h b/net/ftp/ftp_auth_cache.h
index 1286511..c63828d 100644
--- a/net/ftp/ftp_auth_cache.h
+++ b/net/ftp/ftp_auth_cache.h
@@ -5,12 +5,10 @@
 #ifndef NET_FTP_FTP_AUTH_CACHE_H_
 #define NET_FTP_FTP_AUTH_CACHE_H_
 
-#include <string>
-#include <map>
+#include <list>
 
 #include "net/base/auth.h"
-
-class GURL;
+#include "googleurl/src/gurl.h"
 
 namespace net {
 
@@ -27,6 +25,9 @@ class FtpAuthCache {
   FtpAuthCache() {}
   ~FtpAuthCache() {}
 
+  // Maximum number of entries we allow in the cache.
+  static const size_t kMaxEntries;
+
   // Check if we have authentication data for ftp server at |origin|.
   // Returns the address of corresponding AuthData object (if found) or NULL
   // (if not found).
@@ -34,22 +35,29 @@ class FtpAuthCache {
 
   // Add an entry for |origin| to the cache. If there is already an
   // entry for |origin|, it will be overwritten. Both parameters are IN only.
-  void Add(const GURL& origin, AuthData* value);
+  void Add(const GURL& origin, AuthData* auth_data);
 
   // Remove the entry for |origin| from the cache, if one exists.
   void Remove(const GURL& origin);
 
  private:
-  typedef std::string AuthCacheKey;
-  typedef scoped_refptr<AuthData> AuthCacheValue;
-  typedef std::map<AuthCacheKey, AuthCacheValue> AuthCacheMap;
+  struct Entry {
+    Entry(const GURL& origin, AuthData* auth_data)
+        : origin(origin),
+          auth_data(auth_data) {
+    }
+
+    const GURL origin;
+    scoped_refptr<AuthData> auth_data;
+  };
+  typedef std::list<Entry> EntryList;
 
-  // Get the key in hash table |cache_| where entries for ftp server |origin|
-  // should be saved.
-  static AuthCacheKey MakeKey(const GURL& origin);
+  // Return Entry corresponding to given |origin| or NULL if not found.
+  Entry* LookupByOrigin(const GURL& origin);
 
-  // internal representation of cache, an STL map.
-  AuthCacheMap cache_;
+  // Internal representation of cache, an STL list. This makes lookups O(n),
+  // but we expect n to be very low.
+  EntryList entries_;
 };
 
 }  // namespace net
diff --git a/net/ftp/ftp_auth_cache_unittest.cc b/net/ftp/ftp_auth_cache_unittest.cc
index 7f66a60..f74762b 100644
--- a/net/ftp/ftp_auth_cache_unittest.cc
+++ b/net/ftp/ftp_auth_cache_unittest.cc
@@ -2,8 +2,10 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "googleurl/src/gurl.h"
 #include "net/ftp/ftp_auth_cache.h"
+
+#include "base/string_util.h"
+#include "googleurl/src/gurl.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 using net::AuthData;
@@ -93,3 +95,29 @@ TEST(FtpAuthCacheTest, NormalizedKey) {
   cache.Remove(GURL("ftp://HOsT"));
   EXPECT_EQ(NULL, cache.Lookup(GURL("ftp://host")));
 }
+
+TEST(FtpAuthCacheTest, EvictOldEntries) {
+  FtpAuthCache cache;
+
+  scoped_refptr<AuthData> auth_data(new AuthData());
+
+  for (size_t i = 0; i < FtpAuthCache::kMaxEntries; i++)
+    cache.Add(GURL("ftp://host" + IntToString(i)), auth_data.get());
+
+  // No entries should be evicted before reaching the limit.
+  for (size_t i = 0; i < FtpAuthCache::kMaxEntries; i++) {
+    EXPECT_EQ(auth_data.get(),
+              cache.Lookup(GURL("ftp://host" + IntToString(i))));
+  }
+
+  // Adding one entry should cause eviction of the first entry.
+  cache.Add(GURL("ftp://last_host"), auth_data.get());
+  EXPECT_EQ(NULL, cache.Lookup(GURL("ftp://host0")));
+
+  // Remaining entries should not get evicted.
+  for (size_t i = 1; i < FtpAuthCache::kMaxEntries; i++) {
+    EXPECT_EQ(auth_data.get(),
+              cache.Lookup(GURL("ftp://host" + IntToString(i))));
+  }
+  EXPECT_EQ(auth_data.get(), cache.Lookup(GURL("ftp://last_host")));
+}