diff --git a/core/algorithm.hpp b/core/algorithm.hpp
new file mode 100644
index 0000000..5dc9dbb
--- /dev/null
+++ b/core/algorithm.hpp
@@ -0,0 +1,58 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015,  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.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * 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/>.
+ */
+
+#ifndef NFD_CORE_ALGORITHM_HPP
+#define NFD_CORE_ALGORITHM_HPP
+
+#include "common.hpp"
+#include <boost/concept/requires.hpp>
+
+namespace nfd {
+
+/** \brief finds the last element satisfying a predicate
+ *  \tparam It BidirectionalIterator
+ *  \tparam Pred UnaryPredicate
+ *
+ *  \return Iterator to the last element satisfying the condition,
+ *          or \p last if no such element is found.
+ *
+ *  Complexity: at most \p last-first invocations of \p p
+ */
+template<typename It, typename Pred>
+BOOST_CONCEPT_REQUIRES(
+  ((boost::BidirectionalIterator<It>))
+  ((boost::UnaryPredicate<Pred, typename std::iterator_traits<It>::value_type>)),
+  (It)
+)
+find_last_if(It first, It last, Pred p)
+{
+  std::reverse_iterator<It> firstR(first), lastR(last);
+  auto found = std::find_if(lastR, firstR, p);
+  return found == firstR ? last : std::prev(found.base());
+}
+
+} // namespace nfd
+
+#endif // NFD_CORE_ALGORITHM_HPP
diff --git a/daemon/table/cs-entry-impl.cpp b/daemon/table/cs-entry-impl.cpp
new file mode 100644
index 0000000..c97d692
--- /dev/null
+++ b/daemon/table/cs-entry-impl.cpp
@@ -0,0 +1,86 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015,  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.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * 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/>.
+ */
+
+#include "cs-entry-impl.hpp"
+
+namespace nfd {
+namespace cs {
+
+EntryImpl::EntryImpl(const Name& name)
+  : m_queryName(name)
+{
+  BOOST_ASSERT(this->isQuery());
+}
+
+EntryImpl::EntryImpl(shared_ptr<const Data> data, bool isUnsolicited)
+  : queueType(QUEUE_NONE)
+{
+  this->setData(data, isUnsolicited);
+  BOOST_ASSERT(!this->isQuery());
+}
+
+bool
+EntryImpl::isQuery() const
+{
+  return !this->hasData();
+}
+
+bool
+EntryImpl::canStale() const
+{
+  BOOST_ASSERT(!this->isQuery());
+  return this->getStaleTime() < time::steady_clock::TimePoint::max();
+}
+
+void
+EntryImpl::unsetUnsolicited()
+{
+  BOOST_ASSERT(!this->isQuery());
+  this->setData(this->getData(), false);
+}
+
+bool
+EntryImpl::operator<(const EntryImpl& other) const
+{
+  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
+} // namespace nfd
diff --git a/daemon/table/cs-entry-impl.hpp b/daemon/table/cs-entry-impl.hpp
new file mode 100644
index 0000000..0732047
--- /dev/null
+++ b/daemon/table/cs-entry-impl.hpp
@@ -0,0 +1,84 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015,  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.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * 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/>.
+ */
+
+#ifndef NFD_DAEMON_TABLE_CS_ENTRY_IMPL_HPP
+#define NFD_DAEMON_TABLE_CS_ENTRY_IMPL_HPP
+
+#include "cs-internal.hpp"
+#include "cs-entry.hpp"
+#include "core/scheduler.hpp"
+
+namespace nfd {
+namespace cs {
+
+/** \brief an Entry in ContentStore implementation
+ *
+ *  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.
+ *
+ *  \note This type is internal to this specific ContentStore implementation.
+ */
+class EntryImpl : public Entry
+{
+public:
+  /** \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
+   */
+  EntryImpl(const Name& name);
+
+  /** \brief construct Entry for storage
+   */
+  EntryImpl(shared_ptr<const Data> data, bool isUnsolicited);
+
+  /** \return true if entry can become stale, false if entry is never stale
+   */
+  bool
+  canStale() const;
+
+  void
+  unsetUnsolicited();
+
+  bool
+  operator<(const EntryImpl& other) const;
+
+private:
+  bool
+  isQuery() const;
+
+public:
+  QueueType queueType;
+  QueueIt queueIt;
+  scheduler::EventId moveStaleEvent;
+
+private:
+  Name m_queryName;
+};
+
+} // namespace cs
+} // namespace nfd
+
+#endif // NFD_DAEMON_TABLE_CS_ENTRY_IMPL_HPP
diff --git a/daemon/table/cs-entry.cpp b/daemon/table/cs-entry.cpp
index 7bb82ef..d4f3921 100644
--- a/daemon/table/cs-entry.cpp
+++ b/daemon/table/cs-entry.cpp
@@ -21,52 +21,62 @@
  *
  * 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");
-
-Entry::Entry()
-  : m_isUnsolicited(false)
-{
-}
-
 void
-Entry::setData(const Data& data, bool isUnsolicited)
+Entry::setData(shared_ptr<const Data> data, bool isUnsolicited)
 {
+  m_data = data;
   m_isUnsolicited = isUnsolicited;
-  m_dataPacket = data.shared_from_this();
 
   updateStaleTime();
 }
 
-void
-Entry::updateStaleTime()
-{
-  m_staleAt = time::steady_clock::now() + m_dataPacket->getFreshnessPeriod();
-}
-
 bool
 Entry::isStale() const
 {
-  return m_staleAt < time::steady_clock::now();
+  BOOST_ASSERT(this->hasData());
+  return m_staleTime < time::steady_clock::now();
+}
+
+void
+Entry::updateStaleTime()
+{
+  BOOST_ASSERT(this->hasData());
+  if (m_data->getFreshnessPeriod() >= time::milliseconds::zero()) {
+    m_staleTime = time::steady_clock::now() + time::milliseconds(m_data->getFreshnessPeriod());
+  }
+  else {
+    m_staleTime = time::steady_clock::TimePoint::max();
+  }
+}
+
+bool
+Entry::canSatisfy(const Interest& interest) const
+{
+  BOOST_ASSERT(this->hasData());
+  if (!interest.matchesData(*m_data)) {
+    return false;
+  }
+
+  if (interest.getMustBeFresh() == static_cast<int>(true) && this->isStale()) {
+    return false;
+  }
+
+  return true;
 }
 
 void
 Entry::reset()
 {
-  m_staleAt = time::steady_clock::TimePoint();
-  m_dataPacket.reset();
+  m_data.reset();
   m_isUnsolicited = false;
+  m_staleTime = time::steady_clock::TimePoint();
 }
 
 } // namespace cs
diff --git a/daemon/table/cs-entry.hpp b/daemon/table/cs-entry.hpp
index c61345f..fe7846c 100644
--- a/daemon/table/cs-entry.hpp
+++ b/daemon/table/cs-entry.hpp
@@ -21,10 +21,6 @@
  *
  * 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
@@ -35,108 +31,114 @@
 namespace nfd {
 namespace cs {
 
-class Entry;
-
 /** \brief represents a base class for CS entry
  */
-class Entry : noncopyable
+class Entry
 {
-public:
-  Entry();
-
-  /** \brief returns the name of the Data packet stored in the CS entry
-   *  \return{ NDN name }
-   */
-  const Name&
-  getName() const;
-
-  /** \brief returns the full name (including implicit digest) of the Data packet stored
-   *         in the CS entry
-   *  \return{ NDN name }
-   */
-  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  }
-   */
-  bool
-  isUnsolicited() const;
-
-  /** \brief returns the Data packet stored in the CS entry
+public: // exposed through ContentStore enumeration
+  /** \return the stored Data
+   *  \pre hasData()
    */
   const Data&
-  getData() const;
+  getData() const
+  {
+    BOOST_ASSERT(this->hasData());
+    return *m_data;
+  }
 
-  /** \brief changes the content of CS entry and recomputes digest
+  /** \return Name of the stored Data
+   *  \pre hasData()
    */
-  void
-  setData(const Data& data, bool isUnsolicited);
+  const Name&
+  getName() const
+  {
+    BOOST_ASSERT(this->hasData());
+    return m_data->getName();
+  }
 
-  /** \brief returns the absolute time when Data becomes expired
-   *  \return{ Time (resolution up to time::milliseconds) }
+  /** \return full name (including implicit digest) of the stored Data
+   *  \pre hasData()
+   */
+  const Name&
+  getFullName() const
+  {
+    BOOST_ASSERT(this->hasData());
+    return m_data->getFullName();
+  }
+
+  /** \return whether the stored Data is unsolicited
+   *  \pre hasData()
+   */
+  bool
+  isUnsolicited() const
+  {
+    BOOST_ASSERT(this->hasData());
+    return m_isUnsolicited;
+  }
+
+  /** \return the absolute time when the stored Data becomes expired
+   *  \retval time::steady_clock::TimePoint::max() if the stored Data never expires
+   *  \pre hasData()
    */
   const time::steady_clock::TimePoint&
-  getStaleTime() const;
+  getStaleTime() const
+  {
+    BOOST_ASSERT(this->hasData());
+    return m_staleTime;
+  }
 
-  /** \brief refreshes the time when Data becomes expired
-   *  according to the current absolute time.
-   */
-  void
-  updateStaleTime();
-
-  /** \brief checks if the stored Data is stale
+  /** \brief checks if the stored Data is stale now
+   *  \pre hasData()
    */
   bool
   isStale() const;
 
-  /** \brief clears CS entry
-   *  After reset, *this == Entry()
+  /** \brief determines whether Interest can be satisified by the stored Data
+   *  \note ChildSelector is not considered
+   *  \pre hasData()
+   */
+  bool
+  canSatisfy(const Interest& interest) const;
+
+public: // used by generic ContentStore implementation
+  /** \return true if a Data packet is stored
+   */
+  bool
+  hasData() const
+  {
+    return m_data != nullptr;
+  }
+
+  /** \brief replaces the stored Data
+   */
+  void
+  setData(shared_ptr<const Data> data, bool isUnsolicited);
+
+  /** \brief replaces the stored Data
+   */
+  void
+  setData(const Data& data, bool isUnsolicited)
+  {
+    this->setData(data.shared_from_this(), isUnsolicited);
+  }
+
+  /** \brief refreshes stale time relative to current time
+   */
+  void
+  updateStaleTime();
+
+  /** \brief clears the entry
+   *  \post !hasData()
    */
   void
   reset();
 
 private:
-  time::steady_clock::TimePoint m_staleAt;
-  shared_ptr<const Data> m_dataPacket;
-
+  shared_ptr<const Data> m_data;
   bool m_isUnsolicited;
+  time::steady_clock::TimePoint m_staleTime;
 };
 
-inline const Name&
-Entry::getName() const
-{
-  BOOST_ASSERT(m_dataPacket != nullptr);
-  return m_dataPacket->getName();
-}
-
-inline const Name&
-Entry::getFullName() const
-{
-  BOOST_ASSERT(m_dataPacket != nullptr);
-  return m_dataPacket->getFullName();
-}
-
-inline const Data&
-Entry::getData() const
-{
-  BOOST_ASSERT(m_dataPacket != nullptr);
-  return *m_dataPacket;
-}
-
-inline bool
-Entry::isUnsolicited() const
-{
-  return m_isUnsolicited;
-}
-
-inline const time::steady_clock::TimePoint&
-Entry::getStaleTime() const
-{
-  return m_staleAt;
-}
-
 } // namespace cs
 } // namespace nfd
 
