1 /*-
2  * Copyright (c) 2002, 2020 Oracle and/or its affiliates.  All rights reserved.
3  *
4  * See the file LICENSE for license information.
5  *
6  */
7 
8 package com.sleepycat.collections.test;
9 
10 import static org.junit.Assert.assertEquals;
11 import static org.junit.Assert.assertFalse;
12 import static org.junit.Assert.assertNotNull;
13 import static org.junit.Assert.assertNull;
14 import static org.junit.Assert.assertTrue;
15 import static org.junit.Assert.fail;
16 
17 import java.util.ArrayList;
18 import java.util.Collection;
19 import java.util.Collections;
20 import java.util.HashMap;
21 import java.util.Iterator;
22 import java.util.List;
23 import java.util.ListIterator;
24 import java.util.Map;
25 import java.util.NoSuchElementException;
26 import java.util.Set;
27 import java.util.SortedMap;
28 import java.util.SortedSet;
29 import java.util.concurrent.ConcurrentMap;
30 import java.util.regex.Pattern;
31 
32 import org.junit.Test;
33 import org.junit.runner.RunWith;
34 import org.junit.runners.Parameterized;
35 import org.junit.runners.Parameterized.Parameters;
36 
37 import com.sleepycat.bind.EntityBinding;
38 import com.sleepycat.bind.EntryBinding;
39 import com.sleepycat.collections.MapEntryParameter;
40 import com.sleepycat.collections.StoredCollection;
41 import com.sleepycat.collections.StoredCollections;
42 import com.sleepycat.collections.StoredContainer;
43 import com.sleepycat.collections.StoredEntrySet;
44 import com.sleepycat.collections.StoredIterator;
45 import com.sleepycat.collections.StoredKeySet;
46 import com.sleepycat.collections.StoredList;
47 import com.sleepycat.collections.StoredMap;
48 import com.sleepycat.collections.StoredSortedEntrySet;
49 import com.sleepycat.collections.StoredSortedKeySet;
50 import com.sleepycat.collections.StoredSortedMap;
51 import com.sleepycat.collections.StoredSortedValueSet;
52 import com.sleepycat.collections.StoredValueSet;
53 import com.sleepycat.collections.TransactionRunner;
54 import com.sleepycat.collections.TransactionWorker;
55 import com.sleepycat.compat.DbCompat;
56 import com.sleepycat.db.Database;
57 import com.sleepycat.db.DatabaseException;
58 import com.sleepycat.db.Environment;
59 import com.sleepycat.util.ExceptionUnwrapper;
60 import com.sleepycat.util.test.SharedTestUtils;
61 import com.sleepycat.util.test.TestBase;
62 import com.sleepycat.util.test.TestEnv;
63 
64 /**
65  * @author Mark Hayes
66  */
67 @RunWith(Parameterized.class)
68 public class CollectionTest extends TestBase {
69 
70     private static final int NONE = 0;
71     private static final int SUB = 1;
72     private static final int HEAD = 2;
73     private static final int TAIL = 3;
74 
75     /*
76      * For long tests we permute testStoredIterator to test both StoredIterator
77      * and BlockIterator.  When testing BlockIterator, we permute the maxKey
78      * over the array values below.  BlockIterator's block size is 10.  So we
79      * test below the block size (6), at the block size (10), and above it (14
80      * and 22).
81      */
82     protected static final int DEFAULT_MAX_KEY = 6;
83     private static final int[] MAX_KEYS = {6, 10, 14, 22};
84 
85     private boolean testStoredIterator;
86     private static int maxKey; /* Must be a multiple of 2. */
87     protected static int beginKey = 1;
88     private static int endKey;
89 
90     private Environment env;
91     private Database store;
92     private Database index;
93     private final boolean isEntityBinding;
94     private final boolean isAutoCommit;
95     private TestStore testStore;
96     private String testName;
97     private final EntryBinding keyBinding;
98     private final EntryBinding valueBinding;
99     private final EntityBinding entityBinding;
100     private TransactionRunner readRunner;
101     private TransactionRunner writeRunner;
102     private TransactionRunner writeIterRunner;
103     private TestEnv testEnv;
104 
105     private StoredMap map;
106     private StoredMap imap; // insertable map (primary store for indexed map)
107     private StoredSortedMap smap; // sorted map (null or equal to map)
108     private StoredMap saveMap;
109     private StoredSortedMap saveSMap;
110     private int rangeType;
111     private StoredList list;
112     private StoredList ilist; // insertable list (primary store for index list)
113     private StoredList saveList;
114     private StoredKeySet keySet;
115     private StoredValueSet valueSet;
116 
117     @Parameters
genParams()118     public static List<Object[]> genParams() {
119         if (SharedTestUtils.runLongTests()){
120             List<Object[]> list = baseParams(true, DEFAULT_MAX_KEY);
121 
122             for (int i : MAX_KEYS)
123                 list.addAll(baseParams(false, i));
124 
125             return list;
126         }
127         return baseParams(false, 6);
128     }
129 
baseParams(boolean storedIter, int maximumKey)130     private static List<Object[]> baseParams(boolean storedIter,
131                                              int maximumKey){
132 
133         List <Object[]> list = new ArrayList<Object[]>();
134         for (int i = 0; i < TestEnv.ALL.length; i += 1) {
135             for (int j = 0; j < TestStore.ALL.length; j += 1) {
136                 for (int k = 0; k < 2; k += 1) {
137                     boolean entityBinding = (k != 0);
138 
139                     list.add(new Object[] {TestEnv.ALL[i], TestStore.ALL[j],
140                             entityBinding, false, storedIter, maximumKey});
141 
142                     if (TestEnv.ALL[i].isTxnMode()) {
143                         list.add(new Object[]
144                             {TestEnv.ALL[i], TestStore.ALL[j], entityBinding,
145                              true, storedIter, maximumKey});
146                     }
147                 }
148             }
149         }
150 
151         return list;
152     }
153 
CollectionTest(TestEnv testEnv, TestStore testStore, boolean isEntityBinding, boolean isAutoCommit, boolean storedIter, int maxKey)154     public CollectionTest(TestEnv testEnv,
155                           TestStore testStore,
156                           boolean isEntityBinding,
157                           boolean isAutoCommit,
158                           boolean storedIter,
159                           int maxKey) {
160 
161         this.testEnv = testEnv;
162         this.testStore = testStore;
163         this.isEntityBinding = isEntityBinding;
164         this.isAutoCommit = isAutoCommit;
165 
166         keyBinding = testStore.getKeyBinding();
167         valueBinding = testStore.getValueBinding();
168         entityBinding = testStore.getEntityBinding();
169 
170         setParams(storedIter, maxKey);
171         customName = testName;
172     }
173 
setParams(boolean storedIter, int maximumKey)174     private void setParams(boolean storedIter, int maximumKey) {
175 
176         testStoredIterator = storedIter;
177         maxKey = maximumKey;
178         endKey = maximumKey;
179 
180         testName = testEnv.getName() + '-' + testStore.getName() +
181                     (isEntityBinding ? "-entity" : "-value") +
182                     (isAutoCommit ? "-autoCommit" : "") +
183                     (testStoredIterator ? "-storedIter" : "") +
184                     ((maxKey != DEFAULT_MAX_KEY) ? ("-maxKey-" + maxKey) : "");
185     }
186 
187 
188     @Test
runTest()189     public void runTest()
190         throws Exception {
191 
192         try {
193             env = testEnv.open(testName);
194             // For testing auto-commit, use a normal (transactional) runner for
195             // all reading and for writing via an iterator, and a do-nothing
196             // runner for writing via collections; if auto-commit is tested,
197             // the per-collection auto-commit property will be set elsewhere.
198             //
199             TransactionRunner normalRunner = newTransactionRunner(env);
200             normalRunner.setAllowNestedTransactions(
201                     DbCompat.NESTED_TRANSACTIONS);
202             TransactionRunner nullRunner = new NullTransactionRunner(env);
203             readRunner = nullRunner;
204             if (isAutoCommit) {
205                 writeRunner = nullRunner;
206                 writeIterRunner = testStoredIterator ? normalRunner
207                                                      : nullRunner;
208             } else {
209                 writeRunner = normalRunner;
210                 writeIterRunner = normalRunner;
211             }
212 
213             store = testStore.open(env, "unindexed.db");
214             testUnindexed();
215             store.close();
216             store = null;
217 
218             TestStore indexOf = testStore.getIndexOf();
219             if (indexOf != null) {
220                 store = indexOf.open(env, "indexed.db");
221                 index = testStore.openIndex(store, "index.db");
222                 testIndexed();
223                 index.close();
224                 index = null;
225                 store.close();
226                 store = null;
227             }
228             env.close();
229             env = null;
230         } catch (Exception e) {
231             throw ExceptionUnwrapper.unwrap(e);
232         } finally {
233             if (index != null) {
234                 try {
235                     index.close();
236                 } catch (Exception e) {
237                 }
238             }
239             if (store != null) {
240                 try {
241                     store.close();
242                 } catch (Exception e) {
243                 }
244             }
245             if (env != null) {
246                 try {
247                     env.close();
248                 } catch (Exception e) {
249                 }
250             }
251             /* Ensure that GC can cleanup. */
252             index = null;
253             store = null;
254             env = null;
255             readRunner = null;
256             writeRunner = null;
257             writeIterRunner = null;
258             map = null;
259             imap = null;
260             smap = null;
261             saveMap = null;
262             saveSMap = null;
263             list = null;
264             ilist = null;
265             saveList = null;
266             keySet = null;
267             valueSet = null;
268             testEnv = null;
269             testStore = null;
270         }
271     }
272 
273     /**
274      * Is overridden in XACollectionTest.
275      * @throws DatabaseException from subclasses.
276      */
newTransactionRunner(Environment env)277     protected TransactionRunner newTransactionRunner(Environment env)
278         throws DatabaseException {
279 
280         return new TransactionRunner(env);
281     }
282 
testCreation(StoredContainer cont, int expectSize)283     void testCreation(StoredContainer cont, int expectSize) {
284         assertEquals(index != null, cont.isSecondary());
285         assertEquals(testStore.isOrdered(), cont.isOrdered());
286         assertEquals(testStore.areKeyRangesAllowed(),
287                      cont.areKeyRangesAllowed());
288         assertEquals(testStore.areKeysRenumbered(), cont.areKeysRenumbered());
289         assertEquals(testStore.areDuplicatesAllowed(),
290                      cont.areDuplicatesAllowed());
291         assertEquals(testEnv.isTxnMode(), cont.isTransactional());
292         assertEquals(expectSize, cont.size());
293     }
294 
testMapCreation(ConcurrentMap map)295     void testMapCreation(ConcurrentMap map) {
296         assertTrue(map.values() instanceof Set);
297         assertEquals(testStore.areKeyRangesAllowed(),
298                      map.keySet() instanceof SortedSet);
299         assertEquals(testStore.areKeyRangesAllowed(),
300                      map.entrySet() instanceof SortedSet);
301         assertEquals(testStore.areKeyRangesAllowed() && isEntityBinding,
302                      map.values() instanceof SortedSet);
303     }
304 
testUnindexed()305     void testUnindexed()
306         throws Exception {
307 
308         // create primary map
309         if (testStore.areKeyRangesAllowed()) {
310             if (isEntityBinding) {
311                 smap = new StoredSortedMap(store, keyBinding,
312                                            entityBinding,
313                                            testStore.getKeyAssigner());
314                 valueSet = new StoredSortedValueSet(store, entityBinding,
315                                                     true);
316             } else {
317                 smap = new StoredSortedMap(store, keyBinding,
318                                            valueBinding,
319                                            testStore.getKeyAssigner());
320                 // sorted value set is not possible since key cannot be derived
321                 // for performing subSet, etc.
322             }
323             keySet = new StoredSortedKeySet(store, keyBinding, true);
324             map = smap;
325         } else {
326             if (isEntityBinding) {
327                 map = new StoredMap(store, keyBinding, entityBinding,
328                                     testStore.getKeyAssigner());
329                 valueSet = new StoredValueSet(store, entityBinding, true);
330             } else {
331                 map = new StoredMap(store, keyBinding, valueBinding,
332                                     testStore.getKeyAssigner());
333                 valueSet = new StoredValueSet(store, valueBinding, true);
334             }
335             smap = null;
336             keySet = new StoredKeySet(store, keyBinding, true);
337         }
338         imap = map;
339 
340         // create primary list
341         if (testStore.hasRecNumAccess()) {
342             if (isEntityBinding) {
343                 ilist = new StoredList(store, entityBinding,
344                                        testStore.getKeyAssigner());
345             } else {
346                 ilist = new StoredList(store, valueBinding,
347                                        testStore.getKeyAssigner());
348             }
349             list = ilist;
350         } else {
351             try {
352                 if (isEntityBinding) {
353                     ilist = new StoredList(store, entityBinding,
354                                            testStore.getKeyAssigner());
355                 } else {
356                     ilist = new StoredList(store, valueBinding,
357                                            testStore.getKeyAssigner());
358                 }
359                 fail();
360             } catch (IllegalArgumentException expected) {}
361         }
362 
363         testCreation(map, 0);
364         if (list != null) {
365             testCreation(list, 0);
366         }
367         testMapCreation(map);
368         addAll();
369         testAll();
370     }
371 
testIndexed()372     void testIndexed()
373         throws Exception {
374 
375         // create primary map
376         if (isEntityBinding) {
377             map = new StoredMap(store, keyBinding, entityBinding,
378                                 testStore.getKeyAssigner());
379         } else {
380             map = new StoredMap(store, keyBinding, valueBinding,
381                                 testStore.getKeyAssigner());
382         }
383         imap = map;
384         smap = null;
385         // create primary list
386         if (testStore.hasRecNumAccess()) {
387             if (isEntityBinding) {
388                 list = new StoredList(store, entityBinding,
389                                       testStore.getKeyAssigner());
390             } else {
391                 list = new StoredList(store, valueBinding,
392                                       testStore.getKeyAssigner());
393             }
394             ilist = list;
395         }
396 
397         addAll();
398         readAll();
399 
400         // create indexed map (keySet/valueSet)
401         if (testStore.areKeyRangesAllowed()) {
402             if (isEntityBinding) {
403                 map = smap = new StoredSortedMap(index, keyBinding,
404                                                  entityBinding, true);
405                 valueSet = new StoredSortedValueSet(index, entityBinding,
406                                                     true);
407             } else {
408                 map = smap = new StoredSortedMap(index, keyBinding,
409                                                  valueBinding, true);
410                 // sorted value set is not possible since key cannot be derived
411                 // for performing subSet, etc.
412             }
413             keySet = new StoredSortedKeySet(index, keyBinding, true);
414         } else {
415             if (isEntityBinding) {
416                 map = new StoredMap(index, keyBinding, entityBinding, true);
417                 valueSet = new StoredValueSet(index, entityBinding, true);
418             } else {
419                 map = new StoredMap(index, keyBinding, valueBinding, true);
420                 valueSet = new StoredValueSet(index, valueBinding, true);
421             }
422             smap = null;
423             keySet = new StoredKeySet(index, keyBinding, true);
424         }
425 
426         // create indexed list
427         if (testStore.hasRecNumAccess()) {
428             if (isEntityBinding) {
429                 list = new StoredList(index, entityBinding, true);
430             } else {
431                 list = new StoredList(index, valueBinding, true);
432             }
433         } else {
434             try {
435                 if (isEntityBinding) {
436                     list = new StoredList(index, entityBinding, true);
437                 } else {
438                     list = new StoredList(index, valueBinding, true);
439                 }
440                 fail();
441             } catch (IllegalArgumentException expected) {}
442         }
443 
444         testCreation(map, maxKey);
445         testCreation((StoredContainer) map.values(), maxKey);
446         testCreation((StoredContainer) map.keySet(), maxKey);
447         testCreation((StoredContainer) map.entrySet(), maxKey);
448         if (list != null) {
449             testCreation(list, maxKey);
450         }
451         testMapCreation(map);
452         testAll();
453     }
454 
testAll()455     void testAll()
456         throws Exception {
457 
458         checkKeySetAndValueSet();
459         readAll();
460         updateAll();
461         readAll();
462         if (!map.areKeysRenumbered()) {
463             removeOdd();
464             readEven();
465             addOdd();
466             readAll();
467             removeOddIter();
468             readEven();
469             if (imap.areDuplicatesAllowed()) {
470                 addOddDup();
471             } else {
472                 addOdd();
473             }
474             readAll();
475             removeOddEntry();
476             readEven();
477             addOdd();
478             readAll();
479             if (isEntityBinding) {
480                 removeOddEntity();
481                 readEven();
482                 addOddEntity();
483                 readAll();
484             }
485             bulkOperations();
486         }
487         if (isListAddAllowed()) {
488             removeOddList();
489             readEvenList();
490             addOddList();
491             readAll();
492             if (!isEntityBinding) {
493                 removeOddListValue();
494                 readEvenList();
495                 addOddList();
496                 readAll();
497             }
498         }
499         if (list != null) {
500             bulkListOperations();
501         } else {
502             listOperationsNotAllowed();
503         }
504         if (smap != null) {
505             readWriteRange(SUB,  1, 1);
506             readWriteRange(HEAD, 1, 1);
507             readWriteRange(SUB,  1, maxKey);
508             readWriteRange(HEAD, 1, maxKey);
509             readWriteRange(TAIL, 1, maxKey);
510             readWriteRange(SUB,  1, 3);
511             readWriteRange(HEAD, 1, 3);
512             readWriteRange(SUB,  2, 2);
513             readWriteRange(SUB,  2, maxKey);
514             readWriteRange(TAIL, 2, maxKey);
515             readWriteRange(SUB,  maxKey, maxKey);
516             readWriteRange(TAIL, maxKey, maxKey);
517             readWriteRange(SUB,  maxKey + 1, maxKey + 1);
518             readWriteRange(TAIL, maxKey + 1, maxKey + 1);
519             readWriteRange(SUB,  0, 0);
520             readWriteRange(HEAD, 0, 0);
521         }
522         updateAll();
523         readAll();
524         if (map.areDuplicatesAllowed()) {
525             readWriteDuplicates();
526             readAll();
527         } else {
528             duplicatesNotAllowed();
529             readAll();
530         }
531         if (testEnv.isCdbMode()) {
532             testCdbLocking();
533         }
534         removeAll();
535         if (!map.areKeysRenumbered()) {
536             testConcurrentMap();
537         }
538         if (isListAddAllowed()) {
539             testIterAddList();
540             clearAll();
541         }
542         if (imap.areDuplicatesAllowed()) {
543             testIterAddDuplicates();
544             clearAll();
545         }
546         if (isListAddAllowed()) {
547             addAllList();
548             readAll();
549             removeAllList();
550         }
551         appendAll();
552     }
553 
checkKeySetAndValueSet()554     void checkKeySetAndValueSet() {
555 
556         // use bulk operations to check that explicitly constructed
557         // keySet/valueSet are equivalent
558         assertEquals(keySet, imap.keySet());
559         if (valueSet != null) {
560             assertEquals(valueSet, imap.values());
561         }
562     }
563 
iterator(Collection storedCollection)564     Iterator iterator(Collection storedCollection) {
565 
566         if (testStoredIterator) {
567             return ((StoredCollection) storedCollection).storedIterator();
568         } else {
569             return storedCollection.iterator();
570         }
571     }
572 
addAll()573     void addAll()
574         throws Exception {
575 
576         writeRunner.run(new TransactionWorker() {
577             public void doWork() {
578                 assertTrue(imap.isEmpty());
579                 Iterator iter = iterator(imap.entrySet());
580                 try {
581                     assertTrue(!iter.hasNext());
582                 } finally {
583                     StoredIterator.close(iter);
584                 }
585                 assertEquals(0, imap.keySet().toArray().length);
586                 assertEquals(0, imap.keySet().toArray(new Object[0]).length);
587                 assertEquals(0, imap.entrySet().toArray().length);
588                 assertEquals(0, imap.entrySet().toArray(new Object[0]).length);
589                 assertEquals(0, imap.values().toArray().length);
590                 assertEquals(0, imap.values().toArray(new Object[0]).length);
591 
592                 for (int i = beginKey; i <= endKey; i += 1) {
593                     Long key = makeKey(i);
594                     Object val = makeVal(i);
595                     assertNull(imap.get(key));
596                     assertTrue(!imap.keySet().contains(key));
597                     assertTrue(!imap.values().contains(val));
598                     assertNull(imap.put(key, val));
599                     assertEquals(val, imap.get(key));
600                     assertTrue(imap.keySet().contains(key));
601                     assertTrue(imap.values().contains(val));
602                     assertTrue(imap.duplicates(key).contains(val));
603                     if (!imap.areDuplicatesAllowed()) {
604                         assertEquals(val, imap.put(key, val));
605                     }
606                     checkDupsSize(1, imap.duplicates(key));
607                 }
608                 assertTrue(!imap.isEmpty());
609             }
610         });
611     }
612 
appendAll()613     void appendAll()
614         throws Exception {
615 
616         writeRunner.run(new TransactionWorker() {
617             public void doWork() {
618                 assertTrue(imap.isEmpty());
619 
620                 TestKeyAssigner keyAssigner = testStore.getKeyAssigner();
621                 if (keyAssigner != null) {
622                     keyAssigner.reset();
623                 }
624 
625                 for (int i = beginKey; i <= endKey; i += 1) {
626                     boolean useList = (i & 1) == 0;
627                     Long key = makeKey(i);
628                     Object val = makeVal(i);
629                     assertNull(imap.get(key));
630                     if (keyAssigner != null) {
631                         if (useList && ilist != null) {
632                             assertEquals(i - 1, ilist.append(val));
633                         } else {
634                             assertEquals(key, imap.append(val));
635                         }
636                         assertEquals(val, imap.get(key));
637                     } else {
638                         Long recnoKey;
639                         if (useList && ilist != null) {
640                             recnoKey = new Long(ilist.append(val) + 1);
641                         } else {
642                             recnoKey = (Long) imap.append(val);
643                         }
644                         assertNotNull(recnoKey);
645                         Object recnoVal;
646                         if (isEntityBinding) {
647                             recnoVal = makeEntity(recnoKey.intValue(), i);
648                         } else {
649                             recnoVal = val;
650                         }
651                         assertEquals(recnoVal, imap.get(recnoKey));
652                     }
653                 }
654             }
655         });
656     }
657 
updateAll()658     void updateAll()
659         throws Exception {
660 
661         writeRunner.run(new TransactionWorker() {
662             public void doWork() throws Exception {
663                 for (int i = beginKey; i <= endKey; i += 1) {
664                     Long key = makeKey(i);
665                     Object val = makeVal(i);
666                     if (!imap.areDuplicatesAllowed()) {
667                         assertEquals(val, imap.put(key, val));
668                     }
669                     if (isEntityBinding) {
670                         assertTrue(!imap.values().add(val));
671                     }
672                     checkDupsSize(1, imap.duplicates(key));
673                     if (ilist != null) {
674                         int idx = i - 1;
675                         assertEquals(val, ilist.set(idx, val));
676                     }
677                 }
678                 updateIter(map.entrySet());
679                 updateIter(map.values());
680                 if (beginKey <= endKey) {
681                     ListIterator iter = (ListIterator) iterator(map.keySet());
682                     try {
683                         assertNotNull(iter.next());
684                         iter.set(makeKey(beginKey));
685                         fail();
686                     } catch (UnsupportedOperationException e) {
687                     } finally {
688                         StoredIterator.close(iter);
689                     }
690                 }
691                 if (list != null) {
692                     updateIter(list);
693                 }
694             }
695         });
696     }
697 
updateIter(final Collection coll)698     void updateIter(final Collection coll)
699         throws Exception {
700 
701         writeIterRunner.run(new TransactionWorker() {
702             public void doWork() throws Exception {
703                 Pattern suppressedError = Pattern.compile("BDB1004.*");
704                 Object oldErrHandler = DbCompat.getErrorHandler(env);
705                 ListIterator iter = (ListIterator) iterator(coll);
706                 try {
707                     for (int i = beginKey; i <= endKey; i += 1) {
708                         assertTrue(iter.hasNext());
709                         Object obj = iter.next();
710                         if (map.isOrdered()) {
711                             assertEquals(i, intIter(coll, obj));
712                         }
713                         if (index != null) {
714                             try {
715                                 setValuePlusOne(iter, obj);
716                                 fail();
717                             } catch (UnsupportedOperationException e) {}
718                         } else if
719                            (((StoredCollection) coll).areDuplicatesOrdered()) {
720                             DbCompat.suppressError(env, suppressedError);
721                             try {
722                                 setValuePlusOne(iter, obj);
723                                 fail();
724                             } catch (RuntimeException e) {
725                                 Exception e2 = ExceptionUnwrapper.unwrap(e);
726                                 assertTrue(e2.getClass().getName(),
727                                       e2 instanceof IllegalArgumentException ||
728                                       e2 instanceof DatabaseException);
729                             }
730                             DbCompat.setErrorHandler(env, oldErrHandler);
731                         } else {
732                             setValuePlusOne(iter, obj);
733                             /* Ensure iterator position is correct. */
734                             if (map.isOrdered()) {
735                                 assertTrue(iter.hasPrevious());
736                                 obj = iter.previous();
737                                 assertEquals(i, intIter(coll, obj));
738                                 assertTrue(iter.hasNext());
739                                 obj = iter.next();
740                                 assertEquals(i, intIter(coll, obj));
741                             }
742                         }
743                     }
744                     assertTrue(!iter.hasNext());
745                 } finally {
746                     StoredIterator.close(iter);
747                 }
748             }
749         });
750     }
751 
setValuePlusOne(ListIterator iter, Object obj)752     void setValuePlusOne(ListIterator iter, Object obj) {
753 
754         if (obj instanceof Map.Entry) {
755             Map.Entry entry = (Map.Entry) obj;
756             Long key = (Long) entry.getKey();
757             Object oldVal = entry.getValue();
758             Object val = makeVal(key.intValue() + 1);
759             if (isEntityBinding) {
760                 try {
761                     // must fail on attempt to change the key via an entity
762                     entry.setValue(val);
763                     fail();
764                 } catch (IllegalArgumentException e) {}
765                 val = makeEntity(key.intValue(), key.intValue() + 1);
766             }
767             entry.setValue(val);
768             assertEquals(val, entry.getValue());
769             assertEquals(val, map.get(key));
770             assertTrue(map.duplicates(key).contains(val));
771             checkDupsSize(1, map.duplicates(key));
772             entry.setValue(oldVal);
773             assertEquals(oldVal, entry.getValue());
774             assertEquals(oldVal, map.get(key));
775             assertTrue(map.duplicates(key).contains(oldVal));
776             checkDupsSize(1, map.duplicates(key));
777         } else {
778             Object oldVal = obj;
779             Long key = makeKey(intVal(obj));
780             Object val = makeVal(key.intValue() + 1);
781             if (isEntityBinding) {
782                 try {
783                     // must fail on attempt to change the key via an entity
784                     iter.set(val);
785                     fail();
786                 } catch (IllegalArgumentException e) {}
787                 val = makeEntity(key.intValue(), key.intValue() + 1);
788             }
789             iter.set(val);
790             assertEquals(val, map.get(key));
791             assertTrue(map.duplicates(key).contains(val));
792             checkDupsSize(1, map.duplicates(key));
793             iter.set(oldVal);
794             assertEquals(oldVal, map.get(key));
795             assertTrue(map.duplicates(key).contains(oldVal));
796             checkDupsSize(1, map.duplicates(key));
797         }
798     }
799 
removeAll()800     void removeAll()
801         throws Exception {
802 
803         writeIterRunner.run(new TransactionWorker() {
804             public void doWork() {
805                 assertTrue(!map.isEmpty());
806                 ListIterator iter = null;
807                 try {
808                     if (list != null) {
809                         iter = (ListIterator) iterator(list);
810                     } else {
811                         iter = (ListIterator) iterator(map.values());
812                     }
813                     iteratorSetAndRemoveNotAllowed(iter);
814 
815                     Object val = iter.next();
816                     assertNotNull(val);
817                     iter.remove();
818                     iteratorSetAndRemoveNotAllowed(iter);
819 
820                     if (index == null) {
821                         val = iter.next();
822                         assertNotNull(val);
823                         iter.set(val);
824 
825                         if (map.areDuplicatesAllowed()) {
826                             iter.add(makeVal(intVal(val), intVal(val) + 1));
827                             iteratorSetAndRemoveNotAllowed(iter);
828                         }
829                     }
830                 } finally {
831                     StoredIterator.close(iter);
832                 }
833                 map.clear();
834                 assertTrue(map.isEmpty());
835                 assertTrue(map.entrySet().isEmpty());
836                 assertTrue(map.keySet().isEmpty());
837                 assertTrue(map.values().isEmpty());
838                 for (int i = beginKey; i <= endKey; i += 1) {
839                     Long key = makeKey(i);
840                     Object val = makeVal(i);
841                     assertNull(map.get(key));
842                     assertTrue(!map.duplicates(key).contains(val));
843                     checkDupsSize(0, map.duplicates(key));
844                 }
845             }
846         });
847     }
848 
clearAll()849     void clearAll()
850         throws Exception {
851 
852         writeRunner.run(new TransactionWorker() {
853             public void doWork() {
854                 map.clear();
855                 assertTrue(map.isEmpty());
856             }
857         });
858     }
859 
860     /**
861      * Tests that removing while iterating works properly, especially when
862      * removing everything in the key range or everything from some point to
863      * the end of the range. [#15858]
864      */
removeIter()865     void removeIter()
866         throws Exception {
867 
868         writeIterRunner.run(new TransactionWorker() {
869             public void doWork() {
870                 ListIterator iter;
871 
872                 /* Save contents. */
873                 HashMap<Object, Object> savedMap =
874                     new HashMap<Object, Object>(map);
875                 assertEquals(savedMap, map);
876 
877                 /* Remove all moving forward. */
878                 iter = (ListIterator) iterator(map.keySet());
879                 try {
880                     while (iter.hasNext()) {
881                         assertNotNull(iter.next());
882                         iter.remove();
883                     }
884                     assertTrue(!iter.hasNext());
885                     assertTrue(!iter.hasPrevious());
886                     assertTrue(map.isEmpty());
887                 } finally {
888                     StoredIterator.close(iter);
889                 }
890 
891                 /* Restore contents. */
892                 imap.putAll(savedMap);
893                 assertEquals(savedMap, map);
894 
895                 /* Remove all moving backward. */
896                 iter = (ListIterator) iterator(map.keySet());
897                 try {
898                     while (iter.hasNext()) {
899                         assertNotNull(iter.next());
900                     }
901                     while (iter.hasPrevious()) {
902                         assertNotNull(iter.previous());
903                         iter.remove();
904                     }
905                     assertTrue(map.toString(), !iter.hasNext());
906                     assertTrue(!iter.hasPrevious());
907                     assertTrue(map.isEmpty());
908                 } finally {
909                     StoredIterator.close(iter);
910                 }
911 
912                 /* Restore contents. */
913                 imap.putAll(savedMap);
914                 assertEquals(savedMap, map);
915 
916                 int first = Math.max(1, beginKey);
917                 int last = Math.min(maxKey, endKey);
918 
919                 /* Skip N forward, remove all from that point forward. */
920                 for (int readTo = first + 1; readTo <= last; readTo += 1) {
921                     iter = (ListIterator) iterator(map.keySet());
922                     try {
923                         for (int i = first; i < readTo; i += 1) {
924                             assertTrue(iter.hasNext());
925                             assertNotNull(iter.next());
926                         }
927                         for (int i = readTo; i <= last; i += 1) {
928                             assertTrue(iter.hasNext());
929                             assertNotNull(iter.next());
930                             iter.remove();
931                         }
932                         assertTrue(!iter.hasNext());
933                         assertTrue(iter.hasPrevious());
934                         assertEquals(readTo - first, map.size());
935                     } finally {
936                         StoredIterator.close(iter);
937                     }
938 
939                     /* Restore contents. */
940                     for (Map.Entry entry : savedMap.entrySet()) {
941                         if (!imap.entrySet().contains(entry)) {
942                             imap.put(entry.getKey(), entry.getValue());
943                         }
944                     }
945                     assertEquals(savedMap, map);
946                 }
947 
948                 /* Skip N backward, remove all from that point backward. */
949                 for (int readTo = last - 1; readTo >= first; readTo -= 1) {
950                     iter = (ListIterator) iterator(map.keySet());
951                     try {
952                         while (iter.hasNext()) {
953                             assertNotNull(iter.next());
954                         }
955                         for (int i = last; i > readTo; i -= 1) {
956                             assertTrue(iter.hasPrevious());
957                             assertNotNull(iter.previous());
958                         }
959                         for (int i = readTo; i >= first; i -= 1) {
960                             assertTrue(iter.hasPrevious());
961                             assertNotNull(iter.previous());
962                             iter.remove();
963                         }
964                         assertTrue(!iter.hasPrevious());
965                         assertTrue(iter.hasNext());
966                         assertEquals(last - readTo, map.size());
967                     } finally {
968                         StoredIterator.close(iter);
969                     }
970 
971                     /* Restore contents. */
972                     for (Map.Entry entry : savedMap.entrySet()) {
973                         if (!imap.entrySet().contains(entry)) {
974                             imap.put(entry.getKey(), entry.getValue());
975                         }
976                     }
977                     assertEquals(savedMap, map);
978                 }
979             }
980         });
981     }
982 
iteratorSetAndRemoveNotAllowed(ListIterator i)983     void iteratorSetAndRemoveNotAllowed(ListIterator i) {
984 
985         try {
986             i.remove();
987             fail();
988         } catch (IllegalStateException e) {}
989 
990         if (index == null) {
991             try {
992                 Object val = makeVal(1);
993                 i.set(val);
994                 fail();
995             } catch (IllegalStateException e) {}
996         }
997     }
998 
removeOdd()999     void removeOdd()
1000         throws Exception {
1001 
1002         writeRunner.run(new TransactionWorker() {
1003             public void doWork() {
1004                 boolean toggle = false;
1005                 for (int i = beginKey; i <= endKey; i += 2) {
1006                     toggle = !toggle;
1007                     Long key = makeKey(i);
1008                     Object val = makeVal(i);
1009                     if (toggle) {
1010                         assertTrue(map.keySet().contains(key));
1011                         assertTrue(map.keySet().remove(key));
1012                         assertTrue(!map.keySet().contains(key));
1013                     } else {
1014                         assertTrue(map.containsValue(val));
1015                         Object oldVal = map.remove(key);
1016                         assertEquals(oldVal, val);
1017                         assertTrue(!map.containsKey(key));
1018                         assertTrue(!map.containsValue(val));
1019                     }
1020                     assertNull(map.get(key));
1021                     assertTrue(!map.duplicates(key).contains(val));
1022                     checkDupsSize(0, map.duplicates(key));
1023                 }
1024             }
1025         });
1026     }
1027 
removeOddEntity()1028     void removeOddEntity()
1029         throws Exception {
1030 
1031         writeRunner.run(new TransactionWorker() {
1032             public void doWork() {
1033                 for (int i = beginKey; i <= endKey; i += 2) {
1034                     Long key = makeKey(i);
1035                     Object val = makeVal(i);
1036                     assertTrue(map.values().contains(val));
1037                     assertTrue(map.values().remove(val));
1038                     assertTrue(!map.values().contains(val));
1039                     assertNull(map.get(key));
1040                     assertTrue(!map.duplicates(key).contains(val));
1041                     checkDupsSize(0, map.duplicates(key));
1042                 }
1043             }
1044         });
1045     }
1046 
removeOddEntry()1047     void removeOddEntry()
1048         throws Exception {
1049 
1050         writeRunner.run(new TransactionWorker() {
1051             public void doWork() {
1052                 for (int i = beginKey; i <= endKey; i += 2) {
1053                     Long key = makeKey(i);
1054                     Object val = mapEntry(i);
1055                     assertTrue(map.entrySet().contains(val));
1056                     assertTrue(map.entrySet().remove(val));
1057                     assertTrue(!map.entrySet().contains(val));
1058                     assertNull(map.get(key));
1059                 }
1060             }
1061         });
1062     }
1063 
removeOddIter()1064     void removeOddIter()
1065         throws Exception {
1066 
1067         writeIterRunner.run(new TransactionWorker() {
1068             public void doWork() {
1069                 Iterator iter = iterator(map.keySet());
1070                 try {
1071                     for (int i = beginKey; i <= endKey; i += 1) {
1072                         assertTrue(iter.hasNext());
1073                         Long key = (Long) iter.next();
1074                         assertNotNull(key);
1075                         if (map instanceof SortedMap) {
1076                             assertEquals(makeKey(i), key);
1077                         }
1078                         if ((key.intValue() & 1) != 0) {
1079                             iter.remove();
1080                         }
1081                     }
1082                 } finally {
1083                     StoredIterator.close(iter);
1084                 }
1085             }
1086         });
1087     }
1088 
removeOddList()1089     void removeOddList()
1090         throws Exception {
1091 
1092         writeRunner.run(new TransactionWorker() {
1093             public void doWork() {
1094                 for (int i = beginKey; i <= endKey; i += 2) {
1095                     // remove by index
1096                     // (with entity binding, embbeded keys in values are
1097                     // being changed so we can't use values for comparison)
1098                     int idx = (i - beginKey) / 2;
1099                     Object val = makeVal(i);
1100                     if (!isEntityBinding) {
1101                         assertTrue(list.contains(val));
1102                         assertEquals(val, list.get(idx));
1103                         assertEquals(idx, list.indexOf(val));
1104                     }
1105                     assertNotNull(list.get(idx));
1106                     if (isEntityBinding) {
1107                         assertNotNull(list.remove(idx));
1108                     } else {
1109                         assertTrue(list.contains(val));
1110                         assertEquals(val, list.remove(idx));
1111                     }
1112                     assertTrue(!list.remove(val));
1113                     assertTrue(!list.contains(val));
1114                     assertTrue(!val.equals(list.get(idx)));
1115                 }
1116             }
1117         });
1118     }
1119 
removeOddListValue()1120     void removeOddListValue()
1121         throws Exception {
1122 
1123         writeRunner.run(new TransactionWorker() {
1124             public void doWork() {
1125                 for (int i = beginKey; i <= endKey; i += 2) {
1126                     // for non-entity case remove by value
1127                     // (with entity binding, embbeded keys in values are
1128                     // being changed so we can't use values for comparison)
1129                     int idx = (i - beginKey) / 2;
1130                     Object val = makeVal(i);
1131                     assertTrue(list.contains(val));
1132                     assertEquals(val, list.get(idx));
1133                     assertEquals(idx, list.indexOf(val));
1134                     assertTrue(list.remove(val));
1135                     assertTrue(!list.remove(val));
1136                     assertTrue(!list.contains(val));
1137                     assertTrue(!val.equals(list.get(idx)));
1138                 }
1139             }
1140         });
1141     }
1142 
addOdd()1143     void addOdd()
1144         throws Exception {
1145 
1146         writeRunner.run(new TransactionWorker() {
1147             public void doWork() {
1148                 // add using Map.put()
1149                 for (int i = beginKey; i <= endKey; i += 2) {
1150                     Long key = makeKey(i);
1151                     Object val = makeVal(i);
1152                     assertNull(imap.get(key));
1153                     assertNull(imap.put(key, val));
1154                     assertEquals(val, imap.get(key));
1155                     assertTrue(imap.duplicates(key).contains(val));
1156                     checkDupsSize(1, imap.duplicates(key));
1157                     if (isEntityBinding) {
1158                         assertTrue(!imap.values().add(val));
1159                     }
1160                     if (!imap.areDuplicatesAllowed()) {
1161                         assertEquals(val, imap.put(key, val));
1162                     }
1163                 }
1164             }
1165         });
1166     }
1167 
addOddEntity()1168     void addOddEntity()
1169         throws Exception {
1170 
1171         writeRunner.run(new TransactionWorker() {
1172             public void doWork() {
1173                 // add using Map.values().add()
1174                 for (int i = beginKey; i <= endKey; i += 2) {
1175                     Long key = makeKey(i);
1176                     Object val = makeVal(i);
1177                     assertNull(imap.get(key));
1178                     assertTrue(!imap.values().contains(val));
1179                     assertTrue(imap.values().add(val));
1180                     assertEquals(val, imap.get(key));
1181                     assertTrue(imap.values().contains(val));
1182                     assertTrue(imap.duplicates(key).contains(val));
1183                     checkDupsSize(1, imap.duplicates(key));
1184                     if (isEntityBinding) {
1185                         assertTrue(!imap.values().add(val));
1186                     }
1187                 }
1188             }
1189         });
1190     }
1191 
addOddDup()1192     void addOddDup()
1193         throws Exception {
1194 
1195         writeRunner.run(new TransactionWorker() {
1196             public void doWork() {
1197                 // add using Map.duplicates().add()
1198                 for (int i = beginKey; i <= endKey; i += 2) {
1199                     Long key = makeKey(i);
1200                     Object val = makeVal(i);
1201                     assertNull(imap.get(key));
1202                     assertTrue(!imap.values().contains(val));
1203                     assertTrue(imap.duplicates(key).add(val));
1204                     assertEquals(val, imap.get(key));
1205                     assertTrue(imap.values().contains(val));
1206                     assertTrue(imap.duplicates(key).contains(val));
1207                     checkDupsSize(1, imap.duplicates(key));
1208                     assertTrue(!imap.duplicates(key).add(val));
1209                     if (isEntityBinding) {
1210                         assertTrue(!imap.values().add(val));
1211                     }
1212                 }
1213             }
1214         });
1215     }
1216 
addOddList()1217     void addOddList()
1218         throws Exception {
1219 
1220         writeRunner.run(new TransactionWorker() {
1221             public void doWork() {
1222                 for (int i = beginKey; i <= endKey; i += 2) {
1223                     int idx = i - beginKey;
1224                     Object val = makeVal(i);
1225                     assertTrue(!list.contains(val));
1226                     assertTrue(!val.equals(list.get(idx)));
1227                     list.add(idx, val);
1228                     assertTrue(list.contains(val));
1229                     assertEquals(val, list.get(idx));
1230                 }
1231             }
1232         });
1233     }
1234 
addAllList()1235     void addAllList()
1236         throws Exception {
1237 
1238         writeRunner.run(new TransactionWorker() {
1239             public void doWork() {
1240                 for (int i = beginKey; i <= endKey; i += 1) {
1241                     int idx = i - beginKey;
1242                     Object val = makeVal(i);
1243                     assertTrue(!list.contains(val));
1244                     assertTrue(list.add(val));
1245                     assertTrue(list.contains(val));
1246                     assertEquals(val, list.get(idx));
1247                 }
1248             }
1249         });
1250     }
1251 
removeAllList()1252     void removeAllList()
1253         throws Exception {
1254 
1255         writeRunner.run(new TransactionWorker() {
1256             public void doWork() {
1257                 assertTrue(!list.isEmpty());
1258                 list.clear();
1259                 assertTrue(list.isEmpty());
1260                 for (int i = beginKey; i <= endKey; i += 1) {
1261                     int idx = i - beginKey;
1262                     assertNull(list.get(idx));
1263                 }
1264             }
1265         });
1266     }
1267 
1268     /**
1269      * Tests ConcurentMap methods implemented by StordMap.  Starts with an
1270      * empty DB and ends with an empty DB.  [#16218]
1271      */
testConcurrentMap()1272     void testConcurrentMap()
1273         throws Exception {
1274 
1275         writeRunner.run(new TransactionWorker() {
1276             public void doWork() {
1277                 for (int i = beginKey; i <= endKey; i += 1) {
1278                     Long key = makeKey(i);
1279                     Object val = makeVal(i);
1280                     Object valPlusOne = makeVal(i, i + 1);
1281                     assertFalse(imap.containsKey(key));
1282 
1283                     assertNull(imap.putIfAbsent(key, val));
1284                     assertEquals(val, imap.get(key));
1285 
1286                     assertEquals(val, imap.putIfAbsent(key, val));
1287                     assertEquals(val, imap.get(key));
1288 
1289                     if (!imap.areDuplicatesAllowed()) {
1290                         assertEquals(val, imap.replace(key, valPlusOne));
1291                         assertEquals(valPlusOne, imap.get(key));
1292 
1293                         assertEquals(valPlusOne, imap.replace(key, val));
1294                         assertEquals(val, imap.get(key));
1295 
1296                         assertFalse(imap.replace(key, valPlusOne, val));
1297                         assertEquals(val, imap.get(key));
1298 
1299                         assertTrue(imap.replace(key, val, valPlusOne));
1300                         assertEquals(valPlusOne, imap.get(key));
1301 
1302                         assertTrue(imap.replace(key, valPlusOne, val));
1303                         assertEquals(val, imap.get(key));
1304                     }
1305 
1306                     assertFalse(imap.remove(key, valPlusOne));
1307                     assertTrue(imap.containsKey(key));
1308 
1309                     assertTrue(imap.remove(key, val));
1310                     assertFalse(imap.containsKey(key));
1311 
1312                     assertNull(imap.replace(key, val));
1313                     assertFalse(imap.containsKey(key));
1314                 }
1315             }
1316         });
1317     }
1318 
testIterAddList()1319     void testIterAddList()
1320         throws Exception {
1321 
1322         writeIterRunner.run(new TransactionWorker() {
1323             public void doWork() {
1324                 ListIterator i = (ListIterator) iterator(list);
1325                 try {
1326                     assertTrue(!i.hasNext());
1327                     i.add(makeVal(3));
1328                     assertTrue(!i.hasNext());
1329                     assertTrue(i.hasPrevious());
1330                     assertEquals(3, intVal(i.previous()));
1331 
1332                     i.add(makeVal(1));
1333                     assertTrue(i.hasPrevious());
1334                     assertTrue(i.hasNext());
1335                     assertEquals(1, intVal(i.previous()));
1336                     assertTrue(i.hasNext());
1337                     assertEquals(1, intVal(i.next()));
1338                     assertTrue(i.hasNext());
1339                     assertEquals(3, intVal(i.next()));
1340                     assertEquals(3, intVal(i.previous()));
1341 
1342                     assertTrue(i.hasNext());
1343                     i.add(makeVal(2));
1344                     assertTrue(i.hasNext());
1345                     assertTrue(i.hasPrevious());
1346                     assertEquals(2, intVal(i.previous()));
1347                     assertTrue(i.hasNext());
1348                     assertEquals(2, intVal(i.next()));
1349                     assertTrue(i.hasNext());
1350                     assertEquals(3, intVal(i.next()));
1351 
1352                     assertTrue(!i.hasNext());
1353                     i.add(makeVal(4));
1354                     i.add(makeVal(5));
1355                     assertTrue(!i.hasNext());
1356                     assertEquals(5, intVal(i.previous()));
1357                     assertEquals(4, intVal(i.previous()));
1358                     assertEquals(3, intVal(i.previous()));
1359                     assertEquals(2, intVal(i.previous()));
1360                     assertEquals(1, intVal(i.previous()));
1361                     assertTrue(!i.hasPrevious());
1362                 } finally {
1363                     StoredIterator.close(i);
1364                 }
1365             }
1366         });
1367     }
1368 
testIterAddDuplicates()1369     void testIterAddDuplicates()
1370         throws Exception {
1371 
1372         writeIterRunner.run(new TransactionWorker() {
1373             public void doWork() {
1374                 assertNull(imap.put(makeKey(1), makeVal(1)));
1375                 ListIterator i =
1376                     (ListIterator) iterator(imap.duplicates(makeKey(1)));
1377                 try {
1378                     if (imap.areDuplicatesOrdered()) {
1379                         i.add(makeVal(1, 4));
1380                         i.add(makeVal(1, 2));
1381                         i.add(makeVal(1, 3));
1382                         while (i.hasPrevious()) i.previous();
1383                         assertEquals(1, intVal(i.next()));
1384                         assertEquals(2, intVal(i.next()));
1385                         assertEquals(3, intVal(i.next()));
1386                         assertEquals(4, intVal(i.next()));
1387                         assertTrue(!i.hasNext());
1388                     } else {
1389                         assertEquals(1, intVal(i.next()));
1390                         i.add(makeVal(1, 2));
1391                         i.add(makeVal(1, 3));
1392                         assertTrue(!i.hasNext());
1393                         assertTrue(i.hasPrevious());
1394                         assertEquals(3, intVal(i.previous()));
1395                         assertEquals(2, intVal(i.previous()));
1396                         assertEquals(1, intVal(i.previous()));
1397                         assertTrue(!i.hasPrevious());
1398                         i.add(makeVal(1, 4));
1399                         i.add(makeVal(1, 5));
1400                         assertTrue(i.hasNext());
1401                         assertEquals(5, intVal(i.previous()));
1402                         assertEquals(4, intVal(i.previous()));
1403                         assertTrue(!i.hasPrevious());
1404                         assertEquals(4, intVal(i.next()));
1405                         assertEquals(5, intVal(i.next()));
1406                         assertEquals(1, intVal(i.next()));
1407                         assertEquals(2, intVal(i.next()));
1408                         assertEquals(3, intVal(i.next()));
1409                         assertTrue(!i.hasNext());
1410                     }
1411                 } finally {
1412                     StoredIterator.close(i);
1413                 }
1414             }
1415         });
1416     }
1417 
readAll()1418     void readAll()
1419         throws Exception {
1420 
1421         readRunner.run(new TransactionWorker() {
1422             public void doWork() {
1423                 // map
1424 
1425                 assertNotNull(map.toString());
1426                 for (int i = beginKey; i <= endKey; i += 1) {
1427                     Long key = makeKey(i);
1428                     Object val = map.get(key);
1429                     assertEquals(makeVal(i), val);
1430                     assertTrue(map.containsKey(key));
1431                     assertTrue(map.containsValue(val));
1432                     assertTrue(map.keySet().contains(key));
1433                     assertTrue(map.values().contains(val));
1434                     assertTrue(map.duplicates(key).contains(val));
1435                     checkDupsSize(1, map.duplicates(key));
1436                 }
1437                 assertNull(map.get(makeKey(-1)));
1438                 assertNull(map.get(makeKey(0)));
1439                 assertNull(map.get(makeKey(beginKey - 1)));
1440                 assertNull(map.get(makeKey(endKey + 1)));
1441                 checkDupsSize(0, map.duplicates(makeKey(-1)));
1442                 checkDupsSize(0, map.duplicates(makeKey(0)));
1443                 checkDupsSize(0, map.duplicates(makeKey(beginKey - 1)));
1444                 checkDupsSize(0, map.duplicates(makeKey(endKey + 1)));
1445 
1446                 // entrySet
1447 
1448                 Set set = map.entrySet();
1449                 assertNotNull(set.toString());
1450                 assertEquals(beginKey > endKey, set.isEmpty());
1451                 Iterator iter = iterator(set);
1452                 try {
1453                     for (int i = beginKey; i <= endKey; i += 1) {
1454                         assertTrue(iter.hasNext());
1455                         Map.Entry entry = (Map.Entry) iter.next();
1456                         Long key = (Long) entry.getKey();
1457                         Object val = entry.getValue();
1458                         if (map instanceof SortedMap) {
1459                             assertEquals(intKey(key), i);
1460                         }
1461                         assertEquals(intKey(key), intVal(val));
1462                         assertTrue(set.contains(entry));
1463                     }
1464                     assertTrue(!iter.hasNext());
1465                 } finally {
1466                     StoredIterator.close(iter);
1467                 }
1468                 Map.Entry[] entries =
1469                     (Map.Entry[]) set.toArray(new Map.Entry[0]);
1470                 assertNotNull(entries);
1471                 assertEquals(endKey - beginKey + 1, entries.length);
1472                 for (int i = beginKey; i <= endKey; i += 1) {
1473                     Map.Entry entry = entries[i - beginKey];
1474                     assertNotNull(entry);
1475                     if (map instanceof SortedMap) {
1476                         assertEquals(makeKey(i), entry.getKey());
1477                         assertEquals(makeVal(i), entry.getValue());
1478                     }
1479                 }
1480                 readIterator(set, iterator(set), beginKey, endKey);
1481                 if (smap != null) {
1482                     SortedSet sset = (SortedSet) set;
1483                     if (beginKey == 1 && endKey >= 1) {
1484                         readIterator(sset,
1485                                      iterator(sset.subSet(mapEntry(1),
1486                                                           mapEntry(2))),
1487                                      1, 1);
1488                     }
1489                     if (beginKey <= 2 && endKey >= 2) {
1490                         readIterator(sset,
1491                                      iterator(sset.subSet(mapEntry(2),
1492                                                           mapEntry(3))),
1493                                      2, 2);
1494                     }
1495                     if (beginKey <= endKey) {
1496                         readIterator(sset,
1497                                      iterator(sset.subSet
1498                                                 (mapEntry(endKey),
1499                                                  mapEntry(endKey + 1))),
1500                                      endKey, endKey);
1501                     }
1502                     if (isSubMap()) {
1503                         if (beginKey <= endKey) {
1504                             if (rangeType != TAIL) {
1505                                 try {
1506                                     sset.subSet(mapEntry(endKey + 1),
1507                                                 mapEntry(endKey + 2));
1508                                     fail();
1509                                 } catch (IllegalArgumentException e) {}
1510                             }
1511                             if (rangeType != HEAD) {
1512                                 try {
1513                                     sset.subSet(mapEntry(0),
1514                                                 mapEntry(1));
1515                                     fail();
1516                                 } catch (IllegalArgumentException e) {}
1517                             }
1518                         }
1519                     } else {
1520                         readIterator(sset,
1521                                      iterator(sset.subSet
1522                                                 (mapEntry(endKey + 1),
1523                                                  mapEntry(endKey + 2))),
1524                                      endKey, endKey - 1);
1525                         readIterator(sset,
1526                                      iterator(sset.subSet(mapEntry(0),
1527                                                           mapEntry(1))),
1528                                      0, -1);
1529                     }
1530                 }
1531 
1532                 // keySet
1533 
1534                 set = map.keySet();
1535                 assertNotNull(set.toString());
1536                 assertEquals(beginKey > endKey, set.isEmpty());
1537                 iter = iterator(set);
1538                 try {
1539                     for (int i = beginKey; i <= endKey; i += 1) {
1540                         assertTrue(iter.hasNext());
1541                         Long key = (Long) iter.next();
1542                         assertTrue(set.contains(key));
1543                         Object val = map.get(key);
1544                         if (map instanceof SortedMap) {
1545                             assertEquals(key, makeKey(i));
1546                         }
1547                         assertEquals(intKey(key), intVal(val));
1548                     }
1549                     assertTrue("" + beginKey + ' ' + endKey, !iter.hasNext());
1550                 } finally {
1551                     StoredIterator.close(iter);
1552                 }
1553                 Long[] keys = (Long[]) set.toArray(new Long[0]);
1554                 assertNotNull(keys);
1555                 assertEquals(endKey - beginKey + 1, keys.length);
1556                 for (int i = beginKey; i <= endKey; i += 1) {
1557                     Long key = keys[i - beginKey];
1558                     assertNotNull(key);
1559                     if (map instanceof SortedMap) {
1560                         assertEquals(makeKey(i), key);
1561                     }
1562                 }
1563                 readIterator(set, iterator(set), beginKey, endKey);
1564 
1565                 // values
1566 
1567                 Collection coll = map.values();
1568                 assertNotNull(coll.toString());
1569                 assertEquals(beginKey > endKey, coll.isEmpty());
1570                 iter = iterator(coll);
1571                 try {
1572                     for (int i = beginKey; i <= endKey; i += 1) {
1573                         assertTrue(iter.hasNext());
1574                         Object val = iter.next();
1575                         if (map instanceof SortedMap) {
1576                             assertEquals(makeVal(i), val);
1577                         }
1578                     }
1579                     assertTrue(!iter.hasNext());
1580                 } finally {
1581                     StoredIterator.close(iter);
1582                 }
1583                 Object[] values = coll.toArray();
1584                 assertNotNull(values);
1585                 assertEquals(endKey - beginKey + 1, values.length);
1586                 for (int i = beginKey; i <= endKey; i += 1) {
1587                     Object val = values[i - beginKey];
1588                     assertNotNull(val);
1589                     if (map instanceof SortedMap) {
1590                         assertEquals(makeVal(i), val);
1591                     }
1592                 }
1593                 readIterator(coll, iterator(coll), beginKey, endKey);
1594 
1595                 // list
1596 
1597                 if (list != null) {
1598                     assertNotNull(list.toString());
1599                     assertEquals(beginKey > endKey, list.isEmpty());
1600                     for (int i = beginKey; i <= endKey; i += 1) {
1601                         int idx = i - beginKey;
1602                         Object val = list.get(idx);
1603                         assertEquals(makeVal(i), val);
1604                         assertTrue(list.contains(val));
1605                         assertEquals(idx, list.indexOf(val));
1606                         assertEquals(idx, list.lastIndexOf(val));
1607                     }
1608                     ListIterator li = (ListIterator) iterator(list);
1609                     try {
1610                         for (int i = beginKey; i <= endKey; i += 1) {
1611                             int idx = i - beginKey;
1612                             assertTrue(li.hasNext());
1613                             assertEquals(idx, li.nextIndex());
1614                             Object val = li.next();
1615                             assertEquals(makeVal(i), val);
1616                             assertEquals(idx, li.previousIndex());
1617                         }
1618                         assertTrue(!li.hasNext());
1619                     } finally {
1620                         StoredIterator.close(li);
1621                     }
1622                     if (beginKey < endKey) {
1623                         li = list.listIterator(1);
1624                         try {
1625                             for (int i = beginKey + 1; i <= endKey; i += 1) {
1626                                 int idx = i - beginKey;
1627                                 assertTrue(li.hasNext());
1628                                 assertEquals(idx, li.nextIndex());
1629                                 Object val = li.next();
1630                                 assertEquals(makeVal(i), val);
1631                                 assertEquals(idx, li.previousIndex());
1632                             }
1633                             assertTrue(!li.hasNext());
1634                         } finally {
1635                             StoredIterator.close(li);
1636                         }
1637                     }
1638                     values = list.toArray();
1639                     assertNotNull(values);
1640                     assertEquals(endKey - beginKey + 1, values.length);
1641                     for (int i = beginKey; i <= endKey; i += 1) {
1642                         Object val = values[i - beginKey];
1643                         assertNotNull(val);
1644                         assertEquals(makeVal(i), val);
1645                     }
1646                     readIterator(list, iterator(list), beginKey, endKey);
1647                 }
1648 
1649                 // first/last
1650 
1651                 if (smap != null) {
1652                     if (beginKey <= endKey &&
1653                         beginKey >= 1 && beginKey <= maxKey) {
1654                         assertEquals(makeKey(beginKey),
1655                                      smap.firstKey());
1656                         assertEquals(makeKey(beginKey),
1657                                      ((SortedSet) smap.keySet()).first());
1658                         Object entry = ((SortedSet) smap.entrySet()).first();
1659                         assertEquals(makeKey(beginKey),
1660                                      ((Map.Entry) entry).getKey());
1661                         if (smap.values() instanceof SortedSet) {
1662                             assertEquals(makeVal(beginKey),
1663                                          ((SortedSet) smap.values()).first());
1664                         }
1665                     } else {
1666                         assertNull(smap.firstKey());
1667                         assertNull(((SortedSet) smap.keySet()).first());
1668                         assertNull(((SortedSet) smap.entrySet()).first());
1669                         if (smap.values() instanceof SortedSet) {
1670                             assertNull(((SortedSet) smap.values()).first());
1671                         }
1672                     }
1673                     if (beginKey <= endKey &&
1674                         endKey >= 1 && endKey <= maxKey) {
1675                         assertEquals(makeKey(endKey),
1676                                      smap.lastKey());
1677                         assertEquals(makeKey(endKey),
1678                                      ((SortedSet) smap.keySet()).last());
1679                         Object entry = ((SortedSet) smap.entrySet()).last();
1680                         assertEquals(makeKey(endKey),
1681                                      ((Map.Entry) entry).getKey());
1682                         if (smap.values() instanceof SortedSet) {
1683                             assertEquals(makeVal(endKey),
1684                                          ((SortedSet) smap.values()).last());
1685                         }
1686                     } else {
1687                         assertNull(smap.lastKey());
1688                         assertNull(((SortedSet) smap.keySet()).last());
1689                         assertNull(((SortedSet) smap.entrySet()).last());
1690                         if (smap.values() instanceof SortedSet) {
1691                             assertNull(((SortedSet) smap.values()).last());
1692                         }
1693                     }
1694                 }
1695             }
1696         });
1697     }
1698 
readEven()1699     void readEven()
1700         throws Exception {
1701 
1702         readRunner.run(new TransactionWorker() {
1703             public void doWork() {
1704                 int readBegin = ((beginKey & 1) != 0) ?
1705                                     (beginKey + 1) : beginKey;
1706                 int readEnd = ((endKey & 1) != 0) ?  (endKey - 1) : endKey;
1707                 int readIncr = 2;
1708 
1709                 // map
1710 
1711                 for (int i = beginKey; i <= endKey; i += 1) {
1712                     Long key = makeKey(i);
1713                     if ((i & 1) == 0) {
1714                         Object val = map.get(key);
1715                         assertEquals(makeVal(i), val);
1716                         assertTrue(map.containsKey(key));
1717                         assertTrue(map.containsValue(val));
1718                         assertTrue(map.keySet().contains(key));
1719                         assertTrue(map.values().contains(val));
1720                         assertTrue(map.duplicates(key).contains(val));
1721                         checkDupsSize(1, map.duplicates(key));
1722                     } else {
1723                         Object val = makeVal(i);
1724                         assertTrue(!map.containsKey(key));
1725                         assertTrue(!map.containsValue(val));
1726                         assertTrue(!map.keySet().contains(key));
1727                         assertTrue(!map.values().contains(val));
1728                         assertTrue(!map.duplicates(key).contains(val));
1729                         checkDupsSize(0, map.duplicates(key));
1730                     }
1731                 }
1732 
1733                 // entrySet
1734 
1735                 Set set = map.entrySet();
1736                 assertEquals(beginKey > endKey, set.isEmpty());
1737                 Iterator iter = iterator(set);
1738                 try {
1739                     for (int i = readBegin; i <= readEnd; i += readIncr) {
1740                         assertTrue(iter.hasNext());
1741                         Map.Entry entry = (Map.Entry) iter.next();
1742                         Long key = (Long) entry.getKey();
1743                         Object val = entry.getValue();
1744                         if (map instanceof SortedMap) {
1745                             assertEquals(intKey(key), i);
1746                         }
1747                         assertEquals(intKey(key), intVal(val));
1748                         assertTrue(set.contains(entry));
1749                     }
1750                     assertTrue(!iter.hasNext());
1751                 } finally {
1752                     StoredIterator.close(iter);
1753                 }
1754 
1755                 // keySet
1756 
1757                 set = map.keySet();
1758                 assertEquals(beginKey > endKey, set.isEmpty());
1759                 iter = iterator(set);
1760                 try {
1761                     for (int i = readBegin; i <= readEnd; i += readIncr) {
1762                         assertTrue(iter.hasNext());
1763                         Long key = (Long) iter.next();
1764                         assertTrue(set.contains(key));
1765                         Object val = map.get(key);
1766                         if (map instanceof SortedMap) {
1767                             assertEquals(key, makeKey(i));
1768                         }
1769                         assertEquals(intKey(key), intVal(val));
1770                     }
1771                     assertTrue(!iter.hasNext());
1772                 } finally {
1773                     StoredIterator.close(iter);
1774                 }
1775 
1776                 // values
1777 
1778                 Collection coll = map.values();
1779                 assertEquals(beginKey > endKey, coll.isEmpty());
1780                 iter = iterator(coll);
1781                 try {
1782                     for (int i = readBegin; i <= readEnd; i += readIncr) {
1783                         assertTrue(iter.hasNext());
1784                         Object val = iter.next();
1785                         if (map instanceof SortedMap) {
1786                             assertEquals(makeVal(i), val);
1787                         }
1788                     }
1789                     assertTrue(!iter.hasNext());
1790                 } finally {
1791                     StoredIterator.close(iter);
1792                 }
1793 
1794                 // list not used since keys may not be renumbered for this
1795                 // method to work in general
1796 
1797                 // first/last
1798 
1799                 if (smap != null) {
1800                     if (readBegin <= readEnd &&
1801                         readBegin >= 1 && readBegin <= maxKey) {
1802                         assertEquals(makeKey(readBegin),
1803                                      smap.firstKey());
1804                         assertEquals(makeKey(readBegin),
1805                                      ((SortedSet) smap.keySet()).first());
1806                         Object entry = ((SortedSet) smap.entrySet()).first();
1807                         assertEquals(makeKey(readBegin),
1808                                      ((Map.Entry) entry).getKey());
1809                         if (smap.values() instanceof SortedSet) {
1810                             assertEquals(makeVal(readBegin),
1811                                          ((SortedSet) smap.values()).first());
1812                         }
1813                     } else {
1814                         assertNull(smap.firstKey());
1815                         assertNull(((SortedSet) smap.keySet()).first());
1816                         assertNull(((SortedSet) smap.entrySet()).first());
1817                         if (smap.values() instanceof SortedSet) {
1818                             assertNull(((SortedSet) smap.values()).first());
1819                         }
1820                     }
1821                     if (readBegin <= readEnd &&
1822                         readEnd >= 1 && readEnd <= maxKey) {
1823                         assertEquals(makeKey(readEnd),
1824                                      smap.lastKey());
1825                         assertEquals(makeKey(readEnd),
1826                                      ((SortedSet) smap.keySet()).last());
1827                         Object entry = ((SortedSet) smap.entrySet()).last();
1828                         assertEquals(makeKey(readEnd),
1829                                      ((Map.Entry) entry).getKey());
1830                         if (smap.values() instanceof SortedSet) {
1831                             assertEquals(makeVal(readEnd),
1832                                          ((SortedSet) smap.values()).last());
1833                         }
1834                     } else {
1835                         assertNull(smap.lastKey());
1836                         assertNull(((SortedSet) smap.keySet()).last());
1837                         assertNull(((SortedSet) smap.entrySet()).last());
1838                         if (smap.values() instanceof SortedSet) {
1839                             assertNull(((SortedSet) smap.values()).last());
1840                         }
1841                     }
1842                 }
1843             }
1844         });
1845     }
1846 
readEvenList()1847     void readEvenList()
1848         throws Exception {
1849 
1850         readRunner.run(new TransactionWorker() {
1851             public void doWork() {
1852                 int readBegin = ((beginKey & 1) != 0) ?
1853                                     (beginKey + 1) : beginKey;
1854                 int readEnd = ((endKey & 1) != 0) ?  (endKey - 1) : endKey;
1855                 int readIncr = 2;
1856 
1857                 assertEquals(beginKey > endKey, list.isEmpty());
1858                 ListIterator iter = (ListIterator) iterator(list);
1859                 try {
1860                     int idx = 0;
1861                     for (int i = readBegin; i <= readEnd; i += readIncr) {
1862                         assertTrue(iter.hasNext());
1863                         assertEquals(idx, iter.nextIndex());
1864                         Object val = iter.next();
1865                         assertEquals(idx, iter.previousIndex());
1866                         if (isEntityBinding) {
1867                             assertEquals(i, intVal(val));
1868                         } else {
1869                             assertEquals(makeVal(i), val);
1870                         }
1871                         idx += 1;
1872                     }
1873                     assertTrue(!iter.hasNext());
1874                 } finally {
1875                     StoredIterator.close(iter);
1876                 }
1877             }
1878         });
1879     }
1880 
readIterator(Collection coll, Iterator iter, int beginValue, int endValue)1881     void readIterator(Collection coll, Iterator iter,
1882                       int beginValue, int endValue) {
1883 
1884         ListIterator li = (ListIterator) iter;
1885         boolean isList = (coll instanceof List);
1886         Iterator clone = null;
1887         try {
1888             // at beginning
1889             assertTrue(!li.hasPrevious());
1890             assertTrue(!li.hasPrevious());
1891             try { li.previous(); } catch (NoSuchElementException e) {}
1892             if (isList) {
1893                 assertEquals(-1, li.previousIndex());
1894             }
1895             if (endValue < beginValue) {
1896                 // is empty
1897                 assertTrue(!iter.hasNext());
1898                 try { iter.next(); } catch (NoSuchElementException e) {}
1899                 if (isList) {
1900                     assertEquals(Integer.MAX_VALUE, li.nextIndex());
1901                 }
1902             }
1903             // loop thru all and collect in array
1904             int[] values = new int[endValue - beginValue + 1];
1905             for (int i = beginValue; i <= endValue; i += 1) {
1906                 assertTrue(iter.hasNext());
1907                 int idx = i - beginKey;
1908                 if (isList) {
1909                     assertEquals(idx, li.nextIndex());
1910                 }
1911                 int value = intIter(coll, iter.next());
1912                 if (isList) {
1913                     assertEquals(idx, li.previousIndex());
1914                 }
1915                 values[i - beginValue] = value;
1916                 if (((StoredCollection) coll).isOrdered()) {
1917                     assertEquals(i, value);
1918                 } else {
1919                     assertTrue(value >= beginValue);
1920                     assertTrue(value <= endValue);
1921                 }
1922             }
1923             // at end
1924             assertTrue(!iter.hasNext());
1925             try { iter.next(); } catch (NoSuchElementException e) {}
1926             if (isList) {
1927                 assertEquals(Integer.MAX_VALUE, li.nextIndex());
1928             }
1929             // clone at same position
1930             clone = StoredCollections.iterator(iter);
1931             assertTrue(!clone.hasNext());
1932             // loop thru in reverse
1933             for (int i = endValue; i >= beginValue; i -= 1) {
1934                 assertTrue(li.hasPrevious());
1935                 int idx = i - beginKey;
1936                 if (isList) {
1937                     assertEquals(idx, li.previousIndex());
1938                 }
1939                 int value = intIter(coll, li.previous());
1940                 if (isList) {
1941                     assertEquals(idx, li.nextIndex());
1942                 }
1943                 assertEquals(values[i - beginValue], value);
1944             }
1945             // clone should not have changed
1946             assertTrue(!clone.hasNext());
1947             // at beginning
1948             assertTrue(!li.hasPrevious());
1949             try { li.previous(); } catch (NoSuchElementException e) {}
1950             if (isList) {
1951                 assertEquals(-1, li.previousIndex());
1952             }
1953             // loop thru with some back-and-forth
1954             for (int i = beginValue; i <= endValue; i += 1) {
1955                 assertTrue(iter.hasNext());
1956                 int idx = i - beginKey;
1957                 if (isList) {
1958                     assertEquals(idx, li.nextIndex());
1959                 }
1960                 Object obj = iter.next();
1961                 if (isList) {
1962                     assertEquals(idx, li.previousIndex());
1963                 }
1964                 assertEquals(obj, li.previous());
1965                 if (isList) {
1966                     assertEquals(idx, li.nextIndex());
1967                 }
1968                 assertEquals(obj, iter.next());
1969                 if (isList) {
1970                     assertEquals(idx, li.previousIndex());
1971                 }
1972                 int value = intIter(coll, obj);
1973                 assertEquals(values[i - beginValue], value);
1974             }
1975             // at end
1976             assertTrue(!iter.hasNext());
1977             try { iter.next(); } catch (NoSuchElementException e) {}
1978             if (isList) {
1979                 assertEquals(Integer.MAX_VALUE, li.nextIndex());
1980             }
1981         } finally {
1982             StoredIterator.close(iter);
1983             StoredIterator.close(clone);
1984         }
1985     }
1986 
bulkOperations()1987     void bulkOperations()
1988         throws Exception {
1989 
1990         writeRunner.run(new TransactionWorker() {
1991             public void doWork() {
1992                 HashMap hmap = new HashMap();
1993                 for (int i = Math.max(1, beginKey);
1994                          i <= Math.min(maxKey, endKey);
1995                          i += 1) {
1996                     hmap.put(makeKey(i), makeVal(i));
1997                 }
1998                 assertEquals(hmap, map);
1999                 assertEquals(hmap.entrySet(), map.entrySet());
2000                 assertEquals(hmap.keySet(), map.keySet());
2001                 assertEquals(map.values(), hmap.values());
2002 
2003                 assertTrue(map.entrySet().containsAll(hmap.entrySet()));
2004                 assertTrue(map.keySet().containsAll(hmap.keySet()));
2005                 assertTrue(map.values().containsAll(hmap.values()));
2006 
2007                 map.clear();
2008                 assertTrue(map.isEmpty());
2009                 imap.putAll(hmap);
2010                 assertEquals(hmap, map);
2011 
2012                 assertTrue(map.entrySet().removeAll(hmap.entrySet()));
2013                 assertTrue(map.entrySet().isEmpty());
2014                 assertTrue(!map.entrySet().removeAll(hmap.entrySet()));
2015                 assertTrue(imap.entrySet().addAll(hmap.entrySet()));
2016                 assertTrue(map.entrySet().containsAll(hmap.entrySet()));
2017                 assertTrue(!imap.entrySet().addAll(hmap.entrySet()));
2018                 assertEquals(hmap, map);
2019 
2020                 assertTrue(!map.entrySet().retainAll(hmap.entrySet()));
2021                 assertEquals(hmap, map);
2022                 assertTrue(map.entrySet().retainAll(Collections.EMPTY_SET));
2023                 assertTrue(map.isEmpty());
2024                 imap.putAll(hmap);
2025                 assertEquals(hmap, map);
2026 
2027                 assertTrue(map.values().removeAll(hmap.values()));
2028                 assertTrue(map.values().isEmpty());
2029                 assertTrue(!map.values().removeAll(hmap.values()));
2030                 if (isEntityBinding) {
2031                     assertTrue(imap.values().addAll(hmap.values()));
2032                     assertTrue(map.values().containsAll(hmap.values()));
2033                     assertTrue(!imap.values().addAll(hmap.values()));
2034                 } else {
2035                     imap.putAll(hmap);
2036                 }
2037                 assertEquals(hmap, map);
2038 
2039                 assertTrue(!map.values().retainAll(hmap.values()));
2040                 assertEquals(hmap, map);
2041                 assertTrue(map.values().retainAll(Collections.EMPTY_SET));
2042                 assertTrue(map.isEmpty());
2043                 imap.putAll(hmap);
2044                 assertEquals(hmap, map);
2045 
2046                 assertTrue(map.keySet().removeAll(hmap.keySet()));
2047                 assertTrue(map.keySet().isEmpty());
2048                 assertTrue(!map.keySet().removeAll(hmap.keySet()));
2049                 assertTrue(imap.keySet().addAll(hmap.keySet()));
2050                 assertTrue(imap.keySet().containsAll(hmap.keySet()));
2051                 if (index != null) {
2052                     assertTrue(map.keySet().isEmpty());
2053                 }
2054                 assertTrue(!imap.keySet().addAll(hmap.keySet()));
2055                 // restore values to non-null
2056                 imap.keySet().removeAll(hmap.keySet());
2057                 imap.putAll(hmap);
2058                 assertEquals(hmap, map);
2059 
2060                 assertTrue(!map.keySet().retainAll(hmap.keySet()));
2061                 assertEquals(hmap, map);
2062                 assertTrue(map.keySet().retainAll(Collections.EMPTY_SET));
2063                 assertTrue(map.isEmpty());
2064                 imap.putAll(hmap);
2065                 assertEquals(hmap, map);
2066             }
2067         });
2068     }
2069 
bulkListOperations()2070     void bulkListOperations()
2071         throws Exception {
2072 
2073         writeRunner.run(new TransactionWorker() {
2074             public void doWork() {
2075                 ArrayList alist = new ArrayList();
2076                 for (int i = beginKey; i <= endKey; i += 1) {
2077                     alist.add(makeVal(i));
2078                 }
2079 
2080                 assertEquals(alist, list);
2081                 assertTrue(list.containsAll(alist));
2082 
2083                 if (isListAddAllowed()) {
2084                     list.clear();
2085                     assertTrue(list.isEmpty());
2086                     assertTrue(ilist.addAll(alist));
2087                     assertEquals(alist, list);
2088                 }
2089 
2090                 assertTrue(!list.retainAll(alist));
2091                 assertEquals(alist, list);
2092 
2093                 if (isListAddAllowed()) {
2094                     assertTrue(list.retainAll(Collections.EMPTY_SET));
2095                     assertTrue(list.isEmpty());
2096                     assertTrue(ilist.addAll(alist));
2097                     assertEquals(alist, list);
2098                 }
2099 
2100                 if (isListAddAllowed() && !isEntityBinding) {
2101                     // deleting in a renumbered list with entity binding will
2102                     // change the values dynamically, making it very difficult
2103                     // to test
2104                     assertTrue(list.removeAll(alist));
2105                     assertTrue(list.isEmpty());
2106                     assertTrue(!list.removeAll(alist));
2107                     assertTrue(ilist.addAll(alist));
2108                     assertTrue(list.containsAll(alist));
2109                     assertEquals(alist, list);
2110                 }
2111 
2112                 if (isListAddAllowed() && !isEntityBinding) {
2113                     // addAll at an index is also very difficult to test with
2114                     // an entity binding
2115 
2116                     // addAll at first index
2117                     ilist.addAll(beginKey, alist);
2118                     assertTrue(list.containsAll(alist));
2119                     assertEquals(2 * alist.size(), countElements(list));
2120                     for (int i = beginKey; i <= endKey; i += 1)
2121                         ilist.remove(beginKey);
2122                     assertEquals(alist, list);
2123 
2124                     // addAll at last index
2125                     ilist.addAll(endKey, alist);
2126                     assertTrue(list.containsAll(alist));
2127                     assertEquals(2 * alist.size(), countElements(list));
2128                     for (int i = beginKey; i <= endKey; i += 1)
2129                         ilist.remove(endKey);
2130                     assertEquals(alist, list);
2131 
2132                     // addAll in the middle
2133                     ilist.addAll(endKey - 1, alist);
2134                     assertTrue(list.containsAll(alist));
2135                     assertEquals(2 * alist.size(), countElements(list));
2136                     for (int i = beginKey; i <= endKey; i += 1)
2137                         ilist.remove(endKey - 1);
2138                     assertEquals(alist, list);
2139                 }
2140             }
2141         });
2142     }
2143 
readWriteRange(final int type, final int rangeBegin, final int rangeEnd)2144     void readWriteRange(final int type, final int rangeBegin,
2145                         final int rangeEnd)
2146         throws Exception {
2147 
2148         writeRunner.run(new TransactionWorker() {
2149             public void doWork() throws Exception {
2150                 setRange(type, rangeBegin, rangeEnd);
2151                 createOutOfRange(rangeBegin, rangeEnd);
2152                 if (rangeType != TAIL) {
2153                     writeOutOfRange(new Long(rangeEnd + 1));
2154                 }
2155                 if (rangeType != HEAD) {
2156                     writeOutOfRange(new Long(rangeBegin - 1));
2157                 }
2158                 if (rangeBegin <= rangeEnd) {
2159                     updateAll();
2160                 }
2161                 if (rangeBegin < rangeEnd && !map.areKeysRenumbered()) {
2162                     bulkOperations();
2163                     removeIter();
2164                 }
2165                 readAll();
2166                 clearRange();
2167             }
2168         });
2169     }
2170 
setRange(int type, int rangeBegin, int rangeEnd)2171     void setRange(int type, int rangeBegin, int rangeEnd) {
2172 
2173         rangeType = type;
2174         saveMap = map;
2175         saveSMap = smap;
2176         saveList = list;
2177         int listBegin = rangeBegin - beginKey;
2178         boolean canMakeSubList = (list != null && listBegin>= 0);
2179         if (!canMakeSubList) {
2180             list = null;
2181         }
2182         if (list != null) {
2183             try {
2184                 list.subList(-1, 0);
2185                 fail();
2186             } catch (IndexOutOfBoundsException e) { }
2187         }
2188         switch (type) {
2189 
2190         case SUB:
2191             smap = (StoredSortedMap) smap.subMap(makeKey(rangeBegin),
2192                                                  makeKey(rangeEnd + 1));
2193             if (canMakeSubList) {
2194                 list = (StoredList) list.subList(listBegin,
2195                                                  rangeEnd + 1 - beginKey);
2196             }
2197             // check for equivalent ranges
2198             assertEquals(smap,
2199                         (saveSMap).subMap(
2200                             makeKey(rangeBegin), true,
2201                             makeKey(rangeEnd + 1), false));
2202             assertEquals(smap.entrySet(),
2203                         ((StoredSortedEntrySet) saveSMap.entrySet()).subSet(
2204                             mapEntry(rangeBegin), true,
2205                             mapEntry(rangeEnd + 1), false));
2206             assertEquals(smap.keySet(),
2207                         ((StoredSortedKeySet) saveSMap.keySet()).subSet(
2208                             makeKey(rangeBegin), true,
2209                             makeKey(rangeEnd + 1), false));
2210             if (smap.values() instanceof SortedSet) {
2211                 assertEquals(smap.values(),
2212                             ((StoredSortedValueSet) saveSMap.values()).subSet(
2213                                 makeVal(rangeBegin), true,
2214                                 makeVal(rangeEnd + 1), false));
2215             }
2216             break;
2217         case HEAD:
2218             smap = (StoredSortedMap) smap.headMap(makeKey(rangeEnd + 1));
2219             if (canMakeSubList) {
2220                 list = (StoredList) list.subList(0,
2221                                                  rangeEnd + 1 - beginKey);
2222             }
2223             // check for equivalent ranges
2224             assertEquals(smap,
2225                         (saveSMap).headMap(
2226                             makeKey(rangeEnd + 1), false));
2227             assertEquals(smap.entrySet(),
2228                         ((StoredSortedEntrySet) saveSMap.entrySet()).headSet(
2229                             mapEntry(rangeEnd + 1), false));
2230             assertEquals(smap.keySet(),
2231                         ((StoredSortedKeySet) saveSMap.keySet()).headSet(
2232                             makeKey(rangeEnd + 1), false));
2233             if (smap.values() instanceof SortedSet) {
2234                 assertEquals(smap.values(),
2235                             ((StoredSortedValueSet) saveSMap.values()).headSet(
2236                                 makeVal(rangeEnd + 1), false));
2237             }
2238             break;
2239         case TAIL:
2240             smap = (StoredSortedMap) smap.tailMap(makeKey(rangeBegin));
2241             if (canMakeSubList) {
2242                 list = (StoredList) list.subList(listBegin,
2243                                                  maxKey + 1 - beginKey);
2244             }
2245             // check for equivalent ranges
2246             assertEquals(smap,
2247                         (saveSMap).tailMap(
2248                             makeKey(rangeBegin), true));
2249             assertEquals(smap.entrySet(),
2250                         ((StoredSortedEntrySet) saveSMap.entrySet()).tailSet(
2251                             mapEntry(rangeBegin), true));
2252             assertEquals(smap.keySet(),
2253                         ((StoredSortedKeySet) saveSMap.keySet()).tailSet(
2254                             makeKey(rangeBegin), true));
2255             if (smap.values() instanceof SortedSet) {
2256                 assertEquals(smap.values(),
2257                             ((StoredSortedValueSet) saveSMap.values()).tailSet(
2258                                 makeVal(rangeBegin), true));
2259             }
2260             break;
2261         default: throw new RuntimeException();
2262         }
2263         map = smap;
2264         beginKey = rangeBegin;
2265         if (rangeBegin < 1 || rangeEnd > maxKey) {
2266             endKey = rangeBegin - 1; // force empty range for readAll()
2267         } else {
2268             endKey = rangeEnd;
2269         }
2270     }
2271 
clearRange()2272     void clearRange() {
2273 
2274         rangeType = NONE;
2275         beginKey = 1;
2276         endKey = maxKey;
2277         map = saveMap;
2278         smap = saveSMap;
2279         list = saveList;
2280     }
2281 
createOutOfRange(int rangeBegin, int rangeEnd)2282     void createOutOfRange(int rangeBegin, int rangeEnd) {
2283         // map
2284 
2285         if (rangeType != TAIL) {
2286             try {
2287                 smap.subMap(makeKey(rangeBegin), makeKey(rangeEnd + 2));
2288                 fail();
2289             } catch (IllegalArgumentException e) { }
2290             try {
2291                 smap.headMap(makeKey(rangeEnd + 2));
2292                 fail();
2293             } catch (IllegalArgumentException e) { }
2294             checkDupsSize(0, smap.duplicates(makeKey(rangeEnd + 2)));
2295         }
2296         if (rangeType != HEAD) {
2297             try {
2298                 smap.subMap(makeKey(rangeBegin - 1), makeKey(rangeEnd + 1));
2299                 fail();
2300             } catch (IllegalArgumentException e) { }
2301             try {
2302                 smap.tailMap(makeKey(rangeBegin - 1));
2303                 fail();
2304             } catch (IllegalArgumentException e) { }
2305             checkDupsSize(0, smap.duplicates(makeKey(rangeBegin - 1)));
2306         }
2307 
2308         // keySet
2309 
2310         if (rangeType != TAIL) {
2311             SortedSet sset = (SortedSet) map.keySet();
2312             try {
2313                 sset.subSet(makeKey(rangeBegin), makeKey(rangeEnd + 2));
2314                 fail();
2315             } catch (IllegalArgumentException e) { }
2316             try {
2317                 sset.headSet(makeKey(rangeEnd + 2));
2318                 fail();
2319             } catch (IllegalArgumentException e) { }
2320             try {
2321                 iterator(sset.subSet(makeKey(rangeEnd + 1),
2322                                      makeKey(rangeEnd + 2)));
2323                 fail();
2324             } catch (IllegalArgumentException e) { }
2325         }
2326         if (rangeType != HEAD) {
2327             SortedSet sset = (SortedSet) map.keySet();
2328             try {
2329                 sset.subSet(makeKey(rangeBegin - 1), makeKey(rangeEnd + 1));
2330                 fail();
2331             } catch (IllegalArgumentException e) { }
2332             try {
2333                 sset.tailSet(makeKey(rangeBegin - 1));
2334                 fail();
2335             } catch (IllegalArgumentException e) { }
2336             try {
2337                 iterator(sset.subSet(makeKey(rangeBegin - 1),
2338                                      makeKey(rangeBegin)));
2339                 fail();
2340             } catch (IllegalArgumentException e) { }
2341         }
2342 
2343         // entrySet
2344 
2345         if (rangeType != TAIL) {
2346             SortedSet sset = (SortedSet) map.entrySet();
2347             try {
2348                 sset.subSet(mapEntry(rangeBegin), mapEntry(rangeEnd + 2));
2349                 fail();
2350             } catch (IllegalArgumentException e) { }
2351             try {
2352                 sset.headSet(mapEntry(rangeEnd + 2));
2353                 fail();
2354             } catch (IllegalArgumentException e) { }
2355             try {
2356                 iterator(sset.subSet(mapEntry(rangeEnd + 1),
2357                                      mapEntry(rangeEnd + 2)));
2358                 fail();
2359             } catch (IllegalArgumentException e) { }
2360         }
2361         if (rangeType != HEAD) {
2362             SortedSet sset = (SortedSet) map.entrySet();
2363             try {
2364                 sset.subSet(mapEntry(rangeBegin - 1), mapEntry(rangeEnd + 1));
2365                 fail();
2366             } catch (IllegalArgumentException e) { }
2367             try {
2368                 sset.tailSet(mapEntry(rangeBegin - 1));
2369                 fail();
2370             } catch (IllegalArgumentException e) { }
2371             try {
2372                 iterator(sset.subSet(mapEntry(rangeBegin - 1),
2373                                      mapEntry(rangeBegin)));
2374                 fail();
2375             } catch (IllegalArgumentException e) { }
2376         }
2377 
2378         // values
2379 
2380         if (map.values() instanceof SortedSet) {
2381             SortedSet sset = (SortedSet) map.values();
2382             if (rangeType != TAIL) {
2383                 try {
2384                     sset.subSet(makeVal(rangeBegin),
2385                                 makeVal(rangeEnd + 2));
2386                     fail();
2387                 } catch (IllegalArgumentException e) { }
2388                 try {
2389                     sset.headSet(makeVal(rangeEnd + 2));
2390                     fail();
2391                 } catch (IllegalArgumentException e) { }
2392             }
2393             if (rangeType != HEAD) {
2394                 try {
2395                     sset.subSet(makeVal(rangeBegin - 1),
2396                                 makeVal(rangeEnd + 1));
2397                     fail();
2398                 } catch (IllegalArgumentException e) { }
2399                 try {
2400                     sset.tailSet(makeVal(rangeBegin - 1));
2401                     fail();
2402                 } catch (IllegalArgumentException e) { }
2403             }
2404         }
2405 
2406         // list
2407 
2408         if (list != null) {
2409             int size = rangeEnd - rangeBegin + 1;
2410             try {
2411                 list.subList(0, size + 1);
2412                 fail();
2413             } catch (IndexOutOfBoundsException e) { }
2414             try {
2415                 list.subList(-1, size);
2416                 fail();
2417             } catch (IndexOutOfBoundsException e) { }
2418             try {
2419                 list.subList(2, 1);
2420                 fail();
2421             } catch (IndexOutOfBoundsException e) { }
2422             try {
2423                 list.subList(size, size);
2424                 fail();
2425             } catch (IndexOutOfBoundsException e) { }
2426         }
2427     }
2428 
writeOutOfRange(Long badNewKey)2429     void writeOutOfRange(Long badNewKey) {
2430         try {
2431             map.put(badNewKey, makeVal(badNewKey));
2432             fail();
2433         } catch (IllegalArgumentException e) {
2434             assertTrue(e.toString(), index == null);
2435         } catch (UnsupportedOperationException e) {
2436             assertTrue(index != null);
2437         }
2438         try {
2439             map.keySet().add(badNewKey);
2440             fail();
2441         } catch (IllegalArgumentException e) {
2442             assertTrue(index == null);
2443         } catch (UnsupportedOperationException e) {
2444             assertTrue(index != null);
2445         }
2446         try {
2447             map.values().add(makeEntity(badNewKey));
2448             fail();
2449         } catch (IllegalArgumentException e) {
2450             assertTrue(isEntityBinding && index == null);
2451         } catch (UnsupportedOperationException e) {
2452             assertTrue(!(isEntityBinding && index == null));
2453         }
2454         if (list != null) {
2455             int i = badNewKey.intValue() - beginKey;
2456             try {
2457                 list.set(i, makeVal(i));
2458                 fail();
2459             } catch (IndexOutOfBoundsException e) {
2460                 assertTrue(index == null);
2461             } catch (UnsupportedOperationException e) {
2462                 assertTrue(index != null);
2463             }
2464             try {
2465                 list.add(i, makeVal(badNewKey));
2466                 fail();
2467             } catch (UnsupportedOperationException e) {
2468             }
2469         }
2470     }
2471 
readWriteDuplicates()2472     void readWriteDuplicates()
2473         throws Exception {
2474 
2475         writeRunner.run(new TransactionWorker() {
2476             public void doWork() throws Exception {
2477                 if (index == null) {
2478                     readWritePrimaryDuplicates(beginKey);
2479                     readWritePrimaryDuplicates(beginKey + 1);
2480                     readWritePrimaryDuplicates(endKey);
2481                     readWritePrimaryDuplicates(endKey - 1);
2482                 } else {
2483                     readWriteIndexedDuplicates(beginKey);
2484                     readWriteIndexedDuplicates(beginKey + 1);
2485                     readWriteIndexedDuplicates(endKey);
2486                     readWriteIndexedDuplicates(endKey - 1);
2487                 }
2488             }
2489         });
2490     }
2491 
readWritePrimaryDuplicates(int i)2492     void readWritePrimaryDuplicates(int i)
2493         throws Exception {
2494 
2495         Collection dups;
2496         // make duplicate values
2497         final Long key = makeKey(i);
2498         final Object[] values = new Object[5];
2499         for (int j = 0; j < values.length; j += 1) {
2500             values[j] = isEntityBinding
2501                         ? makeEntity(i, i + j)
2502                         : makeVal(i + j);
2503         }
2504         // add duplicates
2505         outerLoop: for (int writeMode = 0;; writeMode += 1) {
2506             //System.out.println("write mode " + writeMode);
2507             switch (writeMode) {
2508                 case 0:
2509                 case 1: {
2510                     // write with Map.put()
2511                     for (int j = 1; j < values.length; j += 1) {
2512                         map.put(key, values[j]);
2513                     }
2514                     break;
2515                 }
2516                 case 2: {
2517                     // write with Map.duplicates().add()
2518                     dups = map.duplicates(key);
2519                     for (int j = 1; j < values.length; j += 1) {
2520                         dups.add(values[j]);
2521                     }
2522                     break;
2523                 }
2524                 case 3: {
2525                     // write with Map.duplicates().iterator().add()
2526                     writeIterRunner.run(new TransactionWorker() {
2527                         public void doWork() {
2528                             Collection dups = map.duplicates(key);
2529                             Iterator iter = iterator(dups);
2530                             assertEquals(values[0], iter.next());
2531                             assertTrue(!iter.hasNext());
2532                             try {
2533                                 for (int j = 1; j < values.length; j += 1) {
2534                                     ((ListIterator) iter).add(values[j]);
2535                                 }
2536                             } finally {
2537                                 StoredIterator.close(iter);
2538                             }
2539                         }
2540                     });
2541                     break;
2542                 }
2543                 case 4: {
2544                     // write with Map.values().add()
2545                     if (!isEntityBinding) {
2546                         continue;
2547                     }
2548                     Collection set = map.values();
2549                     for (int j = 1; j < values.length; j += 1) {
2550                         set.add(values[j]);
2551                     }
2552                     break;
2553                 }
2554                 default: {
2555                     break outerLoop;
2556                 }
2557             }
2558             checkDupsSize(values.length, map.duplicates(key));
2559             // read duplicates
2560             readDuplicates(i, key, values);
2561             // remove duplicates
2562             switch (writeMode) {
2563                 case 0: {
2564                     // remove with Map.remove()
2565                     checkDupsSize(values.length, map.duplicates(key));
2566                     map.remove(key); // remove all values
2567                     checkDupsSize(0, map.duplicates(key));
2568                     map.put(key, values[0]); // put back original value
2569                     checkDupsSize(1, map.duplicates(key));
2570                     break;
2571                 }
2572                 case 1: {
2573                     // remove with Map.keySet().remove()
2574                     map.keySet().remove(key); // remove all values
2575                     map.put(key, values[0]); // put back original value
2576                     break;
2577                 }
2578                 case 2: {
2579                     // remove with Map.duplicates().clear()
2580                     dups = map.duplicates(key);
2581                     dups.clear(); // remove all values
2582                     dups.add(values[0]); // put back original value
2583                     break;
2584                 }
2585                 case 3: {
2586                     // remove with Map.duplicates().iterator().remove()
2587                     writeIterRunner.run(new TransactionWorker() {
2588                         public void doWork() {
2589                             Collection dups = map.duplicates(key);
2590                             Iterator iter = iterator(dups);
2591                             try {
2592                                 for (int j = 0; j < values.length; j += 1) {
2593                                     assertEquals(values[j], iter.next());
2594                                     if (j != 0) {
2595                                         iter.remove();
2596                                     }
2597                                 }
2598                             } finally {
2599                                 StoredIterator.close(iter);
2600                             }
2601                         }
2602                     });
2603                     break;
2604                 }
2605                 case 4: {
2606                     // remove with Map.values().remove()
2607                     if (!isEntityBinding) {
2608                         throw new IllegalStateException();
2609                     }
2610                     Collection set = map.values();
2611                     for (int j = 1; j < values.length; j += 1) {
2612                         set.remove(values[j]);
2613                     }
2614                     break;
2615                 }
2616                 default: throw new IllegalStateException();
2617             }
2618             // verify that only original value is present
2619             dups = map.duplicates(key);
2620             assertTrue(dups.contains(values[0]));
2621             for (int j = 1; j < values.length; j += 1) {
2622                 assertTrue(!dups.contains(values[j]));
2623             }
2624             checkDupsSize(1, dups);
2625         }
2626     }
2627 
readWriteIndexedDuplicates(int i)2628     void readWriteIndexedDuplicates(int i) {
2629         Object key = makeKey(i);
2630         Object[] values = new Object[3];
2631         values[0] = makeVal(i);
2632         for (int j = 1; j < values.length; j += 1) {
2633             values[j] = isEntityBinding
2634                         ? makeEntity(endKey + j, i)
2635                         : makeVal(i);
2636         }
2637         // add duplicates
2638         for (int j = 1; j < values.length; j += 1) {
2639             imap.put(makeKey(endKey + j), values[j]);
2640         }
2641         // read duplicates
2642         readDuplicates(i, key, values);
2643         // remove duplicates
2644         for (int j = 1; j < values.length; j += 1) {
2645             imap.remove(makeKey(endKey + j));
2646         }
2647         checkDupsSize(1, map.duplicates(key));
2648     }
2649 
readDuplicates(int i, Object key, Object[] values)2650     void readDuplicates(int i, Object key, Object[] values) {
2651 
2652         boolean isOrdered = map.isOrdered();
2653         Collection dups;
2654         Iterator iter;
2655         // read with Map.duplicates().iterator()
2656         dups = map.duplicates(key);
2657         checkDupsSize(values.length, dups);
2658         iter = iterator(dups);
2659         try {
2660             for (int j = 0; j < values.length; j += 1) {
2661                 assertTrue(iter.hasNext());
2662                 Object val = iter.next();
2663                 assertEquals(values[j], val);
2664             }
2665             assertTrue(!iter.hasNext());
2666         } finally {
2667             StoredIterator.close(iter);
2668         }
2669         // read with Map.values().iterator()
2670         Collection clone = ((StoredCollection) map.values()).toList();
2671         iter = iterator(map.values());
2672         try {
2673             for (int j = beginKey; j < i; j += 1) {
2674                 Object val = iter.next();
2675                 assertTrue(clone.remove(makeVal(j)));
2676                 if (isOrdered) {
2677                     assertEquals(makeVal(j), val);
2678                 }
2679             }
2680             for (int j = 0; j < values.length; j += 1) {
2681                 Object val = iter.next();
2682                 assertTrue(clone.remove(values[j]));
2683                 if (isOrdered) {
2684                     assertEquals(values[j], val);
2685                 }
2686             }
2687             for (int j = i + 1; j <= endKey; j += 1) {
2688                 Object val = iter.next();
2689                 assertTrue(clone.remove(makeVal(j)));
2690                 if (isOrdered) {
2691                     assertEquals(makeVal(j), val);
2692                 }
2693             }
2694             assertTrue(!iter.hasNext());
2695             assertTrue(clone.isEmpty());
2696         } finally {
2697             StoredIterator.close(iter);
2698         }
2699         // read with Map.entrySet().iterator()
2700         clone = ((StoredCollection) map.entrySet()).toList();
2701         iter = iterator(map.entrySet());
2702         try {
2703             for (int j = beginKey; j < i; j += 1) {
2704                 Map.Entry entry = (Map.Entry) iter.next();
2705                 assertTrue(clone.remove(mapEntry(j)));
2706                 if (isOrdered) {
2707                     assertEquals(makeVal(j), entry.getValue());
2708                     assertEquals(makeKey(j), entry.getKey());
2709                 }
2710             }
2711             for (int j = 0; j < values.length; j += 1) {
2712                 Map.Entry entry = (Map.Entry) iter.next();
2713                 assertTrue(clone.remove(mapEntry(makeKey(i), values[j])));
2714                 if (isOrdered) {
2715                     assertEquals(values[j], entry.getValue());
2716                     assertEquals(makeKey(i), entry.getKey());
2717                 }
2718             }
2719             for (int j = i + 1; j <= endKey; j += 1) {
2720                 Map.Entry entry = (Map.Entry) iter.next();
2721                 assertTrue(clone.remove(mapEntry(j)));
2722                 if (isOrdered) {
2723                     assertEquals(makeVal(j), entry.getValue());
2724                     assertEquals(makeKey(j), entry.getKey());
2725                 }
2726             }
2727             assertTrue(!iter.hasNext());
2728             assertTrue(clone.isEmpty());
2729         } finally {
2730             StoredIterator.close(iter);
2731         }
2732         // read with Map.keySet().iterator()
2733         clone = ((StoredCollection) map.keySet()).toList();
2734         iter = iterator(map.keySet());
2735         try {
2736             for (int j = beginKey; j < i; j += 1) {
2737                 Object val = iter.next();
2738                 assertTrue(clone.remove(makeKey(j)));
2739                 if (isOrdered) {
2740                     assertEquals(makeKey(j), val);
2741                 }
2742             }
2743             if (true) {
2744                 // only one key is iterated for all duplicates
2745                 Object val = iter.next();
2746                 assertTrue(clone.remove(makeKey(i)));
2747                 if (isOrdered) {
2748                     assertEquals(makeKey(i), val);
2749                 }
2750             }
2751             for (int j = i + 1; j <= endKey; j += 1) {
2752                 Object val = iter.next();
2753                 assertTrue(clone.remove(makeKey(j)));
2754                 if (isOrdered) {
2755                     assertEquals(makeKey(j), val);
2756                 }
2757             }
2758             assertTrue(!iter.hasNext());
2759             assertTrue(clone.isEmpty());
2760         } finally {
2761             StoredIterator.close(iter);
2762         }
2763     }
2764 
duplicatesNotAllowed()2765     void duplicatesNotAllowed() {
2766 
2767         Collection dups = map.duplicates(makeKey(beginKey));
2768         try {
2769             dups.add(makeVal(beginKey));
2770             fail();
2771         } catch (UnsupportedOperationException expected) { }
2772         ListIterator iter = (ListIterator) iterator(dups);
2773         try {
2774             iter.add(makeVal(beginKey));
2775             fail();
2776         } catch (UnsupportedOperationException expected) {
2777         } finally {
2778             StoredIterator.close(iter);
2779         }
2780     }
2781 
listOperationsNotAllowed()2782     void listOperationsNotAllowed() {
2783 
2784         ListIterator iter = (ListIterator) iterator(map.values());
2785         try {
2786             try {
2787                 iter.nextIndex();
2788                 fail();
2789             } catch (UnsupportedOperationException expected) { }
2790             try {
2791                 iter.previousIndex();
2792                 fail();
2793             } catch (UnsupportedOperationException expected) { }
2794         } finally {
2795             StoredIterator.close(iter);
2796         }
2797     }
2798 
testCdbLocking()2799     void testCdbLocking() {
2800 
2801         Iterator readIterator;
2802         Iterator writeIterator;
2803         StoredKeySet set = (StoredKeySet) map.keySet();
2804 
2805         // can open two CDB read cursors
2806         readIterator = set.storedIterator(false);
2807         try {
2808             Iterator readIterator2 = set.storedIterator(false);
2809             StoredIterator.close(readIterator2);
2810         } finally {
2811             StoredIterator.close(readIterator);
2812         }
2813 
2814         // can open two CDB write cursors
2815         writeIterator = set.storedIterator(true);
2816         try {
2817             Iterator writeIterator2 = set.storedIterator(true);
2818             StoredIterator.close(writeIterator2);
2819         } finally {
2820             StoredIterator.close(writeIterator);
2821         }
2822 
2823         // cannot open CDB write cursor when read cursor is open,
2824         readIterator = set.storedIterator(false);
2825         try {
2826             writeIterator = set.storedIterator(true);
2827             fail();
2828             StoredIterator.close(writeIterator);
2829         } catch (IllegalStateException e) {
2830         } finally {
2831             StoredIterator.close(readIterator);
2832         }
2833 
2834         if (index == null) {
2835             // cannot put() with read cursor open
2836             readIterator = set.storedIterator(false);
2837             try {
2838                 map.put(makeKey(1), makeVal(1));
2839                 fail();
2840             } catch (IllegalStateException e) {
2841             } finally {
2842                 StoredIterator.close(readIterator);
2843             }
2844 
2845             // cannot append() with write cursor open with RECNO/QUEUE only
2846             writeIterator = set.storedIterator(true);
2847             try {
2848                 if (testStore.isQueueOrRecno()) {
2849                     try {
2850                         map.append(makeVal(1));
2851                         fail();
2852                     } catch (IllegalStateException e) {}
2853                 } else {
2854                     map.append(makeVal(1));
2855                 }
2856             } finally {
2857                 StoredIterator.close(writeIterator);
2858             }
2859         }
2860     }
2861 
makeVal(int key)2862     Object makeVal(int key) {
2863 
2864         if (isEntityBinding) {
2865             return makeEntity(key);
2866         } else {
2867             return new Long(key + 100);
2868         }
2869     }
2870 
makeVal(int key, int val)2871     Object makeVal(int key, int val) {
2872 
2873         if (isEntityBinding) {
2874             return makeEntity(key, val);
2875         } else {
2876             return makeVal(val);
2877         }
2878     }
2879 
makeEntity(int key, int val)2880     Object makeEntity(int key, int val) {
2881 
2882         return new TestEntity(key, val + 100);
2883     }
2884 
intVal(Object val)2885     int intVal(Object val) {
2886 
2887         if (isEntityBinding) {
2888             return ((TestEntity) val).value - 100;
2889         } else {
2890             return ((Long) val).intValue() - 100;
2891         }
2892     }
2893 
intKey(Object key)2894     int intKey(Object key) {
2895 
2896         return ((Long) key).intValue();
2897     }
2898 
makeVal(Long key)2899     Object makeVal(Long key) {
2900 
2901         return makeVal(key.intValue());
2902     }
2903 
makeEntity(int key)2904     Object makeEntity(int key) {
2905 
2906         return makeEntity(key, key);
2907     }
2908 
makeEntity(Long key)2909     Object makeEntity(Long key) {
2910 
2911         return makeEntity(key.intValue());
2912     }
2913 
intIter(Collection coll, Object value)2914     int intIter(Collection coll, Object value) {
2915 
2916         if (coll instanceof StoredKeySet) {
2917             return intKey(value);
2918         } else {
2919             if (coll instanceof StoredEntrySet) {
2920                 value = ((Map.Entry) value).getValue();
2921             }
2922             return intVal(value);
2923         }
2924     }
2925 
mapEntry(Object key, Object val)2926     Map.Entry mapEntry(Object key, Object val) {
2927 
2928         return new MapEntryParameter(key, val);
2929     }
2930 
mapEntry(int key)2931     Map.Entry mapEntry(int key) {
2932 
2933         return new MapEntryParameter(makeKey(key), makeVal(key));
2934     }
2935 
makeKey(int key)2936     Long makeKey(int key) {
2937 
2938         return new Long(key);
2939     }
2940 
isSubMap()2941     boolean isSubMap() {
2942 
2943         return rangeType != NONE;
2944     }
2945 
checkDupsSize(int expected, Collection coll)2946     void checkDupsSize(int expected, Collection coll) {
2947 
2948         assertEquals(expected, coll.size());
2949         if (coll instanceof StoredCollection) {
2950             StoredIterator i = ((StoredCollection) coll).storedIterator(false);
2951             try {
2952                 int actual = 0;
2953                 if (i.hasNext()) {
2954                     i.next();
2955                     actual = i.count();
2956                 }
2957                 assertEquals(expected, actual);
2958             } finally {
2959                 StoredIterator.close(i);
2960             }
2961         }
2962     }
2963 
isListAddAllowed()2964     private boolean isListAddAllowed() {
2965 
2966         return list != null && testStore.isQueueOrRecno() &&
2967                list.areKeysRenumbered();
2968     }
2969 
countElements(Collection coll)2970     private int countElements(Collection coll) {
2971 
2972         int count = 0;
2973         Iterator iter = iterator(coll);
2974         try {
2975             while (iter.hasNext()) {
2976                 iter.next();
2977                 count += 1;
2978             }
2979         } finally {
2980             StoredIterator.close(iter);
2981         }
2982         return count;
2983     }
2984 }
2985