001package co.codewizards.cloudstore.core.collection; 002 003import static co.codewizards.cloudstore.core.util.Util.*; 004import static java.util.Objects.*; 005 006import java.io.Serializable; 007import java.lang.ref.Reference; 008import java.lang.ref.ReferenceQueue; 009import java.lang.ref.WeakReference; 010import java.lang.reflect.Array; 011import java.util.AbstractMap; 012import java.util.AbstractSet; 013import java.util.Collection; 014import java.util.HashMap; 015import java.util.Iterator; 016import java.util.Map; 017import java.util.NoSuchElementException; 018import java.util.Set; 019 020import co.codewizards.cloudstore.core.ref.IdentityWeakReference; 021 022public class WeakIdentityHashMap<K, V> implements Map<K, V>, Serializable { 023 private static final long serialVersionUID = 1L; 024 025 private final ReferenceQueue<K> keyRefQueue = new ReferenceQueue<K>(); 026 private final HashMap<Reference<K>, V> delegate; 027 private transient Set<Map.Entry<K, V>> entrySet; 028 029 public WeakIdentityHashMap() { 030 delegate = new HashMap<>(); 031 } 032 033 public WeakIdentityHashMap(int initialCapacity) { 034 delegate = new HashMap<>(initialCapacity); 035 } 036 037 public WeakIdentityHashMap(final Map<? extends K, ? extends V> map) { 038 this(requireNonNull(map, "map").size()); 039 putAll(map); 040 } 041 042 public WeakIdentityHashMap(int initialCapacity, float loadFactor) { 043 delegate = new HashMap<>(initialCapacity, loadFactor); 044 } 045 046 @Override 047 public V get(final Object key) { 048 expunge(); 049 @SuppressWarnings("unchecked") 050 final WeakReference<K> keyRef = createReference((K) key); 051 return delegate.get(keyRef); 052 } 053 054 @Override 055 public V put(final K key, final V value) { 056 expunge(); 057 requireNonNull(key, "key"); 058 final WeakReference<K> keyRef = createReference(key, keyRefQueue); 059 return delegate.put(keyRef, value); 060 } 061 062 @Override 063 public void putAll(final Map<? extends K, ? extends V> map) { 064 expunge(); 065 requireNonNull(map, "map"); 066 for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 067 final K key = entry.getKey(); 068 requireNonNull(key, "entry.key"); 069 final WeakReference<K> keyRef = createReference(key, keyRefQueue); 070 delegate.put(keyRef, entry.getValue()); 071 } 072 } 073 074 @Override 075 public V remove(final Object key) { 076 expunge(); 077 @SuppressWarnings("unchecked") 078 final WeakReference<K> keyref = createReference((K) key); 079 return delegate.remove(keyref); 080 } 081 082 @Override 083 public void clear() { 084 expunge(); 085 delegate.clear(); 086 } 087 088 @Override 089 public int size() { 090 expunge(); 091 return delegate.size(); 092 } 093 094 @Override 095 public boolean isEmpty() { 096 expunge(); 097 return delegate.isEmpty(); 098 } 099 100 @Override 101 public boolean containsKey(final Object key) { 102 expunge(); 103 @SuppressWarnings("unchecked") 104 final WeakReference<K> keyRef = createReference((K) key); 105 return delegate.containsKey(keyRef); 106 } 107 108 @Override 109 public boolean containsValue(final Object value) { 110 expunge(); 111 return delegate.containsValue(value); 112 } 113 114 @Override 115 public Set<K> keySet() { 116 expunge(); 117 throw new UnsupportedOperationException("NYI"); // TODO implement this! It should be backed! Read javadoc for the proper contract! 118 } 119 120 @Override 121 public Collection<V> values() { 122 expunge(); 123 return delegate.values(); 124 } 125 126 @Override 127 public Set<Map.Entry<K,V>> entrySet() { 128 expunge(); 129 Set<Map.Entry<K,V>> es = entrySet; 130 if (es != null) 131 return es; 132 else 133 return entrySet = new EntrySet(); 134 } 135 136 private class EntrySet extends AbstractSet<Map.Entry<K, V>> { 137 @Override 138 public Iterator<Map.Entry<K,V>> iterator() { 139 return new EntryIterator(); 140 } 141 142 @Override 143 public boolean contains(Object o) { 144 if (! (o instanceof Map.Entry)) 145 return false; 146 147 @SuppressWarnings("unchecked") 148 final Map.Entry<K, V> entry = (Map.Entry<K, V>)o; 149 150 final K keyParam = entry.getKey(); 151 if (! WeakIdentityHashMap.this.containsKey(keyParam)) 152 return false; 153 154 final V value = WeakIdentityHashMap.this.get(keyParam); 155 return equal(value, entry.getValue()); 156 } 157 158 @Override 159 public boolean remove(Object o) { 160 if (!(o instanceof Map.Entry)) 161 return false; 162 163 @SuppressWarnings("unchecked") 164 final Map.Entry<K, V> entry = (Map.Entry<K, V>)o; 165 166 final K keyParam = entry.getKey(); 167 168 if (! WeakIdentityHashMap.this.containsKey(keyParam)) 169 return false; 170 171 WeakIdentityHashMap.this.remove(keyParam); 172 return true; 173 } 174 175 @Override 176 public int size() { 177 return WeakIdentityHashMap.this.size(); 178 } 179 180 @Override 181 public void clear() { 182 WeakIdentityHashMap.this.clear(); 183 } 184 185 /* 186 * Must revert from AbstractSet's impl to AbstractCollection's, as 187 * the former contains an optimization that results in incorrect 188 * behavior when c is a smaller "normal" (non-identity-based) Set. 189 */ 190 @Override 191 public boolean removeAll(Collection<?> c) { 192 boolean modified = false; 193 for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); ) { 194 if (c.contains(i.next())) { 195 i.remove(); 196 modified = true; 197 } 198 } 199 return modified; 200 } 201 202 @Override 203 public Object[] toArray() { 204 int size = size(); 205 Object[] result = new Object[size]; 206 Iterator<Map.Entry<K,V>> it = iterator(); 207 for (int i = 0; i < size; i++) 208 result[i] = new AbstractMap.SimpleEntry<>(it.next()); 209 return result; 210 } 211 212 @Override 213 @SuppressWarnings("unchecked") 214 public <T> T[] toArray(T[] a) { 215 int size = size(); 216 if (a.length < size) a = (T[]) Array.newInstance(a.getClass().getComponentType(), size); 217 Iterator<Map.Entry<K,V>> it = iterator(); 218 for (int i = 0; i < size; i++) 219 a[i] = (T) new AbstractMap.SimpleEntry<>(it.next()); 220 if (a.length > size) 221 a[size] = null; 222 return a; 223 } 224 } 225 226 private class EntryIterator implements Iterator<Map.Entry<K, V>> { 227 private final Iterator<Map.Entry<Reference<K>, V>> delegateIterator = delegate.entrySet().iterator(); 228 private Map.Entry<K, V> nextEntry; 229 230 @Override 231 public boolean hasNext() { 232 if (nextEntry != null) 233 return true; 234 235 nextEntry = pullNext(); 236 return nextEntry != null; 237 } 238 239 @Override 240 public Map.Entry<K, V> next() throws NoSuchElementException { 241 Map.Entry<K, V> result = nextEntry; 242 nextEntry = null; 243 244 if (result == null) { 245 result = pullNext(); 246 247 if (result == null) 248 throw new NoSuchElementException(); 249 } 250 return result; 251 } 252 253 private Map.Entry<K, V> pullNext() { 254 while (delegateIterator.hasNext()) { 255 final Map.Entry<Reference<K>, V> delegateNext = delegateIterator.next(); 256 final K key = delegateNext.getKey().get(); 257 if (key != null) { 258 final V value = delegateNext.getValue(); 259 return new AbstractMap.SimpleEntry<K, V>(key, value) { 260 private static final long serialVersionUID = 1L; 261 @Override 262 public V setValue(V value) { 263 return delegateNext.setValue(value); 264 } 265 }; 266 } 267 } 268 return null; 269 } 270 271 @Override 272 public void remove() throws IllegalStateException { 273 delegateIterator.remove(); 274 } 275 } 276 277 private void expunge() { 278 Reference<? extends K> keyRef; 279 while ((keyRef = keyRefQueue.poll()) != null) 280 delegate.remove(keyRef); 281 } 282 283 private WeakReference<K> createReference(K referent) { 284 return new IdentityWeakReference<K>(referent); 285 } 286 287 private WeakReference<K> createReference(K referent, ReferenceQueue<K> q) { 288 return new IdentityWeakReference<K>(referent, q); 289 } 290}