Mega Code Archive
Hash map for counting references to Object keys
<![CDATA[
/*
* Copyright (c) 2006-2007, Dennis M. Sosnoski. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
* following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this list of conditions and the following
* disclaimer. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
* following disclaimer in the documentation and/or other materials provided with the distribution. Neither the name of
* JiBX nor the names of its contributors may be used to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
import java.util.Iterator;
/**
* Hash map for counting references to <code>Object</code> 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
*/
public class ReferenceCountMap
{
/** Default fill fraction allowed before growing table. */
private static final double DEFAULT_FILL = 0.3d;
/** Minimum size used for hash table. */
private static final int MINIMUM_SIZE = 63;
/** Number of entries present in table. */
private int m_entryCount;
/** Entries allowed before growing table. */
private int m_entryLimit;
/** Size of array used for keys. */
private int m_arraySize;
/** Offset added (modulo table size) to slot number on collision. */
private int m_hitOffset;
/** Array of key table slots. */
private Object[] m_keyTable;
/** Array of value table slots. */
private int[] m_valueTable;
/**
* Constructor with count.
*
* @param count number of values to assume in initial sizing of table
*/
public ReferenceCountMap(int count) {
// compute initial table size (ensuring odd)
m_arraySize = Math.max((int)(count / DEFAULT_FILL), MINIMUM_SIZE);
m_arraySize += (m_arraySize + 1) % 2;
// initialize the table information
m_entryLimit = (int)(m_arraySize * DEFAULT_FILL);
m_hitOffset = m_arraySize / 2;
m_keyTable = new Object[m_arraySize];
m_valueTable = new int[m_arraySize];
}
/**
* Default constructor.
*/
public ReferenceCountMap() {
this(0);
}
/**
* Copy (clone) constructor.
*
* @param base instance being copied
*/
public ReferenceCountMap(ReferenceCountMap base) {
// copy the basic occupancy information
m_entryCount = base.m_entryCount;
m_entryLimit = base.m_entryLimit;
m_arraySize = base.m_arraySize;
m_hitOffset = base.m_hitOffset;
// copy table of items
m_keyTable = new Object[m_arraySize];
System.arraycopy(base.m_keyTable, 0, m_keyTable, 0, m_arraySize);
m_valueTable = new int[m_arraySize];
System.arraycopy(base.m_valueTable, 0, m_valueTable, 0, m_arraySize);
}
/**
* Step the slot number for an entry. Adds the collision offset (modulo the table size) to the slot number.
*
* @param slot slot number to be stepped
* @return stepped slot number
*/
private final int stepSlot(int slot) {
return (slot + m_hitOffset) % m_arraySize;
}
/**
* 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.
*
* @param slot initial slot computed from key
* @return slot at which entry was added
*/
private final int freeSlot(int slot) {
while (m_keyTable[slot] != null) {
slot = stepSlot(slot);
}
return slot;
}
/**
* Standard base slot computation for a key.
*
* @param key key value to be computed
* @return base slot for key
*/
private final int standardSlot(Object key) {
return (key.hashCode() & Integer.MAX_VALUE) % m_arraySize;
}
/**
* Standard find key in table. This method may be used directly for key lookup using either the
* <code>hashCode()</code> method defined for the key objects or the <code>System.identityHashCode()</code>
* method, and either the <code>equals()</code> method defined for the key objects or the <code>==</code>
* 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.
*
* @param key to be found in table
* @return index of matching key, or <code>-index-1</code> of slot to be used for inserting key in table if not
* already present (always negative)
*/
private int standardFind(Object key) {
// find the starting point for searching table
int slot = standardSlot(key);
// scan through table to find target key
while (m_keyTable[slot] != null) {
// check if we have a match on target key
if (m_keyTable[slot].equals(key)) {
return slot;
} else {
slot = stepSlot(slot);
}
}
return -slot - 1;
}
/**
* 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.
*
* @param slot position of entry to be reinserted into hash map
* @return <code>true</code> if the slot number used by the entry has has changed, <code>false</code> if not
*/
private boolean reinsert(int slot) {
Object key = m_keyTable[slot];
m_keyTable[slot] = null;
return assignSlot(key, m_valueTable[slot]) != slot;
}
/**
* Internal remove pair from the table. Removes the pair from the table by setting the key entry to
* <code>null</code> 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 <code>null</code> before this method is called.
*
* @param slot index number of pair to be removed
*/
private void internalRemove(int slot) {
// delete pair from table
m_keyTable[slot] = null;
m_entryCount--;
while (m_keyTable[(slot = stepSlot(slot))] != null) {
// reinsert current entry in table to fill holes
reinsert(slot);
}
}
/**
* 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.
*
* @param keys array of keys
* @param values array of values
*/
private void restructure(Object[] keys, int[] values) {
for (int i = 0; i < keys.length; i++) {
if (keys[i] != null) {
assignSlot(keys[i], values[i]);
}
}
}
/**
* 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.
*
* @param key to be added to table
* @param value associated value for key
* @return slot at which entry was added
*/
private int assignSlot(Object key, int value) {
int offset = freeSlot(standardSlot(key));
m_keyTable[offset] = key;
m_valueTable[offset] = value;
return offset;
}
/**
* 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.
*
* @param key referenced object (non-<code>null</code>)
* @return incremented use count
*/
public int incrementCount(Object key) {
// first validate the parameters
if (key == null) {
throw new IllegalArgumentException("null key not supported");
} else {
// check space available
int min = m_entryCount + 1;
if (min > m_entryLimit) {
// find the array size required
int size = m_arraySize;
int limit = m_entryLimit;
while (limit < min) {
size = size * 2 + 1;
limit = (int)(size * DEFAULT_FILL);
}
// set parameters for new array size
m_arraySize = size;
m_entryLimit = limit;
m_hitOffset = size / 2;
// restructure for larger arrays
Object[] keys = m_keyTable;
m_keyTable = new Object[m_arraySize];
int[] values = m_valueTable;
m_valueTable = new int[m_arraySize];
restructure(keys, values);
}
// find slot of table
int offset = standardFind(key);
if (offset >= 0) {
// replace existing value for key
return ++m_valueTable[offset];
} else {
// add new pair to table
m_entryCount++;
offset = -offset - 1;
m_keyTable[offset] = key;
m_valueTable[offset] = 1;
return 1;
}
}
}
/**
* Find an entry in the table.
*
* @param key key for entry to be returned
* @return value for key, or zero if key not found
*/
public final int getCount(Object key) {
int slot = standardFind(key);
if (slot >= 0) {
return m_valueTable[slot];
} else {
return 0;
}
}
/**
* Get number of entries in map.
*
* @return entry count
*/
public int size() {
return m_entryCount;
}
/**
* Get iterator for keys in map. The returned iterator is not safe, so the iterator behavior is undefined if the map
* is modified.
*
* @return iterator
*/
public Iterator iterator() {
return SparseArrayIterator.buildIterator(m_keyTable);
}
/**
* Get array of keys in map.
*
* @return key array
*/
public Object[] keyArray() {
Object[] keys = new Object[m_entryCount];
int fill = 0;
for (int i = 0; i < m_arraySize; i++) {
if (m_keyTable[i] != null) {
keys[fill++] = m_keyTable[i];
}
}
return keys;
}
/**
* Construct a copy of the table.
*
* @return shallow copy of table
*/
public Object clone() {
return new ReferenceCountMap(this);
}
/**
* Clear all keys and counts.
*/
public void clear() {
for (int i = 0; i < m_keyTable.length; i++) {
if (m_keyTable[i] != null) {
m_keyTable[i] = null;
m_valueTable[i] = 0;
}
}
}
}
/*
* Copyright (c) 2000-2007, Dennis M. Sosnoski. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer. Redistributions in binary
* form must reproduce the above copyright notice, this list of conditions and
* the following disclaimer in the documentation and/or other materials provided
* with the distribution. Neither the name of JiBX nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
/**
* Iterator class for sparse values in an array. This type of iterator
* can be used for an object array which has references interspersed with
* <code>null</code>s.
*
* @author Dennis M. Sosnoski
*/
class SparseArrayIterator implements Iterator
{
/** Empty iterator. */
public static final SparseArrayIterator EMPTY_ITERATOR =
new SparseArrayIterator(new Object[0]);
/** Array supplying values for iteration. */
private Object[] m_array;
/** Offset of next iteration value. */
private int m_offset;
/**
* Internal constructor.
*
* @param array array containing values to be iterated
*/
private SparseArrayIterator(Object[] array) {
m_array = array;
m_offset = -1;
advance();
}
/**
* Advance to next iteration value. This advances the current position in
* the array to the next non-<code>null</code> value.
*
* @return <code>true</code> if element available, <code>false</code> if
* not
*/
protected boolean advance() {
while (++m_offset < m_array.length) {
if (m_array[m_offset] != null) {
return true;
}
}
return false;
}
/**
* Check for iteration element available.
*
* @return <code>true</code> if element available, <code>false</code> if
* not
*/
public boolean hasNext() {
return m_offset < m_array.length;
}
/**
* Get next iteration element.
*
* @return next iteration element
* @exception NoSuchElementException if past end of iteration
*/
public Object next() {
if (m_offset < m_array.length) {
Object result = m_array[m_offset];
advance();
return result;
} else {
throw new RuntimeException("No such method");
}
}
/**
* Remove element from iteration. This optional operation is not supported
* and always throws an exception.
*
* @exception UnsupportedOperationException for unsupported operation
*/
public void remove() {
throw new UnsupportedOperationException();
}
/**
* Build iterator.
*
* @param array array containing values to be iterated (may be
* <code>null</code>)
* @return constructed iterator
*/
public static Iterator buildIterator(Object[] array) {
if (array == null || array.length == 0) {
return EMPTY_ITERATOR;
} else {
return new SparseArrayIterator(array);
}
}
}
]]>