util/Collections/RacingCollections.java

/*
 * Copyright (c) 2006, 2010, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

/*
 * @test
 * @bug 6360946 6360948
 * @summary Test various operations on concurrently mutating collections
 * @author Martin Buchholz
 */

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Vector;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.ConcurrentSkipListSet;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.CopyOnWriteArraySet;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.LinkedTransferQueue;

import static java.util.Collections.asLifoQueue;
import static java.util.Collections.checkedList;
import static java.util.Collections.checkedMap;
import static java.util.Collections.checkedSet;
import static java.util.Collections.newSetFromMap;
import static java.util.Collections.synchronizedList;
import static java.util.Collections.synchronizedMap;
import static java.util.Collections.synchronizedSet;
import static java.util.Collections.unmodifiableList;
import static java.util.Collections.unmodifiableMap;
import static java.util.Collections.unmodifiableSet;

public class RacingCollections {
    /**
     * How long to run each "race" (in milliseconds).
     * Turn this up to some higher value like 1000 for stress testing:
     * java -Dmillis=1000 RacingCollections
     */
    static final long defaultWorkTimeMillis = Long.getLong("millis", 10L);

    /**
     * Whether to print debug information.
     */
    static final boolean debug = Boolean.getBoolean("debug");

    static final Integer one = 1;
    static final Integer two = 2;

    /**
     * A thread that mutates an object forever, alternating between
     * being empty and containing singleton "two"
     */
    static class Frobber extends CheckedThread {
        volatile boolean done = false;
        boolean keepGoing(int i) { return (i % 128 != 0) || ! done; }

        final Object elLoco;
        Frobber(Object elLoco) {
            this.elLoco = elLoco;
            this.start();
        }

        @SuppressWarnings("unchecked")
        void clear(Object o) {
            if (o instanceof Collection)
                ((Collection<?>)o).clear();
            else
                ((Map<?,?>)o).clear();
        }

        @SuppressWarnings("unchecked")
        void realRun() {
            // Mutate elLoco wildly forever, checking occasionally for "done"
            clear(elLoco);
            if (elLoco instanceof List) {
                List<Integer> l = (List<Integer>) elLoco;
                for (int i = 0; keepGoing(i); i++) {
                    switch (i%2) {
                    case 0: l.add(two);    break;
                    case 1: l.add(0, two); break;
                    }
                    switch (i%2) {
                    case 0: l.remove(two); break;
                    case 1: l.remove(0);   break;
                    }}}
            else if (elLoco instanceof Deque) {
                Deque<Integer> q = (Deque<Integer>) elLoco;
                for (int i = 0; keepGoing(i); i++) {
                    switch (i%6) {
                    case 0: q.add(two);        break;
                    case 1: q.addFirst(two);   break;
                    case 2: q.addLast(two);    break;
                    case 3: q.offer(two);      break;
                    case 4: q.offerFirst(two); break;
                    case 5: q.offerLast(two);  break;
                    }
                    switch (i%6) {
                    case 0: q.remove(two);     break;
                    case 1: q.removeFirst();   break;
                    case 2: q.removeLast();    break;
                    case 3: q.poll();          break;
                    case 4: q.pollFirst();     break;
                    case 5: q.pollLast();      break;
                    }}}
            else if (elLoco instanceof Queue) {
                Queue<Integer> q = (Queue<Integer>) elLoco;
                for (int i = 0; keepGoing(i); i++) {
                    switch (i%2) {
                    case 0: q.add(two);    break;
                    case 1: q.offer(two);  break;
                    }
                    switch (i%2) {
                    case 0: q.remove(two); break;
                    case 1: q.poll();      break;
                    }}}
            else if (elLoco instanceof Map) {
                Map<Integer, Boolean> m = (Map<Integer, Boolean>) elLoco;
                for (int i = 0; keepGoing(i); i++) {
                    m.put(two, true);
                    m.remove(two);
                }}
            else if (elLoco instanceof Collection) {
                Collection<Integer> c = (Collection<Integer>) elLoco;
                for (int i = 0; keepGoing(i); i++) {
                    c.add(two);
                    c.remove(two);
                }}
            else { throw new Error("Huh? " + elLoco); }
        }

