Skiplist implementation

Question

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);
}

• yuri: Was this written by more than one person? const placement style seems very inconsistent.
• Nick: no, i place const before class and after integrals
• Sandro4912: i did sth similar but with dynamic node heigth: codereview.stackexchange.com/questions/197752/…. Maybe it gives some inspiration.

Answer 1

For size_t you need <cstddef>. It only compiles because it gets pulled in via <array>.
Also using size_t = std::size_t; is strange. Normally you'd do: using std::size_t; or just prefix every occurrence which is trivial in your case.

 HeightArray<Node *>
 heads_; 

[...]

 struct SkipList::NodeLocator{
 HeightArray<Node **> prev;
 Node *node = nullptr;
 };

Formatting is atrocious. I'm no fan of aligning values which is time consuming and not even done properly in your code. Apart from that you have a severe inconsistency in placing braces ({}), spaces, const, & and *. This makes the code harder to read than it needs to be and IMO always reflects poorly on the author.
In C++ & and * belong with the type and there should be no arbitrary exceptions. Regarding placement of the other factors that is up to you but you should be consistent above all.

Why the repeated use of public/private? You're not writing Java. If you need to alternate them in order for your program to work then your design is most likely flawed.

Your comments are rather cryptic and have typos. Either maintain them properly or drop them.

Don't ignore compiler warnings.
You have shadowed and unused variables as well as not properly initializing some members. There are also padding problems and cast warnings among some others.
You should compile with as many warnings as you can get away with and try to fix them.

Don't omit braces around statemens as this will lead to bugs eventually.

If you don't need certain ctors make your intent clear by marking them properly as delete instead of simply leaving them out.

Is raw memory managment really necessary here?

---

Overall fairly unpleasant to read so if you want more people to review this you should probably rework it or be prepared to offer a much larger bounty to draw in additional reviewers.

• Nick: thanks, but I expected some comments on the algorithm and memory management itself. yes memory management is important. in current way the skiplist consumes may be half of the memory than if i use std::vector, also it does not do unnecery memory allocations.

Answer 2

Are you aware, that if you define the move constructor (as you did) that move-assignment is not default generated and copy assignment and copy construction are deleted, aka will give a compiler error?

Also constexpr implies inline so you can skip that.

• Nick: I know, but I don't need copy constructor. made move constructor just to be able to do some tests code.