storage: a better skiplist
This skiplist refers std::list and removes std::map of previous commit
refs #1737
Change-Id: I6f49849bd8b847d872227ec0f0c7caa9775f447a
diff --git a/src/storage/skiplist.hpp b/src/storage/skiplist.hpp
index 86602b5..1243a71 100644
--- a/src/storage/skiplist.hpp
+++ b/src/storage/skiplist.hpp
@@ -22,17 +22,13 @@
#include "common.hpp"
-#include <boost/utility.hpp>
-#include <boost/random/mersenne_twister.hpp>
-#include <boost/random/uniform_int_distribution.hpp>
-
namespace repo {
-class SkipList32Layers25Probabilty
+class SkipList32Levels25Probabilty
{
public:
static size_t
- getMaxLayers()
+ getMaxLevels()
{
return 32;
}
@@ -40,325 +36,398 @@
static double
getProbability()
{
- return 0.25; /* 25% */
+ 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 = SkipList32Layers25Probabilty >
+ typename Traits = SkipList32Levels25Probabilty>
class SkipList
{
public:
- //@brief layer of skiplist is std::list
- typedef std::list<T> SkipListLayer;
- //@brief iterator of skiplist
- typedef typename SkipListLayer::iterator iterator;
+ 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();
+ SkipList()
+ {
+ initializeHead();
+ }
- ~SkipList();
+ ~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;
+ size() const
+ {
+ return m_size;
+ }
-public: // enumeration
+ const_iterator
+ lower_bound(const T& x) const;
- iterator
- begin() const;
+ const_iterator
+ find(const T& x) const;
- iterator
- end() const;
+ std::pair<const_iterator, bool>
+ insert(const T& x);
- iterator
- find(const T& key);
+ const_iterator
+ erase(const_iterator it);
- iterator
- lower_bound(const T& key);
+protected:
+ /*
+ * @brief allocate memory for node
+ */
+ NodePointer
+ allocateNode()
+ {
+ return m_skiplistAllocator.allocate(sizeof(Node));
+ }
- std::pair<iterator, bool>
- insert(const T& key);
+ /*
+ * @brief deallocate memory of node
+ */
+ void
+ deallocateNode(NodePointer p)
+ {
+ m_skiplistAllocator.deallocate(p, sizeof(Node));
+ }
- iterator
- erase(iterator it);
+ /*
+ * @brief initialize the node
+ */
+ NodePointer
+ createNode()
+ {
+ NodePointer p = allocateNode();
+ Node node;
+ m_skiplistAllocator.construct(p, node);
+ return p;
+ }
-private:
+ /*
+ * @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
- pickRandomLayer() const;
+ pickRandomLevel() const
+ {
+ static boost::random::mt19937 gen;
+ static boost::random::geometric_distribution<size_t> dist(Traits::getProbability());
+ return std::min(dist(gen), Traits::getMaxLevels());
+ }
-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;
+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>
-inline
-SkipList<T, Compare, Traits>::SkipList()
+typename SkipList<T, Compare, Traits>::const_iterator
+SkipList<T, Compare, Traits>::lower_bound(const T& x) const
{
- shared_ptr<SkipListLayer> zeroLayer = make_shared<SkipListLayer>();
- m_skipList.push_back(zeroLayer);
+ 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>
-inline
-SkipList<T, Compare, Traits>::~SkipList()
+typename SkipList<T, Compare, Traits>::const_iterator
+SkipList<T, Compare, Traits>::find(const T& x) const
{
-}
-
-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)
+ 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>
-inline typename SkipList<T, Compare, Traits>::iterator
-SkipList<T, Compare, Traits>::lower_bound(const T& key)
+std::pair<typename SkipList<T, Compare, Traits>::const_iterator, bool>
+SkipList<T, Compare, Traits>::insert(const T& x)
{
- 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 {
+ 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 (int i = 0; i <= static_cast<int>(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_layerToEntry[0].erase(*it);
- m_skipList.end();
- typename SkipList<T, Compare, Traits>::iterator returnIterator =
- (*m_skipList.begin())->erase(it);
+ ++m_size;
+ return std::pair<const_iterator, bool>(const_iterator(newNode), true);
+}
- return returnIterator;
+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();