storage: switch index data structure from skiplist to std::set
test performance of skiplist and std::set
Change-Id: I0aa7f34e57f17a83b96fed3885d6cc6f59ad52dd
diff --git a/tests/other/skiplist-list.hpp b/tests/other/skiplist-list.hpp
new file mode 100644
index 0000000..72d1dda
--- /dev/null
+++ b/tests/other/skiplist-list.hpp
@@ -0,0 +1,478 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+* Copyright (c) 2014, Regents of the University of California.
+*
+* This file is part of NDN repo-ng (Next generation of NDN repository).
+* See AUTHORS.md for complete list of repo-ng authors and contributors.
+*
+* repo-ng 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.
+*
+* repo-ng 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
+* repo-ng, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#ifndef REPO_TESTS_OTHER_SKIPLIST_LIST_HPP
+#define REPO_TESTS_OTHER_SKIPLIST_LIST_HPP
+#include "common.hpp"
+
+namespace update1 {
+
+class SkipList32Levels25Probabilty
+{
+public:
+ static size_t
+ getMaxLevels()
+ {
+ return 32;
+ }
+
+ static double
+ getProbability()
+ {
+ return 0.25; // 25%
+ }
+};
+
+template<typename T>
+struct SkipListNode
+{
+ typedef SkipListNode<T>* SkipListNodePointer;
+ T data;
+ std::list<SkipListNodePointer> prevs;
+ std::list<SkipListNodePointer> nexts;
+};
+
+template<typename T, class Ref, class Ptr>
+class SkipListIterator : public std::iterator<std::bidirectional_iterator_tag, T>
+{
+public:
+ typedef SkipListNode<T>* NodePointer;
+ NodePointer node;
+
+ typedef SkipListIterator<T, Ref, Ptr> Self;
+ typedef T value_type;
+ typedef Ptr pointer;
+ typedef Ref reference;
+ typedef ptrdiff_t difference_type;
+ typedef SkipListIterator<T, const T&, const T*> const_iterator;
+ /// alias of const_iterator
+ typedef const_iterator iterator;
+
+public:
+ // constructor
+ SkipListIterator()
+ {
+ }
+
+ explicit
+ SkipListIterator(NodePointer x)
+ : node(x)
+ {
+ }
+
+ SkipListIterator(const SkipListIterator& x)
+ : node(x.node)
+ {
+ }
+
+ bool
+ operator==(const const_iterator& x) const
+ {
+ return node == x.node;
+ }
+
+ bool
+ operator!=(const const_iterator& x) const
+ {
+ return node != x.node;
+ }
+
+ reference
+ operator*() const
+ {
+ return (*node).data;
+ }
+
+ pointer
+ operator->() const
+ {
+ return &(operator*());
+ }
+
+ Self&
+ operator++()
+ {
+ node = node->nexts.front();
+ return *this;
+ }
+
+ Self
+ operator++(int)
+ {
+ Self tmp = *this;
+ ++*this;
+ return tmp;
+ }
+
+ Self&
+ operator--()
+ {
+ node = node->prevs.front();
+ return *this;
+ }
+
+ Self
+ operator--(int)
+ {
+ Self tmp = *this;
+ --*this;
+ return tmp;
+ }
+};
+
+/*
+ * @brief SkipList
+ *
+ * Examples of internal structure:
+ * "A <-i-> B" means A->nexts[i] = B and B->prevs[i] = A
+ *
+ * case 1: an empty skip list
+ * m_head <-0-> m_head
+ *
+ * case 2: a skip list with only one level and only one node
+ * m_head <-0-> A <-0-> m_head
+ *
+ * case 3: a skip list with three nodes, node A and B appear on one level,
+ * node C appears on two levels
+ * m_head <-1-> C <-1-> m_head
+ * m_head <-0-> A <-0-> B <-0-> C <-0-> m_head
+ */
+
+template<typename T, typename Compare = std::less<T>,
+ typename Traits = SkipList32Levels25Probabilty>
+class SkipList
+{
+public:
+ typedef T value_type;
+ typedef value_type* pointer;
+ typedef const value_type* const_pointer;
+ typedef value_type& reference;
+ typedef const value_type& const_reference;
+ typedef SkipListNode<T> Node;
+ typedef Node* NodePointer;
+ typedef size_t size_type;
+ typedef ptrdiff_t difference_type;
+ typedef SkipListIterator<T, const T&, const T*> const_iterator;
+ /// alias of const_iterator
+ typedef const_iterator iterator;
+ typedef SkipListNode<T>* SkipListNodePointer;
+
+public:
+ explicit
+ SkipList()
+ {
+ initializeHead();
+ }
+
+ ~SkipList()
+ {
+ clear();
+ delete(m_head);
+ }
+
+ const_iterator
+ begin() const
+ {
+ return const_iterator(*(*m_head).nexts.begin());
+ }
+
+ const_iterator
+ end() const
+ {
+ return const_iterator(m_head);
+ }
+
+ bool
+ empty() const
+ {
+ return *(m_head->nexts.begin()) == m_head;
+ }
+
+ size_t
+ size() const
+ {
+ return m_size;
+ }
+
+ const_iterator
+ lower_bound(const T& x) const;
+
+ const_iterator
+ find(const T& x) const;
+
+ std::pair<const_iterator, bool>
+ insert(const T& x);
+
+ const_iterator
+ erase(const_iterator it);
+
+protected:
+
+ /*
+ * @brief initialize the node
+ */
+ NodePointer
+ createNode()
+ {
+ NodePointer p = new Node;
+ return p;
+ }
+
+ /*
+ * @brief initialize the node with given value
+ * @para to be set to the value of node
+ */
+ NodePointer
+ createNode(const T& x)
+ {
+ NodePointer p = new Node;
+ m_dataAllocator.construct(&(p->data), x);
+ return p;
+ }
+
+ /*
+ * @brief destructror of the node
+ * @para given pointer of node to be destructed
+ */
+ void
+ destroyNode(NodePointer p)
+ {
+ delete(p);
+ }
+
+ /*
+ * @brief initialize the head
+ */
+ void
+ initializeHead()
+ {
+ m_head = createNode();
+ m_head->prevs.push_back(m_head);
+ m_head->nexts.push_back(m_head);
+ m_size = 0;
+ }
+
+ /*
+ * @brief destroy all the nodes of skiplist except the head
+ */
+ void
+ clear()
+ {
+ NodePointer cur = m_head->nexts.front();
+ while (cur != m_head) {
+ NodePointer tmp = cur;
+ cur = cur->nexts.front();
+ destroyNode(tmp);
+ }
+ m_head->nexts.front() = m_head;
+ m_head->prevs.front() = m_head;
+ }
+
+ /*
+ * @brief pick a random height for inserted skiplist entry
+ */
+ size_t
+ pickRandomLevel() const
+ {
+ static boost::random::mt19937 gen;
+ static boost::random::geometric_distribution<size_t> dist(Traits::getProbability());
+ return std::min(dist(gen), Traits::getMaxLevels());
+ }
+
+protected:
+ NodePointer m_head;
+ std::allocator<T> m_dataAllocator;
+ Compare m_compare;
+ size_t m_size;
+};
+
+
+template<typename T, typename Compare, typename Traits>
+typename SkipList<T, Compare, Traits>::const_iterator
+SkipList<T, Compare, Traits>::lower_bound(const T& x) const
+{
+ size_t nLevels = m_head->nexts.size();
+ NodePointer p = m_head;
+ NodePointer q = p->nexts.back();
+ for (int i = nLevels - 1; i >= 0; --i) {
+ typename std::list<SkipListNodePointer>::iterator it_p = p->nexts.begin();
+ for (int j = 0; j < i; j++) {
+ it_p++;
+ }
+ q = *it_p;
+ if (q != m_head) {
+ while (m_compare(q->data, x)) {
+ p = *it_p;
+ it_p = p->nexts.begin();
+ for (int j = 0; j < i; j++) {
+ it_p++;
+ }
+ q = *it_p;
+ if (q == m_head) {
+ break;
+ }
+ }
+ }
+ }
+ return const_iterator(q);
+}
+
+template<typename T, typename Compare, typename Traits>
+typename SkipList<T, Compare, Traits>::const_iterator
+SkipList<T, Compare, Traits>::find(const T& x) const
+{
+ const_iterator it = this->lower_bound(x);
+ if (it == this->end() || *it != x)
+ return this->end();
+ return it;
+}
+
+template<typename T, typename Compare, typename Traits>
+std::pair<typename SkipList<T, Compare, Traits>::const_iterator, bool>
+SkipList<T, Compare, Traits>::insert(const T& x)
+{
+ size_t nLevels = m_head->nexts.size();
+ // 1. find insert position
+ std::vector<NodePointer> insertPositions(nLevels);
+ NodePointer p = m_head;
+ NodePointer q = p->nexts.back();
+ for (int i = nLevels - 1; i >= 0; --i) {
+ typename std::list<SkipListNodePointer>::iterator it_p = p->nexts.begin();
+ for (int j = 0; j < i; j++) {
+ it_p++;
+ }
+ q = *it_p;
+ if (q != m_head) {
+ while (m_compare(q->data, x)) {
+ p = *it_p;
+ it_p = p->nexts.begin();
+ for (int j = 0; j < i; j++) {
+ it_p++;
+ }
+ q = *it_p;
+ if (q == m_head) {
+ break;
+ }
+ }
+ }
+ insertPositions[i] = p;
+ }
+ // 2. whether q->data == x?
+ if (q != m_head)
+ if (!m_compare(q->data, x) && !m_compare(x, q->data)) {
+ return std::pair<const_iterator, bool>(const_iterator(q), false);
+ }
+ // 3. construct new node;
+ NodePointer newNode = createNode(x);
+ // 4. pick random nLevels
+ size_t newLevel = pickRandomLevel();
+ // 5. insert the new node
+ newNode->nexts.resize(newLevel + 1);
+ newNode->prevs.resize(newLevel + 1);
+ if (newLevel > nLevels - 1) {
+ m_head->nexts.resize(newLevel + 1, m_head);
+ m_head->prevs.resize(newLevel + 1, m_head);
+ insertPositions.resize(newLevel + 1, m_head);
+ }
+ for (size_t i = 0; i <= newLevel; i++) {
+ typename std::list<SkipListNodePointer>::iterator it_newNode_next = newNode->nexts.begin();
+ for (size_t j = 0; j < i; j++) {
+ it_newNode_next++;
+ }
+ typename std::list<SkipListNodePointer>::iterator it_insert_next = insertPositions[i]->nexts.begin();
+ for (size_t j = 0; j < i; j++) {
+ it_insert_next++;
+ }
+ *it_newNode_next = *it_insert_next;
+
+ typename std::list<SkipListNodePointer>::iterator it_newNode_prev = newNode->prevs.begin();
+ for (size_t j = 0; j < i; j++) {
+ it_newNode_prev++;
+ }
+ *it_newNode_prev = insertPositions[i];
+
+ it_insert_next = insertPositions[i]->nexts.begin();
+ for (size_t j = 0; j < i; j++) {
+ it_insert_next++;
+ }
+ *it_insert_next = newNode;
+ it_newNode_next = newNode->nexts.begin();
+ for (size_t j = 0; j < i; j++) {
+ it_newNode_next++;
+ }
+ typename std::list<SkipListNodePointer>::iterator it_newNode_next_prev = (*it_newNode_next)->prevs.begin();
+ for (size_t j = 0; j < i; j++) {
+ it_newNode_next_prev++;
+ }
+ *it_newNode_next_prev = newNode;
+ }
+
+ ++m_size;
+ return std::pair<const_iterator, bool>(const_iterator(newNode), true);
+}
+
+template<typename T, typename Compare, typename Traits>
+typename SkipList<T, Compare, Traits>::const_iterator
+SkipList<T, Compare, Traits>::erase(typename SkipList<T, Compare, Traits>::const_iterator it)
+{
+ NodePointer eraseNode = it.node;
+ if (!empty() && eraseNode != m_head) {
+ NodePointer returnNode = eraseNode->nexts.front();
+ size_t nLevels = eraseNode->nexts.size();
+ for (int i = nLevels - 1; i >= 0; --i) {
+ typename std::list<SkipListNodePointer>::iterator it_erase_next = eraseNode->nexts.begin();
+ for (int j = 0; j < i; j++) {
+ it_erase_next++;
+ }
+
+ typename std::list<SkipListNodePointer>::iterator it_erase_next_prev = (*it_erase_next)->prevs.begin();
+ for (int j = 0; j < i; j++) {
+ it_erase_next_prev++;
+ }
+
+ typename std::list<SkipListNodePointer>::iterator it_erase_prev = eraseNode->prevs.begin();
+ for (int j = 0; j < i; j++) {
+ it_erase_prev++;
+ }
+ *it_erase_next_prev = *it_erase_prev;
+
+ typename std::list<SkipListNodePointer>::iterator it_erase_prev_next = (*it_erase_prev)->nexts.begin();
+ for (int j = 0; j < i; j++) {
+ it_erase_prev_next++;
+ }
+
+ *it_erase_prev_next = *it_erase_next;
+ // clear empty nLevels
+ if ((*it_erase_next == *it_erase_prev) && i > 0) {
+ m_head->nexts.pop_back();
+ m_head->prevs.pop_back();
+ }
+ }
+ destroyNode(eraseNode);
+ --m_size;
+ return const_iterator(returnNode);
+ }
+ else {
+ return end();
+ }
+}
+
+} //end namespace update1
+
+#endif // REPO_TESTS_UNIT_SKIPLIST_LIST_HPP
diff --git a/tests/other/skiplist-prev.hpp b/tests/other/skiplist-prev.hpp
new file mode 100644
index 0000000..1bb416d
--- /dev/null
+++ b/tests/other/skiplist-prev.hpp
@@ -0,0 +1,439 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+* Copyright (c) 2014, Regents of the University of California.
+*
+* This file is part of NDN repo-ng (Next generation of NDN repository).
+* See AUTHORS.md for complete list of repo-ng authors and contributors.
+*
+* repo-ng 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.
+*
+* repo-ng 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
+* repo-ng, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#ifndef REPO_TESTS_OTHER_SKIPLIST_PREV_HPP
+#define REPO_TESTS_OTHER_SKIPLIST_PREV_HPP
+
+#include "common.hpp"
+
+namespace prev {
+
+class SkipList32Levels25Probabilty
+{
+public:
+ static size_t
+ getMaxLevels()
+ {
+ return 32;
+ }
+
+ static double
+ getProbability()
+ {
+ return 0.25; // 25%
+ }
+};
+
+template<typename T>
+struct SkipListNode
+{
+ typedef SkipListNode<T>* SkipListNodePointer;
+ T data;
+ std::vector<SkipListNodePointer> prevs;
+ std::vector<SkipListNodePointer> nexts;
+};
+
+template<typename T, class Ref, class Ptr>
+class SkipListIterator : public std::iterator<std::bidirectional_iterator_tag, T>
+{
+public:
+ typedef SkipListNode<T>* NodePointer;
+ NodePointer node;
+
+ typedef SkipListIterator<T, Ref, Ptr> Self;
+ typedef T value_type;
+ typedef Ptr pointer;
+ typedef Ref reference;
+ typedef ptrdiff_t difference_type;
+ typedef SkipListIterator<T, const T&, const T*> const_iterator;
+ /// alias of const_iterator
+ typedef const_iterator iterator;
+
+public:
+ // constructor
+ SkipListIterator()
+ {
+ }
+
+ explicit
+ SkipListIterator(NodePointer x)
+ : node(x)
+ {
+ }
+
+ SkipListIterator(const SkipListIterator& x)
+ : node(x.node)
+ {
+ }
+
+ bool
+ operator==(const const_iterator& x) const
+ {
+ return node == x.node;
+ }
+
+ bool
+ operator!=(const const_iterator& x) const
+ {
+ return node != x.node;
+ }
+
+ reference
+ operator*() const
+ {
+ return (*node).data;
+ }
+
+ pointer
+ operator->() const
+ {
+ return &(operator*());
+ }
+
+ Self&
+ operator++()
+ {
+ node = node->nexts[0];
+ return *this;
+ }
+
+ Self
+ operator++(int)
+ {
+ Self tmp = *this;
+ ++*this;
+ return tmp;
+ }
+
+ Self&
+ operator--()
+ {
+ node = node->prevs[0];
+ return *this;
+ }
+
+ Self
+ operator--(int)
+ {
+ Self tmp = *this;
+ --*this;
+ return tmp;
+ }
+};
+
+/*
+ * @brief SkipList
+ *
+ * Examples of internal structure:
+ * "A <-i-> B" means A->nexts[i] = B and B->prevs[i] = A
+ *
+ * case 1: an empty skip list
+ * m_head <-0-> m_head
+ *
+ * case 2: a skip list with only one level and only one node
+ * m_head <-0-> A <-0-> m_head
+ *
+ * case 3: a skip list with three nodes, node A and B appear on one level,
+ * node C appears on two levels
+ * m_head <-1-> C <-1-> m_head
+ * m_head <-0-> A <-0-> B <-0-> C <-0-> m_head
+ */
+
+template<typename T, typename Compare = std::less<T>,
+ typename Traits = SkipList32Levels25Probabilty>
+class SkipList
+{
+public:
+ typedef T value_type;
+ typedef value_type* pointer;
+ typedef const value_type* const_pointer;
+ typedef value_type& reference;
+ typedef const value_type& const_reference;
+ typedef SkipListNode<T> Node;
+ typedef Node* NodePointer;
+ typedef size_t size_type;
+ typedef ptrdiff_t difference_type;
+ typedef SkipListIterator<T, const T&, const T*> const_iterator;
+ /// alias of const_iterator
+ typedef const_iterator iterator;
+
+public:
+ explicit
+ SkipList()
+ {
+ initializeHead();
+ }
+
+ ~SkipList()
+ {
+ clear();
+ deallocateNode(m_head);
+ }
+
+ const_iterator
+ begin() const
+ {
+ return const_iterator(*(*m_head).nexts.begin());
+ }
+
+ const_iterator
+ end() const
+ {
+ return const_iterator(m_head);
+ }
+
+ bool
+ empty() const
+ {
+ return *(m_head->nexts.begin()) == m_head;
+ }
+
+ size_t
+ size() const
+ {
+ return m_size;
+ }
+
+ const_iterator
+ lower_bound(const T& x) const;
+
+ const_iterator
+ find(const T& x) const;
+
+ std::pair<const_iterator, bool>
+ insert(const T& x);
+
+ const_iterator
+ erase(const_iterator it);
+
+protected:
+ /*
+ * @brief allocate memory for node
+ */
+ NodePointer
+ allocateNode()
+ {
+ return m_skiplistAllocator.allocate(sizeof(Node));
+ }
+
+ /*
+ * @brief deallocate memory of node
+ */
+ void
+ deallocateNode(NodePointer p)
+ {
+ m_skiplistAllocator.deallocate(p, sizeof(Node));
+ }
+
+ /*
+ * @brief initialize the node
+ */
+ NodePointer
+ createNode()
+ {
+ NodePointer p = allocateNode();
+ Node node;
+ m_skiplistAllocator.construct(p, node);
+ return p;
+ }
+
+ /*
+ * @brief initialize the node with given value
+ * @para to be set to the value of node
+ */
+ NodePointer
+ createNode(const T& x)
+ {
+ NodePointer p = allocateNode();
+ Node node;
+ m_skiplistAllocator.construct(p, node);
+ m_dataAllocator.construct(&(p->data), x);
+ return p;
+ }
+
+ /*
+ * @brief destructror of the node
+ * @para given pointer of node to be destructed
+ */
+ void
+ destroyNode(NodePointer p)
+ {
+ m_skiplistAllocator.destroy(p);
+ deallocateNode(p);
+ }
+
+ /*
+ * @brief initialize the head
+ */
+ void
+ initializeHead()
+ {
+ m_head = createNode();
+ m_head->prevs.push_back(m_head);
+ m_head->nexts.push_back(m_head);
+ m_size = 0;
+ }
+
+ /*
+ * @brief destroy all the nodes of skiplist except the head
+ */
+ void
+ clear()
+ {
+ NodePointer cur = m_head->nexts[0];
+ while (cur != m_head) {
+ NodePointer tmp = cur;
+ cur = cur->nexts[0];
+ destroyNode(tmp);
+ }
+ m_head->nexts[0] = m_head;
+ m_head->prevs[0] = m_head;
+ }
+
+ /*
+ * @brief pick a random height for inserted skiplist entry
+ */
+ size_t
+ pickRandomLevel() const
+ {
+ static boost::random::mt19937 gen;
+ static boost::random::geometric_distribution<size_t> dist(Traits::getProbability());
+ return std::min(dist(gen), Traits::getMaxLevels());
+ }
+
+protected:
+ NodePointer m_head;
+ std::allocator<Node> m_skiplistAllocator;
+ std::allocator<T> m_dataAllocator;
+ Compare m_compare;
+ size_t m_size;
+};
+
+
+template<typename T, typename Compare, typename Traits>
+typename SkipList<T, Compare, Traits>::const_iterator
+SkipList<T, Compare, Traits>::lower_bound(const T& x) const
+{
+ size_t nLevels = m_head->nexts.size();
+ NodePointer p = m_head;
+ NodePointer q = p->nexts[nLevels - 1];
+ for (int i = nLevels - 1; i >= 0; --i) {
+ q = p->nexts[i];
+ if (q != m_head) {
+ while (m_compare(q->data, x)) {
+ p = p->nexts[i];
+ q = p->nexts[i];
+ if (q == m_head) {
+ break;
+ }
+ }
+ }
+ }
+ return const_iterator(q);
+}
+
+template<typename T, typename Compare, typename Traits>
+typename SkipList<T, Compare, Traits>::const_iterator
+SkipList<T, Compare, Traits>::find(const T& x) const
+{
+ const_iterator it = this->lower_bound(x);
+ if (it == this->end() || *it != x)
+ return this->end();
+ return it;
+}
+
+template<typename T, typename Compare, typename Traits>
+std::pair<typename SkipList<T, Compare, Traits>::const_iterator, bool>
+SkipList<T, Compare, Traits>::insert(const T& x)
+{
+ size_t nLevels = m_head->nexts.size();
+ // 1. find insert position
+ std::vector<NodePointer> insertPositions(nLevels);
+ NodePointer p = m_head;
+ NodePointer q = p->nexts[nLevels - 1];
+ for (int i = nLevels - 1; i >= 0; --i) {
+ q = p->nexts[i];
+ if (q != m_head) {
+ while (m_compare(q->data, x)) {
+ p = p->nexts[i];
+ q = p->nexts[i];
+ if (q == m_head) {
+ break;
+ }
+ }
+ }
+ insertPositions[i] = p;
+ }
+ // 2. whether q->data == x?
+ if (q != m_head)
+ if (!m_compare(q->data, x) && !m_compare(x, q->data)) {
+ return std::pair<const_iterator, bool>(const_iterator(q), false);
+ }
+ // 3. construct new node;
+ NodePointer newNode = createNode(x);
+ // 4. pick random nLevels
+ size_t newLevel = pickRandomLevel();
+ // 5. insert the new node
+ newNode->nexts.resize(newLevel + 1);
+ newNode->prevs.resize(newLevel + 1);
+ if (newLevel > nLevels - 1) {
+ m_head->nexts.resize(newLevel + 1, m_head);
+ m_head->prevs.resize(newLevel + 1, m_head);
+ insertPositions.resize(newLevel + 1, m_head);
+ }
+ for (size_t i = 0; i <= newLevel; i++) {
+ newNode->nexts[i] = insertPositions[i]->nexts[i];
+ newNode->prevs[i] = insertPositions[i];
+ insertPositions[i]->nexts[i] = newNode;
+ newNode->nexts[i]->prevs[i] = newNode;
+ }
+
+ ++m_size;
+ return std::pair<const_iterator, bool>(const_iterator(newNode), true);
+}
+
+template<typename T, typename Compare, typename Traits>
+typename SkipList<T, Compare, Traits>::const_iterator
+SkipList<T, Compare, Traits>::erase(typename SkipList<T, Compare, Traits>::const_iterator it)
+{
+ NodePointer eraseNode = it.node;
+ if (!empty() && eraseNode != m_head) {
+ NodePointer returnNode = eraseNode->nexts[0];
+ size_t nLevels = eraseNode->nexts.size();
+ for (int i = nLevels - 1; i >= 0; --i) {
+ eraseNode->nexts[i]->prevs[i] = eraseNode->prevs[i];
+ eraseNode->prevs[i]->nexts[i] = eraseNode->nexts[i];
+ // clear empty nLevels
+ if ((eraseNode->nexts[i] == eraseNode->prevs[i]) && i > 0) {
+ m_head->nexts.pop_back();
+ m_head->prevs.pop_back();
+ }
+ }
+ destroyNode(eraseNode);
+ --m_size;
+ return const_iterator(returnNode);
+ }
+ else {
+ return end();
+ }
+}
+
+} // namespace prev
+
+#endif // REPO_TESTS_OTHER_SKIPLIST_PREV_HPP
diff --git a/tests/other/skiplist-smoketest.cpp b/tests/other/skiplist-smoketest.cpp
new file mode 100644
index 0000000..645c7a2
--- /dev/null
+++ b/tests/other/skiplist-smoketest.cpp
@@ -0,0 +1,128 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014, Regents of the University of California.
+ *
+ * This file is part of NDN repo-ng (Next generation of NDN repository).
+ * See AUTHORS.md for complete list of repo-ng authors and contributors.
+ *
+ * repo-ng 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.
+ *
+ * repo-ng 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
+ * repo-ng, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "skiplist-list.hpp" // This skiplist is updated by weiqi.
+ // The internal structure of skiplist node is std::list
+
+#include "skiplist-vector.hpp" // This skiplist is revised is revised based on the version above
+ // The internal structure of skiplist node is std::vector
+
+#include "skiplist-prev.hpp" // This skiplist is that of previous commit
+
+#include <iostream>
+#include <set>
+
+using namespace ndn::time;
+
+namespace repo {
+namespace tests {
+
+void
+testSkipList()
+{
+ typedef update1::SkipList<int, std::greater<int> > IntGtContainer;
+ IntGtContainer sl;
+ steady_clock::TimePoint start = steady_clock::now();
+ for (int i = 0; i < 100000; ++i) {
+ sl.insert(i);
+ }
+ milliseconds duration = duration_cast<milliseconds>(steady_clock::now() - start);
+ start = steady_clock::now();
+ std::cout << "SkipList-list insert 100000 integers cost " << duration.count() << "ms" << std::endl;
+ for (int i = 0; i< 100000; ++i) {
+ sl.lower_bound(i);
+ }
+ duration = duration_cast<milliseconds>(steady_clock::now() - start);
+ std::cout << "SkipList-list lower_bound 100000 integers cost " << duration.count() << "ms" << std::endl;
+}
+
+void
+testSkipVector()
+{
+ typedef update2::SkipList<int, std::greater<int> > IntGtContainer;
+ IntGtContainer container;
+ steady_clock::TimePoint start = steady_clock::now();
+ for (int i = 0; i < 100000; ++i) {
+ container.insert(i);
+ }
+ milliseconds duration = duration_cast<milliseconds>(steady_clock::now() - start);
+ start = steady_clock::now();
+ std::cout << "Skiplist-vector insert 100000 integers cost " << duration.count() << "ms" << std::endl;
+ for (int i = 0; i< 100000; ++i) {
+ container.lower_bound(i);
+ }
+ duration = duration_cast<milliseconds>(steady_clock::now() - start);
+ std::cout << "Skiplist-vector lower_bound 100000 integers cost " << duration.count() << "ms" << std::endl;
+}
+
+void
+testSkipPrev()
+{
+ typedef prev::SkipList<int, std::greater<int> > IntGtContainer;
+ IntGtContainer container;
+ steady_clock::TimePoint start = steady_clock::now();
+ for (int i = 0; i < 100000; ++i) {
+ container.insert(i);
+ }
+ milliseconds duration = duration_cast<milliseconds>(steady_clock::now() - start);
+ start = steady_clock::now();
+ std::cout << "Skiplist-prev insert 100000 integers cost " << duration.count() << "ms" << std::endl;
+ for (int i = 0; i< 100000; ++i) {
+ container.lower_bound(i);
+ }
+ duration = duration_cast<milliseconds>(steady_clock::now() - start);
+ std::cout << "Skiplist-prev lower_bound 100000 integers cost " << duration.count() << "ms" << std::endl;
+}
+
+void
+testSet()
+{
+ typedef std::set<int, std::greater<int> > IntGtContainer;
+ IntGtContainer container;
+ steady_clock::TimePoint start = steady_clock::now();
+ for (int i = 0; i < 100000; ++i) {
+ container.insert(i);
+ }
+ milliseconds duration = duration_cast<milliseconds>(steady_clock::now() - start);
+ start = steady_clock::now();
+ std::cout << "Set insert 100000 integers cost " << duration.count() << "ms" << std::endl;
+ for (int i = 0; i< 100000; ++i) {
+ container.lower_bound(i);
+ }
+ duration = duration_cast<milliseconds>(steady_clock::now() - start);
+ std::cout << "Set lower_bound 100000 integers cost " << duration.count() << "ms" << std::endl;
+}
+
+void runTestCases() {
+ testSkipList();
+ testSkipVector();
+ testSkipPrev();
+ testSet();
+}
+
+} // namespace tests
+} // namespace repo
+
+int
+main(int argc, char** argv)
+{
+ repo::tests::runTestCases();
+
+ return 0;
+}
\ No newline at end of file
diff --git a/tests/other/skiplist-vector.hpp b/tests/other/skiplist-vector.hpp
new file mode 100644
index 0000000..6079dd3
--- /dev/null
+++ b/tests/other/skiplist-vector.hpp
@@ -0,0 +1,417 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+* Copyright (c) 2014, Regents of the University of California.
+*
+* This file is part of NDN repo-ng (Next generation of NDN repository).
+* See AUTHORS.md for complete list of repo-ng authors and contributors.
+*
+* repo-ng 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.
+*
+* repo-ng 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
+* repo-ng, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#ifndef REPO_TESTS_OTHER_SKIPLIST_VECTOR_HPP
+#define REPO_TESTS_OTHER_SKIPLIST_VECTOR_HPP
+#include "common.hpp"
+
+namespace update2 {
+
+class SkipList32Levels25Probabilty
+{
+public:
+ static size_t
+ getMaxLevels()
+ {
+ return 32;
+ }
+
+ static double
+ getProbability()
+ {
+ return 0.25; // 25%
+ }
+};
+
+template<typename T>
+struct SkipListNode
+{
+ typedef SkipListNode<T>* SkipListNodePointer;
+ T data;
+ std::vector<SkipListNodePointer> prevs;
+ std::vector<SkipListNodePointer> nexts;
+};
+
+template<typename T, class Ref, class Ptr>
+class SkipListIterator : public std::iterator<std::bidirectional_iterator_tag, T>
+{
+public:
+ typedef SkipListNode<T>* NodePointer;
+ NodePointer node;
+
+ typedef SkipListIterator<T, Ref, Ptr> Self;
+ typedef T value_type;
+ typedef Ptr pointer;
+ typedef Ref reference;
+ typedef ptrdiff_t difference_type;
+ typedef SkipListIterator<T, const T&, const T*> const_iterator;
+ /// alias of const_iterator
+ typedef const_iterator iterator;
+
+public:
+ // constructor
+ SkipListIterator()
+ {
+ }
+
+ explicit
+ SkipListIterator(NodePointer x)
+ : node(x)
+ {
+ }
+
+ SkipListIterator(const SkipListIterator& x)
+ : node(x.node)
+ {
+ }
+
+ bool
+ operator==(const const_iterator& x) const
+ {
+ return node == x.node;
+ }
+
+ bool
+ operator!=(const const_iterator& x) const
+ {
+ return node != x.node;
+ }
+
+ reference
+ operator*() const
+ {
+ return (*node).data;
+ }
+
+ pointer
+ operator->() const
+ {
+ return &(operator*());
+ }
+
+ Self&
+ operator++()
+ {
+ node = node->nexts.front();
+ return *this;
+ }
+
+ Self
+ operator++(int)
+ {
+ Self tmp = *this;
+ ++*this;
+ return tmp;
+ }
+
+ Self&
+ operator--()
+ {
+ node = node->prevs.front();
+ return *this;
+ }
+
+ Self
+ operator--(int)
+ {
+ Self tmp = *this;
+ --*this;
+ return tmp;
+ }
+};
+
+/*
+ * @brief SkipList
+ *
+ * Examples of internal structure:
+ * "A <-i-> B" means A->nexts[i] = B and B->prevs[i] = A
+ *
+ * case 1: an empty skip list
+ * m_head <-0-> m_head
+ *
+ * case 2: a skip list with only one level and only one node
+ * m_head <-0-> A <-0-> m_head
+ *
+ * case 3: a skip list with three nodes, node A and B appear on one level,
+ * node C appears on two levels
+ * m_head <-1-> C <-1-> m_head
+ * m_head <-0-> A <-0-> B <-0-> C <-0-> m_head
+ */
+
+template<typename T, typename Compare = std::less<T>,
+ typename Traits = SkipList32Levels25Probabilty>
+class SkipList
+{
+public:
+ typedef T value_type;
+ typedef value_type* pointer;
+ typedef const value_type* const_pointer;
+ typedef value_type& reference;
+ typedef const value_type& const_reference;
+ typedef SkipListNode<T> Node;
+ typedef Node* NodePointer;
+ typedef size_t size_type;
+ typedef ptrdiff_t difference_type;
+ typedef SkipListIterator<T, const T&, const T*> const_iterator;
+ /// alias of const_iterator
+ typedef const_iterator iterator;
+ typedef SkipListNode<T>* SkipListNodePointer;
+
+public:
+ explicit
+ SkipList()
+ {
+ initializeHead();
+ }
+
+ ~SkipList()
+ {
+ clear();
+ delete(m_head);
+ }
+
+ const_iterator
+ begin() const
+ {
+ return const_iterator(*(*m_head).nexts.begin());
+ }
+
+ const_iterator
+ end() const
+ {
+ return const_iterator(m_head);
+ }
+
+ bool
+ empty() const
+ {
+ return *(m_head->nexts.begin()) == m_head;
+ }
+
+ size_t
+ size() const
+ {
+ return m_size;
+ }
+
+ const_iterator
+ lower_bound(const T& x) const;
+
+ const_iterator
+ find(const T& x) const;
+
+ std::pair<const_iterator, bool>
+ insert(const T& x);
+
+ const_iterator
+ erase(const_iterator it);
+
+protected:
+
+ /*
+ * @brief initialize the node
+ */
+ NodePointer
+ createNode()
+ {
+ NodePointer p = new Node;
+ return p;
+ }
+
+ /*
+ * @brief initialize the node with given value
+ * @para to be set to the value of node
+ */
+ NodePointer
+ createNode(const T& x)
+ {
+ NodePointer p = new Node;
+ m_dataAllocator.construct(&(p->data), x);
+ return p;
+ }
+
+ /*
+ * @brief destructror of the node
+ * @para given pointer of node to be destructed
+ */
+ void
+ destroyNode(NodePointer p)
+ {
+ delete(p);
+ }
+
+ /*
+ * @brief initialize the head
+ */
+ void
+ initializeHead()
+ {
+ m_head = createNode();
+ m_head->prevs.push_back(m_head);
+ m_head->nexts.push_back(m_head);
+ m_size = 0;
+ }
+
+ /*
+ * @brief destroy all the nodes of skiplist except the head
+ */
+ void
+ clear()
+ {
+ NodePointer cur = m_head->nexts[0];
+ while (cur != m_head) {
+ NodePointer tmp = cur;
+ cur = cur->nexts[0];
+ destroyNode(tmp);
+ }
+ m_head->nexts[0] = m_head;
+ m_head->prevs[0] = m_head;
+ }
+
+ /*
+ * @brief pick a random height for inserted skiplist entry
+ */
+ size_t
+ pickRandomLevel() const
+ {
+ static boost::random::mt19937 gen;
+ static boost::random::geometric_distribution<size_t> dist(Traits::getProbability());
+ return std::min(dist(gen), Traits::getMaxLevels());
+ }
+
+protected:
+ NodePointer m_head;
+ std::allocator<T> m_dataAllocator;
+ Compare m_compare;
+ size_t m_size;
+};
+
+
+template<typename T, typename Compare, typename Traits>
+typename SkipList<T, Compare, Traits>::const_iterator
+SkipList<T, Compare, Traits>::lower_bound(const T& x) const
+{
+ size_t nLevels = m_head->nexts.size();
+ NodePointer p = m_head;
+ NodePointer q = p->nexts[nLevels - 1];
+ for (int i = nLevels - 1; i >= 0; --i) {
+ q = p->nexts[i];
+ if (q != m_head) {
+ while (m_compare(q->data, x)) {
+ p = p->nexts[i];
+ q = p->nexts[i];
+ if (q == m_head) {
+ break;
+ }
+ }
+ }
+ }
+ return const_iterator(q);
+}
+
+template<typename T, typename Compare, typename Traits>
+typename SkipList<T, Compare, Traits>::const_iterator
+SkipList<T, Compare, Traits>::find(const T& x) const
+{
+ const_iterator it = this->lower_bound(x);
+ if (it == this->end() || *it != x)
+ return this->end();
+ return it;
+}
+
+template<typename T, typename Compare, typename Traits>
+std::pair<typename SkipList<T, Compare, Traits>::const_iterator, bool>
+SkipList<T, Compare, Traits>::insert(const T& x)
+{
+ size_t nLevels = m_head->nexts.size();
+ // 1. find insert position
+ std::vector<NodePointer> insertPositions(nLevels);
+ NodePointer p = m_head;
+ NodePointer q = p->nexts[nLevels - 1];
+ for (int i = nLevels - 1; i >= 0; --i) {
+ q = p->nexts[i];
+ if (q != m_head) {
+ while (m_compare(q->data, x)) {
+ p = p->nexts[i];
+ q = p->nexts[i];
+ if (q == m_head) {
+ break;
+ }
+ }
+ }
+ insertPositions[i] = p;
+ }
+ // 2. whether q->data == x?
+ if (q != m_head)
+ if (!m_compare(q->data, x) && !m_compare(x, q->data)) {
+ return std::pair<const_iterator, bool>(const_iterator(q), false);
+ }
+ // 3. construct new node;
+ NodePointer newNode = createNode(x);
+ // 4. pick random nLevels
+ size_t newLevel = pickRandomLevel();
+ // 5. insert the new node
+ newNode->nexts.resize(newLevel + 1);
+ newNode->prevs.resize(newLevel + 1);
+ if (newLevel > nLevels - 1) {
+ m_head->nexts.resize(newLevel + 1, m_head);
+ m_head->prevs.resize(newLevel + 1, m_head);
+ insertPositions.resize(newLevel + 1, m_head);
+ }
+ for (size_t i = 0; i <= newLevel; i++) {
+ newNode->nexts[i] = insertPositions[i]->nexts[i];
+ newNode->prevs[i] = insertPositions[i];
+ insertPositions[i]->nexts[i] = newNode;
+ newNode->nexts[i]->prevs[i] = newNode;
+ }
+
+ ++m_size;
+ return std::pair<const_iterator, bool>(const_iterator(newNode), true);
+}
+
+template<typename T, typename Compare, typename Traits>
+typename SkipList<T, Compare, Traits>::const_iterator
+SkipList<T, Compare, Traits>::erase(typename SkipList<T, Compare, Traits>::const_iterator it)
+{
+ NodePointer eraseNode = it.node;
+ if (!empty() && eraseNode != m_head) {
+ NodePointer returnNode = eraseNode->nexts[0];
+ size_t nLevels = eraseNode->nexts.size();
+ for (int i = nLevels - 1; i >= 0; --i) {
+ eraseNode->nexts[i]->prevs[i] = eraseNode->prevs[i];
+ eraseNode->prevs[i]->nexts[i] = eraseNode->nexts[i];
+ // clear empty nLevels
+ if ((eraseNode->nexts[i] == eraseNode->prevs[i]) && i > 0) {
+ m_head->nexts.pop_back();
+ m_head->prevs.pop_back();
+ }
+ }
+ destroyNode(eraseNode);
+ --m_size;
+ return const_iterator(returnNode);
+ }
+ else {
+ return end();
+ }
+
+}
+
+} //end namespace update2
+
+#endif // REPO_TESTS_OTHER_SKIPLIST_VECTOR_HPP
diff --git a/tests/other/wscript b/tests/other/wscript
new file mode 100644
index 0000000..6bb9fb6
--- /dev/null
+++ b/tests/other/wscript
@@ -0,0 +1,10 @@
+# -*- Mode: python; py-indent-offset: 4; indent-tabs-mode: nil; coding: utf-8; -*-
+
+top = '../..'
+
+def build(bld):
+ bld.program(target="../../skiplist-smoketest",
+ source="skiplist-smoketest.cpp",
+ use='ndn-repo-objects',
+ install_path=None,
+ )
\ No newline at end of file
diff --git a/tests/unit/skiplist.cpp b/tests/unit/skiplist.cpp
deleted file mode 100644
index 5bbb0ff..0000000
--- a/tests/unit/skiplist.cpp
+++ /dev/null
@@ -1,189 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014, Regents of the University of California.
- *
- * This file is part of NDN repo-ng (Next generation of NDN repository).
- * See AUTHORS.md for complete list of repo-ng authors and contributors.
- *
- * repo-ng 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.
- *
- * repo-ng 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
- * repo-ng, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- */
-
-#include "storage/skiplist.hpp"
-
-#include "../sqlite-fixture.hpp"
-#include "../dataset-fixtures.hpp"
-
-#include <boost/test/unit_test.hpp>
-#include <boost/concept_check.hpp>
-#include <iostream>
-
-namespace repo {
-namespace tests {
-
-BOOST_AUTO_TEST_SUITE(SkipList)
-
-template<class Dataset>
-class Fixture : public Dataset
-{
-};
-
-BOOST_AUTO_TEST_CASE(Correctness)
-{
- typedef repo::SkipList<int, std::greater<int> > IntGtSkipList;
- IntGtSkipList sl;
- BOOST_CONCEPT_ASSERT((boost::BidirectionalIterator<IntGtSkipList::iterator>));
-
- // initial state
- BOOST_CHECK_EQUAL(sl.size(), 0);
- BOOST_CHECK(sl.begin() == sl.end());
- BOOST_CHECK(sl.lower_bound(10) == sl.end());
-
- // initial contents
- sl.insert(10);
- sl.insert(20);
- sl.insert(30);
- BOOST_CHECK_EQUAL(sl.size(), 3);
- // contents: [30,20,10]
-
- // iterators
- IntGtSkipList::iterator it1 = sl.begin();
- IntGtSkipList::iterator it2 = sl.end();
- --it2;
- BOOST_CHECK_EQUAL(*it1, 30);
- BOOST_CHECK_EQUAL(*it2, 10);
- ++it1;
- BOOST_CHECK_EQUAL(*it1, 20);
- IntGtSkipList::iterator it3 = it1;
- ++it1;
- BOOST_CHECK(it2 == it1);
- BOOST_CHECK_EQUAL(*it3, 20);
-
- // lower_bound
- IntGtSkipList::iterator found = sl.lower_bound(35);
- BOOST_CHECK(found == sl.begin());
- BOOST_CHECK_EQUAL(*found, 30);
- found = sl.lower_bound(30);
- BOOST_CHECK_EQUAL(*found, 30);
- found = sl.lower_bound(25);
- BOOST_CHECK_EQUAL(*found, 20);
- found = sl.lower_bound(20);
- BOOST_CHECK_EQUAL(*found, 20);
- found = sl.lower_bound(15);
- BOOST_CHECK_EQUAL(*found, 10);
- found = sl.lower_bound(10);
- BOOST_CHECK_EQUAL(*found, 10);
- found = sl.lower_bound(5);
- BOOST_CHECK(found == sl.end());
-
- // insert duplicate
- std::pair<IntGtSkipList::iterator, bool> insertRes = sl.insert(10);
- BOOST_CHECK_EQUAL(insertRes.second, false);
- BOOST_CHECK_EQUAL(*(insertRes.first), 10);
- BOOST_CHECK_EQUAL(sl.size(), 3);
- insertRes = sl.insert(20);
- BOOST_CHECK_EQUAL(insertRes.second, false);
- BOOST_CHECK_EQUAL(*(insertRes.first), 20);
- BOOST_CHECK_EQUAL(sl.size(), 3);
- insertRes = sl.insert(30);
- BOOST_CHECK_EQUAL(insertRes.second, false);
- BOOST_CHECK_EQUAL(*(insertRes.first), 30);
- BOOST_CHECK_EQUAL(sl.size(), 3);
-
- // insert non-duplicate
- insertRes = sl.insert(5);
- BOOST_CHECK_EQUAL(insertRes.second, true);
- BOOST_CHECK_EQUAL(*(insertRes.first), 5);
- BOOST_CHECK_EQUAL(sl.size(), 4);
- insertRes = sl.insert(35);
- BOOST_CHECK_EQUAL(insertRes.second, true);
- BOOST_CHECK_EQUAL(*(insertRes.first), 35);
- BOOST_CHECK_EQUAL(sl.size(), 5);
- // contents: [35,30,20,10,5]
-
- // erase
- it1 = sl.erase(sl.begin());
- // contents: [30,20,10,5]
- BOOST_CHECK_EQUAL(*it1, 30);
- BOOST_CHECK_EQUAL(sl.size(), 4);
- it2 = sl.end();
- --it2;
- it1 = sl.erase(it2);
- // contents: [30,20,10]
- BOOST_CHECK(it1 == sl.end());
- BOOST_CHECK_EQUAL(sl.size(), 3);
- it2 = sl.lower_bound(20);
- it1 = sl.erase(it2);
- // contents: [30,10]
- BOOST_CHECK_EQUAL(*it1, 10);
- BOOST_CHECK_EQUAL(sl.size(), 2);
- it3 = it1;
- --it1;
- BOOST_CHECK(it1 == sl.begin());
- BOOST_CHECK_EQUAL(*it1, 30);
- ++it3;
- BOOST_CHECK(it3 == sl.end());
-}
-
-class Item : public ndn::Name
-{
-public:
- explicit
- Item(const ndn::Name& name = "")
- : ndn::Name(name)
- , randomValue(ndn::random::generateWord64())
- {
- }
-
-public:
- uint64_t randomValue;
-};
-
-BOOST_FIXTURE_TEST_CASE_TEMPLATE(Bulk, T, CommonDatasets, Fixture<T>)
-{
- BOOST_TEST_MESSAGE(T::getName());
- typedef repo::SkipList<Item, std::less<Item> > SkipList;
- SkipList skipList;
-
- std::vector<Item> items;
- std::set<ndn::Name> names;
- for (typename T::DataContainer::iterator i = this->data.begin();
- i != this->data.end(); ++i) {
- std::pair<std::set<ndn::Name>::iterator, bool> ret = names.insert((*i)->getName());
- if (ret.second) {
- items.push_back(Item((*i)->getName()));
- }
- }
-
- // Insert
- for (std::vector<Item>::iterator i = items.begin(); i != items.end(); ++i) {
- skipList.insert(*i);
- }
-
- BOOST_CHECK_EQUAL(items.size(), skipList.size());
-
- // Randomize items
- std::random_shuffle(items.begin(), items.end());
-
- // Find items and check if the right item is found
- for (std::vector<Item>::iterator i = items.begin(); i != items.end(); ++i) {
- SkipList::iterator item = skipList.find(*i);
- BOOST_CHECK(item != skipList.end());
-
- BOOST_CHECK_EQUAL(static_cast<const Name&>(*item), static_cast<const Name&>(*i));
- BOOST_CHECK_EQUAL(item->randomValue, i->randomValue);
- }
-}
-
-BOOST_AUTO_TEST_SUITE_END()
-
-} // namespace tests
-} // namespace repo