concurrent/LinkedTransferQueue/WhiteBox.java

/*
 * Written by Martin Buchholz with assistance from members of JCP
 * JSR-166 Expert Group and released to the public domain, as
 * explained at http://creativecommons.org/publicdomain/zero/1.0/
 */

/*
 * @test
 * @modules java.base/java.util.concurrent:open
 * @run testng WhiteBox
 * @summary White box tests of implementation details
 */

import static org.testng.Assert.*;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.LinkedTransferQueue;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import static java.util.stream.Collectors.toList;
import java.util.function.Consumer;

@Test
public class WhiteBox {
    final ThreadLocalRandom rnd = ThreadLocalRandom.current();
    final VarHandle HEAD, TAIL, ITEM, NEXT;

    public WhiteBox() throws ReflectiveOperationException {
        Class<?> qClass = LinkedTransferQueue.class;
        Class<?> nodeClass = Class.forName(qClass.getName() + "$Node");
        MethodHandles.Lookup lookup
            = MethodHandles.privateLookupIn(qClass, MethodHandles.lookup());
        HEAD = lookup.findVarHandle(qClass, "head", nodeClass);
        TAIL = lookup.findVarHandle(qClass, "tail", nodeClass);
        NEXT = lookup.findVarHandle(nodeClass, "next", nodeClass);
        ITEM = lookup.findVarHandle(nodeClass, "item", Object.class);
    }

    Object head(LinkedTransferQueue q) { return HEAD.getVolatile(q); }
    Object tail(LinkedTransferQueue q) { return TAIL.getVolatile(q); }
    Object item(Object node)           { return ITEM.getVolatile(node); }
    Object next(Object node)           { return NEXT.getVolatile(node); }

    int nodeCount(LinkedTransferQueue q) {
        int i = 0;
        for (Object p = head(q); p != null; ) {
            i++;
            if (p == (p = next(p))) p = head(q);
        }
        return i;
    }

    int tailCount(LinkedTransferQueue q) {
        int i = 0;
        for (Object p = tail(q); p != null; ) {
            i++;
            if (p == (p = next(p))) p = head(q);
        }
        return i;
    }

    Object findNode(LinkedTransferQueue q, Object e) {
        for (Object p = head(q); p != null; ) {
            if (item(p) != null && e.equals(item(p)))
                return p;
            if (p == (p = next(p))) p = head(q);
        }
        throw new AssertionError("not found");
    }

    Iterator iteratorAt(LinkedTransferQueue q, Object e) {
        for (Iterator it = q.iterator(); it.hasNext(); )
            if (it.next().equals(e))
                return it;
        throw new AssertionError("not found");
    }

    void assertIsSelfLinked(Object node) {
        assertSame(next(node), node);
        assertNull(item(node));
    }
    void assertIsNotSelfLinked(Object node) {
        assertNotSame(node, next(node));
    }

    @Test
    public void addRemove() {
        LinkedTransferQueue q = new LinkedTransferQueue();
        assertInvariants(q);
        assertNull(next(head(q)));
        assertNull(item(head(q)));
        q.add(1);
        assertEquals(nodeCount(q), 2);
        assertInvariants(q);
        q.remove(1);
        assertEquals(nodeCount(q), 1);
        assertInvariants(q);
    }

    /**
     * Traversal actions that visit every node and do nothing, but
     * have side effect of squeezing out dead nodes.
     */
    @DataProvider
    public Object[][] traversalActions() {
        return List.<Consumer<LinkedTransferQueue>>of(
            q -> q.forEach(e -> {}),
            q -> assertFalse(q.contains(new Object())),
            q -> assertFalse(q.remove(new Object())),
            q -> q.spliterator().forEachRemaining(e -> {}),
            q -> q.stream().collect(toList()),
            q -> assertFalse(q.removeIf(e -> false)),
            q -> assertFalse(q.removeAll(List.of())))
            .stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
    }

    @Test(dataProvider = "traversalActions")
    public void traversalOperationsCollapseLeadingNodes(
        Consumer<LinkedTransferQueue> traversalAction) {
        LinkedTransferQueue q = new LinkedTransferQueue();
        Object oldHead;
        int n = 1 + rnd.nextInt(5);
        for (int i = 0; i < n; i++) q.add(i);
        assertEquals(nodeCount(q), n + 1);
        oldHead = head(q);
        traversalAction.accept(q);
        assertInvariants(q);
        assertEquals(nodeCount(q), n);
        assertIsSelfLinked(oldHead);
    }

