我已经实现了一个惰性锁定跳过列表，就像在“多处理器编程的艺术”一书中一样。但我想增加跳过列表以通过索引访问其元素。这样做我已经编写了这个类（它可以立即运行，只需复制/粘贴）但我的索引访问在多线程模式下仍然失败。
编辑1：
实际上这是一个正在运行的版本！但我必须锁定所有级别直到MAX_LEVEL，而不是当前节点toplevel。所以如果我能摆脱和之间的锁，我会很toplevel高兴MAX_LEVEL。
import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import java.util.Set;
import java.util.concurrent.ConcurrentSkipListSet;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantLock;
public class IndexedSkipList10<T extends Comparable<? super T>> {
private static class SkipNode<T extends Comparable<? super T>> {
final ReentrantLock lock = new ReentrantLock();
private final T data;
private final SkipNode<T>[] next;
private final SkipNode<T>[] prev;
private final AtomicInteger[] span;
private volatile boolean marked = false;
private volatile boolean fullyLinked = false;
public SkipNode (T data, int level) {
this.data = data;
next = new SkipNode[level];
prev = new SkipNode[level];
span = new AtomicInteger[level];
for (int i=0; i<span.length; i++) span[i] = new AtomicInteger(1);
}
public void lock() {
lock.lock();
}
public void unlock() {
lock.unlock();
}
@Override
public String toString() {
return data == null ? "HEAD" : data.toString();
}
}
private class SearchResult {
private final SkipNode<T>[] preds, succs;
private final int[] index;
private final int[] predSpans;
private final int ind, foundLevel;
public SearchResult(SkipNode<T>[] preds, SkipNode<T>[] succs, int[] index, int ind, int foundLevel, int[] predSpans) {
this.preds = preds;
this.succs = succs;
this.index = index;
this.predSpans = predSpans;
this.ind = ind;
this.foundLevel = foundLevel;
}
}
/* Global vars */
private SkipNode<T> head;
private AtomicInteger size = new AtomicInteger(0);
private static final double P = 0.5; //Pugh's skiplist cookbook.
private final int MAX_LEVEL;
public final Random random = new Random();
public IndexedSkipList10(int level) {
this.MAX_LEVEL = level;
head = new SkipNode<T>(null, level);
// set head pointers and distance
for(int i = 0; i < level; i++) {
head.next[i] = head;
head.prev[i] = head;
head.span[i].set(1);
}
// set fully linked
head.fullyLinked = true;
}
private SearchResult find2(T key, int topLevel) {
SkipNode<T>[] preds = new SkipNode[MAX_LEVEL];
SkipNode<T>[] succs = new SkipNode[MAX_LEVEL];
int[] predSpans = new int[MAX_LEVEL];
int[] index = new int[topLevel];
SkipNode<T> curr, pred = head;
int ind = 0, foundLevel = -1;
for(int i = MAX_LEVEL - 1; i >= 0; i--) {
curr = pred.next[i];
while(curr != head && curr.data.compareTo(key) < 0) {
if (i < topLevel) ind += pred.span[i].get();
pred = curr;
curr = pred.next[i];
}
if (foundLevel == -1 && curr.data != null && curr.data.equals(key))
foundLevel = i;
predSpans[i] = pred.span[i].get();
preds[i] = pred;
succs[i] = curr;
if (i < topLevel) index[i] = ind;
}
return new SearchResult(preds, succs, index, ind, foundLevel, predSpans);
}
public boolean insert(T value) {
if(value == null)
return false;
final int topLevel = randomLevel();
SkipNode<T>[] succs, preds;
int[] predSpans, indexes;
SkipNode succ, pred;
entry: while (true) {
//SearchResult found = findOLD(value);
SearchResult found = find2(value, topLevel);
preds = found.preds;
succs = found.succs;
predSpans = found.predSpans;
if (found.foundLevel != -1) {
// this exact same element (key) is already in the list, we need to check if it is not being removed
// and wait until it is fully linked
if (!preds[found.foundLevel].marked) {
while (!preds[found.foundLevel].fullyLinked) {
}
//TODO: in case of Map.Entry preds the value here
return false;
}
continue;
}
int highestLocked = -1;
try {
boolean valid = true;
// lock all preds
// FIXME I would like to get rid of the locks i > toplevel
for (int level = 0; valid && (level < MAX_LEVEL); level++) {
pred = preds[level];
succ = succs[level];
pred.lock();
highestLocked = level;
valid = !pred.marked && !succ.marked && pred.next[level] == succ && pred.span[level].get() == predSpans[level];
}
if (!valid) continue;
// Link Nodes
SkipNode nwNode = new SkipNode<T>(value, topLevel);
for (int i = 0; i < topLevel; i++) {
nwNode.next[i] = succs[i];
preds[i].next[i] = nwNode;
// Set Backlink
nwNode.prev[i] = preds[i];
nwNode.next[i].prev[i] = nwNode;
}
// calculate spans
for (int i = 0; i < MAX_LEVEL; i++) {
if (i >= topLevel) {
preds[i].span[i].incrementAndGet();
} else if (i > 0) {
nwNode.span[i].set(found.index[i] + preds[i].span[i].get() - found.ind);
preds[i].span[i].set(found.ind + 1 - found.index[i]);
} else {
// lowest node spans are always one, we have initilized the node span beeing one so nothing to do here!
}
}
// successful add linearization point
nwNode.fullyLinked = true;
size.incrementAndGet();
return true;
} finally {
for (int level = 0; level <= highestLocked; level++)
preds[level].unlock();
}
}
}
protected int randomLevel() {
int x = random.nextInt() | 0x100; //256
x ^= x << 13;
x ^= x >>> 17;
x ^= x << 5;
if ((x & 0x8001) != 0) // test highest and lowest bits
return 1;
int level = 1;
while (((x >>>= 1) & 1) != 0) ++level;
return Math.min(level+1, MAX_LEVEL-1);
}
private SkipNode<T> searchByIndex(int index) {
if(index > size.get())
return null;
SkipNode<T> curr = head;
int ind = -1;
for (int i = MAX_LEVEL - 1; i >= 0; i--) {
while (ind + curr.span[i].get() <= index) {
ind += curr.span[i].get();
curr = curr.next[i];
}
}
return curr;
}
public Iterator<T> iterator() {
return new Iterator<T>() {
SkipNode n = head;
@Override
public boolean hasNext() {
return n.next[0].data != null;
}
@Override
public T next() {
return (T) (n = n.next[0]).data;
}
};
}
public Iterator<T> iteratorDesc() {
return new Iterator<T>() {
SkipNode n = head;
@Override
public boolean hasNext() {
return n.prev[0].data != null;
}
@Override
public T next() {
return (T) (n = n.prev[0]).data;
}
};
}
public int size() {
return size.get();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
Iterator<T> it = iterator();
while (it.hasNext())
sb.append(it.next()).append(", ");
if (sb.length() > 2)
sb.setLength(sb.length()-2);
return sb.append("]").toString();
}
public static void main(String[] args) throws InterruptedException {
int[] threads = new int[]{1, 5, 10, 15, 25, 50, 75, 100, 200, 500, 1000};
IndexedSkipList10<Integer> b = new IndexedSkipList10<>(5);
b.insert(12);
b.insert(11);
b.insert(15);
b.insert(16);
b.insert(13);
b.insert(10);
b.insert(19);
b.insert(18);
System.out.println(b.searchByIndex(2));
System.out.println(b.searchByIndex(5));
for (int threadCount : threads) {
System.out.println("\n----\ntesting with " + threadCount + " threads!");
ExecutorService es = Executors.newFixedThreadPool(threadCount);
IndexedSkipList10<Integer> a = new IndexedSkipList10<>(32);
ConcurrentSkipListSet<Integer> controll = new ConcurrentSkipListSet<>();
for (int i = 0; i < 50000; i++) {
es.execute(() -> {
int rnd = new Random().nextInt();
a.insert(rnd);
controll.add(rnd);
});
}
es.shutdown();
es.awaitTermination(1L, TimeUnit.DAYS);
System.out.println(controll);
System.out.println(a);
int cnt = 0;
Set<Integer> uniques = new HashSet<>();
Iterator<Integer> itSize = a.iterator();
while (itSize.hasNext()) {
int i = itSize.next();
cnt++;
if (!uniques.add(i))
throw new RuntimeException("Duplicate Element: " + i);
}
System.out.println("\nTest Size");
if (a.size() != cnt)
throw new RuntimeException("Size not equal! exepected: " + cnt + " got: " + a.size());
if (a.size() != controll.size())
throw new RuntimeException("Size not equal! exepected: " + controll.size() + " got: " + a.size());
// Controll Results
System.out.println("\nTest iterator");
Iterator<Integer> ita = a.iterator();
Iterator<Integer> itControl = controll.iterator();
int i = 0;
while (ita.hasNext()) {
Integer dataA = ita.next();
Integer dataControll = itControl.next();
Integer aByIndex = a.searchByIndex(i++).data;
if (!dataControll.equals(dataA))
throw new RuntimeException("Element not equal! " + dataControll + " != " + dataA);
// temporary disable index tests until we have fixed the "normal" skiplist concurrency
if (!dataControll.equals(aByIndex)) throw new RuntimeException("Element by Index not equal! " + dataControll + " != " + aByIndex + " Index: " + (i-1) + " threads: " + threadCount);
}
if (itControl.hasNext() || itControl.hasNext())
throw new RuntimeException("Iterators not equal");
// Controll Results in descending mode
System.out.println("\nTest desc iterator");
ita = a.iteratorDesc();
itControl = controll.descendingIterator();
i = a.size();
while (ita.hasNext()) {
Integer dataA = ita.next();
Integer dataControll = itControl.next();
Integer aByIndex = a.searchByIndex(--i).data;
if (!dataControll.equals(dataA))
throw new RuntimeException("Desc Element not equal! " + dataControll + " != " + dataA);
//temporary disable index tests until we have fixed the "normal" skiplist concurrency
if (!dataControll.equals(aByIndex)) throw new RuntimeException("Desc Element by Index not equal! " + dataControll + " != " + aByIndex);
}
if (itControl.hasNext() || ita.hasNext())
throw new RuntimeException("Desc Iterator not equal");
}
System.out.println("\nFIN");
}
}