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