diff --git a/daemon/table/cs-internal.hpp b/daemon/table/cs-internal.hpp
new file mode 100644
index 0000000..7df3d06
--- /dev/null
+++ b/daemon/table/cs-internal.hpp
@@ -0,0 +1,57 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015,  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.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * 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
+ *  \brief declares ContentStore internal types
+ */
+
+#ifndef NFD_DAEMON_TABLE_CS_INTERNAL_HPP
+#define NFD_DAEMON_TABLE_CS_INTERNAL_HPP
+
+#include "common.hpp"
+
+namespace nfd {
+namespace cs {
+
+class EntryImpl;
+
+typedef std::set<EntryImpl> Table;
+typedef Table::const_iterator TableIt;
+
+typedef std::list<TableIt> Queue;
+typedef Queue::iterator QueueIt;
+
+enum QueueType {
+  QUEUE_UNSOLICITED,
+  QUEUE_STALE,
+  QUEUE_FIFO,
+  QUEUE_MAX,
+  QUEUE_NONE = QUEUE_MAX
+};
+
+} // namespace cs
+} // namespace nfd
+
+#endif // NFD_DAEMON_TABLE_CS_INTERNAL_HPP
diff --git a/daemon/table/cs.cpp b/daemon/table/cs.cpp
index de543fe..e1e8e73 100644
--- a/daemon/table/cs.cpp
+++ b/daemon/table/cs.cpp
@@ -21,32 +21,17 @@
  *
  * 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 "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>
