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 */ 020package org.apache.directory.server.core.avltree; 021 022 023import java.io.ByteArrayInputStream; 024import java.io.ByteArrayOutputStream; 025import java.io.DataInputStream; 026import java.io.DataOutputStream; 027import java.io.IOException; 028import java.util.Comparator; 029 030import 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 */ 038@SuppressWarnings("unchecked") 039public class AvlTreeMarshaller<E> implements Marshaller<AvlTree<E>> 040{ 041 /** used for serialized form of an empty AvlTree */ 042 private static final byte[] EMPTY_TREE = new byte[1]; 043 044 /** marshaller to be used for marshalling the keys */ 045 private Marshaller<E> keyMarshaller; 046 047 /** key Comparator for the AvlTree */ 048 private Comparator<E> comparator; 049 050 051 /** 052 * Creates a new instance of AvlTreeMarshaller with a custom key 053 * Marshaller. 054 * 055 * @param comparator Comparator to be used for key comparision 056 * @param keyMarshaller marshaller for keys 057 */ 058 public AvlTreeMarshaller( Comparator<E> comparator, Marshaller<E> keyMarshaller ) 059 { 060 this.comparator = comparator; 061 this.keyMarshaller = keyMarshaller; 062 } 063 064 065 /** 066 * Creates a new instance of AvlTreeMarshaller with the default key 067 * Marshaller which uses Java Serialization. 068 * 069 * @param comparator Comparator to be used for key comparision 070 */ 071 public AvlTreeMarshaller( Comparator<E> comparator ) 072 { 073 this.comparator = comparator; 074 this.keyMarshaller = ( Marshaller<E> ) DefaultMarshaller.INSTANCE; 075 } 076 077 078 /** 079 * Marshals the given tree to bytes 080 * @param tree the tree to be marshalled 081 */ 082 public byte[] serialize( AvlTree<E> tree ) 083 { 084 if ( tree.isEmpty() ) 085 { 086 return EMPTY_TREE; 087 } 088 089 LinkedAvlNode<E> x = tree.getFirst().next; 090 091 while ( x != null ) 092 { 093 x.setIndex( x.previous.getIndex() + 1 ); 094 x = x.next; 095 } 096 097 byte[] data = null; 098 099 try ( ByteArrayOutputStream byteStream = new ByteArrayOutputStream(); 100 DataOutputStream out = new DataOutputStream( byteStream ) ) 101 { 102 out.writeByte( 0 ); // represents the start of AvlTree byte stream 103 out.writeInt( tree.getSize() ); 104 writeTree( tree.getRoot(), out ); 105 out.flush(); 106 data = byteStream.toByteArray(); 107 } 108 catch ( IOException e ) 109 { 110 e.printStackTrace(); 111 } 112 113 return data; 114 } 115 116 117 /** 118 * writes the content of the AVLTree to an output stream. 119 * The current format is 120 * 121 * AvlTree = [0(zero-byte-value)][node] // the '0' (zero) is to distinguish AvlTree from BTreeRedirect which starts with 1 (one) 122 * node = [size] [data-length] [data] [index] [child-marker] [node] [child-marker] [node] 123 * 124 * @param node the node to be marshalled to bytes 125 * @param out OutputStream 126 * @throws IOException on write failures of serialized tree to stream 127 */ 128 private void writeTree( LinkedAvlNode<E> node, DataOutputStream out ) throws IOException 129 { 130 byte[] data = keyMarshaller.serialize( node.getKey() ); 131 132 out.writeInt( data.length ); // data-length 133 out.write( data ); // data 134 out.writeInt( node.getIndex() ); // index 135 136 if ( node.getLeft() != null ) 137 { 138 out.writeInt( 2 ); // left 139 writeTree( node.getLeft(), out ); 140 } 141 else 142 { 143 out.writeInt( 0 ); 144 } 145 146 if ( node.getRight() != null ) 147 { 148 out.writeInt( 4 ); // right 149 writeTree( node.getRight(), out ); 150 } 151 else 152 { 153 out.writeInt( 0 ); 154 } 155 156 } 157 158 159 /** 160 * Creates an AVLTree from given bytes of data. 161 * 162 * @param data byte array to be converted into AVLTree 163 */ 164 public AvlTree<E> deserialize( byte[] data ) throws IOException 165 { 166 if ( data == null || data.length == 0 ) 167 { 168 throw new IOException( I18n.err( I18n.ERR_439 ) ); 169 } 170 171 if ( data.length == 1 && data[0] == 0 ) 172 { 173 return new AvlTreeImpl<>( comparator ); 174 } 175 176 ByteArrayInputStream bin = new ByteArrayInputStream( data ); 177 DataInputStream din = new DataInputStream( bin ); 178 179 byte startByte = din.readByte(); 180 181 if ( startByte != 0 ) 182 { 183 throw new IOException( I18n.err( I18n.ERR_443 ) ); 184 } 185 186 int size = din.readInt(); 187 188 LinkedAvlNode[] nodes = new LinkedAvlNode[size]; 189 LinkedAvlNode<E> root = readTree( din, nodes ); 190 191 AvlTreeImpl<E> tree = new AvlTreeImpl<>( comparator ); 192 193 tree.setRoot( root ); 194 195 tree.setFirst( nodes[0] ); 196 197 // Update the size 198 tree.setSize( size ); 199 200 if ( nodes.length >= 1 ) 201 { 202 tree.setLast( nodes[nodes.length - 1] ); 203 } 204 205 for ( int i = 0; i < nodes.length - 1; i++ ) 206 { 207 nodes[i].setNext( nodes[i + 1] ); 208 nodes[i + 1].setPrevious( nodes[i] ); 209 } 210 211 return tree; 212 } 213 214 215 /** 216 * Reads the data from given InputStream and creates the LinkedAvlNodes to 217 * form the tree node = [size] [data-length] [data] [index] [child-marker] 218 * [node] [child-marker] [node]. 219 * 220 * @param in the input stream to deserialize from 221 * @param nodes the deserialized nodes 222 * @return the deserialized AvlTree node 223 * @throws IOException on failures to deserialize or read from the stream 224 */ 225 public LinkedAvlNode<E> readTree( DataInputStream in, LinkedAvlNode[] nodes ) 226 throws IOException 227 { 228 int dLen = in.readInt(); 229 230 byte[] data = new byte[dLen]; 231 232 //noinspection ResultOfMethodCallIgnored 233 in.readFully( data ); 234 235 E key = keyMarshaller.deserialize( data ); 236 LinkedAvlNode<E> node = new LinkedAvlNode<>( key ); 237 238 int index = in.readInt(); 239 nodes[index] = node; 240 241 int childMarker = in.readInt(); 242 243 if ( childMarker == 2 ) 244 { 245 node.setLeft( readTree( in, nodes ) ); 246 } 247 248 childMarker = in.readInt(); 249 250 if ( childMarker == 4 ) 251 { 252 node.setRight( readTree( in, nodes ) ); 253 } 254 255 return node; 256 } 257}