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