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.io.File; 024 025 import org.apache.directory.server.core.partition.impl.btree.IndexCursorAdaptor; 026 import org.apache.directory.server.core.partition.impl.btree.LongComparator; 027 import org.apache.directory.server.i18n.I18n; 028 import org.apache.directory.server.xdbm.Index; 029 import org.apache.directory.server.xdbm.IndexCursor; 030 import org.apache.directory.server.xdbm.Tuple; 031 import org.apache.directory.shared.ldap.cursor.Cursor; 032 import org.apache.directory.shared.ldap.entry.BinaryValue; 033 import org.apache.directory.shared.ldap.schema.AttributeType; 034 import org.apache.directory.shared.ldap.schema.LdapComparator; 035 import org.apache.directory.shared.ldap.schema.MatchingRule; 036 import org.apache.directory.shared.ldap.schema.Normalizer; 037 038 039 /** 040 * An Index backed by an AVL Tree. 041 * 042 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 043 * @version $Rev$, $Date$ 044 */ 045 public class AvlIndex<K, O> implements Index<K, O, Long> 046 { 047 private Normalizer normalizer; 048 private AttributeType attributeType; 049 private AvlTable<K, Long> forward; 050 private AvlTable<Long, K> reverse; 051 private String attributeId; 052 053 054 public AvlIndex() 055 { 056 } 057 058 059 public AvlIndex( String attributeId ) 060 { 061 setAttributeId( attributeId ); 062 } 063 064 065 void initialize( AttributeType attributeType ) throws Exception 066 { 067 this.attributeType = attributeType; 068 069 MatchingRule mr = attributeType.getEquality(); 070 071 if ( mr == null ) 072 { 073 mr = attributeType.getOrdering(); 074 } 075 076 if ( mr == null ) 077 { 078 mr = attributeType.getSubstring(); 079 } 080 081 normalizer = mr.getNormalizer(); 082 083 if ( normalizer == null ) 084 { 085 throw new Exception( I18n.err( I18n.ERR_212, attributeType ) ); 086 } 087 088 LdapComparator<K> comp = ( LdapComparator<K> ) mr.getLdapComparator(); 089 090 /* 091 * The forward key/value map stores attribute values to master table 092 * primary keys. A value for an attribute can occur several times in 093 * different entries so the forward map can have more than one value. 094 */ 095 forward = new AvlTable<K, Long>( attributeType.getName(), comp, LongComparator.INSTANCE, true ); 096 097 /* 098 * Now the reverse map stores the primary key into the master table as 099 * the key and the values of attributes as the value. If an attribute 100 * is single valued according to its specification based on a schema 101 * then duplicate keys should not be allowed within the reverse table. 102 */ 103 if ( attributeType.isSingleValued() ) 104 { 105 reverse = new AvlTable<Long, K>( attributeType.getName(), LongComparator.INSTANCE, comp, false ); 106 } 107 else 108 { 109 reverse = new AvlTable<Long, K>( attributeType.getName(), LongComparator.INSTANCE, comp, true ); 110 } 111 } 112 113 114 public void add( K attrVal, Long id ) throws Exception 115 { 116 forward.put( getNormalized( attrVal ), id ); 117 reverse.put( id, getNormalized( attrVal ) ); 118 } 119 120 121 /** 122 * {@inheritDoc} 123 */ 124 public void close() throws Exception 125 { 126 forward.close(); 127 reverse.close(); 128 } 129 130 131 /** 132 * {@inheritDoc} 133 */ 134 public int count() throws Exception 135 { 136 return forward.count(); 137 } 138 139 140 /** 141 * {@inheritDoc} 142 */ 143 public int count( K attrVal ) throws Exception 144 { 145 return forward.count( getNormalized( attrVal ) ); 146 } 147 148 149 /** 150 * {@inheritDoc} 151 */ 152 public void drop( Long id ) throws Exception 153 { 154 Cursor<Tuple<Long, K>> cursor = reverse.cursor( id ); 155 156 while ( cursor.next() ) 157 { 158 Tuple<Long, K> tuple = cursor.get(); 159 forward.remove( tuple.getValue(), id ); 160 } 161 162 reverse.remove( id ); 163 } 164 165 166 /** 167 * {@inheritDoc} 168 */ 169 public void drop( K attrVal, Long id ) throws Exception 170 { 171 forward.remove( getNormalized( attrVal ), id ); 172 reverse.remove( id, getNormalized( attrVal ) ); 173 } 174 175 176 /** 177 * {@inheritDoc} 178 */ 179 public boolean forward( K attrVal ) throws Exception 180 { 181 return forward.has( getNormalized( attrVal ) ); 182 } 183 184 185 /** 186 * {@inheritDoc} 187 */ 188 public boolean forward( K attrVal, Long id ) throws Exception 189 { 190 return forward.has( getNormalized( attrVal ), id ); 191 } 192 193 194 /** 195 * {@inheritDoc} 196 */ 197 @SuppressWarnings("unchecked") 198 public IndexCursor<K, O, Long> forwardCursor() throws Exception 199 { 200 return new IndexCursorAdaptor( forward.cursor(), true ); 201 } 202 203 204 /** 205 * {@inheritDoc} 206 */ 207 @SuppressWarnings("unchecked") 208 public IndexCursor<K, O, Long> forwardCursor( K key ) throws Exception 209 { 210 return new IndexCursorAdaptor( forward.cursor( key ), true ); 211 } 212 213 214 /** 215 * {@inheritDoc} 216 */ 217 public boolean forwardGreaterOrEq( K attrVal ) throws Exception 218 { 219 return forward.hasGreaterOrEqual( getNormalized( attrVal ) ); 220 } 221 222 223 /** 224 * {@inheritDoc} 225 */ 226 public boolean forwardGreaterOrEq( K attrVal, Long id ) throws Exception 227 { 228 return forward.hasGreaterOrEqual( getNormalized( attrVal ), id ); 229 } 230 231 232 /** 233 * {@inheritDoc} 234 */ 235 public boolean forwardLessOrEq( K attrVal ) throws Exception 236 { 237 return forward.hasLessOrEqual( getNormalized( attrVal ) ); 238 } 239 240 241 /** 242 * {@inheritDoc} 243 */ 244 public boolean forwardLessOrEq( K attrVal, Long id ) throws Exception 245 { 246 return forward.hasLessOrEqual( getNormalized( attrVal ), id ); 247 } 248 249 250 /** 251 * {@inheritDoc} 252 */ 253 public Long forwardLookup( K attrVal ) throws Exception 254 { 255 return forward.get( getNormalized( attrVal ) ); 256 } 257 258 259 /** 260 * {@inheritDoc} 261 */ 262 public Cursor<Long> forwardValueCursor( K key ) throws Exception 263 { 264 return forward.valueCursor( key ); 265 } 266 267 268 /** 269 * {@inheritDoc} 270 */ 271 public AttributeType getAttribute() 272 { 273 return attributeType; 274 } 275 276 277 /** 278 * {@inheritDoc} 279 */ 280 public String getAttributeId() 281 { 282 return attributeId; 283 } 284 285 286 /** 287 * {@inheritDoc} 288 */ 289 @SuppressWarnings("unchecked") 290 public K getNormalized( K attrVal ) throws Exception 291 { 292 if ( attrVal instanceof Long ) 293 { 294 return attrVal; 295 } 296 297 if ( attrVal instanceof String ) 298 { 299 return ( K ) normalizer.normalize( ( String ) attrVal ); 300 } 301 else 302 { 303 return ( K ) normalizer.normalize( new BinaryValue( ( byte[] ) attrVal ) ).get(); 304 } 305 } 306 307 308 /** 309 * {@inheritDoc} 310 */ 311 public int greaterThanCount( K attrVal ) throws Exception 312 { 313 return forward.greaterThanCount( getNormalized( attrVal ) ); 314 } 315 316 317 /** 318 * {@inheritDoc} 319 */ 320 public boolean isCountExact() 321 { 322 return false; 323 } 324 325 326 /** 327 * {@inheritDoc} 328 */ 329 public int lessThanCount( K attrVal ) throws Exception 330 { 331 return forward.lessThanCount( getNormalized( attrVal ) ); 332 } 333 334 335 /** 336 * {@inheritDoc} 337 */ 338 public boolean reverse( Long id ) throws Exception 339 { 340 return reverse.has( id ); 341 } 342 343 344 /** 345 * {@inheritDoc} 346 */ 347 public boolean reverse( Long id, K attrVal ) throws Exception 348 { 349 return reverse.has( id, getNormalized( attrVal ) ); 350 } 351 352 353 /** 354 * {@inheritDoc} 355 */ 356 @SuppressWarnings("unchecked") 357 public IndexCursor<K, O, Long> reverseCursor() throws Exception 358 { 359 return new IndexCursorAdaptor( reverse.cursor(), false ); 360 } 361 362 363 /** 364 * {@inheritDoc} 365 */ 366 @SuppressWarnings("unchecked") 367 public IndexCursor<K, O, Long> reverseCursor( Long id ) throws Exception 368 { 369 return new IndexCursorAdaptor( reverse.cursor( id ), false ); 370 } 371 372 373 /** 374 * {@inheritDoc} 375 */ 376 public boolean reverseGreaterOrEq( Long id ) throws Exception 377 { 378 return reverse.hasGreaterOrEqual( id ); 379 } 380 381 382 /** 383 * {@inheritDoc} 384 */ 385 public boolean reverseGreaterOrEq( Long id, K attrVal ) throws Exception 386 { 387 return reverse.hasGreaterOrEqual( id, getNormalized( attrVal ) ); 388 } 389 390 391 /** 392 * {@inheritDoc} 393 */ 394 public boolean reverseLessOrEq( Long id ) throws Exception 395 { 396 return reverse.hasLessOrEqual( id ); 397 } 398 399 400 /** 401 * {@inheritDoc} 402 */ 403 public boolean reverseLessOrEq( Long id, K attrVal ) throws Exception 404 { 405 return reverse.hasLessOrEqual( id, getNormalized( attrVal ) ); 406 } 407 408 409 /** 410 * {@inheritDoc} 411 */ 412 public K reverseLookup( Long id ) throws Exception 413 { 414 return reverse.get( id ); 415 } 416 417 418 /** 419 * {@inheritDoc} 420 */ 421 public Cursor<K> reverseValueCursor( Long id ) throws Exception 422 { 423 return reverse.valueCursor( id ); 424 } 425 426 427 /** 428 * {@inheritDoc} 429 */ 430 public void setAttributeId( String attributeId ) 431 { 432 this.attributeId = attributeId; 433 } 434 435 436 /** 437 * throws UnsupportedOperationException cause it is a in-memory index 438 */ 439 public void setWkDirPath( File wkDirPath ) 440 { 441 throw new UnsupportedOperationException( I18n.err( I18n.ERR_213 ) ); 442 } 443 444 445 /** 446 * this method always returns null for AvlIndex cause this is a in-memory index. 447 */ 448 public File getWkDirPath() 449 { 450 return null; 451 } 452 453 454 /** 455 * throws UnsupportedOperationException cause it is a in-memory index 456 */ 457 public void setCacheSize( int cacheSize ) 458 { 459 throw new UnsupportedOperationException( I18n.err( I18n.ERR_214 ) ); 460 } 461 462 463 public int getCacheSize() 464 { 465 return 0; 466 } 467 468 469 /** 470 * {@inheritDoc} 471 */ 472 public void sync() throws Exception 473 { 474 } 475 }