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 */ 23package org.graalvm.util.test; 24 25import static org.junit.Assert.assertEquals; 26 27import java.util.ArrayList; 28import java.util.Arrays; 29import java.util.Collections; 30import java.util.Iterator; 31import java.util.LinkedHashMap; 32import java.util.List; 33import java.util.Map; 34import java.util.NoSuchElementException; 35import java.util.Objects; 36import java.util.Random; 37import java.util.function.BiFunction; 38 39import org.graalvm.util.CollectionsUtil; 40import org.graalvm.util.EconomicMap; 41import org.graalvm.util.EconomicSet; 42import org.graalvm.util.Equivalence; 43import org.graalvm.util.MapCursor; 44import org.graalvm.util.ObjectSizeEstimate; 45import org.graalvm.util.UnmodifiableMapCursor; 46import org.junit.Assert; 47import org.junit.Test; 48 49public 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} 537