        void enoughAlready() {
            done = true;
            try { join(); } catch (Throwable t) { unexpected(t); }
        }
    }

    private static void checkEqualSanity(Object theRock, Object elLoco) {
        //equal(theRock, theRock);
        equal(elLoco, elLoco);

        // It would be nice someday to have theRock and elLoco never "equal",
        // although the meaning of "equal" for mutating collections
        // is a bit fuzzy.  Uncomment when/if we fix:
        // 6374942: Improve thread safety of collection .equals() methods
        //notEqual(theRock, elLoco);
        //notEqual(elLoco, theRock);

        notEqual(theRock.toString(), elLoco.toString());
    }

    static class Looper {
        final long quittingTime;
        int i = 0;
        Looper() { this(defaultWorkTimeMillis); }
        Looper(long workTimeMillis) {
            quittingTime = System.nanoTime() + workTimeMillis * 1024 * 1024;
        }
        boolean keepGoing() {
            return (i++ % 128 != 0) || (System.nanoTime() - quittingTime < 0);
        }
    }

    private static void frob(Object theRock, Object elLoco) {
        Frobber frobber = new Frobber(elLoco);
        try {
            if (theRock instanceof Collection) {
                @SuppressWarnings("unchecked")
                Collection<Integer> c = (Collection<Integer>) theRock;
                if (! c.contains(one))
                    c.add(one);
            } else {
                @SuppressWarnings("unchecked")
                Map<Integer, Boolean> m = (Map<Integer, Boolean>) theRock;
                if (! m.containsKey(one))
                    m.put(one, true);
            }
            for (Looper looper = new Looper(); looper.keepGoing(); )
                checkEqualSanity(theRock, elLoco);
        }
        catch (Throwable t) { unexpected(t); }
        finally { frobber.enoughAlready(); }
    }

    private static List<Map<Integer, Boolean>> newConcurrentMaps() {
        List<Map<Integer, Boolean>> list = new ArrayList<>();
        list.add(new ConcurrentHashMap<Integer, Boolean>());
        list.add(new ConcurrentSkipListMap<Integer, Boolean>());
        return list;
    }

    private static List<Map<Integer, Boolean>> maps() {
        List<Map<Integer, Boolean>> list = newConcurrentMaps();
        list.add(new Hashtable<Integer, Boolean>());
        list.add(new HashMap<Integer, Boolean>());
        list.add(new TreeMap<Integer, Boolean>());
        Comparator<Integer> cmp = new Comparator<>() {
            public int compare(Integer x, Integer y) {
                return x - y;
            }};
        list.add(new TreeMap<Integer, Boolean>(Collections.reverseOrder(cmp)));
        return list;
    }

    private static List<Set<Integer>> newConcurrentSets() {
        List<Set<Integer>> list = new ArrayList<>();
        list.add(new ConcurrentSkipListSet<Integer>());
        list.add(new CopyOnWriteArraySet<Integer>());
        return list;
    }

    private static List<Set<Integer>> newSets() {
        List<Set<Integer>> list = newConcurrentSets();
        list.add(new HashSet<Integer>());
        list.add(new TreeSet<Integer>());
        list.add(new TreeSet<Integer>(Collections.reverseOrder()));
        return list;
    }

    private static List<List<Integer>> newConcurrentLists() {
        List<List<Integer>> list = new ArrayList<>();
        list.add(new CopyOnWriteArrayList<Integer>());
        return list;
    }

    private static List<List<Integer>> newLists() {
        List<List<Integer>> list = newConcurrentLists();
        list.add(new Vector<Integer>());
        list.add(new ArrayList<Integer>());
        return list;
    }

    private static List<Queue<Integer>> newConcurrentQueues() {
        List<Queue<Integer>> list = new ArrayList<>(newConcurrentDeques());
        list.add(new ArrayBlockingQueue<Integer>(10));
        list.add(new LinkedBlockingQueue<Integer>(10));
        list.add(new LinkedTransferQueue<Integer>());
        list.add(new ConcurrentLinkedQueue<Integer>());
        return list;
    }

