org.apache.directory.server.core.partition.avl

Class AvlIndex<K,O>

java.lang.Object

org.apache.directory.server.core.partition.avl.AvlIndex<K,O>

All Implemented Interfaces:

Index<K,O,Long>

public class AvlIndex<K,O>
extends Object
implements Index<K,O,Long>

An Index backed by an AVL Tree.

Version:

$Rev$, $Date$

Author:

Apache Directory Project

Field Summary

Fields inherited from interface org.apache.directory.server.xdbm.Index

DEFAULT_INDEX_CACHE_SIZE

Constructor Summary

Constructors

Constructor and Description
AvlIndex()
AvlIndex(String attributeId)

Method Summary

Methods

Modifier and Type	Method and Description
void	add(K attrVal, Long id)
void	close()
int	count() Gets the total scan count for this index.
int	count(K attrVal) Gets the scan count for the occurance of a specific attribute value within the index.
void	drop(K attrVal, Long id)
void	drop(Long id) Remove all the reference to an entry from the index.
boolean	forward(K attrVal)
boolean	forward(K attrVal, Long id)
IndexCursor<K,O,Long>	forwardCursor()
IndexCursor<K,O,Long>	forwardCursor(K key)
boolean	forwardGreaterOrEq(K attrVal)
boolean	forwardGreaterOrEq(K attrVal, Long id)
boolean	forwardLessOrEq(K attrVal)
boolean	forwardLessOrEq(K attrVal, Long id)
Long	forwardLookup(K attrVal)
org.apache.directory.shared.ldap.cursor.Cursor<Long>	forwardValueCursor(K key)
org.apache.directory.shared.ldap.schema.AttributeType	getAttribute() Gets the attribute this Index is built upon.
String	getAttributeId() Gets the attribute identifier set at configuration time for this index which may not be the OID but an alias name for the attributeType associated with this Index
int	getCacheSize() Gets the size of the index cache in terms of the number of index entries to be cached.
K	getNormalized(K attrVal) Gets the normalized value for an attribute.
File	getWkDirPath() this method always returns null for AvlIndex cause this is a in-memory index.
int	greaterThanCount(K attrVal)
boolean	isCountExact() Checks whether or not calls to count the number of keys greater than or less than the key are exact.
int	lessThanCount(K attrVal)
boolean	reverse(Long id)
boolean	reverse(Long id, K attrVal)
IndexCursor<K,O,Long>	reverseCursor()
IndexCursor<K,O,Long>	reverseCursor(Long id)
boolean	reverseGreaterOrEq(Long id)
boolean	reverseGreaterOrEq(Long id, K attrVal)
boolean	reverseLessOrEq(Long id)
boolean	reverseLessOrEq(Long id, K attrVal)
K	reverseLookup(Long id)
org.apache.directory.shared.ldap.cursor.Cursor<K>	reverseValueCursor(Long id)
void	setAttributeId(String attributeId) Sets the attribute identifier set at configuration time for this index which may not be the OID but an alias name for the attributeType associated with this Index
void	setCacheSize(int cacheSize) throws UnsupportedOperationException cause it is a in-memory index
void	setWkDirPath(File wkDirPath) throws UnsupportedOperationException cause it is a in-memory index
void	sync()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AvlIndex

public AvlIndex()

AvlIndex

public AvlIndex(String attributeId)

Method Detail

add

public void add(K attrVal,
       Long id)
         throws Exception

Specified by:

add in interface Index<K,O,Long>

Throws:

Exception

close

public void close()
           throws Exception

Specified by:

close in interface Index<K,O,Long>

Throws:

Exception

count

public int count()
          throws Exception

Gets the total scan count for this index.

Specified by:

count in interface Index<K,O,Long>

Returns:

the number of key/value pairs in this index

Throws:

Exception - on failure to access index db files

count

public int count(K attrVal)
          throws Exception

Gets the scan count for the occurance of a specific attribute value within the index.

Specified by:

count in interface Index<K,O,Long>

