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