KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 2002,2006 Oracle. All rights reserved.
5  *
6  * $Id: GetParentNodeTest.java,v 1.41 2006/10/30 21:14:51 bostic Exp $
7  */
8
9 package com.sleepycat.je.tree;
10
11 import java.io.File JavaDoc;
12
13 import junit.framework.TestCase;
14
15 import com.sleepycat.je.Database;
16 import com.sleepycat.je.DatabaseConfig;
17 import com.sleepycat.je.DatabaseException;
18 import com.sleepycat.je.DbInternal;
19 import com.sleepycat.je.Environment;
20 import com.sleepycat.je.EnvironmentConfig;
21 import com.sleepycat.je.OperationStatus;
22 import com.sleepycat.je.Transaction;
23 import com.sleepycat.je.config.EnvironmentParams;
24 import com.sleepycat.je.dbi.DatabaseImpl;
25 import com.sleepycat.je.latch.LatchSupport;
26 import com.sleepycat.je.util.StringDbt;
27 import com.sleepycat.je.util.TestUtils;
28
29 public class GetParentNodeTest extends TestCase {
30     static private final boolean DEBUG = false;
31
32     private File JavaDoc envHome;
33     private Environment env;
34     private Database db;
35     private IN rootIN;
36     private IN firstLevel2IN;
37     private BIN firstBIN;
38     private DBIN firstDBIN;
39
40     public GetParentNodeTest() {
41         envHome = new File JavaDoc(System.getProperty(TestUtils.DEST_DIR));
42     }
43
44     public void setUp()
45         throws Exception JavaDoc {
46         TestUtils.removeLogFiles("Setup", envHome, false);
47         initEnv();
48     }
49
50     public void tearDown()
51         throws Exception JavaDoc {
52         try {
53             db.close();
54             env.close();
55         } catch (DatabaseException E) {
56         }
57                 
58         TestUtils.removeLogFiles("TearDown", envHome, true);
59     }
60
61     private void initEnv()
62         throws DatabaseException {
63
64         EnvironmentConfig envConfig = TestUtils.initEnvConfig();
65         envConfig.setConfigParam(EnvironmentParams.NODE_MAX.getName(), "4");
66         envConfig.setTransactional(true);
67         envConfig.setAllowCreate(true);
68         env = new Environment(envHome, envConfig);
69
70         String JavaDoc databaseName = "testDb";
71         Transaction txn = env.beginTransaction(null, null);
72         DatabaseConfig dbConfig = new DatabaseConfig();
73         dbConfig.setTransactional(true);
74         dbConfig.setAllowCreate(true);
75         dbConfig.setSortedDuplicates(true);
76         db = env.openDatabase(txn, databaseName, dbConfig);
77         txn.commit();
78     }
79
80     /**
81      * Test getParentINForChildIN and GetParentBINForChildLN painstakingly on a
82      * hand constructed tree.
83      */
84     public void testBasic()
85         throws Exception JavaDoc {
86
87         try {
88             /*
89              * Make a tree w/3 levels in the main tree and a single dup
90              * tree. The dupTree has two levels. The tree looks like this:
91          *
92              * root(key=a)
93              * |
94              * +---------------------------+
95              * IN(key=a) IN(key=e)
96              * | |
97              * +------------------+ +--------+--------+
98              * BIN(key=a) BIN(c) BIN(e) BIN(g) BIN(i)
99              * | | | | | | | | | | |
100              * LNa DINb LNc,d LNe,f LNg,h LNi,j,k
101              * |
102              * +----------+-------------+
103              * | | |
104              * DBIN(data1) DBIN(data3) DBIN(data5)
105              * LN LN LN LN LN LN LN
106              */
107             assertEquals(OperationStatus.SUCCESS,
108                          db.put(null, new StringDbt("a"),
109                                 new StringDbt("data1")));
110             assertEquals(OperationStatus.SUCCESS,
111                          db.put(null, new StringDbt("b"),
112                                 new StringDbt("data1")));
113             assertEquals(OperationStatus.SUCCESS,
114                          db.put(null, new StringDbt("c"),
115                                 new StringDbt("data1")));
116             assertEquals(OperationStatus.SUCCESS,
117                          db.put(null, new StringDbt("d"),
118                                 new StringDbt("data1")));
119             assertEquals(OperationStatus.SUCCESS,
120                          db.put(null, new StringDbt("e"),
121                                 new StringDbt("data1")));
122             assertEquals(OperationStatus.SUCCESS,
123                          db.put(null, new StringDbt("f"),
124                                 new StringDbt("data1")));
125             assertEquals(OperationStatus.SUCCESS,
126                          db.put(null, new StringDbt("g"),
127                                 new StringDbt("data1")));
128             assertEquals(OperationStatus.SUCCESS,
129                          db.put(null, new StringDbt("h"),
130                                 new StringDbt("data1")));
131             assertEquals(OperationStatus.SUCCESS,
132                          db.put(null, new StringDbt("i"),
133                                 new StringDbt("data1")));
134             assertEquals(OperationStatus.SUCCESS,
135                          db.put(null, new StringDbt("j"),
136                                 new StringDbt("data1")));
137             assertEquals(OperationStatus.SUCCESS,
138                          db.put(null, new StringDbt("k"),
139                                 new StringDbt("data1")));
140
141             /* Add one dup tree. */
142             byte[] dupKey = "b".getBytes();
143             assertEquals(OperationStatus.SUCCESS,
144                          db.put(null, new StringDbt("b"),
145                                 new StringDbt("data2")));
146             assertEquals(OperationStatus.SUCCESS,
147                          db.put(null, new StringDbt("b"),
148                                 new StringDbt("data3")));
149             assertEquals(OperationStatus.SUCCESS,
150                          db.put(null, new StringDbt("b"),
151                                 new StringDbt("data4")));
152             assertEquals(OperationStatus.SUCCESS,
153                          db.put(null, new StringDbt("b"),
154                                 new StringDbt("data5")));
155             assertEquals(OperationStatus.SUCCESS,
156                          db.put(null, new StringDbt("b"),
157                                 new StringDbt("data6")));
158             assertEquals(OperationStatus.SUCCESS,
159                          db.put(null, new StringDbt("b"),
160                 new StringDbt("data7")));
161
162             /*
163              * Test exact matches.
164              */
165             checkTreeUsingExistingNodes(dupKey, true);
166             checkTreeUsingExistingNodes(dupKey, false);
167
168             /* Test potential matches. */
169             checkTreeUsingPotentialNodes();
170
171             /* Test deletes. */
172         checkTreeWithDeletedBins(true);
173         checkTreeWithDeletedBins(false);
174
175             /* Should be no latches held. */
176             assertEquals(0, LatchSupport.countLatchesHeld());
177         } catch (Throwable JavaDoc t) {
178             t.printStackTrace();
179             throw new Exception JavaDoc(t);
180         }
181     }
182
183     private void checkTreeUsingExistingNodes(byte[] dupKey,
184                                              boolean requireExactMatch)
185         throws DatabaseException {
186
187         /* Start at the root. */
188         DatabaseImpl database = DbInternal.dbGetDatabaseImpl(db);
189         Tree tree = database.getTree();
190
191         if (DEBUG) {
192             tree.dump();
193         }
194
195         rootIN = tree.withRootLatchedShared
196         (new GetRoot(DbInternal.dbGetDatabaseImpl(db)));
197         rootIN.latch();
198         SearchResult result = tree.getParentINForChildIN(rootIN, true, true);
199         assertFalse(result.exactParentFound);
200         assertEquals(rootIN.getNEntries(), 2);
201    
202         /* Second and third level. */
203         BIN dupTreeBin = null;
204         DIN dupTreeDINRoot = null;
205         firstBIN = null;
206         int dupIndex = -1;
207         for (int i = 0; i < rootIN.getNEntries(); i++) {
208             /* Each level 2 IN. */
209             IN in = (IN) rootIN.fetchTarget(i);
210             if (i == 0) {
211                 firstLevel2IN = in;
212             }
213             checkMatch(tree, in, rootIN, i, requireExactMatch);
214
215             /* For each BIN, find its parent, and then find its LNs. */
216             for (int j = 0; j < in.getNEntries(); j++) {
217                 BIN bin = (BIN) in.fetchTarget(j);
218                 if (firstBIN == null) {
219                     firstBIN = bin;
220                 }
221                 checkMatch(tree, bin, in, j, requireExactMatch);
222
223                 for (int k = 0; k < bin.getNEntries(); k++) {
224                     Node n = bin.fetchTarget(k);
225                     if (n instanceof LN) {
226                         checkMatch(tree, (LN) n, bin, bin.getKey(k),
227                                    null, k, bin.getLsn(k));
228                     }
229                 }
230                     
231                 int findIndex = bin.findEntry(dupKey, false, true);
232                 if (findIndex > 0) {
233                     dupIndex = findIndex;
234                     dupTreeDINRoot =
235                         (DIN) bin.fetchTarget(dupIndex);
236                     dupTreeBin = bin;
237                 }
238             }
239         }
240
241         /* Check dup tree, assumes a 2 level tree. */
242         assertTrue(dupTreeBin != null);
243         assertTrue(dupTreeDINRoot != null);
244         checkMatch(tree, dupTreeDINRoot, dupTreeBin, dupIndex,
245                    requireExactMatch);
246         assertTrue(dupTreeDINRoot.getNEntries() > 0);
247
248         for (int i = 0; i < dupTreeDINRoot.getNEntries(); i++) {
249             IN in = (IN) dupTreeDINRoot.fetchTarget(i);
250             checkMatch(tree, in, dupTreeDINRoot, i, requireExactMatch);
251             if (firstDBIN == null) {
252                 firstDBIN = (DBIN)in;
253             }
254
255             for (int k = 0; k < in.getNEntries(); k++) {
256                 Node n = in.fetchTarget(k);
257                 LN ln = (LN) n;
258                 checkMatch(tree, ln, (BIN)in, dupKey,
259                            ln.getData(),
260                            k, in.getLsn(k));
261             }
262         }
263     }
264             
265     /*
266      * Do a parent search, expect to find the parent, check that we do.
267      */
268     private void checkMatch(Tree tree,
269                             IN target,
270                             IN parent,
271                             int index,
272                             boolean requireExactMatch)
273         throws DatabaseException {
274
275         target.latch();
276         SearchResult result = tree.getParentINForChildIN
277             (target, requireExactMatch, true);
278         assertTrue(result.exactParentFound);
279         assertEquals("Target=" + target + " parent=" + parent,
280                      index, result.index);
281         assertEquals(parent, result.parent);
282         parent.releaseLatch();
283     }
284
285     /*
286      * Search for the BIN for this LN.
287      */
288     private void checkMatch(Tree tree,
289                 LN target,
290                 BIN parent,
291                 byte[] mainKey,
292                             byte[] dupKey,
293                 int index,
294                 long expectedLsn)
295         throws DatabaseException {
296         TreeLocation location = new TreeLocation();
297
298         
299         assertTrue
300         (tree.getParentBINForChildLN(location, mainKey, dupKey, target,
301                      false, true, false, true));
302         location.bin.releaseLatch();
303         assertEquals(parent, location.bin);
304         assertEquals(index, location.index);
305         assertEquals(expectedLsn, location.childLsn);
306
307         assertTrue
308         (tree.getParentBINForChildLN(location, mainKey, dupKey, target,
309                      true, false, true, true));
310         location.bin.releaseLatch();
311         assertEquals(parent, location.bin);
312         assertEquals(index, location.index);
313         assertEquals(expectedLsn, location.childLsn);
314
315         assertTrue
316         (tree.getParentBINForChildLN(location, mainKey, dupKey, target,
317                      true, true, false, true));
318         location.bin.releaseLatch();
319         assertEquals(parent, location.bin);
320         assertEquals(index, location.index);
321         assertEquals(expectedLsn, location.childLsn);
322     }
323
324     private class GetRoot implements WithRootLatched {
325
326         private DatabaseImpl db;
327         
328         GetRoot(DatabaseImpl db) {
329         this.db = db;
330         }
331
332         public IN doWork(ChildReference root)
333             throws DatabaseException {
334
335             return (IN) root.fetchTarget(db, null);
336         }
337     }
338
339     /**
340      * Make up non-existent nodes and see where they'd fit in. This exercises
341      * recovery type processing and cleaning.
342      */
343     private void checkTreeUsingPotentialNodes()
344         throws DatabaseException {
345
346         DatabaseImpl database = DbInternal.dbGetDatabaseImpl(db);
347         Tree tree = database.getTree();
348
349         /*
350          * Make an IN with the key "ab". Its potential parent should be the
351          * first level 2 IN.
352          */
353         IN inAB = new IN(database, "ab".getBytes(), 4, 2);
354         checkPotential(tree, inAB, firstLevel2IN);
355
356         /*
357          * Make an BIN with the key "x". Its potential parent should be the
358          * first level 2 IN.
359          */
360         BIN binAB =
361         new BIN(database, "ab".getBytes(), 4, 1);
362         checkPotential(tree, binAB, firstLevel2IN);
363
364         /*
365          * Make a DIN with the key "a". Its potential parent should be BIN(c).
366          */
367         DIN dinA = new DIN(database,
368                            "data1".getBytes(),
369                            4,
370                            "a".getBytes(),
371                            null, 3);
372         checkPotential(tree, dinA, firstBIN);
373
374         /*
375          * Make an LN with the key "ab". It's potential parent should be the
376          * BINa.
377          */
378         LN LNab = new LN("foo".getBytes());
379         byte[] mainKey = "ab".getBytes();
380         checkPotential(tree, LNab, firstBIN, mainKey,
381                        LNab.getData(), mainKey);
382
383         /**
384          * Make a dup LN with the key b. Its potential parent should be DBINb.
385          */
386         LN LNdata = new LN("data".getBytes());
387         mainKey = "b".getBytes();
388         byte[] dupKey = LNdata.getData();
389         checkPotential(tree, LNdata, firstDBIN, mainKey, dupKey, dupKey);
390     }
391
392     private void checkPotential(Tree tree, IN potential, IN expectedParent)
393         throws DatabaseException {
394
395         /* Try an exact match, expect a failure, then try an inexact match. */
396         potential.latch();
397         SearchResult result = tree.getParentINForChildIN
398             (potential, true, true);
399         assertFalse(result.exactParentFound);
400         assertTrue(result.parent == null);
401
402         potential.latch();
403         result = tree.getParentINForChildIN(potential, false, true);
404         assertFalse(result.exactParentFound);
405         assertEquals("expected = " + expectedParent.getNodeId() +
406                      " got" + result.parent.getNodeId(),
407                      expectedParent, result.parent);
408         result.parent.releaseLatch();
409     }
410
411     private void checkPotential(Tree tree, LN potential, BIN expectedParent,
412                                 byte[] mainKey, byte[] dupKey, byte[] expectedKey)
413         throws DatabaseException {
414
415         /* Try an exact match, expect a failure, then try an inexact match. */
416         TreeLocation location = new TreeLocation();
417         assertFalse(tree.getParentBINForChildLN(location,
418                         mainKey, dupKey,
419                         potential, false,
420                         false, true, true));
421         location.bin.releaseLatch();
422         assertEquals(location.bin, expectedParent);
423         assertEquals(expectedKey, location.lnKey);
424     }
425
426     private void checkTreeWithDeletedBins(boolean requireExactMatch)
427         throws DatabaseException {
428
429     /**
430      * Mark all refs from the IN's to the BIN's as "known deleted". Start
431      * at the root.
432      */
433         DatabaseImpl database = DbInternal.dbGetDatabaseImpl(db);
434         Tree tree = database.getTree();
435
436         rootIN = tree.withRootLatchedShared
437         (new GetRoot(DbInternal.dbGetDatabaseImpl(db)));
438    
439         /* Second and third level. */
440         for (int i = 0; i < rootIN.getNEntries(); i++) {
441             /* Each level 2 IN. */
442             IN in = (IN) rootIN.fetchTarget(i);
443             for (int j = 0; j < in.getNEntries(); j++) {
444                 BIN bin = (BIN) in.getTarget(j);
445         in.setKnownDeleted(j);
446         checkDeletedMatch(tree, bin, in, j, requireExactMatch);
447             }
448     }
449     }
450
451     /*
452      * Do a parent search, expect to find the parent, check that we do.
453      */
454     private void checkDeletedMatch(Tree tree,
455                    IN target,
456                    IN parent,
457                    int index,
458                    boolean requireExactMatch)
459         throws DatabaseException {
460
461         target.latch();
462         SearchResult result = tree.getParentINForChildIN
463             (target, requireExactMatch, true);
464         assertFalse(result.exactParentFound);
465         assertEquals("Target=" + target + " parent=" + parent,
466                      index, result.index);
467     if (requireExactMatch) {
468         assertEquals(null, result.parent);
469     } else {
470         assertEquals(parent, result.parent);
471         parent.releaseLatch();
472     }
473     }
474 }
475
Popular Tags