    @Test(dataProvider = "traversalActions")
    public void traversalOperationsCollapseInteriorNodes(
        Consumer<LinkedTransferQueue> traversalAction) {
        LinkedTransferQueue q = new LinkedTransferQueue();
        int n = 6;
        for (int i = 0; i < n; i++) q.add(i);

        // We must be quite devious to reliably create an interior dead node
        Object p0 = findNode(q, 0);
        Object p1 = findNode(q, 1);
        Object p2 = findNode(q, 2);
        Object p3 = findNode(q, 3);
        Object p4 = findNode(q, 4);
        Object p5 = findNode(q, 5);

        Iterator it1 = iteratorAt(q, 1);
        Iterator it2 = iteratorAt(q, 2);

        it2.remove(); // causes it2's ancestor to advance to 1
        assertSame(next(p1), p3);
        assertSame(next(p2), p3);
        assertNull(item(p2));
        it1.remove(); // removes it2's ancestor
        assertSame(next(p0), p3);
        assertSame(next(p1), p3);
        assertSame(next(p2), p3);
        assertNull(item(p1));
        assertEquals(it2.next(), 3);
        it2.remove(); // it2's ancestor can't unlink

        assertSame(next(p0), p3); // p3 is now interior dead node
        assertSame(next(p1), p4); // it2 uselessly CASed p1.next
        assertSame(next(p2), p3);
        assertSame(next(p3), p4);
        assertInvariants(q);

        int c = nodeCount(q);
        traversalAction.accept(q);
        assertEquals(nodeCount(q), c - 1);

        assertSame(next(p0), p4);
        assertSame(next(p1), p4);
        assertSame(next(p2), p3);
        assertSame(next(p3), p4);
        assertInvariants(q);

        // trailing nodes are not unlinked
        Iterator it5 = iteratorAt(q, 5); it5.remove();
        traversalAction.accept(q);
        assertSame(next(p4), p5);
        assertNull(next(p5));
        assertEquals(nodeCount(q), c - 1);
    }

    /**
     * Checks that traversal operations collapse a random pattern of
     * dead nodes as could normally only occur with a race.
     */
    @Test(dataProvider = "traversalActions")
    public void traversalOperationsCollapseRandomNodes(
        Consumer<LinkedTransferQueue> traversalAction) {
        LinkedTransferQueue q = new LinkedTransferQueue();
        int n = rnd.nextInt(6);
        for (int i = 0; i < n; i++) q.add(i);
        ArrayList nulledOut = new ArrayList();
        for (Object p = head(q); p != null; p = next(p))
            if (rnd.nextBoolean()) {
                nulledOut.add(item(p));
                ITEM.setVolatile(p, null);
            }
        traversalAction.accept(q);
        int c = nodeCount(q);
        assertEquals(q.size(), c - (q.contains(n - 1) ? 0 : 1));
        for (int i = 0; i < n; i++)
            assertTrue(nulledOut.contains(i) ^ q.contains(i));
    }

    /**
     * Traversal actions that remove every element, and are also
     * expected to squeeze out dead nodes.
     */
    @DataProvider
    public Object[][] bulkRemovalActions() {
        return List.<Consumer<LinkedTransferQueue>>of(
            q -> q.clear(),
            q -> assertTrue(q.removeIf(e -> true)),
            q -> assertTrue(q.retainAll(List.of())))
            .stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
    }

    @Test(dataProvider = "bulkRemovalActions")
    public void bulkRemovalOperationsCollapseNodes(
        Consumer<LinkedTransferQueue> bulkRemovalAction) {
        LinkedTransferQueue q = new LinkedTransferQueue();
        int n = 1 + rnd.nextInt(5);
        for (int i = 0; i < n; i++) q.add(i);
        bulkRemovalAction.accept(q);
        assertEquals(nodeCount(q), 1);
        assertInvariants(q);
    }

