diff options
Diffstat (limited to 'src/com/iciql/util/WeakIdentityHashMap.java')
| -rw-r--r-- | src/com/iciql/util/WeakIdentityHashMap.java | 243 |
1 files changed, 243 insertions, 0 deletions
diff --git a/src/com/iciql/util/WeakIdentityHashMap.java b/src/com/iciql/util/WeakIdentityHashMap.java new file mode 100644 index 0000000..bc03cd0 --- /dev/null +++ b/src/com/iciql/util/WeakIdentityHashMap.java @@ -0,0 +1,243 @@ +/*
+ * Copyright 2004-2011 H2 Group.
+ * Copyright 2011 James Moger.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.iciql.util;
+
+import java.lang.ref.WeakReference;
+import java.util.Collection;
+import java.util.Map;
+import java.util.Set;
+
+import com.iciql.IciqlException;
+
+/**
+ * This hash map uses weak references, so that elements that are no longer
+ * referenced elsewhere can be garbage collected. It also uses object identity
+ * to compare keys. The garbage collection happens when trying to add new data,
+ * or when resizing.
+ *
+ * @param <K>
+ * the keys
+ * @param <V>
+ * the value
+ */
+
+public class WeakIdentityHashMap<K, V> implements Map<K, V> {
+
+ private static final int MAX_LOAD = 90;
+ private static final WeakReference<Object> DELETED_KEY = new WeakReference<Object>(null);
+ private int mask, len, size, deletedCount, level;
+ private int maxSize, minSize, maxDeleted;
+ private WeakReference<K>[] keys;
+ private V[] values;
+
+ public WeakIdentityHashMap() {
+ reset(2);
+ }
+
+ public int size() {
+ return size;
+ }
+
+ private void checkSizePut() {
+ if (deletedCount > size) {
+ rehash(level);
+ }
+ if (size + deletedCount >= maxSize) {
+ rehash(level + 1);
+ }
+ }
+
+ private void checkSizeRemove() {
+ if (size < minSize && level > 0) {
+ rehash(level - 1);
+ } else if (deletedCount > maxDeleted) {
+ rehash(level);
+ }
+ }
+
+ private int getIndex(Object key) {
+ return System.identityHashCode(key) & mask;
+ }
+
+ @SuppressWarnings("unchecked")
+ private void reset(int newLevel) {
+ minSize = size * 3 / 4;
+ size = 0;
+ level = newLevel;
+ len = 2 << level;
+ mask = len - 1;
+ maxSize = (int) (len * MAX_LOAD / 100L);
+ deletedCount = 0;
+ maxDeleted = 20 + len / 2;
+ keys = new WeakReference[len];
+ values = (V[]) new Object[len];
+ }
+
+ public V put(K key, V value) {
+ checkSizePut();
+ int index = getIndex(key);
+ int plus = 1;
+ int deleted = -1;
+ do {
+ WeakReference<K> k = keys[index];
+ if (k == null) {
+ // found an empty record
+ if (deleted >= 0) {
+ index = deleted;
+ deletedCount--;
+ }
+ size++;
+ keys[index] = new WeakReference<K>(key);
+ values[index] = value;
+ return null;
+ } else if (k == DELETED_KEY) {
+ if (deleted < 0) {
+ // found the first deleted record
+ deleted = index;
+ }
+ } else {
+ Object r = k.get();
+ if (r == null) {
+ delete(index);
+ } else if (r == key) {
+ // update existing
+ V old = values[index];
+ values[index] = value;
+ return old;
+ }
+ }
+ index = (index + plus++) & mask;
+ } while (plus <= len);
+ throw new IciqlException("Hashmap is full");
+ }
+
+ public V remove(Object key) {
+ checkSizeRemove();
+ int index = getIndex(key);
+ int plus = 1;
+ do {
+ WeakReference<K> k = keys[index];
+ if (k == null) {
+ // found an empty record
+ return null;
+ } else if (k == DELETED_KEY) {
+ // continue
+ } else {
+ Object r = k.get();
+ if (r == null) {
+ delete(index);
+ } else if (r == key) {
+ // found the record
+ V old = values[index];
+ delete(index);
+ return old;
+ }
+ }
+ index = (index + plus++) & mask;
+ k = keys[index];
+ } while (plus <= len);
+ // not found
+ return null;
+ }
+
+ @SuppressWarnings("unchecked")
+ private void delete(int index) {
+ keys[index] = (WeakReference<K>) DELETED_KEY;
+ values[index] = null;
+ deletedCount++;
+ size--;
+ }
+
+ private void rehash(int newLevel) {
+ WeakReference<K>[] oldKeys = keys;
+ V[] oldValues = values;
+ reset(newLevel);
+ for (int i = 0; i < oldKeys.length; i++) {
+ WeakReference<K> k = oldKeys[i];
+ if (k != null && k != DELETED_KEY) {
+ K key = k.get();
+ if (key != null) {
+ put(key, oldValues[i]);
+ }
+ }
+ }
+ }
+
+ public V get(Object key) {
+ int index = getIndex(key);
+ int plus = 1;
+ do {
+ WeakReference<K> k = keys[index];
+ if (k == null) {
+ return null;
+ } else if (k == DELETED_KEY) {
+ // continue
+ } else {
+ Object r = k.get();
+ if (r == null) {
+ delete(index);
+ } else if (r == key) {
+ return values[index];
+ }
+ }
+ index = (index + plus++) & mask;
+ } while (plus <= len);
+ return null;
+ }
+
+ public void clear() {
+ reset(2);
+ }
+
+ public boolean containsKey(Object key) {
+ return get(key) != null;
+ }
+
+ public boolean containsValue(Object value) {
+ if (value == null) {
+ return false;
+ }
+ for (V item : values) {
+ if (value.equals(item)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public Set<java.util.Map.Entry<K, V>> entrySet() {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean isEmpty() {
+ return size == 0;
+ }
+
+ public Set<K> keySet() {
+ throw new UnsupportedOperationException();
+ }
+
+ public void putAll(Map<? extends K, ? extends V> m) {
+ throw new UnsupportedOperationException();
+ }
+
+ public Collection<V> values() {
+ throw new UnsupportedOperationException();
+ }
+
+}
|