/** * 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]); }
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()); }
/** * 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)); }
