/**
 * This constructor is only used internally to instantiate a Chunk without a creator and a min-key.
 * The caller should set the creator and min-key before returning the Chunk to the user.
 */
private Chunk(int maxItems, AtomicInteger externalSize, MemoryManager memoryManager, OakComparator<K> comparator,
              OakSerializer<K> keySerializer, OakSerializer<V> valueSerializer, ValueUtils valueOperator) {
    this.maxItems = maxItems;
    this.externalSize = externalSize;
    this.comparator = comparator;
    this.entrySet = new EntrySet<>(memoryManager, maxItems, keySerializer, valueSerializer, valueOperator);
    // if not zero, sorted count keeps the entry index of the last
    // subsequent and ordered entry in the entries array
    this.sortedCount = new AtomicInteger(0);
    this.minKey = new KeyBuffer();
    this.creator = new AtomicReference<>(null);
    this.state = new AtomicReference<>(State.NORMAL);
    this.next = new AtomicMarkableReference<>(null, false);
    this.pendingOps = new AtomicInteger();
    this.rebalancer = new AtomicReference<>(null); // to be updated on rebalance
    this.statistics = new Statistics();
}
 

/**
 * 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 item) {
    int key = item.hashCode();
    while (true) {
        Window window = find(head, key);
        Node<T> pred = window.pred, curr = window.curr;
        if (curr.key == key) {
            return false;
        } else {
            Node<T> node = new Node<>(item);
            node.next = new AtomicMarkableReference<>(curr, false);
            if (pred.next.compareAndSet(curr, node, false, false)) {
                return true;
            }
        }
    }
}
 

public void pushRight(T x) {
    Node node = new Node(x, null, null);
    Node next = tail;
    Node prev = next.prev.getReference();
    while (true) {
        if (!prev.next.compareAndSet(next, next, false, false)) {
            // concurrent push inserted -> get new prev
            prev = helpInsert(prev, next, "concurrentPushRight");
            continue;
        }
        // 0 push step
        node.prev = new AtomicMarkableReference<>(prev, false);
        node.next = new AtomicMarkableReference<>(next, false);
        // 1 push step
        if (prev.next.compareAndSet(next, node, false, false)) {
            break;
        }
    }
    // 2 push step
    pushCommon(node, next);
}
 

public void pushLeft(T x) {
    Node node = new Node(x, null, null);
    Node prev = head;
    Node next = prev.next.getReference();
    while (true) {
        if (!prev.next.compareAndSet(next, next, false, false)) {
            next = prev.next.getReference();
            continue;
        }
        node.prev = new AtomicMarkableReference<>(prev, false);
        node.next = new AtomicMarkableReference<>(next, false);

        if (prev.next.compareAndSet(next, node, false, false)) {
            break;
        }
    }
    pushCommon(node, next);
}
 

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

public static void main(String[] args) throws InterruptedException {

        final AtomicMarkableReference<String> amr = new AtomicMarkableReference<>(INIT_TEXT, false);

        ExecutorService executorService = Executors.newFixedThreadPool(3);
        for (int i = 0; i < 10; i++) {
            executorService.submit(new Runnable() {
                @Override
                public void run() {
                    try {
                        Thread.sleep(Math.abs((int) (Math.random() * 100)));
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }

                    String name = Thread.currentThread().getName();
                    if (amr.compareAndSet(INIT_TEXT, name, amr.isMarked(), !amr.isMarked())) {
                        System.out.println(Thread.currentThread().getName() + " 修改了对象！");
                        System.out.println("新的对象为：" + amr.getReference());
                    }
                }
            });
        }

        executorService.shutdown();
        executorService.awaitTermination(3, TimeUnit.SECONDS);
    }
 

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

private void pushCommon(Node node, Node next) {
    while (true) {
        AtomicMarkableReference<Node> link1 = next.prev;
        if (link1.isMarked() || !node.next.compareAndSet(next, next, false, false)) {
            break;
        }
        if (next.prev.compareAndSet(link1.getReference(), node, false, false)) {
            if (node.prev.isMarked()) {
                helpInsert(node, next, "pushCommon");
            }
            break;
        }
    }
}
 

private void markPrev(Node node) {
    while (true) {
        AtomicMarkableReference<Node> link1 = node.prev;
        if (link1.isMarked() || node.prev.compareAndSet(link1.getReference(), link1.getReference(), false, true)) {
            break;
        }
    }
}
 

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

@Test
void givenMarkValueAsTrue_whenUsingIsMarkedMethod_thenMarkValueShouldBeTrue() {
    Employee employee = new Employee(123, "Mike");
    AtomicMarkableReference<Employee> employeeNode = new AtomicMarkableReference<Employee>(employee, true);

    Assertions.assertTrue(employeeNode.isMarked());
}
 

@Test
void givenMarkValueAsFalse_whenUsingIsMarkedMethod_thenMarkValueShouldBeFalse() {
    Employee employee = new Employee(123, "Mike");
    AtomicMarkableReference<Employee> employeeNode = new AtomicMarkableReference<Employee>(employee, false);

    Assertions.assertFalse(employeeNode.isMarked());
}
 

@Test
void whenUsingGetReferenceMethod_thenCurrentReferenceShouldBeReturned() {
    Employee employee = new Employee(123, "Mike");
    AtomicMarkableReference<Employee> employeeNode = new AtomicMarkableReference<Employee>(employee, true);

    Assertions.assertEquals(employee, employeeNode.getReference());
}
 

@Test
void whenUsingGetMethod_thenCurrentReferenceAndMarkShouldBeReturned() {
    Employee employee = new Employee(123, "Mike");
    AtomicMarkableReference<Employee> employeeNode = new AtomicMarkableReference<Employee>(employee, true);

    boolean[] markHolder = new boolean[1];
    Employee currentEmployee = employeeNode.get(markHolder);

    Assertions.assertEquals(employee, currentEmployee);
    Assertions.assertTrue(markHolder[0]);
}
 

@Test
void givenNewReferenceAndMark_whenUsingSetMethod_thenCurrentReferenceAndMarkShouldBeUpdated() {
    Employee employee = new Employee(123, "Mike");
    AtomicMarkableReference<Employee> employeeNode = new AtomicMarkableReference<Employee>(employee, true);

    Employee newEmployee = new Employee(124, "John");
    employeeNode.set(newEmployee, false);

    Assertions.assertEquals(newEmployee, employeeNode.getReference());
    Assertions.assertFalse(employeeNode.isMarked());
}
 

@Test
void givenTheSameObjectReference_whenUsingAttemptMarkMethod_thenMarkShouldBeUpdated() {
    Employee employee = new Employee(123, "Mike");
    AtomicMarkableReference<Employee> employeeNode = new AtomicMarkableReference<Employee>(employee, true);

    Assertions.assertTrue(employeeNode.attemptMark(employee, false));
    Assertions.assertFalse(employeeNode.isMarked());
}
 

@Test
void givenDifferentObjectReference_whenUsingAttemptMarkMethod_thenMarkShouldNotBeUpdated() {
    Employee employee = new Employee(123, "Mike");
    AtomicMarkableReference<Employee> employeeNode = new AtomicMarkableReference<Employee>(employee, true);
    Employee expectedEmployee = new Employee(123, "Mike");

    Assertions.assertFalse(employeeNode.attemptMark(expectedEmployee, false));
    Assertions.assertTrue(employeeNode.isMarked());
}
 

@Test
void givenCurrentReferenceAndCurrentMark_whenUsingCompareAndSet_thenReferenceAndMarkShouldBeUpdated() {
    Employee employee = new Employee(123, "Mike");
    AtomicMarkableReference<Employee> employeeNode = new AtomicMarkableReference<Employee>(employee, true);
    Employee newEmployee = new Employee(124, "John");

    Assertions.assertTrue(employeeNode.compareAndSet(employee, newEmployee, true, false));
    Assertions.assertEquals(newEmployee, employeeNode.getReference());
    Assertions.assertFalse(employeeNode.isMarked());
}