|
1
8
9 package com.sleepycat.je.tree;
10
11 import com.sleepycat.je.DatabaseException;
12 import com.sleepycat.je.DbInternal;
13 import com.sleepycat.je.dbi.NullCursor;
14 import com.sleepycat.je.txn.BasicLocker;
15 import com.sleepycat.je.txn.Locker;
16 import com.sleepycat.je.txn.LockResult;
17 import com.sleepycat.je.util.TestUtils;
18
19 public class TreeDuplicateTest extends TreeTestBase {
20
21 public TreeDuplicateTest() {
22 super();
23 }
24
25 private static final int N_DUPLICATES_PER_KEY = N_KEYS;
26 private static final int N_TOP_LEVEL_KEYS = 10;
27
28
31 public void testSimpleTreeCreation()
32 throws Throwable  {
33
34 try {
35
36 initEnv(true);
37 Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
38 NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
39
40 try {
41 byte[][] keys = new byte[N_TOP_LEVEL_KEYS][];
42 LN[][] lns = new LN[N_TOP_LEVEL_KEYS][];
43 for (int i = 0; i < N_TOP_LEVEL_KEYS; i++) {
44 byte[] key = new byte[N_KEY_BYTES];
45 keys[i] = key;
46 lns[i] = new LN[N_DUPLICATES_PER_KEY];
47 TestUtils.generateRandomAlphaBytes(key);
48 for (int j = 0; j < N_DUPLICATES_PER_KEY; j++) {
49 byte[] data = new byte[N_KEY_BYTES];
50 TestUtils.generateRandomAlphaBytes(data);
51 LN ln = new LN(data);
52 lns[i][j] = ln;
53 insertAndRetrieveDuplicate(key, ln, cursor);
54 }
55 }
56
57 for (int i = 0; i < N_TOP_LEVEL_KEYS; i++) {
58 byte[] key = keys[i];
59 for (int j = 0; j < N_DUPLICATES_PER_KEY; j++) {
60 LN ln = lns[i][j];
61 retrieveDuplicateLN(key, ln);
62 }
63 }
64 } finally {
65 txn.operationEnd();
66 }
67 } catch (Throwable t) {
68 t.printStackTrace();
69 throw t;
70 }
71 }
72
73
76 public void testNullRoot()
77 throws DatabaseException {
78
79 initEnv(false);
80 assertTrue(tree.search(null, Tree.SearchType.NORMAL, -1, null, true) ==
81 null);
82 TestUtils.checkLatchCount();
83 }
84
85
89 public void testGetFirstLast()
90 throws DatabaseException {
91
92 initEnv(true);
93 Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
94 NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
95
96
97 try {
98 TestUtils.checkLatchCount();
99 tree.getFirstNode(null);
100 fail("Tree.getFirstNode didn't throw IllegalArgumentException");
101 } catch (IllegalArgumentException IAE) {
102 }
103 TestUtils.checkLatchCount();
104
105 try {
106 TestUtils.checkLatchCount();
107 tree.getLastNode(null);
108 fail("Tree.getLastNode didn't throw IllegalArgumentException");
109 } catch (IllegalArgumentException IAE) {
110 }
111 TestUtils.checkLatchCount();
112
113 byte[][] keys = new byte[N_TOP_LEVEL_KEYS][];
114 LN[][] lns = new LN[N_TOP_LEVEL_KEYS][];
115 byte[][] minKeys = new byte[N_TOP_LEVEL_KEYS][];
116 byte[][] maxKeys = new byte[N_TOP_LEVEL_KEYS][];
117 for (int i = 0; i < N_TOP_LEVEL_KEYS; i++) {
118 byte[] key = new byte[N_KEY_BYTES];
119 byte[] minKey = null;
120 byte[] maxKey = null;
121 keys[i] = key;
122 lns[i] = new LN[N_DUPLICATES_PER_KEY];
123 TestUtils.generateRandomAlphaBytes(key);
124 for (int j = 0; j < N_DUPLICATES_PER_KEY; j++) {
125 byte[] data = new byte[N_KEY_BYTES];
126 TestUtils.generateRandomAlphaBytes(data);
127 byte[] dupKey = data;
128
129 if (minKey == null) {
130 minKey = dupKey;
131 } else if (Key.compareKeys(dupKey, minKey, null) < 0) {
132 minKey = dupKey;
133 }
134
135 if (maxKey == null) {
136 maxKey = dupKey;
137 } else if (Key.compareKeys(maxKey, dupKey, null) < 0) {
138 maxKey = dupKey;
139 }
140
141 LN ln = new LN(data);
142 lns[i][j] = ln;
143 insertAndRetrieveDuplicate(key, ln, cursor);
144 }
145 minKeys[i] = minKey;
146 maxKeys[i] = maxKey;
147 }
148
149 for (int i = 0; i < N_TOP_LEVEL_KEYS; i++) {
150 byte[] key = keys[i];
151 for (int j = 0; j < N_DUPLICATES_PER_KEY; j++) {
152 validateFirstLast(key, minKeys[i], maxKeys[i]);
153 }
154 }
155 txn.operationEnd();
156 }
157
158
162 private void validateFirstLast(byte[] key, byte[] minKey, byte[] maxKey)
163 throws DatabaseException {
164
165 TestUtils.checkLatchCount();
166
167
168 IN dr = tree.search(key, Tree.SearchType.NORMAL, -1, null, true);
169 if (!(dr instanceof BIN)) {
170 fail("search didn't return a BIN for key: " + key);
171 }
172 BIN topBin = (BIN) dr;
173 int index = topBin.findEntry(key, false, true);
174 if (index == -1) {
175 fail("Didn't read back key: " + key);
176 }
177 Node dupEntry = topBin.getTarget(index);
178 if (!(dupEntry instanceof DIN)) {
179 fail("Didn't find a DIN");
180 }
181 topBin.releaseLatch();
182 DIN duplicateRoot = (DIN) dupEntry;
183 duplicateRoot.latch();
184
185 DBIN leftMostNode = tree.getFirstNode(duplicateRoot);
186
187 assertTrue(leftMostNode instanceof DBIN);
188 leftMostNode.releaseLatch();
189 assertTrue(Key.compareKeys(leftMostNode.getKey(0), minKey, null) == 0);
190
191 duplicateRoot.latch();
192 DBIN rightMostNode = tree.getLastNode(duplicateRoot);
193
194 assertTrue(rightMostNode instanceof DBIN);
195 rightMostNode.releaseLatch();
196 assertTrue(Key.compareKeys
197 (rightMostNode.getKey(rightMostNode.getNEntries() - 1), maxKey,
198 null) == 0);
199
200 TestUtils.checkLatchCount();
201 }
202
203 private void insertAndRetrieveDuplicate(byte[] key, LN ln, NullCursor cursor)
204 throws DatabaseException {
205
206 TestUtils.checkLatchCount();
207 assertTrue(tree.insert(ln, key, true, cursor,
208 new LockResult(null, null)));
209 TestUtils.checkLatchCount();
210 assertTrue(retrieveDuplicateLN(key, ln) == ln);
211 }
212
213
216 private LN retrieveDuplicateLN(byte[] key, LN ln)
217 throws DatabaseException {
218
219 TreeLocation location = new TreeLocation();
220 try {
221 assertTrue(tree.getParentBINForChildLN(location,
222 key,
223 ln.getData(),
224 ln,
225 false,
226 false,
227 false,
228 true));
229
230 return (LN) location.bin.getTarget(location.index);
231 } finally {
232 location.bin.releaseLatch();
233 TestUtils.checkLatchCount();
234 }
235 }
236 }
237 |
Popular Tags |
Java API By Example, From Geeks To Geeks.