Java 类java.util.concurrent.atomic.AtomicMarkableReference 实例源码

/**
 * get returns the last values of reference and mark set
 */
public void testGetSet() {
    boolean[] mark = new boolean[1];
    AtomicMarkableReference ai = new AtomicMarkableReference(one, false);
    assertSame(one, ai.getReference());
    assertFalse(ai.isMarked());
    assertSame(one, ai.get(mark));
    assertFalse(mark[0]);
    ai.set(two, false);
    assertSame(two, ai.getReference());
    assertFalse(ai.isMarked());
    assertSame(two, ai.get(mark));
    assertFalse(mark[0]);
    ai.set(one, true);
    assertSame(one, ai.getReference());
    assertTrue(ai.isMarked());
    assertSame(one, ai.get(mark));
    assertTrue(mark[0]);
}

/**
 * compareAndSet succeeds in changing values if equal to expected reference
 * and mark else fails
 */
public void testCompareAndSet() {
    boolean[] mark = new boolean[1];
    AtomicMarkableReference ai = new AtomicMarkableReference(one, false);
    assertSame(one, ai.get(mark));
    assertFalse(ai.isMarked());
    assertFalse(mark[0]);

    assertTrue(ai.compareAndSet(one, two, false, false));
    assertSame(two, ai.get(mark));
    assertFalse(mark[0]);

    assertTrue(ai.compareAndSet(two, m3, false, true));
    assertSame(m3, ai.get(mark));
    assertTrue(mark[0]);

    assertFalse(ai.compareAndSet(two, m3, true, true));
    assertSame(m3, ai.get(mark));
    assertTrue(mark[0]);
}

/**
 * compareAndSet in one thread enables another waiting for reference value
 * to succeed
 */
public void testCompareAndSetInMultipleThreads() throws Exception {
    final AtomicMarkableReference ai = new AtomicMarkableReference(one, false);
    Thread t = new Thread(new CheckedRunnable() {
        public void realRun() {
            while (!ai.compareAndSet(two, three, false, false))
                Thread.yield();
        }});

    t.start();
    assertTrue(ai.compareAndSet(one, two, false, false));
    t.join(LONG_DELAY_MS);
    assertFalse(t.isAlive());
    assertSame(three, ai.getReference());
    assertFalse(ai.isMarked());
}

/**
 * compareAndSet in one thread enables another waiting for mark value
 * to succeed
 */
public void testCompareAndSetInMultipleThreads2() throws Exception {
    final AtomicMarkableReference ai = new AtomicMarkableReference(one, false);
    Thread t = new Thread(new CheckedRunnable() {
        public void realRun() {
            while (!ai.compareAndSet(one, one, true, false))
                Thread.yield();
        }});

    t.start();
    assertTrue(ai.compareAndSet(one, one, false, true));
    t.join(LONG_DELAY_MS);
    assertFalse(t.isAlive());
    assertSame(one, ai.getReference());
    assertFalse(ai.isMarked());
}

/**
 * repeated weakCompareAndSet succeeds in changing values when equal
 * to expected
 */
public void testWeakCompareAndSet() {
    boolean[] mark = new boolean[1];
    AtomicMarkableReference ai = new AtomicMarkableReference(one, false);
    assertSame(one, ai.get(mark));
    assertFalse(ai.isMarked());
    assertFalse(mark[0]);

    do {} while (!ai.weakCompareAndSet(one, two, false, false));
    assertSame(two, ai.get(mark));
    assertFalse(mark[0]);

    do {} while (!ai.weakCompareAndSet(two, m3, false, true));
    assertSame(m3, ai.get(mark));
    assertTrue(mark[0]);
}

/**
 * get returns the last values of reference and mark set
 */
public void testGetSet() {
    boolean[] mark = new boolean[1];
    AtomicMarkableReference ai = new AtomicMarkableReference(one, false);
    assertSame(one, ai.getReference());
    assertFalse(ai.isMarked());
    assertSame(one, ai.get(mark));
    assertFalse(mark[0]);
    ai.set(two, false);
    assertSame(two, ai.getReference());
    assertFalse(ai.isMarked());
    assertSame(two, ai.get(mark));
    assertFalse(mark[0]);
    ai.set(one, true);
    assertSame(one, ai.getReference());
    assertTrue(ai.isMarked());
    assertSame(one, ai.get(mark));
    assertTrue(mark[0]);
}

/**
 * compareAndSet succeeds in changing values if equal to expected reference
 * and mark else fails
 */
