• 35.2k
• 13
• 134
• 238

• 1.7k
• 11
• 21

• 1.7k
• 11
• 21

This is simplified version of my skip-list.

The only simplification is instead of K and V I use special class, that resemble big std:pair<char *,Blob>.

At the moment the skip-list acts more like a set of int.

At the end of skiplist.cc I also added main() function with some test usage.

Real code is here:
https://github.com/nmmmnu/HM4/blob/master/hm4/linklist.cc

I want to know if there are some mistakes or performance improvements I missed.

Any help will be appreciated.

#skiplist.h
#ifndef _SKIP_LIST_LIST_H
#define _SKIP_LIST_LIST_H
#include <cstdint>
#include <array>
using size_t = std::size_t;
using V = int;
using K = int;
constexpr int compare(V const a, K const b){
 return a - b;
}
class SkipList {
public:
 using size_type = size_t;
 using height_type = uint8_t;
public:
 static constexpr height_type MAX_HEIGHT = 64;
 static constexpr height_type DEFAULT_HEIGHT = 32;
 class Iterator;
public:
 explicit
 SkipList(height_type height = DEFAULT_HEIGHT);
 SkipList(SkipList &&other);
 ~SkipList();
public:
 bool clear();
 const K *operator[](const K &key) const;
 bool erase(const V &key);
 bool insert(V &&data);
 size_type size(bool const = false) const noexcept{
 return dataCount_;
 }
public:
 Iterator lowerBound(const V &key) const;
 Iterator begin() const;
 static constexpr Iterator end();
private:
 struct Node;
 template<typename T>
 using HeightArray = std::array<T, MAX_HEIGHT>;
 height_type height_;
 HeightArray<Node *>
 heads_;
 size_type dataCount_;
private:
 void zeroing_();
 struct NodeLocator;
 NodeLocator locate_(const K &key, bool shortcut_evaluation);
 const Node *locateNode_(const K &key, bool const exact) const;
 height_type getRandomHeight_();
private:
 class RandomGenerator;
 static RandomGenerator rand_;
};
// ==============================
class SkipList::Iterator{
private:
 friend class SkipList;
 constexpr Iterator(const Node *node) : node_(node){}
public:
 Iterator &operator++();
 const V &operator*() const;
public:
 bool operator==(const Iterator &other) const{
 return node_ == other.node_;
 }
 bool operator!=(const Iterator &other) const{
 return ! operator==(other);
 }
 const V *operator ->() const{
 return & operator*();
 }
private:
 const Node *node_;
};
// ==============================
inline auto SkipList::lowerBound(const K &key) const -> Iterator{
 return locateNode_(key, false);
}
inline auto SkipList::begin() const -> Iterator{
 return heads_[0];
}
inline constexpr auto SkipList::end() -> Iterator{
 return nullptr;
}
#endif

#skiplist.cc