    /**
     * Actions that remove the first element, and are expected to
     * leave at most one slack dead node at head.
     */
    @DataProvider
    public Object[][] pollActions() {
        return List.<Consumer<LinkedTransferQueue>>of(
            q -> assertNotNull(q.poll()),
            q -> { try { assertNotNull(q.poll(1L, TimeUnit.DAYS)); }
                catch (Throwable x) { throw new AssertionError(x); }},
            q -> { try { assertNotNull(q.take()); }
                catch (Throwable x) { throw new AssertionError(x); }},
            q -> assertNotNull(q.remove()))
            .stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
    }

    @Test(dataProvider = "pollActions")
    public void pollActionsOneNodeSlack(
        Consumer<LinkedTransferQueue> pollAction) {
        LinkedTransferQueue q = new LinkedTransferQueue();
        int n = 1 + rnd.nextInt(5);
        for (int i = 0; i < n; i++) q.add(i);
        assertEquals(nodeCount(q), n + 1);
        for (int i = 0; i < n; i++) {
            int c = nodeCount(q);
            boolean slack = item(head(q)) == null;
            if (slack) assertNotNull(item(next(head(q))));
            pollAction.accept(q);
            assertEquals(nodeCount(q), q.isEmpty() ? 1 : c - (slack ? 2 : 0));
        }
        assertInvariants(q);
    }

    /**
     * Actions that append an element, and are expected to
     * leave at most one slack node at tail.
     */
    @DataProvider
    public Object[][] addActions() {
        return List.<Consumer<LinkedTransferQueue>>of(
            q -> q.add(1),
            q -> q.offer(1))
            .stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
    }

    @Test(dataProvider = "addActions")
    public void addActionsOneNodeSlack(
        Consumer<LinkedTransferQueue> addAction) {
        LinkedTransferQueue q = new LinkedTransferQueue();
        int n = 1 + rnd.nextInt(9);
        for (int i = 0; i < n; i++) {
            boolean slack = next(tail(q)) != null;
            addAction.accept(q);
            if (slack)
                assertNull(next(tail(q)));
            else {
                assertNotNull(next(tail(q)));
                assertNull(next(next(tail(q))));
            }
            assertInvariants(q);
        }
    }

    byte[] serialBytes(Object o) {
        try {
            ByteArrayOutputStream bos = new ByteArrayOutputStream();
            ObjectOutputStream oos = new ObjectOutputStream(bos);
            oos.writeObject(o);
            oos.flush();
            oos.close();
            return bos.toByteArray();
        } catch (Exception fail) {
            throw new AssertionError(fail);
        }
    }

    @SuppressWarnings("unchecked")
    <T> T serialClone(T o) {
        try {
            ObjectInputStream ois = new ObjectInputStream
                (new ByteArrayInputStream(serialBytes(o)));
            T clone = (T) ois.readObject();
            assertNotSame(o, clone);
            assertSame(o.getClass(), clone.getClass());
            return clone;
        } catch (Exception fail) {
            throw new AssertionError(fail);
        }
    }

    @Test
    public void testSerialization() {
        LinkedTransferQueue q = serialClone(new LinkedTransferQueue());
        assertInvariants(q);
    }

