1 /*

     2  * Copyright (c) 2017, 2017, 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.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 package org.graalvm.collections.test;

    26 

    27 import java.util.Arrays;

    28 import java.util.Collection;

    29 import java.util.Iterator;

    30 import java.util.LinkedHashMap;

    31 import java.util.Objects;

    32 import java.util.Random;

    33 

    34 import org.graalvm.collections.EconomicMap;

    35 import org.graalvm.collections.Equivalence;

    36 import org.graalvm.collections.MapCursor;

    37 import org.graalvm.collections.UnmodifiableMapCursor;

    38 import org.junit.Assert;

    39 import org.junit.Test;

    40 import org.junit.runner.RunWith;

    41 import org.junit.runners.Parameterized;

    42 import org.junit.runners.Parameterized.Parameter;

    43 import org.junit.runners.Parameterized.Parameters;

    44 

    45 @RunWith(Parameterized.class)

    46 public class EconomicMapLargeTest {

    47 

    48     @Parameter(value = 0) public EconomicMap<Object, Object> testMap;

    49     @Parameter(value = 1) public EconomicMap<Object, Object> referenceMap;

    50     @Parameter(value = 2) public String name;

    51 

    52     @Parameters(name = "{2}")

    53     public static Collection<Object[]> data() {

    54         return Arrays.asList(new Object[]{EconomicMap.create(Equivalence.DEFAULT), EconomicMap.create(Equivalence.DEFAULT), "EconomicMap"},

    55                         new Object[]{EconomicMap.create(Equivalence.IDENTITY), EconomicMap.create(Equivalence.IDENTITY), "EconomicMap(IDENTITY)"},

    56                         new Object[]{EconomicMap.create(Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE), EconomicMap.create(Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE),

    57                                         "EconomicMap(IDENTITY_WITH_SYSTEM_HASHCODE)"},

    58                         new Object[]{EconomicMap.create(Equivalence.DEFAULT), EconomicMap.wrapMap(new LinkedHashMap<>()), "EconomicMap<->wrapMap"},

    59                         new Object[]{EconomicMap.wrapMap(new LinkedHashMap<>()), EconomicMap.wrapMap(new LinkedHashMap<>()), "wrapMap"});

    60     }

    61 

    62     private static int[] createRandomRange(Random random, int count) {

    63         int[] result = new int[count];

    64         for (int i = 0; i < count; ++i) {

    65             int range = random.nextInt(14);

    66             if (range == 0 || range > 10) {

    67                 range = Integer.MAX_VALUE;

    68             } else if (range == 10) {

    69                 range = 100;

    70             }

    71             result[i] = range;

    72         }

    73         return result;

    74     }

    75 

    76     private static final class BadHashClass {

    77         private int value;

    78 

    79         BadHashClass(int randomInt) {

    80             this.value = randomInt;

    81         }

    82 

    83         @Override

    84         public int hashCode() {

    85             return 0;

    86         }

    87 

    88         @Override

    89         public boolean equals(Object other) {

    90             if (other instanceof BadHashClass) {

    91                 BadHashClass badHashClass = (BadHashClass) other;

    92                 return badHashClass.value == value;

    93             }

    94             return false;

    95         }

    96     }

    97 

    98     interface MapAction {

    99         Object perform(EconomicMap<Object, Object> map, int randomInt);

   100     }

   101 

   102     static final Object EXISTING_VALUE = new Object();

   103 

   104     static final MapAction[] INCREASE_ACTIONS = new MapAction[]{

   105                     (map, randomInt) -> map.put(randomInt, "value"),

   106                     (map, randomInt) -> map.get(randomInt)

   107     };

   108 

   109     static final MapAction[] ACTIONS = new MapAction[]{

   110                     (map, randomInt) -> map.removeKey(randomInt),

   111                     (map, randomInt) -> map.put(randomInt, "value"),

   112                     (map, randomInt) -> map.put(randomInt, null),

   113                     (map, randomInt) -> map.put(EXISTING_VALUE, randomInt),

   114                     (map, randomInt) -> {

   115                         if (randomInt == 0) {

   116                             map.clear();

   117                         }

   118                         return map.isEmpty();

   119                     },

   120                     (map, randomInt) -> map.containsKey(randomInt),

   121                     (map, randomInt) -> map.get(randomInt),

   122                     (map, randomInt) -> map.put(new BadHashClass(randomInt), "unique"),

   123                     (map, randomInt) -> {

   124                         if (randomInt == 0) {

   125                             map.replaceAll((key, value) -> Objects.toString(value) + "!");

   126                         }

   127                         return map.isEmpty();

   128                     }

   129 

   130     };

   131 

   132     @Test

   133     public void testVeryLarge() {

   134         testMap.clear();

   135         referenceMap.clear();

   136 

   137         Random random = new Random(0);

   138         for (int i = 0; i < 200000; ++i) {

   139             for (int j = 0; j < INCREASE_ACTIONS.length; ++j) {

   140                 int nextInt = random.nextInt(10000000);

   141                 MapAction action = INCREASE_ACTIONS[j];

   142                 Object result = action.perform(testMap, nextInt);

   143                 Object referenceResult = action.perform(referenceMap, nextInt);

   144                 Assert.assertEquals(result, referenceResult);

   145             }

   146         }

   147     }

   148 

   149     /**

   150      * Tests a sequence of random operations on the map.

   151      */

   152     @Test

   153     public void testAddRemove() {

   154         testMap.clear();

   155         referenceMap.clear();

   156 

   157         for (int seed = 0; seed < 10; ++seed) {

   158             Random random = new Random(seed);

   159             int[] ranges = createRandomRange(random, ACTIONS.length);

   160             int value = random.nextInt(10000);

   161             for (int i = 0; i < value; ++i) {

   162                 for (int j = 0; j < ACTIONS.length; ++j) {

   163                     if (random.nextInt(ranges[j]) == 0) {

   164                         int nextInt = random.nextInt(100);

   165                         MapAction action = ACTIONS[j];

   166                         Object result = action.perform(testMap, nextInt);

   167                         Object referenceResult = action.perform(referenceMap, nextInt);

   168                         Assert.assertEquals(result, referenceResult);

   169                         if (j % 100 == 0) {

   170                             checkEquality(testMap, referenceMap);

   171                         }

   172                     }

   173                 }

   174 

   175                 if (random.nextInt(20) == 0) {

   176                     removeElement(random.nextInt(100), testMap, referenceMap);

   177                 }

   178             }

   179         }

   180     }

   181 

   182     private static void removeElement(int index, EconomicMap<?, ?> map, EconomicMap<?, ?> referenceMap) {

   183         Assert.assertEquals(referenceMap.size(), map.size());

   184         MapCursor<?, ?> cursor = map.getEntries();

   185         MapCursor<?, ?> referenceCursor = referenceMap.getEntries();

   186         int z = 0;

   187         while (cursor.advance()) {

   188             Assert.assertTrue(referenceCursor.advance());

   189             Assert.assertEquals(referenceCursor.getKey(), cursor.getKey());

   190             Assert.assertEquals(referenceCursor.getValue(), cursor.getValue());

   191             if (index == z) {

   192                 cursor.remove();

   193                 referenceCursor.remove();

   194             }

   195             ++z;

   196         }

   197 

   198         Assert.assertFalse(referenceCursor.advance());

   199     }

   200 

   201     private static void checkEquality(EconomicMap<?, ?> map, EconomicMap<?, ?> referenceMap) {

   202         Assert.assertEquals(referenceMap.size(), map.size());

   203 

   204         // Check entries.

   205         UnmodifiableMapCursor<?, ?> cursor = map.getEntries();

   206         UnmodifiableMapCursor<?, ?> referenceCursor = referenceMap.getEntries();

   207         while (cursor.advance()) {

   208             Assert.assertTrue(referenceCursor.advance());

   209             Assert.assertEquals(referenceCursor.getKey(), cursor.getKey());

   210             Assert.assertEquals(referenceCursor.getValue(), cursor.getValue());

   211         }

   212 

   213         // Check keys.

   214         Iterator<?> iterator = map.getKeys().iterator();

   215         Iterator<?> referenceIterator = referenceMap.getKeys().iterator();

   216         while (iterator.hasNext()) {

   217             Assert.assertTrue(referenceIterator.hasNext());

   218             Assert.assertEquals(iterator.next(), referenceIterator.next());

   219         }

   220 

   221         // Check values.

   222         iterator = map.getValues().iterator();

   223         referenceIterator = referenceMap.getValues().iterator();

   224         while (iterator.hasNext()) {

   225             Assert.assertTrue(referenceIterator.hasNext());

   226             Assert.assertEquals(iterator.next(), referenceIterator.next());

   227         }

   228         Assert.assertFalse(referenceIterator.hasNext());

   229     }

   230 

   231 }