You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
|
|
package server.util;
/* !!! WORK IN PROGRESS !!!
trying to implement a wait-free queue */
import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicMarkableReference; import java.util.concurrent.atomic.AtomicReferenceArray;
public class Queue<T> {
private AtomicMarkableReference<Integer> head, tail; private final int capacity; private AtomicReferenceArray<T> items;
public Queue(int capacity) { this.capacity = capacity; this.head = new AtomicMarkableReference(0, false); this.tail = new AtomicMarkableReference(0, false); items = new AtomicReferenceArray<T>(capacity); }
public boolean enq(T x) { boolean[] mark = new boolean[1]; if (tail.get(mark) - head.get(mark) == capacity) return false; int tmp; do { tmp = tail.get(mark); System.out.println("enq: " + x); System.out.println("val tmp: " + tmp); System.out.println("val tmp: " + next(tmp)); items.compareAndSet(tmp, null, x); } while (tail.compareAndSet(tmp, next(tmp), true, false)); System.out.println("head: " + head.getReference() + "\ntail: " + tail.getReference() + "\ndiff: " + (tail.getReference() - head.getReference())); return true; }
public T deq() { boolean[] mark = new boolean[1]; System.out.println("test: " + (tail.get(mark) - head.get(mark)) + "\ncap: " + capacity); if (tail.get(mark) - head.get(mark) == 0) return null; int tmp; T x; do { tmp = head.get(mark); System.out.println("head: " + next(tmp)); x = items.getAndSet(tmp, null); } while (head.compareAndSet(tmp, next(tmp), false, true)); return x; }
private int next(int x) { return (x + 1) % capacity; } }
|