Will the add() method of theLockFreeSkipList work even ifthe bottom level is lin
ID: 3575072 • Letter: W
Question
Will the add() method of theLockFreeSkipList work even ifthe bottom level is linked and then all other levels are linked in some arbitrary order? Is the same true for the marking of the next references in the remove() method: the bottom level next reference is marked last, but references at all other levels are marked in an arbitrary order?
Code for LockFreeSkipList (from textbook):
public final class LockFreeSkipList<T> {
static final int MAX_LEVEL = ...;
final Node<T> head = new Node<T>(Integer.MIN_VALUE);
final Node<T> tail = new Node<T>(Integer.MAX_VALUE);
public LockFreeSkipList() {
for(int i - 0; i < head.next.length; i++) {
head.next[i] = new AtomicMarkableReference<LockFreeSkipList.Node<T>>(tail, false);
}
}
public static final class Node<T> {
final T value; final int key;
final AtomicMarkableReference<Node<T>>[] next;
private int topLevel;
public Node(int key) {
value = null; key = key;
next = (AtomicMarkableReference<Node<T>>[])new AtomicMarkableReference[MAX_LEVEL + 1];
for(int i = 0; i < next.lenght; i++) {
next[i] = new AtomicMarkableReference<Node<T>>(null, false);
}
topLevel = MAX_LEVEL;
}
public Node(T x, int height) {
value = x;
key = x.hashCode();
next = (AtomicMarkableReference<Node<T>>[])new AtomicMarkableReference[MAX_LEVEL + 1];
for(int i = 0; i < next.lenght; i++) {
next[i] = new AtomicMarkableReference<Node<T>>(null, false);
}
topLevel = height;
}
}
boolean add(T x) {
int topLevel = randomLevel();
int bottomLevel = 0;
Node<T>[] preds = (Node<T>[]) new Node[MAX_LEVEL + 1];
Node<T>[] succs = (Node<T>[]) new Node[MAX_LEVEL + 1];
while (true) {
boolean found = find(x, preds, succs);
if(found) {
return false;
} else {
Node<T> newNode - new Node(x, topLevel);
for(int level = bottomLevel; level <= topLevel; level++) {
Node<T> succ = succs[level];
newNode.next[level].set(succ, false);
}
Node<T> pred = preds[bottomLevel];
Node<T> succ = succs[bottomLevel];
if(!pred.next[bottomLevel].compareAndSet(succ, newNode, false, false)) {
continue;
}
for(int level = bottomLevel + 1; level <= topLevel; level++) {
while (true) {
pred = preds[level];
succ = succs[level];
if(pred.next[level].compareAndSet(succ, newNode, false, false))
break;
find(x, preds, succs);
}
}
return true;
}
}
}
boolean remove(T x) {
int bottomLevel = 0;
Node<T>[] preds = (Node<T>[]) new Node[MAX_LEVEL + 1];
Node<T>[] succs = (Node<T>[]) new Node[MAX_LEVEL + 1];
while (true) {
boolean found = find(x, preds, succs);
if(!found) {
return false;
} else {
Node<T> nodeToRemove = succs[bottomLevel];
for(int level = nodeToRemove.topLevel; level >= bottomLevel + 1; level--) {
boolean[] marked = {false};
succ = nodeToRemove.next[level].get(marked);
while(!marked[0]) {
nodeToRemove.next[level].compareAndSet(succ, succ, false, true);
succ = nodeToRemove.next[level].get(marked);
}
}
boolean[] marked = {false};
succ = nodeToRemove.next[bottomLevel].get(marked);
while(true) {
boolean iMarkedIt = nodeToRemove.next[bottomLevel].compareAndSet(succ, succ, false, true);
succ = succs[bottomLevel].next[bottomLevel].get(marked);
if(iMarkedIt) {
find(x, preds, succs);
return true;
}
else if (marks[0]) return false;
}
}
}
}
boolean find(T x, Node<T>[] preds, Node<T>[] succs) {
int bottomLevel = 0;
int key = x.hashCode();
boolean[] marked = {false};
boolean snip;
Node<T> pred = null, curr = null, succ = null;
retry:
while(true) {
pred = head;
for(int level = MAX_LEVEL; level >= bottomLevel; level--) {
curr = pred.next[level].getReference();
while(true) {
succ = curr.next[level].get(marked);
while(marked[0]) {
snip = pred.next[level].compareAndSet(curr, succ, false, false);
if(!snip) continue retry;
curr = pred.next[level].getReference();
succ = curr.next[level].get(marked);
}
if (curr.key < key) {
pred = curr; curr = succ;
} else {
break;
}
}
preds[level] = pred;
succs[level] = curr;
}
return(curr.key == key);
}
}
}
Explanation / Answer
import java.util.concurrent.atomic.AtomicMarkableReference;
import com.sun.electric.tool.util.concurrent.runtime.MultiThreadedRandomizer;
@Deprecated
public class SkipList<T> extends IStructure<T>
{
private static final int MAX_LEVEL = 4;
private MultiThreadedRandomizer randomizer;
private final Node<T> head = new Node<T>(Integer.MAX_VALUE);
@SuppressWarnings("unused")
private final Node<T> tail = new Node<T>(Integer.MAX_VALUE);
public SkipList() {
randomizer = new MultiThreadedRandomizer(0);
for (int i = 0; i < head.next.length; i++) {
head.next[i] = new AtomicMarkableReference<Node<T>>(null, false);
}
}
@SuppressWarnings("unchecked")
@Override
public void add(T item) {
int topLevel = randomLevel();
int bottomLevel = 0;
Node<T>[] preds = (Node<T>[]) new Node[MAX_LEVEL + 1];
Node<T>[] succs = (Node<T>[]) new Node[MAX_LEVEL + 1];
while (true) {
boolean found = find(item, preds, succs);
if (!found) {
Node<T> newNode = new Node<T>(item, topLevel);
for (int level = bottomLevel; level <= topLevel; level++) {
Node<T> succ = succs[level];
newNode.next[level].set(succ, false);
}
Node<T> succ = succs[bottomLevel];
Node<T> pred = preds[bottomLevel];
newNode.next[bottomLevel].set(succ, false);
if (!pred.next[bottomLevel].compareAndSet(succ, newNode, false, false))
continue;
for (int level = bottomLevel + 1; level <= topLevel; level++) {
while (true) {
pred = preds[level];
succ = succs[level];
if (pred.next[level].compareAndSet(succ, newNode, false, false)) {
break;
}
find(item, preds, succs);
}
}
return;
} else {
return;
}
}
}
private boolean find(T item, Node<T>[] preds, Node<T>[] succs) {
int bottomLevel = 0;
int key = item.hashCode();
boolean[] marked = { false };
boolean snip;
Node<T> pred = null, curr = null, succ = null;
retry: while (true) {
pred = head;
for (int level = MAX_LEVEL; level >= bottomLevel; level--) {
curr = pred.next[level].getReference();
while (true) {
succ = curr.next[level].get(marked);
while (marked[0]) {
snip = pred.next[level].compareAndSet(curr, succ, false, false);
if (!snip)
continue retry;
curr = pred.next[level].getReference();
succ = curr.next[level].get(marked);
}
if(curr.key < key) {
pred = curr;
curr = succ;
} else {
break;
}
}
preds[level] = pred;
succs[level] = curr;
}
return (curr.key == key);
}
}
private int randomLevel() {
return randomizer.getRandomizer().nextInt(MAX_LEVEL + 1);
}
@Override
public boolean isEmpty() {
return false;
}
@Override
public T remove() {
return null;
}
public static final class Node<T> {
@SuppressWarnings("unused")
private final T value;
private final int key;
private final AtomicMarkableReference<Node<T>>[] next;
@SuppressWarnings("unused")
private int topLevel;
@SuppressWarnings("unchecked")
public Node(int key) {
this.value = null;
this.key = key;
this.next = (AtomicMarkableReference<Node<T>>[]) new AtomicMarkableReference[MAX_LEVEL + 1];
for (int i = 0; i < next.length; i++)
next[i] = new AtomicMarkableReference<Node<T>>(null, false);
topLevel = MAX_LEVEL;
}
@SuppressWarnings("unchecked")
public Node(T x, int height) {
value = x;
key = x.hashCode();
this.next = (AtomicMarkableReference<Node<T>>[]) new AtomicMarkableReference[height + 1];
for (int i = 0; i < next.length; i++)
next[i] = new AtomicMarkableReference<Node<T>>(null, false);
topLevel = height;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.