Parameters:

attrVal - the value of the attribute to get a scan count for

Returns:

the number of key/value pairs in this index with the value value

Throws:

Exception - on failure to access index db files

drop

public void drop(Long id)
          throws Exception

Remove all the reference to an entry from the index. As an entry might be referenced more than once in the forward index, depending on which index we are dealing with, we need to iterate over all the values contained into the reverse index for this entryId. For instance, considering the ObjectClass index for an entry having three ObjectClasses (top, person, inetOrgPerson), then the reverse index will contain : [entryId, [top, person, inetOrgPerson]] and the forward index will contain many entries like : [top, [..., entryId, ...]] [person, [..., entryId, ...]] [inetOrgPerson, [..., entryId, ...]] So dropping the entryId means that we must first get all the values from the reverse index (and we will get [top, person, inetOrgPerson]) then to iterate through all those values to remove entryId from the associated list of entryIds.

Specified by:

drop in interface Index<K,O,Long>

Parameters:

id - The master table entry ID to remove

Throws:

Exception

drop

public void drop(K attrVal,
        Long id)
          throws Exception

Specified by:

drop in interface Index<K,O,Long>

Throws:

Exception

forward

public boolean forward(K attrVal)
                throws Exception

Specified by:

forward in interface Index<K,O,Long>

Throws:

Exception

forward

public boolean forward(K attrVal,
              Long id)
                throws Exception

Specified by:

forward in interface Index<K,O,Long>

Throws:

Exception

forwardCursor

public IndexCursor<K,O,Long> forwardCursor()
                                    throws Exception

Specified by:

forwardCursor in interface Index<K,O,Long>

Throws:

Exception

forwardCursor

public IndexCursor<K,O,Long> forwardCursor(K key)
                                    throws Exception

Specified by:

forwardCursor in interface Index<K,O,Long>

Throws:

Exception

forwardGreaterOrEq

public boolean forwardGreaterOrEq(K attrVal)
                           throws Exception

Specified by:

forwardGreaterOrEq in interface Index<K,O,Long>

Throws:

Exception

forwardGreaterOrEq

public boolean forwardGreaterOrEq(K attrVal,
                         Long id)
                           throws Exception

Specified by:

forwardGreaterOrEq in interface Index<K,O,Long>

Throws:

Exception

forwardLessOrEq

public boolean forwardLessOrEq(K attrVal)
                        throws Exception

Specified by:

forwardLessOrEq in interface Index<K,O,Long>

Throws:

Exception

forwardLessOrEq

public boolean forwardLessOrEq(K attrVal,
                      Long id)
                        throws Exception

Specified by:

forwardLessOrEq in interface Index<K,O,Long>

Throws:

Exception

forwardLookup

public Long forwardLookup(K attrVal)
                   throws Exception

Specified by:

forwardLookup in interface Index<K,O,Long>

Throws:

Exception

forwardValueCursor

public org.apache.directory.shared.ldap.cursor.Cursor<Long> forwardValueCursor(K key)
                                                                        throws Exception

Specified by:

forwardValueCursor in interface Index<K,O,Long>

Throws:

Exception

getAttribute

public org.apache.directory.shared.ldap.schema.AttributeType getAttribute()

Gets the attribute this Index is built upon.

Specified by:

getAttribute in interface Index<K,O,Long>

Returns:

the id of the Index's attribute

getAttributeId

public String getAttributeId()

Gets the attribute identifier set at configuration time for this index which may not be the OID but an alias name for the attributeType associated with this Index

Specified by:

getAttributeId in interface Index<K,O,Long>

Returns:

configured attribute oid or alias name

getNormalized

public K getNormalized(K attrVal)
                throws Exception

Gets the normalized value for an attribute.

Specified by:

getNormalized in interface Index<K,O,Long>

Parameters:

attrVal - the user provided value to normalize

Returns:

the normalized value.

Throws:

Exception - if something goes wrong.

greaterThanCount

