Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package faaqueue;
- import kotlinx.atomicfu.*;
- import static faaqueue.FAAQueue.Node.NODE_SIZE;
- public class FAAQueue<T> implements Queue<T> {
- private static final Object DONE = new Object(); // Marker for the "DONE" slot state; to avoid memory leaks
- private AtomicRef<Node> head; // Head pointer, similarly to the Michael-Scott queue (but the first node is _not_ sentinel)
- private AtomicRef<Node> tail; // Tail pointer, similarly to the Michael-Scott queue
- public FAAQueue() {
- Node firstNode = new Node();
- head = new AtomicRef<>(firstNode);
- tail = new AtomicRef<>(firstNode);
- }
- @Override
- public void enqueue(T x) {
- while (true) {
- int enqIdx = tail.getValue().enqIdx.getAndAdd(1);
- if (enqIdx >= NODE_SIZE) {
- Node curTail = tail.getValue();
- Node newTail = new Node(x);
- if (tail.getValue().next.compareAndSet(null, newTail)) {
- if (tail.compareAndSet(curTail, newTail)) {
- //
- System.out.println(333);
- }
- } else {
- continue;
- }
- } else {
- if (tail.getValue().data.get(enqIdx).compareAndSet(null, x)) {
- return;
- }
- }
- }
- // int enqIdx = tail.getValue().enqIdx++;
- // if (enqIdx >= NODE_SIZE) {
- // Node newTail = new Node(x);
- // this.tail.getValue().next = newTail;
- // this.tail.setValue(newTail);
- // return;
- // }
- // this.tail.getValue().data[enqIdx] = x;
- }
- @Override
- public T dequeue() {
- while (true) {
- Node curHead = head.getValue();
- if (curHead.isEmpty()) {
- Node curHeadNext = curHead.next.getValue();
- if (curHeadNext == null) {
- return null;
- }
- head.compareAndSet(curHead, curHeadNext);
- } else {
- int deqIdx = head.getValue().deqIdx.getAndAdd(1);
- if (deqIdx >= NODE_SIZE) {
- continue;
- }
- Object res = head.getValue().data.get(deqIdx).getAndSet(DONE);
- if (res == null) continue;
- return (T) res;
- }
- }
- // while (true) {
- // if (this.head.getValue().isEmpty()) {
- // if (this.head.getValue().next == null) return null;
- // this.head.setValue(this.head.getValue().next);
- // continue;
- // }
- // int deqIdx = this.head.getValue().deqIdx++;
- // Object res = head.getValue().data[deqIdx];
- // head.getValue().data[deqIdx] = DONE;
- // return (T) res;
- // }
- }
- static class Node {
- static final int NODE_SIZE = 2; // CHANGE ME FOR BENCHMARKING ONLY
- private AtomicRef<Node> next = new AtomicRef<>(null);
- private AtomicInt enqIdx = new AtomicInt(0); // index for the next enqueue operation
- private AtomicInt deqIdx = new AtomicInt(0); // index for the next dequeue operation
- private final AtomicArray<Object> data = new AtomicArray<>(NODE_SIZE);
- Node() {
- }
- Node(Object x) {
- enqIdx.setValue(1);
- data.get(0).setValue(x);
- }
- private boolean isEmpty() {
- return deqIdx.getValue() >= enqIdx.getValue() ||
- deqIdx.getValue() >= NODE_SIZE;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement