This is a version of my skip-list implementation. In my project I store my custom class that is similar to a pair of blobs. I replaced my custom class with int
. At the end of skiplist.cc, I also added the main()
function with some test usage. I want to know if there are some mistakes or performance improvements I missed.
#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);
}
const
placement style seems very inconsistent. \$\endgroup\$