KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 2002,2006 Oracle. All rights reserved.
5  *
6  * $Id: SplitTest.java,v 1.23 2006/10/30 21:14:52 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.DatabaseEntry;
18 import com.sleepycat.je.DatabaseException;
19 import com.sleepycat.je.DbInternal;
20 import com.sleepycat.je.Environment;
21 import com.sleepycat.je.EnvironmentConfig;
22 import com.sleepycat.je.LockMode;
23 import com.sleepycat.je.OperationStatus;
24 import com.sleepycat.je.Transaction;
25 import com.sleepycat.je.config.EnvironmentParams;
26 import com.sleepycat.je.util.TestUtils;
27
28 public class SplitTest extends TestCase {
29     private static final boolean DEBUG = false;
30
31     private File JavaDoc envHome;
32     private Environment env;
33     private Database db;
34
35     public SplitTest() {
36         envHome = new File JavaDoc(System.getProperty(TestUtils.DEST_DIR));
37     }
38
39     public void setUp()
40         throws Exception JavaDoc {
41         TestUtils.removeLogFiles("Setup", envHome, false);
42         initEnv();
43     }
44
45     public void tearDown()
46         throws Exception JavaDoc {
47         try {
48             db.close();
49             env.close();
50         } catch (DatabaseException E) {
51         }
52                 
53         TestUtils.removeLogFiles("TearDown", envHome, true);
54     }
55
56     private void initEnv()
57         throws DatabaseException {
58
59         EnvironmentConfig envConfig = TestUtils.initEnvConfig();
60         envConfig.setConfigParam(EnvironmentParams.NODE_MAX.getName(), "4");
61         envConfig.setTransactional(true);
62         envConfig.setAllowCreate(true);
63         env = new Environment(envHome, envConfig);
64
65         String JavaDoc databaseName = "testDb";
66         Transaction txn = env.beginTransaction(null, null);
67         DatabaseConfig dbConfig = new DatabaseConfig();
68         dbConfig.setTransactional(true);
69         dbConfig.setAllowCreate(true);
70         db = env.openDatabase(txn, databaseName, dbConfig);
71         txn.commit();
72     }
73
74     /**
75      * Test splits on a case where the 0th entry gets promoted.
76      */

77     public void test0Split()
78         throws Exception JavaDoc {
79
80         Key.DUMP_BINARY = true;
81         try {
82             /* Build up a tree. */
83             for (int i = 160; i > 0; i-= 10) {
84                 assertEquals(OperationStatus.SUCCESS,
85                              db.put(null, new DatabaseEntry
86                  (new byte[] {(byte)i }),
87                                     new DatabaseEntry(new byte[] {1})));
88             }
89             if (DEBUG) {
90                 System.out.println("<dump>");
91                 DbInternal.dbGetDatabaseImpl(db).getTree().dump();
92             }
93             assertEquals(OperationStatus.SUCCESS,
94                          db.put(null, new DatabaseEntry(new byte[]{(byte)151}),
95                                 new DatabaseEntry(new byte[] {1})));
96             assertEquals(OperationStatus.SUCCESS,
97                          db.put(null, new DatabaseEntry(new byte[]{(byte)152}),
98                                 new DatabaseEntry(new byte[] {1})));
99             assertEquals(OperationStatus.SUCCESS,
100                          db.put(null, new DatabaseEntry(new byte[]{(byte)153}),
101                                 new DatabaseEntry(new byte[] {1})));
102
103             if (DEBUG) {
104                 DbInternal.dbGetDatabaseImpl(db).getTree().dump();
105                 System.out.println("</dump>");
106             }
107
108             /*
109              * These inserts make a tree where the right most mid-level IN
110              * has an idkey greater than its parent entry.
111              *
112              * +---------------+
113              * | id = 90 |
114              * | 50 | 90 | 130 |
115              * +---------------+
116              * | | |
117              * |
118              * +-----------------+
119              * | id = 160 |
120              * | 130 | 150 | 152 |
121              * +-----------------+
122              * | | |
123              * | | +-----------+
124              * | | |
125              * +-----------+ +-----------+ +-----------------+
126              * | BIN | | BIN | | BIN |
127              * | id = 130 | | id = 150 | | id=160 |
128              * | 130 | 140 | | 150 | 151 | | 152 | 153 | 160 |
129              * +-----------+ +-----------+ +-----------------+
130          *
131              * Now delete records 130 and 140 to empty out the subtree with BIN
132              * with id=130.
133              */

134             assertEquals(OperationStatus.SUCCESS,
135                          db.delete(null,
136                                    new DatabaseEntry(new byte[]{(byte) 130})));
137             assertEquals(OperationStatus.SUCCESS,
138                          db.delete(null,
139                                    new DatabaseEntry(new byte[]{(byte) 140})));
140             env.compress();
141
142             /*
143              * These deletes make the mid level IN's 0th entry > its parent
144              * reference.
145          *
146              * +---------------+
147              * | id = 90 |
148              * | 50 | 90 | 130 |
149              * +---------------+
150              * | | |
151              * |
152              * +-----------+
153              * | id = 160 |
154              * | 150 | 152 |
155              * +-----------+
156              * | |
157              * | |
158              * | |
159              * +-----------+ +-----------------+
160              * | BIN | | BIN |
161              * | id = 150 | | id=160 |
162              * | 150 | 151 | | 152 | 153 | 160 |
163              * +-----------+ +-----------------+
164              *
165              * Now insert 140 into BIN (id = 160) so that its first entry is
166              * less than the mid level IN.
167              */

168             assertEquals(OperationStatus.SUCCESS,
169                          db.put(null, new DatabaseEntry(new byte[]{(byte)140}),
170                                 new DatabaseEntry(new byte[] {1})));
171
172             /*
173              * Now note that the mid level tree's 0th entry is greater than its
174              * reference in the root.
175              *
176              * +---------------+
177              * | id = 90 |
178              * | 50 | 90 | 130 |
179              * +---------------+
180              * | | |
181              * |
182              * +-----------+
183              * | id = 160 |
184              * | 150 | 152 |
185              * +-----------+
186              * | |
187              * | |
188              * | |
189              * +----------------+ +-----------------+
190              * | BIN | | BIN |
191              * | id = 150 | | id=160 |
192              * | 140 |150 | 151 | | 152 | 153 | 160 |
193              * +----------------+ +-----------------+
194              *
195              * Now split the mid level node, putting the new child on the left.
196              */

197             for (int i = 154; i < 159; i++) {
198                 assertEquals(OperationStatus.SUCCESS,
199                              db.put(null,
200                                     new DatabaseEntry(new byte[]{(byte)i}),
201                                     new DatabaseEntry(new byte[] {1})));
202             }
203
204             /*
205              * This used to result in the following broken tree, which would
206              * cause us to not be able to retrieve record 140. With the new
207              * split code, entry "150" in the root should stay 130.
208          *
209              * +---------------------+
210              * | id = 90 |
211              * | 50 | 90 | 150 | 154 | NOTE: we'v lost record 140
212              * +---------------------+
213              * | | | \
214              * | \
215              * +-----------+ +----------+
216              * | id = 150 | |id=160 |
217              * | 150 | 152 | |154 | 156 |
218              * +-----------+ +----------+
219              * | |
220              * | |
221              * | |
222              * +------------+ +-------+
223              * | BIN | | BIN |
224              * | id = 150 | | id=152|
225              * | 140|150|151| |152|153|
226              * +------------+ +-------+
227              */

228             DatabaseEntry data = new DatabaseEntry();
229             assertEquals(OperationStatus.SUCCESS,
230                          db.get(null, new DatabaseEntry(new byte[]
231                  { (byte)140 }),
232                                 data, LockMode.DEFAULT));
233
234         } catch (Throwable JavaDoc t) {
235             t.printStackTrace();
236             throw new Exception JavaDoc(t);
237         }
238     }
239 }
240
Popular Tags