table: rewrite ContentStore
This is the first of a series of commits that rewrites the ContentStore
with a cleaner design.
refs #2254
Change-Id: I6595dca63137760d2283934a8f311a14dc2183bf
diff --git a/daemon/table/cs-entry.cpp b/daemon/table/cs-entry.cpp
index 1262065..be6202c 100644
--- a/daemon/table/cs-entry.cpp
+++ b/daemon/table/cs-entry.cpp
@@ -21,64 +21,121 @@
*
* You should have received a copy of the GNU General Public License along with
* NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- *
- * \author Ilya Moiseenko <http://ilyamoiseenko.com/>
- * \author Junxiao Shi <http://www.cs.arizona.edu/people/shijunxiao/>
- * \author Alexander Afanasyev <http://lasr.cs.ucla.edu/afanasyev/index.html>
*/
#include "cs-entry.hpp"
-#include "core/logger.hpp"
namespace nfd {
namespace cs {
-NFD_LOG_INIT("CsEntry");
-
-void
-Entry::release()
+Entry::Entry(const Name& name)
+ : m_queryName(name)
{
- BOOST_ASSERT(m_layerIterators.empty());
+ BOOST_ASSERT(this->isQuery());
+}
- m_dataPacket.reset();
+Entry::Entry(shared_ptr<const Data> data, bool isUnsolicited)
+ : queueType(Cs::QUEUE_NONE)
+ , m_data(data)
+ , m_isUnsolicited(isUnsolicited)
+{
+ BOOST_ASSERT(!this->isQuery());
+}
+
+bool
+Entry::isQuery() const
+{
+ return m_data == nullptr;
+}
+
+shared_ptr<const Data>
+Entry::getData() const
+{
+ BOOST_ASSERT(!this->isQuery());
+ return m_data;
+}
+
+const Name&
+Entry::getFullName() const
+{
+ BOOST_ASSERT(!this->isQuery());
+ return m_data->getFullName();
+}
+
+bool
+Entry::canStale() const
+{
+ BOOST_ASSERT(!this->isQuery());
+ return m_data->getFreshnessPeriod() >= time::milliseconds::zero();
+}
+
+bool
+Entry::isStale() const
+{
+ BOOST_ASSERT(!this->isQuery());
+ return time::steady_clock::now() > m_staleAt;
}
void
-Entry::setData(const Data& data, bool isUnsolicited)
+Entry::refresh()
{
- m_isUnsolicited = isUnsolicited;
- m_dataPacket = data.shared_from_this();
+ BOOST_ASSERT(!this->isQuery());
+ if (this->canStale()) {
+ m_staleAt = time::steady_clock::now() + time::milliseconds(m_data->getFreshnessPeriod());
+ }
+ else {
+ m_staleAt = time::steady_clock::TimePoint::max();
+ }
+}
- updateStaleTime();
+bool
+Entry::isUnsolicited() const
+{
+ BOOST_ASSERT(!this->isQuery());
+ return m_isUnsolicited;
}
void
-Entry::updateStaleTime()
+Entry::unsetUnsolicited()
{
- m_staleAt = time::steady_clock::now() + m_dataPacket->getFreshnessPeriod();
+ BOOST_ASSERT(!this->isQuery());
+ m_isUnsolicited = false;
}
-void
-Entry::setIterator(int layer, const Entry::LayerIterators::mapped_type& layerIterator)
+bool
+Entry::canSatisfy(const Interest& interest) const
{
- m_layerIterators[layer] = layerIterator;
+ BOOST_ASSERT(!this->isQuery());
+ if (!interest.matchesData(*m_data)) {
+ return false;
+ }
+
+ if (interest.getMustBeFresh() == static_cast<int>(true) && this->isStale()) {
+ return false;
+ }
+
+ return true;
}
-void
-Entry::removeIterator(int layer)
+bool
+Entry::operator<(const Entry& other) const
{
- m_layerIterators.erase(layer);
-}
-
-void
-Entry::printIterators() const
-{
- for (LayerIterators::const_iterator it = m_layerIterators.begin();
- it != m_layerIterators.end();
- ++it)
- {
- NFD_LOG_TRACE("[" << it->first << "]" << " " << &(*it->second));
+ if (this->isQuery()) {
+ if (other.isQuery()) {
+ return m_queryName < other.m_queryName;
}
+ else {
+ return m_queryName < other.m_queryName;
+ }
+ }
+ else {
+ if (other.isQuery()) {
+ return this->getFullName() < other.m_queryName;
+ }
+ else {
+ return this->getFullName() < other.getFullName();
+ }
+ }
}
} // namespace cs
diff --git a/daemon/table/cs-entry.hpp b/daemon/table/cs-entry.hpp
index 0373e60..12a65b0 100644
--- a/daemon/table/cs-entry.hpp
+++ b/daemon/table/cs-entry.hpp
@@ -21,149 +21,82 @@
*
* You should have received a copy of the GNU General Public License along with
* NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- *
- * \author Ilya Moiseenko <http://ilyamoiseenko.com/>
- * \author Junxiao Shi <http://www.cs.arizona.edu/people/shijunxiao/>
- * \author Alexander Afanasyev <http://lasr.cs.ucla.edu/afanasyev/index.html>
*/
#ifndef NFD_DAEMON_TABLE_CS_ENTRY_HPP
#define NFD_DAEMON_TABLE_CS_ENTRY_HPP
-#include "common.hpp"
+#include "cs.hpp"
+#include "core/scheduler.hpp"
namespace nfd {
namespace cs {
-class Entry;
-
-/** \brief represents a CS entry
+/** \brief an Entry in ContentStore
+ * \note This type is internal to ContentStore.
+ *
+ * An Entry is either a stored Entry which contains a Data packet and related attributes,
+ * or a query Entry which contains a Name that is LessComparable to other stored/query Entry
+ * and is used to lookup a container of entries.
*/
-class Entry : noncopyable
+class Entry
{
public:
- typedef std::map<int, std::list<Entry*>::iterator > LayerIterators;
-
- Entry();
-
- /** \brief releases reference counts on shared objects
+ /** \brief construct Entry for query
+ * \note Name is implicitly convertible to Entry, so that Name can be passed to
+ * lookup functions on a container of Entry
*/
- void
- release();
+ Entry(const Name& name);
- /** \brief returns the name of the Data packet stored in the CS entry
- * \return{ NDN name }
+ /** \brief construct Entry for storage
*/
- const Name&
- getName() const;
+ Entry(shared_ptr<const Data> data, bool isUnsolicited);
- /** \brief returns the full name (including implicit digest) of the Data packet stored
- * in the CS entry
- * \return{ NDN name }
- */
+ shared_ptr<const Data>
+ getData() const;
+
const Name&
getFullName() const;
- /** \brief Data packet is unsolicited if this particular NDN node
- * did not receive an Interest packet for it, or the Interest packet has already expired
- * \return{ True if the Data packet is unsolicited; otherwise False }
+ /** \return true if entry can become stale, false if entry is never stale
*/
bool
+ canStale() const;
+
+ bool
+ isStale() const;
+
+ void
+ refresh();
+
+ bool
isUnsolicited() const;
- /** \brief returns the absolute time when Data becomes expired
- * \return{ Time (resolution up to time::milliseconds) }
- */
- const time::steady_clock::TimePoint&
- getStaleTime() const;
-
- /** \brief returns the Data packet stored in the CS entry
- */
- const Data&
- getData() const;
-
- /** \brief changes the content of CS entry and recomputes digest
- */
void
- setData(const Data& data, bool isUnsolicited);
+ unsetUnsolicited();
- /** \brief refreshes the time when Data becomes expired
- * according to the current absolute time.
- */
- void
- updateStaleTime();
+ bool
+ canSatisfy(const Interest& interest) const;
- /** \brief saves the iterator pointing to the CS entry on a specific layer of skip list
- */
- void
- setIterator(int layer, const LayerIterators::mapped_type& layerIterator);
-
- /** \brief removes the iterator pointing to the CS entry on a specific layer of skip list
- */
- void
- removeIterator(int layer);
-
- /** \brief returns the table containing <layer, iterator> pairs.
- */
- const LayerIterators&
- getIterators() const;
+ bool
+ operator<(const Entry& other) const;
private:
- /** \brief prints <layer, iterator> pairs.
- */
- void
- printIterators() const;
+ bool
+ isQuery() const;
+
+public:
+ Cs::QueueType queueType;
+ Cs::QueueIt queueIt;
+ scheduler::EventId moveStaleEvent;
private:
+ Name m_queryName;
+ shared_ptr<const Data> m_data;
time::steady_clock::TimePoint m_staleAt;
- shared_ptr<const Data> m_dataPacket;
-
bool m_isUnsolicited;
-
- LayerIterators m_layerIterators;
};
-inline
-Entry::Entry()
-{
-}
-
-inline const Name&
-Entry::getName() const
-{
- return m_dataPacket->getName();
-}
-
-inline const Name&
-Entry::getFullName() const
-{
- return m_dataPacket->getFullName();
-}
-
-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 e575694..822cb84 100644
--- a/daemon/table/cs.cpp
+++ b/daemon/table/cs.cpp
@@ -21,806 +21,214 @@
*
* You should have received a copy of the GNU General Public License along with
* NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- *
- * \author Ilya Moiseenko <http://ilyamoiseenko.com/>
- * \author Junxiao Shi <http://www.cs.arizona.edu/people/shijunxiao/>
- * \author Alexander Afanasyev <http://lasr.cs.ucla.edu/afanasyev/index.html>
*/
#include "cs.hpp"
+#include "cs-entry.hpp"
#include "core/logger.hpp"
-#include "core/random.hpp"
-
-#include <ndn-cxx/util/crypto.hpp>
-#include <ndn-cxx/security/signature-sha256-with-rsa.hpp>
-
-#include <boost/random/bernoulli_distribution.hpp>
-
-/// max skip list layers
-static const size_t SKIPLIST_MAX_LAYERS = 32;
-/// probability for an entry in layer N to appear also in layer N+1
-static const double SKIPLIST_PROBABILITY = 0.25;
+#include <numeric>
NFD_LOG_INIT("ContentStore");
namespace nfd {
+namespace cs {
Cs::Cs(size_t nMaxPackets)
- : m_nMaxPackets(nMaxPackets)
- , m_nPackets(0)
+ : m_limit(nMaxPackets)
{
- SkipListLayer* zeroLayer = new SkipListLayer();
- m_skipList.push_back(zeroLayer);
-
- for (size_t i = 0; i < m_nMaxPackets; i++)
- m_freeCsEntries.push(new cs::Entry());
+ BOOST_ASSERT(nMaxPackets > 0);
}
Cs::~Cs()
{
- // 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_nPackets; // size of the first layer in a skip list
+ // It's necessary to put this empty destructor in cs.cpp,
+ // because cs::Entry has incomplete type in cs.hpp.
}
void
Cs::setLimit(size_t nMaxPackets)
{
- size_t oldNMaxPackets = m_nMaxPackets;
- m_nMaxPackets = nMaxPackets;
-
- while (size() > m_nMaxPackets) {
- evictItem();
- }
-
- if (m_nMaxPackets >= oldNMaxPackets) {
- for (size_t i = oldNMaxPackets; i < m_nMaxPackets; i++) {
- m_freeCsEntries.push(new cs::Entry());
- }
- }
- else {
- for (size_t i = oldNMaxPackets; i > m_nMaxPackets; i--) {
- delete m_freeCsEntries.front();
- m_freeCsEntries.pop();
- }
- }
+ BOOST_ASSERT(nMaxPackets > 0);
+ m_limit = nMaxPackets;
+ this->evict();
}
size_t
-Cs::getLimit() const
+Cs::size() const
{
- return m_nMaxPackets;
-}
-
-//Reference: "Skip Lists: A Probabilistic Alternative to Balanced Trees" by W.Pugh
-std::pair<cs::Entry*, bool>
-Cs::insertToSkipList(const Data& data, bool isUnsolicited)
-{
- NFD_LOG_TRACE("insertToSkipList() " << data.getFullName() << ", "
- << "skipList size " << size());
-
- 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;
- SkipList::reverse_iterator topLayer = m_skipList.rbegin();
- SkipListLayer::iterator updateTable[SKIPLIST_MAX_LAYERS];
- SkipListLayer::iterator head = (*topLayer)->begin();
-
- 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)
- head = (*rit)->begin();
-
- updateTable[layer] = head;
-
- if (head != (*rit)->end())
- {
- // it can happen when begin() contains the element in front of which we need to insert
- if (!isIterated && ((*head)->getFullName() >= entry->getFullName()))
- {
- --updateTable[layer];
- insertInFront = true;
- }
- else
- {
- SkipListLayer::iterator it = head;
-
- while ((*it)->getFullName() < entry->getFullName())
- {
- head = it;
- updateTable[layer] = it;
- isIterated = true;
-
- ++it;
- if (it == (*rit)->end())
- break;
- }
- }
- }
-
- if (layer > 0)
- head = (*head)->getIterators().find(layer - 1)->second; // move HEAD to the lower layer
-
- layer--;
- }
- }
- else
- {
- updateTable[0] = (*topLayer)->begin(); //initialization
- }
-
- head = updateTable[0];
- ++head; // look at the next slot to check if it contains a duplicate
-
- bool isCsEmpty = (size() == 0);
- bool isInBoundaries = (head != (*m_skipList.begin())->end());
- bool isNameIdentical = false;
- if (!isCsEmpty && isInBoundaries)
- {
- isNameIdentical = (*head)->getFullName() == entry->getFullName();
- }
-
- //check if this is a duplicate packet
- if (isNameIdentical)
- {
- NFD_LOG_TRACE("Duplicate name (with digest)");
-
- (*head)->setData(data, isUnsolicited); //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);
- }
-
- NFD_LOG_TRACE("Not a duplicate");
-
- size_t randomLayer = pickRandomLayer();
-
- while (m_skipList.size() < randomLayer + 1)
- {
- SkipListLayer* newLayer = new SkipListLayer();
- m_skipList.push_back(newLayer);
-
- updateTable[(m_skipList.size() - 1)] = newLayer->begin();
- }
-
- size_t layer = 0;
- for (SkipList::iterator i = m_skipList.begin();
- i != m_skipList.end() && layer <= randomLayer; ++i)
- {
- if (updateTable[layer] == (*i)->end() && !insertInFront)
- {
- (*i)->push_back(entry);
- SkipListLayer::iterator last = (*i)->end();
- --last;
- entry->setIterator(layer, last);
-
- NFD_LOG_TRACE("pushback " << &(*last));
- }
- else if (updateTable[layer] == (*i)->end() && insertInFront)
- {
- (*i)->push_front(entry);
- entry->setIterator(layer, (*i)->begin());
-
- NFD_LOG_TRACE("pushfront ");
- }
- else
- {
- NFD_LOG_TRACE("insertafter");
- ++updateTable[layer]; // insert after
- SkipListLayer::iterator position = (*i)->insert(updateTable[layer], entry);
- entry->setIterator(layer, position); // save iterator where item was inserted
- }
- layer++;
- }
-
- return std::make_pair(entry, true);
+ return m_table.size();
}
bool
Cs::insert(const Data& data, bool isUnsolicited)
{
- NFD_LOG_TRACE("insert() " << data.getFullName());
+ NFD_LOG_DEBUG("insert " << data.getFullName());
- if (isFull())
- {
- evictItem();
- }
+ bool isNewEntry = false; TableIt it;
+ // use .insert because gcc46 does not support .emplace
+ std::tie(it, isNewEntry) = m_table.insert(Entry(data.shared_from_this(), isUnsolicited));
+ Entry& entry = const_cast<Entry&>(*it);
- //pointer and insertion status
- std::pair<cs::Entry*, bool> entry = insertToSkipList(data, isUnsolicited);
-
- //new entry
- if (static_cast<bool>(entry.first) && (entry.second == true))
- {
- m_cleanupIndex.push_back(entry.first);
- return true;
- }
-
- return false;
-}
-
-size_t
-Cs::pickRandomLayer() const
-{
- static boost::random::bernoulli_distribution<> dist(SKIPLIST_PROBABILITY);
- // TODO rewrite using geometry_distribution
- size_t layer;
- for (layer = 0; layer < SKIPLIST_MAX_LAYERS; ++layer) {
- if (!dist(getGlobalRng())) {
- break;
+ if (!isNewEntry) { // existing entry
+ this->detachQueue(it);
+ // XXX This doesn't forbid unsolicited Data from refreshing a solicited entry.
+ if (entry.isUnsolicited() && !isUnsolicited) {
+ entry.unsetUnsolicited();
}
}
- return layer;
+ entry.refresh();
+ this->attachQueue(it);
+
+ // check there are same amount of entries in the table and in queues
+ BOOST_ASSERT(m_table.size() == std::accumulate(m_queues, m_queues + QUEUE_UBOUND, 0U,
+ [] (size_t sum, const Queue queue) { return sum + queue.size(); }));
+
+ this->evict(); // XXX The new entry could be evicted, but it shouldn't matter.
+
+ return true;
}
bool
-Cs::isFull() const
+Cs::isNewRightmostCandidate(const Name& prefix, TableIt a, TableIt b)
{
- if (size() >= m_nMaxPackets) //size of the first layer vs. max size
- return true;
-
- return false;
-}
-
-bool
-Cs::eraseFromSkipList(cs::Entry* entry)
-{
- NFD_LOG_TRACE("eraseFromSkipList() " << entry->getFullName());
- NFD_LOG_TRACE("SkipList size " << size());
-
- bool isErased = false;
-
- const std::map<int, std::list<cs::Entry*>::iterator>& iterators = entry->getIterators();
-
- 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;
- }
- }
-
- //delete entry;
- if (isErased)
- {
- entry->release();
- m_freeCsEntries.push(entry);
- m_nPackets--;
- }
-
- return isErased;
-}
-
-bool
-Cs::evictItem()
-{
- NFD_LOG_TRACE("evictItem()");
-
- if (!m_cleanupIndex.get<unsolicited>().empty()) {
- CleanupIndex::index<unsolicited>::type::const_iterator firstSolicited =
- m_cleanupIndex.get<unsolicited>().upper_bound(false);
-
- if (firstSolicited != m_cleanupIndex.get<unsolicited>().begin()) {
- --firstSolicited;
- BOOST_ASSERT((*firstSolicited)->isUnsolicited());
- NFD_LOG_TRACE("Evict from unsolicited queue");
-
- eraseFromSkipList(*firstSolicited);
- m_cleanupIndex.get<unsolicited>().erase(firstSolicited);
- return true;
- }
- else {
- BOOST_ASSERT(!(*m_cleanupIndex.get<unsolicited>().begin())->isUnsolicited());
- }
- }
-
- if (!m_cleanupIndex.get<byStaleness>().empty() &&
- (*m_cleanupIndex.get<byStaleness>().begin())->getStaleTime() < time::steady_clock::now())
- {
- NFD_LOG_TRACE("Evict from staleness queue");
-
- eraseFromSkipList(*m_cleanupIndex.get<byStaleness>().begin());
- m_cleanupIndex.get<byStaleness>().erase(m_cleanupIndex.get<byStaleness>().begin());
+ if (a->getFullName().size() == prefix.size()) {
return true;
}
-
- if (!m_cleanupIndex.get<byArrival>().empty())
- {
- NFD_LOG_TRACE("Evict from arrival queue");
-
- eraseFromSkipList(*m_cleanupIndex.get<byArrival>().begin());
- m_cleanupIndex.get<byArrival>().erase(m_cleanupIndex.get<byArrival>().begin());
- return true;
- }
-
- return false;
+ return b->getFullName().at(prefix.size()) > a->getFullName().at(prefix.size());
}
const Data*
Cs::find(const Interest& interest) const
{
- NFD_LOG_TRACE("find() " << interest.getName());
+ const Name& prefix = interest.getName();
+ bool isRightmost = interest.getChildSelector() == 1;
+ NFD_LOG_DEBUG("find " << prefix << (isRightmost ? " R" : " L"));
+ TableIt rightmostCandidate = m_table.end();
- bool isIterated = false;
- SkipList::const_reverse_iterator topLayer = m_skipList.rbegin();
- SkipListLayer::iterator head = (*topLayer)->begin();
-
- if (!(*topLayer)->empty())
- {
- //start from the upper layer towards bottom
- int layer = m_skipList.size() - 1;
- for (SkipList::const_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)
- head = (*rit)->begin();
-
- if (head != (*rit)->end())
- {
- // it happens when begin() contains the element we want to find
- if (!isIterated && (interest.getName().isPrefixOf((*head)->getFullName())))
- {
- if (layer > 0)
- {
- layer--;
- continue; // try lower layer
- }
- else
- {
- isIterated = true;
- }
- }
- else
- {
- SkipListLayer::iterator it = head;
-
- while ((*it)->getFullName() < interest.getName())
- {
- NFD_LOG_TRACE((*it)->getFullName() << " < " << interest.getName());
- head = it;
- isIterated = true;
-
- ++it;
- if (it == (*rit)->end())
- break;
- }
- }
- }
-
- if (layer > 0)
- {
- head = (*head)->getIterators().find(layer - 1)->second; // move HEAD to the lower layer
- }
- else //if we reached the first layer
- {
- if (isIterated)
- return selectChild(interest, head);
- }
-
- layer--;
- }
+ TableIt left = m_table.lower_bound(prefix);
+ TableIt right = m_table.end();
+ if (prefix.size() > 0) {
+ right = m_table.lower_bound(prefix.getSuccessor());
+ }
+ for (TableIt it = left; it != right; ++it) {
+ const Entry& entry = *it;
+ if (!entry.canSatisfy(interest)) {
+ NFD_LOG_TRACE("cannotSatisfy " << entry.getFullName());
+ continue;
+ }
+ NFD_LOG_TRACE("canSatisfy " << entry.getFullName());
+ if (!isRightmost) {
+ return entry.getData().get();
}
- return 0;
-}
-
-const Data*
-Cs::selectChild(const Interest& interest, SkipListLayer::iterator startingPoint) const
-{
- BOOST_ASSERT(startingPoint != (*m_skipList.begin())->end());
-
- if (startingPoint != (*m_skipList.begin())->begin())
- {
- BOOST_ASSERT((*startingPoint)->getFullName() < interest.getName());
+ if (rightmostCandidate == m_table.end() ||
+ isNewRightmostCandidate(prefix, rightmostCandidate, it)) {
+ NFD_LOG_TRACE("rightmostCandidate=" << entry.getFullName());
+ rightmostCandidate = it;
}
-
- NFD_LOG_TRACE("selectChild() " << interest.getChildSelector() << " "
- << (*startingPoint)->getFullName());
-
- bool hasLeftmostSelector = (interest.getChildSelector() <= 0);
- bool hasRightmostSelector = !hasLeftmostSelector;
-
- if (hasLeftmostSelector)
- {
- bool doesInterestContainDigest = recognizeInterestWithDigest(interest, *startingPoint);
- bool isInPrefix = false;
-
- if (doesInterestContainDigest)
- {
- isInPrefix = interest.getName().getPrefix(-1).isPrefixOf((*startingPoint)->getFullName());
- }
- else
- {
- isInPrefix = interest.getName().isPrefixOf((*startingPoint)->getFullName());
- }
-
- if (isInPrefix)
- {
- if (doesComplyWithSelectors(interest, *startingPoint, doesInterestContainDigest))
- {
- return &(*startingPoint)->getData();
- }
- }
- }
-
- //iterate to the right
- SkipListLayer::iterator rightmost = startingPoint;
- if (startingPoint != (*m_skipList.begin())->end())
- {
- SkipListLayer::iterator rightmostCandidate = startingPoint;
- Name currentChildPrefix("");
-
- while (true)
- {
- ++rightmostCandidate;
-
- bool isInBoundaries = (rightmostCandidate != (*m_skipList.begin())->end());
- bool isInPrefix = false;
- bool doesInterestContainDigest = false;
- if (isInBoundaries)
- {
- doesInterestContainDigest = recognizeInterestWithDigest(interest,
- *rightmostCandidate);
-
- if (doesInterestContainDigest)
- {
- isInPrefix = interest.getName().getPrefix(-1)
- .isPrefixOf((*rightmostCandidate)->getFullName());
- }
- else
- {
- isInPrefix = interest.getName().isPrefixOf((*rightmostCandidate)->getFullName());
- }
- }
-
- if (isInPrefix)
- {
- if (doesComplyWithSelectors(interest, *rightmostCandidate, doesInterestContainDigest))
- {
- if (hasLeftmostSelector)
- {
- return &(*rightmostCandidate)->getData();
- }
-
- if (hasRightmostSelector)
- {
- if (doesInterestContainDigest)
- {
- // get prefix which is one component longer than Interest name
- // (without digest)
- const Name& childPrefix = (*rightmostCandidate)->getFullName()
- .getPrefix(interest.getName().size());
- NFD_LOG_TRACE("Child prefix" << childPrefix);
-
- if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix))
- {
- currentChildPrefix = childPrefix;
- rightmost = rightmostCandidate;
- }
- }
- else
- {
- // get prefix which is one component longer than Interest name
- const Name& childPrefix = (*rightmostCandidate)->getFullName()
- .getPrefix(interest.getName().size() + 1);
- NFD_LOG_TRACE("Child prefix" << childPrefix);
-
- if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix))
- {
- currentChildPrefix = childPrefix;
- rightmost = rightmostCandidate;
- }
- }
- }
- }
- }
- else
- break;
- }
- }
-
- if (rightmost != startingPoint)
- {
- return &(*rightmost)->getData();
- }
-
- if (hasRightmostSelector) // if rightmost was not found, try starting point
- {
- bool doesInterestContainDigest = recognizeInterestWithDigest(interest, *startingPoint);
- bool isInPrefix = false;
-
- if (doesInterestContainDigest)
- {
- isInPrefix = interest.getName().getPrefix(-1).isPrefixOf((*startingPoint)->getFullName());
- }
- else
- {
- isInPrefix = interest.getName().isPrefixOf((*startingPoint)->getFullName());
- }
-
- if (isInPrefix)
- {
- if (doesComplyWithSelectors(interest, *startingPoint, doesInterestContainDigest))
- {
- return &(*startingPoint)->getData();
- }
- }
- }
-
- return 0;
-}
-
-bool
-Cs::doesComplyWithSelectors(const Interest& interest,
- cs::Entry* entry,
- bool doesInterestContainDigest) const
-{
- NFD_LOG_TRACE("doesComplyWithSelectors()");
-
- /// \todo The following detection is not correct
- /// 1. If Interest 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)
-
- if (doesInterestContainDigest)
- {
- if (interest.getName().get(-1) != entry->getFullName().get(-1))
- {
- NFD_LOG_TRACE("violates implicit digest");
- return false;
- }
- }
-
- if (!doesInterestContainDigest)
- {
- if (interest.getMinSuffixComponents() >= 0)
- {
- size_t minDataNameLength = interest.getName().size() + interest.getMinSuffixComponents();
-
- bool isSatisfied = (minDataNameLength <= entry->getFullName().size());
- if (!isSatisfied)
- {
- NFD_LOG_TRACE("violates minComponents");
- return false;
- }
- }
-
- if (interest.getMaxSuffixComponents() >= 0)
- {
- size_t maxDataNameLength = interest.getName().size() + interest.getMaxSuffixComponents();
-
- bool isSatisfied = (maxDataNameLength >= entry->getFullName().size());
- if (!isSatisfied)
- {
- NFD_LOG_TRACE("violates maxComponents");
- return false;
- }
- }
- }
-
- if (interest.getMustBeFresh() && entry->getStaleTime() < time::steady_clock::now())
- {
- NFD_LOG_TRACE("violates mustBeFresh");
- return false;
- }
-
- if (!interest.getPublisherPublicKeyLocator().empty())
- {
- if (entry->getData().getSignature().getType() == ndn::Signature::Sha256WithRsa)
- {
- ndn::SignatureSha256WithRsa rsaSignature(entry->getData().getSignature());
- if (rsaSignature.getKeyLocator() != interest.getPublisherPublicKeyLocator())
- {
- NFD_LOG_TRACE("violates publisher key selector");
- return false;
- }
- }
- else
- {
- NFD_LOG_TRACE("violates publisher key selector");
- return false;
- }
- }
-
- if (doesInterestContainDigest)
- {
- const ndn::name::Component& lastComponent = entry->getFullName().get(-1);
-
- if (!lastComponent.empty())
- {
- if (interest.getExclude().isExcluded(lastComponent))
- {
- NFD_LOG_TRACE("violates exclusion");
- return false;
- }
- }
- }
- else
- {
- if (entry->getFullName().size() >= interest.getName().size() + 1)
- {
- const ndn::name::Component& nextComponent = entry->getFullName()
- .get(interest.getName().size());
- if (!nextComponent.empty())
- {
- if (interest.getExclude().isExcluded(nextComponent))
- {
- NFD_LOG_TRACE("violates exclusion");
- return false;
- }
- }
- }
- }
-
- NFD_LOG_TRACE("complies");
- return true;
-}
-
-bool
-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
- if (interest.getMinSuffixComponents() <= 0 &&
- interest.getName().size() == (entry->getFullName().size()))
- {
- const ndn::name::Component& last = interest.getName().get(-1);
- if (last.value_size() == ndn::crypto::SHA256_DIGEST_SIZE)
- {
- NFD_LOG_TRACE("digest recognized");
- return true;
- }
- }
-
- return false;
+ }
+ if (isRightmost) {
+ return rightmostCandidate == m_table.end() ? nullptr :
+ rightmostCandidate->getData().get();
+ }
+ return nullptr;
}
void
-Cs::erase(const Name& exactName)
+Cs::attachQueue(TableIt it)
{
- NFD_LOG_TRACE("insert() " << exactName << ", "
- << "skipList size " << size());
+ Entry& entry = const_cast<Entry&>(*it);
- bool isIterated = false;
- SkipListLayer::iterator updateTable[SKIPLIST_MAX_LAYERS];
- SkipList::reverse_iterator topLayer = m_skipList.rbegin();
- SkipListLayer::iterator head = (*topLayer)->begin();
+ if (entry.queueType != QUEUE_NONE) {
+ this->detachQueue(it);
+ }
- 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)
- head = (*rit)->begin();
+ if (entry.isUnsolicited()) {
+ entry.queueType = QUEUE_UNSOLICITED;
+ }
+ else if (entry.isStale()) {
+ entry.queueType = QUEUE_STALE;
+ }
+ else {
+ entry.queueType = QUEUE_FIFO;
- updateTable[layer] = head;
-
- if (head != (*rit)->end())
- {
- // it can happen when begin() contains the element we want to remove
- if (!isIterated && ((*head)->getFullName() == exactName))
- {
- eraseFromSkipList(*head);
- return;
- }
- else
- {
- SkipListLayer::iterator it = head;
-
- while ((*it)->getFullName() < exactName)
- {
- head = it;
- updateTable[layer] = it;
- isIterated = true;
-
- ++it;
- if (it == (*rit)->end())
- break;
- }
- }
- }
-
- if (layer > 0)
- head = (*head)->getIterators().find(layer - 1)->second; // move HEAD to the lower layer
-
- layer--;
- }
+ if (entry.canStale()) {
+ entry.moveStaleEvent = scheduler::schedule(entry.getData()->getFreshnessPeriod(),
+ bind(&Cs::moveToStaleQueue, this, it));
}
- else
- {
- return;
- }
+ }
- head = updateTable[0];
- ++head; // look at the next slot to check if it contains the item we want to remove
-
- bool isCsEmpty = (size() == 0);
- bool isInBoundaries = (head != (*m_skipList.begin())->end());
- bool isNameIdentical = false;
- if (!isCsEmpty && isInBoundaries)
- {
- NFD_LOG_TRACE("Identical? " << (*head)->getFullName());
- isNameIdentical = (*head)->getFullName() == exactName;
- }
-
- if (isNameIdentical)
- {
- NFD_LOG_TRACE("Found target " << (*head)->getFullName());
- eraseFromSkipList(*head);
- }
+ Queue& queue = m_queues[entry.queueType];
+ entry.queueIt = queue.insert(queue.end(), it);
}
void
-Cs::printSkipList() const
+Cs::detachQueue(TableIt it)
{
- NFD_LOG_TRACE("print()");
- //start from the upper layer towards bottom
- int layer = m_skipList.size() - 1;
- for (SkipList::const_reverse_iterator rit = m_skipList.rbegin(); rit != m_skipList.rend(); ++rit)
- {
- for (SkipListLayer::iterator it = (*rit)->begin(); it != (*rit)->end(); ++it)
- {
- NFD_LOG_TRACE("Layer " << layer << " " << (*it)->getFullName());
- }
- layer--;
- }
+ Entry& entry = const_cast<Entry&>(*it);
+
+ BOOST_ASSERT(entry.queueType != QUEUE_NONE);
+
+ if (entry.queueType == QUEUE_FIFO) {
+ scheduler::cancel(entry.moveStaleEvent);
+ }
+
+ m_queues[entry.queueType].erase(entry.queueIt);
+ entry.queueType = QUEUE_NONE;
}
-} //namespace nfd
+void
+Cs::moveToStaleQueue(TableIt it)
+{
+ Entry& entry = const_cast<Entry&>(*it);
+
+ BOOST_ASSERT(entry.queueType == QUEUE_FIFO);
+ m_queues[QUEUE_FIFO].erase(entry.queueIt);
+
+ entry.queueType = QUEUE_STALE;
+ Queue& queue = m_queues[QUEUE_STALE];
+ entry.queueIt = queue.insert(queue.end(), it);
+}
+
+std::tuple<Cs::TableIt, std::string>
+Cs::evictPick()
+{
+ if (!m_queues[QUEUE_UNSOLICITED].empty()) {
+ return std::make_tuple(m_queues[QUEUE_UNSOLICITED].front(), "unsolicited");
+ }
+ if (!m_queues[QUEUE_STALE].empty()) {
+ return std::make_tuple(m_queues[QUEUE_STALE].front(), "stale");
+ }
+ if (!m_queues[QUEUE_FIFO].empty()) {
+ return std::make_tuple(m_queues[QUEUE_FIFO].front(), "fifo");
+ }
+
+ BOOST_ASSERT(false);
+ return std::make_tuple(m_table.end(), "error");
+}
+
+
+void
+Cs::evict()
+{
+ while (this->size() > m_limit) {
+ TableIt it; std::string reason;
+ std::tie(it, reason) = this->evictPick();
+
+ NFD_LOG_DEBUG("evict " << it->getFullName() << " " << reason);
+ this->detachQueue(it);
+ m_table.erase(it);
+ }
+}
+
+void
+Cs::dump()
+{
+ NFD_LOG_DEBUG("dump table");
+ for (const Entry& entry : m_table) {
+ NFD_LOG_TRACE(entry.getFullName());
+ }
+}
+
+} // namespace cs
+} // namespace nfd
diff --git a/daemon/table/cs.hpp b/daemon/table/cs.hpp
index f683a20..4eadd40 100644
--- a/daemon/table/cs.hpp
+++ b/daemon/table/cs.hpp
@@ -21,92 +21,41 @@
*
* You should have received a copy of the GNU General Public License along with
* NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/** \file
*
- * \author Ilya Moiseenko <http://ilyamoiseenko.com/>
- * \author Junxiao Shi <http://www.cs.arizona.edu/people/shijunxiao/>
- * \author Alexander Afanasyev <http://lasr.cs.ucla.edu/afanasyev/index.html>
+ * \brief implements the ContentStore
+ *
+ * This ContentStore implementation consists of two data structures,
+ * a Table, and a set of cleanup queues.
+ *
+ * The Table is a container (std::set) sorted by full Names of stored Data packets.
+ * Data packets are wrapped in Entry objects.
+ * Each Entry contain the Data packet itself,
+ * and a few addition attributes such as the staleness of the Data packet.
+ *
+ * The cleanup queues are three doubly linked lists which stores Table iterators.
+ * The three queues keep track of unsolicited, stale, and fresh Data packet, respectively.
+ * Table iterator is placed into, removed from, and moved between suitable queues
+ * whenever an Entry is added, removed, or has other attribute changes.
+ * The Table iterator of an Entry should be in exactly one queue at any moment.
+ * Within each queue, the iterators are kept in first-in-first-out order.
+ * Eviction procedure exhausts the first queue before moving onto the next queue,
+ * in the order of unsolicited, stale, and fresh queue.
*/
#ifndef NFD_DAEMON_TABLE_CS_HPP
#define NFD_DAEMON_TABLE_CS_HPP
#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>
-
-#include <queue>
namespace nfd {
+namespace cs {
-typedef std::list<cs::Entry*> SkipListLayer;
-typedef std::list<SkipListLayer*> SkipList;
+class Entry;
-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();
- }
-
- bool
- operator()(bool isUnsolicited, const cs::Entry* entry) const
- {
- if (isUnsolicited)
- return true;
- else
- return !entry->isUnsolicited();
- }
-};
-
-// tags
-class unsolicited;
-class byStaleness;
-class byArrival;
-
-typedef boost::multi_index_container<
- cs::Entry*,
- boost::multi_index::indexed_by<
-
- // by arrival (FIFO)
- boost::multi_index::sequenced<
- boost::multi_index::tag<byArrival>
- >,
-
- // index by staleness time
- boost::multi_index::ordered_non_unique<
- boost::multi_index::tag<byStaleness>,
- boost::multi_index::identity<cs::Entry*>,
- StalenessComparator
- >,
-
- // unsolicited Data is in the front
- boost::multi_index::ordered_non_unique<
- boost::multi_index::tag<unsolicited>,
- boost::multi_index::identity<cs::Entry*>,
- UnsolicitedComparator
- >
-
- >
-> CleanupIndex;
-
-/** \brief represents Content Store
+/** \brief represents the ContentStore
*/
class Cs : noncopyable
{
@@ -117,123 +66,101 @@
~Cs();
/** \brief inserts a Data packet
- * This method does not consider the payload of the Data packet.
- *
- * Packets are considered duplicate if the name matches.
- * The new Data packet with the identical name, but a different payload
- * is not placed in the Content Store
- * \return{ whether the Data is added }
+ * \return true
*/
bool
insert(const Data& data, bool isUnsolicited = false);
- /** \brief finds the best match Data for an Interest
- * \return{ the best match, if any; otherwise 0 }
+ /** \brief finds the best matching Data packet
*/
const Data*
find(const Interest& interest) const;
- /** \brief deletes CS entry by the exact name
- */
void
- erase(const Name& exactName);
+ erase(const Name& exactName)
+ {
+ BOOST_ASSERT_MSG(false, "not implemented");
+ }
- /** \brief sets maximum allowed size of Content Store (in packets)
+ /** \brief changes capacity (in number of packets)
*/
void
setLimit(size_t nMaxPackets);
- /** \brief returns maximum allowed size of Content Store (in packets)
- * \return{ number of packets that can be stored in Content Store }
+ /** \return capacity (in number of packets)
*/
size_t
- getLimit() const;
+ getLimit() const
+ {
+ return m_limit;
+ }
- /** \brief returns current size of Content Store measured in packets
- * \return{ number of packets located in Content Store }
+ /** \return number of stored packets
*/
size_t
size() const;
-protected:
- /** \brief removes one Data packet from Content Store based on replacement policy
- * \return{ whether the Data was removed }
- */
- bool
- evictItem();
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ void
+ dump();
+
+public:
+ typedef std::set<Entry> Table;
+ typedef Table::const_iterator TableIt;
+ typedef std::list<TableIt> Queue;
+ typedef Queue::iterator QueueIt;
+ enum QueueType {
+ QUEUE_UNSOLICITED,
+ QUEUE_STALE,
+ QUEUE_FIFO,
+ QUEUE_UBOUND,
+ QUEUE_NONE = QUEUE_UBOUND
+ };
private:
- /** \brief returns True if the Content Store is at its maximum capacity
- * \return{ True if Content Store is full; otherwise False}
+ /** \brief determines whether b should be the rightmost candidate instead of a
*/
- bool
- isFull() const;
+ static bool
+ isNewRightmostCandidate(const Name& prefix, TableIt a, TableIt b);
- /** \brief Computes the layer where new Content Store Entry is placed
- *
- * Reference: "Skip Lists: A Probabilistic Alternative to Balanced Trees" by W.Pugh
- * \return{ returns random layer (number) in a skip list}
- */
- size_t
- pickRandomLayer() const;
-
- /** \brief Inserts a new Content Store Entry in a skip list
- * \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<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(cs::Entry* entry);
-
- /** \brief Prints contents of the skip list, starting from the top layer
+ /** \brief attaches an entry to a suitable cleanup queue
+ * \note if the entry is already attached to a queue, it's automatically detached
*/
void
- printSkipList() const;
+ attachQueue(TableIt it);
- /** \brief Implements child selector (leftmost, rightmost, undeclared).
- * Operates on the first layer of a skip list.
- *
- * startingPoint must be less than Interest Name.
- * startingPoint can be equal to Interest Name only when the item is in the begin() position.
- *
- * Iterates toward greater Names, terminates when CS entry falls out of Interest prefix.
- * When childSelector = leftmost, returns first CS entry that satisfies other selectors.
- * When childSelector = rightmost, it goes till the end, and returns CS entry that satisfies
- * other selectors. Returned CS entry is the leftmost child of the rightmost child.
- * \return{ the best match, if any; otherwise 0 }
+ /** \brief detaches an entry from its current cleanup queue
+ * \warning if the entry is unattached, this will cause undefined behavior
*/
- const Data*
- selectChild(const Interest& interest, SkipListLayer::iterator startingPoint) const;
+ void
+ detachQueue(TableIt it);
- /** \brief checks if Content Store entry satisfies Interest selectors (MinSuffixComponents,
- * MaxSuffixComponents, Implicit Digest, MustBeFresh)
- * \return{ true if satisfies all selectors; false otherwise }
+ /** \brief moves an entry from FIFO queue to STALE queue
*/
- bool
- doesComplyWithSelectors(const Interest& interest,
- cs::Entry* entry,
- bool doesInterestContainDigest) const;
+ void
+ moveToStaleQueue(TableIt it);
- /** \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 }
+ /** \brief picks an entry for eviction
*/
- bool
- recognizeInterestWithDigest(const Interest& interest, cs::Entry* entry) const;
+ std::tuple<TableIt, std::string/*reason*/>
+ evictPick();
+
+ /** \brief evicts zero or more entries so that number of stored entries
+ * is not greater than capacity
+ */
+ void
+ evict();
private:
- SkipList m_skipList;
- 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
+ size_t m_limit;
+ Table m_table;
+ Queue m_queues[QUEUE_UBOUND];
};
+} // namespace cs
+
+using cs::Cs;
+
} // namespace nfd
#endif // NFD_DAEMON_TABLE_CS_HPP
diff --git a/tests/daemon/table/cs.cpp b/tests/daemon/table/cs.cpp
index d38538e..6a55353 100644
--- a/tests/daemon/table/cs.cpp
+++ b/tests/daemon/table/cs.cpp
@@ -1,11 +1,12 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014 Regents of the University of California,
- * Arizona Board of Regents,
- * Colorado State University,
- * University Pierre & Marie Curie, Sorbonne University,
- * Washington University in St. Louis,
- * Beijing Institute of Technology
+ * Copyright (c) 2014, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis
*
* This file is part of NFD (Named Data Networking Forwarding Daemon).
* See AUTHORS.md for complete list of NFD authors and contributors.
@@ -20,633 +21,32 @@
*
* You should have received a copy of the GNU General Public License along with
* NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- *
- * \author Ilya Moiseenko <iliamo@ucla.edu>
- **/
+ */
#include "table/cs.hpp"
-#include "table/cs-entry.hpp"
+#include <ndn-cxx/util/crypto.hpp>
#include "tests/test-common.hpp"
namespace nfd {
namespace tests {
-class CsAccessor : public Cs
-{
-public:
- bool
- evictItem_accessor()
- {
- return evictItem();
- }
-};
-
BOOST_FIXTURE_TEST_SUITE(TableCs, BaseFixture)
-BOOST_AUTO_TEST_CASE(SetLimit)
-{
- Cs cs(1);
-
- BOOST_CHECK_EQUAL(cs.insert(*makeData("/1")), true);
- BOOST_CHECK_EQUAL(cs.insert(*makeData("/2")), true);
- BOOST_CHECK_EQUAL(cs.size(), 1);
-
- cs.setLimit(3);
- BOOST_CHECK_EQUAL(cs.insert(*makeData("/3")), true);
- BOOST_CHECK_EQUAL(cs.insert(*makeData("/4")), true);
- BOOST_CHECK_EQUAL(cs.insert(*makeData("/5")), true);
- BOOST_CHECK_EQUAL(cs.size(), 3);
-
- cs.setLimit(2);
- BOOST_CHECK_EQUAL(cs.size(), 2);
-}
-
-BOOST_AUTO_TEST_CASE(Insertion)
-{
- Cs cs;
-
- BOOST_CHECK_EQUAL(cs.insert(*makeData("/insertion")), true);
-}
-
-BOOST_AUTO_TEST_CASE(Insertion2)
-{
- Cs cs;
-
- cs.insert(*makeData("/a"));
- cs.insert(*makeData("/b"));
- cs.insert(*makeData("/c"));
- cs.insert(*makeData("/d"));
-
- BOOST_CHECK_EQUAL(cs.size(), 4);
-}
-
-BOOST_AUTO_TEST_CASE(DuplicateInsertion)
-{
- Cs cs;
-
- shared_ptr<Data> data0 = makeData("/insert/smth");
- BOOST_CHECK_EQUAL(cs.insert(*data0), true);
-
- shared_ptr<Data> data = makeData("/insert/duplicate");
- BOOST_CHECK_EQUAL(cs.insert(*data), true);
-
- cs.insert(*data);
- BOOST_CHECK_EQUAL(cs.size(), 2);
-}
-
-
-BOOST_AUTO_TEST_CASE(DuplicateInsertion2)
-{
- Cs cs;
-
- shared_ptr<Data> data = makeData("/insert/duplicate");
- BOOST_CHECK_EQUAL(cs.insert(*data), true);
-
- cs.insert(*data);
- BOOST_CHECK_EQUAL(cs.size(), 1);
-
- shared_ptr<Data> data2 = makeData("/insert/original");
- BOOST_CHECK_EQUAL(cs.insert(*data2), true);
- BOOST_CHECK_EQUAL(cs.size(), 2);
-}
-
-BOOST_AUTO_TEST_CASE(InsertAndFind)
-{
- Cs cs;
-
- Name name("/insert/and/find");
-
- shared_ptr<Data> data = makeData(name);
- BOOST_CHECK_EQUAL(cs.insert(*data), true);
-
- shared_ptr<Interest> interest = make_shared<Interest>(name);
-
- const Data* found = cs.find(*interest);
-
- BOOST_REQUIRE(found != 0);
- BOOST_CHECK_EQUAL(data->getName(), found->getName());
-}
-
-BOOST_AUTO_TEST_CASE(InsertAndNotFind)
-{
- Cs cs;
-
- Name name("/insert/and/find");
- shared_ptr<Data> data = makeData(name);
- BOOST_CHECK_EQUAL(cs.insert(*data), true);
-
- Name name2("/not/find");
- shared_ptr<Interest> interest = make_shared<Interest>(name2);
-
- const Data* found = cs.find(*interest);
-
- BOOST_CHECK_EQUAL(found, static_cast<const Data*>(0));
-}
-
-
-BOOST_AUTO_TEST_CASE(InsertAndErase)
-{
- CsAccessor cs;
-
- shared_ptr<Data> data = makeData("/insertandelete");
- cs.insert(*data);
- BOOST_CHECK_EQUAL(cs.size(), 1);
-
- cs.evictItem_accessor();
- BOOST_CHECK_EQUAL(cs.size(), 0);
-}
-
-BOOST_AUTO_TEST_CASE(StalenessQueue)
-{
- CsAccessor cs;
-
- Name name2("/insert/fresh");
- shared_ptr<Data> data2 = makeData(name2);
- data2->setFreshnessPeriod(time::milliseconds(5000));
- signData(data2);
- cs.insert(*data2);
-
- Name name("/insert/expire");
- shared_ptr<Data> data = makeData(name);
- data->setFreshnessPeriod(time::milliseconds(500));
- signData(data);
- cs.insert(*data);
-
- BOOST_CHECK_EQUAL(cs.size(), 2);
-
- sleep(3);
-
- cs.evictItem_accessor();
- BOOST_CHECK_EQUAL(cs.size(), 1);
-
- shared_ptr<Interest> interest = make_shared<Interest>(name2);
- const Data* found = cs.find(*interest);
- BOOST_REQUIRE(found != 0);
- BOOST_CHECK_EQUAL(found->getName(), name2);
-}
-
-BOOST_AUTO_TEST_CASE(Bug2043) // eviction order of unsolicited packets
-{
- Cs cs(3);
-
- cs.insert(*makeData("/a"), true);
- cs.insert(*makeData("/b"), true);
- cs.insert(*makeData("/c"), true);
- BOOST_CHECK_EQUAL(cs.size(), 3);
-
- cs.insert(*makeData("/d"), true);
- BOOST_CHECK_EQUAL(cs.size(), 3);
-
- const Data* oldestData = cs.find(Interest("/a"));
- const Data* newestData = cs.find(Interest("/c"));
- BOOST_CHECK(oldestData == 0);
- BOOST_CHECK(newestData != 0);
-}
-
-BOOST_AUTO_TEST_CASE(UnsolicitedWithSolicitedEvictionOrder)
-{
- Cs cs(3);
-
- cs.insert(*makeData("/a"), true);
- cs.insert(*makeData("/b"), false);
- cs.insert(*makeData("/c"), true);
- BOOST_CHECK_EQUAL(cs.size(), 3);
-
- cs.insert(*makeData("/d"), true);
- BOOST_CHECK_EQUAL(cs.size(), 3);
-
- const Data* oldestData = cs.find(Interest("/a"));
- const Data* newestData = cs.find(Interest("/c"));
- BOOST_CHECK(oldestData == 0);
- BOOST_CHECK(newestData != 0);
-}
-
-//even max size
-BOOST_AUTO_TEST_CASE(ReplacementEvenSize)
-{
- Cs cs(4);
-
- shared_ptr<Data> data = makeData("/a");
- cs.insert(*data);
-
- shared_ptr<Data> data2 = makeData("/b");
- cs.insert(*data2);
-
- shared_ptr<Data> data3 = makeData("/c");
- cs.insert(*data3);
-
- shared_ptr<Data> data4 = makeData("/d");
- cs.insert(*data4);
-
- shared_ptr<Data> data5 = makeData("/e");
- cs.insert(*data5);
-
- BOOST_CHECK_EQUAL(cs.size(), 4);
-}
-
-//odd max size
-BOOST_AUTO_TEST_CASE(Replacement2)
-{
- Cs cs(3);
-
- shared_ptr<Data> data = makeData("/a");
- cs.insert(*data);
-
- shared_ptr<Data> data2 = makeData("/b");
- cs.insert(*data2);
-
- shared_ptr<Data> data3 = makeData("/c");
- cs.insert(*data3);
-
- shared_ptr<Data> data4 = makeData("/d");
- cs.insert(*data4);
-
- BOOST_CHECK_EQUAL(cs.size(), 3);
-}
-
-BOOST_AUTO_TEST_CASE(InsertAndEraseByName)
-{
- CsAccessor cs;
-
- Name name("/insertandremovebyname");
- shared_ptr<Data> data = makeData(name);
- cs.insert(*data);
-
- ndn::ConstBufferPtr digest1 = ndn::crypto::sha256(data->wireEncode().wire(),
- data->wireEncode().size());
-
- shared_ptr<Data> data2 = makeData("/a");
- cs.insert(*data2);
-
- shared_ptr<Data> data3 = makeData("/z");
- cs.insert(*data3);
-
- BOOST_CHECK_EQUAL(cs.size(), 3);
-
- name.appendImplicitSha256Digest(digest1);
- cs.erase(name);
- BOOST_CHECK_EQUAL(cs.size(), 2);
-}
-
-BOOST_AUTO_TEST_CASE(DigestCalculation)
-{
- shared_ptr<Data> data = makeData("/digest/compute");
-
- ndn::ConstBufferPtr digest1 = ndn::crypto::sha256(data->wireEncode().wire(),
- data->wireEncode().size());
- BOOST_CHECK_EQUAL(digest1->size(), 32);
-
- cs::Entry* entry = new cs::Entry();
- entry->setData(*data, false);
-
- BOOST_CHECK_EQUAL_COLLECTIONS(digest1->begin(), digest1->end(),
- entry->getFullName()[-1].value_begin(),
- entry->getFullName()[-1].value_end());
-}
-
-BOOST_AUTO_TEST_CASE(InsertCanonical)
-{
- Cs cs;
-
- shared_ptr<Data> data = makeData("/a");
- cs.insert(*data);
-
- shared_ptr<Data> data2 = makeData("/b");
- cs.insert(*data2);
-
- shared_ptr<Data> data3 = makeData("/c");
- cs.insert(*data3);
-
- shared_ptr<Data> data4 = makeData("/d");
- cs.insert(*data4);
-
- shared_ptr<Data> data5 = makeData("/c/c/1/2/3/4/5/6");
- cs.insert(*data5);
-
- shared_ptr<Data> data6 = makeData("/c/c/1/2/3");
- cs.insert(*data6);
-
- shared_ptr<Data> data7 = makeData("/c/c/1");
- cs.insert(*data7);
-}
-
-BOOST_AUTO_TEST_CASE(EraseCanonical)
-{
- Cs cs;
-
- shared_ptr<Data> data = makeData("/a");
- cs.insert(*data);
-
- shared_ptr<Data> data2 = makeData("/b");
- cs.insert(*data2);
-
- shared_ptr<Data> data3 = makeData("/c");
- cs.insert(*data3);
-
- shared_ptr<Data> data4 = makeData("/d");
- cs.insert(*data4);
-
- shared_ptr<Data> data5 = makeData("/c/c/1/2/3/4/5/6");
- cs.insert(*data5);
-
- shared_ptr<Data> data6 = makeData("/c/c/1/2/3");
- cs.insert(*data6);
-
- shared_ptr<Data> data7 = makeData("/c/c/1");
- cs.insert(*data7);
-
- ndn::ConstBufferPtr digest1 = ndn::crypto::sha256(data->wireEncode().wire(),
- data->wireEncode().size());
-
- Name name("/a");
- name.appendImplicitSha256Digest(digest1->buf(), digest1->size());
- cs.erase(name);
- BOOST_CHECK_EQUAL(cs.size(), 6);
-}
-
-BOOST_AUTO_TEST_CASE(ImplicitDigestSelector)
-{
- CsAccessor cs;
-
- Name name("/digest/works");
- shared_ptr<Data> data = makeData(name);
- cs.insert(*data);
-
- shared_ptr<Data> data2 = makeData("/a");
- cs.insert(*data2);
-
- shared_ptr<Data> data3 = makeData("/z/z/z");
- cs.insert(*data3);
-
- ndn::ConstBufferPtr digest1 = ndn::crypto::sha256(data->wireEncode().wire(),
- data->wireEncode().size());
- uint8_t digest2[32] = {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};
-
- shared_ptr<Interest> interest = make_shared<Interest>();
- interest->setName(Name(name).append(digest1->buf(), digest1->size()));
- interest->setMinSuffixComponents(0);
- interest->setMaxSuffixComponents(0);
-
- const Data* found = cs.find(*interest);
- BOOST_CHECK_NE(found, static_cast<const Data*>(0));
- BOOST_CHECK_EQUAL(found->getName(), name);
-
- shared_ptr<Interest> interest2 = make_shared<Interest>();
- interest2->setName(Name(name).append(digest2, 32));
- interest2->setMinSuffixComponents(0);
- interest2->setMaxSuffixComponents(0);
-
- const Data* notfound = cs.find(*interest2);
- BOOST_CHECK_EQUAL(notfound, static_cast<const Data*>(0));
-}
-
-BOOST_AUTO_TEST_CASE(ChildSelector)
-{
- Cs cs;
-
- shared_ptr<Data> data = makeData("/a");
- cs.insert(*data);
-
- shared_ptr<Data> data2 = makeData("/b");
- cs.insert(*data2);
-
- shared_ptr<Data> data4 = makeData("/d");
- cs.insert(*data4);
-
- shared_ptr<Data> data5 = makeData("/c/c");
- cs.insert(*data5);
-
- shared_ptr<Data> data6 = makeData("/c/f");
- cs.insert(*data6);
-
- shared_ptr<Data> data7 = makeData("/c/n");
- cs.insert(*data7);
-
- shared_ptr<Interest> interest = make_shared<Interest>("/c");
- interest->setChildSelector(1);
-
- const Data* found = cs.find(*interest);
- BOOST_CHECK_EQUAL(found->getName(), "/c/n");
-
- shared_ptr<Interest> interest2 = make_shared<Interest>("/c");
- interest2->setChildSelector(0);
-
- const Data* found2 = cs.find(*interest2);
- BOOST_CHECK_EQUAL(found2->getName(), "/c/c");
-}
-
-BOOST_AUTO_TEST_CASE(ChildSelector2)
-{
- Cs cs;
-
- shared_ptr<Data> data = makeData("/a/b/1");
- cs.insert(*data);
-
- shared_ptr<Data> data2 = makeData("/a/b/2");
- cs.insert(*data2);
-
- shared_ptr<Data> data3 = makeData("/a/z/1");
- cs.insert(*data3);
-
- shared_ptr<Data> data4 = makeData("/a/z/2");
- cs.insert(*data4);
-
- shared_ptr<Interest> interest = make_shared<Interest>("/a");
- interest->setChildSelector(1);
-
- const Data* found = cs.find(*interest);
- BOOST_CHECK_EQUAL(found->getName(), "/a/z/1");
-}
-
-BOOST_AUTO_TEST_CASE(MustBeFreshSelector)
-{
- Cs cs;
-
- Name name("/insert/nonfresh");
- shared_ptr<Data> data = makeData(name);
- data->setFreshnessPeriod(time::milliseconds(500));
- signData(data);
- cs.insert(*data);
-
- sleep(1);
-
- shared_ptr<Interest> interest = make_shared<Interest>(name);
- interest->setMustBeFresh(true);
-
- const Data* found = cs.find(*interest);
- BOOST_CHECK_EQUAL(found, static_cast<const Data*>(0));
-}
-
-BOOST_AUTO_TEST_CASE(PublisherKeySelector)
-{
- Cs cs;
-
- Name name("/insert/withkey");
- shared_ptr<Data> data = makeData(name);
- cs.insert(*data);
-
- shared_ptr<Interest> interest = make_shared<Interest>(name);
- Name keyName("/somewhere/key");
-
- ndn::KeyLocator locator(keyName);
- interest->setPublisherPublicKeyLocator(locator);
-
- const Data* found = cs.find(*interest);
- BOOST_CHECK_EQUAL(found, static_cast<const Data*>(0));
-}
-
-BOOST_AUTO_TEST_CASE(PublisherKeySelector2)
-{
- Cs cs;
- Name name("/insert/withkey");
- shared_ptr<Data> data = makeData(name);
- cs.insert(*data);
-
- Name name2("/insert/withkey2");
- shared_ptr<Data> data2 = make_shared<Data>(name2);
-
- Name keyName("/somewhere/key");
- const ndn::KeyLocator locator(keyName);
-
- ndn::SignatureSha256WithRsa fakeSignature;
- fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue,
- reinterpret_cast<const uint8_t*>(0), 0));
-
- fakeSignature.setKeyLocator(locator);
- data2->setSignature(fakeSignature);
- data2->wireEncode();
-
- cs.insert(*data2);
-
- shared_ptr<Interest> interest = make_shared<Interest>(name2);
- interest->setPublisherPublicKeyLocator(locator);
-
- const Data* found = cs.find(*interest);
- BOOST_CHECK_NE(found, static_cast<const Data*>(0));
- BOOST_CHECK_EQUAL(found->getName(), data2->getName());
-}
-
-
-/// @todo Expected failures, needs to be fixed as part of Issue #2118
-BOOST_AUTO_TEST_CASE_EXPECTED_FAILURES(MinMaxComponentsSelector, 1)
-BOOST_AUTO_TEST_CASE(MinMaxComponentsSelector)
-{
- Cs cs;
-
- shared_ptr<Data> data = makeData("/a");
- cs.insert(*data);
-
- shared_ptr<Data> data2 = makeData("/b");
- cs.insert(*data2);
-
- shared_ptr<Data> data4 = makeData("/d");
- cs.insert(*data4);
-
- shared_ptr<Data> data5 = makeData("/c/c/1/2/3/4/5/6");
- cs.insert(*data5);
-
- shared_ptr<Data> data6 = makeData("/c/c/6/7/8/9");
- cs.insert(*data6);
-
- shared_ptr<Data> data7 = makeData("/c/c/1/2/3");
- cs.insert(*data7);
-
- shared_ptr<Data> data8 = makeData("/c/c/1");
- cs.insert(*data8);
-
- shared_ptr<Interest> interest = make_shared<Interest>("/c/c");
- interest->setMinSuffixComponents(3);
- interest->setChildSelector(0);
-
- const Data* found = cs.find(*interest);
- BOOST_CHECK_EQUAL(found->getName(), "/c/c/1/2/3/4/5/6");
-
- shared_ptr<Interest> interest2 = make_shared<Interest>("/c/c");
- interest2->setMinSuffixComponents(4);
- interest2->setChildSelector(1);
-
- const Data* found2 = cs.find(*interest2);
- BOOST_CHECK_EQUAL(found2->getName(), "/c/c/6/7/8/9");
-
- shared_ptr<Interest> interest3 = make_shared<Interest>("/c/c");
- interest3->setMaxSuffixComponents(2);
- interest3->setChildSelector(1);
-
- const Data* found3 = cs.find(*interest3);
- BOOST_CHECK_EQUAL(found3->getName(), "/c/c/1");
-}
-
-BOOST_AUTO_TEST_CASE(ExcludeSelector)
-{
- Cs cs;
-
- shared_ptr<Data> data = makeData("/a");
- cs.insert(*data);
-
- shared_ptr<Data> data2 = makeData("/b");
- cs.insert(*data2);
-
- shared_ptr<Data> data3 = makeData("/c/a");
- cs.insert(*data3);
-
- shared_ptr<Data> data4 = makeData("/d");
- cs.insert(*data4);
-
- shared_ptr<Data> data5 = makeData("/c/c");
- cs.insert(*data5);
-
- shared_ptr<Data> data6 = makeData("/c/f");
- cs.insert(*data6);
-
- shared_ptr<Data> data7 = makeData("/c/n");
- cs.insert(*data7);
-
- shared_ptr<Interest> interest = make_shared<Interest>("/c");
- interest->setChildSelector(1);
- Exclude e;
- e.excludeOne (Name::Component("n"));
- interest->setExclude(e);
-
- const Data* found = cs.find(*interest);
- BOOST_CHECK_EQUAL(found->getName(), "/c/f");
-
- shared_ptr<Interest> interest2 = make_shared<Interest>("/c");
- interest2->setChildSelector(0);
-
- Exclude e2;
- e2.excludeOne (Name::Component("a"));
- interest2->setExclude(e2);
-
- const Data* found2 = cs.find(*interest2);
- BOOST_CHECK_EQUAL(found2->getName(), "/c/c");
-
- shared_ptr<Interest> interest3 = make_shared<Interest>("/c");
- interest3->setChildSelector(0);
-
- Exclude e3;
- e3.excludeOne (Name::Component("c"));
- interest3->setExclude(e3);
-
- const Data* found3 = cs.find(*interest3);
- BOOST_CHECK_EQUAL(found3->getName(), "/c/a");
-}
-
-//
-
class FindFixture : protected BaseFixture
{
protected:
- void
+ Name
insert(uint32_t id, const Name& name)
{
shared_ptr<Data> data = makeData(name);
data->setFreshnessPeriod(time::milliseconds(99999));
data->setContent(reinterpret_cast<const uint8_t*>(&id), sizeof(id));
- signData(data);
+ data->wireEncode();
m_cs.insert(*data);
+
+ return data->getFullName();
}
Interest&
@@ -659,8 +59,10 @@
uint32_t
find()
{
+ // m_cs.dump();
+
const Data* found = m_cs.find(*m_interest);
- if (found == 0) {
+ if (found == nullptr) {
return 0;
}
const Block& content = found->getContent();
@@ -693,6 +95,30 @@
BOOST_CHECK_EQUAL(find(), 1);
}
+BOOST_AUTO_TEST_CASE(ExactName)
+{
+ insert(1, "ndn:/");
+ insert(2, "ndn:/A");
+ insert(3, "ndn:/A/B");
+ insert(4, "ndn:/A/C");
+ insert(5, "ndn:/D");
+
+ startInterest("ndn:/A");
+ BOOST_CHECK_EQUAL(find(), 2);
+}
+
+BOOST_AUTO_TEST_CASE(FullName)
+{
+ Name n1 = insert(1, "ndn:/A");
+ Name n2 = insert(2, "ndn:/A");
+
+ startInterest(n1);
+ BOOST_CHECK_EQUAL(find(), 1);
+
+ startInterest(n2);
+ BOOST_CHECK_EQUAL(find(), 2);
+}
+
BOOST_AUTO_TEST_CASE(Leftmost)
{
insert(1, "ndn:/A");
@@ -720,126 +146,96 @@
BOOST_CHECK_EQUAL(find(), 4);
}
-/// @todo Expected failures, needs to be fixed as part of Issue #2118
-BOOST_AUTO_TEST_CASE_EXPECTED_FAILURES(Leftmost_ExactName1, 1)
-BOOST_AUTO_TEST_CASE(Leftmost_ExactName1)
-{
- insert(1, "ndn:/");
- insert(2, "ndn:/A/B");
- insert(3, "ndn:/A/C");
- insert(4, "ndn:/A");
- insert(5, "ndn:/D");
-
- // Intuitively you would think Data 4 should be between Data 1 and 2,
- // but Data 4 has full Name ndn:/A/<32-octet hash>.
- startInterest("ndn:/A");
- BOOST_CHECK_EQUAL(find(), 2);
-}
-
-BOOST_AUTO_TEST_CASE(Leftmost_ExactName33)
+BOOST_AUTO_TEST_CASE(MinSuffixComponents)
{
insert(1, "ndn:/");
insert(2, "ndn:/A");
- insert(3, "ndn:/A/BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"); // 33 'B's
- insert(4, "ndn:/A/CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"); // 33 'C's
- insert(5, "ndn:/D");
-
- // Data 2 is returned, because <32-octet hash> is less than Data 3.
- startInterest("ndn:/A");
- BOOST_CHECK_EQUAL(find(), 2);
-}
-
-/// @todo Expected failures, needs to be fixed as part of Issue #2118
-BOOST_AUTO_TEST_CASE_EXPECTED_FAILURES(MinSuffixComponents, 2)
-BOOST_AUTO_TEST_CASE(MinSuffixComponents)
-{
- insert(1, "ndn:/A/1/2/3/4");
- insert(2, "ndn:/B/1/2/3");
- insert(3, "ndn:/C/1/2");
- insert(4, "ndn:/D/1");
- insert(5, "ndn:/E");
- insert(6, "ndn:/");
+ insert(3, "ndn:/B/1");
+ insert(4, "ndn:/C/1/2");
+ insert(5, "ndn:/D/1/2/3");
+ insert(6, "ndn:/E/1/2/3/4");
startInterest("ndn:/")
- .setChildSelector(1)
.setMinSuffixComponents(0);
- BOOST_CHECK_EQUAL(find(), 6);
-
- startInterest("ndn:/")
- .setChildSelector(1)
- .setMinSuffixComponents(1);
- BOOST_CHECK_EQUAL(find(), 6);
-
- startInterest("ndn:/")
- .setChildSelector(1)
- .setMinSuffixComponents(2);
- BOOST_CHECK_EQUAL(find(), 5);
-
- startInterest("ndn:/")
- .setChildSelector(1)
- .setMinSuffixComponents(3);
- BOOST_CHECK_EQUAL(find(), 4);
-
- startInterest("ndn:/")
- .setChildSelector(1)
- .setMinSuffixComponents(4);
- BOOST_CHECK_EQUAL(find(), 3);
-
- startInterest("ndn:/")
- .setChildSelector(1)
- .setMinSuffixComponents(5);
- BOOST_CHECK_EQUAL(find(), 2);
-
- startInterest("ndn:/")
- .setChildSelector(1)
- .setMinSuffixComponents(6);
BOOST_CHECK_EQUAL(find(), 1);
startInterest("ndn:/")
- .setChildSelector(1)
+ .setMinSuffixComponents(1);
+ BOOST_CHECK_EQUAL(find(), 1);
+
+ startInterest("ndn:/")
+ .setMinSuffixComponents(2);
+ BOOST_CHECK_EQUAL(find(), 2);
+
+ startInterest("ndn:/")
+ .setMinSuffixComponents(3);
+ BOOST_CHECK_EQUAL(find(), 3);
+
+ startInterest("ndn:/")
+ .setMinSuffixComponents(4);
+ BOOST_CHECK_EQUAL(find(), 4);
+
+ startInterest("ndn:/")
+ .setMinSuffixComponents(5);
+ BOOST_CHECK_EQUAL(find(), 5);
+
+ startInterest("ndn:/")
+ .setMinSuffixComponents(6);
+ BOOST_CHECK_EQUAL(find(), 6);
+
+ startInterest("ndn:/")
.setMinSuffixComponents(7);
BOOST_CHECK_EQUAL(find(), 0);
}
-/// @todo Expected failures, needs to be fixed as part of Issue #2118
-BOOST_AUTO_TEST_CASE_EXPECTED_FAILURES(MaxSuffixComponents, 5)
BOOST_AUTO_TEST_CASE(MaxSuffixComponents)
{
insert(1, "ndn:/");
insert(2, "ndn:/A");
- insert(3, "ndn:/A/B");
- insert(4, "ndn:/A/B/C");
- insert(5, "ndn:/A/B/C/D");
- insert(6, "ndn:/A/B/C/D/E");
- // Order is 6,5,4,3,2,1, because <32-octet hash> is greater than a 1-octet component.
+ insert(3, "ndn:/B/2");
+ insert(4, "ndn:/C/2/3");
+ insert(5, "ndn:/D/2/3/4");
+ insert(6, "ndn:/E/2/3/4/5");
startInterest("ndn:/")
+ .setChildSelector(1)
.setMaxSuffixComponents(0);
BOOST_CHECK_EQUAL(find(), 0);
startInterest("ndn:/")
+ .setChildSelector(1)
.setMaxSuffixComponents(1);
BOOST_CHECK_EQUAL(find(), 1);
startInterest("ndn:/")
+ .setChildSelector(1)
.setMaxSuffixComponents(2);
BOOST_CHECK_EQUAL(find(), 2);
startInterest("ndn:/")
+ .setChildSelector(1)
.setMaxSuffixComponents(3);
BOOST_CHECK_EQUAL(find(), 3);
startInterest("ndn:/")
+ .setChildSelector(1)
.setMaxSuffixComponents(4);
BOOST_CHECK_EQUAL(find(), 4);
startInterest("ndn:/")
+ .setChildSelector(1)
.setMaxSuffixComponents(5);
BOOST_CHECK_EQUAL(find(), 5);
startInterest("ndn:/")
+ .setChildSelector(1)
.setMaxSuffixComponents(6);
BOOST_CHECK_EQUAL(find(), 6);
+
+ startInterest("ndn:/")
+ .setChildSelector(1)
+ .setMaxSuffixComponents(7);
+ BOOST_CHECK_EQUAL(find(), 6);
}
BOOST_AUTO_TEST_CASE(DigestOrder)
@@ -859,134 +255,149 @@
BOOST_CHECK_NE(leftmost, rightmost);
}
-/// @todo Expected failures, needs to be fixed as part of Issue #2118
-BOOST_AUTO_TEST_CASE_EXPECTED_FAILURES(DigestExclude, 1)
BOOST_AUTO_TEST_CASE(DigestExclude)
{
- insert(1, "ndn:/A/B");
- insert(2, "ndn:/A");
- insert(3, "ndn:/A/CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"); // 33 'C's
+ insert(1, "ndn:/A");
+ Name n2 = insert(2, "ndn:/A");
+ insert(3, "ndn:/A/B");
+
+ uint8_t digest00[ndn::crypto::SHA256_DIGEST_SIZE];
+ std::fill_n(digest00, sizeof(digest00), 0x00);
+ uint8_t digestFF[ndn::crypto::SHA256_DIGEST_SIZE];
+ std::fill_n(digestFF, sizeof(digestFF), 0xFF);
+
+ Exclude excludeDigest;
+ excludeDigest.excludeRange(
+ name::Component::fromImplicitSha256Digest(digest00, sizeof(digest00)),
+ name::Component::fromImplicitSha256Digest(digestFF, sizeof(digestFF)));
startInterest("ndn:/A")
- .setExclude(Exclude().excludeBefore(name::Component(reinterpret_cast<const uint8_t*>(
- "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF"
- "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF"), 31))); // 31 0xFF's
- BOOST_CHECK_EQUAL(find(), 2);
+ .setChildSelector(0)
+ .setExclude(excludeDigest);
+ BOOST_CHECK_EQUAL(find(), 3);
startInterest("ndn:/A")
.setChildSelector(1)
- .setExclude(Exclude().excludeAfter(name::Component(reinterpret_cast<const uint8_t*>(
- "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
- "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
- "\x00"), 33))); // 33 0x00's
- BOOST_CHECK_EQUAL(find(), 2);
-}
-
-BOOST_AUTO_TEST_CASE(ExactName32)
-{
- insert(1, "ndn:/A/BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"); // 32 'B's
- insert(2, "ndn:/A/CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"); // 32 'C's
-
- startInterest("ndn:/A/BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB");
- BOOST_CHECK_EQUAL(find(), 1);
-}
-
-/// @todo Expected failures, needs to be fixed as part of Issue #2118
-BOOST_AUTO_TEST_CASE_EXPECTED_FAILURES(MinSuffixComponents32, 2)
-BOOST_AUTO_TEST_CASE(MinSuffixComponents32)
-{
- insert(1, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/1/2/3/4"); // 32 'x's
- insert(2, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/B/1/2/3");
- insert(3, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/C/1/2");
- insert(4, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/D/1");
- insert(5, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/E");
- insert(6, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
-
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
- .setChildSelector(1)
- .setMinSuffixComponents(0);
- BOOST_CHECK_EQUAL(find(), 6);
-
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
- .setChildSelector(1)
- .setMinSuffixComponents(1);
- BOOST_CHECK_EQUAL(find(), 6);
-
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
- .setChildSelector(1)
- .setMinSuffixComponents(2);
- BOOST_CHECK_EQUAL(find(), 5);
-
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
- .setChildSelector(1)
- .setMinSuffixComponents(3);
- BOOST_CHECK_EQUAL(find(), 4);
-
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
- .setChildSelector(1)
- .setMinSuffixComponents(4);
+ .setExclude(excludeDigest);
BOOST_CHECK_EQUAL(find(), 3);
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
- .setChildSelector(1)
- .setMinSuffixComponents(5);
- BOOST_CHECK_EQUAL(find(), 2);
+ Exclude excludeGeneric;
+ excludeGeneric.excludeAfter(name::Component(static_cast<uint8_t*>(nullptr), 0));
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ startInterest("ndn:/A")
+ .setChildSelector(0)
+ .setExclude(excludeGeneric);
+ int found1 = find();
+ BOOST_CHECK(found1 == 1 || found1 == 2);
+
+ startInterest("ndn:/A")
.setChildSelector(1)
- .setMinSuffixComponents(6);
+ .setExclude(excludeGeneric);
+ int found2 = find();
+ BOOST_CHECK(found2 == 1 || found2 == 2);
+
+ Exclude exclude2 = excludeGeneric;
+ exclude2.excludeOne(n2.get(-1));
+
+ startInterest("ndn:/A")
+ .setChildSelector(0)
+ .setExclude(exclude2);
BOOST_CHECK_EQUAL(find(), 1);
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ startInterest("ndn:/A")
.setChildSelector(1)
- .setMinSuffixComponents(7);
- BOOST_CHECK_EQUAL(find(), 0);
+ .setExclude(exclude2);
+ BOOST_CHECK_EQUAL(find(), 1);
}
-/// @todo Expected failures, needs to be fixed as part of Issue #2118
-BOOST_AUTO_TEST_CASE_EXPECTED_FAILURES(MaxSuffixComponents32, 5)
-BOOST_AUTO_TEST_CASE(MaxSuffixComponents32)
+BOOST_AUTO_TEST_SUITE_END()
+
+BOOST_FIXTURE_TEST_CASE(Evict, UnitTestTimeFixture)
{
- insert(1, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/"); // 32 'x's
- insert(2, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A");
- insert(3, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/B");
- insert(4, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/B/C");
- insert(5, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/B/C/D");
- insert(6, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/B/C/D/E");
- // Order is 6,5,4,3,2,1, because <32-octet hash> is greater than a 1-octet component.
+ Cs cs(3);
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
- .setMaxSuffixComponents(0);
- BOOST_CHECK_EQUAL(find(), 0);
+ shared_ptr<Data> dataA = makeData("ndn:/A");
+ dataA->setFreshnessPeriod(time::milliseconds(99999));
+ dataA->wireEncode();
+ cs.insert(*dataA);
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
- .setMaxSuffixComponents(1);
- BOOST_CHECK_EQUAL(find(), 1);
+ shared_ptr<Data> dataB = makeData("ndn:/B");
+ dataB->setFreshnessPeriod(time::milliseconds(10));
+ dataB->wireEncode();
+ cs.insert(*dataB);
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
- .setMaxSuffixComponents(2);
- BOOST_CHECK_EQUAL(find(), 2);
+ shared_ptr<Data> dataC = makeData("ndn:/C");
+ dataC->setFreshnessPeriod(time::milliseconds(99999));
+ dataC->wireEncode();
+ cs.insert(*dataC, true);
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
- .setMaxSuffixComponents(3);
- BOOST_CHECK_EQUAL(find(), 3);
+ this->advanceClocks(time::milliseconds(11));
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
- .setMaxSuffixComponents(4);
- BOOST_CHECK_EQUAL(find(), 4);
+ // evict unsolicited
+ shared_ptr<Data> dataD = makeData("ndn:/D");
+ dataD->setFreshnessPeriod(time::milliseconds(99999));
+ dataD->wireEncode();
+ cs.insert(*dataD);
+ BOOST_CHECK_EQUAL(cs.size(), 3);
+ BOOST_CHECK(cs.find(Interest("ndn:/C")) == nullptr);
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
- .setMaxSuffixComponents(5);
- BOOST_CHECK_EQUAL(find(), 5);
+ // evict stale
+ shared_ptr<Data> dataE = makeData("ndn:/E");
+ dataE->setFreshnessPeriod(time::milliseconds(99999));
+ dataE->wireEncode();
+ cs.insert(*dataE);
+ BOOST_CHECK_EQUAL(cs.size(), 3);
+ BOOST_CHECK(cs.find(Interest("ndn:/B")) == nullptr);
- startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
- .setMaxSuffixComponents(6);
- BOOST_CHECK_EQUAL(find(), 6);
+ // evict fifo
+ shared_ptr<Data> dataF = makeData("ndn:/F");
+ dataF->setFreshnessPeriod(time::milliseconds(99999));
+ dataF->wireEncode();
+ cs.insert(*dataF);
+ BOOST_CHECK_EQUAL(cs.size(), 3);
+ BOOST_CHECK(cs.find(Interest("ndn:/A")) == nullptr);
}
-BOOST_AUTO_TEST_SUITE_END() // Find
+BOOST_FIXTURE_TEST_CASE(Refresh, UnitTestTimeFixture)
+{
+ Cs cs(3);
-BOOST_AUTO_TEST_SUITE_END() // TableCs
+ shared_ptr<Data> dataA = makeData("ndn:/A");
+ dataA->setFreshnessPeriod(time::milliseconds(99999));
+ dataA->wireEncode();
+ cs.insert(*dataA);
+
+ shared_ptr<Data> dataB = makeData("ndn:/B");
+ dataB->setFreshnessPeriod(time::milliseconds(10));
+ dataB->wireEncode();
+ cs.insert(*dataB);
+
+ shared_ptr<Data> dataC = makeData("ndn:/C");
+ dataC->setFreshnessPeriod(time::milliseconds(10));
+ dataC->wireEncode();
+ cs.insert(*dataC);
+
+ this->advanceClocks(time::milliseconds(11));
+
+ // refresh dataB
+ shared_ptr<Data> dataB2 = make_shared<Data>(*dataB);
+ dataB2->wireEncode();
+ cs.insert(*dataB2);
+ BOOST_CHECK_EQUAL(cs.size(), 3);
+ BOOST_CHECK(cs.find(Interest("ndn:/A")) != nullptr);
+ BOOST_CHECK(cs.find(Interest("ndn:/B")) != nullptr);
+ BOOST_CHECK(cs.find(Interest("ndn:/C")) != nullptr);
+
+ // evict dataC stale
+ shared_ptr<Data> dataD = makeData("ndn:/D");
+ dataD->setFreshnessPeriod(time::milliseconds(99999));
+ dataD->wireEncode();
+ cs.insert(*dataD);
+ BOOST_CHECK_EQUAL(cs.size(), 3);
+ BOOST_CHECK(cs.find(Interest("ndn:/C")) == nullptr);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
} // namespace tests
} // namespace nfd
diff --git a/tests/other/cs-smoketest.cpp b/tests/other/cs-smoketest.cpp
index 1fc97c9..415d03d 100644
--- a/tests/other/cs-smoketest.cpp
+++ b/tests/other/cs-smoketest.cpp
@@ -24,7 +24,6 @@
*/
#include "table/cs.hpp"
-#include "table/cs-entry.hpp"
#include <ndn-cxx/security/key-chain.hpp>
namespace nfd {