public void testCompareAndSet() {
    boolean[] mark = new boolean[1];
    AtomicMarkableReference ai = new AtomicMarkableReference(one, false);
    assertSame(one, ai.get(mark));
    assertFalse(ai.isMarked());
    assertFalse(mark[0]);

    assertTrue(ai.compareAndSet(one, two, false, false));
    assertSame(two, ai.get(mark));
    assertFalse(mark[0]);

    assertTrue(ai.compareAndSet(two, m3, false, true));
    assertSame(m3, ai.get(mark));
    assertTrue(mark[0]);

    assertFalse(ai.compareAndSet(two, m3, true, true));
    assertSame(m3, ai.get(mark));
    assertTrue(mark[0]);
}

/**
 * compareAndSet in one thread enables another waiting for reference value
 * to succeed
 */
public void testCompareAndSetInMultipleThreads() throws Exception {
    final AtomicMarkableReference ai = new AtomicMarkableReference(one, false);
    Thread t = new Thread(new CheckedRunnable() {
        public void realRun() {
            while (!ai.compareAndSet(two, three, false, false))
                Thread.yield();
        }});

    t.start();
    assertTrue(ai.compareAndSet(one, two, false, false));
    t.join(LONG_DELAY_MS);
    assertFalse(t.isAlive());
    assertSame(three, ai.getReference());
    assertFalse(ai.isMarked());
}

/**
 * compareAndSet in one thread enables another waiting for mark value
 * to succeed
 */
public void testCompareAndSetInMultipleThreads2() throws Exception {
    final AtomicMarkableReference ai = new AtomicMarkableReference(one, false);
    Thread t = new Thread(new CheckedRunnable() {
        public void realRun() {
            while (!ai.compareAndSet(one, one, true, false))
                Thread.yield();
        }});

    t.start();
    assertTrue(ai.compareAndSet(one, one, false, true));
    t.join(LONG_DELAY_MS);
    assertFalse(t.isAlive());
    assertSame(one, ai.getReference());
    assertFalse(ai.isMarked());
}

/**
 * repeated weakCompareAndSet succeeds in changing values when equal
 * to expected
 */
public void testWeakCompareAndSet() {
    boolean[] mark = new boolean[1];
    AtomicMarkableReference ai = new AtomicMarkableReference(one, false);
    assertSame(one, ai.get(mark));
    assertFalse(ai.isMarked());
    assertFalse(mark[0]);

    do {} while (!ai.weakCompareAndSet(one, two, false, false));
    assertSame(two, ai.get(mark));
    assertFalse(mark[0]);

    do {} while (!ai.weakCompareAndSet(two, m3, false, true));
    assertSame(m3, ai.get(mark));
    assertTrue(mark[0]);
}

@Override
    public boolean add(T value) {
        while (true) {
//            System.out.print(value);
//            System.out.println(" add");
            NodePair nodePair = find(value); // find place for insert
            Node parent = nodePair.parent, child = nodePair.child;
            // if current is not a tail and it has the same value
            if (child.item != null && child.get().compareTo(value) == 0) { // check for unique
                return false;
            }
            // else add new node
            Node new_node = new Node(value);
            new_node.next = new AtomicMarkableReference<>(child, false);
            // IF (|parent.next| -> |child|) AND (parent.marked = false)
            // THEN (|parent.next| -> |new_node|) AND (new_node.marked = false)
            if (parent.next.compareAndSet(child, new_node, false, false)) {
                return true;
            }

        }
    }

public boolean add(T value) {
    while (true) {
        // find insert position
        NodesPair p = find(value);

        if (p.found != null && p.found.value.compareTo(value) == 0) {
            return false;
        } else {
            // create new node
            ListNode newNode = new ListNode(value, new AtomicMarkableReference<ListNode>(p.found, false));
            // insert with CAS
            if (p.prev.nextRef.compareAndSet(p.found, newNode, false, false)) {
                return true;
            }
        }
    }
}

@Override
public boolean add(T value) {
    while (true) {
        PredCurrPair pair = find(value);
        Node pred = pair.pred;
        Node curr = pair.curr;

        if (curr != null && curr.key.compareTo(value) == 0) {
            return false;
        }

        Node node = new Node(value, new AtomicMarkableReference<>(curr, false));
        if (pred.next.compareAndSet(curr, node, false, false)) {
            return true;
        }
    }
}

