From c7fd7f1539a47ed9634e3c3183bcf7762065d98d Mon Sep 17 00:00:00 2001 From: adam Date: Sat, 15 Jan 2005 10:10:21 +0000 Subject: [PATCH] fix the total mess in Basket.java darcs-hash:20050115101021-5007d-6f39aa374981ebb746978c66bb24fe583c3c829d.gz --- src/org/ibex/util/Basket.java | 155 +++++++++++++++++++---------------------- src/org/ibex/util/Cache.java | 5 ++ 2 files changed, 75 insertions(+), 85 deletions(-) diff --git a/src/org/ibex/util/Basket.java b/src/org/ibex/util/Basket.java index 648b884..f3b2504 100644 --- a/src/org/ibex/util/Basket.java +++ b/src/org/ibex/util/Basket.java @@ -174,29 +174,24 @@ public interface Basket extends Serializable { * @author adam@ibex.org, crawshaw@ibex.org */ public abstract class Hash implements Basket { - private static final long serialVersionUID = 3948384093L; + static final long serialVersionUID = 3948384093L; /** Used internally to record used slots. */ - protected final Object placeholder = new java.io.Serializable() { - private static final long serialVersionUID = 1331L; - }; + final Object placeholder = new java.io.Serializable() { private static final long serialVersionUID = 1331L; }; /** When loadFactor * usedslots > num_slots, call * rehash(). */ - protected final float loadFactor; + final float loadFactor; /** Used to determine the number of array slots required by each * mapping entry. */ - protected final int indexmultiple; - - /** Number of entries with non-null key (includes placeholder slots). */ - protected int usedslots = 0; - - /** Number of currently available entry slots. */ - protected int numslots = 0; + final int indexmultiple; /** Number of currently active entries. */ - protected int size = 0; + private int size = 0; + + /** Number of placeholders in entries[]. */ + private int placeholders = 0; /** Array of mappings. * @@ -208,24 +203,20 @@ public interface Basket extends Serializable { * Default implementation uses indexmultiple == 1, and * stores only the keys in entries. */ - protected Object[] entries = null; + private Object[] entries = null; + public Hash() { this(16, 0.75F); } + public Hash(int cap, float load) { this(2, cap, load); } public Hash(int indexmultiple, int initialCapacity, float loadFactor) { // using a pseudoprime in the form 4x+3 ensures full coverage - initialCapacity = initialCapacity / 4; - initialCapacity = 4 * initialCapacity + 3; - this.numslots = initialCapacity; + initialCapacity = (initialCapacity / 4) * 4 + 3; this.loadFactor = loadFactor; this.indexmultiple = indexmultiple; - - entries = new Object[initialCapacity * indexmultiple]; + this.entries = new Object[initialCapacity * indexmultiple]; } public int size() { return size; } - public void clear() { - for (int i = usedslots * indexmultiple; i >= 0; i--) entries[i] = null; - size = usedslots = 0; - } + public void clear() { for (int i = 0; i= 0; } @@ -233,41 +224,62 @@ public interface Basket extends Serializable { * containsKey(). For a value map, use Basket.HashMap. */ public boolean containsValue(Object k) { return containsKey(k); } - public void remove(Object k) { remove(indexOf(k)); } + // UGLY + public Object[] dumpkeys() { + Object[] ret = new Object[size]; + int pos = 0; + for(int i=0; i numslots * loadFactor) rehash(); - if (dest >= 0) { // update existing entry - entryUpdated(dest); - } else { // new entry - dest = -1 * dest - 1; - entries[dest] = k; - for (int inc = 1; inc < indexmultiple; inc++) - entries[dest + inc] = null; - entryAdded(dest); - } - return dest; + public Object get(Object key) { return get(key, 0); } + public Object get(Object key, int whichval) { + int i = indexOf(key); + return i >= 0 ? entries[i + 1 + whichval] : null; } - /** Called immediately after the addition of a new entry. */ - protected abstract void entryAdded(int dest); - - /** Called immediately after the update of a current entry. */ - protected abstract void entryUpdated(int dest); + public Object put(Object key, Object value) { return put(key, value, 0); } + public Object put(Object key, Object value, int whichval) { + if (loadFactor * (size + placeholders) > entries.length) rehash(); + int dest = indexOf(key); + Object old = null; + if (dest < 0) { + dest = -1 * (dest + 1); + if (entries[dest] != placeholder) size++; + entries[dest] = key; + for(int i=1; iuserKey is the key * passed to the map, storedKey is from the map. @@ -293,19 +305,19 @@ public interface Basket extends Serializable { *

Uses placeholder as a placeholder object, and * compares keys using equals(Object, Object).

*/ - protected int indexOf(Object k) { + private int indexOf(Object k) { // special case null key if (k == null) return equals(placeholder, entries[0]) ? -1 : 0; int hash = k == null ? 0 : k.hashCode(); - final int orig = Math.abs(hash) % numslots; + final int orig = Math.abs(hash) % (entries.length / indexmultiple); int dest = orig * indexmultiple; int tries = 1; boolean plus = true; while (entries[dest] != null) { if (equals(k, entries[dest])) return dest; - dest = Math.abs((orig + (plus ? 1 : -1) * tries * tries) % numslots) * indexmultiple; + dest = Math.abs((orig + (plus ? 1 : -1) * tries * tries) % (entries.length / indexmultiple)) * indexmultiple; if (plus) tries++; plus = !plus; } @@ -316,56 +328,29 @@ public interface Basket extends Serializable { * set (removes placeholder references) and if necessary * by increasing the size of the entries array. */ - protected void rehash() { - int oldnumslots = numslots; + private void rehash() { Object[] oldentries = entries; + entries = new Object[oldentries.length * indexmultiple]; - if (size * 2 > usedslots) numslots *= 2; - entries = new Object[numslots * indexmultiple]; - - for (int i=0; i < oldnumslots; i++) { + for (int i=0; i < (oldentries.length/indexmultiple); i++) { int pos = i * indexmultiple; if (pos > 0 && oldentries[pos] == null) continue; if (oldentries[pos] == placeholder) continue; // dont adjust any of the support entries int dest = indexOf(oldentries[pos]); - dest = -1 * dest - 1; size++; usedslots++; // always new entry + dest = -1 * dest - 1; size++; // always new entry for (int inc=0; inc < indexmultiple; inc++) entries[dest + inc] = oldentries[pos + inc]; } + placeholders = 0; } } public class HashMap extends Hash implements Map { - private static final long serialVersionUID = 2348905755L; - - public HashMap() { this(16, 0.75F); } - public HashMap(int cap, float load) { super(2, cap, load); } - - public Object get(Object key) { int i = indexOf(key); return i >= 0 ? entries[i + 1] : null; } - public Object put(Object key, Object value) { - Object old = null; - int dest = indexOf(key); - if (dest >= 0) old = entries[(-1 * dest - 1) + 1]; - dest = put(dest, key); - entries[dest + 1] = value; - return old; - } - - protected void entryAdded(int dest) {} - protected void entryUpdated(int dest) {} - protected void entryRemoved(int dest) {} - - public boolean containsKey(Object k) { return super.containsValue(k); } - - public boolean containsValue(Object v) { - for (int i=0; i < numslots; i++) - if ((i == 0 || entries[i * indexmultiple] != null) && // exception for null key - !equals(placeholder, entries[i * indexmultiple]) && - v == null ? entries[i + 1] == null : v.equals(entries[i + 1])) - return true; - return false; - } + public HashMap() { super(); } + public HashMap(int x, float y) { super(x,y); } + public HashMap(int x, int z, float y) { super(x,z,y); } } + } diff --git a/src/org/ibex/util/Cache.java b/src/org/ibex/util/Cache.java index dc903b8..33c04c5 100644 --- a/src/org/ibex/util/Cache.java +++ b/src/org/ibex/util/Cache.java @@ -11,6 +11,10 @@ package org.ibex.util; * @author crawshaw@ibex.org */ public class Cache extends Basket.HashMap { + public Cache(int maxSize, boolean accessOrder) { + super(maxSize * 2, 0.75F); + } + /* private static final long serialVersionUID = 23498092L; private final int maxSize; @@ -64,4 +68,5 @@ public class Cache extends Basket.HashMap { protected void entryUpdated(int i) { if (!accessOrder) { entryRemoved(i); entryAdded(i); } } + */ } -- 1.7.10.4