-#include <boost/concept/assert.hpp>
-#include <boost/concept_check.hpp>
-#include <type_traits>
-
-/// 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 "core/algorithm.hpp"
+#include <numeric>
 
 NFD_LOG_INIT("ContentStore");
 
 namespace nfd {
+namespace cs {
 
 // http://en.cppreference.com/w/cpp/concept/ForwardIterator
 BOOST_CONCEPT_ASSERT((boost::ForwardIterator<Cs::const_iterator>));
@@ -60,788 +45,216 @@
 #endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
 
 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::skip_list::Entry());
-}
-
-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
+  BOOST_ASSERT(nMaxPackets > 0);
 }
 
 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::skip_list::Entry());
-    }
-  }
-  else {
-    for (size_t i = oldNMaxPackets; i > m_nMaxPackets; i--) {
-      delete m_freeCsEntries.front();
-      m_freeCsEntries.pop();
-    }
-  }
-}
-
-size_t
-Cs::getLimit() const
-{
-  return m_nMaxPackets;
-}
-
-//Reference: "Skip Lists: A Probabilistic Alternative to Balanced Trees" by W.Pugh
-std::pair<cs::skip_list::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::skip_list::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);
+  BOOST_ASSERT(nMaxPackets > 0);
+  m_limit = nMaxPackets;
+  this->evict();
 }
 
 bool
 Cs::insert(const Data& data, bool isUnsolicited)
 {
-  NFD_LOG_TRACE("insert() " << data.getFullName());
+  NFD_LOG_DEBUG("insert " << data.getName());
 
-  if (isFull())
-    {
-      evictItem();
-    }
+  bool isNewEntry = false; TableIt it;
+  // use .insert because gcc46 does not support .emplace
+  std::tie(it, isNewEntry) = m_table.insert(EntryImpl(data.shared_from_this(), isUnsolicited));
+  EntryImpl& entry = const_cast<EntryImpl&>(*it);
 
-  //pointer and insertion status
-  std::pair<cs::skip_list::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.updateStaleTime();
+  this->attachQueue(it);
 
-bool
-Cs::isFull() const
-{
-  if (size() >= m_nMaxPackets) //size of the first layer vs. max size
-    return true;
+  // 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_MAX, 0U,
+      [] (size_t sum, const Queue queue) { return sum + queue.size(); }));
 
-  return false;
-}
+  this->evict(); // XXX The new entry could be evicted, but it shouldn't matter.
 