    private static List<Queue<Integer>> newQueues() {
        List<Queue<Integer>> list = new ArrayList<>(newDeques());
        list.add(new LinkedBlockingQueue<Integer>(10));
        return list;
    }

    private static List<Deque<Integer>> newConcurrentDeques() {
        List<Deque<Integer>> list = new ArrayList<>();
        list.add(new LinkedBlockingDeque<Integer>(10));
        list.add(new ConcurrentLinkedDeque<Integer>());
        return list;
    }

    private static List<Deque<Integer>> newDeques() {
        List<Deque<Integer>> list = newConcurrentDeques();
        list.add(new ArrayDeque<Integer>());
        list.add(new LinkedList<Integer>());
        return list;
    }

    private static void describe(Class<?> k, Object x, Object y) {
        if (debug)
            System.out.printf("%s: %s, %s%n", k.getSimpleName(),
                              x.getClass().getSimpleName(),
                              y.getClass().getSimpleName());
    }

    private static void realMain(String[] args) {
        for (Map<Integer, Boolean> x : maps())
            for (Map<Integer, Boolean> y : newConcurrentMaps()) {
                describe(Map.class, x, y);
                x.put(one, true);
                frob(x, y);
                frob(unmodifiableMap(x), y);
                frob(synchronizedMap(x), y);
                frob(x, synchronizedMap(y));
                frob(checkedMap(x, Integer.class, Boolean.class), y);
                frob(x, checkedMap(y, Integer.class, Boolean.class));
                x.clear();
                frob(newSetFromMap(x), newSetFromMap(y));
                frob(x.keySet(), newSetFromMap(y));
            }

        for (Set<Integer> x : newSets())
            for (Set<Integer> y : newConcurrentSets()) {
                describe(Set.class, x, y);
                frob(x, y);
                frob(unmodifiableSet(x), y);
                frob(synchronizedSet(x), y);
                frob(x, synchronizedSet(y));
                frob(checkedSet(x, Integer.class), y);
                frob(x, checkedSet(y, Integer.class));
            }

        for (List<Integer> x : newLists())
            for (List<Integer> y : newConcurrentLists()) {
                describe(List.class, x, y);
                frob(x, y);
                frob(unmodifiableList(x), y);
                frob(synchronizedList(x), y);
                frob(x, synchronizedList(y));
                frob(checkedList(x, Integer.class), y);
                frob(x, checkedList(y, Integer.class));
            }

        for (Queue<Integer> x : newQueues())
            for (Queue<Integer> y : newConcurrentQueues()) {
                describe(Queue.class, x, y);
                frob(x, y);
            }

        for (Deque<Integer> x : newDeques())
            for (Deque<Integer> y : newConcurrentDeques()) {
                describe(Deque.class, x, y);
                frob(asLifoQueue(x), y);
                frob(x, asLifoQueue(y));
            }
    }

