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.

     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 package org.graalvm.util.test;

    24 

    25 import static org.junit.Assert.assertEquals;

    26 

    27 import java.util.ArrayList;

    28 import java.util.Arrays;

    29 import java.util.Collections;

    30 import java.util.Iterator;

    31 import java.util.LinkedHashMap;

    32 import java.util.List;

    33 import java.util.Map;

    34 import java.util.NoSuchElementException;

    35 import java.util.Objects;

    36 import java.util.Random;

    37 import java.util.function.BiFunction;

    38 

    39 import org.graalvm.util.CollectionsUtil;

    40 import org.graalvm.util.EconomicMap;

    41 import org.graalvm.util.EconomicSet;

    42 import org.graalvm.util.Equivalence;

    43 import org.graalvm.util.MapCursor;

    44 import org.graalvm.util.ObjectSizeEstimate;

    45 import org.graalvm.util.UnmodifiableMapCursor;

    46 import org.junit.Assert;

    47 import org.junit.Test;

    48 

    49 public class CollectionTest {

    50 

    51     /**

    52      * Tests the memory size of an empty map and a map with only one or two entries.

    53      */

    54     @Test

    55     public void testSize() {

    56         EconomicMap<Object, Object> map = EconomicMap.create(Equivalence.IDENTITY);

    57         assertEquals(48, ObjectSizeEstimate.forObject(map).getTotalBytes());

    58 

    59         Integer value = 1;

    60         map.put(value, value);

    61         assertEquals(152, ObjectSizeEstimate.forObject(map).getTotalBytes());

    62 

    63         Integer secondValue = 2;

    64         map.put(secondValue, secondValue);

    65         assertEquals(152 + 20, ObjectSizeEstimate.forObject(map).getTotalBytes());

    66     }

    67 

    68     /**

    69      * Tests whether the map actually compresses the entries array when a large number of entries

    70      * are deleted.

    71      */

    72     @Test

    73     public void testCompress() {

    74         EconomicMap<Object, Object> map = EconomicMap.create();

    75 

    76         // Measuring size of map with one entry.

    77         Object firstValue = 0;

    78         map.put(firstValue, firstValue);

    79         ObjectSizeEstimate afterFirstValue = ObjectSizeEstimate.forObject(map);

    80 

    81         // Add 999 more entries.

    82         for (int i = 1; i < 1000; ++i) {

    83             Object value = i;

    84             map.put(value, value);

    85         }

    86         ObjectSizeEstimate beforeRemove = ObjectSizeEstimate.forObject(map);

    87 

    88         // Remove 999 first entries.

    89         for (int i = 0; i < 999; ++i) {

    90             map.removeKey(i);

    91         }

    92         ObjectSizeEstimate afterRemove = ObjectSizeEstimate.forObject(map);

    93 

    94         // Check that size is same size as with one entry.

    95         assertEquals(afterFirstValue, afterRemove);

    96 

    97         // Add 999 new entries.

    98         for (int i = 0; i < 999; ++i) {

    99             Object value = i;

   100             map.put(value, value);

   101         }

   102         ObjectSizeEstimate afterAdd = ObjectSizeEstimate.forObject(map);

   103 

   104         // Check that entries array is same size again.

   105         assertEquals(beforeRemove.getPointerCount(), afterAdd.getPointerCount());

   106     }

   107 

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

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

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

   111             int range = random.nextInt(14);

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

   113                 range = Integer.MAX_VALUE;

   114             } else if (range == 10) {

   115                 range = 100;

   116             }

   117             result[i] = range;

   118         }

   119         return result;

   120     }

   121 

   122     private static final class BadHashClass {

   123         private int value;

   124 

   125         BadHashClass(int randomInt) {

   126             this.value = randomInt;

   127         }

   128 

   129         @Override

   130         public int hashCode() {

   131             return 0;

   132         }

   133 

   134         @Override

   135         public boolean equals(Object other) {

   136             if (other instanceof BadHashClass) {

   137                 BadHashClass badHashClass = (BadHashClass) other;

   138                 return badHashClass.value == value;

   139             }

   140             return false;

   141         }

   142     }

   143 

   144     interface MapAction {

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

   146     }

   147 

   148     static final Object EXISTING_VALUE = new Object();

   149 

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

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

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

   153     };

   154 

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

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

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

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

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

   160                     (map, randomInt) -> {

   161                         if (randomInt == 0) {

   162                             map.clear();

   163                         }

   164                         return map.isEmpty();

   165                     },

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

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

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

   169                     (map, randomInt) -> {

   170                         if (randomInt == 0) {

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

   172                         }

   173                         return map.isEmpty();

   174                     }

   175 

   176     };

   177 

   178     @Test

   179     public void testVeryLarge() {

   180         EconomicMap<Object, Object> map = EconomicMap.create();

   181         EconomicMap<Object, Object> referenceMap = createDebugMap();

   182 

   183         Random random = new Random(0);

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

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

   186                 int nextInt = random.nextInt(10000000);

   187                 MapAction action = INCREASE_ACTIONS[j];

   188                 Object result = action.perform(map, nextInt);

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

   190                 Assert.assertEquals(result, referenceResult);

   191             }

   192         }

   193     }

   194 

   195     /**

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

   197      */

   198     @Test

   199     public void testAddRemove() {

   200         EconomicMap<Object, Object> map = EconomicMap.create();

   201         EconomicMap<Object, Object> referenceMap = createDebugMap();

   202 

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

   204             Random random = new Random(seed);

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

   206             int value = random.nextInt(10000);

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

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

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

   210                         int nextInt = random.nextInt(100);

   211                         MapAction action = ACTIONS[j];

   212                         Object result = action.perform(map, nextInt);

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

   214                         Assert.assertEquals(result, referenceResult);

   215                         if (j % 100 == 0) {

   216                             checkEquality(map, referenceMap);

   217                         }

   218                     }

   219                 }

   220 

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

   222                     removeElement(random.nextInt(100), map, referenceMap);

   223                 }

   224             }

   225         }

   226     }

   227 

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

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

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

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

   232         int z = 0;

   233         while (cursor.advance()) {

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

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

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

   237             if (index == z) {

   238                 cursor.remove();

   239                 referenceCursor.remove();

   240             }

   241             ++z;

   242         }

   243 

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

   245     }

   246 

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

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

   249 

   250         // Check entries.

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

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

   253         while (cursor.advance()) {

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

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

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

   257         }

   258 

   259         // Check keys.

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

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

   262         while (iterator.hasNext()) {

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

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

   265         }

   266 

   267         // Check values.

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

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

   270         while (iterator.hasNext()) {

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

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

   273         }

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

   275     }

   276 

   277     public static <K, V> EconomicMap<K, V> createDebugMap() {

   278         final LinkedHashMap<K, V> linkedMap = new LinkedHashMap<>();

   279         final EconomicMap<K, V> sparseMap = EconomicMap.create();

   280         return new EconomicMap<K, V>() {

   281 

   282             @Override

   283             public V get(K key) {

   284                 V result = linkedMap.get(key);

   285                 V sparseResult = sparseMap.get(key);

   286                 assert Objects.equals(result, sparseResult);

   287                 return result;

   288             }

   289 

   290             @Override

   291             public V put(K key, V value) {

   292                 V result = linkedMap.put(key, value);

   293                 assert Objects.equals(result, sparseMap.put(key, value));

   294                 return result;

   295             }

   296 

   297             @Override

   298             public int size() {

   299                 int result = linkedMap.size();

   300                 assert result == sparseMap.size();

   301                 return result;

   302             }

   303 

   304             @Override

   305             public boolean containsKey(K key) {

   306                 boolean result = linkedMap.containsKey(key);

   307                 assert result == sparseMap.containsKey(key);

   308                 return result;

   309             }

   310 

   311             @Override

   312             public void clear() {

   313                 linkedMap.clear();

   314                 sparseMap.clear();

   315             }

   316 

   317             @Override

   318             public V removeKey(K key) {

   319                 V result = linkedMap.remove(key);

   320                 assert Objects.equals(result, sparseMap.removeKey(key));

   321                 return result;

   322             }

   323 

   324             @Override

   325             public Iterable<V> getValues() {

   326 

   327                 Iterator<V> iterator = linkedMap.values().iterator();

   328                 Iterator<V> sparseIterator = sparseMap.getValues().iterator();

   329                 return new Iterable<V>() {

   330 

   331                     @Override

   332                     public Iterator<V> iterator() {

   333                         return new Iterator<V>() {

   334 

   335                             @Override

   336                             public boolean hasNext() {

   337                                 boolean result = iterator.hasNext();

   338                                 boolean otherResult = sparseIterator.hasNext();

   339                                 assert result == otherResult;

   340                                 return result;

   341                             }

   342 

   343                             @Override

   344                             public V next() {

   345                                 V sparseNext = sparseIterator.next();

   346                                 V next = iterator.next();

   347                                 assert Objects.equals(sparseNext, next);

   348                                 return next;

   349                             }

   350 

   351                             @Override

   352                             public void remove() {

   353                                 iterator.remove();

   354                                 sparseIterator.remove();

   355                             }

   356                         };

   357                     }

   358 

   359                 };

   360             }

   361 

   362             @Override

   363             public Iterable<K> getKeys() {

   364 

   365                 Iterator<K> iterator = linkedMap.keySet().iterator();

   366                 Iterator<K> sparseIterator = sparseMap.getKeys().iterator();

   367                 return new Iterable<K>() {

   368 

   369                     @Override

   370                     public Iterator<K> iterator() {

   371                         return new Iterator<K>() {

   372 

   373                             @Override

   374                             public boolean hasNext() {

   375                                 boolean result = iterator.hasNext();

   376                                 boolean otherResult = sparseIterator.hasNext();

   377                                 assert result == otherResult;

   378                                 return result;

   379                             }

   380 

   381                             @Override

   382                             public K next() {

   383                                 K sparseNext = sparseIterator.next();

   384                                 K next = iterator.next();

   385                                 assert Objects.equals(sparseNext, next);

   386                                 return next;

   387                             }

   388 

   389                             @Override

   390                             public void remove() {

   391                                 iterator.remove();

   392                                 sparseIterator.remove();

   393                             }

   394                         };

   395                     }

   396 

   397                 };

   398             }

   399 

   400             @Override

   401             public boolean isEmpty() {

   402                 boolean result = linkedMap.isEmpty();

   403                 assert result == sparseMap.isEmpty();

   404                 return result;

   405             }

   406 

   407             @Override

   408             public MapCursor<K, V> getEntries() {

   409                 Iterator<java.util.Map.Entry<K, V>> iterator = linkedMap.entrySet().iterator();

   410                 MapCursor<K, V> cursor = sparseMap.getEntries();

   411                 return new MapCursor<K, V>() {

   412 

   413                     private Map.Entry<K, V> current;

   414 

   415                     @Override

   416                     public boolean advance() {

   417                         boolean result = iterator.hasNext();

   418                         boolean otherResult = cursor.advance();

   419                         assert result == otherResult;

   420                         if (result) {

   421                             current = iterator.next();

   422                         }

   423 

   424                         return result;

   425                     }

   426 

   427                     @Override

   428                     public K getKey() {

   429                         K key = current.getKey();

   430                         assert key == cursor.getKey();

   431                         return key;

   432                     }

   433 

   434                     @Override

   435                     public V getValue() {

   436                         V value = current.getValue();

   437                         assert Objects.equals(value, cursor.getValue());

   438                         return value;

   439                     }

   440 

   441                     @Override

   442                     public void remove() {

   443                         iterator.remove();

   444                         cursor.remove();

   445                     }

   446                 };

   447             }

   448 

   449             @Override

   450             public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {

   451                 linkedMap.replaceAll(function);

   452                 sparseMap.replaceAll(function);

   453             }

   454         };

   455     }

   456 

   457     @Test

   458     public void testIterableConcat() {

   459         List<String> i1 = Arrays.asList("1", "2", "3");

   460         List<String> i2 = Arrays.asList();

   461         List<String> i3 = Arrays.asList("4", "5");

   462         List<String> i4 = Arrays.asList();

   463         List<String> i5 = Arrays.asList("6");

   464         List<String> iNull = null;

   465 

   466         List<String> actual = new ArrayList<>();

   467         List<String> expected = new ArrayList<>();

   468         expected.addAll(i1);

   469         expected.addAll(i2);

   470         expected.addAll(i3);

   471         expected.addAll(i4);

   472         expected.addAll(i5);

   473         Iterable<String> iterable = CollectionsUtil.concat(Arrays.asList(i1, i2, i3, i4, i5));

   474         for (String s : iterable) {

   475             actual.add(s);

   476         }

   477         Assert.assertEquals(expected, actual);

   478 

   479         Iterator<String> iter = iterable.iterator();

   480         while (iter.hasNext()) {

   481             iter.next();

   482         }

   483         try {

   484             iter.next();

   485             Assert.fail("Expected NoSuchElementException");

   486         } catch (NoSuchElementException e) {

   487             // Expected

   488         }

   489         try {

   490             CollectionsUtil.concat(i1, iNull);

   491             Assert.fail("Expected NullPointerException");

   492         } catch (NullPointerException e) {

   493             // Expected

   494         }

   495 

   496         Iterable<Object> emptyIterable = CollectionsUtil.concat(Collections.emptyList());

   497         Assert.assertFalse(emptyIterable.iterator().hasNext());

   498     }

   499 

   500     @Test

   501     public void testSetRemoval() {

   502         ArrayList<Integer> initialList = new ArrayList<>();

   503         ArrayList<Integer> removalList = new ArrayList<>();

   504         ArrayList<Integer> finalList = new ArrayList<>();

   505         EconomicSet<Integer> set = EconomicSet.create(Equivalence.IDENTITY);

   506         set.add(1);

   507         set.add(2);

   508         set.add(3);

   509         set.add(4);

   510         set.add(5);

   511         set.add(6);

   512         set.add(7);

   513         set.add(8);

   514         set.add(9);

   515         Iterator<Integer> i1 = set.iterator();

   516         while (i1.hasNext()) {

   517             initialList.add(i1.next());

   518         }

   519         int size = 0;

   520         Iterator<Integer> i2 = set.iterator();

   521         while (i2.hasNext()) {

   522             Integer elem = i2.next();

   523             if (size++ < 8) {

   524                 i2.remove();

   525             }

   526             removalList.add(elem);

   527         }

   528         Iterator<Integer> i3 = set.iterator();

   529         while (i3.hasNext()) {

   530             finalList.add(i3.next());

   531         }

   532         Assert.assertEquals(initialList, removalList);

   533         Assert.assertEquals(1, finalList.size());

   534         Assert.assertEquals(new Integer(9), finalList.get(0));

   535     }

   536 }