我正在尝试无锁链表。这是我的第一枪,但我不知道为什么即使在调试器中可以看到值,toString方法也总是返回空字符串。
package com.linkedq;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicReference;
public class LinkedQueue <E> {
private static class Node <E> {
final E item;
final AtomicReference<Node<E>> next;
Node(E item, Node<E> next) {
this.item = item;
this.next = new AtomicReference<>(next);
}
@Override
public String toString() {
return item.toString();
}
}
private AtomicReference<Node<E>> head = new AtomicReference<>(new Node<E>(null, null));
private AtomicReference<Node<E>> tail = head;
public boolean put(E item) {
Node<E> newNode = new Node<E>(item, null);
while (true) {
Node<E> curTail = tail.get();
Node<E> residue = curTail.next.get();
if (curTail == tail.get()) {
if (residue == null) /* A */ {
if (curTail.next.compareAndSet(null, newNode)) /* C */ {
tail.compareAndSet(curTail, newNode) /* D */ ;
return true;
}
} else {
tail.compareAndSet(curTail, residue) /* B */;
}
}
}
}
public void remove(E item) {
Node<E> current = this.head.get().next.get();
Node<E> next = null;
while (current != null) {
next = current.next.get();
if (next.equals(item)) {
if (!current.next.compareAndSet(next, next.next.get())) {
// some other thread changed the list, do a retry
remove(item);
}
}
current = next;
}
}
@Override
public String toString() {
Node<E> current = head.get().next.get();
StringBuilder sb = new StringBuilder();
while (current != null) {
sb.append(current).append(", ");
current = current.next.get();
}
return sb.toString();
}
public static void main(String[] args) throws InterruptedException {
final ExecutorService es = Executors.newFixedThreadPool(10);
final LinkedQueue<Integer> q = new LinkedQueue<>();
for (int i=0; i<10000; i++) {
es.execute(new Inserter(q, i));
}
// es.shutdown();
// es.awaitTermination(1L, TimeUnit.HOURS);
System.out.println("FIN" + q);
}
private static class Inserter implements Runnable {
private final LinkedQueue<Integer> q;
private final int value;
public Inserter(LinkedQueue<Integer> q, int value) {
this.q = q;
this.value = value;
}
@Override
public void run() {
q.put(value);
System.out.println("q = " + q);
}
}
}
至少一个明显的错误是您head
和tail
实际上是同一AtomicReference
对象,因此,当您更新时tail
,head
也会被更新。采用
private AtomicReference<Node<E>> head = new AtomicReference<>(new Node<E>(null, null));
private AtomicReference<Node<E>> tail = new AtomicReference<>(head.get());
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句