diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..a6f89c2
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+/target/
\ No newline at end of file
diff --git a/pom.xml b/pom.xml
index 6068905..39a14c5 100644
--- a/pom.xml
+++ b/pom.xml
@@ -3,7 +3,7 @@
4.0.0
ua.net.uid
uid.tools
- 1.0.0-SNAPSHOT
+ 1.0.1-SNAPSHOT
jar
@@ -69,7 +69,8 @@
true
@{project.version}
- release
+
+ false
@@ -79,13 +80,26 @@
UTF-8
1.8
1.8
+ uid-releases
+
+
+ ua.net.uid-releases
+ https://git.uid.net.ua/maven/releases/
+
+
+ ua.net.uid-snapshots
+ https://git.uid.net.ua/maven/snapshots/
+
+
+
scm:git:https://git.uid.net.ua/git/uid/uid.tools.git
scm:git:https://git.uid.net.ua/git/uid/uid.tools.git
https://git.uid.net.ua/git/uid/uid.tools.git
-
+ HEAD
+
diff --git a/src/main/java/ua/net/uid/utils/io/ExpiringCache.java b/src/main/java/ua/net/uid/utils/io/ExpiringCache.java
index 9fa4fa3..6ad3a73 100644
--- a/src/main/java/ua/net/uid/utils/io/ExpiringCache.java
+++ b/src/main/java/ua/net/uid/utils/io/ExpiringCache.java
@@ -15,298 +15,237 @@
*/
package ua.net.uid.utils.io;
-import ua.net.uid.utils.concurrent.ReadyFuture;
-
import java.util.Date;
import java.util.Objects;
-import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
-import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
+import java.util.function.Function;
public class ExpiringCache {
- static final int NCPU = Runtime.getRuntime().availableProcessors();
- private final ReadWriteLock lock = new ReentrantReadWriteLock();
- private final AtomicInteger count = new AtomicInteger();
- private final ExecutorService executor;
+ ////////////////////////////////////////////////////////////////////////////
+ public static final int MAX_TABLE_SIZE = Integer.MAX_VALUE >>> 3;
+ public static final int INIT_SIZE = 64;
+ public static final float LOAD_FACTOR = 7F/3F;
+ ////////////////////////////////////////////////////////////////////////////
+ private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
+ private final AtomicInteger count = new AtomicInteger(0);
+ private final AtomicInteger modified = new AtomicInteger(0);
+ private final float loadFactor;
+ private int nextResize;
private Chain[] table;
+
public ExpiringCache() {
- this(Executors.newCachedThreadPool());
+ this(INIT_SIZE, LOAD_FACTOR);
+ }
+ public ExpiringCache(int initSize) {
+ this(initSize, LOAD_FACTOR);
+ }
+ public ExpiringCache(float loadFactor) {
+ this(INIT_SIZE, loadFactor);
+ }
+ public ExpiringCache(int initSize, float loadFactor) {
+ this.loadFactor = loadFactor;
+ this.nextResize = (int)(loadFactor * initSize);
+ this.table = create(initSize);
}
- public ExpiringCache(ExecutorService executor) {
- this.executor = executor;
- table = new Chain[NCPU * 2];
- }
-
- public Future future(K key) {
- return chain(key).get(System.currentTimeMillis(), key);
- }
-
- public Future future(K key, Callable callable) {
- return chain(key).future(System.currentTimeMillis(), key, callable, Long.MAX_VALUE);
- }
-
- public Future future(K key, Callable callable, long ttl) {
- long now;
- return chain(key).future(now = System.currentTimeMillis(), key, callable, now + ttl);
- }
-
- public Future future(K key, Callable callable, Date expiry) {
- return chain(key).future(System.currentTimeMillis(), key, callable, expiry.getTime());
- }
-
+ public int getSize() { return count.get(); }
+
+ public int getTableSize() { return table.length; }
+
+ int getModifiedCount() { return modified.get(); }
+
public V get(K key) {
- Future future = future(key);
- return future == null ? null : value(future);
+ return get(key, now());
+ }
+
+ public V get(K key, long now) {
+ return chain(key.hashCode()).get(key, now);
}
- public V get(K key, Callable callable) {
- return value(future(key, callable));
+ public V get(K key, Function callback, long ttl) {
+ return get(key, callback, ttl, now());
+ }
+
+ public V get(K key, Function callback, Date expiry) {
+ return get(key, callback, expiry, now());
}
- public V get(K key, Callable callable, long ttl) {
- return value(future(key, callable, ttl));
+ public V get(K key, Function callback, long ttl, long now) {
+ return chain(key.hashCode()).get(key, callback, now + ttl, now);
}
-
- public V get(K key, Callable callable, Date expiry) {
- return value(future(key, callable, expiry));
+
+ public V get(K key, Function callback, Date expiry, long now) {
+ return chain(key.hashCode()).get(key, callback, expiry.getTime(), now);
}
-
- public void set(K key, V value) {
- chain(key).set(System.currentTimeMillis(), key, value, Long.MAX_VALUE);
- }
-
+
public void set(K key, V value, long ttl) {
- long now;
- chain(key).set(now = System.currentTimeMillis(), key, value, now + ttl);
+ set(key, value, ttl, now());
}
-
+
public void set(K key, V value, Date expiry) {
- chain(key).set(System.currentTimeMillis(), key, value, expiry.getTime());
+ set(key, value, expiry, now());
}
- public void put(K key, Callable callable) {
- chain(key).put(System.currentTimeMillis(), key, callable, Long.MAX_VALUE);
+ public void set(K key, V value, long ttl, long now) {
+ chain(key.hashCode()).set(key, value, ttl + now, now);
}
-
- public void put(K key, Callable callable, long ttl) {
- long now;
- chain(key).put(now = System.currentTimeMillis(), key, callable, now + ttl);
+
+ public void set(K key, V value, Date expiry, long now) {
+ chain(key.hashCode()).set(key, value, expiry.getTime(), now);
}
-
- public void put(K key, Callable callable, Date expiry) {
- chain(key).put(System.currentTimeMillis(), key, callable, expiry.getTime());
- }
-
- public Future extractFuture(K key) {
- return chain(key).extract(System.currentTimeMillis(), key);
- }
-
- public V extract(K key) {
- Future future = extractFuture(key);
- return future == null ? null : value(future);
- }
-
+
public void remove(K key) {
- chain(key).remove(System.currentTimeMillis(), key);
+ remove(key, now());
}
-
- public void clear() {
+
+ public void remove(K key, long now) {
+ chain(key.hashCode()).remove(key, now);
+ }
+
+ public V extract(K key) {
+ return extract(key, now());
+ }
+
+ public V extract(K key, long now) {
+ return chain(key.hashCode()).extract(key, now);
+ }
+
+ public void gc() {
+ lock.readLock().lock();
+ try {
+ long now = now();
+ for(Chain chain: table)
+ chain.gc(now);
+ modified.set(0);
+ } finally {
+ lock.readLock().unlock();
+ }
+ }
+ /*
+ //TODO public void pack()
+ public void pack() {
lock.writeLock().lock();
try {
- for (Chain chain : table) {
- chain.clear();
- }
- //count.set(0);
+ throw new UnsupportedOperationException("TODO: Not supported yet.");
+ } finally {
+ lock.writeLock().unlock();
+ }
+ }
+ */
+ public void empty() {
+ lock.readLock().lock();
+ try {
+ for(Chain chain: table)
+ chain.next = null;
+ modified.set(0);
+ } finally {
+ lock.readLock().unlock();
+ }
+ }
+
+ public void clear(int initSize) {
+ lock.writeLock().lock();
+ try {
+ table = create(initSize);
+ modified.set(0);
} finally {
lock.writeLock().unlock();
}
}
- public int count() {
- return count.get();
+ public void clear() {
+ clear(INIT_SIZE);
+ }
+ ////////////////////////////////////////////////////////////////////////////
+ private static long now() { return System.currentTimeMillis(); }
+
+ private Chain[] create(int size) {
+ Chain[] result = (Chain[]) new Chain[size];
+ for(int i = 0; i < size; ++i)
+ result[i] = new Chain<>(this);
+ return result;
}
- public void gc() {
+ private static int index(int hash, int length) {
+ return (hash & MAX_TABLE_SIZE) % length;
+ }
+
+ private Chain chain(int hash) {
lock.readLock().lock();
try {
- long now = System.currentTimeMillis();
- for (Chain chain : table) {
- chain.gc(now);
+ return table[index(hash, table.length)];
+ } finally {
+ lock.readLock().unlock();
+ }
+ }
+
+ private void resize(int delta) {
+ int newSize = Math.min(MAX_TABLE_SIZE, count.addAndGet(delta));
+ if (newSize > nextResize) {
+ lock.writeLock().lock();
+ try {
+ Chain[] result = create(newSize);
+ int newCount = 0;
+ long now = now();
+ for(Chain src : table) {
+ Entry old = src.next;
+ while (old != null && old.expiry > now) {
+ result[index(old.key.hashCode(), newSize)].add(old.key, old.value, old.expiry);
+ ++newCount;
+ old = old.next;
+ }
+ src.next = null;
+ }
+ table = result;
+ count.set(newCount);
+ modified.set(0);
+ nextResize = Math.min(MAX_TABLE_SIZE, (int)(loadFactor * newSize));
+ } finally {
+ lock.writeLock().unlock();
}
- } finally {
- lock.readLock().unlock();
+ } else {
+ if (modified.incrementAndGet() > nextResize)
+ gc();
}
}
- ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- private Chain chain(K key) {
- int hash = key.hashCode();
- lock.readLock().lock();
- try {
- return table[hash % table.length];
- } finally {
- lock.readLock().unlock();
- }
- }
-
- private V value(Future future) {
- try {
- return future.get();
- } catch (ExecutionException | InterruptedException ex) {
- throw new RuntimeException(ex);
- }
- }
- ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+ ////////////////////////////////////////////////////////////////////////////
private static abstract class Item {
Entry next;
Item(Entry next) { this.next = next; }
}
-
- private final static class Entry extends Item {
+ ////////////////////////////////////////////////////////////////////////////
+ private static final class Entry extends Item {
final K key;
- Future future;
- long expiry;
-
- private Entry(K key, Future future, long expiry, Entry next) {
+ final V value;
+ final long expiry;
+ Entry(K key, V value, long expiry, Entry next) {
super(next);
- this.key = key;
- this.future = future;
this.expiry = expiry;
+ this.key = key;
+ this.value = value;
}
}
-
- private final static class Chain extends Item {
- private final ExpiringCache cache;
- private int count = 0;
-
- Chain(ExpiringCache cache, Entry next) {
- super(next);
+ ////////////////////////////////////////////////////////////////////////////
+ private static final class Chain extends Item {
+ final ExpiringCache cache;
+ int count = 0;
+
+ Chain(ExpiringCache cache) {
+ super(null);
this.cache = cache;
}
-
- synchronized Future get(long now, K key) {
- Item item = this;
- int cnt = 0;
- while (next(now, item)) {
- if (Objects.equals(key, item.next.key)) {
- return item.next.future;
- }
- ++cnt;
- item = item.next;
+
+ private void count(int value) {
+ if (count != value) {
+ int old = count;
+ count = value;
+ cache.resize(value - old);
}
- count(cnt);
- return null;
}
- synchronized Future future(long now, K key, Callable callable, long expiry) {
- Item item = this, last = this;
- int cnt = 0;
- while (next(now, item)) {
- if (Objects.equals(key, item.next.key)) {
- return item.next.future;
- }
- ++cnt;
- if (item.next.expiry > expiry) {
- last = item.next;
- }
- item = item.next;
- }
- last.next = new Entry<>(key, cache.executor.submit(callable), expiry, last.next);
- count(cnt + 1);
- return last.next.future;
- }
-
- synchronized void set(long now, K key, V value, long expiry) {
- Item item = this, last = this;
- int cnt = 0;
- while (next(now, item)) {
- if (Objects.equals(key, item.next.key)) {
- item.next = item.next.next;
- continue;
- }
- ++cnt;
- if (item.next.expiry > expiry) {
- last = item.next;
- }
- item = item.next;
- }
- last.next = new Entry<>(key, new ReadyFuture<>(value), expiry, last.next);
- count(cnt + 1);
- }
-
- synchronized void put(long now, K key, Callable callable, long expiry) {
- Item item = this, last = this;
- int cnt = 0;
- while (next(now, item)) {
- if (Objects.equals(key, item.next.key)) {
- item.next = item.next.next;
- continue;
- }
- ++cnt;
- if (item.next.expiry > expiry) {
- last = item.next;
- }
- item = item.next;
- }
- last.next = new Entry<>(key, cache.executor.submit(callable), expiry, last.next);
- count(cnt + 1);
- }
-
- synchronized Future extract(long now, K key) {
- Item item = this;
- int cnt = 0;
- while (next(now, item)) {
- if (Objects.equals(key, item.next.key)) {
- try {
- return item.next.future;
- } finally {
- item.next = item.next.next;
- --count;
- cache.count.decrementAndGet();
- }
- }
- ++cnt;
- item = item.next;
- }
- count(cnt);
- return null;
- }
-
- synchronized void remove(long now, K key) {
- Item item = this;
- int cnt = 0;
- while (next(now, item)) {
- if (Objects.equals(key, item.next.key)) {
- item.next = item.next.next;
- --count;
- cache.count.decrementAndGet();
- return;
- }
- ++cnt;
- item = item.next;
- }
- count(cnt);
- }
-
- void gc(long now) {
- Item item = this;
- int cnt = 0;
- while (next(now, item)) {
- ++cnt;
- item = item.next;
- }
- count(cnt);
- }
-
- void clear() {
- cache.count.addAndGet(-count);
- count = 0;
- next = null;
- }
-
- private boolean next(long now, Item current) {
+ private boolean checkNext(Item current, long now) {
if (current.next != null) {
if (current.next.expiry <= now) {
current.next = null;
@@ -317,11 +256,113 @@
return false;
}
- private void count(int value) {
- if (count != value) {
- cache.count.addAndGet(value - count);
- count = value;
+ void add(K key, V value, long expiry) {
+ Item item = this;
+ while (item.next != null && item.next.expiry > expiry) {
+ item = item.next;
}
+ item.next = new Entry<>(key, value, expiry, item.next);
+ ++count;
+ }
+
+ synchronized V get(K key, long now) {
+ Item item = this;
+ int cnt = 0;
+ V result = null;
+ while (checkNext(item, now)) {
+ if (Objects.equals(key, item.next.key))
+ result = item.next.value;
+ ++cnt;
+ item = item.next;
+ }
+ count(cnt);
+ return result;
+ }
+
+ synchronized V get(K key, Function callback, long expiry, long now) {
+ Item item = this, last = this;
+ int cnt = 0;
+ while (checkNext(item, now)) {
+ ++cnt;
+ if (Objects.equals(key, item.next.key)) {
+ V value = item.next.value;
+ while (checkNext(item = item.next, now)) ++cnt;
+ count(cnt);
+ return value;
+ }
+ if (item.next.expiry > expiry)
+ last = item.next;
+ item = item.next;
+ }
+ V value = callback.apply(key);
+ last.next = new Entry<>(key, value, expiry, last.next);
+ count(cnt + 1);
+ return value;
+ }
+
+ synchronized void set(K key, V value, long expiry, long now) {
+ Item item = this, last = this;
+ int cnt = 0;
+ while (checkNext(item, now)) {
+ if (Objects.equals(key, item.next.key)) {
+ item.next = item.next.next;
+ while (checkNext(item, now)) {
+ ++cnt;
+ if (item.next.expiry > expiry)
+ last = item.next;
+ item = item.next;
+ }
+ break;
+ }
+ ++cnt;
+ if (item.next.expiry > expiry)
+ last = item.next;
+ item = item.next;
+ }
+ last.next = new Entry<>(key, value, expiry, last.next);
+ count(cnt + 1);
+ }
+
+ synchronized void remove(K key, long now) {
+ Item item = this;
+ int cnt = 0;
+ while (checkNext(item, now)) {
+ if (Objects.equals(key, item.next.key)) {
+ item.next = item.next.next;
+ } else {
+ ++cnt;
+ item = item.next;
+ }
+ }
+ count(cnt);
+ }
+
+ synchronized V extract(K key, long now) {
+ Item item = this;
+ int cnt = 0;
+ V result = null;
+ while (checkNext(item, now)) {
+ if (Objects.equals(key, item.next.key)) {
+ result = item.next.value;
+ item.next = item.next.next;
+ } else {
+ ++cnt;
+ item = item.next;
+ }
+ }
+ count(cnt);
+ return result;
+ }
+
+ synchronized void gc(long now) {
+ Item item = this;
+ int cnt = 0;
+ while (checkNext(item, now)) {
+ ++cnt;
+ item = item.next;
+ }
+ count(cnt);
}
}
+ ////////////////////////////////////////////////////////////////////////////
}
diff --git a/src/test/java/ua/net/uid/utils/io/ExpiringCacheTest.java b/src/test/java/ua/net/uid/utils/io/ExpiringCacheTest.java
index 3002b9f..afb3214 100644
--- a/src/test/java/ua/net/uid/utils/io/ExpiringCacheTest.java
+++ b/src/test/java/ua/net/uid/utils/io/ExpiringCacheTest.java
@@ -6,84 +6,73 @@
//TODO ExpiringCacheTest
class ExpiringCacheTest {
-
+
@Test
- void future() {
+ public void testSavingOfItems() throws Exception {
+ ExpiringCache instance = new ExpiringCache<>(2, 4f/3f);
+
+ assertEquals(Integer.valueOf(1), instance.get(1, (key) -> key * key, 1500));
+ assertEquals(Integer.valueOf(4), instance.get(2, (key) -> key * key, 2000));
+ assertEquals(2, instance.getSize());
+ assertEquals(2, instance.getTableSize());
+ assertEquals(2, instance.getModifiedCount());
+
+ assertEquals(Integer.valueOf(4), instance.get(2, (key) -> key, 2000));
+ assertEquals(2, instance.getSize());
+ assertEquals(2, instance.getTableSize());
+ assertEquals(2, instance.getModifiedCount());
+
+ assertEquals(Integer.valueOf(9), instance.get(3, (key) -> key * key, 2000));
+ assertEquals(3, instance.getSize());
+ assertEquals(3, instance.getTableSize());
+ assertEquals(0, instance.getModifiedCount());
+
+ assertEquals(Integer.valueOf(16), instance.get(4, (key) -> key * key, 2000));
+ assertEquals(4, instance.getSize());
+ assertEquals(3, instance.getTableSize());
+ assertEquals(1, instance.getModifiedCount());
+
+ assertEquals(Integer.valueOf(25), instance.get(-5, (key) -> key * key, 1000));
+ assertEquals(5, instance.getSize());
+ assertEquals(5, instance.getTableSize());
+ assertEquals(0, instance.getModifiedCount());
+
+ assertEquals(Integer.valueOf(25), instance.get(-5));
+ assertEquals(5, instance.getSize());
+ assertEquals(5, instance.getTableSize());
+ assertEquals(0, instance.getModifiedCount());
+
+ assertNull(instance.get(-5, System.currentTimeMillis() + 1000));
+ assertEquals(4, instance.getSize());
+ assertEquals(5, instance.getTableSize());
+ assertEquals(1, instance.getModifiedCount());
+
+ assertEquals(Integer.valueOf(25), instance.get(5, (key) -> key * key, 1));
+ assertEquals(5, instance.getSize());
+ assertEquals(5, instance.getTableSize());
+ assertEquals(2, instance.getModifiedCount());
+
+ assertEquals(Integer.valueOf(2), instance.get(1, (key) -> key + 1, 1, System.currentTimeMillis() + 1500));
+ assertEquals(5, instance.getSize());
+ assertEquals(5, instance.getTableSize());
+ assertEquals(2, instance.getModifiedCount());
+
+ assertEquals(Integer.valueOf(9), instance.get(3));
+ assertEquals(Integer.valueOf(4), instance.get(2));
+ instance.remove(3);
+ assertNull(instance.get(3));
+ assertEquals(Integer.valueOf(4), instance.get(2));
+
+ assertEquals(4, instance.getSize());
+ assertEquals(5, instance.getTableSize());
+ assertEquals(3, instance.getModifiedCount());
+
+ assertEquals(Integer.valueOf(3), instance.get(3, (key) -> key, 2000));
+ assertEquals(5, instance.getSize());
+ assertEquals(5, instance.getTableSize());
+ assertEquals(4, instance.getModifiedCount());
+
+
}
- @Test
- void future1() {
- }
-
- @Test
- void future2() {
- }
-
- @Test
- void future3() {
- }
-
- @Test
- void get() {
- }
-
- @Test
- void get1() {
- }
-
- @Test
- void get2() {
- }
-
- @Test
- void get3() {
- }
-
- @Test
- void set() {
- }
-
- @Test
- void set1() {
- }
-
- @Test
- void set2() {
- }
-
- @Test
- void put() {
- }
-
- @Test
- void put1() {
- }
-
- @Test
- void put2() {
- }
-
- @Test
- void extractFuture() {
- }
-
- @Test
- void extract() {
- }
-
- @Test
- void remove() {
- }
-
- @Test
- void clear() {
- }
-
- @Test
- void count() {
- }
-
- @Test
- void gc() {
- }
}
\ No newline at end of file