Implementation for memory only sparse caching

Implemented the following methods for memory only cache:
  ReadSparseData
  WriteSparseData
  GetAvailableRange

BUG=12258
Review URL: http://codereview.chromium.org/140049

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

1 files changed, 53 insertions, 13 deletions

diff --git a/net/disk_cache/mem_entry_impl.h b/net/disk_cache/mem_entry_impl.h
index c63f928..5f596bb 100644
--- a/net/disk_cache/mem_entry_impl.h
+++ b/net/disk_cache/mem_entry_impl.h
@@ -5,6 +5,8 @@
 #ifndef NET_DISK_CACHE_MEM_ENTRY_IMPL_H_
 #define NET_DISK_CACHE_MEM_ENTRY_IMPL_H_
 
+#include "base/hash_tables.h"
+#include "base/scoped_ptr.h"
 #include "net/disk_cache/disk_cache.h"
 #include "testing/gtest/include/gtest/gtest_prod.h"
 
@@ -15,17 +17,31 @@ class MemBackendImpl;
 // This class implements the Entry interface for the memory-only cache. An
 // object of this class represents a single entry on the cache. We use two
 // types of entries, parent and child to support sparse caching.
+//
 // A parent entry is non-sparse until a sparse method is invoked (i.e.
 // ReadSparseData, WriteSparseData, GetAvailableRange) when sparse information
 // is initialized. It then manages a list of child entries and delegates the
 // sparse API calls to the child entries. It creates and deletes child entries
 // and updates the list when needed.
+//
 // A child entry is used to carry partial cache content, non-sparse methods like
 // ReadData and WriteData cannot be applied to them. The lifetime of a child
 // entry is managed by the parent entry that created it except that the entry
 // can be evicted independently. A child entry does not have a key and it is not
 // registered in the backend's entry map. It is registered in the backend's
 // ranking list to enable eviction of a partial content.
+//
+// A sparse entry has a fixed maximum size and can be partially filled. There
+// can only be one continous filled region in a sparse entry, as illustrated by
+// the following example:
+// | xxx ooooo |
+// x = unfilled region
+// o = filled region
+// It is guranteed that there is at most one unfilled region and one filled
+// region, and the unfilled region (if there is one) is always before the filled
+// region. The book keeping for filled region in a sparse entry is done by using
+// the variable |child_first_pos_| (inclusive).
+
 class MemEntryImpl : public Entry {
  public:
   enum EntryType {
@@ -57,12 +73,6 @@ class MemEntryImpl : public Entry {
   // cache.
   bool CreateEntry(const std::string& key);
 
-  // Performs the initialization of a MemEntryImpl as a child entry.
-  // TODO(hclam): this method should be private. Leave this as public because
-  // this is the only way to create a child entry. Move this method to private
-  // once child entries are created by parent entry.
-  bool CreateChildEntry(MemEntryImpl* parent);
-
   // Permanently destroys this entry.
   void InternalDoom();
 
@@ -86,13 +96,15 @@ class MemEntryImpl : public Entry {
   }
 
   EntryType type() const {
-    return type_;
+    return parent_ ? kChildEntry : kParentEntry;
   }
 
  private:
-   enum {
-     NUM_STREAMS = 3
-   };
+  typedef base::hash_map<int, MemEntryImpl*> EntryMap;
+
+  enum {
+    NUM_STREAMS = 3
+  };
 
   ~MemEntryImpl();
 
@@ -102,19 +114,47 @@ class MemEntryImpl : public Entry {
   // Updates ranking information.
   void UpdateRank(bool modified);
 
+  // Initializes the children map and sparse info. This method is only called
+  // on a parent entry.
+  bool InitSparseInfo();
+
+  // Performs the initialization of a MemEntryImpl as a child entry.
+  // |parent| is the pointer to the parent entry. |child_id| is the ID of
+  // the new child.
+  bool InitChildEntry(MemEntryImpl* parent, int child_id);
+
+  // Returns an entry responsible for |offset|. The returned entry can be a
+  // child entry or this entry itself if |offset| points to the first range.
+  // If such entry does not exist and |create| is true, a new child entry is
+  // created.
+  MemEntryImpl* OpenChild(int64 offset, bool create);
+
+  // Finds the first child located within the range [|offset|, |offset + len|).
+  // Returns the number of bytes ahead of |offset| to reach the first available
+  // bytes in the entry. The first child found is output to |child|.
+  int FindNextChild(int64 offset, int len, MemEntryImpl** child);
+
+  // Removes child indexed by |child_id| from the children map.
+  void DetachChild(int child_id);
+
   std::string key_;
   std::vector<char> data_[NUM_STREAMS];  // User data.
   int32 data_size_[NUM_STREAMS];
   int ref_count_;
 
-  MemEntryImpl* next_;         // Pointers for the LRU list.
+  MemEntryImpl* next_;               // Pointers for the LRU list.
   MemEntryImpl* prev_;
-  MemEntryImpl* parent_;       // Pointer to the parent entry.
+  MemEntryImpl* parent_;             // Pointer to the parent entry.
+  scoped_ptr<EntryMap> children_;
+
+  int child_id_;               // The ID of a child entry.
+  int child_first_pos_;        // The position of the first byte in a child
+                               // entry.
+
   base::Time last_modified_;   // LRU information.
   base::Time last_used_;
   MemBackendImpl* backend_;    // Back pointer to the cache.
   bool doomed_;                // True if this entry was removed from the cache.
-  EntryType type_;             // The type of this entry.
 
   DISALLOW_EVIL_CONSTRUCTORS(MemEntryImpl);
 };