Skip List

skip_list.h

#pragma once
#include <algorithm>
#include <array>
#include <cstring>
#include <random>

template <typename T, size_t max_level = 32, typename Compare = std::less<T>>
class SkipList {
  struct Node {
    union {
      T data;
    };
    size_t height;
    Node **next() { return reinterpret_cast<Node **>(this + 1); }
    static Node *create(size_t height) {
      Node *node = reinterpret_cast<Node *>(
          new std::uint8_t[sizeof(Node) + height * sizeof(Node *)]);
      node->height = height;
      memset(node->next(), 0, height * sizeof(Node *));
      return node;
    }
    static void destroy(Node *node) {
      delete[] reinterpret_cast<std::uint8_t *>(node);
    }
  };

  Node *head;
  size_t current_size;
  size_t max_height;
  Compare cmp;
  std::minstd_rand engine;

  // [1, max_level]
  size_t gen_random_level() {
    return max_level - std::__lg((engine() + 1) & ((1ull << max_level) - 1));
  }

public:
  SkipList(const Compare &compare = Compare())
      : head(Node::create(max_level)), current_size(0), max_height(0),
        cmp(compare), engine(std::random_device{}()) {}
  ~SkipList() {
    clear();
    Node::destroy(head);
  }
  std::array<Node **, max_level> collect_prev_nodes(const T &key) {
    std::array<Node **, max_level> prev_nodes{};
    Node **current = &head;
    for (int level = int(max_level) - 1; level >= 0; --level) {
      while ((*current)->next()[level] &&
             cmp((*current)->next()[level]->data, key)) {
        current = &(*current)->next()[level];
      }
      prev_nodes[level] = current;
    }
    return prev_nodes;
  }
  bool insert(const T &value) {
    auto prev_nodes = collect_prev_nodes(value);
    if (Node *next_node = (*prev_nodes[0])->next()[0]) {
      if (!cmp(value, next_node->data) && !cmp(next_node->data, value)) {
        return false;
      }
    }
    Node *new_node = Node::create(gen_random_level());
    new (&new_node->data) T(value);
    for (size_t level = 0; level < new_node->height; ++level) {
      new_node->next()[level] = (*prev_nodes[level])->next()[level];
      (*prev_nodes[level])->next()[level] = new_node;
    }
    max_height = std::max(max_height, new_node->height);
    ++current_size;
    return true;
  }
  bool erase(const T &value) {
    auto prev_nodes = collect_prev_nodes(value);
    if (!(*prev_nodes[0]))
      return false;
    Node *current = (*prev_nodes[0])->next()[0];
    if (!current || cmp(value, current->data) || cmp(current->data, value)) {
      return false;
    }
    for (size_t level = 0; level < current->height; ++level) {
      (*prev_nodes[level])->next()[level] = current->next()[level];
    }
    current->data.~T();
    Node::destroy(current);
    --current_size;
    while (max_height > 0 && head->next()[max_height - 1] == nullptr) {
      --max_height;
    }
    return true;
  }
  bool contains(const T &value) const {
    Node *current = head;
    for (int level = int(max_height) - 1; level >= 0; --level) {
      while (current->next()[level] &&
             cmp(current->next()[level]->data, value)) {
        current = current->next()[level];
      }
    }
    current = current->next()[0];
    return current && !cmp(value, current->data) && !cmp(current->data, value);
  }
  void clear() {
    Node *current = head->next()[0];
    while (current) {
      Node *next = current->next()[0];
      current->data.~T();
      Node::destroy(current);
      current = next;
    }
    memset(head->next(), 0, max_level * sizeof(Node *));
    current_size = 0;
    max_height = 0;
  }
  size_t size() const { return current_size; }
};