001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020 package org.apache.directory.server.core.avltree; 021 022 023 import java.io.ByteArrayInputStream; 024 import java.io.ByteArrayOutputStream; 025 import java.io.DataInputStream; 026 import java.io.DataOutputStream; 027 import java.io.IOException; 028 import java.util.Comparator; 029 030 import org.apache.directory.server.i18n.I18n; 031 032 033 /** 034 * Class to serialize the AvlTree node data. 035 * 036 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 037 * @version $Rev$, $Date$ 038 */ 039 @SuppressWarnings("unchecked") 040 public class AvlTreeMarshaller<E> implements Marshaller<AvlTree<E>> 041 { 042 /** used for serialized form of an empty AvlTree */ 043 private static final byte[] EMPTY_TREE = new byte[1]; 044 045 /** marshaller to be used for marshalling the keys */ 046 private Marshaller<E> keyMarshaller; 047 048 /** key Comparator for the AvlTree */ 049 private Comparator<E> comparator; 050 051 052 /** 053 * Creates a new instance of AvlTreeMarshaller with a custom key 054 * Marshaller. 055 * 056 * @param comparator Comparator to be used for key comparision 057 * @param keyMarshaller marshaller for keys 058 */ 059 public AvlTreeMarshaller( Comparator<E> comparator, Marshaller<E> keyMarshaller ) 060 { 061 this.comparator = comparator; 062 this.keyMarshaller = keyMarshaller; 063 } 064 065 066 /** 067 * Creates a new instance of AvlTreeMarshaller with the default key 068 * Marshaller which uses Java Serialization. 069 * 070 * @param comparator Comparator to be used for key comparision 071 */ 072 public AvlTreeMarshaller( Comparator<E> comparator ) 073 { 074 this.comparator = comparator; 075 this.keyMarshaller = ( Marshaller<E> ) DefaultMarshaller.INSTANCE; 076 } 077 078 079 /** 080 * Marshals the given tree to bytes 081 * @param tree the tree to be marshalled 082 */ 083 public byte[] serialize( AvlTree<E> tree ) 084 { 085 if( tree.isEmpty() ) 086 { 087 return EMPTY_TREE; 088 } 089 090 LinkedAvlNode<E> x = tree.getFirst().next; 091 092 while( x != null ) 093 { 094 x.setIndex( x.previous.getIndex() + 1 ); 095 x = x.next; 096 } 097 098 ByteArrayOutputStream byteStream = new ByteArrayOutputStream(); 099 DataOutputStream out = new DataOutputStream( byteStream ); 100 byte[] data = null; 101 102 try 103 { 104 out.writeByte( 0 ); // represents the start of AvlTree byte stream 105 out.writeInt( tree.getSize() ); 106 writeTree( tree.getRoot(), out ); 107 out.flush(); 108 data = byteStream.toByteArray(); 109 out.close(); 110 } 111 catch( IOException e ) 112 { 113 e.printStackTrace(); 114 } 115 116 return data; 117 } 118 119 120 /** 121 * writes the content of the AVLTree to an output stream. 122 * The current format is 123 * 124 * AvlTree = [0(zero-byte-value)][node] // the '0' (zero) is to distinguish AvlTree from BTreeRedirect which starts with 1 (one) 125 * node = [size] [data-length] [data] [index] [child-marker] [node] [child-marker] [node] 126 * 127 * @param node the node to be marshalled to bytes 128 * @param out OutputStream 129 * @throws IOException on write failures of serialized tree to stream 130 */ 131 private void writeTree( LinkedAvlNode<E> node, DataOutputStream out ) throws IOException 132 { 133 byte[] data = keyMarshaller.serialize( node.getKey() ); 134 135 out.writeInt( data.length ); // data-length 136 out.write( data ); // data 137 out.writeInt( node.getIndex() ); // index 138 139 if( node.getLeft() != null ) 140 { 141 out.writeInt( 2 ); // left 142 writeTree( node.getLeft(), out ); 143 } 144 else 145 { 146 out.writeInt( 0 ); 147 } 148 149 if( node.getRight() != null ) 150 { 151 out.writeInt( 4 ); // right 152 writeTree( node.getRight(), out ); 153 } 154 else 155 { 156 out.writeInt( 0 ); 157 } 158 159 } 160 161 162 /** 163 * Creates an AVLTree from given bytes of data. 164 * 165 * @param data byte array to be converted into AVLTree 166 */ 167 public AvlTree<E> deserialize( byte[] data ) throws IOException 168 { 169 if ( data == null || data.length == 0 ) 170 { 171 throw new IOException( I18n.err( I18n.ERR_439 ) ); 172 } 173 174 if ( data.length == 1 && data[0] == 0 ) 175 { 176 return new AvlTreeImpl<E>( comparator ); 177 } 178 179 ByteArrayInputStream bin = new ByteArrayInputStream( data ); 180 DataInputStream din = new DataInputStream( bin ); 181 182 byte startByte = din.readByte(); 183 184 if( startByte != 0 ) 185 { 186 throw new IOException( I18n.err( I18n.ERR_443 ) ); 187 } 188 189 int size = din.readInt(); 190 191 LinkedAvlNode[] nodes = new LinkedAvlNode[ size ]; 192 LinkedAvlNode<E> root = readTree( din, null, nodes ); 193 194 AvlTreeImpl<E> tree = new AvlTreeImpl<E>( comparator ); 195 196 tree.setRoot( root ); 197 198 tree.setFirst( nodes[0] ); 199 200 // Update the size 201 tree.setSize( size ); 202 203 if( nodes.length >= 1 ) 204 { 205 tree.setLast( nodes[ nodes.length - 1 ] ); 206 } 207 208 for( int i = 0; i < nodes.length - 1; i++ ) 209 { 210 nodes[ i ].setNext( nodes[ i + 1] ); 211 nodes[ i + 1].setPrevious( nodes[ i ] ); 212 } 213 214 return tree; 215 } 216 217 218 /** 219 * Reads the data from given InputStream and creates the LinkedAvlNodes to 220 * form the tree node = [size] [data-length] [data] [index] [child-marker] 221 * [node] [child-marker] [node]. 222 * 223 * @param in the input stream to deserialize from 224 * @param node the node to deserialize 225 * @return the deserialized AvlTree node 226 * @throws IOException on failures to deserialize or read from the stream 227 */ 228 public LinkedAvlNode<E> readTree( DataInputStream in, LinkedAvlNode<E> node, LinkedAvlNode[] nodes ) throws IOException 229 { 230 int dLen = in.readInt(); 231 232 byte[] data = new byte[ dLen ]; 233 234 //noinspection ResultOfMethodCallIgnored 235 in.read( data ); 236 237 E key = keyMarshaller.deserialize( data ); 238 node = new LinkedAvlNode( key ); 239 240 int index = in.readInt(); 241 nodes[ index ] = node; 242 243 int childMarker = in.readInt(); 244 245 if( childMarker == 2) 246 { 247 node.setLeft( readTree( in, node.getLeft(), nodes ) ); 248 } 249 250 childMarker = in.readInt(); 251 252 if( childMarker == 4 ) 253 { 254 node.setRight( readTree( in, node.getRight(), nodes ) ); 255 } 256 257 return node; 258 } 259 }