diff --git a/daemon/table/cs.cpp b/daemon/table/cs.cpp
index 2c1b657..e575694 100644
--- a/daemon/table/cs.cpp
+++ b/daemon/table/cs.cpp
@@ -349,14 +349,22 @@
 {
   NFD_LOG_TRACE("evictItem()");
 
-  if (!m_cleanupIndex.get<unsolicited>().empty() &&
-      (*m_cleanupIndex.get<unsolicited>().begin())->isUnsolicited())
-  {
-    NFD_LOG_TRACE("Evict from unsolicited queue");
+  if (!m_cleanupIndex.get<unsolicited>().empty()) {
+    CleanupIndex::index<unsolicited>::type::const_iterator firstSolicited =
+      m_cleanupIndex.get<unsolicited>().upper_bound(false);
 
-    eraseFromSkipList(*m_cleanupIndex.get<unsolicited>().begin());
-    m_cleanupIndex.get<unsolicited>().erase(m_cleanupIndex.get<unsolicited>().begin());
-    return true;
+    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() &&
diff --git a/daemon/table/cs.hpp b/daemon/table/cs.hpp
index 67cc611..f683a20 100644
--- a/daemon/table/cs.hpp
+++ b/daemon/table/cs.hpp
@@ -64,6 +64,15 @@
   {
     return entry1->isUnsolicited();
   }
+
+  bool
+  operator()(bool isUnsolicited, const cs::Entry* entry) const
+  {
+    if (isUnsolicited)
+      return true;
+    else
+      return !entry->isUnsolicited();
+  }
 };
 
 // tags