-bool
-Cs::eraseFromSkipList(cs::skip_list::Entry* entry)
-{
-  NFD_LOG_TRACE("eraseFromSkipList() "  << entry->getFullName());
-  NFD_LOG_TRACE("SkipList size " << size());
-
-  bool isErased = false;
-
-  const std::map<int, std::list<cs::skip_list::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::skip_list::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());
-    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 true;
 }
 
 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"));
 
-  bool isIterated = false;
-  SkipList::const_reverse_iterator topLayer = m_skipList.rbegin();
-  SkipListLayer::iterator head = (*topLayer)->begin();
+  TableIt first = m_table.lower_bound(prefix);
+  TableIt last = m_table.end();
+  if (prefix.size() > 0) {
+    last = m_table.lower_bound(prefix.getSuccessor());
+  }
 
-  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();
+  TableIt match = last;
+  if (isRightmost) {
+    match = this->findRightmost(interest, first, last);
+  }
+  else {
+    match = this->findLeftmost(interest, first, last);
+  }
 
-          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--;
-        }
-    }
-
-  return 0;
+  if (match == last) {
+    NFD_LOG_DEBUG("  no-match");
+    return nullptr;
+  }
+  NFD_LOG_DEBUG("  matching " << match->getName());
+  return &match->getData();
 }
 
-const Data*
-Cs::selectChild(const Interest& interest, SkipListLayer::iterator startingPoint) const
+TableIt
+Cs::findLeftmost(const Interest& interest, TableIt first, TableIt last) const
 {
-  BOOST_ASSERT(startingPoint != (*m_skipList.begin())->end());
-
-  if (startingPoint != (*m_skipList.begin())->begin())
-    {
-      BOOST_ASSERT((*startingPoint)->getFullName() < interest.getName());
-    }
-
-  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;
+  return std::find_if(first, last, bind(&cs::EntryImpl::canSatisfy, _1, interest));
 }
 
-bool
-Cs::doesComplyWithSelectors(const Interest& interest,
-                            cs::skip_list::Entry* entry,
-                            bool doesInterestContainDigest) const
+TableIt
+Cs::findRightmost(const Interest& interest, TableIt first, TableIt last) const
 {
-  NFD_LOG_TRACE("doesComplyWithSelectors()");
+  // Each loop visits a sub-namespace under a prefix one component longer than Interest Name.
+  // If there is a match in that sub-namespace, the leftmost match is returned;
+  // otherwise, loop continues.
 
-  /// \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)
+  size_t interestNameLength = interest.getName().size();
+  for (TableIt right = last; right != first;) {
+    TableIt prev = std::prev(right);
 
-  if (doesInterestContainDigest)
-    {
-      if (interest.getName().get(-1) != entry->getFullName().get(-1))
-        {
-          NFD_LOG_TRACE("violates implicit digest");
-          return false;
-        }
+    // special case: [first,prev] have exact Names
+    if (prev->getName().size() == interestNameLength) {
+      NFD_LOG_TRACE("  find-among-exact " << prev->getName());
+      TableIt matchExact = this->findRightmostAmongExact(interest, first, right);
+      return matchExact == right ? last : matchExact;
     }
 
-  if (!doesInterestContainDigest)
-    {
-      if (interest.getMinSuffixComponents() >= 0)
-        {
-          size_t minDataNameLength = interest.getName().size() + interest.getMinSuffixComponents();
+    Name prefix = prev->getName().getPrefix(interestNameLength + 1);
+    TableIt left = m_table.lower_bound(prefix);
 
-          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;
-            }
-        }
+    // normal case: [left,right) are under one-component-longer prefix
+    NFD_LOG_TRACE("  find-under-prefix " << prefix);
+    TableIt match = this->findLeftmost(interest, left, right);
+    if (match != right) {
+      return match;
     }
-
-  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;
+    right = left;
+  }
+  return last;
 }
 
-bool
-Cs::recognizeInterestWithDigest(const Interest& interest, cs::skip_list::Entry* entry) const
+TableIt
+Cs::findRightmostAmongExact(const Interest& interest, TableIt first, TableIt last) 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;
+  return find_last_if(first, last, bind(&EntryImpl::canSatisfy, _1, interest));
 }
 
 void
