1 /* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package android.util.cts; 18 19 import android.os.Bundle; 20 import android.os.Parcel; 21 import android.os.Parcelable; 22 import android.test.AndroidTestCase; 23 import android.util.ArrayMap; 24 import android.util.Log; 25 26 import java.lang.reflect.InvocationTargetException; 27 import java.lang.reflect.Method; 28 import java.util.Collection; 29 import java.util.HashMap; 30 import java.util.Iterator; 31 import java.util.Map; 32 import java.util.Set; 33 34 public class ArrayMapTest extends AndroidTestCase { 35 static final boolean DEBUG = false; 36 37 static final int OP_ADD = 1; 38 static final int OP_REM = 2; 39 40 static int[] OPS = new int[] { 41 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 42 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 43 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 44 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 45 46 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 47 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 48 49 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 50 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 51 52 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 53 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 54 55 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 56 OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, 57 OP_ADD, OP_ADD, OP_ADD, 58 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 59 OP_REM, OP_REM, OP_REM, 60 OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, 61 }; 62 63 static int[] KEYS = new int[] { 64 // General adding and removing. 65 -1, 1900, 600, 200, 1200, 1500, 1800, 100, 1900, 66 2100, 300, 800, 600, 1100, 1300, 2000, 1000, 1400, 67 600, -1, 1900, 600, 300, 2100, 200, 800, 800, 68 1800, 1500, 1300, 1100, 2000, 1400, 1000, 1200, 1900, 69 70 // Shrink when removing item from end. 71 100, 200, 300, 400, 500, 600, 700, 800, 900, 72 900, 800, 700, 600, 500, 400, 300, 200, 100, 73 74 // Shrink when removing item from middle. 75 100, 200, 300, 400, 500, 600, 700, 800, 900, 76 900, 800, 700, 600, 500, 400, 200, 300, 100, 77 78 // Shrink when removing item from front. 79 100, 200, 300, 400, 500, 600, 700, 800, 900, 80 900, 800, 700, 600, 500, 400, 100, 200, 300, 81 82 // Test hash collisions. 83 105, 106, 108, 104, 102, 102, 107, 5, 205, 84 4, 202, 203, 3, 5, 101, 109, 200, 201, 85 0, -1, 100, 86 106, 108, 104, 102, 103, 105, 107, 101, 109, 87 -1, 100, 0, 88 4, 5, 3, 5, 200, 203, 202, 201, 205, 89 }; 90 91 public static class ControlledHash implements Parcelable { 92 final int mValue; 93 ControlledHash(int value)94 ControlledHash(int value) { 95 mValue = value; 96 } 97 98 @Override equals(Object o)99 public final boolean equals(Object o) { 100 if (o == null) { 101 return false; 102 } 103 return mValue == ((ControlledHash)o).mValue; 104 } 105 106 @Override hashCode()107 public final int hashCode() { 108 return mValue/100; 109 } 110 111 @Override toString()112 public final String toString() { 113 return Integer.toString(mValue); 114 } 115 116 @Override describeContents()117 public int describeContents() { 118 return 0; 119 } 120 121 @Override writeToParcel(Parcel dest, int flags)122 public void writeToParcel(Parcel dest, int flags) { 123 dest.writeInt(mValue); 124 } 125 126 public static final Parcelable.Creator<ControlledHash> CREATOR 127 = new Parcelable.Creator<ControlledHash>() { 128 public ControlledHash createFromParcel(Parcel in) { 129 return new ControlledHash(in.readInt()); 130 } 131 132 public ControlledHash[] newArray(int size) { 133 return new ControlledHash[size]; 134 } 135 }; 136 } 137 compare(Object v1, Object v2)138 private static boolean compare(Object v1, Object v2) { 139 if (v1 == null) { 140 return v2 == null; 141 } 142 if (v2 == null) { 143 return false; 144 } 145 return v1.equals(v2); 146 } 147 compareMaps(HashMap map, ArrayMap array)148 private static void compareMaps(HashMap map, ArrayMap array) { 149 if (map.size() != array.size()) { 150 fail("Bad size: expected " + map.size() + ", got " + array.size()); 151 } 152 153 Set<Map.Entry> mapSet = map.entrySet(); 154 for (Map.Entry entry : mapSet) { 155 Object expValue = entry.getValue(); 156 Object gotValue = array.get(entry.getKey()); 157 if (!compare(expValue, gotValue)) { 158 fail("Bad value: expected " + expValue + ", got " + gotValue 159 + " at key " + entry.getKey()); 160 } 161 } 162 163 for (int i=0; i<array.size(); i++) { 164 Object gotValue = array.valueAt(i); 165 Object key = array.keyAt(i); 166 Object expValue = map.get(key); 167 if (!compare(expValue, gotValue)) { 168 fail("Bad value: expected " + expValue + ", got " + gotValue 169 + " at key " + key); 170 } 171 } 172 173 if (map.entrySet().hashCode() != array.entrySet().hashCode()) { 174 fail("Entry set hash codes differ: map=0x" 175 + Integer.toHexString(map.entrySet().hashCode()) + " array=0x" 176 + Integer.toHexString(array.entrySet().hashCode())); 177 } 178 179 if (!map.entrySet().equals(array.entrySet())) { 180 fail("Failed calling equals on map entry set against array set"); 181 } 182 183 if (!array.entrySet().equals(map.entrySet())) { 184 fail("Failed calling equals on array entry set against map set"); 185 } 186 187 if (map.keySet().hashCode() != array.keySet().hashCode()) { 188 fail("Key set hash codes differ: map=0x" 189 + Integer.toHexString(map.keySet().hashCode()) + " array=0x" 190 + Integer.toHexString(array.keySet().hashCode())); 191 } 192 193 if (!map.keySet().equals(array.keySet())) { 194 fail("Failed calling equals on map key set against array set"); 195 } 196 197 if (!array.keySet().equals(map.keySet())) { 198 fail("Failed calling equals on array key set against map set"); 199 } 200 201 if (!map.keySet().containsAll(array.keySet())) { 202 fail("Failed map key set contains all of array key set"); 203 } 204 205 if (!array.keySet().containsAll(map.keySet())) { 206 fail("Failed array key set contains all of map key set"); 207 } 208 209 if (!array.containsAll(map.keySet())) { 210 fail("Failed array contains all of map key set"); 211 } 212 213 if (!map.entrySet().containsAll(array.entrySet())) { 214 fail("Failed map entry set contains all of array entry set"); 215 } 216 217 if (!array.entrySet().containsAll(map.entrySet())) { 218 fail("Failed array entry set contains all of map entry set"); 219 } 220 } 221 validateArrayMap(ArrayMap array)222 private static void validateArrayMap(ArrayMap array) { 223 Set<Map.Entry> entrySet = array.entrySet(); 224 int index=0; 225 Iterator<Map.Entry> entryIt = entrySet.iterator(); 226 while (entryIt.hasNext()) { 227 Map.Entry entry = entryIt.next(); 228 Object value = entry.getKey(); 229 Object realValue = array.keyAt(index); 230 if (!compare(realValue, value)) { 231 fail("Bad array map entry set: expected key " + realValue 232 + ", got " + value + " at index " + index); 233 } 234 value = entry.getValue(); 235 realValue = array.valueAt(index); 236 if (!compare(realValue, value)) { 237 fail("Bad array map entry set: expected value " + realValue 238 + ", got " + value + " at index " + index); 239 } 240 index++; 241 } 242 243 index = 0; 244 Set keySet = array.keySet(); 245 Iterator keyIt = keySet.iterator(); 246 while (keyIt.hasNext()) { 247 Object value = keyIt.next(); 248 Object realValue = array.keyAt(index); 249 if (!compare(realValue, value)) { 250 fail("Bad array map key set: expected key " + realValue 251 + ", got " + value + " at index " + index); 252 } 253 index++; 254 } 255 256 index = 0; 257 Collection valueCol = array.values(); 258 Iterator valueIt = valueCol.iterator(); 259 while (valueIt.hasNext()) { 260 Object value = valueIt.next(); 261 Object realValue = array.valueAt(index); 262 if (!compare(realValue, value)) { 263 fail("Bad array map value col: expected value " + realValue 264 + ", got " + value + " at index " + index); 265 } 266 index++; 267 } 268 } 269 compareBundles(Bundle bundle1, Bundle bundle2)270 private static void compareBundles(Bundle bundle1, Bundle bundle2) { 271 Set<String> keySet1 = bundle1.keySet(); 272 Iterator<String> iterator1 = keySet1.iterator(); 273 while (iterator1.hasNext()) { 274 String key = iterator1.next(); 275 int value1 = bundle1.getInt(key); 276 if (bundle2.get(key) == null) { 277 fail("Bad Bundle: bundle2 didn't have expected key " + key); 278 } 279 int value2 = bundle2.getInt(key); 280 if (value1 != value2) { 281 fail("Bad Bundle: at key key " + key + " expected " + value1 + ", got " + value2); 282 } 283 } 284 Set<String> keySet2 = bundle2.keySet(); 285 Iterator<String> iterator2 = keySet2.iterator(); 286 while (iterator2.hasNext()) { 287 String key = iterator2.next(); 288 if (bundle1.get(key) == null) { 289 fail("Bad Bundle: bundle1 didn't have expected key " + key); 290 } 291 int value1 = bundle1.getInt(key); 292 int value2 = bundle2.getInt(key); 293 if (value1 != value2) { 294 fail("Bad Bundle: at key key " + key + " expected " + value1 + ", got " + value2); 295 } 296 } 297 } 298 dump(Map map, ArrayMap array)299 private static void dump(Map map, ArrayMap array) { 300 Log.e("test", "HashMap of " + map.size() + " entries:"); 301 Set<Map.Entry> mapSet = map.entrySet(); 302 for (Map.Entry entry : mapSet) { 303 Log.e("test", " " + entry.getKey() + " -> " + entry.getValue()); 304 } 305 Log.e("test", "ArrayMap of " + array.size() + " entries:"); 306 for (int i=0; i<array.size(); i++) { 307 Log.e("test", " " + array.keyAt(i) + " -> " + array.valueAt(i)); 308 } 309 } 310 dump(ArrayMap map1, ArrayMap map2)311 private static void dump(ArrayMap map1, ArrayMap map2) { 312 Log.e("test", "ArrayMap of " + map1.size() + " entries:"); 313 for (int i=0; i<map1.size(); i++) { 314 Log.e("test", " " + map1.keyAt(i) + " -> " + map1.valueAt(i)); 315 } 316 Log.e("test", "ArrayMap of " + map2.size() + " entries:"); 317 for (int i=0; i<map2.size(); i++) { 318 Log.e("test", " " + map2.keyAt(i) + " -> " + map2.valueAt(i)); 319 } 320 } 321 dump(Bundle bundle1, Bundle bundle2)322 private static void dump(Bundle bundle1, Bundle bundle2) { 323 Log.e("test", "First Bundle of " + bundle1.size() + " entries:"); 324 Set<String> keys1 = bundle1.keySet(); 325 for (String key : keys1) { 326 Log.e("test", " " + key + " -> " + bundle1.get(key)); 327 } 328 Log.e("test", "Second Bundle of " + bundle2.size() + " entries:"); 329 Set<String> keys2 = bundle2.keySet(); 330 for (String key : keys2) { 331 Log.e("test", " " + key + " -> " + bundle2.get(key)); 332 } 333 } 334 testBasicArrayMap()335 public void testBasicArrayMap() { 336 HashMap<ControlledHash, Integer> hashMap = new HashMap<ControlledHash, Integer>(); 337 ArrayMap<ControlledHash, Integer> arrayMap = new ArrayMap<ControlledHash, Integer>(); 338 Bundle bundle = new Bundle(); 339 340 for (int i=0; i<OPS.length; i++) { 341 Integer oldHash; 342 Integer oldArray; 343 ControlledHash key = KEYS[i] < 0 ? null : new ControlledHash(KEYS[i]); 344 String strKey = KEYS[i] < 0 ? null : Integer.toString(KEYS[i]); 345 switch (OPS[i]) { 346 case OP_ADD: 347 if (DEBUG) Log.i("test", "Adding key: " + key); 348 oldHash = hashMap.put(key, i); 349 oldArray = arrayMap.put(key, i); 350 bundle.putInt(strKey, i); 351 break; 352 case OP_REM: 353 if (DEBUG) Log.i("test", "Removing key: " + key); 354 oldHash = hashMap.remove(key); 355 oldArray = arrayMap.remove(key); 356 bundle.remove(strKey); 357 break; 358 default: 359 fail("Bad operation " + OPS[i] + " @ " + i); 360 return; 361 } 362 if (!compare(oldHash, oldArray)) { 363 String msg = "Bad result: expected " + oldHash + ", got " + oldArray; 364 Log.e("test", msg); 365 dump(hashMap, arrayMap); 366 fail(msg); 367 } 368 try { 369 validateArrayMap(arrayMap); 370 } catch (Throwable e) { 371 Log.e("test", e.getMessage()); 372 dump(hashMap, arrayMap); 373 throw e; 374 } 375 try { 376 compareMaps(hashMap, arrayMap); 377 } catch (Throwable e) { 378 Log.e("test", e.getMessage()); 379 dump(hashMap, arrayMap); 380 throw e; 381 } 382 Parcel parcel = Parcel.obtain(); 383 bundle.writeToParcel(parcel, 0); 384 parcel.setDataPosition(0); 385 Bundle bundle2 = parcel.readBundle(); 386 try { 387 compareBundles(bundle, bundle2); 388 } catch (Throwable e) { 389 Log.e("test", e.getMessage()); 390 dump(bundle, bundle2); 391 throw e; 392 } 393 } 394 395 arrayMap.put(new ControlledHash(50000), 100); 396 ControlledHash lookup = new ControlledHash(50000); 397 Iterator<ControlledHash> it = arrayMap.keySet().iterator(); 398 while (it.hasNext()) { 399 if (it.next().equals(lookup)) { 400 it.remove(); 401 } 402 } 403 if (arrayMap.containsKey(lookup)) { 404 String msg = "Bad map iterator: didn't remove test key"; 405 Log.e("test", msg); 406 dump(hashMap, arrayMap); 407 fail(msg); 408 } 409 410 //Log.e("test", "Test successful; printing final map."); 411 //dump(hashMap, arrayMap); 412 } 413 414 public void testCopyArrayMap() { 415 // map copy constructor test 416 ArrayMap newMap = new ArrayMap<Integer, String>(); 417 for (int i = 0; i < 10; ++i) { 418 newMap.put(i, String.valueOf(i)); 419 } 420 ArrayMap mapCopy = new ArrayMap(newMap); 421 if (!compare(mapCopy, newMap)) { 422 String msg = "ArrayMap copy constructor failure: expected " + 423 newMap + ", got " + mapCopy; 424 Log.e("test", msg); 425 dump(newMap, mapCopy); 426 fail(msg); 427 return; 428 } 429 } 430 431 public void testEqualsArrayMap() { 432 ArrayMap<Integer, String> map1 = new ArrayMap<Integer, String>(); 433 ArrayMap<Integer, String> map2 = new ArrayMap<Integer, String>(); 434 HashMap<Integer, String> map3 = new HashMap<Integer, String>(); 435 if (!compare(map1, map2) || !compare(map1, map3) || !compare(map3, map2)) { 436 fail("ArrayMap equals failure for empty maps " + map1 + ", " + 437 map2 + ", " + map3); 438 } 439 440 for (int i = 0; i < 10; ++i) { 441 String value = String.valueOf(i); 442 map1.put(i, value); 443 map2.put(i, value); 444 map3.put(i, value); 445 } 446 if (!compare(map1, map2) || !compare(map1, map3) || !compare(map3, map2)) { 447 fail("ArrayMap equals failure for populated maps " + map1 + ", " + 448 map2 + ", " + map3); 449 } 450 451 map1.remove(0); 452 if (compare(map1, map2) || compare(map1, map3) || compare(map3, map1)) { 453 fail("ArrayMap equals failure for map size " + map1 + ", " + 454 map2 + ", " + map3); 455 } 456 457 map1.put(0, "-1"); 458 if (compare(map1, map2) || compare(map1, map3) || compare(map3, map1)) { 459 fail("ArrayMap equals failure for map contents " + map1 + ", " + 460 map2 + ", " + map3); 461 } 462 } 463 464 /** 465 * Test creating a malformed array map with duplicated keys and that we will catch this 466 * when unparcelling. 467 */ 468 public void testDuplicateKeys() throws NoSuchMethodException, 469 InvocationTargetException, IllegalAccessException, NoSuchFieldException { 470 ArrayMap<String, Object> map1 = new ArrayMap(2); 471 472 Method appendMethod = ArrayMap.class.getMethod("append", Object.class, Object.class); 473 appendMethod.invoke(map1, Integer.toString(100000), "foo"); 474 appendMethod.invoke(map1, Integer.toString(100000), "bar"); 475 476 // Now parcel/unparcel, and verify we get the expected error. 477 Parcel parcel = Parcel.obtain(); 478 Method writeArrayMapMethod = Parcel.class.getMethod("writeArrayMap", ArrayMap.class); 479 writeArrayMapMethod.invoke(parcel, map1); 480 parcel.setDataPosition(0); 481 ArrayMap<String, Object> map2 = new ArrayMap(2); 482 483 try { 484 Parcel.class.getMethod("readArrayMap", ArrayMap.class, ClassLoader.class).invoke( 485 parcel, map2, null); 486 } catch (InvocationTargetException e) { 487 Throwable cause = e.getCause(); 488 if (cause instanceof IllegalArgumentException) { 489 // Good! 490 return; 491 } 492 throw e; 493 } 494 495 String msg = "Didn't throw expected IllegalArgumentException"; 496 Log.e("test", msg); 497 dump(map1, map2); 498 fail(msg); 499 } 500 } 501