    /** Checks conditions which should always be true. */
    void assertInvariants(LinkedTransferQueue q) {
        assertNotNull(head(q));
        assertNotNull(tail(q));
        // head is never self-linked (but tail may!)
        for (Object h; next(h = head(q)) == h; )
            assertNotSame(h, head(q)); // must be update race
    }
}
Revision:	1.12
Committed:	Fri Jun 5 11:10:33 2020 UTC (4 years ago) by dl
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.11:	+0 -34 lines
Log Message:	Remove now-inappplicable test
#	Content
1	/*
2	* Written by Martin Buchholz with assistance from members of JCP
3	* JSR-166 Expert Group and released to the public domain, as
4	* explained at http://creativecommons.org/publicdomain/zero/1.0/
5	*/
6
7	/*
8	* @test
9	* @modules java.base/java.util.concurrent:open
10	* @run testng WhiteBox
11	* @summary White box tests of implementation details
12	*/
13
14	import static org.testng.Assert.*;
15	import org.testng.annotations.DataProvider;
16	import org.testng.annotations.Test;
17
18	import java.io.ByteArrayInputStream;
19	import java.io.ByteArrayOutputStream;
20	import java.io.ObjectInputStream;
21	import java.io.ObjectOutputStream;
22	import java.lang.invoke.MethodHandles;
23	import java.lang.invoke.VarHandle;
24	import java.util.ArrayList;
25	import java.util.Iterator;
26	import java.util.List;
27	import java.util.concurrent.LinkedTransferQueue;
28	import java.util.concurrent.ThreadLocalRandom;
29	import java.util.concurrent.TimeUnit;
30	import static java.util.stream.Collectors.toList;
31	import java.util.function.Consumer;
32
33	@Test
34	public class WhiteBox {
35	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
36	final VarHandle HEAD, TAIL, ITEM, NEXT;
37
38	public WhiteBox() throws ReflectiveOperationException {
39	Class<?> qClass = LinkedTransferQueue.class;
40	Class<?> nodeClass = Class.forName(qClass.getName() + "$Node");
41	MethodHandles.Lookup lookup
42	= MethodHandles.privateLookupIn(qClass, MethodHandles.lookup());
43	HEAD = lookup.findVarHandle(qClass, "head", nodeClass);
44	TAIL = lookup.findVarHandle(qClass, "tail", nodeClass);
45	NEXT = lookup.findVarHandle(nodeClass, "next", nodeClass);
46	ITEM = lookup.findVarHandle(nodeClass, "item", Object.class);
47	}
48
49	Object head(LinkedTransferQueue q) { return HEAD.getVolatile(q); }
50	Object tail(LinkedTransferQueue q) { return TAIL.getVolatile(q); }
51	Object item(Object node) { return ITEM.getVolatile(node); }
52	Object next(Object node) { return NEXT.getVolatile(node); }
53
54	int nodeCount(LinkedTransferQueue q) {
55	int i = 0;
56	for (Object p = head(q); p != null; ) {
57	i++;
58	if (p == (p = next(p))) p = head(q);
59	}
60	return i;
61	}
62
63	int tailCount(LinkedTransferQueue q) {
64	int i = 0;
65	for (Object p = tail(q); p != null; ) {
66	i++;
67	if (p == (p = next(p))) p = head(q);
68	}
69	return i;
70	}
71
72	Object findNode(LinkedTransferQueue q, Object e) {
73	for (Object p = head(q); p != null; ) {
74	if (item(p) != null && e.equals(item(p)))
75	return p;
76	if (p == (p = next(p))) p = head(q);
77	}
78	throw new AssertionError("not found");
79	}
80
81	Iterator iteratorAt(LinkedTransferQueue q, Object e) {
82	for (Iterator it = q.iterator(); it.hasNext(); )
83	if (it.next().equals(e))
84	return it;
85	throw new AssertionError("not found");
86	}
87
88	void assertIsSelfLinked(Object node) {
89	assertSame(next(node), node);
90	assertNull(item(node));
91	}
92	void assertIsNotSelfLinked(Object node) {
93	assertNotSame(node, next(node));
94	}
95
96	@Test
97	public void addRemove() {
98	LinkedTransferQueue q = new LinkedTransferQueue();
99	assertInvariants(q);
100	assertNull(next(head(q)));
101	assertNull(item(head(q)));
102	q.add(1);
103	assertEquals(nodeCount(q), 2);
104	assertInvariants(q);
105	q.remove(1);
106	assertEquals(nodeCount(q), 1);
107	assertInvariants(q);
108	}
109
110	/**
111	* Traversal actions that visit every node and do nothing, but
112	* have side effect of squeezing out dead nodes.
113	*/
114	@DataProvider
115	public Object[][] traversalActions() {
116	return List.<Consumer<LinkedTransferQueue>>of(
117	q -> q.forEach(e -> {}),
118	q -> assertFalse(q.contains(new Object())),
119	q -> assertFalse(q.remove(new Object())),
120	q -> q.spliterator().forEachRemaining(e -> {}),
121	q -> q.stream().collect(toList()),
122	q -> assertFalse(q.removeIf(e -> false)),
123	q -> assertFalse(q.removeAll(List.of())))
124	.stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
125	}
126
127	@Test(dataProvider = "traversalActions")
128	public void traversalOperationsCollapseLeadingNodes(
129	Consumer<LinkedTransferQueue> traversalAction) {
130	LinkedTransferQueue q = new LinkedTransferQueue();
131	Object oldHead;
132	int n = 1 + rnd.nextInt(5);
133	for (int i = 0; i < n; i++) q.add(i);
134	assertEquals(nodeCount(q), n + 1);
135	oldHead = head(q);
136	traversalAction.accept(q);
137	assertInvariants(q);
138	assertEquals(nodeCount(q), n);
139	assertIsSelfLinked(oldHead);
140	}
141
142	@Test(dataProvider = "traversalActions")
143	public void traversalOperationsCollapseInteriorNodes(
144	Consumer<LinkedTransferQueue> traversalAction) {
145	LinkedTransferQueue q = new LinkedTransferQueue();
146	int n = 6;
147	for (int i = 0; i < n; i++) q.add(i);
148
149	// We must be quite devious to reliably create an interior dead node
150	Object p0 = findNode(q, 0);
151	Object p1 = findNode(q, 1);
152	Object p2 = findNode(q, 2);
153	Object p3 = findNode(q, 3);
154	Object p4 = findNode(q, 4);
155	Object p5 = findNode(q, 5);
156
157	Iterator it1 = iteratorAt(q, 1);
158	Iterator it2 = iteratorAt(q, 2);
159
160	it2.remove(); // causes it2's ancestor to advance to 1
161	assertSame(next(p1), p3);
162	assertSame(next(p2), p3);
163	assertNull(item(p2));
164	it1.remove(); // removes it2's ancestor
165	assertSame(next(p0), p3);
166	assertSame(next(p1), p3);
167	assertSame(next(p2), p3);
168	assertNull(item(p1));
169	assertEquals(it2.next(), 3);
170	it2.remove(); // it2's ancestor can't unlink
171
172	assertSame(next(p0), p3); // p3 is now interior dead node
173	assertSame(next(p1), p4); // it2 uselessly CASed p1.next
174	assertSame(next(p2), p3);
175	assertSame(next(p3), p4);
176	assertInvariants(q);
177
178	int c = nodeCount(q);
179	traversalAction.accept(q);
180	assertEquals(nodeCount(q), c - 1);
181
182	assertSame(next(p0), p4);
183	assertSame(next(p1), p4);
184	assertSame(next(p2), p3);
185	assertSame(next(p3), p4);
186	assertInvariants(q);
187
188	// trailing nodes are not unlinked
189	Iterator it5 = iteratorAt(q, 5); it5.remove();
190	traversalAction.accept(q);
191	assertSame(next(p4), p5);
192	assertNull(next(p5));
193	assertEquals(nodeCount(q), c - 1);
194	}
195
196	/**
197	* Checks that traversal operations collapse a random pattern of
198	* dead nodes as could normally only occur with a race.
199	*/
200	@Test(dataProvider = "traversalActions")
201	public void traversalOperationsCollapseRandomNodes(
202	Consumer<LinkedTransferQueue> traversalAction) {
203	LinkedTransferQueue q = new LinkedTransferQueue();
204	int n = rnd.nextInt(6);
205	for (int i = 0; i < n; i++) q.add(i);
206	ArrayList nulledOut = new ArrayList();
207	for (Object p = head(q); p != null; p = next(p))
208	if (rnd.nextBoolean()) {
209	nulledOut.add(item(p));
210	ITEM.setVolatile(p, null);
211	}
212	traversalAction.accept(q);
213	int c = nodeCount(q);
214	assertEquals(q.size(), c - (q.contains(n - 1) ? 0 : 1));
215	for (int i = 0; i < n; i++)
216	assertTrue(nulledOut.contains(i) ^ q.contains(i));
217	}
218
219	/**
220	* Traversal actions that remove every element, and are also
221	* expected to squeeze out dead nodes.
222	*/
223	@DataProvider
224	public Object[][] bulkRemovalActions() {
225	return List.<Consumer<LinkedTransferQueue>>of(
226	q -> q.clear(),
227	q -> assertTrue(q.removeIf(e -> true)),
228	q -> assertTrue(q.retainAll(List.of())))
229	.stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
230	}
231
232	@Test(dataProvider = "bulkRemovalActions")
233	public void bulkRemovalOperationsCollapseNodes(
234	Consumer<LinkedTransferQueue> bulkRemovalAction) {
235	LinkedTransferQueue q = new LinkedTransferQueue();
236	int n = 1 + rnd.nextInt(5);
237	for (int i = 0; i < n; i++) q.add(i);
238	bulkRemovalAction.accept(q);
239	assertEquals(nodeCount(q), 1);
240	assertInvariants(q);
241	}
242
243	/**
244	* Actions that remove the first element, and are expected to
245	* leave at most one slack dead node at head.
246	*/
247	@DataProvider
248	public Object[][] pollActions() {
249	return List.<Consumer<LinkedTransferQueue>>of(
250	q -> assertNotNull(q.poll()),
251	q -> { try { assertNotNull(q.poll(1L, TimeUnit.DAYS)); }
252	catch (Throwable x) { throw new AssertionError(x); }},
253	q -> { try { assertNotNull(q.take()); }
254	catch (Throwable x) { throw new AssertionError(x); }},
255	q -> assertNotNull(q.remove()))
256	.stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
257	}
258
259	@Test(dataProvider = "pollActions")
260	public void pollActionsOneNodeSlack(
261	Consumer<LinkedTransferQueue> pollAction) {
262	LinkedTransferQueue q = new LinkedTransferQueue();
263	int n = 1 + rnd.nextInt(5);
264	for (int i = 0; i < n; i++) q.add(i);
265	assertEquals(nodeCount(q), n + 1);
266	for (int i = 0; i < n; i++) {
267	int c = nodeCount(q);
268	boolean slack = item(head(q)) == null;
269	if (slack) assertNotNull(item(next(head(q))));
270	pollAction.accept(q);
271	assertEquals(nodeCount(q), q.isEmpty() ? 1 : c - (slack ? 2 : 0));
272	}
273	assertInvariants(q);
274	}
275
276	/**
277	* Actions that append an element, and are expected to
278	* leave at most one slack node at tail.
279	*/
280	@DataProvider
281	public Object[][] addActions() {
282	return List.<Consumer<LinkedTransferQueue>>of(
283	q -> q.add(1),
284	q -> q.offer(1))
285	.stream().map(x -> new Object[]{ x }).toArray(Object[][]::new);
286	}
287
288	@Test(dataProvider = "addActions")
289	public void addActionsOneNodeSlack(
290	Consumer<LinkedTransferQueue> addAction) {
291	LinkedTransferQueue q = new LinkedTransferQueue();
292	int n = 1 + rnd.nextInt(9);
293	for (int i = 0; i < n; i++) {
294	boolean slack = next(tail(q)) != null;
295	addAction.accept(q);
296	if (slack)
297	assertNull(next(tail(q)));
298	else {
299	assertNotNull(next(tail(q)));
300	assertNull(next(next(tail(q))));
301	}
302	assertInvariants(q);
303	}
304	}
305
306	byte[] serialBytes(Object o) {
307	try {
308	ByteArrayOutputStream bos = new ByteArrayOutputStream();
309	ObjectOutputStream oos = new ObjectOutputStream(bos);
310	oos.writeObject(o);
311	oos.flush();
312	oos.close();
313	return bos.toByteArray();
314	} catch (Exception fail) {
315	throw new AssertionError(fail);
316	}
317	}
318
319	@SuppressWarnings("unchecked")
320	<T> T serialClone(T o) {
321	try {
322	ObjectInputStream ois = new ObjectInputStream
323	(new ByteArrayInputStream(serialBytes(o)));
324	T clone = (T) ois.readObject();
325	assertNotSame(o, clone);
326	assertSame(o.getClass(), clone.getClass());
327	return clone;
328	} catch (Exception fail) {
329	throw new AssertionError(fail);
330	}
331	}
332
333	@Test
334	public void testSerialization() {
335	LinkedTransferQueue q = serialClone(new LinkedTransferQueue());
336	assertInvariants(q);
337	}
338
339	/** Checks conditions which should always be true. */
340	void assertInvariants(LinkedTransferQueue q) {
341	assertNotNull(head(q));
342	assertNotNull(tail(q));
343	// head is never self-linked (but tail may!)
344	for (Object h; next(h = head(q)) == h; )
345	assertNotSame(h, head(q)); // must be update race
346	}
347	}