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