@Override
public boolean add(T value) {
    while (true) {
        SlidingWindow<T> window = SlidingWindow.find(head, value);
        Node<T> previous = window.previous,
                current = window.current;
        // добавляемое значение уже существует, возвращаем отказ
        if (current != null && current.value.compareTo(value) == 0) {
            return false;
        }
        // если мы добавили, возвращаем успех
        Node<T> next = new Node<>(value, new AtomicMarkableReference<>(current, false));
        if (previous.next.compareAndSet(current, next, false, false)) {
            return true;
        }
    }
}

Finding(T value) {
    retry: while (true) {
        prev = head;
        curr = head.reference.getReference();
        Node succ;
        while (curr != null) {
            AtomicMarkableReference<Node> ref = curr.reference;
            succ = ref.getReference();
            if (ref.isMarked()) { // try to delete physically
                if (!prev.reference.compareAndSet(curr, succ, false, false)) {
                    continue retry;
                }
                curr = succ;
            } else {
                if (curr.value.compareTo(value) >= 0) return;
                prev = curr;
                curr = succ;
            }
        }
        return;
    }
}

@Override
public boolean add(T value) {
    Node newNode = new Node(value, null);

    while (true) {
        Pair<AtomicMarkableReference<Node>, Node> pair = find(value);
        AtomicMarkableReference<Node> curr = pair.getKey();
        Node next = pair.getValue();

        if (next != null && next.value.equals(value) && !next.next.isMarked()) {
            return false;
        }

        newNode.next.set(next, false);

        if (curr.compareAndSet(next, newNode, false, false))
            return true;
    }
}

@Override
public boolean remove(T value) {
    while (true) {
        Pair<AtomicMarkableReference<Node>, Node> pair = find(value);
        AtomicMarkableReference<Node> prev = pair.getKey();
        Node curr = pair.getValue();

        if (curr == null || !curr.value.equals(value))
            return false;

        Node next = curr.next.getReference();

        if (!curr.next.compareAndSet(next, next, false, true))
            continue;

        prev.compareAndSet(curr, next, false, false);

        return true;
    }
}

private Pair<AtomicMarkableReference<Node>, Node> find(T value) {
    while (true) {
        AtomicMarkableReference<Node> curr = head;
        Node next = head.getReference();

        while (true) {
            if (next == null)
                return new Pair<>(curr, null);

            if (next.next.isMarked()) {
                if (!curr.compareAndSet(next, next.next.getReference(), false, false))
                    break;
                next = next.next.getReference();
            } else {
                if (curr.getReference().value.compareTo(value) >= 0)
                    return new Pair<>(curr, next);
                curr = next.next;
                next = curr.getReference();
            }
        }
    }
}

@Override
public boolean add(T value) {
    while (true) {
        NodePair finded = find(value);
        Node curr = finded.first, prev = finded.second;
        if (curr != null && curr.value.compareTo(value) == 0) {
            return false;
        }

        Node new_node = new Node(value,  new AtomicMarkableReference<Node>(null, false));
        if (prev == null) {
            if (head.compareAndSet(null, new_node, false, false)) {
                size.incrementAndGet();
                return true;
            }
        } else {
            if (prev.next.compareAndSet(curr, new_node, false, false)) {
                size.incrementAndGet();
                return true;
            }
        }
    }
}

public boolean add(T item)
{
    while (true)
    {
        Pair pair_lc = search(item);
        Node left = pair_lc.left;
        Node curr = pair_lc.curr;

        if(curr.item != null && curr.item.compareTo(item) == 0)
            return false;
        else
        {
            Node node = new Node(item);
            node.next = new AtomicMarkableReference(curr, false);

            if (left.next.compareAndSet(curr, node, false, false))
                return true;
        }
    }
}

/**
 * Adds key to the set.
 *
 * Type: lock-free
 *
 * @param value value of the key
 * @return false if key already exists in the set, true if key was successfully added
 */
private boolean add(Value value) {
    while (true) {
        PNode found = find(value);
        Node pred = found.getFirst(), curr = found.getSecond();

        if (curr.getValue().equals(value)) {
            return false;
        }

        Node item = new Node(new AtomicMarkableReference<>(curr, false), value);
        if (pred.getNext().compareAndSet(curr, item, false, false)) {
            return true;
        }
    }
}

@SuppressWarnings({ "unchecked", "rawtypes" })
public boolean add(Integer key) {
    while (true) {
        Window window = find(head, key);
        Node pred = window.pred, curr = window.curr;
        if (curr.key == key) {
            return false;
        } else {
            Node node = new Node(key);
            node.next = new AtomicMarkableReference(curr, false);
            if (pred.next.compareAndSet(curr, node, false, false)) {
                return true;
            }
        }
    }
}

