KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sleepycat > je > tree > TreeTest


1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 2002,2006 Oracle. All rights reserved.
5  *
6  * $Id: TreeTest.java,v 1.86 2006/10/30 21:14:52 bostic Exp $
7  */
8
9 package com.sleepycat.je.tree;
10
11 import java.io.IOException JavaDoc;
12
13 import com.sleepycat.je.BtreeStats;
14 import com.sleepycat.je.DatabaseException;
15 import com.sleepycat.je.DatabaseStats;
16 import com.sleepycat.je.DbInternal;
17 import com.sleepycat.je.VerifyConfig;
18 import com.sleepycat.je.dbi.NullCursor;
19 import com.sleepycat.je.txn.BasicLocker;
20 import com.sleepycat.je.txn.Locker;
21 import com.sleepycat.je.util.TestUtils;
22
23 public class TreeTest extends TreeTestBase {
24
25     public TreeTest() {
26     super();
27     }
28
29     /**
30      * Rudimentary insert/retrieve test.
31      */
32     public void testSimpleTreeCreation()
33     throws DatabaseException {
34         initEnv(false);
35         Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
36         NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
37         insertAndRetrieve(cursor, "aaaaa".getBytes(),
38                           new LN((byte[]) null));
39         insertAndRetrieve(cursor, "aaaab".getBytes(),
40                           new LN((byte[]) null));
41         insertAndRetrieve(cursor, "aaaa".getBytes(),
42                           new LN((byte[]) null));
43         insertAndRetrieve(cursor, "aaa".getBytes(),
44                           new LN((byte[]) null));
45         txn.operationEnd();
46     }
47
48     /**
49      * Slightly less rudimentary test inserting a handfull of keys and LN's.
50      */
51     public void testMultipleInsertRetrieve0()
52     throws DatabaseException {
53
54         /*
55      * Set the seed to reproduce a specific problem found while debugging:
56          * IN.split was splitting with the identifier key being on the right
57          * side.
58      */
59         initEnv(false);
60         Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
61         NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
62         for (int i = 0; i < 21; i++) {
63             byte[] key = new byte[N_KEY_BYTES];
64             TestUtils.generateRandomAlphaBytes(key);
65             insertAndRetrieve(cursor, key, new LN((byte[]) null));
66         }
67         txn.operationEnd();
68     }
69
70     /**
71      * Insert a bunch of keys and test that they retrieve back ok. While we
72      * insert, maintain the highest and lowest keys inserted. Verify that
73      * getFirstNode and getLastNode return those two entries. Lather, rinse,
74      * repeat.
75      */
76     public void testMultipleInsertRetrieve1()
77     throws DatabaseException, IOException JavaDoc {
78
79         initEnv(false);
80     doMultipleInsertRetrieve1();
81     }
82
83     /**
84      * Helper routine for above.
85      */
86     private void doMultipleInsertRetrieve1()
87     throws DatabaseException {
88
89         byte[][] keys = new byte[N_KEYS][];
90         LN[] lns = new LN[N_KEYS];
91         Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
92         NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
93         for (int i = 0; i < N_KEYS; i++) {
94             byte[] key = new byte[N_KEY_BYTES];
95             keys[i] = key;
96             lns[i] = new LN((byte[]) null);
97             TestUtils.generateRandomAlphaBytes(key);
98             insertAndRetrieve(cursor, key, lns[i]);
99         }
100
101         for (int i = 0; i < N_KEYS; i++) {
102             assertTrue(retrieveLN(keys[i]) == lns[i]);
103         }
104
105         TestUtils.checkLatchCount();
106         IN leftMostNode = tree.getFirstNode();
107
108         assertTrue(leftMostNode instanceof BIN);
109         BIN lmn = (BIN) leftMostNode;
110         lmn.releaseLatch();
111         TestUtils.checkLatchCount();
112         assertTrue(Key.compareKeys(lmn.getKey(0), minKey, null) == 0);
113
114         TestUtils.checkLatchCount();
115         IN rightMostNode = tree.getLastNode();
116
117         assertTrue(rightMostNode instanceof BIN);
118         BIN rmn = (BIN) rightMostNode;
119         rmn.releaseLatch();
120         TestUtils.checkLatchCount();
121         assertTrue(Key.compareKeys
122             (rmn.getKey(rmn.getNEntries() - 1), maxKey, null) == 0);
123         TreeStats ts = tree.getTreeStats();
124         assertTrue(ts.nRootSplits > 1);
125
126         txn.operationEnd();
127     }
128
129     /**
130      * Create a tree. After creation, walk the bins forwards using getNextBin
131      * counting the keys and validating that the keys are being returned in
132      * ascending order. Ensure that the correct number of keys were returned.
133      */
134     public void testCountAndValidateKeys()
135     throws DatabaseException, IOException JavaDoc {
136
137         initEnv(false);
138     doCountAndValidateKeys();
139     }
140
141     /**
142      * Helper routine for above test.
143      */
144     private void doCountAndValidateKeys()
145     throws DatabaseException {
146         byte[][] keys = new byte[N_KEYS][];
147         LN[] lns = new LN[N_KEYS];
148         Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
149         NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
150
151         for (int i = 0; i < N_KEYS; i++) {
152             byte[] key = new byte[N_KEY_BYTES];
153             keys[i] = key;
154             lns[i] = new LN((byte[]) null);
155             TestUtils.generateRandomAlphaBytes(key);
156             insertAndRetrieve(cursor, key, lns[i]);
157         }
158         assertTrue(countAndValidateKeys(tree) == N_KEYS);
159         txn.operationEnd();
160     }
161
162     /**
163      * Create a tree. After creation, walk the bins backwards using getPrevBin
164      * counting the keys and validating that the keys are being returned in
165      * descending order. Ensure that the correct number of keys were returned.
166      */
167     public void testCountAndValidateKeysBackwards()
168     throws DatabaseException, IOException JavaDoc {
169
170         initEnv(false);
171     doCountAndValidateKeysBackwards();
172     }
173
174     /**
175      * Helper routine for above test.
176      */
177     public void doCountAndValidateKeysBackwards()
178     throws DatabaseException {
179
180         byte[][] keys = new byte[N_KEYS][];
181         LN[] lns = new LN[N_KEYS];
182         Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
183         NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
184         for (int i = 0; i < N_KEYS; i++) {
185             byte[] key = new byte[N_KEY_BYTES];
186             keys[i] = key;
187             lns[i] = new LN((byte[]) null);
188             TestUtils.generateRandomAlphaBytes(key);
189             insertAndRetrieve(cursor, key, lns[i]);
190         }
191         assertTrue(countAndValidateKeysBackwards(tree) == N_KEYS);
192         txn.operationEnd();
193     }
194
195     public void testAscendingInsertBalance()
196     throws DatabaseException {
197
198         initEnv(false);
199         Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
200         NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
201
202         /* Fill up a db with data */
203         for (int i = 0; i < N_KEYS; i++) {
204             byte[] keyBytes = new byte[4];
205             TestUtils.putUnsignedInt(keyBytes, TestUtils.alphaKey(i));
206             insertAndRetrieve(cursor, keyBytes,
207                               new LN((byte[]) null));
208         }
209         
210         TestUtils.checkLatchCount();
211
212         /* Count the number of levels on the left. */
213         IN leftMostNode = tree.getFirstNode();
214         assertTrue(leftMostNode instanceof BIN);
215         int leftSideLevels = 0;
216         do {
217             SearchResult result =
218         tree.getParentINForChildIN(leftMostNode, true, true);
219             leftMostNode = result.parent;
220             leftSideLevels++;
221         } while (leftMostNode != null);
222         TestUtils.checkLatchCount();
223
224         /* Count the number of levels on the right. */
225         IN rightMostNode = tree.getLastNode();
226         assertTrue(rightMostNode instanceof BIN);
227         int rightSideLevels = 0;
228         do {
229             SearchResult result =
230         tree.getParentINForChildIN(rightMostNode, true, true);
231             rightMostNode = result.parent;
232             rightSideLevels++;
233         } while (rightMostNode != null);
234         TestUtils.checkLatchCount();
235         if (leftSideLevels > 10 ||
236             rightSideLevels > 10) {
237             fail("Levels too high (" +
238                  leftSideLevels +
239                  "/" +
240                  rightSideLevels +
241                  ") on descending insert");
242         }
243         txn.operationEnd();
244     }
245
246     public void testDescendingInsertBalance()
247     throws DatabaseException {
248         initEnv(false);
249         Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
250         NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
251
252         for (int i = N_KEYS; i >= 0; --i) {
253             byte[] keyBytes = new byte[4];
254             TestUtils.putUnsignedInt(keyBytes, TestUtils.alphaKey(i));
255             insertAndRetrieve(cursor, keyBytes,
256                               new LN((byte[]) null));
257         }
258         
259         TestUtils.checkLatchCount();
260         IN leftMostNode = tree.getFirstNode();
261
262         assertTrue(leftMostNode instanceof BIN);
263         int leftSideLevels = 0;
264         do {
265             SearchResult result =
266         tree.getParentINForChildIN(leftMostNode, true, true);
267             leftMostNode = result.parent;
268             leftSideLevels++;
269         } while (leftMostNode != null);
270         TestUtils.checkLatchCount();
271
272         IN rightMostNode = tree.getLastNode();
273
274         assertTrue(rightMostNode instanceof BIN);
275         int rightSideLevels = 0;
276         do {
277             SearchResult result =
278         tree.getParentINForChildIN(rightMostNode, true, true);
279             rightMostNode = result.parent;
280             rightSideLevels++;
281         } while (rightMostNode != null);
282         TestUtils.checkLatchCount();
283         if (leftSideLevels > 10 ||
284             rightSideLevels > 10) {
285             fail("Levels too high (" +
286                  leftSideLevels +
287                  "/" +
288                  rightSideLevels +
289                  ") on descending insert");
290         }
291         txn.operationEnd();
292     }
293
294     /**
295      * Insert a bunch of keys. Call verify and validate the results.
296      */
297     public void testVerify()
298     throws DatabaseException {
299
300         initEnv(false);
301     byte[][] keys = new byte[N_KEYS][];
302     LN[] lns = new LN[N_KEYS];
303         Locker txn = new BasicLocker(DbInternal.envGetEnvironmentImpl(env));
304         NullCursor cursor = new NullCursor(tree.getDatabase(), txn);
305         
306     for (int i = 0; i < N_KEYS; i++) {
307         byte[] key = new byte[N_KEY_BYTES];
308         keys[i] = key;
309         lns[i] = new LN((byte[]) new byte[1]);
310         TestUtils.generateRandomAlphaBytes(key);
311         insertAndRetrieve(cursor, key, lns[i]);
312     }
313
314         /*
315          * Note that verify will attempt to continue past errors, so
316          * assertTrue on the status return.
317          */
318         assertTrue(env.verify(new VerifyConfig(), System.err));
319     DatabaseStats stats = db.verify(new VerifyConfig());
320     BtreeStats btStats = (BtreeStats) stats;
321
322     assertTrue(btStats.getInternalNodeCount() <
323            btStats.getBottomInternalNodeCount());
324     assertTrue(btStats.getBottomInternalNodeCount() <
325            btStats.getLeafNodeCount() +
326            btStats.getDeletedLeafNodeCount());
327     assertTrue(btStats.getLeafNodeCount() +
328            btStats.getDeletedLeafNodeCount() ==
329            N_KEYS);
330         txn.operationEnd();
331
332         /* Now intentionally create LogFileNotFoundExceptions */
333         /*
334           db.close();
335           env.close();
336
337           This is disabled until the method for flipping files is
338           introduced. It's too hard to create a LogFileNotFoundException
339           by brute force deleting a file; often recovery doesn't work.
340           Instead, use a flipped file later on.
341
342         String [] jeFiles =
343             FileManager.listFiles(envHome,
344                                   new String[] {FileManager.JE_SUFFIX});
345         int targetIdx = jeFiles.length / 2;
346         assertTrue(targetIdx > 0);
347         File targetFile = new File(envHome, jeFiles[targetIdx]);
348         assertTrue(targetFile.delete());
349
350         initEnv(false);
351         assertFalse(env.verify(new VerifyConfig(), System.err));
352         */
353     }
354 }
355
Popular Tags