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