@Test
public void should_create_error_message_for_AtomicMarkableReference() throws Exception {
  // GIVEN
  AtomicMarkableReference<String> actual = new AtomicMarkableReference<>("foo", true);
  // WHEN
  String message = shouldHaveReference(actual, actual.getReference(), "bar").create(TEST_DESCRIPTION,
                                                                                    CONFIGURATION_PROVIDER.representation());
  // THEN
  assertThat(message).isEqualTo(format("[TEST] %n" +
                                       "Expecting%n" +
                                       "  <AtomicMarkableReference[marked=true, reference=\"foo\"]>%n" +
                                       "to have reference:%n" +
                                       "  <\"bar\">%n" +
                                       "but had:%n" +
                                       "  <\"foo\">"));
}

/**
 * constructor initializes to given reference and mark
 */
public void testConstructor() {
    AtomicMarkableReference ai = new AtomicMarkableReference(one, false);
    assertSame(one, ai.getReference());
    assertFalse(ai.isMarked());
    AtomicMarkableReference a2 = new AtomicMarkableReference(null, true);
    assertNull(a2.getReference());
    assertTrue(a2.isMarked());
}

/**
 * attemptMark succeeds in single thread
 */
public void testAttemptMark() {
    boolean[] mark = new boolean[1];
    AtomicMarkableReference ai = new AtomicMarkableReference(one, false);
    assertFalse(ai.isMarked());
    assertTrue(ai.attemptMark(one, true));
    assertTrue(ai.isMarked());
    assertSame(one, ai.get(mark));
    assertTrue(mark[0]);
}

/**
 * constructor initializes to given reference and mark
 */
public void testConstructor() {
    AtomicMarkableReference ai = new AtomicMarkableReference(one, false);
    assertSame(one, ai.getReference());
    assertFalse(ai.isMarked());
    AtomicMarkableReference a2 = new AtomicMarkableReference(null, true);
    assertNull(a2.getReference());
    assertTrue(a2.isMarked());
}

/**
 * attemptMark succeeds in single thread
 */
public void testAttemptMark() {
    boolean[] mark = new boolean[1];
    AtomicMarkableReference ai = new AtomicMarkableReference(one, false);
    assertFalse(ai.isMarked());
    assertTrue(ai.attemptMark(one, true));
    assertTrue(ai.isMarked());
    assertSame(one, ai.get(mark));
    assertTrue(mark[0]);
}

RewatchOnExpireWatcher(ZKClient client, ActionType actionType, String path, Watcher delegate) {
  this.client = client;
  this.actionType = actionType;
  this.path = path;
  this.delegate = delegate;
  this.lastResult = new AtomicMarkableReference<Object>(null, false);
}

@Override
public boolean add(T value) {
    while (true) {
        Finding pair = new Finding(value);
        Node curr = pair.curr;
        if (curr != null && curr.value.compareTo(value) == 0) {
            return false;
        } else {
            Node newNode = new Node(value, new AtomicMarkableReference<>(curr, false));
            if (pair.prev.reference.compareAndSet(curr, newNode, false, false)) {
                return true;
            }
        }
    }
}

@Override
public boolean add(Type key) {
    while (true) {
        NodePair nodePair = find(key);
        Node prev = nodePair.prev();
        Node current = nodePair.current();

        if (current != null && current.getKey().compareTo(key) == 0)
            return false;

        Node node = new Node(new AtomicMarkableReference<Node>(current, false), key);
        if (prev.next().compareAndSet(current, node, false, false))
            return true;
    }
}

@Override
public boolean add(T value) {
    while (true) {
        Pair pair = find(value);
        Node pred = pair.pred;
        Node curr = pair.curr;
        if (curr != null && curr.value.equals(value)) {
            return false;
        }
        Node node = new Node(value, new AtomicMarkableReference<>(curr, false));
        if (pred.next.compareAndSet(curr, node, false, false)) {
            return true;
        }
    }
}

public LockFreeList() {
    Value minValue = new Value(ValueType.MIN);
    Value maxValue = new Value(ValueType.MAX);

    Node tailNode = new Node(new AtomicMarkableReference<>(null, false), maxValue);
    Node headNode = new Node(new AtomicMarkableReference<>(tailNode, false), minValue);
    head = new AtomicMarkableReference<>(headNode, false);
}

/**
 * Find key in the set.
 *
 * Type: wait-free
 *
 * @param value value of the key
 * @return true if key already exists in the set, otherwise false
 */

