New disk cache eviction algorithm.

net/disk_cache/backend_impl.h

Index: net/disk_cache/backend_impl.h
===================================================================
--- net/disk_cache/backend_impl.h	(revision 11078)
+++ net/disk_cache/backend_impl.h	(working copy)
@@ -4,8 +4,8 @@
 
 // See net/disk_cache/disk_cache.h for the public interface of the cache.
 
-#ifndef NET_DISK_CACHE_BACKEND_IMPL_H__
-#define NET_DISK_CACHE_BACKEND_IMPL_H__
+#ifndef NET_DISK_CACHE_BACKEND_IMPL_H_
+#define NET_DISK_CACHE_BACKEND_IMPL_H_
 
 #include "base/timer.h"
 #include "net/disk_cache/block_files.h"
@@ -24,11 +24,13 @@
  public:
   explicit BackendImpl(const std::wstring& path)
       : path_(path), block_files_(path), mask_(0), max_size_(0), init_(false),
-        restarted_(false), unit_test_(false), read_only_(false) {}
+        restarted_(false), unit_test_(false), read_only_(false),
+        new_eviction_(false) {}
   // mask can be used to limit the usable size of the hash table, for testing.
   BackendImpl(const std::wstring& path, uint32 mask)
       : path_(path), block_files_(path), mask_(mask), max_size_(0),
-        init_(false), restarted_(false), unit_test_(false), read_only_(false) {}
+        init_(false), restarted_(false), unit_test_(false), read_only_(false),
+        new_eviction_(false) {}
   ~BackendImpl();
 
   // Performs general initialization for this current instance of the cache.
@@ -77,9 +79,12 @@
   // method checks it and takes the appropriate action.
   void RecoveredEntry(CacheRankingsBlock* rankings);
 
-  // Permanently deletes an entry.
+  // Permanently deletes an entry, but still keeps track of it.
   void InternalDoomEntry(EntryImpl* entry);
 
+  // Removes all references to this entry.
+  void RemoveEntry(EntryImpl* entry);
+
   // This method must be called whenever an entry is released for the last time.
   void CacheEntryDestroyed();
 
@@ -144,12 +149,24 @@
   // Returns a given entry from the cache. The entry to match is determined by
   // key and hash, and the returned entry may be the matched one or it's parent
   // on the list of entries with the same hash (or bucket).
-  EntryImpl* MatchEntry(const std::string& key, uint32 hash,
-                         bool find_parent);
+  EntryImpl* MatchEntry(const std::string& key, uint32 hash, bool find_parent);
 
   // Opens the next or previous entry on a cache iteration.
   bool OpenFollowingEntry(bool forward, void** iter, Entry** next_entry);
 
+  // Opens the next or previous entry on a single list. If successfull,
+  // |from_entry| will be updated to point to the new entry, otherwise it will
+  // be set to NULL; in other words, it is used as an explicit iterator.
+  bool OpenFollowingEntryFromList(bool forward, Rankings::List list,
+                                  CacheRankingsBlock** from_entry,
+                                  EntryImpl** next_entry);
+
+  // Returns the entry that is pointed by |next|.
+  EntryImpl* GetEnumeratedEntry(CacheRankingsBlock* next);
+
+  // Re-opens an entry that was previously deleted.
+  bool ResurrectEntry(EntryImpl* deleted_entry, Entry** entry);
+
   void DestroyInvalidEntry(Addr address, EntryImpl* entry);
 
   // Handles the used storage count.
@@ -159,10 +176,15 @@
   // Update the number of referenced cache entries.
   void IncreaseNumRefs();
   void DecreaseNumRefs();
+  void IncreaseNumEntries();
+  void DecreaseNumEntries();
 
   // Dumps current cache statistics to the log.
   void LogStats();
 
+  // Upgrades the index file to version 2.1.
+  void UpgradeTo2_1();
+
   // Performs basic checks on the index file. Returns false on failure.
   bool CheckIndex();
 
@@ -181,13 +203,14 @@
   int32 max_size_;  // Maximum data size for this instance.
   Eviction eviction_;  // Handler of the eviction algorithm.
   int num_refs_;  // Number of referenced cache entries.
-  int max_refs_;  // Max number of eferenced cache entries.
+  int max_refs_;  // Max number of referenced cache entries.
   int num_pending_io_;  // Number of pending IO operations;
   bool init_;  // controls the initialization of the system.
   bool restarted_;
   bool unit_test_;
   bool read_only_;  // Prevents updates of the rankings data (used by tools).
   bool disabled_;
+  bool new_eviction_;  // What eviction algorithm should be used.
 
   Stats stats_;  // Usage statistcs.
   base::RepeatingTimer<BackendImpl> timer_;  // Usage timer.
@@ -198,5 +221,5 @@
 
 }  // namespace disk_cache
 
-#endif  // NET_DISK_CACHE_BACKEND_IMPL_H__
+#endif  // NET_DISK_CACHE_BACKEND_IMPL_H_