并发跳表：ConcurrentSkipListMap 的设计

Node* search(SkipList *sl, int key) {
    Node *curr = sl->head;
    for (int level = sl->max_level - 1; level >= 0; level--) {
        while (curr->next[level] != NULL &&
               curr->next[level]->key < key) {
            curr = curr->next[level];
        }
    }
    curr = curr->next[0];
    if (curr != NULL && curr->key == key)
        return curr;
    return NULL;
}

void insert(SkipList *sl, int key, int value) {
    Node *update[MAX_LEVEL];
    Node *curr = sl->head;

    for (int i = sl->max_level - 1; i >= 0; i--) {
        while (curr->next[i] != NULL && curr->next[i]->key < key)
            curr = curr->next[i];
        update[i] = curr;
    }

    int new_level = random_level();
    if (new_level > sl->max_level) {
        for (int i = sl->max_level; i < new_level; i++)
            update[i] = sl->head;
        sl->max_level = new_level;
    }

    Node *new_node = create_node(key, value, new_level);
    for (int i = 0; i < new_level; i++) {
        new_node->next[i] = update[i]->next[i];
        update[i]->next[i] = new_node;
    }
}

int random_level(void) {
    int level = 1;
    while ((rand() & 1) && level < MAX_LEVEL)
        level++;
    return level;
}

// 数据节点（Level 0 链表）
static final class Node<K,V> {
    final K key;
    volatile Object value;   // 值为 null 表示已删除/正在删除
    volatile Node<K,V> next;
}

// 索引节点（上层链表）
static final class Index<K,V> {
    final Node<K,V> node;    // 指向对应的数据节点
    final Index<K,V> down;   // 指向下一层的索引
    volatile Index<K,V> right; // 同层的下一个索引
}

// 头索引节点
static final class HeadIndex<K,V> extends Index<K,V> {
    final int level;
}

// 删除节点 n：
// 1. 将 n.value 设为 null（逻辑删除）
// 2. 在 n 后面插入一个 marker 节点
// 3. CAS 将 n 的前驱的 next 从 n 改为 n.next.next

// 标记节点的特征：value == this（自引用）
boolean isMarker() {
    return value == this;
}

private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
    for (;;) {
        Index<K,V> q = head;
        Index<K,V> r = q.right;
        for (;;) {
            if (r != null) {
                Node<K,V> n = r.node;
                K k = n.key;
                // 如果数据节点已被删除，帮忙断开索引
                if (n.value == null) {
                    if (!q.unlink(r))
                        break;           // 被别人抢先了，从头重来
                    r = q.right;         // 重新读取
                    continue;
                }
                if (cpr(cmp, key, k) > 0) {
                    q = r;               // 向右移动
                    r = r.right;
                    continue;
                }
            }
            // 向下移动
            Index<K,V> d = q.down;
            if (d != null) {
                q = d;
                r = q.right;
            } else {
                return q.node;           // 到达 Level 0，返回
            }
        }
    }
}

private V doPut(K key, V value, boolean onlyIfAbsent) {
    for (;;) {
        Node<K,V> b = findPredecessor(key, comparator);
        Node<K,V> n = b.next;
        
        // 在 Level 0 找到正确位置
        for (;;) {
            if (n != null) {
                Node<K,V> f = n.next;
                if (n != b.next)        // 不一致，重试
                    break;
                Object v = n.value;
                if (v == null) {        // n 已被删除
                    n.helpDelete(b, f); // 帮忙清理
                    break;
                }
                if (b.value == null || v == n) // b 被删除了
                    break;
                int c = cpr(comparator, key, n.key);
                if (c > 0) {
                    b = n;
                    n = f;
                    continue;
                }
                if (c == 0) {
                    // 键已存在，尝试更新
                    if (onlyIfAbsent || n.casValue(v, value))
                        return (V) v;
                    break;              // CAS 失败，重试
                }
            }
            
            // 在 b 和 n 之间插入新节点
            Node<K,V> z = new Node<K,V>(key, value, n);
            if (!b.casNext(n, z))
                break;                  // CAS 失败，重试
            
            // Level 0 插入成功，现在随机决定是否建立索引
            int rnd = ThreadLocalRandom.current().nextInt();
            if ((rnd & 0x80000001) == 0) { // 概率约 0.5
                // 建立索引层...
                addIndex(z, rnd);
            }
            return null;
        }
    }
}

