Disk cache: remove the hard coded list from rankings.cc

The rankings module now works with any list, not just
the first one. This is part of the support needed for
new eviction algorithms.

note: Rankings::CheckList() is basically the code that
was implementing the old Rankings::SelfCheck() (moved
with this cl).

The disk cache behavior is not changing with this cl.

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

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

6 files changed, 204 insertions, 143 deletions

diff --git a/net/disk_cache/addr.h b/net/disk_cache/addr.h
index 3a1cc33..375b2c5 100644
--- a/net/disk_cache/addr.h
+++ b/net/disk_cache/addr.h
@@ -50,6 +50,7 @@ const int kFirstAdditionlBlockFile = 4;
 //   0000 0000 0000 0000 1111 1111 1111 1111 : block#  0 - 65,535 (2^16)
 class Addr {
  public:
+  Addr() : value_(0) {}
   explicit Addr(CacheAddr address) : value_(address) {}
   Addr(FileType file_type, int max_blocks, int block_file, int index) {
     value_ = ((file_type << kFileTypeOffset) & kFileTypeMask) |
diff --git a/net/disk_cache/backend_impl.cc b/net/disk_cache/backend_impl.cc
index c9a2315..23b0f9dc 100644
--- a/net/disk_cache/backend_impl.cc
+++ b/net/disk_cache/backend_impl.cc
@@ -355,7 +355,7 @@ bool BackendImpl::CreateEntry(const std::string& key, Entry** entry) {
 
   data_->header.num_entries++;
   DCHECK(data_->header.num_entries > 0);
-  rankings_.Insert(cache_entry->rankings(), true);
+  rankings_.Insert(cache_entry->rankings(), true, Rankings::NO_USE);
   if (!parent.get())
     data_->table[hash & mask_] = entry_address.value();
 
@@ -573,9 +573,10 @@ LruData* BackendImpl::GetLruData() {
   return &data_->header.lru;
 }
 
-void BackendImpl::UpdateRank(CacheRankingsBlock* node, bool modified) {
-  if (!read_only_)
-    rankings_.UpdateRank(node, modified);
+void BackendImpl::UpdateRank(EntryImpl* entry, bool modified) {
+  if (!read_only_) {
+    rankings_.UpdateRank(entry->rankings(), modified, Rankings::NO_USE);
+  }
 }
 
 void BackendImpl::RecoveredEntry(CacheRankingsBlock* rankings) {
@@ -603,7 +604,7 @@ void BackendImpl::InternalDoomEntry(EntryImpl* entry) {
 
   Trace("Doom entry 0x%p", entry);
 
-  rankings_.Remove(entry->rankings());
+  rankings_.Remove(entry->rankings(), Rankings::NO_USE);
 
   entry->InternalDoom();
 
@@ -971,8 +972,9 @@ bool BackendImpl::OpenFollowingEntry(bool forward, void** iter,
 
   Rankings::ScopedRankingsBlock rankings(&rankings_,
       reinterpret_cast<CacheRankingsBlock*>(*iter));
-  CacheRankingsBlock* next_block = forward ? rankings_.GetNext(rankings.get()) :
-                                             rankings_.GetPrev(rankings.get());
+  CacheRankingsBlock* next_block = forward ?
+      rankings_.GetNext(rankings.get(), Rankings::NO_USE) :
+      rankings_.GetPrev(rankings.get(), Rankings::NO_USE);
   Rankings::ScopedRankingsBlock next(&rankings_, next_block);
   *next_entry = NULL;
   *iter = NULL;
@@ -1018,7 +1020,7 @@ void BackendImpl::DestroyInvalidEntry(Addr address, EntryImpl* entry) {
   LOG(WARNING) << "Destroying invalid entry.";
   Trace("Destroying invalid entry 0x%p", entry);
 
-  rankings_.Remove(entry->rankings());
+  rankings_.Remove(entry->rankings(), Rankings::NO_USE);
   entry->SetPointerForInvalidEntry(GetCurrentEntryId());
 
   entry->InternalDoom();
@@ -1035,13 +1037,14 @@ void BackendImpl::TrimCache(bool empty) {
 
   Time start = Time::Now();
   Rankings::ScopedRankingsBlock node(&rankings_);
-  Rankings::ScopedRankingsBlock next(&rankings_, rankings_.GetPrev(node.get()));
+  Rankings::ScopedRankingsBlock next(&rankings_,
+      rankings_.GetPrev(node.get(), Rankings::NO_USE));
   DCHECK(next.get());
   int target_size = empty ? 0 : LowWaterAdjust(max_size_);
   int deleted = 0;
   while (data_->header.num_bytes > target_size && next.get()) {
     node.reset(next.release());
-    next.reset(rankings_.GetPrev(node.get()));
+    next.reset(rankings_.GetPrev(node.get(), Rankings::NO_USE));
     if (!node->Data()->pointer || empty) {
       // This entry is not being used by anybody.
       EntryImpl* entry;
diff --git a/net/disk_cache/backend_impl.h b/net/disk_cache/backend_impl.h
index 9373e90..4725fe3 100644
--- a/net/disk_cache/backend_impl.h
+++ b/net/disk_cache/backend_impl.h
@@ -72,7 +72,7 @@ class BackendImpl : public Backend {
   LruData* GetLruData();
 
   // Updates the ranking information for an entry.
-  void UpdateRank(CacheRankingsBlock* node, bool modified);
+  void UpdateRank(EntryImpl* entry, bool modified);
 
   // A node was recovered from a crash, it may not be on the index, so this
   // method checks it and takes the appropriate action.
diff --git a/net/disk_cache/entry_impl.cc b/net/disk_cache/entry_impl.cc
index cc2b07d..0f6d426 100644
--- a/net/disk_cache/entry_impl.cc
+++ b/net/disk_cache/entry_impl.cc
@@ -562,7 +562,7 @@ void EntryImpl::DeleteData(Addr address, int index) {
 void EntryImpl::UpdateRank(bool modified) {
   if (!doomed_) {
     // Everything is handled by the backend.
-    backend_->UpdateRank(&node_, true);
+    backend_->UpdateRank(this, true);
     return;
   }
 
diff --git a/net/disk_cache/rankings.cc b/net/disk_cache/rankings.cc
index b690c75..286998e 100644
--- a/net/disk_cache/rankings.cc
+++ b/net/disk_cache/rankings.cc
@@ -16,14 +16,6 @@ disk_cache::RankCrashes g_rankings_crash = disk_cache::NO_CRASH;
 
 namespace {
 
-enum Lists {
-  NO_USE = 0,   // List of entries that have not been reused.
-  LOW_USE,      // List of entries with low reuse.
-  HIGH_USE,     // List of entries with high reuse.
-  DELETED,      // List of recently deleted or doomed entries.
-  LAST_ELEMENT
-};
-
 enum Operation {
   INSERT = 1,
   REMOVE
@@ -170,8 +162,8 @@ bool Rankings::Init(BackendImpl* backend) {
 
   control_data_ = backend_->GetLruData();
 
-  head_ = ReadHead();
-  tail_ = ReadTail();
+  ReadHeads();
+  ReadTails();
 
   if (control_data_->transaction)
     CompleteTransaction();
@@ -182,8 +174,10 @@ bool Rankings::Init(BackendImpl* backend) {
 
 void Rankings::Reset() {
   init_ = false;
-  head_.set_value(0);
-  tail_.set_value(0);
+  for (int i = 0; i < LAST_ELEMENT; i++) {
+    heads_[i].set_value(0);
+    tails_[i].set_value(0);
+  }
   control_data_ = NULL;
 }
 
@@ -223,16 +217,18 @@ bool Rankings::GetRanking(CacheRankingsBlock* rankings) {
   return true;
 }
 
-void Rankings::Insert(CacheRankingsBlock* node, bool modified) {
+void Rankings::Insert(CacheRankingsBlock* node, bool modified, List list) {
   Trace("Insert 0x%x", node->address().value());
   DCHECK(node->HasData());
-  Transaction lock(control_data_, node->address(), INSERT, NO_USE);
-  CacheRankingsBlock head(backend_->File(head_), head_);
-  if (head_.is_initialized()) {
+  Addr& my_head = heads_[list];
+  Addr& my_tail = tails_[list];
+  Transaction lock(control_data_, node->address(), INSERT, list);
+  CacheRankingsBlock head(backend_->File(my_head), my_head);
+  if (my_head.is_initialized()) {
     if (!GetRanking(&head))
       return;
 
-    if (head.Data()->prev != head_.value() &&  // Normal path.
+    if (head.Data()->prev != my_head.value() &&  // Normal path.
         head.Data()->prev != node->address().value()) {  // FinishInsert().
       backend_->CriticalError(ERR_INVALID_LINKS);
       return;
@@ -244,14 +240,14 @@ void Rankings::Insert(CacheRankingsBlock* node, bool modified) {
     UpdateIterators(&head);
   }
 
-  node->Data()->next = head_.value();
+  node->Data()->next = my_head.value();
   node->Data()->prev = node->address().value();
-  head_.set_value(node->address().value());
+  my_head.set_value(node->address().value());
 
-  if (!tail_.is_initialized() || tail_.value() == node->address().value()) {
-    tail_.set_value(node->address().value());
-    node->Data()->next = tail_.value();
-    WriteTail();
+  if (!my_tail.is_initialized() || my_tail.value() == node->address().value()) {
+    my_tail.set_value(node->address().value());
+    node->Data()->next = my_tail.value();
+    WriteTail(list);
     GenerateCrash(ON_INSERT_2);
   }
 
@@ -263,7 +259,7 @@ void Rankings::Insert(CacheRankingsBlock* node, bool modified) {
   GenerateCrash(ON_INSERT_3);
 
   // The last thing to do is move our head to point to a node already stored.
-  WriteHead();
+  WriteHead(list);
   GenerateCrash(ON_INSERT_4);
 }
 
@@ -293,7 +289,7 @@ void Rankings::Insert(CacheRankingsBlock* node, bool modified) {
 //    2. a(x, r), r(a, r), head(x), tail(a)           WriteTail()
 //    3. a(x, a), r(a, r), head(x), tail(a)           prev.Store()
 //    4. a(x, a), r(0, 0), head(x), tail(a)           next.Store()
-void Rankings::Remove(CacheRankingsBlock* node) {
+void Rankings::Remove(CacheRankingsBlock* node, List list) {
   Trace("Remove 0x%x (0x%x 0x%x)", node->address().value(), node->Data()->next,
         node->Data()->prev);
   DCHECK(node->HasData());
@@ -310,35 +306,37 @@ void Rankings::Remove(CacheRankingsBlock* node) {
   if (!GetRanking(&next) || !GetRanking(&prev))
     return;
 
-  if (!CheckLinks(node, &prev, &next))
+  if (!CheckLinks(node, &prev, &next, list))
     return;
 
-  Transaction lock(control_data_, node->address(), REMOVE, NO_USE);
+  Transaction lock(control_data_, node->address(), REMOVE, list);
   prev.Data()->next = next.address().value();
   next.Data()->prev = prev.address().value();
   GenerateCrash(ON_REMOVE_1);
 
   CacheAddr node_value = node->address().value();
-  if (node_value == head_.value() || node_value == tail_.value()) {
-    if (head_.value() == tail_.value()) {
-      head_.set_value(0);
-      tail_.set_value(0);
-
-      WriteHead();
+  Addr& my_head = heads_[list];
+  Addr& my_tail = tails_[list];
+  if (node_value == my_head.value() || node_value == my_tail.value()) {
+    if (my_head.value() == my_tail.value()) {
+      my_head.set_value(0);
+      my_tail.set_value(0);
+
+      WriteHead(list);
       GenerateCrash(ON_REMOVE_2);
-      WriteTail();
+      WriteTail(list);
       GenerateCrash(ON_REMOVE_3);
-    } else if (node_value == head_.value()) {
-      head_.set_value(next.address().value());
+    } else if (node_value == my_head.value()) {
+      my_head.set_value(next.address().value());
       next.Data()->prev = next.address().value();
 
-      WriteHead();
+      WriteHead(list);
       GenerateCrash(ON_REMOVE_4);
-    } else if (node_value == tail_.value()) {
-      tail_.set_value(prev.address().value());
+    } else if (node_value == my_tail.value()) {
+      my_tail.set_value(prev.address().value());
       prev.Data()->next = prev.address().value();
 
-      WriteTail();
+      WriteTail(list);
       GenerateCrash(ON_REMOVE_5);
 
       // Store the new tail to make sure we can undo the operation if we crash.
@@ -366,10 +364,10 @@ void Rankings::Remove(CacheRankingsBlock* node) {
 // list. We want to avoid that case as much as we can (as while waiting for IO),
 // but the net effect is just an assert on debug when attempting to remove the
 // entry. Otherwise we'll need reentrant transactions, which is an overkill.
-void Rankings::UpdateRank(CacheRankingsBlock* node, bool modified) {
+void Rankings::UpdateRank(CacheRankingsBlock* node, bool modified, List list) {
   Time start = Time::Now();
-  Remove(node);
-  Insert(node, modified);
+  Remove(node, list);
+  Insert(node, modified, list);
   UMA_HISTOGRAM_TIMES(L"DiskCache.UpdateRank", Time::Now() - start);
 }
 
@@ -390,14 +388,17 @@ void Rankings::CompleteTransaction() {
   node.Data()->pointer = NULL;
   node.Store();
 
+  Addr& my_head = heads_[control_data_->operation_list];
+  Addr& my_tail = tails_[control_data_->operation_list];
+
   // We want to leave the node inside the list. The entry must me marked as
   // dirty, and will be removed later. Otherwise, we'll get assertions when
   // attempting to remove the dirty entry.
   if (INSERT == control_data_->operation) {
-    Trace("FinishInsert h:0x%x t:0x%x", head_.value(), tail_.value());
+    Trace("FinishInsert h:0x%x t:0x%x", my_head.value(), my_tail.value());
     FinishInsert(&node);
   } else if (REMOVE == control_data_->operation) {
-    Trace("RevertRemove h:0x%x t:0x%x", head_.value(), tail_.value());
+    Trace("RevertRemove h:0x%x t:0x%x", my_head.value(), my_tail.value());
     RevertRemove(&node);
   } else {
     NOTREACHED();
@@ -408,13 +409,15 @@ void Rankings::CompleteTransaction() {
 void Rankings::FinishInsert(CacheRankingsBlock* node) {
   control_data_->transaction = 0;
   control_data_->operation = 0;
-  if (head_.value() != node->address().value()) {
-    if (tail_.value() == node->address().value()) {
+  Addr& my_head = heads_[control_data_->operation_list];
+  Addr& my_tail = tails_[control_data_->operation_list];
+  if (my_head.value() != node->address().value()) {
+    if (my_tail.value() == node->address().value()) {
       // This part will be skipped by the logic of Insert.
-      node->Data()->next = tail_.value();
+      node->Data()->next = my_tail.value();
     }
 
-    Insert(node, true);
+    Insert(node, true, static_cast<List>(control_data_->operation_list));
   }
 
   // Tell the backend about this entry.
@@ -454,19 +457,22 @@ void Rankings::RevertRemove(CacheRankingsBlock* node) {
   if (node_value != next_addr.value())
     next.Data()->prev = node_value;
 
-  if (!head_.is_initialized() || !tail_.is_initialized()) {
-    head_.set_value(node_value);
-    tail_.set_value(node_value);
-    WriteHead();
-    WriteTail();
-  } else if (head_.value() == next.address().value()) {
-    head_.set_value(node_value);
+  List my_list = static_cast<List>(control_data_->operation_list);
+  Addr& my_head = heads_[my_list];
+  Addr& my_tail = tails_[my_list];
+  if (!my_head.is_initialized() || !my_tail.is_initialized()) {
+    my_head.set_value(node_value);
+    my_tail.set_value(node_value);
+    WriteHead(my_list);
+    WriteTail(my_list);
+  } else if (my_head.value() == next.address().value()) {
+    my_head.set_value(node_value);
     prev.Data()->next = next.address().value();
-    WriteHead();
-  } else if (tail_.value() == prev.address().value()) {
-    tail_.set_value(node_value);
+    WriteHead(my_list);
+  } else if (my_tail.value() == prev.address().value()) {
+    my_tail.set_value(node_value);
     next.Data()->prev = prev.address().value();
-    WriteTail();
+    WriteTail(my_list);
   }
 
   next.Store();
@@ -475,16 +481,18 @@ void Rankings::RevertRemove(CacheRankingsBlock* node) {
   control_data_->operation = 0;
 }
 
-CacheRankingsBlock* Rankings::GetNext(CacheRankingsBlock* node) {
+CacheRankingsBlock* Rankings::GetNext(CacheRankingsBlock* node, List list) {
   ScopedRankingsBlock next(this);
   if (!node) {
-    if (!head_.is_initialized())
+    Addr& my_head = heads_[list];
+    if (!my_head.is_initialized())
       return NULL;
-    next.reset(new CacheRankingsBlock(backend_->File(head_), head_));
+    next.reset(new CacheRankingsBlock(backend_->File(my_head), my_head));
   } else {
-    if (!tail_.is_initialized())
+    Addr& my_tail = tails_[list];
+    if (!my_tail.is_initialized())
       return NULL;
-    if (tail_.value() == node->address().value())
+    if (my_tail.value() == node->address().value())
       return NULL;
     Addr address(node->Data()->next);
     next.reset(new CacheRankingsBlock(backend_->File(address), address));
@@ -501,16 +509,18 @@ CacheRankingsBlock* Rankings::GetNext(CacheRankingsBlock* node) {
   return next.release();
 }
 
-CacheRankingsBlock* Rankings::GetPrev(CacheRankingsBlock* node) {
+CacheRankingsBlock* Rankings::GetPrev(CacheRankingsBlock* node, List list) {
   ScopedRankingsBlock prev(this);
   if (!node) {
-    if (!tail_.is_initialized())
+    Addr& my_tail = tails_[list];
+    if (!my_tail.is_initialized())
       return NULL;
-    prev.reset(new CacheRankingsBlock(backend_->File(tail_), tail_));
+    prev.reset(new CacheRankingsBlock(backend_->File(my_tail), my_tail));
   } else {
-    if (!head_.is_initialized())
+    Addr& my_head = heads_[list];
+    if (!my_head.is_initialized())
       return NULL;
-    if (head_.value() == node->address().value())
+    if (my_head.value() == node->address().value())
       return NULL;
     Addr address(node->Data()->prev);
     prev.reset(new CacheRankingsBlock(backend_->File(address), address));
@@ -532,40 +542,14 @@ void Rankings::FreeRankingsBlock(CacheRankingsBlock* node) {
 }
 
 int Rankings::SelfCheck() {
-  if (!head_.is_initialized()) {
-    if (!tail_.is_initialized())
-      return 0;
-    return ERR_INVALID_TAIL;
+  int total = 0;
+  for (int i = 0; i < LAST_ELEMENT; i++) {
+    int partial = CheckList(static_cast<List>(i));
+    if (partial < 0)
+      return partial;
+    total += partial;
   }
-  if (!tail_.is_initialized())
-    return ERR_INVALID_HEAD;
-
-  if (tail_.is_separate_file())
-    return ERR_INVALID_TAIL;
-
-  if (head_.is_separate_file())
-    return ERR_INVALID_HEAD;
-
-  int num_items = 0;
-  Addr address(head_.value());
-  Addr prev(head_.value());
-  scoped_ptr<CacheRankingsBlock> node;
-  do {
-    node.reset(new CacheRankingsBlock(backend_->File(address), address));
-    node->Load();
-    if (node->Data()->prev != prev.value())
-      return ERR_INVALID_PREV;
-    if (!CheckEntry(node.get()))
-      return ERR_INVALID_ENTRY;
-
-    prev.set_value(address.value());
-    address.set_value(node->Data()->next);
-    if (!address.is_initialized() || address.is_separate_file())
-      return ERR_INVALID_NEXT;
-
-    num_items++;
-  } while (node->address().value() != address.value());
-  return num_items;
+  return total;
 }
 
 bool Rankings::SanityCheck(CacheRankingsBlock* node, bool from_list) {
@@ -584,29 +568,31 @@ bool Rankings::SanityCheck(CacheRankingsBlock* node, bool from_list) {
   if (!data->next && !data->prev && from_list)
     return false;
 
-  if ((node->address().value() == data->prev) && (head_.value() != data->prev))
+  if ((node->address().value() == data->prev) && !IsHead(data->prev))
     return false;
 
-  if ((node->address().value() == data->next) && (tail_.value() != data->next))
+  if ((node->address().value() == data->next) && !IsTail(data->next))
     return false;
 
   return true;
 }
 
-Addr Rankings::ReadHead() {
-  return Addr(control_data_->heads[NO_USE]);
+void Rankings::ReadHeads() {
+  for (int i = 0; i < LAST_ELEMENT; i++)
+    heads_[i] = Addr(control_data_->heads[i]);
 }
 
-Addr Rankings::ReadTail() {
-  return Addr(control_data_->tails[NO_USE]);
+void Rankings::ReadTails() {
+  for (int i = 0; i < LAST_ELEMENT; i++)
+    tails_[i] = Addr(control_data_->tails[i]);
 }
 
-void Rankings::WriteHead() {
-  control_data_->heads[NO_USE] = head_.value();
+void Rankings::WriteHead(List list) {
+  control_data_->heads[list] = heads_[list].value();
 }
 
-void Rankings::WriteTail() {
-  control_data_->tails[NO_USE] = tail_.value();
+void Rankings::WriteTail(List list) {
+  control_data_->tails[list] = tails_[list].value();
 }
 
 bool Rankings::CheckEntry(CacheRankingsBlock* rankings) {
@@ -618,11 +604,11 @@ bool Rankings::CheckEntry(CacheRankingsBlock* rankings) {
 }
 
 bool Rankings::CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev,
-                          CacheRankingsBlock* next) {
+                          CacheRankingsBlock* next, List list) {
   if ((prev->Data()->next != node->address().value() &&
-       head_.value() != node->address().value()) ||
+       heads_[list].value() != node->address().value()) ||
       (next->Data()->prev != node->address().value() &&
-       tail_.value() != node->address().value())) {
+       tails_[list].value() != node->address().value())) {
     LOG(ERROR) << "Inconsistent LRU.";
 
     if (prev->Data()->next == next->address().value() &&
@@ -653,6 +639,61 @@ bool Rankings::CheckSingleLink(CacheRankingsBlock* prev,
   return true;
 }
 
+int Rankings::CheckList(List list) {
+  Addr& my_head = heads_[list];
+  Addr& my_tail = tails_[list];
+  if (!my_head.is_initialized()) {
+    if (!my_tail.is_initialized())
+      return 0;
+    // If there is no head, having a tail is an error.
+    return ERR_INVALID_TAIL;
+  }
+  // If there is no tail, having a head is an error.
+  if (!my_tail.is_initialized())
+    return ERR_INVALID_HEAD;
+
+  if (my_tail.is_separate_file())
+    return ERR_INVALID_TAIL;
+
+  if (my_head.is_separate_file())
+    return ERR_INVALID_HEAD;
+
+  int num_items = 0;
+  Addr address(my_head.value());
+  Addr prev(my_head.value());
+  scoped_ptr<CacheRankingsBlock> node;
+  do {
+    node.reset(new CacheRankingsBlock(backend_->File(address), address));
+    node->Load();
+    if (node->Data()->prev != prev.value())
+      return ERR_INVALID_PREV;
+    if (!CheckEntry(node.get()))
+      return ERR_INVALID_ENTRY;
+
+    prev.set_value(address.value());
+    address.set_value(node->Data()->next);
+    if (!address.is_initialized() || address.is_separate_file())
+      return ERR_INVALID_NEXT;
+
+    num_items++;
+  } while (node->address().value() != address.value());
+  return num_items;
+}
+
+bool Rankings::IsHead(CacheAddr addr) {
+  for (int i = 0; i < LAST_ELEMENT; i++)
+    if (addr == heads_[i].value())
+      return true;
+  return false;
+}
+
+bool Rankings::IsTail(CacheAddr addr) {
+  for (int i = 0; i < LAST_ELEMENT; i++)
+    if (addr == tails_[i].value())
+      return true;
+  return false;
+}
+
 void Rankings::TrackRankingsBlock(CacheRankingsBlock* node,
                                   bool start_tracking) {
   if (!node)
diff --git a/net/disk_cache/rankings.h b/net/disk_cache/rankings.h
index 4347fa2..1434235 100644
--- a/net/disk_cache/rankings.h
+++ b/net/disk_cache/rankings.h
@@ -48,6 +48,15 @@ enum RankCrashes {
 // This class handles the ranking information for the cache.
 class Rankings {
  public:
+  // Possible lists of entries.
+  enum List {
+    NO_USE = 0,   // List of entries that have not been reused.
+    LOW_USE,      // List of entries with low reuse.
+    HIGH_USE,     // List of entries with high reuse.
+    DELETED,      // List of recently deleted or doomed entries.
+    LAST_ELEMENT
+  };
+
   // This class provides a specialized version of scoped_ptr, that calls
   // Rankings whenever a CacheRankingsBlock is deleted, to keep track of cache
   // iterators that may go stale.
@@ -73,8 +82,7 @@ class Rankings {
     DISALLOW_EVIL_CONSTRUCTORS(ScopedRankingsBlock);
   };
 
-  Rankings()
-      : init_(false), head_(0), tail_(0) {}
+  Rankings() : init_(false) {}
   ~Rankings() {}
 
   bool Init(BackendImpl* backend);
@@ -83,20 +91,20 @@ class Rankings {
   void Reset();
 
   // Inserts a given entry at the head of the queue.
-  void Insert(CacheRankingsBlock* node, bool modified);
+  void Insert(CacheRankingsBlock* node, bool modified, List list);
 
   // Removes a given entry from the LRU list.
-  void Remove(CacheRankingsBlock* node);
+  void Remove(CacheRankingsBlock* node, List list);
 
   // Moves a given entry to the head.
-  void UpdateRank(CacheRankingsBlock* node, bool modified);
+  void UpdateRank(CacheRankingsBlock* node, bool modified, List list);
 
   // Iterates through the list.
-  CacheRankingsBlock* GetNext(CacheRankingsBlock* node);
-  CacheRankingsBlock* GetPrev(CacheRankingsBlock* node);
+  CacheRankingsBlock* GetNext(CacheRankingsBlock* node, List list);
+  CacheRankingsBlock* GetPrev(CacheRankingsBlock* node, List list);
   void FreeRankingsBlock(CacheRankingsBlock* node);
 
-  // Peforms a simple self-check of the list, and returns the number of items
+  // Peforms a simple self-check of the lists, and returns the number of items
   // or an error code (negative value).
   int SelfCheck();
 
@@ -108,10 +116,10 @@ class Rankings {
   typedef std::pair<CacheAddr, CacheRankingsBlock*> IteratorPair;
   typedef std::list<IteratorPair> IteratorList;
 
-  Addr ReadHead();
-  Addr ReadTail();
-  void WriteHead();
-  void WriteTail();
+  void ReadHeads();
+  void ReadTails();
+  void WriteHead(List list);
+  void WriteTail(List list);
 
   // Gets the rankings information for a given rankings node.
   bool GetRanking(CacheRankingsBlock* rankings);
@@ -127,11 +135,19 @@ class Rankings {
 
   // Returns false if node is not properly linked.
   bool CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev,
-                  CacheRankingsBlock* next);
+                  CacheRankingsBlock* next, List list);
 
   // Checks the links between two consecutive nodes.
   bool CheckSingleLink(CacheRankingsBlock* prev, CacheRankingsBlock* next);
 
+  // Peforms a simple check of the list, and returns the number of items or an
+  // error code (negative value).
+  int CheckList(List list);
+
+  // Returns true if addr is the head or tail of any list.
+  bool IsHead(CacheAddr addr);
+  bool IsTail(CacheAddr addr);
+
   // Controls tracking of nodes used for enumerations.
   void TrackRankingsBlock(CacheRankingsBlock* node, bool start_tracking);
 
@@ -139,8 +155,8 @@ class Rankings {
   void UpdateIterators(CacheRankingsBlock* node);
 
   bool init_;
-  Addr head_;
-  Addr tail_;
+  Addr heads_[LAST_ELEMENT];
+  Addr tails_[LAST_ELEMENT];
   BackendImpl* backend_;
   LruData* control_data_;  // Data related to the LRU lists.
   IteratorList iterators_;