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