table: Content Store performance fix
Change-Id: I7f6752ec279e64e81c90c0b3e8d756da34194965
Refs: #1432
diff --git a/daemon/common.hpp b/daemon/common.hpp
index 974fa57..e60dbc7 100644
--- a/daemon/common.hpp
+++ b/daemon/common.hpp
@@ -79,6 +79,7 @@
using ndn::Interest;
using ndn::Data;
using ndn::Name;
+namespace name = ndn::name;
using ndn::Exclude;
using ndn::Block;
namespace tlv {
diff --git a/daemon/table/cs-entry.cpp b/daemon/table/cs-entry.cpp
index 0708de4..447c710 100644
--- a/daemon/table/cs-entry.cpp
+++ b/daemon/table/cs-entry.cpp
@@ -32,42 +32,22 @@
NFD_LOG_INIT("CsEntry");
-Entry::Entry(const Data& data, bool isUnsolicited)
- : m_dataPacket(data.shared_from_this())
- , m_isUnsolicited(isUnsolicited)
- , m_wasRefreshedByDuplicate(false)
- , m_nameWithDigest(data.getName())
+void
+Entry::release()
{
- updateStaleTime();
- m_nameWithDigest.append(ndn::name::Component(getDigest()));
-}
+ BOOST_ASSERT(m_layerIterators.empty());
-
-Entry::~Entry()
-{
-}
-
-const Name&
-Entry::getName() const
-{
- return m_nameWithDigest;
-}
-
-const Data&
-Entry::getData() const
-{
- return *m_dataPacket;
+ m_dataPacket.reset();
+ m_digest.reset();
+ m_nameWithDigest.clear();
}
void
-Entry::setData(const Data& data)
+Entry::setData(const Data& data, bool isUnsolicited)
{
- /// \todo This method may not be necessary (if it is real duplicate,
- /// there is no reason to recalculate the same digest
-
+ m_isUnsolicited = isUnsolicited;
m_dataPacket = data.shared_from_this();
m_digest.reset();
- m_wasRefreshedByDuplicate = true;
updateStaleTime();
@@ -76,14 +56,10 @@
}
void
-Entry::setData(const Data& data, const ndn::ConstBufferPtr& digest)
+Entry::setData(const Data& data, bool isUnsolicited, const ndn::ConstBufferPtr& digest)
{
- /// \todo This method may not be necessary (if it is real duplicate,
- /// there is no reason to recalculate the same digest
-
m_dataPacket = data.shared_from_this();
m_digest = digest;
- m_wasRefreshedByDuplicate = true;
updateStaleTime();
@@ -91,30 +67,12 @@
m_nameWithDigest.append(ndn::name::Component(getDigest()));
}
-bool
-Entry::isUnsolicited() const
-{
- return m_isUnsolicited;
-}
-
-const time::steady_clock::TimePoint&
-Entry::getStaleTime() const
-{
- return m_staleAt;
-}
-
void
Entry::updateStaleTime()
{
m_staleAt = time::steady_clock::now() + m_dataPacket->getFreshnessPeriod();
}
-bool
-Entry::wasRefreshedByDuplicate() const
-{
- return m_wasRefreshedByDuplicate;
-}
-
const ndn::ConstBufferPtr&
Entry::getDigest() const
{
@@ -139,12 +97,6 @@
m_layerIterators.erase(layer);
}
-const Entry::LayerIterators&
-Entry::getIterators() const
-{
- return m_layerIterators;
-}
-
void
Entry::printIterators() const
{
diff --git a/daemon/table/cs-entry.hpp b/daemon/table/cs-entry.hpp
index be26645..ce3d538 100644
--- a/daemon/table/cs-entry.hpp
+++ b/daemon/table/cs-entry.hpp
@@ -41,11 +41,14 @@
class Entry : noncopyable
{
public:
- typedef std::map<int, std::list< shared_ptr<Entry> >::iterator> LayerIterators;
+ typedef std::map<int, std::list<Entry*>::iterator > LayerIterators;
- Entry(const Data& data, bool isUnsolicited = false);
+ Entry();
- ~Entry();
+ /** \brief releases reference counts on shared objects
+ */
+ void
+ release();
/** \brief returns the name of the Data packet stored in the CS entry
* \return{ NDN name }
@@ -60,11 +63,6 @@
bool
isUnsolicited() const;
- /** \brief Returns True if CS entry was refreshed by a duplicate Data packet
- */
- bool
- wasRefreshedByDuplicate() const;
-
/** \brief returns the absolute time when Data becomes expired
* \return{ Time (resolution up to time::milliseconds) }
*/
@@ -79,12 +77,12 @@
/** \brief changes the content of CS entry and recomputes digest
*/
void
- setData(const Data& data);
+ setData(const Data& data, bool isUnsolicited);
/** \brief changes the content of CS entry and modifies digest
*/
void
- setData(const Data& data, const ndn::ConstBufferPtr& digest);
+ setData(const Data& data, bool isUnsolicited, const ndn::ConstBufferPtr& digest);
/** \brief refreshes the time when Data becomes expired
* according to the current absolute time.
@@ -123,8 +121,6 @@
shared_ptr<const Data> m_dataPacket;
bool m_isUnsolicited;
- bool m_wasRefreshedByDuplicate;
-
Name m_nameWithDigest;
mutable ndn::ConstBufferPtr m_digest;
@@ -132,6 +128,41 @@
LayerIterators m_layerIterators;
};
+inline
+Entry::Entry()
+{
+}
+
+inline const Name&
+Entry::getName() const
+{
+ return m_nameWithDigest;
+}
+
+inline const Data&
+Entry::getData() const
+{
+ return *m_dataPacket;
+}
+
+inline bool
+Entry::isUnsolicited() const
+{
+ return m_isUnsolicited;
+}
+
+inline const time::steady_clock::TimePoint&
+Entry::getStaleTime() const
+{
+ return m_staleAt;
+}
+
+inline const Entry::LayerIterators&
+Entry::getIterators() const
+{
+ return m_layerIterators;
+}
+
} // namespace cs
} // namespace nfd
diff --git a/daemon/table/cs.cpp b/daemon/table/cs.cpp
index 3add035..c86ba54 100644
--- a/daemon/table/cs.cpp
+++ b/daemon/table/cs.cpp
@@ -26,11 +26,10 @@
#include "cs.hpp"
#include "core/logger.hpp"
-
#include <ndn-cpp-dev/util/crypto.hpp>
#define SKIPLIST_MAX_LAYERS 32
-#define SKIPLIST_PROBABILITY 50 // 50% ( p = 1/2 )
+#define SKIPLIST_PROBABILITY 25 // 25% (p = 1/4)
NFD_LOG_INIT("ContentStore");
@@ -38,21 +37,34 @@
Cs::Cs(int nMaxPackets)
: m_nMaxPackets(nMaxPackets)
+ , m_nPackets(0)
{
- srand (time::toUnixTimestamp(time::system_clock::now()).count());
SkipListLayer* zeroLayer = new SkipListLayer();
m_skipList.push_back(zeroLayer);
+
+ for (size_t i = 0; i < m_nMaxPackets; i++)
+ m_freeCsEntries.push(new cs::Entry());
}
Cs::~Cs()
{
- /// \todo Fix memory leak
+ // evict all items from CS
+ while (evictItem())
+ ;
+
+ BOOST_ASSERT(m_freeCsEntries.size() == m_nMaxPackets);
+
+ while (!m_freeCsEntries.empty())
+ {
+ delete m_freeCsEntries.front();
+ m_freeCsEntries.pop();
+ }
}
size_t
Cs::size() const
{
- return (*m_skipList.begin())->size(); // size of the first layer in a skip list
+ return m_nPackets; // size of the first layer in a skip list
}
void
@@ -62,7 +74,8 @@
while (isFull())
{
- evictItem();
+ if (!evictItem())
+ break;
}
}
@@ -73,13 +86,20 @@
}
//Reference: "Skip Lists: A Probabilistic Alternative to Balanced Trees" by W.Pugh
-std::pair< shared_ptr<cs::Entry>, bool>
+std::pair<cs::Entry*, bool>
Cs::insertToSkipList(const Data& data, bool isUnsolicited)
{
NFD_LOG_TRACE("insertToSkipList() " << data.getName() << ", "
<< "skipList size " << size());
- shared_ptr<cs::Entry> entry = make_shared<cs::Entry>(data, isUnsolicited);
+ BOOST_ASSERT(m_cleanupIndex.size() <= size());
+ BOOST_ASSERT(m_freeCsEntries.size() > 0);
+
+ // take entry for the memory pool
+ cs::Entry* entry = m_freeCsEntries.front();
+ m_freeCsEntries.pop();
+ m_nPackets++;
+ entry->setData(data, isUnsolicited);
bool insertInFront = false;
bool isIterated = false;
@@ -87,14 +107,14 @@
SkipListLayer::iterator updateTable[SKIPLIST_MAX_LAYERS];
SkipListLayer::iterator head = (*topLayer)->begin();
- if ( !(*topLayer)->empty() )
+ if (!(*topLayer)->empty())
{
//start from the upper layer towards bottom
int layer = m_skipList.size() - 1;
for (SkipList::reverse_iterator rit = topLayer; rit != m_skipList.rend(); ++rit)
{
//if we didn't do any iterations on the higher layers, start from the begin() again
- if ( !isIterated )
+ if (!isIterated)
head = (*rit)->begin();
updateTable[layer] = head;
@@ -102,7 +122,7 @@
if (head != (*rit)->end())
{
// it can happen when begin() contains the element in front of which we need to insert
- if ( !isIterated && ((*head)->getName() >= entry->getName()) )
+ if (!isIterated && ((*head)->getName() >= entry->getName()))
{
--updateTable[layer];
insertInFront = true;
@@ -153,6 +173,11 @@
(*head)->setData(data, entry->getDigest()); //updates stale time
+ // new entry not needed, returning to the pool
+ entry->release();
+ m_freeCsEntries.push(entry);
+ m_nPackets--;
+
return std::make_pair(*head, false);
}
@@ -160,7 +185,7 @@
size_t randomLayer = pickRandomLayer();
- while ( m_skipList.size() < randomLayer + 1)
+ while (m_skipList.size() < randomLayer + 1)
{
SkipListLayer* newLayer = new SkipListLayer();
m_skipList.push_back(newLayer);
@@ -198,8 +223,6 @@
layer++;
}
- printSkipList();
-
return std::make_pair(entry, true);
}
@@ -214,17 +237,12 @@
}
//pointer and insertion status
- std::pair< shared_ptr<cs::Entry>, bool> entry = insertToSkipList(data, isUnsolicited);
+ std::pair<cs::Entry*, bool> entry = insertToSkipList(data, isUnsolicited);
//new entry
- if (entry.first && (entry.second == true))
+ if (static_cast<bool>(entry.first) && (entry.second == true))
{
- m_contentByArrival.push(entry.first);
- m_contentByStaleness.push(entry.first);
-
- if (entry.first->isUnsolicited())
- m_unsolicitedContent.push(entry.first);
-
+ m_cleanupIndex.push_back(entry.first);
return true;
}
@@ -242,7 +260,7 @@
layer++;
randomValue = rand() % 100 + 1;
}
- while ( (randomValue < SKIPLIST_PROBABILITY) && (layer < SKIPLIST_MAX_LAYERS) );
+ while ((randomValue < SKIPLIST_PROBABILITY) && (layer < SKIPLIST_MAX_LAYERS));
return static_cast<size_t>(layer);
}
@@ -257,40 +275,52 @@
}
bool
-Cs::eraseFromSkipList(shared_ptr<cs::Entry> entry)
+Cs::eraseFromSkipList(cs::Entry* entry)
{
NFD_LOG_TRACE("eraseFromSkipList() " << entry->getName());
NFD_LOG_TRACE("SkipList size " << size());
bool isErased = false;
- int layer = m_skipList.size() - 1;
- for (SkipList::reverse_iterator rit = m_skipList.rbegin(); rit != m_skipList.rend(); ++rit)
- {
- const std::map<int, std::list< shared_ptr<cs::Entry> >::iterator>& iterators = entry->getIterators();
- std::map<int, std::list< shared_ptr<cs::Entry> >::iterator>::const_iterator it = iterators.find(layer);
- if (it != iterators.end())
- {
- (*rit)->erase(it->second);
- entry->removeIterator(layer);
- isErased = true;
- }
+ const std::map<int, std::list<cs::Entry*>::iterator>& iterators = entry->getIterators();
- layer--;
+ if (!iterators.empty())
+ {
+ int layer = 0;
+
+ for (SkipList::iterator it = m_skipList.begin(); it != m_skipList.end(); )
+ {
+ std::map<int, std::list<cs::Entry*>::iterator>::const_iterator i = iterators.find(layer);
+
+ if (i != iterators.end())
+ {
+ (*it)->erase(i->second);
+ entry->removeIterator(layer);
+ isErased = true;
+
+ //remove layers that do not contain any elements (starting from the second layer)
+ if ((layer != 0) && (*it)->empty())
+ {
+ delete *it;
+ it = m_skipList.erase(it);
+ }
+ else
+ ++it;
+
+ layer++;
+ }
+ else
+ break;
+ }
}
- printSkipList();
-
- //remove layers that do not contain any elements (starting from the second layer)
- for (SkipList::iterator it = (++m_skipList.begin()); it != m_skipList.end();)
- {
- if ((*it)->empty())
- {
- it = m_skipList.erase(it);
- }
- else
- ++it;
- }
+ //delete entry;
+ if (isErased)
+ {
+ entry->release();
+ m_freeCsEntries.push(entry);
+ m_nPackets--;
+ }
return isErased;
}
@@ -300,65 +330,34 @@
{
NFD_LOG_TRACE("evictItem()");
- //because there is a possibility that this item is in a queue, but no longer in skiplist
- while ( !m_unsolicitedContent.empty() )
- {
- NFD_LOG_TRACE("Evict from unsolicited queue");
+ if (!m_cleanupIndex.get<unsolicited>().empty() &&
+ (*m_cleanupIndex.get<unsolicited>().begin())->isUnsolicited())
+ {
+ NFD_LOG_TRACE("Evict from unsolicited queue");
- shared_ptr<cs::Entry> entry = m_unsolicitedContent.front();
- m_unsolicitedContent.pop();
- bool isErased = eraseFromSkipList(entry);
+ eraseFromSkipList(*m_cleanupIndex.get<unsolicited>().begin());
+ m_cleanupIndex.get<unsolicited>().erase(m_cleanupIndex.get<unsolicited>().begin());
+ return true;
+ }
- if (isErased)
- return true;
- }
+ if (!m_cleanupIndex.get<byStaleness>().empty() &&
+ (*m_cleanupIndex.get<byStaleness>().begin())->getStaleTime() < time::steady_clock::now())
+ {
+ NFD_LOG_TRACE("Evict from staleness queue");
- //because there is a possibility that this item is in a queue, but no longer in skiplist
- int nIterations = size() * 0.01; // 1% of the Content Store
- while ( !m_contentByStaleness.empty() )
- {
- NFD_LOG_TRACE("Evict from staleness queue");
+ eraseFromSkipList(*m_cleanupIndex.get<byStaleness>().begin());
+ m_cleanupIndex.get<byStaleness>().erase(m_cleanupIndex.get<byStaleness>().begin());
+ return true;
+ }
- shared_ptr<cs::Entry> entry = m_contentByStaleness.top();
+ if (!m_cleanupIndex.get<byArrival>().empty())
+ {
+ NFD_LOG_TRACE("Evict from arrival queue");
- //because stale time could be updated by the duplicate packet
- if (entry->getStaleTime() < time::steady_clock::now())
- {
- m_contentByStaleness.pop();
- bool isErased = eraseFromSkipList(entry);
-
- if (isErased)
- return true;
- }
- else if ( (entry->getStaleTime() > time::steady_clock::now()) && entry->wasRefreshedByDuplicate() )
- {
- m_contentByStaleness.pop();
- m_contentByStaleness.push(entry); // place in a right order
-
- nIterations--;
- // if 1% of the CS are non-expired refreshed CS entries (allocated sequentially),
- // then stop to prevent too many iterations
- if ( nIterations <= 0 )
- break;
- }
- else //no further item will be expired, stop
- {
- break;
- }
- }
-
- //because there is a possibility that this item is in a queue, but no longer in skiplist
- while ( !m_contentByArrival.empty() )
- {
- NFD_LOG_TRACE("Evict from arrival queue");
-
- shared_ptr<cs::Entry> entry = m_contentByArrival.front();
- m_contentByArrival.pop();
- bool isErased = eraseFromSkipList(entry);
-
- if (isErased)
- return true;
- }
+ eraseFromSkipList(*m_cleanupIndex.get<byArrival>().begin());
+ m_cleanupIndex.get<byArrival>().erase(m_cleanupIndex.get<byArrival>().begin());
+ return true;
+ }
return false;
}
@@ -372,7 +371,7 @@
SkipList::const_reverse_iterator topLayer = m_skipList.rbegin();
SkipListLayer::iterator head = (*topLayer)->begin();
- if ( !(*topLayer)->empty() )
+ if (!(*topLayer)->empty())
{
//start from the upper layer towards bottom
int layer = m_skipList.size() - 1;
@@ -385,7 +384,7 @@
if (head != (*rit)->end())
{
// it happens when begin() contains the element we want to find
- if ( !isIterated && (interest.getName().isPrefixOf((*head)->getName())) )
+ if (!isIterated && (interest.getName().isPrefixOf((*head)->getName())))
{
if (layer > 0)
{
@@ -401,7 +400,7 @@
{
SkipListLayer::iterator it = head;
- while ( (*it)->getName() < interest.getName() )
+ while ((*it)->getName() < interest.getName())
{
NFD_LOG_TRACE((*it)->getName() << " < " << interest.getName());
head = it;
@@ -420,7 +419,7 @@
}
else //if we reached the first layer
{
- if ( isIterated )
+ if (isIterated)
return selectChild(interest, head);
}
@@ -431,19 +430,18 @@
return 0;
}
-// because skip list is a probabilistic data structure and the way it is traversed,
-// there is no guarantee that startingPoint is an element preceding the leftmost child
const Data*
Cs::selectChild(const Interest& interest, SkipListLayer::iterator startingPoint) const
{
- BOOST_ASSERT( startingPoint != (*m_skipList.begin())->end() );
+ BOOST_ASSERT(startingPoint != (*m_skipList.begin())->end());
if (startingPoint != (*m_skipList.begin())->begin())
{
- BOOST_ASSERT( (*startingPoint)->getName() < interest.getName() );
+ BOOST_ASSERT((*startingPoint)->getName() < interest.getName());
}
- NFD_LOG_TRACE("selectChild() " << interest.getChildSelector() << " " << (*startingPoint)->getName());
+ NFD_LOG_TRACE("selectChild() " << interest.getChildSelector() << " "
+ << (*startingPoint)->getName());
bool hasLeftmostSelector = (interest.getChildSelector() <= 0);
bool hasRightmostSelector = !hasLeftmostSelector;
@@ -464,7 +462,7 @@
if (isInPrefix)
{
- if (doesComplyWithSelectors(interest, *startingPoint))
+ if (doesComplyWithSelectors(interest, *startingPoint, doesInterestContainDigest))
{
return &(*startingPoint)->getData();
}
@@ -487,11 +485,13 @@
bool doesInterestContainDigest = false;
if (isInBoundaries)
{
- doesInterestContainDigest = recognizeInterestWithDigest(interest, *rightmostCandidate);
+ doesInterestContainDigest = recognizeInterestWithDigest(interest,
+ *rightmostCandidate);
if (doesInterestContainDigest)
{
- isInPrefix = interest.getName().getPrefix(-1).isPrefixOf((*rightmostCandidate)->getName());
+ isInPrefix = interest.getName().getPrefix(-1)
+ .isPrefixOf((*rightmostCandidate)->getName());
}
else
{
@@ -501,7 +501,7 @@
if (isInPrefix)
{
- if (doesComplyWithSelectors(interest, *rightmostCandidate))
+ if (doesComplyWithSelectors(interest, *rightmostCandidate, doesInterestContainDigest))
{
if (hasLeftmostSelector)
{
@@ -512,11 +512,13 @@
{
if (doesInterestContainDigest)
{
- // get prefix which is one component longer than Interest name (without digest)
- const Name& childPrefix = (*rightmostCandidate)->getName().getPrefix(interest.getName().size());
+ // get prefix which is one component longer than Interest name
+ // (without digest)
+ const Name& childPrefix = (*rightmostCandidate)->getName()
+ .getPrefix(interest.getName().size());
NFD_LOG_TRACE("Child prefix" << childPrefix);
- if ( currentChildPrefix.empty() || (childPrefix != currentChildPrefix) )
+ if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix))
{
currentChildPrefix = childPrefix;
rightmost = rightmostCandidate;
@@ -525,10 +527,11 @@
else
{
// get prefix which is one component longer than Interest name
- const Name& childPrefix = (*rightmostCandidate)->getName().getPrefix(interest.getName().size() + 1);
+ const Name& childPrefix = (*rightmostCandidate)->getName()
+ .getPrefix(interest.getName().size() + 1);
NFD_LOG_TRACE("Child prefix" << childPrefix);
- if ( currentChildPrefix.empty() || (childPrefix != currentChildPrefix) )
+ if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix))
{
currentChildPrefix = childPrefix;
rightmost = rightmostCandidate;
@@ -563,7 +566,7 @@
if (isInPrefix)
{
- if (doesComplyWithSelectors(interest, *startingPoint))
+ if (doesComplyWithSelectors(interest, *startingPoint, doesInterestContainDigest))
{
return &(*startingPoint)->getData();
}
@@ -574,16 +577,18 @@
}
bool
-Cs::doesComplyWithSelectors(const Interest& interest, shared_ptr<cs::Entry> entry) const
+Cs::doesComplyWithSelectors(const Interest& interest,
+ cs::Entry* entry,
+ bool doesInterestContainDigest) const
{
NFD_LOG_TRACE("doesComplyWithSelectors()");
/// \todo The following detection is not correct
/// 1. If data name ends with 32-octet component doesn't mean that this component is digest
- /// 2. Only min/max selectors (both 0) can be specified, all other selectors do not make sense
- /// for interests with digest (though not sure if we need to enforce this)
- bool doesInterestContainDigest = recognizeInterestWithDigest(interest, entry);
- if ( doesInterestContainDigest )
+ /// 2. Only min/max selectors (both 0) can be specified, all other selectors do not
+ /// make sense for interests with digest (though not sure if we need to enforce this)
+
+ if (doesInterestContainDigest)
{
const ndn::name::Component& last = interest.getName().get(-1);
const ndn::ConstBufferPtr& digest = entry->getDigest();
@@ -598,14 +603,14 @@
}
}
- if ( !doesInterestContainDigest )
+ if (!doesInterestContainDigest)
{
if (interest.getMinSuffixComponents() >= 0)
{
size_t minDataNameLength = interest.getName().size() + interest.getMinSuffixComponents();
bool isSatisfied = (minDataNameLength <= entry->getName().size());
- if ( !isSatisfied )
+ if (!isSatisfied)
{
NFD_LOG_TRACE("violates minComponents");
return false;
@@ -617,7 +622,7 @@
size_t maxDataNameLength = interest.getName().size() + interest.getMaxSuffixComponents();
bool isSatisfied = (maxDataNameLength >= entry->getName().size());
- if ( !isSatisfied )
+ if (!isSatisfied)
{
NFD_LOG_TRACE("violates maxComponents");
return false;
@@ -631,11 +636,11 @@
return false;
}
- if ( doesInterestContainDigest )
+ if (doesInterestContainDigest)
{
const ndn::name::Component& lastComponent = entry->getName().get(-1);
- if ( !lastComponent.empty() )
+ if (!lastComponent.empty())
{
if (interest.getExclude().isExcluded(lastComponent))
{
@@ -648,9 +653,9 @@
{
if (entry->getName().size() >= interest.getName().size() + 1)
{
- const ndn::name::Component& nextComponent = entry->getName().get(interest.getName().size());
-
- if ( !nextComponent.empty() )
+ const ndn::name::Component& nextComponent = entry->getName()
+ .get(interest.getName().size());
+ if (!nextComponent.empty())
{
if (interest.getExclude().isExcluded(nextComponent))
{
@@ -666,7 +671,7 @@
}
bool
-Cs::recognizeInterestWithDigest(const Interest& interest, shared_ptr<cs::Entry> entry) const
+Cs::recognizeInterestWithDigest(const Interest& interest, cs::Entry* entry) const
{
// only when min selector is not specified or specified with value of 0
// and Interest's name length is exactly the length of the name of CS entry
@@ -695,14 +700,14 @@
SkipList::reverse_iterator topLayer = m_skipList.rbegin();
SkipListLayer::iterator head = (*topLayer)->begin();
- if ( !(*topLayer)->empty() )
+ if (!(*topLayer)->empty())
{
//start from the upper layer towards bottom
int layer = m_skipList.size() - 1;
for (SkipList::reverse_iterator rit = topLayer; rit != m_skipList.rend(); ++rit)
{
//if we didn't do any iterations on the higher layers, start from the begin() again
- if ( !isIterated )
+ if (!isIterated)
head = (*rit)->begin();
updateTable[layer] = head;
@@ -710,7 +715,7 @@
if (head != (*rit)->end())
{
// it can happen when begin() contains the element we want to remove
- if ( !isIterated && ((*head)->getName() == exactName) )
+ if (!isIterated && ((*head)->getName() == exactName))
{
eraseFromSkipList(*head);
return;
@@ -726,7 +731,7 @@
isIterated = true;
++it;
- if ( it == (*rit)->end() )
+ if (it == (*rit)->end())
break;
}
}
@@ -760,8 +765,6 @@
NFD_LOG_TRACE("Found target " << (*head)->getName());
eraseFromSkipList(*head);
}
-
- printSkipList();
}
void
diff --git a/daemon/table/cs.hpp b/daemon/table/cs.hpp
index 56783ef..a1769ea 100644
--- a/daemon/table/cs.hpp
+++ b/daemon/table/cs.hpp
@@ -30,11 +30,71 @@
#include "common.hpp"
#include "cs-entry.hpp"
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+#include <boost/multi_index/identity.hpp>
+
+using namespace ::boost;
+using namespace ::boost::multi_index;
+
namespace nfd {
-typedef std::list< shared_ptr<cs::Entry> > SkipListLayer;
+typedef std::list<cs::Entry*> SkipListLayer;
typedef std::list<SkipListLayer*> SkipList;
+class StalenessComparator
+{
+public:
+ bool
+ operator()(const cs::Entry* entry1, const cs::Entry* entry2) const
+ {
+ return entry1->getStaleTime() < entry2->getStaleTime();
+ }
+};
+
+class UnsolicitedComparator
+{
+public:
+ bool
+ operator()(const cs::Entry* entry1, const cs::Entry* entry2) const
+ {
+ return entry1->isUnsolicited();
+ }
+};
+
+// tags
+class unsolicited;
+class byStaleness;
+class byArrival;
+
+typedef multi_index_container<
+ cs::Entry*,
+ indexed_by<
+
+ // by arrival (FIFO)
+ sequenced<
+ tag<byArrival>
+ >,
+
+ // index by staleness time
+ ordered_non_unique<
+ tag<byStaleness>,
+ identity<cs::Entry*>,
+ StalenessComparator
+ >,
+
+ // unsolicited Data is in the front
+ ordered_non_unique<
+ tag<unsolicited>,
+ identity<cs::Entry*>,
+ UnsolicitedComparator
+ >
+
+ >
+> CleanupIndex;
+
/** \brief represents Content Store
*/
class Cs : noncopyable
@@ -110,14 +170,14 @@
* \return{ returns a pair containing a pointer to the CS Entry,
* and a flag indicating if the entry was newly created (True) or refreshed (False) }
*/
- std::pair< shared_ptr<cs::Entry>, bool>
+ std::pair<cs::Entry*, bool>
insertToSkipList(const Data& data, bool isUnsolicited = false);
/** \brief Removes a specific CS Entry from all layers of a skip list
* \return{ returns True if CS Entry was succesfully removed and False if CS Entry was not found}
*/
bool
- eraseFromSkipList(shared_ptr<cs::Entry> entry);
+ eraseFromSkipList(cs::Entry* entry);
/** \brief Prints contents of the skip list, starting from the top layer
*/
@@ -144,32 +204,23 @@
* \return{ true if satisfies all selectors; false otherwise }
*/
bool
- doesComplyWithSelectors(const Interest& interest, shared_ptr<cs::Entry> entry) const;
+ doesComplyWithSelectors(const Interest& interest,
+ cs::Entry* entry,
+ bool doesInterestContainDigest) const;
/** \brief interprets minSuffixComponent and name lengths to understand if Interest contains
* implicit digest of the data
* \return{ True if Interest name contains digest; False otherwise }
*/
bool
- recognizeInterestWithDigest(const Interest& interest, shared_ptr<cs::Entry> entry) const;
+ recognizeInterestWithDigest(const Interest& interest, cs::Entry* entry) const;
private:
- class StalenessComparator
- {
- public:
- bool
- operator() (shared_ptr<cs::Entry> entry1, shared_ptr<cs::Entry> entry2)
- {
- return entry1->getStaleTime() > entry2->getStaleTime();
- }
- };
-
SkipList m_skipList;
- size_t m_nMaxPackets; //user defined maximum size of the Content Store in packets
-
- std::queue< shared_ptr<cs::Entry> > m_unsolicitedContent; //FIFO for unsolicited Data
- std::queue< shared_ptr<cs::Entry> > m_contentByArrival; //FIFO index
- std::priority_queue< shared_ptr<cs::Entry>, std::vector< shared_ptr<cs::Entry> >, StalenessComparator> m_contentByStaleness; //index by staleness time
+ CleanupIndex m_cleanupIndex;
+ size_t m_nMaxPackets; // user defined maximum size of the Content Store in packets
+ size_t m_nPackets; // current number of packets in Content Store
+ std::queue<cs::Entry*> m_freeCsEntries; // memory pool
};
} // namespace nfd