org.jibx.util
Class ReferenceCountMap

java.lang.Object
  extended by org.jibx.util.ReferenceCountMap

public class ReferenceCountMap
extends java.lang.Object

Hash map for counting references to Object keys. The map implementation is not very efficient when resizing, but works well when the size of the map is known in advance or when accesses are substantially more common than adds.

Author:
Dennis M. Sosnoski

Field Summary
private static double DEFAULT_FILL
          Default fill fraction allowed before growing table.
private  int m_arraySize
          Size of array used for keys.
private  int m_entryCount
          Number of entries present in table.
private  int m_entryLimit
          Entries allowed before growing table.
private  int m_hitOffset
          Offset added (modulo table size) to slot number on collision.
private  java.lang.Object[] m_keyTable
          Array of key table slots.
private  int[] m_valueTable
          Array of value table slots.
private static int MINIMUM_SIZE
          Minimum size used for hash table.
 
Constructor Summary
ReferenceCountMap()
          Default constructor.
ReferenceCountMap(int count)
          Constructor with count.
ReferenceCountMap(ReferenceCountMap base)
          Copy (clone) constructor.
 
Method Summary
private  int assignSlot(java.lang.Object key, int value)
          Assign slot for entry.
 void clear()
          Clear all keys and counts.
 java.lang.Object clone()
          Construct a copy of the table.
private  int freeSlot(int slot)
          Find free slot number for entry.
 int getCount(java.lang.Object key)
          Find an entry in the table.
 int incrementCount(java.lang.Object key)
          Increment a use count in the table.
private  void internalRemove(int slot)
          Internal remove pair from the table.
 java.util.Iterator iterator()
          Get iterator for keys in map.
 java.lang.Object[] keyArray()
          Get array of keys in map.
private  boolean reinsert(int slot)
          Reinsert an entry into the hash map.
private  void restructure(java.lang.Object[] keys, int[] values)
          Restructure the table.
 int size()
          Get number of entries in map.
private  int standardFind(java.lang.Object key)
          Standard find key in table.
private  int standardSlot(java.lang.Object key)
          Standard base slot computation for a key.
private  int stepSlot(int slot)
          Step the slot number for an entry.
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DEFAULT_FILL

private static final double DEFAULT_FILL
Default fill fraction allowed before growing table.

See Also:
Constant Field Values

MINIMUM_SIZE

private static final int MINIMUM_SIZE
Minimum size used for hash table.

See Also:
Constant Field Values

m_entryCount

private int m_entryCount
Number of entries present in table.


m_entryLimit

private int m_entryLimit
Entries allowed before growing table.


m_arraySize

private int m_arraySize
Size of array used for keys.


m_hitOffset

private int m_hitOffset
Offset added (modulo table size) to slot number on collision.


m_keyTable

private java.lang.Object[] m_keyTable
Array of key table slots.


m_valueTable

private int[] m_valueTable
Array of value table slots.

Constructor Detail

ReferenceCountMap

public ReferenceCountMap(int count)
Constructor with count.

Parameters:
count - number of values to assume in initial sizing of table

ReferenceCountMap

public ReferenceCountMap()
Default constructor.


ReferenceCountMap

public ReferenceCountMap(ReferenceCountMap base)
Copy (clone) constructor.

Parameters:
base - instance being copied
Method Detail

stepSlot

private final int stepSlot(int slot)
Step the slot number for an entry. Adds the collision offset (modulo the table size) to the slot number.

Parameters:
slot - slot number to be stepped
Returns:
stepped slot number

freeSlot

private final int freeSlot(int slot)
Find free slot number for entry. Starts at the slot based directly on the hashed key value. If this slot is already occupied, it adds the collision offset (modulo the table size) to the slot number and checks that slot, repeating until an unused slot is found.

Parameters:
slot - initial slot computed from key
Returns:
slot at which entry was added

standardSlot

private final int standardSlot(java.lang.Object key)
Standard base slot computation for a key.

Parameters:
key - key value to be computed
Returns:
base slot for key

standardFind

private int standardFind(java.lang.Object key)
Standard find key in table. This method may be used directly for key lookup using either the hashCode() method defined for the key objects or the System.identityHashCode() method, and either the equals() method defined for the key objects or the == operator, as selected by the hash technique constructor parameter. To implement a hash class based on some other methods of hashing and/or equality testing, define a separate method in the subclass with a different name and use that method instead. This avoids the overhead caused by overrides of a very heavily used method.

Parameters:
key - to be found in table
Returns:
index of matching key, or -index-1 of slot to be used for inserting key in table if not already present (always negative)

reinsert

private boolean reinsert(int slot)
Reinsert an entry into the hash map. This is used when the table is being directly modified, and does not adjust the count present or check the table capacity.

Parameters:
slot - position of entry to be reinserted into hash map
Returns:
true if the slot number used by the entry has has changed, false if not

internalRemove

private void internalRemove(int slot)
Internal remove pair from the table. Removes the pair from the table by setting the key entry to null and adjusting the count present, then chains through the table to reinsert any other pairs which may have collided with the removed pair. If the associated value is an object reference, it should be set to null before this method is called.

Parameters:
slot - index number of pair to be removed

restructure

private void restructure(java.lang.Object[] keys,
                         int[] values)
Restructure the table. This is used when the table is increasing or decreasing in size, and works directly with the old table representation arrays. It inserts pairs from the old arrays directly into the table without adjusting the count present or checking the table size.

Parameters:
keys - array of keys
values - array of values

assignSlot

private int assignSlot(java.lang.Object key,
                       int value)
Assign slot for entry. Starts at the slot found by the hashed key value. If this slot is already occupied, it steps the slot number and checks the resulting slot, repeating until an unused slot is found. This method does not check for duplicate keys, so it should only be used for internal reordering of the tables.

Parameters:
key - to be added to table
value - associated value for key
Returns:
slot at which entry was added

incrementCount

public int incrementCount(java.lang.Object key)
Increment a use count in the table. If the key object is already present in the table this adds one to the reference count; if not present, this adds the key with an initial reference count of one.

Parameters:
key - referenced object (non-null)
Returns:
incremented use count

getCount

public final int getCount(java.lang.Object key)
Find an entry in the table.

Parameters:
key - key for entry to be returned
Returns:
value for key, or zero if key not found

size

public int size()
Get number of entries in map.

Returns:
entry count

iterator

public java.util.Iterator iterator()
Get iterator for keys in map. The returned iterator is not safe, so the iterator behavior is undefined if the map is modified.

Returns:
iterator

keyArray

public java.lang.Object[] keyArray()
Get array of keys in map.

Returns:
key array

clone

public java.lang.Object clone()
Construct a copy of the table.

Overrides:
clone in class java.lang.Object
Returns:
shallow copy of table

clear

public void clear()
Clear all keys and counts.



Project Web Site