1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.directory.mavibot.btree.memory;
21
22
23 import static org.junit.Assert.assertEquals;
24 import static org.junit.Assert.assertTrue;
25 import static org.junit.Assert.fail;
26
27 import java.io.IOException;
28
29 import org.apache.directory.mavibot.btree.BorrowedFromLeftResult;
30 import org.apache.directory.mavibot.btree.BorrowedFromRightResult;
31 import org.apache.directory.mavibot.btree.DeleteResult;
32 import org.apache.directory.mavibot.btree.InsertResult;
33 import org.apache.directory.mavibot.btree.NotPresentResult;
34 import org.apache.directory.mavibot.btree.Page;
35 import org.apache.directory.mavibot.btree.RemoveResult;
36 import org.apache.directory.mavibot.btree.Tuple;
37 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
38 import org.apache.directory.mavibot.btree.serializer.LongSerializer;
39 import org.apache.directory.mavibot.btree.serializer.StringSerializer;
40 import org.junit.After;
41 import org.junit.Before;
42 import org.junit.Test;
43
44
45
46
47
48
49
50 public class LeafTest
51 {
52 private BTree<Long, String> btree = null;
53
54
55
56
57
58 @Before
59 public void setup() throws IOException
60 {
61 btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
62 btree.setPageSize( 8 );
63 }
64
65
66 @After
67 public void shutdown() throws IOException
68 {
69 btree.close();
70 }
71
72
73
74
75
76
77 private Leaf<Long, String> insert( Leaf<Long, String> leaf, long key, String value ) throws IOException
78 {
79 InsertResult<Long, String> result = leaf.insert( 1L, key, value );
80
81 return ( Leaf<Long, String> ) ( (org.apache.directory.mavibot.btree.ModifyResult<Long, String> ) result ).getModifiedPage();
82 }
83
84
85
86
87
88
89 @Test
90 public void testDeleteFromEmptyLeaf() throws IOException
91 {
92 Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
93
94 DeleteResult<Long, String> result = leaf.delete( 1L, 1L, null, null, -1 );
95
96 assertEquals( NotPresentResult.NOT_PRESENT, result );
97 }
98
99
100
101
102
103
104 @Test
105 public void testDeleteNotPresentElementFromRootLeaf() throws IOException
106 {
107 Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
108 leaf = insert( leaf, 1L, "v1" );
109 leaf = insert( leaf, 2L, "v2" );
110 leaf = insert( leaf, 3L, "v3" );
111 leaf = insert( leaf, 4L, "v4" );
112
113 DeleteResult<Long, String> result = leaf.delete( 2L, 5L, null, null, -1 );
114
115 assertEquals( NotPresentResult.NOT_PRESENT, result );
116 }
117
118
119
120
121
122
123 @Test
124 public void testDeletePresentElementFromRootLeaf() throws IOException
125 {
126 Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
127 leaf = insert( leaf, 1L, "v1" );
128 leaf = insert( leaf, 2L, "v2" );
129 leaf = insert( leaf, 3L, "v3" );
130 leaf = insert( leaf, 4L, "v4" );
131
132 DeleteResult<Long, String> result = leaf.delete( 4L, 3L, null, null, -1 );
133
134 assertTrue( result instanceof RemoveResult );
135
136 Tuple<Long, String> removedElement = ( (org.apache.directory.mavibot.btree.RemoveResult<Long, String> ) result ).getRemovedElement();
137 Page<Long, String> newLeaf = ( (org.apache.directory.mavibot.btree.RemoveResult<Long, String> ) result ).getModifiedPage();
138
139 assertEquals( Long.valueOf( 3L ), removedElement.getKey() );
140 assertEquals( "v3", removedElement.getValue() );
141 assertEquals( 3, newLeaf.getNbElems() );
142
143 try
144 {
145 assertEquals( "v1", newLeaf.get( 1L ) );
146 assertEquals( "v2", newLeaf.get( 2L ) );
147 assertEquals( "v4", newLeaf.get( 4L ) );
148 }
149 catch ( KeyNotFoundException knfe )
150 {
151 fail();
152 }
153
154 try
155 {
156 newLeaf.get( 3L );
157 fail();
158 }
159 catch ( KeyNotFoundException knfe )
160 {
161
162 }
163 }
164
165
166
167
168
169
170 @Test
171 public void testDeleteFirstElementFromRootLeaf() throws IOException
172 {
173 Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
174 leaf = insert( leaf, 1L, "v1" );
175 leaf = insert( leaf, 2L, "v2" );
176 leaf = insert( leaf, 3L, "v3" );
177 leaf = insert( leaf, 4L, "v4" );
178
179 DeleteResult<Long, String> result = leaf.delete( 4L, 1L, null, null, -1 );
180
181 assertTrue( result instanceof RemoveResult );
182
183 RemoveResult<Long, String> removeResult = (org.apache.directory.mavibot.btree.RemoveResult<Long, String> ) result;
184
185 Tuple<Long, String> removedElement = removeResult.getRemovedElement();
186 Page<Long, String> newLeaf = removeResult.getModifiedPage();
187
188 assertEquals( Long.valueOf( 1L ), removedElement.getKey() );
189 assertEquals( "v1", removedElement.getValue() );
190 assertEquals( 3, newLeaf.getNbElems() );
191
192 try
193 {
194 newLeaf.get( 1L );
195 fail();
196 }
197 catch ( KeyNotFoundException knfe )
198 {
199
200 }
201
202 try
203 {
204 assertEquals( "v2", newLeaf.get( 2L ) );
205 assertEquals( "v3", newLeaf.get( 3L ) );
206 assertEquals( "v4", newLeaf.get( 4L ) );
207 }
208 catch ( KeyNotFoundException knfe )
209 {
210 fail();
211 }
212 }
213
214
215
216
217
218
219
220
221
222
223
224 @Test
225 public void testDeleteBorrowingFromLeftSibling() throws IOException
226 {
227 Node<Long, String> parent = new Node<Long, String>( btree, 1L, 2 );
228 Leaf<Long, String> left = new Leaf<Long, String>( btree );
229 Leaf<Long, String> target = new Leaf<Long, String>( btree );
230 Leaf<Long, String> right = new Leaf<Long, String>( btree );
231
232
233 left = insert( left, 1L, "v1" );
234 left = insert( left, 2L, "v2" );
235 left = insert( left, 3L, "v3" );
236 left = insert( left, 4L, "v4" );
237 left = insert( left, 5L, "v5" );
238
239
240 target = insert( target, 6L, "v6" );
241 target = insert( target, 7L, "v7" );
242 target = insert( target, 8L, "v8" );
243 target = insert( target, 9L, "v9" );
244
245
246 right = insert( right, 10L, "v10" );
247 right = insert( right, 11L, "v11" );
248 right = insert( right, 12L, "v12" );
249 right = insert( right, 13L, "v13" );
250
251 parent.children[0] = left;
252 parent.children[1] = target;
253 parent.children[2] = right;
254
255
256 parent.keys[0] = 6L;
257 parent.keys[1] = 10L;
258
259
260 DeleteResult<Long, String> result = target.delete( 2L, 7L, null, parent, 1 );
261
262 assertTrue( result instanceof BorrowedFromLeftResult );
263
264 BorrowedFromLeftResult<Long, String> borrowed = (org.apache.directory.mavibot.btree.BorrowedFromLeftResult<Long, String> ) result;
265 Tuple<Long, String> removedKey = borrowed.getRemovedElement();
266
267 assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
268
269
270 Leaf<Long, String> newLeaf = ( Leaf<Long, String> ) borrowed.getModifiedPage();
271
272 assertEquals( 4, newLeaf.nbElems );
273 assertEquals( Long.valueOf( 5L ), newLeaf.keys[0] );
274 assertEquals( Long.valueOf( 6L ), newLeaf.keys[1] );
275 assertEquals( Long.valueOf( 8L ), newLeaf.keys[2] );
276 assertEquals( Long.valueOf( 9L ), newLeaf.keys[3] );
277
278
279 Leaf<Long, String> leftSibling = ( Leaf<Long, String> ) borrowed.getModifiedSibling();
280
281 assertEquals( 4, leftSibling.nbElems );
282 assertEquals( Long.valueOf( 1L ), leftSibling.keys[0] );
283 assertEquals( Long.valueOf( 2L ), leftSibling.keys[1] );
284 assertEquals( Long.valueOf( 3L ), leftSibling.keys[2] );
285 assertEquals( Long.valueOf( 4L ), leftSibling.keys[3] );
286 }
287
288
289
290
291
292
293
294 @Test
295 public void testDeleteBorrowingFromRightSibling() throws IOException
296 {
297 Node<Long, String> parent = new Node<Long, String>( btree, 1L, 2 );
298 Leaf<Long, String> left = new Leaf<Long, String>( btree );
299 Leaf<Long, String> target = new Leaf<Long, String>( btree );
300 Leaf<Long, String> right = new Leaf<Long, String>( btree );
301
302
303 left = insert( left, 1L, "v1" );
304 left = insert( left, 2L, "v2" );
305 left = insert( left, 3L, "v3" );
306 left = insert( left, 4L, "v4" );
307
308
309 target = insert( target, 6L, "v6" );
310 target = insert( target, 7L, "v7" );
311 target = insert( target, 8L, "v8" );
312 target = insert( target, 9L, "v9" );
313
314
315 right = insert( right, 10L, "v10" );
316 right = insert( right, 11L, "v11" );
317 right = insert( right, 12L, "v12" );
318 right = insert( right, 13L, "v13" );
319 right = insert( right, 14L, "v14" );
320
321 parent.children[0] = left;
322 parent.children[1] = target;
323 parent.children[2] = right;
324
325
326 parent.keys[0] = 6L;
327 parent.keys[1] = 10L;
328
329
330 DeleteResult<Long, String> result = target.delete( 2L, 7L, null, parent, 1 );
331
332 assertTrue( result instanceof BorrowedFromRightResult );
333
334 BorrowedFromRightResult<Long, String> borrowed = (org.apache.directory.mavibot.btree.BorrowedFromRightResult<Long, String> ) result;
335 assertEquals( Long.valueOf( 11L ), borrowed.getModifiedSibling().getKey( 0 ) );
336 Tuple<Long, String> removedKey = borrowed.getRemovedElement();
337
338 assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
339
340
341 Leaf<Long, String> newLeaf = ( Leaf<Long, String> ) borrowed.getModifiedPage();
342
343 assertEquals( 4, newLeaf.nbElems );
344 assertEquals( Long.valueOf( 6L ), newLeaf.keys[0] );
345 assertEquals( Long.valueOf( 8L ), newLeaf.keys[1] );
346 assertEquals( Long.valueOf( 9L ), newLeaf.keys[2] );
347 assertEquals( Long.valueOf( 10L ), newLeaf.keys[3] );
348
349
350 Leaf<Long, String> rightSibling = ( Leaf<Long, String> ) borrowed.getModifiedSibling();
351
352 assertEquals( 4, rightSibling.nbElems );
353 assertEquals( Long.valueOf( 11L ), rightSibling.keys[0] );
354 assertEquals( Long.valueOf( 12L ), rightSibling.keys[1] );
355 assertEquals( Long.valueOf( 13L ), rightSibling.keys[2] );
356 assertEquals( Long.valueOf( 14L ), rightSibling.keys[3] );
357 }
358
359
360
361
362
363
364
365 @Test
366 public void testDeleteMergeWithSibling() throws IOException
367 {
368 Node<Long, String> parent = new Node<Long, String>( btree, 1L, 2 );
369 Leaf<Long, String> left = new Leaf<Long, String>( btree );
370 Leaf<Long, String> target = new Leaf<Long, String>( btree );
371 Leaf<Long, String> right = new Leaf<Long, String>( btree );
372
373
374 left = insert( left, 1L, "v1" );
375 left = insert( left, 2L, "v2" );
376 left = insert( left, 3L, "v3" );
377 left = insert( left, 4L, "v4" );
378
379
380 target = insert( target, 5L, "v5" );
381 target = insert( target, 6L, "v6" );
382 target = insert( target, 7L, "v7" );
383 target = insert( target, 8L, "v8" );
384
385
386 right = insert( right, 9L, "v9" );
387 right = insert( right, 10L, "v10" );
388 right = insert( right, 11L, "v11" );
389 right = insert( right, 12L, "v12" );
390
391 parent.children[0] = left;
392 parent.children[1] = target;
393 parent.children[2] = right;
394
395
396 parent.keys[0] = 5L;
397 parent.keys[1] = 9L;
398
399
400 DeleteResult<Long, String> result = target.delete( 2L, 7L, null, parent, 1 );
401
402 assertTrue( result instanceof MergedWithSiblingResult );
403
404 MergedWithSiblingResult<Long, String> merged = ( MergedWithSiblingResult<Long, String> ) result;
405 Tuple<Long, String> removedKey = merged.getRemovedElement();
406
407 assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
408
409
410 Leaf<Long, String> newLeaf = ( Leaf<Long, String> ) merged.getModifiedPage();
411
412 assertEquals( 7, newLeaf.nbElems );
413 assertEquals( Long.valueOf( 1L ), newLeaf.keys[0] );
414 assertEquals( Long.valueOf( 2L ), newLeaf.keys[1] );
415 assertEquals( Long.valueOf( 3L ), newLeaf.keys[2] );
416 assertEquals( Long.valueOf( 4L ), newLeaf.keys[3] );
417 assertEquals( Long.valueOf( 5L ), newLeaf.keys[4] );
418 assertEquals( Long.valueOf( 6L ), newLeaf.keys[5] );
419 assertEquals( Long.valueOf( 8L ), newLeaf.keys[6] );
420 }
421
422
423
424
425
426
427 @Test
428 public void testFindPos() throws Exception
429 {
430 Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
431
432
433 for ( long i = 0; i < 8; i++ )
434 {
435 long value = i + i + 1;
436 leaf = ( Leaf<Long, String> ) ( (org.apache.directory.mavibot.btree.ModifyResult<Long, String> ) leaf.insert( 0L, value, "V" + value ) )
437 .getModifiedPage();
438 }
439
440
441 for ( long i = 0; i < 17; i++ )
442 {
443 if ( i % 2 == 1 )
444 {
445 assertEquals( -( i / 2 + 1 ), leaf.findPos( i ) );
446 }
447 else
448 {
449 assertEquals( i / 2, leaf.findPos( i ) );
450 }
451 }
452 }
453 }