Author: mes
Date: 2012-04-09 13:37:10 -0700 (Mon, 09 Apr 2012)
New Revision: 28770
Modified:
core3/impl/trunk/model-impl/impl/src/main/java/org/cytoscape/model/internal/LongTHash.java
core3/impl/trunk/model-impl/impl/src/test/java/org/cytoscape/model/internal/LongTHashTest.java
Log:
fixes: 849 This updates the hash to deal with deletions better. There may
still be problems here.
Modified:
core3/impl/trunk/model-impl/impl/src/main/java/org/cytoscape/model/internal/LongTHash.java
===================================================================
---
core3/impl/trunk/model-impl/impl/src/main/java/org/cytoscape/model/internal/LongTHash.java
2012-04-09 19:31:49 UTC (rev 28769)
+++
core3/impl/trunk/model-impl/impl/src/main/java/org/cytoscape/model/internal/LongTHash.java
2012-04-09 20:37:10 UTC (rev 28770)
@@ -82,6 +82,10 @@
private final Class<T> clazz;
+ private static final int REUSABLE = -1;
+ private static final int UNSET = -2;
+ private static final int FIRST_AVAILABLE = 0;
+
/**
* Creates a new hashtable.
*/
@@ -93,10 +97,10 @@
m_thresholdSize = (int) (THRESHOLD_FACTOR * (double)
m_keys.length);
for (int i = 0; i < m_keys.length; i++)
- m_keys[i] = -1;
+ m_keys[i] = UNSET;
- m_prevKey = -1;
- m_prevInx = -1;
+ m_prevKey = UNSET;
+ m_prevInx = UNSET;
}
/**
@@ -113,14 +117,18 @@
if (key < 0)
throw new IllegalArgumentException("key is negative");
+ //System.err.println("put " + key + " -> " + value);
+
if (key != m_prevKey) {
- calcPrevInx(key);
+ calcPrevInx(key,FIRST_AVAILABLE);
m_prevKey = key;
}
final Object returnVal = m_vals[m_prevInx];
+ //System.err.println("put m_prevInx:" + m_prevInx + " val: " +
returnVal);
if (returnVal == null) {
+ //System.err.println(" entering null");
if (m_elements == m_thresholdSize) {
incrSize();
@@ -132,13 +140,21 @@
m_vals[m_prevInx] = value;
if ( value == null )
- m_keys[m_prevInx] = -1;
+ m_keys[m_prevInx] = REUSABLE;
else
m_keys[m_prevInx] = key;
+ //dump("put");
+
return clazz.cast(returnVal);
}
+ private void dump(String s) {
+ System.err.println(s + " m_prevInx: " + m_prevInx);
+ System.err.println(s + " m_keys: " +
java.util.Arrays.toString(m_keys));
+ System.err.println(s + " m_vals: " +
java.util.Arrays.toString(m_vals));
+ }
+
/**
* Returns the value bound to the specified key or null if no value is
* currently bound to the specified key.<p>
@@ -149,19 +165,23 @@
public final T get(final long key) {
if (key < 0)
return null;
+ //System.err.println("get " + key );
if (key != m_prevKey) {
- calcPrevInx(key);
+ calcPrevInx(key,REUSABLE);
m_prevKey = key;
}
+ //dump("get");
return clazz.cast(m_vals[m_prevInx]);
}
public final T remove(final long key) {
+ //System.err.println("remove " + key );
Object ret = get(key);
put(key,null);
m_elements--;
+ //dump("remove");
return clazz.cast(ret);
}
@@ -170,14 +190,22 @@
return m_elements;
}
- private void calcPrevInx(long key) {
+ // The threshold value determines when to stop searching for an index.
+ // If threshold is set to 0, it will stop at the first unset entry (used
+ // for putting new values into the hash). If the threshold is set to
-1,
+ // then it will search all available indices (used for getting values
from
+ // the hash).
+ private void calcPrevInx(long key, int threshold) {
int incr = 0;
for (m_prevInx = (int)(key % (long)m_keys.length);
- (m_keys[m_prevInx] >= 0) && (m_keys[m_prevInx] != key);
- m_prevInx = (m_prevInx + incr) % m_keys.length)
- if (incr == 0)
+ (m_keys[m_prevInx] >= threshold) && (m_keys[m_prevInx] !=
key);
+ m_prevInx = (m_prevInx + incr) % m_keys.length) {
+ //System.err.println(" m_prevInx: " + m_prevInx);
+ if (incr == 0) {
incr = 1 + (int)(key % ((long)m_keys.length -
1));
+ }
+ }
}
private final void incrSize() {
@@ -198,7 +226,7 @@
final Object[] newVals = new Object[newSize];
for (int i = 0; i < newKeys.length; i++)
- newKeys[i] = -1L;
+ newKeys[i] = UNSET;
m_thresholdSize = (int) (THRESHOLD_FACTOR * (double)
newKeys.length);
@@ -211,7 +239,8 @@
incr = 0;
- for (newIndex = (int)(m_keys[oldIndex] %
(long)newKeys.length); newKeys[newIndex] >= 0;
+ for (newIndex = (int)(m_keys[oldIndex] %
(long)newKeys.length);
+ newKeys[newIndex] >= 0;
newIndex = (newIndex + incr) % newKeys.length)
if (incr == 0)
incr = 1 + ((int)(m_keys[oldIndex] %
(long)(newKeys.length - 1)));
@@ -222,7 +251,8 @@
m_keys = newKeys;
m_vals = newVals;
- m_prevKey = -1;
- m_prevInx = -1;
+ m_prevKey = UNSET;
+ m_prevInx = UNSET;
+ //dump("incrSize");
}
}
Modified:
core3/impl/trunk/model-impl/impl/src/test/java/org/cytoscape/model/internal/LongTHashTest.java
===================================================================
---
core3/impl/trunk/model-impl/impl/src/test/java/org/cytoscape/model/internal/LongTHashTest.java
2012-04-09 19:31:49 UTC (rev 28769)
+++
core3/impl/trunk/model-impl/impl/src/test/java/org/cytoscape/model/internal/LongTHashTest.java
2012-04-09 20:37:10 UTC (rev 28770)
@@ -77,7 +77,7 @@
ith.put(6L,"smithers");
}
- //@Test
+ @Test
public void testTicket849() {
LongTHash<String> hash = new LongTHash<String>(String.class);
hash.put(3476L, "A");
@@ -90,4 +90,21 @@
hash.remove(3490L);
assertEquals("F", hash.get(3491L));
}
+
+ @Test
+ public void testForceResize() {
+ LongTHash<String> hash = new LongTHash<String>(String.class);
+ hash.put(0L, "A");
+ hash.put(1L, "A");
+ hash.put(2L, "A");
+ hash.put(3L, "A");
+ hash.put(4L, "A");
+ hash.put(5L, "A");
+ hash.put(6L, "A");
+ hash.put(7L, "A");
+ hash.put(8L, "A");
+ hash.put(9L, "A");
+ hash.put(10L, "A");
+ hash.put(11L, "A");
+ }
}
--
You received this message because you are subscribed to the Google Groups
"cytoscape-cvs" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/cytoscape-cvs?hl=en.