    //--------------------- Infrastructure ---------------------------
    static volatile int passed = 0, failed = 0;
    static void pass() {passed++;}
    static void fail() {failed++; Thread.dumpStack();}
    static void fail(String msg) {System.out.println(msg); fail();}
    static void unexpected(Throwable t) {failed++; t.printStackTrace();}
    static void check(boolean cond) {if (cond) pass(); else fail();}
    static String toString(Object x) {
        return ((x instanceof Collection) || (x instanceof Map)) ?
            x.getClass().getName() : x.toString();}
    static void equal(Object x, Object y) {
        if (x == null ? y == null : x.equals(y)) pass();
        else fail(toString(x) + " not equal to " + toString(y));}
    static void notEqual(Object x, Object y) {
        if (x == null ? y == null : x.equals(y))
            fail(toString(x) + " equal to " + toString(y));
        else pass();}
    public static void main(String[] args) throws Throwable {
        try {realMain(args);} catch (Throwable t) {unexpected(t);}
        System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
        if (failed > 0) throw new AssertionError("Some tests failed");}
    private abstract static class CheckedThread extends Thread {
        abstract void realRun() throws Throwable;
        public void run() {
            try { realRun(); } catch (Throwable t) { unexpected(t); }}}
}
Revision:	1.9
Committed:	Mon Jan 8 03:12:03 2018 UTC (6 years, 4 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.8:	+40 -3 lines
Log Message:	organize imports
#	User	Rev	Content
1	jsr166	1.1	/*
2	jsr166	1.7	* Copyright (c) 2006, 2010, Oracle and/or its affiliates. All rights reserved.
3	jsr166	1.1	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4			*
5			* This code is free software; you can redistribute it and/or modify it
6			* under the terms of the GNU General Public License version 2 only, as
7			* published by the Free Software Foundation.
8			*
9			* This code is distributed in the hope that it will be useful, but WITHOUT
10			* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11			* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12			* version 2 for more details (a copy is included in the LICENSE file that
13			* accompanied this code).
14			*
15			* You should have received a copy of the GNU General Public License version
16			* 2 along with this work; if not, write to the Free Software Foundation,
17			* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18			*
19	jsr166	1.3	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20			* or visit www.oracle.com if you need additional information or have any
21			* questions.
22	jsr166	1.1	*/
23
24			/*
25			* @test
26			* @bug 6360946 6360948
27			* @summary Test various operations on concurrently mutating collections
28			* @author Martin Buchholz
29			*/
30
31	jsr166	1.9	import java.util.ArrayDeque;
32			import java.util.ArrayList;
33			import java.util.Collection;
34			import java.util.Collections;
35			import java.util.Comparator;
36			import java.util.Deque;
37			import java.util.HashMap;
38			import java.util.HashSet;
39			import java.util.Hashtable;
40			import java.util.LinkedList;
41			import java.util.List;
42			import java.util.Map;
43			import java.util.Queue;
44			import java.util.Set;
45			import java.util.TreeMap;
46			import java.util.TreeSet;
47			import java.util.Vector;
48			import java.util.concurrent.ArrayBlockingQueue;
49			import java.util.concurrent.ConcurrentHashMap;
50			import java.util.concurrent.ConcurrentLinkedDeque;
51			import java.util.concurrent.ConcurrentLinkedQueue;
52			import java.util.concurrent.ConcurrentSkipListMap;
53			import java.util.concurrent.ConcurrentSkipListSet;
54			import java.util.concurrent.CopyOnWriteArrayList;
55			import java.util.concurrent.CopyOnWriteArraySet;
56			import java.util.concurrent.LinkedBlockingDeque;
57			import java.util.concurrent.LinkedBlockingQueue;
58			import java.util.concurrent.LinkedTransferQueue;
59
60			import static java.util.Collections.asLifoQueue;
61			import static java.util.Collections.checkedList;
62			import static java.util.Collections.checkedMap;
63			import static java.util.Collections.checkedSet;
64			import static java.util.Collections.newSetFromMap;
65			import static java.util.Collections.synchronizedList;
66			import static java.util.Collections.synchronizedMap;
67			import static java.util.Collections.synchronizedSet;
68			import static java.util.Collections.unmodifiableList;
69			import static java.util.Collections.unmodifiableMap;
70			import static java.util.Collections.unmodifiableSet;
71	jsr166	1.1
72			public class RacingCollections {
73			/**
74			* How long to run each "race" (in milliseconds).
75			* Turn this up to some higher value like 1000 for stress testing:
76			* java -Dmillis=1000 RacingCollections
77			*/
78	jsr166	1.4	static final long defaultWorkTimeMillis = Long.getLong("millis", 10L);
79	jsr166	1.1
80			/**
81			* Whether to print debug information.
82			*/
83	jsr166	1.4	static final boolean debug = Boolean.getBoolean("debug");
84	jsr166	1.1
85	jsr166	1.4	static final Integer one = 1;
86			static final Integer two = 2;
87	jsr166	1.1
88			/**
89			* A thread that mutates an object forever, alternating between
90			* being empty and containing singleton "two"
91			*/
92			static class Frobber extends CheckedThread {
93			volatile boolean done = false;
94			boolean keepGoing(int i) { return (i % 128 != 0) \|\| ! done; }
95
96			final Object elLoco;
97			Frobber(Object elLoco) {
98			this.elLoco = elLoco;
99			this.start();
100			}
101
102	jsr166	1.5	@SuppressWarnings("unchecked")
103			void clear(Object o) {
104	jsr166	1.1	if (o instanceof Collection)
105			((Collection<?>)o).clear();
106			else
107			((Map<?,?>)o).clear();
108			}
109
110	jsr166	1.5	@SuppressWarnings("unchecked")
111			void realRun() {
112	jsr166	1.1	// Mutate elLoco wildly forever, checking occasionally for "done"
113			clear(elLoco);
114			if (elLoco instanceof List) {
115			List<Integer> l = (List<Integer>) elLoco;
116			for (int i = 0; keepGoing(i); i++) {
117			switch (i%2) {
118			case 0: l.add(two); break;
119			case 1: l.add(0, two); break;
120			}
121			switch (i%2) {
122			case 0: l.remove(two); break;
123			case 1: l.remove(0); break;
124			}}}
125			else if (elLoco instanceof Deque) {
126			Deque<Integer> q = (Deque<Integer>) elLoco;
127			for (int i = 0; keepGoing(i); i++) {
128			switch (i%6) {
129			case 0: q.add(two); break;
130			case 1: q.addFirst(two); break;
131			case 2: q.addLast(two); break;
132			case 3: q.offer(two); break;
133			case 4: q.offerFirst(two); break;
134			case 5: q.offerLast(two); break;
135			}
136			switch (i%6) {
137			case 0: q.remove(two); break;
138			case 1: q.removeFirst(); break;
139			case 2: q.removeLast(); break;
140			case 3: q.poll(); break;
141			case 4: q.pollFirst(); break;
142			case 5: q.pollLast(); break;
143			}}}
144			else if (elLoco instanceof Queue) {
145			Queue<Integer> q = (Queue<Integer>) elLoco;
146			for (int i = 0; keepGoing(i); i++) {
147			switch (i%2) {
148			case 0: q.add(two); break;
149			case 1: q.offer(two); break;
150			}
151			switch (i%2) {
152			case 0: q.remove(two); break;
153			case 1: q.poll(); break;
154			}}}
155			else if (elLoco instanceof Map) {
156			Map<Integer, Boolean> m = (Map<Integer, Boolean>) elLoco;
157			for (int i = 0; keepGoing(i); i++) {
158			m.put(two, true);
159			m.remove(two);
160			}}
161			else if (elLoco instanceof Collection) {
162			Collection<Integer> c = (Collection<Integer>) elLoco;
163			for (int i = 0; keepGoing(i); i++) {
164			c.add(two);
165			c.remove(two);
166			}}
167			else { throw new Error("Huh? " + elLoco); }
168			}
169
170			void enoughAlready() {
171			done = true;
172			try { join(); } catch (Throwable t) { unexpected(t); }
173			}
174			}
175
176			private static void checkEqualSanity(Object theRock, Object elLoco) {
177			//equal(theRock, theRock);
178			equal(elLoco, elLoco);
179
180			// It would be nice someday to have theRock and elLoco never "equal",
181			// although the meaning of "equal" for mutating collections
182			// is a bit fuzzy. Uncomment when/if we fix:
183			// 6374942: Improve thread safety of collection .equals() methods
184			//notEqual(theRock, elLoco);
185			//notEqual(elLoco, theRock);
186
187			notEqual(theRock.toString(), elLoco.toString());
188			}
189
190			static class Looper {
191			final long quittingTime;
192			int i = 0;
193			Looper() { this(defaultWorkTimeMillis); }
194			Looper(long workTimeMillis) {
195			quittingTime = System.nanoTime() + workTimeMillis * 1024 * 1024;
196			}
197			boolean keepGoing() {
198	jsr166	1.6	return (i++ % 128 != 0) \|\| (System.nanoTime() - quittingTime < 0);
199	jsr166	1.1	}
200			}
201
202			private static void frob(Object theRock, Object elLoco) {
203			Frobber frobber = new Frobber(elLoco);
204			try {
205			if (theRock instanceof Collection) {
206			@SuppressWarnings("unchecked")
207			Collection<Integer> c = (Collection<Integer>) theRock;
208			if (! c.contains(one))
209			c.add(one);
210			} else {
211			@SuppressWarnings("unchecked")
212			Map<Integer, Boolean> m = (Map<Integer, Boolean>) theRock;
213			if (! m.containsKey(one))
214			m.put(one, true);
215			}
216			for (Looper looper = new Looper(); looper.keepGoing(); )
217			checkEqualSanity(theRock, elLoco);
218			}
219			catch (Throwable t) { unexpected(t); }
220			finally { frobber.enoughAlready(); }
221			}
222
223			private static List<Map<Integer, Boolean>> newConcurrentMaps() {
224	jsr166	1.8	List<Map<Integer, Boolean>> list = new ArrayList<>();
225	jsr166	1.1	list.add(new ConcurrentHashMap<Integer, Boolean>());
226			list.add(new ConcurrentSkipListMap<Integer, Boolean>());
227			return list;
228			}
229
230			private static List<Map<Integer, Boolean>> maps() {
231			List<Map<Integer, Boolean>> list = newConcurrentMaps();
232			list.add(new Hashtable<Integer, Boolean>());
233			list.add(new HashMap<Integer, Boolean>());
234			list.add(new TreeMap<Integer, Boolean>());
235	jsr166	1.8	Comparator<Integer> cmp = new Comparator<>() {
236	jsr166	1.1	public int compare(Integer x, Integer y) {
237			return x - y;
238			}};
239			list.add(new TreeMap<Integer, Boolean>(Collections.reverseOrder(cmp)));
240			return list;
241			}
242
243			private static List<Set<Integer>> newConcurrentSets() {
244	jsr166	1.8	List<Set<Integer>> list = new ArrayList<>();
245	jsr166	1.1	list.add(new ConcurrentSkipListSet<Integer>());
246			list.add(new CopyOnWriteArraySet<Integer>());
247			return list;
248			}
249
250			private static List<Set<Integer>> newSets() {
251			List<Set<Integer>> list = newConcurrentSets();
252			list.add(new HashSet<Integer>());
253			list.add(new TreeSet<Integer>());
254			list.add(new TreeSet<Integer>(Collections.reverseOrder()));
255			return list;
256			}
257
258			private static List<List<Integer>> newConcurrentLists() {
259	jsr166	1.8	List<List<Integer>> list = new ArrayList<>();
260	jsr166	1.1	list.add(new CopyOnWriteArrayList<Integer>());
261			return list;
262			}
263
264			private static List<List<Integer>> newLists() {
265			List<List<Integer>> list = newConcurrentLists();
266			list.add(new Vector<Integer>());
267			list.add(new ArrayList<Integer>());
268			return list;
269			}
270
271			private static List<Queue<Integer>> newConcurrentQueues() {
272	jsr166	1.8	List<Queue<Integer>> list = new ArrayList<>(newConcurrentDeques());
273	jsr166	1.6	list.add(new ArrayBlockingQueue<Integer>(10));
274	jsr166	1.1	list.add(new LinkedBlockingQueue<Integer>(10));
275			list.add(new LinkedTransferQueue<Integer>());
276	jsr166	1.2	list.add(new ConcurrentLinkedQueue<Integer>());
277	jsr166	1.1	return list;
278			}
279
280			private static List<Queue<Integer>> newQueues() {
281	jsr166	1.8	List<Queue<Integer>> list = new ArrayList<>(newDeques());
282	jsr166	1.1	list.add(new LinkedBlockingQueue<Integer>(10));
283			return list;
284			}
285
286			private static List<Deque<Integer>> newConcurrentDeques() {
287	jsr166	1.8	List<Deque<Integer>> list = new ArrayList<>();
288	jsr166	1.1	list.add(new LinkedBlockingDeque<Integer>(10));
289	jsr166	1.2	list.add(new ConcurrentLinkedDeque<Integer>());
290	jsr166	1.1	return list;
291			}
292
293			private static List<Deque<Integer>> newDeques() {
294			List<Deque<Integer>> list = newConcurrentDeques();
295			list.add(new ArrayDeque<Integer>());
296			list.add(new LinkedList<Integer>());
297			return list;
298			}
299
300			private static void describe(Class<?> k, Object x, Object y) {
301			if (debug)
302			System.out.printf("%s: %s, %s%n", k.getSimpleName(),
303			x.getClass().getSimpleName(),
304			y.getClass().getSimpleName());
305			}
306
307			private static void realMain(String[] args) {
308			for (Map<Integer, Boolean> x : maps())
309			for (Map<Integer, Boolean> y : newConcurrentMaps()) {
310			describe(Map.class, x, y);
311			x.put(one, true);
312			frob(x, y);
313			frob(unmodifiableMap(x), y);
314			frob(synchronizedMap(x), y);
315			frob(x, synchronizedMap(y));
316			frob(checkedMap(x, Integer.class, Boolean.class), y);
317			frob(x, checkedMap(y, Integer.class, Boolean.class));
318			x.clear();
319			frob(newSetFromMap(x), newSetFromMap(y));
320			frob(x.keySet(), newSetFromMap(y));
321			}
322
323			for (Set<Integer> x : newSets())
324			for (Set<Integer> y : newConcurrentSets()) {
325			describe(Set.class, x, y);
326			frob(x, y);
327			frob(unmodifiableSet(x), y);
328			frob(synchronizedSet(x), y);
329			frob(x, synchronizedSet(y));
330			frob(checkedSet(x, Integer.class), y);
331			frob(x, checkedSet(y, Integer.class));
332			}
333
334			for (List<Integer> x : newLists())
335			for (List<Integer> y : newConcurrentLists()) {
336			describe(List.class, x, y);
337			frob(x, y);
338			frob(unmodifiableList(x), y);
339			frob(synchronizedList(x), y);
340			frob(x, synchronizedList(y));
341			frob(checkedList(x, Integer.class), y);
342			frob(x, checkedList(y, Integer.class));
343			}
344
345			for (Queue<Integer> x : newQueues())
346			for (Queue<Integer> y : newConcurrentQueues()) {
347			describe(Queue.class, x, y);
348			frob(x, y);
349			}
350
351			for (Deque<Integer> x : newDeques())
352			for (Deque<Integer> y : newConcurrentDeques()) {
353			describe(Deque.class, x, y);
354			frob(asLifoQueue(x), y);
355			frob(x, asLifoQueue(y));
356			}
357			}
358
359			//--------------------- Infrastructure ---------------------------
360			static volatile int passed = 0, failed = 0;
361			static void pass() {passed++;}
362			static void fail() {failed++; Thread.dumpStack();}
363			static void fail(String msg) {System.out.println(msg); fail();}
364			static void unexpected(Throwable t) {failed++; t.printStackTrace();}
365			static void check(boolean cond) {if (cond) pass(); else fail();}
366			static String toString(Object x) {
367			return ((x instanceof Collection) \|\| (x instanceof Map)) ?
368			x.getClass().getName() : x.toString();}
369			static void equal(Object x, Object y) {
370			if (x == null ? y == null : x.equals(y)) pass();
371			else fail(toString(x) + " not equal to " + toString(y));}
372			static void notEqual(Object x, Object y) {
373			if (x == null ? y == null : x.equals(y))
374			fail(toString(x) + " equal to " + toString(y));
375			else pass();}
376			public static void main(String[] args) throws Throwable {
377			try {realMain(args);} catch (Throwable t) {unexpected(t);}
378			System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
379			if (failed > 0) throw new AssertionError("Some tests failed");}
380	jsr166	1.4	private abstract static class CheckedThread extends Thread {
381	jsr166	1.1	abstract void realRun() throws Throwable;
382			public void run() {
383			try { realRun(); } catch (Throwable t) { unexpected(t); }}}
384			}