final V doRemove(Object key, Object value) {
    for (;;) {
        Node<K,V> b = findPredecessor(key, comparator);
        Node<K,V> n = b.next;
        
        for (;;) {
            if (n == null)
                return null;
            Node<K,V> f = n.next;
            if (n != b.next)
                break;
            Object v = n.value;
            if (v == null) {
                n.helpDelete(b, f);
                break;
            }
            if (b.value == null || v == n)
                break;
            int c = cpr(comparator, key, n.key);
            if (c < 0)
                return null;
            if (c > 0) {
                b = n; n = f;
                continue;
            }
            // 找到目标节点 n
            // 1. CAS value 为 null（逻辑删除）
            if (!n.casValue(v, null))
                break;
            // 2. 追加 marker 并 CAS 断开
            if (!n.appendMarker(f) || !b.casNext(n, f))
                findNode(key);  // 清理失败则通过 findNode 帮忙清理
            else {
                findPredecessor(key, comparator); // 清理索引层
            }
            return (V) v;
        }
    }
}

// 在 doPut 中
int rnd = ThreadLocalRandom.current().nextInt();
if ((rnd & 0x80000001) == 0) {  // 最高位和最低位都为 0
    int level = 1;
    while (((rnd >>>= 1) & 1) != 0)
        ++level;
    // level 服从几何分布，p ≈ 0.5
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <limits.h>
#include <time.h>

#define MAX_LEVEL   16
#define PROB_HALF   (RAND_MAX / 2)

typedef struct sl_node {
    int                  key;
    int                  value;
    int                  top_level;    /* 该节点的最高层索引 */
    pthread_mutex_t      lock;
    int                  marked;       /* 逻辑删除标记 */
    int                  fully_linked; /* 所有层都已链接完毕 */
    struct sl_node      *next[MAX_LEVEL];
} sl_node_t;

typedef struct {
    sl_node_t           *head;
    sl_node_t           *tail;
    int                  max_level;
} skiplist_t;

/* ---- 辅助函数 ---- */

static sl_node_t *node_create(int key, int value, int level)
{
    sl_node_t *n = calloc(1, sizeof(*n));
    n->key          = key;
    n->value        = value;
    n->top_level    = level;
    n->marked       = 0;
    n->fully_linked = 0;
    pthread_mutex_init(&n->lock, NULL);
    return n;
}

static void node_destroy(sl_node_t *n)
{
    pthread_mutex_destroy(&n->lock);
    free(n);
}

static int random_level(void)
{
    int lvl = 1;
    while (rand() < PROB_HALF && lvl < MAX_LEVEL)
        lvl++;
    return lvl;
}

/* ---- 跳表初始化 ---- */

skiplist_t *skiplist_create(void)
{
    skiplist_t *sl = malloc(sizeof(*sl));
    sl->max_level  = MAX_LEVEL;

    sl->head = node_create(INT_MIN, 0, MAX_LEVEL);
    sl->tail = node_create(INT_MAX, 0, MAX_LEVEL);

    for (int i = 0; i < MAX_LEVEL; i++)
        sl->head->next[i] = sl->tail;

    sl->head->fully_linked = 1;
    sl->tail->fully_linked = 1;
    return sl;
}

void skiplist_destroy(skiplist_t *sl)
{
    sl_node_t *curr = sl->head->next[0];
    while (curr != sl->tail) {
        sl_node_t *tmp = curr->next[0];
        node_destroy(curr);
        curr = tmp;
    }
    node_destroy(sl->head);
    node_destroy(sl->tail);
    free(sl);
}

/* ---- 搜索：纯无锁 ---- */

static int find(skiplist_t *sl, int key,
                sl_node_t *preds[], sl_node_t *succs[])
{
    int found = -1;
    sl_node_t *pred = sl->head;

    for (int level = MAX_LEVEL - 1; level >= 0; level--) {
        sl_node_t *curr = pred->next[level];
        while (curr->key < key) {
            pred = curr;
            curr = pred->next[level];
        }
        if (found == -1 && curr->key == key)
            found = level;
        preds[level] = pred;
        succs[level] = curr;
    }
    return found;
}

int skiplist_contains(skiplist_t *sl, int key)
{
    sl_node_t *preds[MAX_LEVEL], *succs[MAX_LEVEL];
    int found = find(sl, key, preds, succs);
    return (found != -1
            && succs[found]->fully_linked
            && !succs[found]->marked);
}

/* ---- 插入 ---- */

int skiplist_insert(skiplist_t *sl, int key, int value)
{
    int top_level = random_level();

    for (;;) {
        sl_node_t *preds[MAX_LEVEL], *succs[MAX_LEVEL];
        int found = find(sl, key, preds, succs);

        if (found != -1) {
            sl_node_t *node_found = succs[found];
            if (!node_found->marked) {
                /* 等待节点完全链接 */
                while (!node_found->fully_linked)
                    ; /* spin */
                return 0; /* 键已存在 */
            }
            continue; /* 节点正在被删除，重试 */
        }

        /* 按层从低到高加锁，避免死锁 */
        int highest_locked = -1;
        sl_node_t *pred, *succ;
        int valid = 1;

        for (int level = 0; valid && level < top_level; level++) {
            pred = preds[level];
            succ = succs[level];
            pthread_mutex_lock(&pred->lock);
            highest_locked = level;
            /* 验证：pred 未被删除且 pred->next 仍是 succ */
            valid = !pred->marked && !succ->marked
                    && pred->next[level] == succ;
        }

        if (!valid) {
            /* 验证失败，解锁并重试 */
            for (int level = highest_locked; level >= 0; level--)
                pthread_mutex_unlock(&preds[level]->lock);
            continue;
        }

        /* 创建新节点并链接 */
        sl_node_t *new_node = node_create(key, value, top_level);
        for (int level = 0; level < top_level; level++) {
            new_node->next[level] = succs[level];
            preds[level]->next[level] = new_node;
        }
        new_node->fully_linked = 1;

        for (int level = highest_locked; level >= 0; level--)
            pthread_mutex_unlock(&preds[level]->lock);

        return 1;
    }
}

/* ---- 删除 ---- */

static int ok_to_delete(sl_node_t *n, int found_level)
{
    return n->fully_linked
           && n->top_level == found_level + 1
           && !n->marked;
}

int skiplist_remove(skiplist_t *sl, int key)
{
    sl_node_t *victim = NULL;
    int is_marked  = 0;
    int top_level  = -1;

    for (;;) {
        sl_node_t *preds[MAX_LEVEL], *succs[MAX_LEVEL];
        int found = find(sl, key, preds, succs);

        if (is_marked
            || (found != -1 && ok_to_delete(succs[found], found))) {

            if (!is_marked) {
                victim = succs[found];
                top_level = victim->top_level;
                pthread_mutex_lock(&victim->lock);
                if (victim->marked) {
                    pthread_mutex_unlock(&victim->lock);
                    return 0;
                }
                victim->marked = 1;
                is_marked = 1;
            }

            /* 锁住每一层的前驱 */
            int highest_locked = -1;
            int valid = 1;
            sl_node_t *pred;

            for (int level = 0; valid && level < top_level; level++) {
                pred = preds[level];
                pthread_mutex_lock(&pred->lock);
                highest_locked = level;
                valid = !pred->marked
                        && pred->next[level] == victim;
            }

            if (!valid) {
                for (int level = highest_locked; level >= 0; level--)
                    pthread_mutex_unlock(&preds[level]->lock);
                continue; /* 重试 */
            }

            /* 物理断开 */
            for (int level = top_level - 1; level >= 0; level--)
                preds[level]->next[level] = victim->next[level];

            for (int level = highest_locked; level >= 0; level--)
                pthread_mutex_unlock(&preds[level]->lock);
            pthread_mutex_unlock(&victim->lock);

            /* 注意：实际生产中需要安全内存回收（如 hazard pointers）*/
            return 1;
        } else {
            return 0;
        }
    }
}

/* ---- 调试用：打印跳表 ---- */

void skiplist_print(skiplist_t *sl)
{
    printf("=== Skip List ===\n");
    for (int i = MAX_LEVEL - 1; i >= 0; i--) {
        sl_node_t *curr = sl->head->next[i];
        printf("Level %2d: ", i);
        while (curr != sl->tail) {
            printf("%d%s ", curr->key,
                   curr->marked ? "(D)" : "");
            curr = curr->next[i];
        }
        printf("\n");
    }
}

/* ---- 简易测试 ---- */

#define NUM_THREADS  8
#define OPS_PER_THR  10000

typedef struct {
    skiplist_t *sl;
    int         tid;
} thread_arg_t;

static void *worker(void *arg)
{
    thread_arg_t *ta = arg;
    unsigned int seed = (unsigned int)(ta->tid * 1234567);

    for (int i = 0; i < OPS_PER_THR; i++) {
        int key = rand_r(&seed) % (OPS_PER_THR * 2);
        int op  = rand_r(&seed) % 100;

        if (op < 50) {
            skiplist_contains(ta->sl, key);
        } else if (op < 80) {
            skiplist_insert(ta->sl, key, key * 10);
        } else {
            skiplist_remove(ta->sl, key);
        }
    }
    return NULL;
}

int main(void)
{
    srand((unsigned)time(NULL));
    skiplist_t *sl = skiplist_create();

    pthread_t threads[NUM_THREADS];
    thread_arg_t args[NUM_THREADS];

    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);

    for (int i = 0; i < NUM_THREADS; i++) {
        args[i].sl  = sl;
        args[i].tid = i;
        pthread_create(&threads[i], NULL, worker, &args[i]);
    }
    for (int i = 0; i < NUM_THREADS; i++)
        pthread_join(threads[i], NULL);

    clock_gettime(CLOCK_MONOTONIC, &t1);
    double elapsed = (t1.tv_sec - t0.tv_sec)
                   + (t1.tv_nsec - t0.tv_nsec) / 1e9;

    printf("Threads: %d, Ops: %d, Time: %.3f s, Throughput: %.0f ops/s\n",
           NUM_THREADS, NUM_THREADS * OPS_PER_THR,
           elapsed,
           (NUM_THREADS * OPS_PER_THR) / elapsed);

    skiplist_print(sl);
    skiplist_destroy(sl);
    return 0;
}

