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.xdbm.impl.avl; 021 022 023import java.util.Comparator; 024 025import org.apache.directory.api.ldap.model.cursor.Cursor; 026import org.apache.directory.api.ldap.model.cursor.EmptyCursor; 027import org.apache.directory.api.ldap.model.cursor.SingletonCursor; 028import org.apache.directory.api.ldap.model.cursor.Tuple; 029import org.apache.directory.api.ldap.model.exception.LdapException; 030import org.apache.directory.server.core.api.partition.PartitionTxn; 031import org.apache.directory.server.core.avltree.AvlSingletonOrOrderedSetCursor; 032import org.apache.directory.server.core.avltree.AvlTree; 033import org.apache.directory.server.core.avltree.AvlTreeCursor; 034import org.apache.directory.server.core.avltree.AvlTreeMap; 035import org.apache.directory.server.core.avltree.AvlTreeMapImpl; 036import org.apache.directory.server.core.avltree.AvlTreeMapNoDupsWrapperCursor; 037import org.apache.directory.server.core.avltree.KeyTupleAvlCursor; 038import org.apache.directory.server.core.avltree.LinkedAvlMapNode; 039import org.apache.directory.server.core.avltree.SingletonOrOrderedSet; 040import org.apache.directory.server.xdbm.AbstractTable; 041 042 043/** 044 * A Table implementation backed by in memory AVL tree. 045 * 046 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 047 */ 048public class AvlTable<K, V> extends AbstractTable<K, V> 049{ 050 private final AvlTreeMap<K, V> avl; 051 private final Comparator<Tuple<K, V>> keyOnlytupleComparator; 052 053 054 public AvlTable( String name, final Comparator<K> keyComparator, final Comparator<V> valueComparator, 055 boolean dupsEnabled ) 056 { 057 super( null, name, keyComparator, valueComparator ); 058 this.avl = new AvlTreeMapImpl<>( keyComparator, valueComparator, dupsEnabled ); 059 allowsDuplicates = this.avl.isDupsAllowed(); 060 this.keyOnlytupleComparator = new Comparator<Tuple<K, V>>() 061 { 062 public int compare( Tuple<K, V> t0, Tuple<K, V> t1 ) 063 { 064 return keyComparator.compare( t0.getKey(), t1.getKey() ); 065 } 066 }; 067 } 068 069 070 /** 071 * {@inheritDoc} 072 */ 073 @Override 074 public void close( PartitionTxn transaction ) throws LdapException 075 { 076 ( ( AvlTreeMapImpl<K, V> ) avl ).removeAll(); 077 } 078 079 080 /** 081 * {@inheritDoc} 082 */ 083 @Override 084 public long count( PartitionTxn transaction, K key ) throws LdapException 085 { 086 if ( key == null ) 087 { 088 return 0L; 089 } 090 091 LinkedAvlMapNode<K, V> node = avl.find( key ); 092 093 if ( node == null ) 094 { 095 return 0L; 096 } 097 098 SingletonOrOrderedSet<V> val = node.getValue(); 099 100 if ( val.isOrderedSet() ) 101 { 102 return val.getOrderedSet().getSize(); 103 } 104 105 return 1L; 106 } 107 108 109 /** 110 * {@inheritDoc} 111 */ 112 @Override 113 public V get( PartitionTxn transaction, K key ) throws LdapException 114 { 115 if ( key == null ) 116 { 117 return null; 118 } 119 120 LinkedAvlMapNode<K, V> node = avl.find( key ); 121 122 if ( node == null ) 123 { 124 return null; 125 } 126 127 SingletonOrOrderedSet<V> val = node.getValue(); 128 129 if ( val.isOrderedSet() ) 130 { 131 return val.getOrderedSet().getFirst().getKey(); 132 } 133 134 return val.getSingleton(); 135 } 136 137 138 /** 139 * {@inheritDoc} 140 */ 141 @Override 142 public long greaterThanCount( PartitionTxn transaction, K key ) throws LdapException 143 { 144 return avl.getSize(); 145 } 146 147 148 /** 149 * {@inheritDoc} 150 */ 151 @Override 152 public boolean has( PartitionTxn transaction, K key ) throws LdapException 153 { 154 if ( key == null ) 155 { 156 return false; 157 } 158 159 return avl.find( key ) != null; 160 } 161 162 163 /** 164 * {@inheritDoc} 165 */ 166 @Override 167 public boolean has( PartitionTxn transaction, K key, V value ) throws LdapException 168 { 169 if ( key == null ) 170 { 171 return false; 172 } 173 174 return avl.find( key, value ) != null; 175 } 176 177 178 /** 179 * {@inheritDoc} 180 */ 181 @Override 182 public boolean hasGreaterOrEqual( PartitionTxn transaction, K key ) throws LdapException 183 { 184 if ( key == null ) 185 { 186 return false; 187 } 188 189 return avl.findGreaterOrEqual( key ) != null; 190 } 191 192 193 /** 194 * {@inheritDoc} 195 */ 196 @Override 197 public boolean hasGreaterOrEqual( PartitionTxn transaction, K key, V val ) throws LdapException 198 { 199 if ( key == null ) 200 { 201 return false; 202 } 203 204 LinkedAvlMapNode<K, V> node = avl.findGreaterOrEqual( key ); 205 206 if ( node == null ) 207 { 208 return false; 209 } 210 211 if ( node.getValue().isOrderedSet() ) 212 { 213 AvlTree<V> values = node.getValue().getOrderedSet(); 214 return values.findGreaterOrEqual( val ) != null; 215 } 216 217 return valueComparator.compare( node.getValue().getSingleton(), val ) >= 0; 218 } 219 220 221 /** 222 * {@inheritDoc} 223 */ 224 @Override 225 public boolean hasLessOrEqual( PartitionTxn transaction, K key ) throws LdapException 226 { 227 if ( key == null ) 228 { 229 return false; 230 } 231 232 return avl.findLessOrEqual( key ) != null; 233 } 234 235 236 /** 237 * {@inheritDoc} 238 */ 239 @Override 240 public boolean hasLessOrEqual( PartitionTxn transaction, K key, V val ) throws LdapException 241 { 242 if ( key == null ) 243 { 244 return false; 245 } 246 247 LinkedAvlMapNode<K, V> node = avl.findLessOrEqual( key ); 248 249 if ( node == null ) 250 { 251 return false; 252 } 253 254 if ( node.getValue().isOrderedSet() ) 255 { 256 AvlTree<V> values = node.getValue().getOrderedSet(); 257 return values.findLessOrEqual( val ) != null; 258 } 259 260 return valueComparator.compare( node.getValue().getSingleton(), val ) <= 0; 261 } 262 263 264 /** 265 * {@inheritDoc} 266 */ 267 @Override 268 public long lessThanCount( PartitionTxn transaction, K key ) throws LdapException 269 { 270 return count; 271 } 272 273 274 /** 275 * {@inheritDoc} 276 */ 277 @Override 278 public void put( PartitionTxn partitionTxn, K key, V value ) throws LdapException 279 { 280 if ( ( key == null ) || ( value == null ) ) 281 { 282 return; 283 } 284 285 if ( avl.insert( key, value ) == null ) 286 { 287 count++; 288 } 289 } 290 291 292 /** 293 * {@inheritDoc} 294 */ 295 @Override 296 public void remove( PartitionTxn partitionTxn, K key ) throws LdapException 297 { 298 if ( key == null ) 299 { 300 return; 301 } 302 303 SingletonOrOrderedSet<V> value = avl.remove( key ); 304 305 if ( value == null ) 306 { 307 return; 308 } 309 310 if ( value.isOrderedSet() ) 311 { 312 count -= value.getOrderedSet().getSize(); 313 } 314 else 315 { 316 count--; 317 } 318 } 319 320 321 /** 322 * {@inheritDoc} 323 */ 324 @Override 325 public void remove( PartitionTxn partitionTxn, K key, V value ) throws LdapException 326 { 327 if ( avl.remove( key, value ) != null ) 328 { 329 count--; 330 } 331 } 332 333 334 /** 335 * {@inheritDoc} 336 */ 337 @Override 338 public Cursor<Tuple<K, V>> cursor() 339 { 340 if ( !allowsDuplicates ) 341 { 342 return new AvlTreeMapNoDupsWrapperCursor<>( 343 new AvlSingletonOrOrderedSetCursor<K, V>( avl ) ); 344 } 345 346 return new AvlTableDupsCursor<>( this ); 347 } 348 349 350 /** 351 * {@inheritDoc} 352 */ 353 @Override 354 public Cursor<Tuple<K, V>> cursor( PartitionTxn partitionTxn, K key ) throws LdapException 355 { 356 if ( key == null ) 357 { 358 return new EmptyCursor<>(); 359 } 360 361 LinkedAvlMapNode<K, V> node = avl.find( key ); 362 363 if ( node == null ) 364 { 365 return new EmptyCursor<>(); 366 } 367 368 if ( node.getValue().isOrderedSet() ) 369 { 370 return new KeyTupleAvlCursor<>( node.getValue().getOrderedSet(), key ); 371 } 372 373 return new SingletonCursor<>( new Tuple<K, V>( key, node.getValue().getSingleton() ), 374 keyOnlytupleComparator ); 375 } 376 377 378 /** 379 * {@inheritDoc} 380 */ 381 @Override 382 public Cursor<V> valueCursor( PartitionTxn transaction, K key ) throws LdapException 383 { 384 if ( key == null ) 385 { 386 return new EmptyCursor<>(); 387 } 388 389 LinkedAvlMapNode<K, V> node = avl.find( key ); 390 391 if ( node == null ) 392 { 393 return new EmptyCursor<>(); 394 } 395 396 if ( node.getValue().isOrderedSet() ) 397 { 398 return new AvlTreeCursor<>( node.getValue().getOrderedSet() ); 399 } 400 401 return new SingletonCursor<>( node.getValue().getSingleton(), valueComparator ); 402 } 403 404 405 /** 406 * Returns the internal AvlTreeMap so other classes like Cursors 407 * in the same package can access it. 408 * 409 * @return AvlTreeMap used to store Tuples 410 */ 411 AvlTreeMap<K, V> getAvlTreeMap() 412 { 413 return avl; 414 } 415}