storage: skiplist for repo index
This version of skiplist is low efficient because of the map in it
Change-Id: Idecc9016619ca9ab5cbb17b078f71b1cc3d4b03e
refs #1737
diff --git a/src/storage/skiplist.hpp b/src/storage/skiplist.hpp
new file mode 100644
index 0000000..86602b5
--- /dev/null
+++ b/src/storage/skiplist.hpp
@@ -0,0 +1,370 @@
+/* -*- 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_STORAGE_SKIPLIST_HPP
+#define REPO_STORAGE_SKIPLIST_HPP
+
+#include "common.hpp"
+
+#include <boost/utility.hpp>
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/random/uniform_int_distribution.hpp>
+
+namespace repo {
+
+class SkipList32Layers25Probabilty
+{
+public:
+ static size_t
+ getMaxLayers()
+ {
+ return 32;
+ }
+
+ static double
+ getProbability()
+ {
+ return 0.25; /* 25% */
+ }
+};
+
+template<typename T, typename Compare = std::less<T>,
+ typename Traits = SkipList32Layers25Probabilty >
+class SkipList
+{
+public:
+ //@brief layer of skiplist is std::list
+ typedef std::list<T> SkipListLayer;
+ //@brief iterator of skiplist
+ typedef typename SkipListLayer::iterator iterator;
+
+public:
+ explicit
+ SkipList();
+
+ ~SkipList();
+
+ size_t
+ size() const;
+
+public: // enumeration
+
+ iterator
+ begin() const;
+
+ iterator
+ end() const;
+
+ iterator
+ find(const T& key);
+
+ iterator
+ lower_bound(const T& key);
+
+ std::pair<iterator, bool>
+ insert(const T& key);
+
+ iterator
+ erase(iterator it);
+
+private:
+ size_t
+ pickRandomLayer() const;
+
+private:
+ //@brief store multiple layers
+ typedef std::list<shared_ptr<SkipListLayer> > SkipListHeadLayer;
+ //@brief iterate one layer of skiplist
+ typedef typename SkipListLayer::iterator layer_iterator;
+ //@brief iterate among different layers
+ typedef typename SkipListHeadLayer::iterator head_iterator;
+ typedef typename SkipListHeadLayer::reverse_iterator head_reverse_iterator;
+
+private:
+ SkipListHeadLayer m_skipList;
+ //@brief keep the locations of iterator where element is inserted in each layer
+ //key of external map is the layer of skiplist
+ //value is the internal map which maps the key T with the iterator of each layer
+ std::map<size_t, std::map<T, layer_iterator, Compare> > m_layerToEntry;
+ Compare m_compare;
+};
+
+template<typename T, typename Compare, typename Traits>
+inline
+SkipList<T, Compare, Traits>::SkipList()
+{
+ shared_ptr<SkipListLayer> zeroLayer = make_shared<SkipListLayer>();
+ m_skipList.push_back(zeroLayer);
+}
+
+template<typename T, typename Compare, typename Traits>
+inline
+SkipList<T, Compare, Traits>::~SkipList()
+{
+}
+
+template<typename T, typename Compare, typename Traits>
+inline size_t
+SkipList<T, Compare, Traits>::size() const
+{
+ return (*m_skipList.begin())->size();
+}
+
+template<typename T, typename Compare, typename Traits>
+inline typename SkipList<T, Compare, Traits>::iterator
+SkipList<T, Compare, Traits>::begin() const
+{
+ return (*m_skipList.begin())->begin();
+}
+
+template<typename T, typename Compare, typename Traits>
+inline typename SkipList<T, Compare, Traits>::iterator
+SkipList<T, Compare, Traits>::end() const
+{
+ return (*m_skipList.begin())->end();
+}
+
+template<typename T, typename Compare, typename Traits>
+inline typename SkipList<T, Compare, Traits>::iterator
+SkipList<T, Compare, Traits>::find(const T& key)
+{
+ iterator it = this->lower_bound(key);
+ if (it == this->end() || *it != key)
+ return this->end();
+ return it;
+}
+
+template<typename T, typename Compare, typename Traits>
+inline typename SkipList<T, Compare, Traits>::iterator
+SkipList<T, Compare, Traits>::lower_bound(const T& key)
+{
+ bool isIterated = false;
+ bool isIdentical = false;
+ head_reverse_iterator topLayer = m_skipList.rbegin();
+ layer_iterator head = (*topLayer)->begin();
+
+ if (!(*topLayer)->empty()) {
+ size_t layer = m_skipList.size() - 1;
+ for (head_reverse_iterator headReverseIterator = topLayer;
+ headReverseIterator != m_skipList.rend(); ++headReverseIterator) {
+ if (!isIterated)
+ head = (*headReverseIterator)->begin();
+
+ if (head != (*headReverseIterator)->end()) {
+ if (!isIterated && (!m_compare(*head, key) && !m_compare(key, *head))) {
+ if (layer > 0) {
+ layer--;
+ continue; // try lower layer
+ }
+ else {
+ isIterated = true;
+ isIdentical = true;
+ }
+ }
+ else {
+ layer_iterator layerIterator = head;
+ while (m_compare((*layerIterator) , key)) {
+ head = layerIterator;
+ isIterated = true;
+
+ ++layerIterator;
+ if (layerIterator == (*headReverseIterator)->end())
+ break;
+ }
+
+ }
+ }
+
+ if (layer > 0) {
+ //find the head in the lower layer
+ head = m_layerToEntry[layer - 1][*head];
+ }
+ else { //if we reached the first layer
+ if (isIterated) {
+ if (!isIdentical)
+ ++head;
+ //result = head;
+ return head;
+ }
+ else {
+ return head;
+ }
+ }
+
+ layer--;
+ }
+ }
+ return (*m_skipList.begin())->end();
+}
+
+template<typename T, typename Compare, typename Traits>
+inline size_t
+SkipList<T, Compare, Traits>::pickRandomLayer() const
+{
+ static boost::random::mt19937 gen;
+ static boost::random::geometric_distribution<size_t> dist(Traits::getProbability());
+ return std::min(dist(gen), Traits::getMaxLayers());
+}
+
+template<typename T, typename Compare, typename Traits>
+inline std::pair<typename SkipList<T, Compare, Traits>::iterator ,bool>
+SkipList<T, Compare, Traits>::insert(const T& key)
+{
+ bool insertInFront = false;
+ bool isIterated = false;
+ head_reverse_iterator topLayer = m_skipList.rbegin();
+ std::vector<layer_iterator> updateTable(Traits::getMaxLayers());
+ layer_iterator head = (*topLayer)->begin();
+
+ if (!(*topLayer)->empty()) {
+ size_t layer = m_skipList.size() - 1;
+ for (head_reverse_iterator headReverseIterator = topLayer;
+ headReverseIterator != m_skipList.rend(); ++headReverseIterator) {
+ if (!isIterated)
+ head = (*headReverseIterator)->begin();
+
+ updateTable[layer] = head;
+
+ if (head != (*headReverseIterator)->end()) {
+ if (!isIterated && !m_compare(*head, key)) {
+ --updateTable[layer];
+ insertInFront = true;
+ }
+ else {
+ layer_iterator layerIterator = head;
+
+ while (m_compare(*layerIterator , key)) {
+ head = layerIterator;
+ updateTable[layer] = layerIterator;
+ isIterated = true;
+
+ ++layerIterator;
+ if (layerIterator == (*headReverseIterator)->end())
+ break;
+ }
+
+ }
+ }
+
+ if (layer > 0)
+ head = m_layerToEntry[layer - 1][*head]; // move HEAD to the lower layer
+
+ layer--;
+ }
+ }
+ else {
+ updateTable[0] = (*topLayer)->begin(); //initialization
+ }
+
+ head = updateTable[0];
+ ++head;
+
+ bool isInBoundaries = (head != (*m_skipList.begin())->end());
+ bool isKeyIdentical = false;
+ if (isInBoundaries) {
+ isKeyIdentical = (!m_compare(*head, key) && !m_compare(key, *head));
+ }
+ if (isKeyIdentical) {
+ return std::make_pair(head, false);
+ }
+
+ size_t randomLayer = pickRandomLayer();
+
+ while (m_skipList.size() < randomLayer + 1) {
+ boost::shared_ptr<SkipListLayer> newLayer = make_shared<SkipListLayer>();
+ m_skipList.push_back(newLayer);
+
+ updateTable[(m_skipList.size() - 1)] = newLayer->begin();
+ }
+
+ size_t layer = 0;
+ layer_iterator result;
+
+ for (head_iterator headIterator = m_skipList.begin();
+ headIterator != m_skipList.end() && layer <= randomLayer; ++headIterator) {
+ if (updateTable[layer] == (*headIterator)->end() && !insertInFront) {
+ (*headIterator)->push_back(key);
+ layer_iterator last = (*headIterator)->end();
+ --last;
+ m_layerToEntry[layer][key] = last;
+
+ }
+ else if (updateTable[layer] == (*headIterator)->end() && insertInFront) {
+ (*headIterator)->push_front(key);
+ m_layerToEntry[layer][key] = (*headIterator)->begin();
+ }
+ else {
+ ++updateTable[layer]; // insert after
+ iterator position = (*headIterator)->insert(updateTable[layer], key);
+ m_layerToEntry[layer][key] = position; // save iterator where item was inserted
+ }
+ if (layer == 0)
+ result = m_layerToEntry[layer][key];
+ layer++;
+ }
+ return make_pair(result, true);
+}
+
+template<typename T, typename Compare, typename Traits>
+inline typename SkipList<T, Compare, Traits>::iterator
+SkipList<T, Compare, Traits>::erase(typename SkipList<T, Compare, Traits>::iterator it)
+{
+ if (it != end()) {
+ int layer = 1;
+ head_iterator headIterator = m_skipList.begin();
+ headIterator++;
+ for (; headIterator != m_skipList.end();) {
+ const std::map<T, layer_iterator, Compare>& layerIterators = m_layerToEntry[layer];
+ if(!layerIterators.empty()) {
+ typename std::map<T, layer_iterator, Compare>::const_iterator eraseIterator =
+ layerIterators.find(*it);
+ if (eraseIterator != layerIterators.end()) {
+ (*headIterator)->erase(eraseIterator->second);
+ m_layerToEntry[layer].erase(*it);
+ //remove layers that do not contain any elements (starting from the second layer)
+ if ((*headIterator)->empty()) {
+ // delete headIterator;
+ headIterator = m_skipList.erase(headIterator);
+ }
+ else {
+ ++headIterator;
+ }
+ layer++;
+ }
+ else {
+ break;
+ }
+ }
+ }
+
+ m_layerToEntry[0].erase(*it);
+ m_skipList.end();
+ typename SkipList<T, Compare, Traits>::iterator returnIterator =
+ (*m_skipList.begin())->erase(it);
+
+ return returnIterator;
+ }
+ else {
+ return end();
+ }
+}
+
+} // namespace repo
+
+#endif // REPO_STORAGE_SKIPLIST_HPP