private boolean contains(Value value) {
    if (value == null) {
        return false;
    }

    AtomicMarkableReference<Node> curr = head;
    while (curr.getReference().getValue().compareTo(value) == -1) {
        curr = curr.getReference().getNext();
    }
    return (curr.getReference().getValue().equals(value) && !curr.isMarked());
}

RewatchOnExpireWatcher(ZKClient client, ActionType actionType, String path, Watcher delegate) {
  this.client = client;
  this.actionType = actionType;
  this.path = path;
  this.delegate = delegate;
  this.lastResult = new AtomicMarkableReference<Object>(null, false);
}

/**
 * Returns standard the {@code toString} representation of the given object. It may or not the object's own
 * implementation of {@code toString}.
 * 
 * @param object the given object.
 * @return the {@code toString} representation of the given object.
 */
@Override
public String toStringOf(Object object) {
  if (object == null) return null;
  if (hasCustomFormatterFor(object)) return customFormat(object);
  if (object instanceof Calendar) return toStringOf((Calendar) object);
  if (object instanceof Class<?>) return toStringOf((Class<?>) object);
  if (object instanceof Date) return toStringOf((Date) object);
  if (object instanceof AtomicBoolean) return toStringOf((AtomicBoolean) object);
  if (object instanceof AtomicInteger) return toStringOf((AtomicInteger) object);
  if (object instanceof AtomicLong) return toStringOf((AtomicLong) object);
  if (object instanceof AtomicReference) return toStringOf((AtomicReference<?>) object);
  if (object instanceof AtomicMarkableReference) return toStringOf((AtomicMarkableReference<?>) object);
  if (object instanceof AtomicStampedReference) return toStringOf((AtomicStampedReference<?>) object);
  if (object instanceof AtomicIntegerFieldUpdater) return AtomicIntegerFieldUpdater.class.getSimpleName();
  if (object instanceof AtomicLongFieldUpdater) return AtomicLongFieldUpdater.class.getSimpleName();
  if (object instanceof AtomicReferenceFieldUpdater) return AtomicReferenceFieldUpdater.class.getSimpleName();
  if (object instanceof Number) return toStringOf((Number) object);
  if (object instanceof File) return toStringOf((File) object);
  if (object instanceof String) return toStringOf((String) object);
  if (object instanceof Character) return toStringOf((Character) object);
  if (object instanceof Comparator) return toStringOf((Comparator<?>) object);
  if (object instanceof SimpleDateFormat) return toStringOf((SimpleDateFormat) object);
  if (object instanceof PredicateDescription) return toStringOf((PredicateDescription) object);
  if (object instanceof CompletableFuture) return toStringOf((CompletableFuture<?>) object);
  if (isArray(object)) return formatArray(object);
  if (object instanceof Collection<?>) return smartFormat((Collection<?>) object);
  if (object instanceof Map<?, ?>) return toStringOf((Map<?, ?>) object);
  if (object instanceof Tuple) return toStringOf((Tuple) object);
  if (object instanceof MapEntry) return toStringOf((MapEntry<?, ?>) object);
  if (object instanceof Method) return ((Method) object).toGenericString();
  if (object instanceof InsertDelta<?>) return toStringOf((InsertDelta<?>) object);
  if (object instanceof ChangeDelta<?>) return toStringOf((ChangeDelta<?>) object);
  if (object instanceof DeleteDelta<?>) return toStringOf((DeleteDelta<?>) object);
  return object == null ? null : fallbackToStringOf(object);
}

@Test
public void should_fail_if_expected_value_is_null_and_does_not_contain_expected_value() throws Exception {
  AtomicMarkableReference<String> actual = new AtomicMarkableReference<>("actual", true);
  thrown.expectAssertionError(shouldHaveReference(actual, actual.getReference(), null).create());

  assertThat(actual).hasReference(null);
}

@Test
public void should_fail_if_atomicMarkableReference_does_not_contain_expected_value() throws Exception {
  AtomicMarkableReference<String> actual = new AtomicMarkableReference<>("actual", true);

  thrown.expectAssertionError(shouldHaveReference(actual, actual.getReference(), expectedValue).create());

  assertThat(actual).hasReference(expectedValue);
}

Node(final T value, final Node next) {
    this.value = value;
    this.next = new AtomicMarkableReference<>(next, false);
}

public SimpleLockFreeSet() {
    head.next = new AtomicMarkableReference<>(tail, false);
    tail.next = new AtomicMarkableReference<>(tail, false);
}

public LockFreeOrderedList() {
    head = new ListNode(null, new AtomicMarkableReference<ListNode>(null, false));
}