[svn] commit: r2315 - /branches/trac192/src/lib/datasrc/cache.cc

[BIND 10 source code commits]

Author: each
Date: Mon Jun 28 20:44:09 2010
New Revision: 2315

Log:
Refactor HotCache to use a std::list for the LRU queue.

Modified:
    branches/trac192/src/lib/datasrc/cache.cc

Modified: branches/trac192/src/lib/datasrc/cache.cc
==============================================================================
--- branches/trac192/src/lib/datasrc/cache.cc (original)
+++ branches/trac192/src/lib/datasrc/cache.cc Mon Jun 28 20:44:09 2010
@@ -23,6 +23,8 @@
 #include <dns/rrset.h>
 #include <dns/rrtype.h>
 
+#include <list>
+
 #include <datasrc/cache.h>
 
 using namespace std;
@@ -111,9 +113,9 @@
     bool isValid() const;
     //@}
 
-    // Links to next and previous nodes in the LRU list.
-    CacheNodePtr prev;
-    CacheNodePtr next;
+    // An iterator referencing this entry in the LRU list. This
+    // permits unit-time removal using list::erase().
+    list<CacheNodePtr>::iterator lru_entry_;
 
     /// The \c Question (name/rrclass/rrtype) answered by this cache node
     const isc::dns::Question question;
@@ -135,8 +137,6 @@
     expiry = now + lifespan;
 
     entry = CacheEntryPtr(new CacheEntry(rrset, flags));
-    prev = CacheNodePtr();
-    next = CacheNodePtr();
 }
 
 // CacheNode constructor for a negative cache entry
@@ -151,10 +151,7 @@
     expiry = now + lifespan;
 
     entry = CacheEntryPtr(new CacheEntry(RRsetPtr(), flags));
-    prev = CacheNodePtr();
-    next = CacheNodePtr();
-}
-
+}
 // Returns true if the node has not yet expired.
 bool
 CacheNode::isValid() const {
@@ -177,16 +174,14 @@
 class HotCacheImpl {
 public:
     HotCacheImpl(int slots, bool enabled);
-    ~HotCacheImpl();
-
-    // Pointers to the head and tail of the LRU list.
-    CacheNodePtr lru_head_;
-    CacheNodePtr lru_tail_;
-
-    // Is this cache enabled?  (True by default)
+
+    // The LRU list
+    list<CacheNodePtr> lru_;
+
+    // Flag to indicate whether the cache is enabled
     bool enabled_;
 
-    // Number of available slots in the LRU list.  (If zero,
+    // The number of available slots in the LRU list.  (If zero,
     // then the list is unbounded; otherwise, items are removed
     // from the tail of the list whenever it grows past slots_.)
     int slots_;
@@ -194,10 +189,11 @@
     // The number of items currently in the list.
     int count_;
 
-    // Map from query tuple to cache node pointer, allowing faster retrieval
+    // Map from query tuple to cache node pointer, allowing fast retrieval
+    // of data without a linear search of the LRU list
     std::map<Question, CacheNodePtr> map_;
 
-    // Move a node to the front of the LRU queue.
+    // Move a node to the front of the LRU list.
     void promote(CacheNodePtr node);
 
     // Remove a node from the cache.
@@ -211,19 +207,6 @@
 HotCacheImpl::HotCacheImpl(int slots, bool enabled) :
     enabled_(enabled), slots_(slots), count_(0)
 {}
-
-// HotCacheImpl destructor
-HotCacheImpl::~HotCacheImpl() {
-    CacheNodePtr node;
-    for (node = lru_head_; node != CacheNodePtr(); node = node->next) {
-        lru_head_ = node->next;
-        if (lru_head_) {
-            lru_head_->prev = CacheNodePtr();
-        }
-    }
-
-    lru_head_ = lru_tail_ = CacheNodePtr();
-}
 
 // Insert a cache node into the cache
 inline void
@@ -237,74 +220,35 @@
         }
     }
 
-    if (lru_head_) {
-        node->next = lru_head_;
-        lru_head_->prev = node;
-        lru_head_ = node;
-    } else {
-        node->next = lru_head_;
-        lru_head_ = node;
-        lru_tail_ = node;
-    }
+    lru_.push_front(node);
+    node->lru_entry_ = lru_.begin();
 
     map_[node->question] = node;
     ++count_;
 
-    if (slots_ != 0 && count_ > slots_ && lru_tail_) {
-        remove(lru_tail_);
-        assert(count_ == slots_);
-    }
-}
-
-// Promote a node to the head of the LRU queue
+    if (slots_ != 0 && count_ > slots_) {
+        remove(lru_.back());
+    }
+}
+
+// Promote a node to the head of the LRU list
 void
 HotCacheImpl::promote(CacheNodePtr node) {
-    if (!node || node == lru_head_) {
-        return;
-    }
-
-    if (node->prev) {
-        node->prev->next = node->next;
-    }
-
-    if (node->next) {
-        node->next->prev = node->prev;
-    }
-
-    if (node == lru_tail_) {
-        lru_tail_ = node->prev;
-        lru_tail_->next = CacheNodePtr();
-    }
-
-    lru_head_->prev = node;
-    node->prev = CacheNodePtr();
-    node->next = lru_head_;
-    lru_head_ = node;
-}
-
-// Remove a node from the LRU queue and the map
+    if (!node) {
+        return;
+    }
+    if (node->lru_entry_ == lru_.begin()) {
+        return;
+    }
+    lru_.erase(node->lru_entry_);
+    lru_.push_front(node);
+    node->lru_entry_ = lru_.begin();
+}
+
+// Remove a node from the LRU list and the map
 void
 HotCacheImpl::remove(ConstCacheNodePtr node) {
-    if (!node) {
-        return;
-    }
-    
-    if (node == lru_head_) {
-        lru_head_ = node->next;
-    }
-
-    if (node == lru_tail_) {
-        lru_tail_ = node->prev;
-    }
-
-    if (node->next) {
-        node->next->prev = node->prev;
-    }
-
-    if (node->prev) {
-        node->prev->next = node->next;
-    }
-
+    lru_.erase(node->lru_entry_);
     map_.erase(node->question);
     --count_;
 }
@@ -387,10 +331,8 @@
         return;
     }
 
-    while (impl_->slots_ != 0 && impl_->count_ > impl_->slots_ &&
-           impl_->lru_tail_)
-    {
-        impl_->remove(impl_->lru_tail_);
+    while (impl_->slots_ != 0 && impl_->count_ > impl_->slots_) {
+        impl_->remove(impl_->lru_.back());
     }
 }