-Cs::erase(const Name& exactName)
+Cs::attachQueue(TableIt it)
 {
-  NFD_LOG_TRACE("insert() " << exactName << ", "
-                << "skipList size " << size());
+  EntryImpl& entry = const_cast<EntryImpl&>(*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))
-                {
-                  cs::skip_list::Entry* entryToDelete = *head;
-                  NFD_LOG_TRACE("Found target " << entryToDelete->getFullName());
-                  eraseFromSkipList(entryToDelete);
-                  // head can become invalid after eraseFromSkipList
-                  m_cleanupIndex.remove(entryToDelete);
-                  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)
-    {
-      cs::skip_list::Entry* entryToDelete = *head;
-      NFD_LOG_TRACE("Found target " << entryToDelete->getFullName());
-      eraseFromSkipList(entryToDelete);
-      // head can become invalid after eraseFromSkipList
-      m_cleanupIndex.remove(entryToDelete);
-    }
+  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--;
-    }
+  EntryImpl& entry = const_cast<EntryImpl&>(*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)
+{
+  EntryImpl& entry = const_cast<EntryImpl&>(*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<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->getName() << " " << reason);
+    this->detachQueue(it);
+    m_table.erase(it);
+  }
+}
+
+void
+Cs::dump()
+{
+  NFD_LOG_DEBUG("dump table");
+  for (const EntryImpl& 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 ae6fa79..77a4474 100644
--- a/daemon/table/cs.hpp
+++ b/daemon/table/cs.hpp
@@ -21,92 +21,40 @@
  *
  * 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-skip-list-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>
+#include "cs-entry-impl.hpp"
+#include <boost/iterator/transform_iterator.hpp>
 
 namespace nfd {
+namespace cs {
 
-typedef std::list<cs::skip_list::Entry*> SkipListLayer;
-typedef std::list<SkipListLayer*> SkipList;
-
-class StalenessComparator
-{
-public:
-  bool
-  operator()(const cs::skip_list::Entry* entry1, const cs::skip_list::Entry* entry2) const
-  {
-    return entry1->getStaleTime() < entry2->getStaleTime();
-  }
-};
-
-class UnsolicitedComparator
-{
-public:
-  bool
-  operator()(const cs::skip_list::Entry* entry1, const cs::skip_list::Entry* entry2) const
-  {
-    return entry1->isUnsolicited();
-  }
-
-  bool
-  operator()(bool isUnsolicited, const cs::skip_list::Entry* entry) const
-  {
-    if (isUnsolicited)
-      return true;
-    else
-      return !entry->isUnsolicited();
-  }
-};
-
-// tags
-class unsolicited;
-class byStaleness;
-class byArrival;
-
-typedef boost::multi_index_container<
-  cs::skip_list::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::skip_list::Entry*>,
-      StalenessComparator
-    >,
-
-    // unsolicited Data is in the front
-    boost::multi_index::ordered_non_unique<
-      boost::multi_index::tag<unsolicited>,
-      boost::multi_index::identity<cs::skip_list::Entry*>,
-      UnsolicitedComparator
-    >
-
-  >
-> CleanupIndex;
-
-/** \brief represents Content Store
+/** \brief represents the ContentStore
  */
 class Cs : noncopyable
 {
@@ -114,234 +62,133 @@
   explicit
   Cs(size_t nMaxPackets = 10);
 
-  ~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;
+  size() const
+  {
+    return m_table.size();
+  }
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+  void
+  dump();
 
 public: // enumeration
-  class const_iterator;
-
-  /** \brief returns an iterator pointing to the first CS entry
-   *  \note Iteration order is implementation-specific and is undefined
-   *  \note The returned iterator may get invalidated if CS is modified
-   */
-  const_iterator
-  begin() const;
-
-  /** \brief returns an iterator referring to the past-the-end CS entry
-   *  \note The returned iterator may get invalidated if CS is modified
-   */
-  const_iterator
-  end() const;
-
-  class const_iterator : public std::iterator<std::forward_iterator_tag, const cs::Entry>
+  struct EntryFromEntryImpl
   {
-  public:
-    const_iterator() = default;
+    typedef const Entry& result_type;
 
-    const_iterator(SkipListLayer::const_iterator it);
-
-    ~const_iterator();
-
-    reference
-    operator*() const;
-
-    pointer
-    operator->() const;
-
-    const_iterator&
-    operator++();
-
-    const_iterator
-    operator++(int);
-
-    bool
-    operator==(const const_iterator& other) const;
-
-    bool
-    operator!=(const const_iterator& other) const;
-
-  private:
-    SkipListLayer::const_iterator m_skipListIterator;
+    const Entry&
+    operator()(const EntryImpl& entry) const
+    {
+      return entry;
+    }
   };
 
-protected:
-  /** \brief removes one Data packet from Content Store based on replacement policy
-   *  \return{ whether the Data was removed }
+  /** \brief ContentStore iterator (public API)
    */
-  bool
-  evictItem();
+  typedef boost::transform_iterator<EntryFromEntryImpl, TableIt, const Entry&> const_iterator;
 
-private:
-  /** \brief returns True if the Content Store is at its maximum capacity
-   *  \return{ True if Content Store is full; otherwise False}
+  const_iterator
+  begin() const
+  {
+    return boost::make_transform_iterator(m_table.begin(), EntryFromEntryImpl());
+  }
+
+  const_iterator
+  end() const
+  {
+    return boost::make_transform_iterator(m_table.end(), EntryFromEntryImpl());
+  }
+
+private: // find
+  /** \brief find leftmost match in [first,last)
+   *  \return the leftmost match, or last if not found
    */
-  bool
-  isFull() const;
+  TableIt
+  findLeftmost(const Interest& interest, TableIt left, TableIt right) const;
 
-  /** \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}
+  /** \brief find rightmost match in [first,last)
+   *  \return the rightmost match, or last if not found
    */
-  size_t
-  pickRandomLayer() const;
+  TableIt
+  findRightmost(const Interest& interest, TableIt first, TableIt last) 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) }
+  /** \brief find rightmost match among entries with exact Names in [first,last)
+   *  \return the rightmost match, or last if not found
    */
-  std::pair<cs::skip_list::Entry*, bool>
-  insertToSkipList(const Data& data, bool isUnsolicited = false);
+  TableIt
+  findRightmostAmongExact(const Interest& interest, TableIt first, TableIt last) const;
 
-  /** \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::skip_list::Entry* entry);
-
-  /** \brief Prints contents of the skip list, starting from the top layer
+private: // cleanup
+  /** \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::skip_list::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::skip_list::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::skip_list::Entry*> m_freeCsEntries; // memory pool
+  size_t m_limit;
+  Table m_table;
+  Queue m_queues[QUEUE_MAX];
 };
 
-inline Cs::const_iterator
-Cs::begin() const
-{
-  return const_iterator(m_skipList.front()->begin());
-}
+} // namespace cs
 
-inline Cs::const_iterator
-Cs::end() const
-{
-  return const_iterator(m_skipList.front()->end());
-}
-
-inline
-Cs::const_iterator::const_iterator(SkipListLayer::const_iterator it)
-  : m_skipListIterator(it)
-{
-}
-
-inline
-Cs::const_iterator::~const_iterator()
-{
-}
-
-inline Cs::const_iterator&
-Cs::const_iterator::operator++()
-{
-  ++m_skipListIterator;
-  return *this;
-}
-
-inline Cs::const_iterator
-Cs::const_iterator::operator++(int)
-{
-  Cs::const_iterator temp(*this);
-  ++(*this);
-  return temp;
-}
-
-inline Cs::const_iterator::reference
-Cs::const_iterator::operator*() const
-{
-  return *(this->operator->());
-}
-
-inline Cs::const_iterator::pointer
-Cs::const_iterator::operator->() const
-{
-  return *m_skipListIterator;
-}
-
-inline bool
-Cs::const_iterator::operator==(const Cs::const_iterator& other) const
-{
-  return m_skipListIterator == other.m_skipListIterator;
-}
-
-inline bool
-Cs::const_iterator::operator!=(const Cs::const_iterator& other) const
-{
-  return !(*this == other);
-}
+using cs::Cs;
 
 } // namespace nfd
 
diff --git a/tests/core/algorithm.cpp b/tests/core/algorithm.cpp
new file mode 100644
index 0000000..941166d
--- /dev/null
+++ b/tests/core/algorithm.cpp
@@ -0,0 +1,62 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015,  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.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * 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/>.
+ */
+
+#include "core/algorithm.hpp"
+
+#include "tests/test-common.hpp"
+
+namespace nfd {
+namespace tests {
+
+BOOST_FIXTURE_TEST_SUITE(CoreAlgorithm, BaseFixture)
+
+BOOST_AUTO_TEST_CASE(FindLastIf)
+{
+  std::vector<int> vec{1, 2, 3, 4, 5, 6, 7, 8, 9};
+
+  int hit1 = 0;
+  std::vector<int>::const_iterator found1 = find_last_if(vec.begin(), vec.end(),
+      [&hit1] (int n) -> bool {
+        ++hit1;
+        return n % 2 == 0;
+      });
+  BOOST_REQUIRE(found1 != vec.end());
+  BOOST_CHECK_EQUAL(*found1, 8);
+  BOOST_CHECK_LE(hit1, vec.size());
+
+  int hit2 = 0;
+  std::vector<int>::const_iterator found2 = find_last_if(vec.begin(), vec.end(),
+      [&hit2] (int n) -> bool {
+        ++hit2;
+        return n < 0;
+      });
+  BOOST_CHECK(found2 == vec.end());
+  BOOST_CHECK_LE(hit2, vec.size());
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nfd
diff --git a/tests/daemon/table/cs.cpp b/tests/daemon/table/cs.cpp
index a09d4ed..e9efddf 100644
--- a/tests/daemon/table/cs.cpp
+++ b/tests/daemon/table/cs.cpp
@@ -21,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&
@@ -660,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();
@@ -694,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");
@@ -721,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)
@@ -860,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_CASE(Iterator)
+  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_CASE(Enumeration)
 {
   Cs cs;
 
@@ -1023,7 +433,7 @@
   BOOST_CHECK_EQUAL_COLLECTIONS(actual.begin(), actual.end(), expected.begin(), expected.end());
 }
 
-BOOST_AUTO_TEST_SUITE_END() // TableCs
+BOOST_AUTO_TEST_SUITE_END()
 
 } // namespace tests
 } // namespace nfd
diff --git a/tests/other/cs-benchmark.cpp b/tests/other/cs-benchmark.cpp
new file mode 100644
index 0000000..71c9e10
--- /dev/null
+++ b/tests/other/cs-benchmark.cpp
@@ -0,0 +1,213 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015,  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.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * 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/>.
+ */
+
+#include "table/cs.hpp"
+#include <ndn-cxx/security/key-chain.hpp>
+
+#include "tests/test-common.hpp"
+
+namespace nfd {
+namespace tests {
+
+class CsBenchmarkFixture : public BaseFixture
+{
+protected:
+  CsBenchmarkFixture()
+  {
+#ifdef _DEBUG
+    BOOST_TEST_MESSAGE("Benchmark compiled in debug mode is unreliable, "
+                       "please compile in release mode.");
+#endif // _DEBUG
+
+    cs.setLimit(CS_CAPACITY);
+  }
+
+  time::microseconds
+  timedRun(std::function<void()> f)
+  {
+    time::steady_clock::TimePoint t1 = time::steady_clock::now();
+    f();
+    time::steady_clock::TimePoint t2 = time::steady_clock::now();
+    return time::duration_cast<time::microseconds>(t2 - t1);
+  }
+
+protected:
+  typedef std::function<Name(size_t)> NameGenerator;
+
+  class SimpleNameGenerator
+  {
+  public:
+    explicit
+    SimpleNameGenerator(const Name& prefix = "/cs/benchmark")
+      : m_prefix(prefix)
+    {
+    }
+
+    Name
+    operator()(size_t i) const
+    {
+      Name name(m_prefix);
+      name.appendNumber(i % 4);
+      name.appendNumber(i);
+      return name;
+    }
+
+  private:
+    Name m_prefix;
+  };
+
+  std::vector<shared_ptr<Interest>>
+  makeInterestWorkload(size_t count, const NameGenerator& genName = SimpleNameGenerator())
+  {
+    std::vector<shared_ptr<Interest>> workload(count);
+    for (size_t i = 0; i < count; ++i) {
+      Name name = genName(i);
+      workload[i] = makeInterest(name);
+    }
+    return workload;
+  }
+
+  std::vector<shared_ptr<Data>>
+  makeDataWorkload(size_t count, const NameGenerator& genName = SimpleNameGenerator())
+  {
+    std::vector<shared_ptr<Data>> workload(count);
+    for (size_t i = 0; i < count; ++i) {
+      Name name = genName(i);
+      workload[i] = makeData(name);
+    }
+    return workload;
+  }
+
+protected:
+  Cs cs;
+  static const size_t CS_CAPACITY = 50000;
+};
+
+BOOST_FIXTURE_TEST_SUITE(TableCsBenchmark, CsBenchmarkFixture)
+
+// find miss, then insert
+BOOST_AUTO_TEST_CASE(FindMissInsert)
+{
+  std::vector<shared_ptr<Interest>> interestWorkload = makeInterestWorkload(CS_CAPACITY);
+  const size_t REPEAT = 4;
+  std::vector<shared_ptr<Data>> dataWorkload[REPEAT];
+  for (size_t j = 0; j < REPEAT; ++j) {
+    dataWorkload[j] = makeDataWorkload(CS_CAPACITY);
+  }
+
+  time::microseconds d = timedRun([&] {
+    for (size_t j = 0; j < REPEAT; ++j) {
+      for (size_t i = 0; i < CS_CAPACITY; ++i) {
+        cs.find(*interestWorkload[i]);
+        cs.insert(*dataWorkload[j][i], false);
+      }
+    }
+  });
+  BOOST_TEST_MESSAGE("find(miss)-insert " << (CS_CAPACITY * REPEAT) << ": " << d);
+}
+
+// insert, then find hit
+BOOST_AUTO_TEST_CASE(InsertFindHit)
+{
+  std::vector<shared_ptr<Interest>> interestWorkload = makeInterestWorkload(CS_CAPACITY);
+  const size_t REPEAT = 4;
+  std::vector<shared_ptr<Data>> dataWorkload[REPEAT];
+  for (size_t j = 0; j < REPEAT; ++j) {
+    dataWorkload[j] = makeDataWorkload(CS_CAPACITY);
+  }
+
+  time::microseconds d = timedRun([&] {
+    for (size_t j = 0; j < REPEAT; ++j) {
+      for (size_t i = 0; i < CS_CAPACITY; ++i) {
+        cs.insert(*dataWorkload[j][i], false);
+        cs.find(*interestWorkload[i]);
+      }
+    }
+  });
+  BOOST_TEST_MESSAGE("insert-find(hit) " << (CS_CAPACITY * REPEAT) << ": " << d);
+}
+
+// find(leftmost) hit
+BOOST_AUTO_TEST_CASE(Leftmost)
+{
+  const size_t N_CHILDREN = 10;
+  const size_t N_INTERESTS = CS_CAPACITY / N_CHILDREN;
+  std::vector<shared_ptr<Interest>> interestWorkload = makeInterestWorkload(N_INTERESTS);
+  for (auto&& interest : interestWorkload) {
+    interest->setChildSelector(0);
+    for (size_t j = 0; j < N_CHILDREN; ++j) {
+      Name name = interest->getName();
+      name.appendNumber(j);
+      shared_ptr<Data> data = makeData(name);
+      cs.insert(*data, false);
+    }
+  }
+  BOOST_REQUIRE(cs.size() == N_INTERESTS * N_CHILDREN);
+
+  const size_t REPEAT = 4;
+
+  time::microseconds d = timedRun([&] {
+    for (size_t j = 0; j < REPEAT; ++j) {
+      for (const auto& interest : interestWorkload) {
+        cs.find(*interest);
+      }
+    }
+  });
+  BOOST_TEST_MESSAGE("find(leftmost) " << (N_INTERESTS * N_CHILDREN * REPEAT) << ": " << d);
+}
+
+// find(rightmost) hit
+BOOST_AUTO_TEST_CASE(Rightmost)
+{
+  const size_t N_CHILDREN = 10;
+  const size_t N_INTERESTS = CS_CAPACITY / N_CHILDREN;
+  std::vector<shared_ptr<Interest>> interestWorkload = makeInterestWorkload(N_INTERESTS);
+  for (auto&& interest : interestWorkload) {
+    interest->setChildSelector(1);
+    for (size_t j = 0; j < N_CHILDREN; ++j) {
+      Name name = interest->getName();
+      name.appendNumber(j);
+      shared_ptr<Data> data = makeData(name);
+      cs.insert(*data, false);
+    }
+  }
+  BOOST_REQUIRE(cs.size() == N_INTERESTS * N_CHILDREN);
+
+  const size_t REPEAT = 4;
+
+  time::microseconds d = timedRun([&] {
+    for (size_t j = 0; j < REPEAT; ++j) {
+      for (const auto& interest : interestWorkload) {
+        cs.find(*interest);
+      }
+    }
+  });
+  BOOST_TEST_MESSAGE("find(rightmost) " << (N_INTERESTS * N_CHILDREN * REPEAT) << ": " << d);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nfd
diff --git a/tests/other/cs-smoketest.cpp b/tests/other/cs-smoketest.cpp
deleted file mode 100644
index 1fc97c9..0000000
--- a/tests/other/cs-smoketest.cpp
+++ /dev/null
@@ -1,111 +0,0 @@
-/* -*- 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,
- *                      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.
- *
- * NFD is free software: you can redistribute it and/or modify it under the terms
- * of the GNU General Public License as published by the Free Software Foundation,
- * either version 3 of the License, or (at your option) any later version.
- *
- * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
- * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
- * PURPOSE.  See the GNU General Public License for more details.
- *
- * 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/>.
- */
-
-#include "table/cs.hpp"
-#include "table/cs-entry.hpp"
-#include <ndn-cxx/security/key-chain.hpp>
-
-namespace nfd {
-namespace cs_smoketest {
-
-static void
-runStressTest()
-{
-  shared_ptr<Data> dataWorkload[70000];
-  shared_ptr<Interest> interestWorkload[70000];
-
-  ndn::SignatureSha256WithRsa fakeSignature;
-  fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue,
-                                        reinterpret_cast<const uint8_t*>(0), 0));
-
-  // 182 MB in memory
-  for (int i = 0; i < 70000; i++) {
-    Name name("/stress/test");
-    name.appendNumber(i % 4);
-    name.appendNumber(i);
-
-    shared_ptr<Interest> interest = make_shared<Interest>(name);
-    interestWorkload[i] = interest;
-
-    shared_ptr<Data> data = make_shared<Data>(name);
-    data->setSignature(fakeSignature);
-    dataWorkload[i] = data;
-  }
-
-  time::duration<double, boost::nano> previousResult(0);
-
-  for (size_t nInsertions = 1000; nInsertions < 10000000; nInsertions *= 2) {
-    Cs cs;
-    srand(time::toUnixTimestamp(time::system_clock::now()).count());
-
-    time::steady_clock::TimePoint startTime = time::steady_clock::now();
-
-    size_t workloadCounter = 0;
-    for (size_t i = 0; i < nInsertions; i++) {
-      if (workloadCounter > 69999)
-        workloadCounter = 0;
-
-      cs.find(*interestWorkload[workloadCounter]);
-      Data& data = *dataWorkload[workloadCounter];
-      data.setName(data.getName()); // reset data.m_fullName
-      data.wireEncode();
-      cs.insert(data);
-
-      workloadCounter++;
-    }
-
-    time::steady_clock::TimePoint endTime = time::steady_clock::now();
-
-    time::duration<double, boost::nano> runDuration = endTime - startTime;
-    time::duration<double, boost::nano> perOperationTime = runDuration / nInsertions;
-
-    std::cout << "nItem = " << nInsertions << std::endl;
-    std::cout << "Total running time = "
-              << time::duration_cast<time::duration<double> >(runDuration)
-              << std::endl;
-    std::cout << "Average per-operation time = "
-              << time::duration_cast<time::duration<double, boost::micro> >(perOperationTime)
-              << std::endl;
-
-    if (previousResult > time::nanoseconds(1))
-      std::cout << "Change compared to the previous: "
-                << (100.0 * perOperationTime / previousResult) << "%" << std::endl;
-
-    std::cout << "\n=================================\n" << std::endl;
-
-    previousResult = perOperationTime;
-  }
-}
-
-} // namespace cs_smoketest
-} // namespace nfd
-
-int
-main(int argc, char** argv)
-{
-  nfd::cs_smoketest::runStressTest();
-
-  return 0;
-}
diff --git a/tests/other/wscript b/tests/other/wscript
index 69aa2bb..51f8b6b 100644
--- a/tests/other/wscript
+++ b/tests/other/wscript
@@ -1,12 +1,13 @@
 # -*- Mode: python; py-indent-offset: 4; indent-tabs-mode: nil; coding: utf-8; -*-
 
 """
-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-2015,  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.
@@ -26,8 +27,8 @@
 top = '../..'
 
 def build(bld):
-    bld.program(target="../../cs-smoketest",
-                source="cs-smoketest.cpp",
-                use='daemon-objects',
+    bld.program(target="../../cs-benchmark",
+                source="cs-benchmark.cpp",
+                use='daemon-objects unit-tests-main',
                 install_path=None,
                 )