gcc -O2 -pthread -o concurrent_skiplist concurrent_skiplist.c
./concurrent_skiplist

/* 基准测试框架（概要） */
typedef struct {
    int num_threads;
    int read_pct;      /* 读操作百分比 */
    int insert_pct;    /* 插入操作百分比 */
    int remove_pct;    /* 删除操作百分比 */
    int key_range;     /* 键值范围 */
    int ops_per_thread; /* 每线程操作数 */
} bench_config_t;

void run_benchmark(bench_config_t *cfg, skiplist_t *sl)
{
    pthread_t *threads = malloc(sizeof(pthread_t) * cfg->num_threads);
    /* ... 启动线程，收集结果 ... */
    /* 每个线程根据 read_pct/insert_pct/remove_pct 随机选择操作 */
    free(threads);
}

// 典型的 Go 并发跳表接口
type ConcurrentSkipList[K comparable, V any] interface {
    Get(key K) (V, bool)
    Put(key K, value V) bool
    Delete(key K) bool
    Range(from, to K) []Entry[K, V]
}

use crossbeam_skiplist::SkipMap;

let map = SkipMap::new();
// 可以安全地在多线程间共享
map.insert(1, "one");
map.insert(2, "two");

// 范围查询
for entry in map.range(1..=2) {
    println!("{}: {}", entry.key(), entry.value());
}

#include <folly/ConcurrentSkipList.h>

using SkipList = folly::ConcurrentSkipList<int>;
auto sl = SkipList::createInstance(12); // max height = 12
auto accessor = SkipList::Accessor(sl);
accessor.insert(42);