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.io.IOException; 024import java.net.URI; 025 026import org.apache.directory.api.ldap.model.cursor.Cursor; 027import org.apache.directory.api.ldap.model.cursor.CursorException; 028import org.apache.directory.api.ldap.model.cursor.EmptyCursor; 029import org.apache.directory.api.ldap.model.cursor.Tuple; 030import org.apache.directory.api.ldap.model.exception.LdapException; 031import org.apache.directory.api.ldap.model.exception.LdapOtherException; 032import org.apache.directory.api.ldap.model.schema.AttributeType; 033import org.apache.directory.api.ldap.model.schema.LdapComparator; 034import org.apache.directory.api.ldap.model.schema.MatchingRule; 035import org.apache.directory.api.ldap.model.schema.Normalizer; 036import org.apache.directory.api.ldap.model.schema.SchemaManager; 037import org.apache.directory.api.ldap.model.schema.comparators.UuidComparator; 038import org.apache.directory.server.core.api.partition.PartitionTxn; 039import org.apache.directory.server.core.partition.impl.btree.IndexCursorAdaptor; 040import org.apache.directory.server.i18n.I18n; 041import org.apache.directory.server.xdbm.AbstractIndex; 042import org.apache.directory.server.xdbm.IndexEntry; 043 044 045/** 046 * An Index backed by an AVL Tree. 047 * 048 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 049 */ 050public class AvlIndex<K> extends AbstractIndex<K, String> 051{ 052 protected Normalizer normalizer; 053 protected AvlTable<K, String> forward; 054 protected AvlTable<String, K> reverse; 055 056 057 public AvlIndex() 058 { 059 super( true ); 060 } 061 062 063 public AvlIndex( String attributeId ) 064 { 065 super( attributeId, true ); 066 } 067 068 069 public AvlIndex( String attributeId, boolean withReverse ) 070 { 071 super( attributeId, withReverse ); 072 } 073 074 075 public void init( SchemaManager schemaManager, AttributeType attributeType ) throws LdapException 076 { 077 this.attributeType = attributeType; 078 079 MatchingRule mr = attributeType.getEquality(); 080 081 if ( mr == null ) 082 { 083 mr = attributeType.getOrdering(); 084 } 085 086 if ( mr == null ) 087 { 088 mr = attributeType.getSubstring(); 089 } 090 091 normalizer = mr.getNormalizer(); 092 093 if ( normalizer == null ) 094 { 095 throw new LdapOtherException( I18n.err( I18n.ERR_212, attributeType ) ); 096 } 097 098 LdapComparator<K> comp = ( LdapComparator<K> ) mr.getLdapComparator(); 099 100 /* 101 * The forward key/value map stores attribute values to master table 102 * primary keys. A value for an attribute can occur several times in 103 * different entries so the forward map can have more than one value. 104 */ 105 forward = new AvlTable<>( attributeType.getName(), comp, UuidComparator.INSTANCE, true ); 106 107 /* 108 * Now the reverse map stores the primary key into the master table as 109 * the key and the values of attributes as the value. If an attribute 110 * is single valued according to its specification based on a schema 111 * then duplicate keys should not be allowed within the reverse table. 112 */ 113 if ( withReverse ) 114 { 115 if ( attributeType.isSingleValued() ) 116 { 117 reverse = new AvlTable<>( attributeType.getName(), UuidComparator.INSTANCE, comp, false ); 118 } 119 else 120 { 121 reverse = new AvlTable<>( attributeType.getName(), UuidComparator.INSTANCE, comp, true ); 122 } 123 } 124 } 125 126 127 public void add( PartitionTxn partitionTxn, K attrVal, String id ) throws LdapException 128 { 129 forward.put( partitionTxn, attrVal, id ); 130 131 if ( withReverse ) 132 { 133 reverse.put( partitionTxn, id, attrVal ); 134 } 135 } 136 137 138 /** 139 * {@inheritDoc} 140 */ 141 @Override 142 public void close( PartitionTxn partitionTxn ) throws LdapException, IOException 143 { 144 if ( forward != null ) 145 { 146 forward.close( partitionTxn ); 147 } 148 149 if ( reverse != null ) 150 { 151 reverse.close( partitionTxn ); 152 } 153 } 154 155 156 /** 157 * {@inheritDoc} 158 */ 159 public long count( PartitionTxn partitionTxn ) throws LdapException 160 { 161 return forward.count( partitionTxn ); 162 } 163 164 165 /** 166 * {@inheritDoc} 167 */ 168 public long count( PartitionTxn partitionTxn, K attrVal ) throws LdapException 169 { 170 return forward.count( partitionTxn, attrVal ); 171 } 172 173 174 /** 175 * {@inheritDoc} 176 */ 177 public void drop( PartitionTxn partitionTxn, String id ) throws LdapException 178 { 179 if ( withReverse ) 180 { 181 if ( isDupsEnabled() ) 182 { 183 Cursor<Tuple<String, K>> cursor = reverse.cursor( partitionTxn, id ); 184 185 try 186 { 187 while ( cursor.next() ) 188 { 189 Tuple<String, K> tuple = cursor.get(); 190 forward.remove( partitionTxn, tuple.getValue(), id ); 191 } 192 193 cursor.close(); 194 } 195 catch ( CursorException | IOException e ) 196 { 197 throw new LdapOtherException( e.getMessage(), e ); 198 } 199 } 200 else 201 { 202 K key = reverse.get( partitionTxn, id ); 203 forward.remove( partitionTxn, key ); 204 } 205 206 reverse.remove( partitionTxn, id ); 207 } 208 } 209 210 211 /** 212 * {@inheritDoc} 213 */ 214 @Override 215 public void drop( PartitionTxn partitionTxn, K attrVal, String id ) throws LdapException 216 { 217 forward.remove( partitionTxn, attrVal, id ); 218 219 if ( withReverse ) 220 { 221 reverse.remove( partitionTxn, id, attrVal ); 222 } 223 } 224 225 226 /** 227 * {@inheritDoc} 228 */ 229 public boolean forward( PartitionTxn partitionTxn, K attrVal ) throws LdapException 230 { 231 return forward.has( partitionTxn, attrVal ); 232 } 233 234 235 /** 236 * {@inheritDoc} 237 */ 238 public boolean forward( PartitionTxn partitionTxn, K attrVal, String id ) throws LdapException 239 { 240 return forward.has( partitionTxn, attrVal, id ); 241 } 242 243 244 /** 245 * {@inheritDoc} 246 */ 247 @Override 248 public Cursor<IndexEntry<K, String>> forwardCursor( PartitionTxn partitionTxn ) throws LdapException 249 { 250 return new IndexCursorAdaptor( partitionTxn, forward.cursor(), true ); 251 } 252 253 254 /** 255 * {@inheritDoc} 256 */ 257 @SuppressWarnings("unchecked") 258 public Cursor<IndexEntry<K, String>> forwardCursor( PartitionTxn partitionTxn, K key ) throws LdapException 259 { 260 return new IndexCursorAdaptor( partitionTxn, forward.cursor( partitionTxn, key ), true ); 261 } 262 263 264 /** 265 * {@inheritDoc} 266 */ 267 public String forwardLookup( PartitionTxn partitionTxn, K attrVal ) throws LdapException 268 { 269 return forward.get( partitionTxn, attrVal ); 270 } 271 272 273 /** 274 * {@inheritDoc} 275 */ 276 @Override 277 public Cursor<String> forwardValueCursor( PartitionTxn partitionTxn, K key ) throws LdapException 278 { 279 return forward.valueCursor( partitionTxn, key ); 280 } 281 282 283 /** 284 * {@inheritDoc} 285 */ 286 @Override 287 public long greaterThanCount( PartitionTxn partitionTxn, K attrVal ) throws LdapException 288 { 289 return forward.greaterThanCount( partitionTxn, attrVal ); 290 } 291 292 293 /** 294 * {@inheritDoc} 295 */ 296 @Override 297 public long lessThanCount( PartitionTxn partitionTxn, K attrVal ) throws LdapException 298 { 299 return forward.lessThanCount( partitionTxn, attrVal ); 300 } 301 302 303 /** 304 * {@inheritDoc} 305 */ 306 @Override 307 public boolean reverse( PartitionTxn partitionTxn, String id ) throws LdapException 308 { 309 if ( withReverse ) 310 { 311 return reverse.has( partitionTxn, id ); 312 } 313 else 314 { 315 return false; 316 } 317 } 318 319 320 /** 321 * {@inheritDoc} 322 */ 323 @Override 324 public boolean reverse( PartitionTxn partitionTxn, String id, K attrVal ) throws LdapException 325 { 326 if ( withReverse ) 327 { 328 return reverse.has( partitionTxn, id, attrVal ); 329 } 330 else 331 { 332 return false; 333 } 334 } 335 336 337 /** 338 * {@inheritDoc} 339 */ 340 public K reverseLookup( PartitionTxn partitionTxn, String id ) throws LdapException 341 { 342 if ( withReverse ) 343 { 344 return reverse.get( partitionTxn, id ); 345 } 346 else 347 { 348 return null; 349 } 350 } 351 352 353 /** 354 * {@inheritDoc} 355 */ 356 @Override 357 public Cursor<K> reverseValueCursor( PartitionTxn partitionTxn, String id ) throws LdapException 358 { 359 if ( withReverse ) 360 { 361 return reverse.valueCursor( partitionTxn, id ); 362 } 363 else 364 { 365 return new EmptyCursor<>(); 366 } 367 } 368 369 370 /** 371 * throws UnsupportedOperationException cause it is a in-memory index 372 */ 373 public void setWkDirPath( URI wkDirPath ) 374 { 375 throw new UnsupportedOperationException( I18n.err( I18n.ERR_213 ) ); 376 } 377 378 379 /** 380 * this method always returns null for AvlIndex cause this is a in-memory index. 381 */ 382 public URI getWkDirPath() 383 { 384 return null; 385 } 386 387 388 /** 389 * {@inheritDoc} 390 */ 391 @Override 392 public boolean isDupsEnabled() 393 { 394 if ( withReverse ) 395 { 396 return reverse.isDupsEnabled(); 397 } 398 else 399 { 400 return false; 401 } 402 } 403}