rev 5382 : 7126277: Alternative hashing implementation

   1 /*
   2  * Copyright (c) 2006, 2010, Oracle and/or its affiliates. All rights reserved.
   3  * 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  * 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  */
  23 
  24 /*
  25  * @test
  26  * @bug 6415641 6377302
  27  * @summary Concurrent collections are permitted to lie about their size
  28  * @author Martin Buchholz
  29  */
  30 
  31 import java.io.*;
  32 import java.util.*;
  33 import java.util.concurrent.*;
  34 
  35 @SuppressWarnings("unchecked")
  36 public class BiggernYours {
  37     static final Random rnd = new Random();
  38 
  39     static void compareCollections(Collection c1, Collection c2) {
  40         arrayEqual(c1.toArray(),
  41                    c2.toArray());
  42         arrayEqual(c1.toArray(new Object[0]),
  43                    c2.toArray(new Object[0]));
  44         arrayEqual(c1.toArray(new Object[5]),
  45                    c2.toArray(new Object[5]));










  46     }
  47 
  48     static void compareMaps(Map m1, Map m2) {
  49         compareCollections(m1.keySet(),
  50                            m2.keySet());
  51         compareCollections(m1.values(),
  52                            m2.values());
  53         compareCollections(m1.entrySet(),
  54                            m2.entrySet());
  55     }
  56 
  57     static void compareNavigableMaps(NavigableMap m1, NavigableMap m2) {
  58         compareMaps(m1, m2);
  59         compareMaps(m1.descendingMap(),
  60                     m2.descendingMap());
  61         compareMaps(m1.tailMap(Integer.MIN_VALUE),
  62                     m2.tailMap(Integer.MIN_VALUE));
  63         compareMaps(m1.headMap(Integer.MAX_VALUE),
  64                     m2.headMap(Integer.MAX_VALUE));
  65     }
  66 
  67     static void compareNavigableSets(NavigableSet s1, NavigableSet s2) {
  68         compareCollections(s1, s2);
  69         compareCollections(s1.descendingSet(),
  70                            s2.descendingSet());
  71         compareCollections(s1.tailSet(Integer.MIN_VALUE),
  72                            s2.tailSet(Integer.MIN_VALUE));
  73     }
  74 
  75     static abstract class MapFrobber { abstract void frob(Map m); }
  76     static abstract class SetFrobber { abstract void frob(Set s); }
  77     static abstract class ColFrobber { abstract void frob(Collection c); }
  78 
  79     static ColFrobber adder(final int i) {
  80         return new ColFrobber() {void frob(Collection c) { c.add(i); }};
  81     }
  82 
  83     static final ColFrobber[] adders =
  84     { adder(1), adder(3), adder(2) };
  85 
  86     static MapFrobber putter(final int k, final int v) {
  87         return new MapFrobber() {void frob(Map m) { m.put(k,v); }};
  88     }
  89 
  90     static final MapFrobber[] putters =
  91     { putter(1, -2), putter(3, -6), putter(2, -4) };
  92 
  93     static void unexpected(Throwable t, Object suspect) {
  94         System.out.println(suspect.getClass());
  95         unexpected(t);
  96     }
  97 
  98     static void testCollections(Collection c1, Collection c2) {
  99         try {
 100             compareCollections(c1, c2);
 101             for (ColFrobber adder : adders) {
 102                 for (Collection c : new Collection[]{c1, c2})
 103                     adder.frob(c);
 104                 compareCollections(c1, c2);
 105             }
 106         } catch (Throwable t) { unexpected(t, c1); }
 107     }
 108 
 109     static void testNavigableSets(NavigableSet s1, NavigableSet s2) {
 110         try {
 111             compareNavigableSets(s1, s2);
 112             for (ColFrobber adder : adders) {
 113                 for (Set s : new Set[]{s1, s2})
 114                     adder.frob(s);
 115                 compareNavigableSets(s1, s2);
 116             }
 117         } catch (Throwable t) { unexpected(t, s1); }
 118     }
 119 
 120     static void testMaps(Map m1, Map m2) {
 121         try {
 122             compareMaps(m1, m2);
 123             for (MapFrobber putter : putters) {
 124                 for (Map m : new Map[]{m1, m2})
 125                     putter.frob(m);
 126                 compareMaps(m1, m2);
 127             }
 128         } catch (Throwable t) { unexpected(t, m1); }
 129     }
 130 
 131     static void testNavigableMaps(NavigableMap m1, NavigableMap m2) {
 132         try {
 133             compareNavigableMaps(m1, m2);
 134             for (MapFrobber putter : putters) {
 135                 for (Map m : new Map[]{m1, m2})
 136                     putter.frob(m);
 137                 compareNavigableMaps(m1, m2);
 138             }
 139         } catch (Throwable t) { unexpected(t, m1); }
 140     }
 141 
 142     static int randomize(int size) { return rnd.nextInt(size + 2); }
 143 
 144     @SuppressWarnings("serial")
 145     private static void realMain(String[] args) throws Throwable {
 146         testNavigableMaps(
 147             new ConcurrentSkipListMap(),
 148             new ConcurrentSkipListMap() {
 149                 public int size() {return randomize(super.size());}});
 150 
 151         testNavigableSets(
 152             new ConcurrentSkipListSet(),
 153             new ConcurrentSkipListSet() {
 154                 public int size() {return randomize(super.size());}});
 155 
 156         testCollections(
 157             new CopyOnWriteArraySet(),
 158             new CopyOnWriteArraySet() {
 159                 public int size() {return randomize(super.size());}});
 160 
 161         testCollections(
 162             new CopyOnWriteArrayList(),
 163             new CopyOnWriteArrayList() {
 164                 public int size() {return randomize(super.size());}});
 165 
 166         testCollections(
 167             new TreeSet(),
 168             new TreeSet() {
 169                 public int size() {return randomize(super.size());}});
 170 
 171         testMaps(
 172             new ConcurrentHashMap(),
 173             new ConcurrentHashMap() {
 174                 public int size() {return randomize(super.size());}});
 175 
 176         testCollections(
 177             new ConcurrentLinkedDeque(),
 178             new ConcurrentLinkedDeque() {
 179                 public int size() {return randomize(super.size());}});
 180 
 181         testCollections(
 182             new ConcurrentLinkedQueue(),
 183             new ConcurrentLinkedQueue() {
 184                 public int size() {return randomize(super.size());}});
 185 
 186         testCollections(
 187             new LinkedTransferQueue(),
 188             new LinkedTransferQueue() {
 189                 public int size() {return randomize(super.size());}});
 190 
 191         testCollections(
 192             new LinkedBlockingQueue(),
 193             new LinkedBlockingQueue() {
 194                 public int size() {return randomize(super.size());}});
 195 
 196         testCollections(
 197             new LinkedBlockingDeque(),
 198             new LinkedBlockingDeque() {
 199                 public int size() {return randomize(super.size());}});
 200 
 201         testCollections(
 202             new ArrayBlockingQueue(5),
 203             new ArrayBlockingQueue(5) {
 204                 public int size() {return randomize(super.size());}});
 205 
 206         testCollections(
 207             new PriorityBlockingQueue(5),
 208             new PriorityBlockingQueue(5) {
 209                 public int size() {return randomize(super.size());}});
 210     }
 211 
 212     //--------------------- Infrastructure ---------------------------
 213     static volatile int passed = 0, failed = 0;
 214     static void pass() {passed++;}
 215     static void fail() {failed++; Thread.dumpStack();}
 216     static void fail(String msg) {System.out.println(msg); fail();}
 217     static void unexpected(Throwable t) {failed++; t.printStackTrace();}
 218     static void check(boolean cond) {if (cond) pass(); else fail();}
 219     static void equal(Object x, Object y) {
 220         if (x == null ? y == null : x.equals(y)) pass();
 221         else fail(x + " not equal to " + y);}
 222     static void arrayEqual(Object[] x, Object[] y) {
 223         if (x == null ? y == null : Arrays.equals(x, y)) pass();
 224         else fail(Arrays.toString(x) + " not equal to " + Arrays.toString(y));}
 225     public static void main(String[] args) throws Throwable {
 226         try {realMain(args);} catch (Throwable t) {unexpected(t);}
 227         System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
 228         if (failed > 0) throw new AssertionError("Some tests failed");}
 229     private static abstract class Fun {abstract void f() throws Throwable;}
 230     static void THROWS(Class<? extends Throwable> k, Fun... fs) {
 231         for (Fun f : fs)
 232             try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
 233             catch (Throwable t) {
 234                 if (k.isAssignableFrom(t.getClass())) pass();
 235                 else unexpected(t);}}
 236     private static abstract class CheckedThread extends Thread {
 237         abstract void realRun() throws Throwable;
 238         public void run() {
 239             try {realRun();} catch (Throwable t) {unexpected(t);}}}
 240 }
--- EOF ---