看到一篇文章,关于非阻塞算法的链表:
其代码如下:
(详细见:http://www-128.ibm.com/developerworks/cn/java/j-jtp04186/)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<Node<E>>(next);
}
}
private AtomicReference<Node<E>> head
= new AtomicReference<Node<E>>(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 */;
}
}
}
}
}我测试了下,发现有个问题:插入数据后,链表头部和尾部始终相同。我改造如下,是否会有什么问题,即是否线程安全。另外添加了一个变量:size, 为AtomicInteger型。
主要列出put方法: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 */ ;
////////////////////////////这里设置size
while(true){
int value = size.get();
if(size.compareAndSet(value, value + 1))
break;
}
break;
}
} else {
tail.compareAndSet(curTail, residue) /* B */;
}
}
}
/////////这里修改头部
if(head == tail){
AtomicReference<Node<E>> newHead = new AtomicReference<Node<E>>(new Node<E>(null,null));
newHead.get().next.set(newNode);
if(head == tail)
head = newHead;
}
return true;
}我的修改是否可行?或者还有什么其他方法?请详细说明。
欢迎讨论!
其代码如下:
(详细见:http://www-128.ibm.com/developerworks/cn/java/j-jtp04186/)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<Node<E>>(next);
}
}
private AtomicReference<Node<E>> head
= new AtomicReference<Node<E>>(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 */;
}
}
}
}
}我测试了下,发现有个问题:插入数据后,链表头部和尾部始终相同。我改造如下,是否会有什么问题,即是否线程安全。另外添加了一个变量:size, 为AtomicInteger型。
主要列出put方法: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 */ ;
////////////////////////////这里设置size
while(true){
int value = size.get();
if(size.compareAndSet(value, value + 1))
break;
}
break;
}
} else {
tail.compareAndSet(curTail, residue) /* B */;
}
}
}
/////////这里修改头部
if(head == tail){
AtomicReference<Node<E>> newHead = new AtomicReference<Node<E>>(new Node<E>(null,null));
newHead.get().next.set(newNode);
if(head == tail)
head = newHead;
}
return true;
}我的修改是否可行?或者还有什么其他方法?请详细说明。
欢迎讨论!
解决方案 »
免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货