net.sf.ivmaidns.storage
Class HashedStorage

java.lang.Object
  net.sf.ivmaidns.util.ObservedCore
      net.sf.ivmaidns.storage.Storage
          net.sf.ivmaidns.storage.ObjectStorage
              net.sf.ivmaidns.storage.HashedStorage

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, MultiObservable, ReallyCloneable, Sortable, TrimToSizeable, Verifiable

public class HashedStorage
extends ObjectStorage

Class for storage of hashed elements.

Version:

2.0

Author:

Ivan Maidanski

See Also:

Serialized Form

Field Summary

protected int[]	links NOTE: links must be !
protected int	size NOTE: size must be the number of elements in the storage.

Fields inherited from class net.sf.ivmaidns.storage.ObjectStorage

elements

Constructor Summary

HashedStorage()

HashedStorage(java.lang.Object[] initialValues)
NOTE: initialValues must be !

Method Summary

protected static int	addressOf(int hash, int location, int[] links) NOTE: location must be > 0.
java.lang.Object	clone() NOTE: Must be synchronized outside.
int	emptyLocation() NOTE: Result is an empty location (result > 0).
void	integrityCheck() NOTE: Shallow check for integrity of this object.
int	locationOf(java.lang.Object value, int prevLocation, boolean forward) NOTE: value is compared against elements.
protected void	minimizeCapacity() NOTE: Must be synchronized outside.
protected static void	randomize(int[] links, int count) NOTE: Called internally only just before rehashing or if size == 0.
void	rehash() NOTE: The effectiveness is nearly linear.
java.lang.Object	setAt(int location, java.lang.Object value) NOTE: No equals checking is performed here.
int	size() NOTE: Result is the count of elements.

Methods inherited from class net.sf.ivmaidns.storage.ObjectStorage

childLocation, findLessGreater, getAt, insertAt, isValidAt, parentLocation, siblingLocation

Methods inherited from class net.sf.ivmaidns.storage.Storage

add, addAll, addAll, clear, contains, containsAll, containsAll, containsCount, equals, greaterThan, hasChildren, hashCode, insertAtAll, insertAtAll, nextLocation, notifyObservers, notifyObservers, remove, removeAll, removeAll, removeAt, toArray, toInlineString, toOutlineString, toString, trimToSize

Methods inherited from class net.sf.ivmaidns.util.ObservedCore

addObserver, hasObservers, removeObserver

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

links

protected transient int[] links

NOTE: links must be != null, links length == (elements length + 1) * 2 + (2 leftShift ~links[0]), links[0] = seedAndShift, links[1] = emptyLocation() - 1, links[loc * 2] = elements[loc - 1] != null ? elements[loc - 1] hashCode() : -nextEmptyLocation(loc), links[loc * 2 + 1] = elements[loc - 1] != null ? chainNext(loc) : -prevEmptyLocation(loc), links[links length - rootIndex - 1] = chainRoots(rootIndex), where rootIndex = ((links[loc * 2] ^ links[0]) * JavaConsts GOLD_MEDIAN) >>> links[0]. All values in each chain are ordered ascending first by their (signed) hash, and then by their locations. seed and order of empty locations are not serialized.

size

protected transient int size

NOTE: size must be the number of elements in the storage.

Constructor Detail

HashedStorage

public HashedStorage()

HashedStorage

public HashedStorage(java.lang.Object[] initialValues)
              throws java.lang.NullPointerException

NOTE: initialValues must be != null, initialValues[index] may be == null (ignored) for any index. capacity is set to initialValues length, each value from initialValues is added to storage. The effectiveness is nearly linear.

Throws:

java.lang.NullPointerException

Method Detail

size

public final int size()

NOTE: Result is the count of elements. Result >= 0.

minimizeCapacity

protected void minimizeCapacity()

NOTE: Must be synchronized outside.

Overrides:

minimizeCapacity in class ObjectStorage

rehash

public void rehash()

NOTE: The effectiveness is nearly linear. Hash values are not recalculated. Must be synchronized outside.

randomize

protected static final void randomize(int[] links,
                                      int count)
                               throws java.lang.NullPointerException,
                                      java.lang.ArrayIndexOutOfBoundsException

NOTE: Called internally only just before rehashing or if size == 0. NullPointerException and ArrayIndexOutOfBoundsException are thrown only if parameters are bad. Must be synchronized outside.

Throws:

java.lang.NullPointerException

java.lang.ArrayIndexOutOfBoundsException

addressOf

protected static final int addressOf(int hash,
                                     int location,
                                     int[] links)
                              throws java.lang.NullPointerException,
                                     java.lang.ArrayIndexOutOfBoundsException

NOTE: location must be > 0. Result > 0. NullPointerException and ArrayIndexOutOfBoundsException are thrown only if parameters are bad. Must be synchronized outside.

Throws:

java.lang.NullPointerException

java.lang.ArrayIndexOutOfBoundsException

emptyLocation

public final int emptyLocation()

Description copied from class: Storage

NOTE: Result is an empty location (result > 0). Storage state is not altered. The effectiveness is constant (typically). The order of empty locations is undefined. Requires no synchronization.

Overrides:

emptyLocation in class ObjectStorage

setAt

public java.lang.Object setAt(int location,
                              java.lang.Object value)
                       throws java.lang.IllegalArgumentException

NOTE: No equals checking is performed here. The effectiveness is nearly constant (may be linear in the worst case). Observers notification is performed. Must be synchronized outside.

Overrides:

setAt in class ObjectStorage

Throws:

java.lang.IllegalArgumentException

locationOf

public int locationOf(java.lang.Object value,
                      int prevLocation,
                      boolean forward)
               throws java.lang.IllegalArgumentException

NOTE: value is compared against elements. The effectiveness is nearly constant (may be linear in the worst case). Must be synchronized outside.

Overrides:

locationOf in class ObjectStorage

Throws:

java.lang.IllegalArgumentException

clone

public java.lang.Object clone()

NOTE: Must be synchronized outside.

Specified by:

clone in interface ReallyCloneable

Overrides:

clone in class ObjectStorage

Returns:

a copy (may be null) of this instance.

integrityCheck

public void integrityCheck()

NOTE: Shallow check for integrity of this object. Must be synchronized outside. For debug purpose only.

Specified by:

integrityCheck in interface Verifiable

Overrides:

integrityCheck in class ObjectStorage