public int greaterThanCount(K attrVal)
                     throws Exception

Specified by:

greaterThanCount in interface Index<K,O,Long>

Throws:

Exception

isCountExact

public boolean isCountExact()

Checks whether or not calls to count the number of keys greater than or less than the key are exact. Checking to see the number of values greater than or less than some key may be excessively costly. Since this is not a critical function but one that assists in optimizing searches some implementations can just return a worst case (maximum) guess.

Specified by:

isCountExact in interface Index<K,O,Long>

Returns:

true if the count is an exact value or a worst case guess

lessThanCount

public int lessThanCount(K attrVal)
                  throws Exception

Specified by:

lessThanCount in interface Index<K,O,Long>

Throws:

Exception

reverse

public boolean reverse(Long id)
                throws Exception

Specified by:

reverse in interface Index<K,O,Long>

Throws:

Exception

reverse

public boolean reverse(Long id,
              K attrVal)
                throws Exception

Specified by:

reverse in interface Index<K,O,Long>

Throws:

Exception

reverseCursor

public IndexCursor<K,O,Long> reverseCursor()
                                    throws Exception

Specified by:

reverseCursor in interface Index<K,O,Long>

Throws:

Exception

reverseCursor

public IndexCursor<K,O,Long> reverseCursor(Long id)
                                    throws Exception

Specified by:

reverseCursor in interface Index<K,O,Long>

Throws:

Exception

reverseGreaterOrEq

public boolean reverseGreaterOrEq(Long id)
                           throws Exception

Specified by:

reverseGreaterOrEq in interface Index<K,O,Long>

Throws:

Exception

reverseGreaterOrEq

public boolean reverseGreaterOrEq(Long id,
                         K attrVal)
                           throws Exception

Specified by:

reverseGreaterOrEq in interface Index<K,O,Long>

Throws:

Exception

reverseLessOrEq

public boolean reverseLessOrEq(Long id)
                        throws Exception

Specified by:

reverseLessOrEq in interface Index<K,O,Long>

Throws:

Exception

reverseLessOrEq

public boolean reverseLessOrEq(Long id,
                      K attrVal)
                        throws Exception

Specified by:

reverseLessOrEq in interface Index<K,O,Long>

Throws:

Exception

reverseLookup

public K reverseLookup(Long id)
                throws Exception

Specified by:

reverseLookup in interface Index<K,O,Long>

Throws:

Exception

reverseValueCursor

public org.apache.directory.shared.ldap.cursor.Cursor<K> reverseValueCursor(Long id)
                                                                     throws Exception

Specified by:

reverseValueCursor in interface Index<K,O,Long>

Throws:

Exception

setAttributeId

public void setAttributeId(String attributeId)

Sets the attribute identifier set at configuration time for this index which may not be the OID but an alias name for the attributeType associated with this Index

Specified by:

setAttributeId in interface Index<K,O,Long>

Parameters:

attributeId - configured attribute oid or alias name

setWkDirPath

public void setWkDirPath(File wkDirPath)

throws UnsupportedOperationException cause it is a in-memory index

Specified by:

setWkDirPath in interface Index<K,O,Long>

Parameters:

wkDirPath - optional working directory path

getWkDirPath

public File getWkDirPath()

this method always returns null for AvlIndex cause this is a in-memory index.

Specified by:

getWkDirPath in interface Index<K,O,Long>

Returns:

optional working directory path

setCacheSize

public void setCacheSize(int cacheSize)

throws UnsupportedOperationException cause it is a in-memory index

Specified by:

setCacheSize in interface Index<K,O,Long>

Parameters:

cacheSize - the size of the index cache

getCacheSize

public int getCacheSize()

Description copied from interface: Index

Gets the size of the index cache in terms of the number of index entries to be cached.

Specified by:

getCacheSize in interface Index<K,O,Long>

Returns:

the size of the index cache

sync

public void sync()
          throws Exception

Specified by:

sync in interface Index<K,O,Long>

Throws:

Exception