leetcode-go/basis/algorithms/skiplist/java/ConcurrentSkipList.java

import sun.misc.Unsafe;

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;

public class ConcurrentSkipList<K extends Comparable<K>, V> {
    private static Unsafe unsafe = getUnsafe();
    private static long valueOffset;
    private static long nextOffset;
    static {
        try {
            valueOffset = unsafe.objectFieldOffset(Node.class.getDeclaredField("value"));
            nextOffset = unsafe.objectFieldOffset(Node.class.getDeclaredField("next"));
        } catch (Exception e) {
            // Ignore
        }
    }

    private final ThreadLocalRandom random;
    private final int maxLevel;
    private final double p;

    private volatile Index<K, V> head;

    public ConcurrentSkipList(int maxLevel, double p) {
        random = ThreadLocalRandom.current();
        this.maxLevel = maxLevel;
        this.p = p;
        Node<K, V> node = new Node<>(null);
        head = new Index<>(node);
    }
    
    public V put(K key, V value) {
        Stack<Index<K, V>> update = new Stack<>();
        Index<K, V> curr = head;
        while (curr != null) {
            while (curr.right != null && cmp(key, curr.right.node.key) > 0) {
                curr = curr.right;
            }
            update.add(curr);
            curr = curr.down;
        }
        Node<K, V> p = update.peek().node;
        while (p.next != null && cmp(key, p.next.key) >= 0) {
            p = p.next;
        }
        if (p.key != null && cmp(key, p.key) == 0) {
            // update value only
            while (!unsafe.compareAndSwapObject(p, valueOffset, p.value, value)) {
            }
            return value;
        }
        Node<K, V> after = putAfter(p, key, value);
        while (!update.isEmpty()) {
            update.pop();
        }
        return value;
    }

    public boolean containsKey(K key) {
        Index curr = head;
        while (curr != null) {
            while (curr.right != null && cmp(key, curr.right.node.key) > 0) {
                curr = curr.right;
            }
            if (curr.down == null) {
                break;
            } else {
                curr = curr.down;
            }
        }
        Node node = curr.node;
        while (node.next != null && cmp(key, node.next.key) > 0) {
            node = node.next;
        }
        return node.next != null && cmp(key, node.next.key) == 0;
    }

    public V get(K key) {
        Index<K, V> curr = head;
        while (curr != null) {
            while (curr.right != null && cmp(key, curr.right.node.key) > 0) {
                curr = curr.right;
            }
            if (curr.down == null) {
                break;
            } else {
                curr = curr.down;
            }
        }
        Node<K, V> node = curr.node;
        while (node.next != null && cmp(key, node.next.key) > 0) {
            node = node.next;
        }
        node = node.next;
        if (node != null && cmp(key, node.key) == 0) {
            return node.value;
        }
        return null;
    }

    private static Unsafe getUnsafe() {
        try {
            Class<?> unsafeClass = Class.forName("sun.misc.Unsafe");
            Field field = unsafeClass.getDeclaredField("theUnsafe");
            field.setAccessible(true);
            Unsafe unsafe = (Unsafe) field.get(null);
            return unsafe;
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }

    private Node<K, V> putAfter(Node<K, V> before, K key, V value) {
        Node<K, V> after = new Node<>(key, value);
        while (true) {
            Node<K, V> next = before.next;
            after.next = next;
            if (unsafe.compareAndSwapObject(before, nextOffset, next, after)) {
                break;
            }
        }
        return after;
    }

    private int cmp(Object o1, Object o2) {
        return ((Comparable) o1).compareTo((Comparable) o2);
    }

    public static void main(String[] args) {
        ConcurrentSkipList<Integer, String> skipList = new ConcurrentSkipList<>(20, 0.2);
        skipList.put(1, "answer");
        System.out.println(skipList.get(1));
    }

    private static class Node<K, V> {
        private K key;
        private V value;
        private Node<K, V> next;

        private Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        private Node(Node<K, V> next) {
            this.next = next;
        }
    }

    private static class Index<K, V> {
        private Node<K, V> node;
        private Index<K, V> down;
        private Index<K, V> right;

        private Index(Node<K, V> node) {
            this.node = node;
        }
    }
}