KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 2002,2006 Oracle. All rights reserved.
5  *
6  * $Id: INTest.java,v 1.59 2006/10/30 21:14:51 bostic Exp $
7  */
8
9 package com.sleepycat.je.tree;
10
11 import java.io.File JavaDoc;
12 import java.util.Random JavaDoc;
13
14 import junit.framework.TestCase;
15
16 import com.sleepycat.je.DatabaseConfig;
17 import com.sleepycat.je.DatabaseException;
18 import com.sleepycat.je.EnvironmentConfig;
19 import com.sleepycat.je.config.EnvironmentParams;
20 import com.sleepycat.je.dbi.DatabaseId;
21 import com.sleepycat.je.dbi.DatabaseImpl;
22 import com.sleepycat.je.dbi.EnvironmentImpl;
23 import com.sleepycat.je.util.TestUtils;
24 import com.sleepycat.je.utilint.DbLsn;
25
26 public class INTest extends TestCase {
27     static private final int N_BYTES_IN_KEY = 3;
28     private int initialINCapacity;
29     private DatabaseImpl db = null;
30     static private long FAKE_LSN = DbLsn.makeLsn(0, 0);
31     private EnvironmentImpl noLogEnv;
32     private File JavaDoc envHome;
33
34     public INTest()
35     throws DatabaseException {
36
37         envHome = new File JavaDoc(System.getProperty(TestUtils.DEST_DIR));
38     }
39
40     public void setUp()
41     throws DatabaseException {
42
43         EnvironmentConfig envConfig = TestUtils.initEnvConfig();
44         envConfig.setConfigParam(EnvironmentParams.NODE_MAX.getName(), "6");
45         envConfig.setAllowCreate(true);
46         noLogEnv = new EnvironmentImpl(envHome, envConfig);
47     initialINCapacity =
48         noLogEnv.getConfigManager().getInt(EnvironmentParams.NODE_MAX);
49         db = new DatabaseImpl("foo", new DatabaseId(11), noLogEnv,
50                   new DatabaseConfig());
51     }
52
53     public void tearDown()
54     throws DatabaseException {
55
56     noLogEnv.close();
57     }
58
59     public void testFindEntry()
60     throws DatabaseException {
61
62     IN in = new IN(db, new byte[0], initialINCapacity, 7);
63     in.latch();
64
65     byte[] zeroBytes = new byte[N_BYTES_IN_KEY];
66     for (int i = 0; i < N_BYTES_IN_KEY; i++) {
67         zeroBytes[i] = 0x00;
68     }
69
70     byte[] maxBytes = new byte[N_BYTES_IN_KEY];
71     for (int i = 0; i < N_BYTES_IN_KEY; i++) {
72         /* Use FF since that sets the sign bit negative on a byte.
73            This checks the Key.compareTo routine for proper unsigned
74            comparisons. */
75         maxBytes[i] = (byte) 0xFF;
76     }
77
78     assertTrue(in.findEntry(zeroBytes, false, false) == -1);
79     assertTrue(in.findEntry(maxBytes, false, false) == -1);
80     assertTrue(in.findEntry(zeroBytes, false, true) == -1);
81     assertTrue(in.findEntry(maxBytes, false, true) == -1);
82     assertTrue(in.findEntry(zeroBytes, true, false) == -1);
83     assertTrue(in.findEntry(maxBytes, true, false) == -1);
84     assertTrue(in.findEntry(zeroBytes, true, true) == -1);
85     assertTrue(in.findEntry(maxBytes, true, true) == -1);
86     for (int i = 0; i < initialINCapacity; i++) {
87         /* Insert a key and check that we get the same index
88            in return from the binary search. Check the next
89            highest and next lowest keys also. */
90         byte[] keyBytes = new byte[N_BYTES_IN_KEY];
91         byte[] nextKeyBytes = new byte[N_BYTES_IN_KEY];
92         byte[] prevKeyBytes = new byte[N_BYTES_IN_KEY];
93         nextKeyBytes[0] = prevKeyBytes[0] = keyBytes[0] = 0x01;
94         nextKeyBytes[1] = prevKeyBytes[1] = keyBytes[1] = (byte) i;
95         nextKeyBytes[2] = prevKeyBytes[2] = keyBytes[2] = 0x10;
96         nextKeyBytes[2]++;
97         prevKeyBytes[2]--;
98         in.setEntry(i, null, keyBytes, FAKE_LSN, (byte) 0);
99         assertTrue(in.findEntry(zeroBytes, false, false) == 0);
100         assertTrue(in.findEntry(maxBytes, false, false) == i);
101         assertTrue(in.findEntry(zeroBytes, false, true) == -1);
102         assertTrue(in.findEntry(maxBytes, false, true) == -1);
103         assertTrue(in.findEntry(zeroBytes, true, false) == -1);
104         assertTrue(in.findEntry(maxBytes, true, false) == i);
105         assertTrue(in.findEntry(zeroBytes, true, true) == -1);
106         assertTrue(in.findEntry(maxBytes, true, true) == -1);
107         for (int j = 1; j < in.getNEntries(); j++) { // 0th key is virtual
108 assertTrue(in.findEntry(in.getKey(j), false, false)
109                == j);
110         assertTrue(in.findEntry(in.getKey(j), false, true)
111                == j);
112         assertTrue(in.findEntry(in.getKey(j), true, false) ==
113                (j | IN.EXACT_MATCH));
114         assertTrue(in.findEntry(in.getKey(j), true, true) ==
115                (j | IN.EXACT_MATCH));
116         assertTrue(in.findEntry(nextKeyBytes, false, false) == i);
117         assertTrue(in.findEntry(prevKeyBytes, false, false) == i - 1);
118         assertTrue(in.findEntry(nextKeyBytes, false, true) == -1);
119         assertTrue(in.findEntry(prevKeyBytes, false, true) == -1);
120         }
121     }
122     in.releaseLatch();
123     }
124
125     public void testInsertEntry()
126     throws DatabaseException {
127
128     for (int i = 0; i < 10; i++) { // cwl: consider upping this
129 doInsertEntry(false);
130         doInsertEntry(true);
131     }
132     }
133
134     private void doInsertEntry(boolean withMinMax)
135     throws DatabaseException {
136
137     IN in = new IN(db, new byte[0], initialINCapacity, 7);
138     in.latch();
139
140     byte[] zeroBytes = new byte[N_BYTES_IN_KEY];
141     for (int i = 0; i < N_BYTES_IN_KEY; i++) {
142         zeroBytes[i] = 0x00;
143     }
144
145     byte[] maxBytes = new byte[N_BYTES_IN_KEY];
146     for (int i = 0; i < N_BYTES_IN_KEY; i++) {
147         maxBytes[i] = (byte) 0xFF;
148     }
149
150     if (withMinMax) {
151         try {
152         in.insertEntry(new ChildReference(null, zeroBytes, FAKE_LSN));
153         in.verify(null);
154         in.insertEntry(new ChildReference(null, maxBytes, FAKE_LSN));
155         in.verify(null);
156         } catch (InconsistentNodeException INE) {
157         fail("caught InconsistentNodeException");
158         }
159
160         assertTrue(in.findEntry(zeroBytes, false, false) == 0);
161         assertTrue(in.findEntry(maxBytes, false, false) == 1);
162         /* shadowed by the virtual 0'th key */
163         assertTrue(in.findEntry(zeroBytes, false, true) == 0);
164         assertTrue(in.findEntry(maxBytes, false, true) == 1);
165
166         assertTrue(in.findEntry(zeroBytes, true, false) == IN.EXACT_MATCH);
167         assertTrue(in.findEntry(maxBytes, true, false) ==
168                (1 | IN.EXACT_MATCH));
169         /* shadowed by the virtual 0'th key */
170         assertTrue(in.findEntry(zeroBytes, true, true) == IN.EXACT_MATCH);
171         assertTrue(in.findEntry(maxBytes, true, true) ==
172                (1 | IN.EXACT_MATCH));
173     }
174
175     Random JavaDoc rnd = new Random JavaDoc();
176
177     try {
178         for (int i = 0;
179          i < initialINCapacity - (withMinMax ? 2 : 0);
180          i++) {
181         /* Insert a key and check that we get the same index
182            in return from the binary search. Check the next
183            highest and next lowest keys also. */
184         byte[] keyBytes = new byte[N_BYTES_IN_KEY];
185
186         /* There's a small chance that we may generate the
187            same sequence of bytes that are already present. */
188         while (true) {
189             rnd.nextBytes(keyBytes);
190             int index = in.findEntry(keyBytes, true, false);
191             if ((index & IN.EXACT_MATCH) != 0 &&
192             index >= 0) {
193             continue;
194             }
195             break;
196         }
197
198         in.insertEntry(new ChildReference(null, keyBytes, FAKE_LSN));
199         try {
200             in.verify(null);
201         } catch (InconsistentNodeException INE) {
202             Key.DUMP_BINARY = true;
203             in.dump(0);
204         }
205
206         if (withMinMax) {
207             assertTrue(in.findEntry(zeroBytes, false, false) == 0);
208             assertTrue(in.findEntry(maxBytes, false, false) ==
209                    in.getNEntries() - 1);
210             /* shadowed by the virtual 0'th key */
211             assertTrue(in.findEntry(zeroBytes, false, true) == 0);
212             assertTrue(in.findEntry(maxBytes, false, true) ==
213                    in.getNEntries() - 1);
214
215             assertTrue(in.findEntry(zeroBytes, true, false) ==
216                    IN.EXACT_MATCH);
217             assertTrue(in.findEntry(maxBytes, true, false) ==
218                    ((in.getNEntries() - 1) | IN.EXACT_MATCH));
219             /* shadowed by the virtual 0'th key */
220             assertTrue(in.findEntry(zeroBytes, true, true) ==
221                    IN.EXACT_MATCH);
222             assertTrue(in.findEntry(maxBytes, true, true) ==
223                    ((in.getNEntries() - 1) | IN.EXACT_MATCH));
224         } else {
225             assertTrue(in.findEntry(zeroBytes, false, false) == 0);
226             assertTrue(in.findEntry(maxBytes, false, false) ==
227                    in.getNEntries() - 1);
228             assertTrue(in.findEntry(zeroBytes, false, true) == -1);
229             assertTrue(in.findEntry(maxBytes, false, true) == -1);
230
231             assertTrue(in.findEntry(zeroBytes, true, false) == -1);
232             assertTrue(in.findEntry(maxBytes, true, false) ==
233                    in.getNEntries() - 1);
234         }
235
236         for (int j = 1; j < in.getNEntries(); j++) {
237             assertTrue(in.findEntry(in.getKey(j), false, false) == j);
238             assertTrue(in.findEntry(in.getKey(j), false, true) == j);
239
240             assertTrue(in.findEntry(in.getKey(j), false, true) == j);
241             assertTrue(in.findEntry(in.getKey(j), true, false) ==
242                    (j | IN.EXACT_MATCH));
243         }
244         }
245     } catch (InconsistentNodeException INE) {
246         fail("caught InconsistentNodeException");
247     }
248
249     /* Should be full so insertEntry should return false */
250     byte[] keyBytes = new byte[N_BYTES_IN_KEY];
251     rnd.nextBytes(keyBytes);
252
253     try {
254         in.insertEntry(new ChildReference(null, keyBytes, FAKE_LSN));
255         fail("should have caught InconsistentNodeException, but didn't");
256     } catch (InconsistentNodeException INE) {
257     }
258     in.releaseLatch();
259     }
260
261     public void testDeleteEntry()
262     throws DatabaseException {
263
264     for (int i = 0; i < 10; i++) { // cwl: consider upping this
265 doDeleteEntry(true);
266         doDeleteEntry(false);
267     }
268     }
269
270     private void doDeleteEntry(boolean withMinMax)
271     throws DatabaseException {
272
273     IN in = new IN(db, new byte[0], initialINCapacity, 7);
274     in.latch();
275
276     byte[] zeroBytes = new byte[N_BYTES_IN_KEY];
277     for (int i = 0; i < N_BYTES_IN_KEY; i++) {
278         zeroBytes[i] = 0x00;
279     }
280
281     byte[] maxBytes = new byte[N_BYTES_IN_KEY];
282     for (int i = 0; i < N_BYTES_IN_KEY; i++) {
283         maxBytes[i] = (byte) 0xFF;
284     }
285
286     if (withMinMax) {
287         try {
288         in.insertEntry(new ChildReference(null, zeroBytes, FAKE_LSN));
289         in.verify(null);
290         in.insertEntry(new ChildReference(null, maxBytes, FAKE_LSN));
291         in.verify(null);
292         } catch (InconsistentNodeException INE) {
293         fail("caught InconsistentNodeException");
294         }
295
296         assertTrue(in.findEntry(zeroBytes, false, false) == 0);
297         assertTrue(in.findEntry(maxBytes, false, false) == 1);
298         /* shadowed by the virtual 0'th key */
299         assertTrue(in.findEntry(zeroBytes, false, true) == 0);
300         assertTrue(in.findEntry(maxBytes, false, true) == 1);
301
302         assertTrue(in.findEntry(zeroBytes, true, false) == IN.EXACT_MATCH);
303         assertTrue(in.findEntry(maxBytes, true, false) ==
304                (1 | IN.EXACT_MATCH));
305         /* shadowed by the virtual 0'th key */
306         assertTrue(in.findEntry(zeroBytes, true, true) == IN.EXACT_MATCH);
307         assertTrue(in.findEntry(maxBytes, true, true) ==
308                (1 | IN.EXACT_MATCH));
309     }
310
311     Random JavaDoc rnd = new Random JavaDoc();
312
313     try {
314         /* Fill up the IN with random entries. */
315         for (int i = 0;
316          i < initialINCapacity - (withMinMax ? 2 : 0);
317          i++) {
318         /* Insert a key and check that we get the same index
319            in return from the binary search. Check the next
320            highest and next lowest keys also. */
321         byte[] keyBytes = new byte[N_BYTES_IN_KEY];
322
323         /* There's a small chance that we may generate the
324            same sequence of bytes that are already present. */
325         while (true) {
326             rnd.nextBytes(keyBytes);
327             int index = in.findEntry(keyBytes, true, false);
328             if ((index & IN.EXACT_MATCH) != 0 &&
329             index >= 0) {
330             continue;
331             }
332             break;
333         }
334
335         in.insertEntry(new ChildReference(null, keyBytes, FAKE_LSN));
336         }
337
338         if (withMinMax) {
339         assertTrue(in.findEntry(zeroBytes, false, false) == 0);
340         assertTrue(in.findEntry(maxBytes, false, false) ==
341                in.getNEntries() - 1);
342         /* zeroBytes is in the 0th entry, but that's the
343            virtual key so it's not an exact match. */
344         assertTrue(in.findEntry(zeroBytes, false, true) == 0);
345         assertTrue(in.findEntry(maxBytes, false, true) ==
346                in.getNEntries() - 1);
347
348         assertTrue(in.findEntry(zeroBytes, false, true) == 0);
349         assertTrue(in.findEntry(maxBytes, false, true) ==
350                in.getNEntries() - 1);
351         assertTrue(in.findEntry(zeroBytes, true, false) == IN.EXACT_MATCH);
352         assertTrue(in.findEntry(maxBytes, true, false) ==
353                ((in.getNEntries() - 1) | IN.EXACT_MATCH));
354         }
355
356         while (in.getNEntries() > 1) {
357         int i = rnd.nextInt(in.getNEntries() - 1) + 1;
358         assertTrue(in.deleteEntry(in.getKey(i), false));
359         }
360
361         /*
362          * We should only be able to delete the zero Key if it was inserted
363          * in the first place.
364          */
365         assertEquals(withMinMax, in.deleteEntry(zeroBytes, false));
366     } catch (InconsistentNodeException INE) {
367         fail("caught InconsistentNodeException");
368     }
369     in.releaseLatch();
370     }
371 }
372
Popular Tags