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..fda6ff2 100644 --- a/src/main/java/ua/net/uid/utils/io/ExpiringCache.java +++ b/src/main/java/ua/net/uid/utils/io/ExpiringCache.java @@ -15,168 +15,359 @@ */ 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(ExecutorService executor) { - this.executor = executor; - table = new Chain[NCPU * 2]; + public ExpiringCache(int initSize) { + this(initSize, LOAD_FACTOR); } - - public Future future(K key) { - return chain(key).get(System.currentTimeMillis(), key); + public ExpiringCache(float loadFactor) { + this(INIT_SIZE, loadFactor); } - - public Future future(K key, Callable callable) { - return chain(key).future(System.currentTimeMillis(), key, callable, Long.MAX_VALUE); + public ExpiringCache(int initSize, float loadFactor) { + this.loadFactor = loadFactor; + this.nextResize = (int)(loadFactor * initSize); + this.table = create(initSize); } - - 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 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 static final class Chain extends Item { + final ExpiringCache cache; + int count = 0; + + Chain(ExpiringCache cache) { + super(null); + this.cache = cache; + } + + private void count(int value) { + if (count != value) { + int old = count; + count = value; + cache.resize(value - old); + } + } + private boolean checkNext(Item current, long now) { + if (current.next != null) { + if (current.next.expiry <= now) { + current.next = null; + } else { + return true; + } + } + return false; + } + + 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, now)) { + ++cnt; + item = item.next; + } + 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); + } + } + //////////////////////////////////////////////////////////////////////////// + + + + /* + //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// private final static class Chain extends Item { private final ExpiringCache cache; private int count = 0; @@ -323,5 +514,5 @@ count = value; } } - } + }*/ }