-
-
Save pcan/16faf4e59942678377e0 to your computer and use it in GitHub Desktop.
/* | |
* Copyright (c) 2019 Pierantonio Cangianiello | |
* | |
* MIT License | |
* | |
* Permission is hereby granted, free of charge, to any person obtaining a copy | |
* of this software and associated documentation files (the "Software"), to deal | |
* in the Software without restriction, including without limitation the rights | |
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
* copies of the Software, and to permit persons to whom the Software is | |
* furnished to do so, subject to the following conditions: | |
* | |
* The above copyright notice and this permission notice shall be included in all | |
* copies or substantial portions of the Software. | |
* | |
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE | |
* SOFTWARE. | |
*/ | |
import java.util.Collection; | |
import java.util.Map; | |
import java.util.Map.Entry; | |
import java.util.Set; | |
import java.util.WeakHashMap; | |
import java.util.concurrent.ConcurrentHashMap; | |
import java.util.concurrent.DelayQueue; | |
import java.util.concurrent.Delayed; | |
import java.util.concurrent.TimeUnit; | |
/** | |
* A HashMap which entries expires after the specified life time. | |
* The life-time can be defined on a per-key basis, or using a default one, that is passed to the | |
* constructor. | |
* | |
* @author Pierantonio Cangianiello | |
* @param <K> the Key type | |
* @param <V> the Value type | |
*/ | |
public class SelfExpiringHashMap<K, V> implements SelfExpiringMap<K, V> { | |
private final Map<K, V> internalMap; | |
private final Map<K, ExpiringKey<K>> expiringKeys; | |
/** | |
* Holds the map keys using the given life time for expiration. | |
*/ | |
private final DelayQueue<ExpiringKey> delayQueue = new DelayQueue<ExpiringKey>(); | |
/** | |
* The default max life time in milliseconds. | |
*/ | |
private final long maxLifeTimeMillis; | |
public SelfExpiringHashMap() { | |
internalMap = new ConcurrentHashMap<K, V>(); | |
expiringKeys = new WeakHashMap<K, ExpiringKey<K>>(); | |
this.maxLifeTimeMillis = Long.MAX_VALUE; | |
} | |
public SelfExpiringHashMap(long defaultMaxLifeTimeMillis) { | |
internalMap = new ConcurrentHashMap<K, V>(); | |
expiringKeys = new WeakHashMap<K, ExpiringKey<K>>(); | |
this.maxLifeTimeMillis = defaultMaxLifeTimeMillis; | |
} | |
public SelfExpiringHashMap(long defaultMaxLifeTimeMillis, int initialCapacity) { | |
internalMap = new ConcurrentHashMap<K, V>(initialCapacity); | |
expiringKeys = new WeakHashMap<K, ExpiringKey<K>>(initialCapacity); | |
this.maxLifeTimeMillis = defaultMaxLifeTimeMillis; | |
} | |
public SelfExpiringHashMap(long defaultMaxLifeTimeMillis, int initialCapacity, float loadFactor) { | |
internalMap = new ConcurrentHashMap<K, V>(initialCapacity, loadFactor); | |
expiringKeys = new WeakHashMap<K, ExpiringKey<K>>(initialCapacity, loadFactor); | |
this.maxLifeTimeMillis = defaultMaxLifeTimeMillis; | |
} | |
/** | |
* {@inheritDoc} | |
*/ | |
@Override | |
public int size() { | |
cleanup(); | |
return internalMap.size(); | |
} | |
/** | |
* {@inheritDoc} | |
*/ | |
@Override | |
public boolean isEmpty() { | |
cleanup(); | |
return internalMap.isEmpty(); | |
} | |
/** | |
* {@inheritDoc} | |
*/ | |
@Override | |
public boolean containsKey(Object key) { | |
cleanup(); | |
return internalMap.containsKey((K) key); | |
} | |
/** | |
* {@inheritDoc} | |
*/ | |
@Override | |
public boolean containsValue(Object value) { | |
cleanup(); | |
return internalMap.containsValue((V) value); | |
} | |
@Override | |
public V get(Object key) { | |
cleanup(); | |
renewKey((K) key); | |
return internalMap.get((K) key); | |
} | |
/** | |
* {@inheritDoc} | |
*/ | |
@Override | |
public V put(K key, V value) { | |
return this.put(key, value, maxLifeTimeMillis); | |
} | |
/** | |
* {@inheritDoc} | |
*/ | |
@Override | |
public V put(K key, V value, long lifeTimeMillis) { | |
cleanup(); | |
ExpiringKey delayedKey = new ExpiringKey(key, lifeTimeMillis); | |
ExpiringKey oldKey = expiringKeys.put((K) key, delayedKey); | |
if(oldKey != null) { | |
expireKey(oldKey); | |
expiringKeys.put((K) key, delayedKey); | |
} | |
delayQueue.offer(delayedKey); | |
return internalMap.put(key, value); | |
} | |
/** | |
* {@inheritDoc} | |
*/ | |
@Override | |
public V remove(Object key) { | |
V removedValue = internalMap.remove((K) key); | |
expireKey(expiringKeys.remove((K) key)); | |
return removedValue; | |
} | |
/** | |
* Not supported. | |
*/ | |
@Override | |
public void putAll(Map<? extends K, ? extends V> m) { | |
throw new UnsupportedOperationException(); | |
} | |
/** | |
* {@inheritDoc} | |
*/ | |
@Override | |
public boolean renewKey(K key) { | |
ExpiringKey<K> delayedKey = expiringKeys.get((K) key); | |
if (delayedKey != null) { | |
delayedKey.renew(); | |
return true; | |
} | |
return false; | |
} | |
private void expireKey(ExpiringKey<K> delayedKey) { | |
if (delayedKey != null) { | |
delayedKey.expire(); | |
cleanup(); | |
} | |
} | |
/** | |
* {@inheritDoc} | |
*/ | |
@Override | |
public void clear() { | |
delayQueue.clear(); | |
expiringKeys.clear(); | |
internalMap.clear(); | |
} | |
/** | |
* Not supported. | |
*/ | |
@Override | |
public Set<K> keySet() { | |
throw new UnsupportedOperationException(); | |
} | |
/** | |
* Not supported. | |
*/ | |
@Override | |
public Collection<V> values() { | |
throw new UnsupportedOperationException(); | |
} | |
/** | |
* Not supported. | |
*/ | |
@Override | |
public Set<Entry<K, V>> entrySet() { | |
throw new UnsupportedOperationException(); | |
} | |
private void cleanup() { | |
ExpiringKey<K> delayedKey = delayQueue.poll(); | |
while (delayedKey != null) { | |
internalMap.remove(delayedKey.getKey()); | |
expiringKeys.remove(delayedKey.getKey()); | |
delayedKey = delayQueue.poll(); | |
} | |
} | |
private class ExpiringKey<K> implements Delayed { | |
private long startTime = System.currentTimeMillis(); | |
private final long maxLifeTimeMillis; | |
private final K key; | |
public ExpiringKey(K key, long maxLifeTimeMillis) { | |
this.maxLifeTimeMillis = maxLifeTimeMillis; | |
this.key = key; | |
} | |
public K getKey() { | |
return key; | |
} | |
/** | |
* {@inheritDoc} | |
*/ | |
@Override | |
public boolean equals(Object obj) { | |
if (obj == null) { | |
return false; | |
} | |
if (getClass() != obj.getClass()) { | |
return false; | |
} | |
final ExpiringKey<K> other = (ExpiringKey<K>) obj; | |
if (this.key != other.key && (this.key == null || !this.key.equals(other.key))) { | |
return false; | |
} | |
return true; | |
} | |
/** | |
* {@inheritDoc} | |
*/ | |
@Override | |
public int hashCode() { | |
int hash = 7; | |
hash = 31 * hash + (this.key != null ? this.key.hashCode() : 0); | |
return hash; | |
} | |
/** | |
* {@inheritDoc} | |
*/ | |
@Override | |
public long getDelay(TimeUnit unit) { | |
return unit.convert(getDelayMillis(), TimeUnit.MILLISECONDS); | |
} | |
private long getDelayMillis() { | |
return (startTime + maxLifeTimeMillis) - System.currentTimeMillis(); | |
} | |
public void renew() { | |
startTime = System.currentTimeMillis(); | |
} | |
public void expire() { | |
startTime = Long.MIN_VALUE; | |
} | |
/** | |
* {@inheritDoc} | |
*/ | |
@Override | |
public int compareTo(Delayed that) { | |
return Long.compare(this.getDelayMillis(), ((ExpiringKey) that).getDelayMillis()); | |
} | |
} | |
} |
/* | |
* Copyright (c) 2019 Pierantonio Cangianiello | |
* | |
* MIT License | |
* | |
* Permission is hereby granted, free of charge, to any person obtaining a copy | |
* of this software and associated documentation files (the "Software"), to deal | |
* in the Software without restriction, including without limitation the rights | |
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
* copies of the Software, and to permit persons to whom the Software is | |
* furnished to do so, subject to the following conditions: | |
* | |
* The above copyright notice and this permission notice shall be included in all | |
* copies or substantial portions of the Software. | |
* | |
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE | |
* SOFTWARE. | |
*/ | |
import it.pcan.util.map.SelfExpiringHashMap; | |
import it.pcan.util.map.SelfExpiringMap; | |
import static org.junit.Assert.*; | |
import org.junit.Test; | |
/** | |
* | |
* @author Pierantonio Cangianiello | |
*/ | |
public class SelfExpiringHashMapTests { | |
private final static int SLEEP_MULTIPLIER = 80; | |
@Test | |
public void basicGetTest() throws InterruptedException { | |
SelfExpiringMap<String, String> map = new SelfExpiringHashMap<String, String>(); | |
map.put("a", "b", 2 * SLEEP_MULTIPLIER); | |
Thread.sleep(1 * SLEEP_MULTIPLIER); | |
assertEquals("b", map.get("a")); | |
} | |
@Test | |
public void basicExpireTest() throws InterruptedException { | |
SelfExpiringMap<String, String> map = new SelfExpiringHashMap<String, String>(); | |
map.put("a", "b", 2 * SLEEP_MULTIPLIER); | |
Thread.sleep(3 * SLEEP_MULTIPLIER); | |
assertNull(map.get("a")); | |
} | |
@Test | |
public void basicRenewTest() throws InterruptedException { | |
SelfExpiringMap<String, String> map = new SelfExpiringHashMap<String, String>(); | |
map.put("a", "b", 3 * SLEEP_MULTIPLIER); | |
Thread.sleep(2 * SLEEP_MULTIPLIER); | |
map.renewKey("a"); | |
Thread.sleep(2 * SLEEP_MULTIPLIER); | |
assertEquals("b", map.get("a")); | |
} | |
@Test | |
public void getRenewTest() throws InterruptedException { | |
SelfExpiringMap<String, String> map = new SelfExpiringHashMap<String, String>(); | |
map.put("a", "b", 3 * SLEEP_MULTIPLIER); | |
Thread.sleep(2 * SLEEP_MULTIPLIER); | |
assertEquals("b", map.get("a")); | |
Thread.sleep(2 * SLEEP_MULTIPLIER); | |
assertEquals("b", map.get("a")); | |
} | |
@Test | |
public void multiplePutThenRemoveTest() throws InterruptedException { | |
SelfExpiringMap<String, String> map = new SelfExpiringHashMap<String, String>(); | |
map.put("a", "b", 2 * SLEEP_MULTIPLIER); | |
Thread.sleep(1 * SLEEP_MULTIPLIER); | |
map.put("a", "c", 2 * SLEEP_MULTIPLIER); | |
Thread.sleep(1 * SLEEP_MULTIPLIER); | |
map.put("a", "d", 400 * SLEEP_MULTIPLIER); | |
Thread.sleep(2 * SLEEP_MULTIPLIER); | |
assertEquals("d", map.remove("a")); | |
} | |
@Test | |
public void multiplePutThenGetTest() throws InterruptedException { | |
SelfExpiringMap<String, String> map = new SelfExpiringHashMap<String, String>(); | |
map.put("a", "b", 2 * SLEEP_MULTIPLIER); | |
Thread.sleep(1 * SLEEP_MULTIPLIER); | |
map.put("a", "c", 2 * SLEEP_MULTIPLIER); | |
Thread.sleep(1 * SLEEP_MULTIPLIER); | |
map.put("a", "d", 400 * SLEEP_MULTIPLIER); | |
Thread.sleep(2 * SLEEP_MULTIPLIER); | |
assertEquals("d", map.get("a")); | |
} | |
@Test | |
public void insertionOrderTest() throws InterruptedException { | |
SelfExpiringMap<String, Integer> map = new SelfExpiringHashMap<String, Integer>(30000); | |
map.put("123456", 999); | |
assertEquals(map.get("123456"), Integer.valueOf(999)); | |
map.put("123456", 123); | |
map.put("777456", 333); | |
assertEquals(map.get("123456"), Integer.valueOf(123)); | |
assertEquals(map.get("777456"), Integer.valueOf(333)); | |
map.put("777456", 123); | |
map.put("123456", 321); | |
assertEquals(map.get("123456"), Integer.valueOf(321)); | |
assertEquals(map.get("777456"), Integer.valueOf(123)); | |
} | |
} |
/* | |
* Copyright (c) 2019 Pierantonio Cangianiello | |
* | |
* MIT License | |
* | |
* Permission is hereby granted, free of charge, to any person obtaining a copy | |
* of this software and associated documentation files (the "Software"), to deal | |
* in the Software without restriction, including without limitation the rights | |
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
* copies of the Software, and to permit persons to whom the Software is | |
* furnished to do so, subject to the following conditions: | |
* | |
* The above copyright notice and this permission notice shall be included in all | |
* copies or substantial portions of the Software. | |
* | |
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE | |
* SOFTWARE. | |
*/ | |
import java.util.Map; | |
/** | |
* | |
* @author Pierantonio Cangianiello | |
* @param <K> the Key type | |
* @param <V> the Value type | |
*/ | |
public interface SelfExpiringMap<K, V> extends Map<K, V> { | |
/** | |
* Renews the specified key, setting the life time to the initial value. | |
* | |
* @param key | |
* @return true if the key is found, false otherwise | |
*/ | |
public boolean renewKey(K key); | |
/** | |
* Associates the given key to the given value in this map, with the specified life | |
* times in milliseconds. | |
* | |
* @param key | |
* @param value | |
* @param lifeTimeMillis | |
* @return a previously associated object for the given key (if exists). | |
*/ | |
public V put(K key, V value, long lifeTimeMillis); | |
} |
Hi,
While testing out this code, I came across a test case that was not giving me the expected result. I noticed that if the first element is renewed, the second element even if expired, will not be removed from the map. If the order of initial insert are swapped, the test case passes. I had to either remove the renew method, which was called from the get method or remove the element and re-insert it to the map in a synchronized method to ensure all the keys expire in the cleanup method as expected. Is this the correct way to do this?
@Test
public void multiplePutTillExpireTest() throws InterruptedException {
SelfExpiringMap<String, String> map = new SelfExpiringHashMap<>(60000);
map.put("Test1.txt", "c");
map.put("Test2.txt", "b");
Thread.sleep(50*1000);
if(map.containsKey("Test1.txt"))
map.get("Test1.txt");
Thread.sleep(40*1000);
assertFalse(map.containsKey("Test2.txt"));
}
Hi @prameeshas, this issue seems related to the DelayQueue internals, since it lacks an efficient mechanism for key renewal. I'm going to fix the implementation in order to make your test case pass. Thank you for reporting this issue.
Hi @pcan, the current implementation seems to leak elements in the DelayQueue when removing them from the map before they expire. After e.g. invoking:
map.put("foo", 1);
map.remove("foo");
the SelfExpiringHashMap seems to be empty at first glance, but the DelayQueue still holds an ExpiringKey instance for the key "foo". The issue seems to come from the change to set startTime = Long.MIN_VALUE
when expire()
is called for this key and the subsequent calculation of getDelay()
. Polling the queue fails then. After making ExpiringKey available to this small test by declaring it public static you can see that an expired key (what remove is essentially doing) cannot be polled from the queue:
@Test
void testDelay() {
final DelayQueue<ExpiringKey<String>> queue = new DelayQueue<>();
final ExpiringKey<String> key = new ExpiringKey<>("foo", 1000);
queue.add(key);
key.expire();
assertNotNull(queue.poll());
}
hi @fdummert, basically this triggers the same issue of the one reported by prameeshas. I still haven't got time to fix this, but basically I will move the implementation to a RB-tree instead of a priority-queue based (as current DelayQueue implementation relies on).
Hi @pcan , why method get(Object key) need to renewKey() again?
Thank you @pcan