1   /*
2    *   Licensed to the Apache Software Foundation (ASF) under one
3    *   or more contributor license agreements.  See the NOTICE file
4    *   distributed with this work for additional information
5    *   regarding copyright ownership.  The ASF licenses this file
6    *   to you under the Apache License, Version 2.0 (the
7    *   "License"); you may not use this file except in compliance
8    *   with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *   Unless required by applicable law or agreed to in writing,
13   *   software distributed under the License is distributed on an
14   *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *   KIND, either express or implied.  See the License for the
16   *   specific language governing permissions and limitations
17   *   under the License.
18   *
19   */
20  package org.apache.directory.server.core.avltree;
21  
22   
23  import static org.junit.Assert.assertEquals;
24  import static org.junit.Assert.assertFalse;
25  import static org.junit.Assert.assertNotNull;
26  import static org.junit.Assert.assertTrue;
27  
28  import java.io.File;
29  import java.io.FileInputStream;
30  import java.io.FileNotFoundException;
31  import java.io.FileOutputStream;
32  import java.io.IOException;
33  import java.io.Serializable;
34  import java.util.Comparator;
35  
36  import org.junit.AfterClass;
37  import org.junit.Before;
38  import org.junit.Test;
39  import org.slf4j.Logger;
40  import org.slf4j.LoggerFactory;
41  
42  
43  /**
44   * TestCase for AvlTreeMarshaller.
45   *
46   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
47   * @version $Rev$, $Date$
48   */
49  public class AvlTreeMarshallerTest
50  {
51      private static final long[] AVLTREE_KEYS_PRE_REMOVE =
52      {
53          2, 14, 26, 86, 110, 122, 134, 182
54      };
55          
56      private static final long[] AVLTREE_EXPECTED_KEYS_POST_REMOVE =
57      {
58          2, 14, 26, 86, 122, 134, 182
59      };
60          
61      private static final byte[] SERIALIZED_AVLTREE_PRE_REMOVE =
62      {
63          0, 0, 0, 0, 8, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 
64          110, 0, 0, 0, 4, 0, 0, 0, 2, 0, 0, 0, 8, 0, 0, 0, 
65          0, 0, 0, 0, 26, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 
66          8, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 
67          0, 0, 0, 0, 4, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 
68          14, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
69          4, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 86, 0, 0, 0, 
70          3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 
71          8, 0, 0, 0, 0, 0, 0, 0, -122, 0, 0, 0, 6, 0, 0, 0, 
72          2, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 122, 0, 0, 0, 
73          5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 
74          8, 0, 0, 0, 0, 0, 0, 0, -74, 0, 0, 0, 7, 0, 0, 0, 
75          0, 0, 0, 0, 0 
76      };
77      
78  //    private static final byte[] SERIALIZED_AVLTREE_POST_REMOVE = 
79  //    { 
80  //        0, 0, 0, 0, 7, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 
81  //        86, 0, 0, 0, 3, 0, 0, 0, 2, 0, 0, 0, 8, 0, 0, 0, 
82  //        0, 0, 0, 0, 26, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 
83  //        0, 0, 0, 0, 4, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, -122, 
84  //        0, 0, 0, 5, 0, 0, 0, 2, 0, 0, 0, 8, 0, 0, 0, 0, 
85  //        0, 0, 0, 122, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 
86  //        0, 0, 0, 4, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, -74, 
87  //        0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0 
88  //    };
89  
90      AvlTree<Integer> tree;
91      Comparator<Integer> comparator;
92      AvlTreeMarshaller<Integer> treeMarshaller;
93      
94      static AvlTree<Integer> savedTree;
95      
96      static File treeFile = new File( System.getProperty( "java.io.tmpdir" ) + File.separator + "avl.tree");
97      
98      private static final Logger LOG = LoggerFactory.getLogger( AvlTreeMarshallerTest.class.getSimpleName() );
99  
100     
101     @Before
102     public void createTree()
103     {
104         comparator = new Comparator<Integer>() 
105         {
106             public int compare( Integer i1, Integer i2 )
107             {
108                 return i1.compareTo( i2 );
109             }
110         };
111         
112       
113         tree = new AvlTree<Integer>( comparator );
114         treeMarshaller = new AvlTreeMarshaller<Integer>( comparator, new IntegerKeyMarshaller() );
115     }
116 
117     
118     @AfterClass
119     public static void deleteFiles()
120     {
121         treeFile.delete();
122     }
123     
124     
125     @Test
126     public void testRemoveBug() throws IOException
127     {
128         Comparator<Long> comparator = new Comparator<Long>() 
129         {
130             public int compare( Long i1, Long i2 )
131             {
132                 return i1.compareTo( i2 );
133             }
134         };
135 
136         /*
137          * This deserializes the state of the AvlTree before the remove 
138          * operation and it should work checking to make sure that all
139          * the pre-remove keys are present.
140          */
141 
142         AvlTreeMarshaller<Long> treeMarshaller = new AvlTreeMarshaller<Long>( comparator, new LongMarshaller() );
143         AvlTree<Long> tree = treeMarshaller.deserialize( SERIALIZED_AVLTREE_PRE_REMOVE );
144         
145         for ( long key : AVLTREE_KEYS_PRE_REMOVE )
146         {
147             assertNotNull( "Should find " + key, tree.find( key ) );
148         }
149         
150         /*
151          * Now we remove the key 110 and this should show that we don't have 
152          * the expected keys.  We will be missing 134, 2 and 14.
153          */
154         
155         tree.remove( 110L );
156 
157         for ( long key : AVLTREE_EXPECTED_KEYS_POST_REMOVE )
158         {
159             assertNotNull( "Should find " + key, tree.find( key ) );
160         }
161     }
162     
163 
164     @Test
165     public void testMarshalEmptyTree() throws IOException
166     {
167         byte[] bites = treeMarshaller.serialize( new AvlTree<Integer>( comparator ) );
168         AvlTree<Integer> tree = treeMarshaller.deserialize( bites );
169         assertNotNull( tree );
170     }
171 
172 
173     @Test
174     public void testRoundTripEmpty() throws IOException
175     {
176         AvlTree<Integer> original = new AvlTree<Integer>( comparator );
177         byte[] bites = treeMarshaller.serialize( original );
178         AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
179         assertTrue( deserialized.isEmpty() );
180     }
181 
182 
183     @Test
184     public void testRoundTripOneEntry() throws IOException
185     {
186         AvlTree<Integer> original = new AvlTree<Integer>( comparator );
187         original.insert( 0 );
188         byte[] bites = treeMarshaller.serialize( original );
189         AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
190         assertFalse( deserialized.isEmpty() );
191         assertEquals( 1, deserialized.getSize() );
192         assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
193     }
194 
195 
196     @Test
197     public void testRoundTripOneEntryFirstLast() throws IOException
198     {
199         AvlTree<Integer> original = new AvlTree<Integer>( comparator );
200         original.insert( 0 );
201         byte[] bites = treeMarshaller.serialize( original );
202         AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
203         assertFalse( deserialized.isEmpty() );
204         assertEquals( 1, deserialized.getSize() );
205         assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
206 
207         assertNotNull( original.getFirst() );
208         assertEquals( 0, ( int ) original.getFirst().getKey() );
209 
210         assertNotNull( deserialized.getFirst() );
211         assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
212 
213         assertNotNull( original.getLast() );
214         assertEquals( 0, ( int ) original.getLast().getKey() );
215 
216         // this marshaller fails to preserve last node reference
217         assertNotNull( deserialized.getLast() );
218         assertEquals( 0, ( int ) deserialized.getLast().getKey() );
219     }
220 
221 
222     @Test
223     public void testRoundTripTwoEntries() throws IOException
224     {
225         AvlTree<Integer> original = new AvlTree<Integer>( comparator );
226         original.insert( 0 );
227         original.insert( 1 );
228         byte[] bites = treeMarshaller.serialize( original );
229         AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
230         assertFalse( deserialized.isEmpty() );
231         assertEquals( 2, deserialized.getSize() );
232         assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
233         assertEquals( 1, ( int ) deserialized.getFirst().next.getKey() );
234     }
235 
236 
237     @Test
238     public void testRoundTripTwoEntriesFirstLast() throws IOException
239     {
240         AvlTree<Integer> original = new AvlTree<Integer>( comparator );
241         original.insert( 0 );
242         original.insert( 1 );
243         byte[] bites = treeMarshaller.serialize( original );
244         AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
245         assertFalse( deserialized.isEmpty() );
246         assertEquals( 2, deserialized.getSize() );
247         assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
248         assertEquals( 1, ( int ) deserialized.getFirst().next.getKey() );
249 
250         assertNotNull( original.getFirst() );
251         assertEquals( 0, ( int ) original.getFirst().getKey() );
252 
253         assertNotNull( deserialized.getFirst() );
254         assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
255 
256         assertNotNull( original.getLast() );
257         assertEquals( 1, ( int ) original.getLast().getKey() );
258 
259         // this marshaller fails to preserve last node reference
260         assertNotNull( deserialized.getLast() );
261         assertEquals( 1, ( int ) deserialized.getLast().getKey() );
262     }
263 
264 
265     @Test
266     public void testRoundTripManyEntries() throws Exception
267     {
268         AvlTree<Integer> original = new AvlTree<Integer>( comparator );
269         for ( int ii = 0; ii < 100; ii++ )
270         {
271             original.insert( ii );
272         }
273         byte[] bites = treeMarshaller.serialize( original );
274         AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
275         assertFalse( deserialized.isEmpty() );
276         assertEquals( 100, deserialized.getSize() );
277 
278         AvlTreeCursor<Integer> cursor = new AvlTreeCursor<Integer>( deserialized );
279         cursor.first();
280         for ( int ii = 0; ii < 100; ii++ )
281         {
282             assertEquals( ii, ( int ) cursor.get() );
283             cursor.next();
284         }
285     }
286 
287 
288     @Test
289     public void testRoundTripManyEntriesFirstLast() throws Exception
290     {
291         AvlTree<Integer> original = new AvlTree<Integer>( comparator );
292         for ( int ii = 0; ii < 100; ii++ )
293         {
294             original.insert( ii );
295         }
296         byte[] bites = treeMarshaller.serialize( original );
297         AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
298         assertFalse( deserialized.isEmpty() );
299         assertEquals( 100, deserialized.getSize() );
300 
301         AvlTreeCursor<Integer> cursor = new AvlTreeCursor<Integer>( deserialized );
302         cursor.first();
303         for ( int ii = 0; ii < 100; ii++ )
304         {
305             assertEquals( ii, ( int ) cursor.get() );
306             cursor.next();
307         }
308 
309         assertNotNull( original.getFirst() );
310         assertEquals( 0, ( int ) original.getFirst().getKey() );
311 
312         assertNotNull( deserialized.getFirst() );
313         assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
314 
315         assertNotNull( original.getLast() );
316         assertEquals( 99, ( int ) original.getLast().getKey() );
317 
318         // this marshaller fails to preserve last node reference
319         assertNotNull( deserialized.getLast() );
320         assertEquals( 99, ( int ) deserialized.getLast().getKey() );
321     }
322 
323 
324     @Test
325     public void testRoundTripManyEntriesDefaultSerialization() throws Exception
326     {
327         Comparator<Bar> barComparator = new Comparator<Bar>() {
328             public int compare( Bar o1, Bar o2 )
329             {
330                 return o1.intValue.compareTo( o2.intValue );
331             }
332         };
333 
334         AvlTree<Bar> original = new AvlTree<Bar>( barComparator );
335 
336         for ( int ii = 0; ii < 100; ii++ )
337         {
338             original.insert( new Bar( ii ) );
339         }
340 
341         AvlTreeMarshaller<Bar> marshaller = new AvlTreeMarshaller<Bar>( barComparator );
342         byte[] bites = marshaller.serialize( original );
343         AvlTree<Bar> deserialized = marshaller.deserialize( bites );
344         assertFalse( deserialized.isEmpty() );
345         assertEquals( 100, deserialized.getSize() );
346 
347         AvlTreeCursor<Bar> cursor = new AvlTreeCursor<Bar>( deserialized );
348         cursor.first();
349         for ( int ii = 0; ii < 100; ii++ )
350         {
351             assertEquals( ii, ( int ) cursor.get().intValue );
352             cursor.next();
353         }
354     }
355 
356 
357     static class Bar implements Serializable
358     {
359         Integer intValue = 37;
360         String stringValue = "bar";
361         long longValue = 32L;
362         Foo fooValue = new Foo();
363 
364 
365         public Bar( int ii )
366         {
367             intValue = ii;
368         }
369     }
370 
371 
372     static class Foo implements Serializable
373     {
374         float floatValue = 3;
375         String stringValue = "foo";
376         double doubleValue = 1.2;
377         byte byteValue = 3;
378         char charValue = 'a';
379     }
380 
381 
382     @Test
383     public void testMarshal() throws IOException
384     {
385         tree.insert( 37 );
386         tree.insert( 7 );
387         tree.insert( 25 );
388         tree.insert( 8 );
389         tree.insert( 9 );
390 
391         FileOutputStream fout = new FileOutputStream( treeFile );
392         fout.write( treeMarshaller.serialize( tree ) );
393         fout.close();
394         
395         savedTree = tree; // to reference in other tests
396         
397         if( LOG.isDebugEnabled() )
398         {
399             LOG.debug("saved tree\n--------");
400             tree.printTree();
401         }
402         
403         assertTrue( true );
404     }
405 
406 
407     @Test
408     public void testUnMarshal() throws FileNotFoundException, IOException
409     {
410         FileInputStream fin = new FileInputStream(treeFile);
411         
412         byte[] data = new byte[ ( int )treeFile.length() ];
413         fin.read( data );
414         
415         AvlTree<Integer> unmarshalledTree = treeMarshaller.deserialize( data );
416         
417         if( LOG.isDebugEnabled() )
418         {
419             LOG.debug("\nunmarshalled tree\n---------------");
420             unmarshalledTree.printTree();
421         }
422         
423         assertTrue( savedTree.getRoot().getKey() == unmarshalledTree.getRoot().getKey() );
424 
425         unmarshalledTree.insert( 6 ); // will change the root as part of balancing
426         
427         assertTrue( savedTree.getRoot().getKey() == unmarshalledTree.getRoot().getKey() );
428         assertTrue( 8 == unmarshalledTree.getRoot().getKey() ); // new root
429         
430         assertTrue( 37 == unmarshalledTree.getLast().getKey() );
431         unmarshalledTree.insert( 99 );
432         assertTrue( 99 == unmarshalledTree.getLast().getKey() );
433 
434         assertTrue( 6 == unmarshalledTree.getFirst().getKey() );
435         
436         unmarshalledTree.insert( 0 );
437         assertTrue( 0 == unmarshalledTree.getFirst().getKey() );
438         
439         if( LOG.isDebugEnabled() )
440         {
441             LOG.debug("\nmodified tree after unmarshalling\n---------------");
442             unmarshalledTree.printTree();
443         }
444         
445         assertNotNull(unmarshalledTree.getFirst());
446         assertNotNull(unmarshalledTree.getLast());
447     }
448     
449     
450     @Test( expected = IOException.class )
451     public void testDeserializeNullData() throws IOException
452     {
453         treeMarshaller.deserialize( null );
454     }
455     
456     
457     public class LongMarshaller implements Marshaller<Long>
458     {
459         public byte[] serialize( Long obj ) throws IOException
460         {
461             long id = obj.longValue();
462             byte[] bites = new byte[8];
463 
464             bites[0] = ( byte ) ( id >> 56 );
465             bites[1] = ( byte ) ( id >> 48 );
466             bites[2] = ( byte ) ( id >> 40 );
467             bites[3] = ( byte ) ( id >> 32 );
468             bites[4] = ( byte ) ( id >> 24 );
469             bites[5] = ( byte ) ( id >> 16 );
470             bites[6] = ( byte ) ( id >> 8 );
471             bites[7] = ( byte ) id;
472 
473             return bites;
474         }
475 
476 
477         public Long deserialize( byte[] bites ) throws IOException
478         {
479             long id;
480             id = bites[0]  + ( ( bites[0] < 0 ) ? 256 : 0 );
481             id <<= 8;
482             id += bites[1] + ( ( bites[1] < 0 ) ? 256 : 0 );
483             id <<= 8;
484             id += bites[2] + ( ( bites[2] < 0 ) ? 256 : 0 );
485             id <<= 8;
486             id += bites[3] + ( ( bites[3] < 0 ) ? 256 : 0 );
487             id <<= 8;
488             id += bites[4] + ( ( bites[4] < 0 ) ? 256 : 0 );
489             id <<= 8;
490             id += bites[5] + ( ( bites[5] < 0 ) ? 256 : 0 );
491             id <<= 8;
492             id += bites[6] + ( ( bites[6] < 0 ) ? 256 : 0 );
493             id <<= 8;
494             id += bites[7] + ( ( bites[7] < 0 ) ? 256 : 0 );
495             return id;
496         }
497     }
498 }