#include "skiplist.h"
#include <stdexcept>
#include <algorithm> // fill
#include <random> // mt19937, bernoulli_distribution
#include <cassert>
class SkipList::RandomGenerator{
public:
 bool operator()(){
 return distr_(gen_);
 }
private:
 std::mt19937 gen_{ (uint32_t) time(nullptr) };
 std::bernoulli_distribution distr_{ 0.5 };
};
SkipList::RandomGenerator SkipList::rand_;
// ==============================
/*
We do ***NOT*** store next[] array size,
***NOR*** we store NULL after last next node.
It turn out it does not need, because NULL lanes are already NULL.
Disadvantage is once allocated, no one knows the size,
except probably with malloc_usable_size();
[2]------------------------------->NULL
[1]------>[1]------>[1]----------->NULL
[0]->[0]->[0]->[0]->[0]->[0]->[0]->NULL
*/
struct SkipList::Node{
 V data;
 Node *next[1]; // system dependent, dynamic, at least 1
public:
 // no need universal ref
 Node(V &&data) : data(std::move(data)){}
private:
 static size_t calcNewSize__(size_t const size, height_type const height){
 return size + (height - 1) * sizeof(Node *);
 }
public:
 static void *operator new(size_t const size, height_type const height) {
 return ::operator new(calcNewSize__(size, height));
 }
 static void *operator new(size_t const size, height_type const height, std::nothrow_t ) {
 return ::operator new(calcNewSize__(size, height), std::nothrow);
 }
};
// ==============================
struct SkipList::NodeLocator{
 HeightArray<Node **> prev;
 Node *node = nullptr;
};
// ==============================
SkipList::SkipList(height_type const height) :
 height_(height){
 assert( height > 0 && height <= MAX_HEIGHT );
 zeroing_();
}
SkipList::SkipList(SkipList &&other):
 height_ (std::move(other.height_ )),
 heads_ (std::move(other.heads_ )),
 dataCount_ (std::move(other.dataCount_ )){
 other.zeroing_();
}
SkipList::~SkipList(){
 clear();
}
bool SkipList::clear(){
 for(const Node *node = heads_[0]; node; ){
 const Node *copy = node;
 node = node->next[0];
 delete copy;
 }
 zeroing_();
 return true;
}
bool SkipList::insert(V && newdata){
 const auto &key = newdata;
 const auto nl = locate_(key, true);
 if (nl.node){
 // update in place.
 V & olddata = nl.node->data;
 // copy assignment
 olddata = std::move(newdata);
 return true;
 }
 // create new node
 height_type const height = getRandomHeight_();
 Node *newnode = new(height, std::nothrow) Node(std::move(newdata));
 if (newnode == nullptr){
 // newdata will be magically destroyed.
 return false;
 }
 /* SEE REMARK ABOUT NEXT[] SIZE AT THE TOP */
 // newnode->height = height
 // place new node where it belongs
 for(height_type i = 0; i < height; ++i){
 newnode->next[i] = *nl.prev[i];
 *nl.prev[i] = newnode;
 }
#ifdef DEBUG_PRINT_LANES
 printf("%3u Lanes-> ", height);
 for(height_type i = 0; i < height; ++i)
 printf("%p ", (void *) newnode->next[i]);
 printf("\n");
#endif
 /* SEE REMARK ABOUT NEXT[] SIZE AT THE TOP */
 // newnode->next[i] = NULL;
 ++dataCount_;
 return true;
}
const V *SkipList::operator[](const K &key) const{
 const Node *node = locateNode_(key, true);
 return node ? & node->data : nullptr;
}
bool SkipList::erase(const K &key){
 const auto nl = locate_(key, false);
 if (nl.node == nullptr)
 return true;
 for(height_type h = 0; h < height_; ++h){
 if (*nl.prev[h] == nl.node)
 *nl.prev[h] = nl.node->next[h];
 else
 break;
 }
 const V & data = nl.node->data;
 dataCount_--;
 delete nl.node;
 return true;
}
// ==============================
void SkipList::zeroing_(){
 dataCount_ = 0;
 std::fill(heads_.begin(), heads_.end(), nullptr);
}
auto SkipList::locate_(const K &key, bool const shortcut_evaluation) -> NodeLocator{
 NodeLocator nl;
 Node **jtable = heads_.data();
 for(height_type h = height_; h --> 0;){
 for(Node *node = jtable[h]; node; node = node->next[h]){
 const V & data = node->data;
 int const cmp = compare(data, key);
 if (cmp >= 0){
 if (cmp == 0 && (shortcut_evaluation || h == 0) ){
 // found
 nl.node = node;
 if (shortcut_evaluation){
 // at this point, we do not really care,
 // if nl.prev is setup correctly.
 return nl;
 }
 }
 break;
 }
 jtable = node->next;
 }
 nl.prev[h] = & jtable[h];
 }
 return nl;
}
auto SkipList::locateNode_(const K &key, bool const exact) const -> const Node *{
 const Node * const *jtable = heads_.data();
 const Node *node = nullptr;
 for(height_type h = height_; h --> 0;){
 for(node = jtable[h]; node; node = node->next[h]){
 const V & data = node->data;
 int const cmp = compare(data, key);
 if (cmp >= 0){
 if (cmp == 0){
 // found
 return node;
 }
 break;
 }
 jtable = node->next;
 }
 }
 return exact ? nullptr : node;
}
auto SkipList::getRandomHeight_() -> height_type{
 // This gives slightly better performance,
 // than divide by 3 or multply by 0.33
 // We execute rand() inside the loop,
 // but performance is fast enought.
 height_type h = 1;
 while( h < height_ && rand_() )
 h++;
 return h;
}
// ==============================
SkipList::Iterator &SkipList::Iterator::operator++(){
 node_ = node_->next[0];
 return *this;
}
const V &SkipList::Iterator::operator*() const{
 assert(node_);
 return node_->data;
}
// ==============================
// ==============================
// ==============================
#include <iostream>
inline void print(const char *val){
 std::cout << val << '\n';
}
inline void println(){
 print("-------------------");
}
inline void print(const V val){
 std::cout << val << '\n';
}
inline void print(const V *val){
 if (val)
 print(*val);
 else
 print("_none_");
}
inline void print(const SkipList &list){
 for(auto x : list)
 print(x);
 println();
}
constexpr V samples[] = { 100, 5, 22, 59, 35, 25, 8, 3 };
int main(){
 SkipList list;
 for(auto x : samples)
 list.insert(std::move(x));
 print(list);
 print(list[22]);
 print(list[999]);
 println();
 list.erase(22);
 print(list[22]);
 println();
 print(list);
}