From c270234f37f0d9bdb1755f22561cbcba156b6e8c Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Wed, 18 Aug 2010 16:54:59 +0000 Subject: Introduce SoftValuedCache, which evicts more aggressively than SoftValuedHashMap. --- .../com/amazon/carbonado/util/BelatedCreator.java | 5 +- .../java/com/amazon/carbonado/util/Converter.java | 4 +- .../carbonado/util/QuickConstructorGenerator.java | 7 +- .../com/amazon/carbonado/util/SoftValuedCache.java | 372 +++++++++++++++++++++ 4 files changed, 379 insertions(+), 9 deletions(-) create mode 100644 src/main/java/com/amazon/carbonado/util/SoftValuedCache.java (limited to 'src/main/java/com/amazon/carbonado/util') diff --git a/src/main/java/com/amazon/carbonado/util/BelatedCreator.java b/src/main/java/com/amazon/carbonado/util/BelatedCreator.java index 513a0c0..cc476cf 100644 --- a/src/main/java/com/amazon/carbonado/util/BelatedCreator.java +++ b/src/main/java/com/amazon/carbonado/util/BelatedCreator.java @@ -36,7 +36,6 @@ import org.cojen.classfile.Modifiers; import org.cojen.classfile.TypeDesc; import org.cojen.util.ClassInjector; -import org.cojen.util.SoftValuedHashMap; /** * Generic one-shot factory which supports late object creation. If the object @@ -54,12 +53,12 @@ import org.cojen.util.SoftValuedHashMap; public abstract class BelatedCreator { private static final String REF_FIELD_NAME = "ref"; - private static final Map, Class> cWrapperCache; + private static final SoftValuedCache, Class> cWrapperCache; private static final ExecutorService cThreadPool; static { - cWrapperCache = new SoftValuedHashMap(); + cWrapperCache = SoftValuedCache.newCache(11); cThreadPool = Executors.newCachedThreadPool(new TFactory()); } diff --git a/src/main/java/com/amazon/carbonado/util/Converter.java b/src/main/java/com/amazon/carbonado/util/Converter.java index 61f832a..44f28eb 100644 --- a/src/main/java/com/amazon/carbonado/util/Converter.java +++ b/src/main/java/com/amazon/carbonado/util/Converter.java @@ -38,7 +38,6 @@ import org.cojen.classfile.Opcode; import org.cojen.classfile.TypeDesc; import org.cojen.util.ClassInjector; -import org.cojen.util.SoftValuedHashMap; /** * General purpose type converter. Custom conversions are possible by supplying @@ -50,7 +49,8 @@ import org.cojen.util.SoftValuedHashMap; * @since 1.2 */ public abstract class Converter { - private static final Map> cCache = new SoftValuedHashMap(); + private static final SoftValuedCache> cCache = + SoftValuedCache.newCache(7); /** * @param converterType type of converter to generate diff --git a/src/main/java/com/amazon/carbonado/util/QuickConstructorGenerator.java b/src/main/java/com/amazon/carbonado/util/QuickConstructorGenerator.java index 7a10440..a746c1f 100644 --- a/src/main/java/com/amazon/carbonado/util/QuickConstructorGenerator.java +++ b/src/main/java/com/amazon/carbonado/util/QuickConstructorGenerator.java @@ -29,7 +29,6 @@ import org.cojen.classfile.CodeBuilder; import org.cojen.classfile.TypeDesc; import org.cojen.util.ClassInjector; import org.cojen.util.WeakIdentityMap; -import org.cojen.util.SoftValuedHashMap; /** * Generates code to invoke constructors. This is a replacement for {@link @@ -48,7 +47,7 @@ import org.cojen.util.SoftValuedHashMap; public class QuickConstructorGenerator { // Map> @SuppressWarnings("unchecked") - private static Map, Map, Object>> cCache = new WeakIdentityMap(); + private static Map, SoftValuedCache, Object>> cCache = new WeakIdentityMap(); /** * Returns a factory instance for one type of object. Each method in the @@ -87,9 +86,9 @@ public class QuickConstructorGenerator { */ @SuppressWarnings("unchecked") public static synchronized F getInstance(Class objectType, Class factory) { - Map, Object> innerCache = cCache.get(factory); + SoftValuedCache, Object> innerCache = cCache.get(factory); if (innerCache == null) { - innerCache = new SoftValuedHashMap(); + innerCache = SoftValuedCache.newCache(7); cCache.put(factory, innerCache); } F instance = (F) innerCache.get(objectType); diff --git a/src/main/java/com/amazon/carbonado/util/SoftValuedCache.java b/src/main/java/com/amazon/carbonado/util/SoftValuedCache.java new file mode 100644 index 0000000..3e9e767 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/util/SoftValuedCache.java @@ -0,0 +1,372 @@ +/* + * Copyright 2010 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.util; + +import java.lang.ref.Reference; +import java.lang.ref.ReferenceQueue; +import java.lang.ref.SoftReference; + +/** + * Simple thread-safe cache which evicts entries via a shared background + * thread. Cache permits null keys, but not null values. + * + * @author Brian S O'Neill + */ +public abstract class SoftValuedCache { + // Design note: Public class is abstract to make it easy to swap out this + // implementation with something available in a shared collection library. + + public static SoftValuedCache newCache(int capacity) { + return new Impl(capacity); + } + + public abstract int size(); + + public abstract boolean isEmpty(); + + public abstract V get(K key); + + public abstract V put(K key, V value); + + public abstract V putIfAbsent(K key, V value); + + public abstract V remove(K key); + + public abstract boolean remove(K key, V value); + + public abstract boolean replace(K key, V oldValue, V newValue); + + public abstract V replace(K key, V value); + + public abstract void clear(); + + public abstract String toString(); + + private static class Impl extends SoftValuedCache { + private static final float LOAD_FACTOR = 0.75f; + + private Entry[] mEntries; + private int mSize; + private int mThreshold; + + Impl(int capacity) { + mEntries = new Entry[capacity]; + mThreshold = (int) (capacity * LOAD_FACTOR); + } + + @Override + public synchronized int size() { + return mSize; + } + + @Override + public synchronized boolean isEmpty() { + return mSize == 0; + } + + @Override + public synchronized V get(K key) { + int hash = key == null ? 0 : key.hashCode(); + Entry[] entries = mEntries; + int index = (hash & 0x7fffffff) % entries.length; + for (Entry e = entries[index]; e != null; e = e.mNext) { + if (e.matches(key, hash)) { + return e.get(); + } + } + return null; + } + + @Override + public synchronized V put(K key, V value) { + int hash = key == null ? 0 : key.hashCode(); + Entry[] entries = mEntries; + int index = (hash & 0x7fffffff) % entries.length; + for (Entry e = entries[index], prev = null; e != null; e = e.mNext) { + if (e.matches(key, hash)) { + V old = e.get(); + e.clear(); + Entry newEntry; + if (prev == null) { + newEntry = new Entry(this, hash, key, value, e.mNext); + } else { + prev.mNext = e.mNext; + newEntry = new Entry(this, hash, key, value, entries[index]); + } + entries[index] = newEntry; + return old; + } else { + prev = e; + } + } + + if (mSize >= mThreshold) { + cleanup(); + if (mSize >= mThreshold) { + rehash(); + entries = mEntries; + index = (hash & 0x7fffffff) % entries.length; + } + } + + entries[index] = new Entry(this, hash, key, value, entries[index]); + mSize++; + return null; + } + + @Override + public synchronized V putIfAbsent(K key, V value) { + V existing = get(key); + return existing == null ? put(key, value) : existing; + } + + @Override + public synchronized V remove(K key) { + int hash = key == null ? 0 : key.hashCode(); + Entry[] entries = mEntries; + int index = (hash & 0x7fffffff) % entries.length; + for (Entry e = entries[index], prev = null; e != null; e = e.mNext) { + if (e.matches(key, hash)) { + V old = e.get(); + e.clear(); + if (prev == null) { + entries[index] = e.mNext; + } else { + prev.mNext = e.mNext; + } + mSize--; + return old; + } else { + prev = e; + } + } + return null; + } + + @Override + public synchronized boolean remove(K key, V value) { + V existing = get(key); + if (existing != null && existing.equals(value)) { + remove(key); + return true; + } else { + return false; + } + } + + @Override + public synchronized boolean replace(K key, V oldValue, V newValue) { + V existing = get(key); + if (existing != null && existing.equals(oldValue)) { + put(key, newValue); + return true; + } else { + return false; + } + } + + @Override + public synchronized V replace(K key, V value) { + return get(key) == null ? null : put(key, value); + } + + @Override + public synchronized void clear() { + Entry[] entries = mEntries; + for (int i=entries.length; --i>=0; ) { + Entry e = entries[i]; + if (e != null) { + e.clear(); + entries[i] = null; + } + } + mSize = 0; + } + + @Override + public synchronized String toString() { + if (isEmpty()) { + return "{}"; + } + + StringBuilder b = new StringBuilder(); + b.append('{'); + + Entry[] entries = mEntries; + int removed = 0; + boolean any = false; + + for (int i=entries.length; --i>=0 ;) { + for (Entry e = entries[i], prev = null; e != null; e = e.mNext) { + V value = e.get(); + if (value == null) { + // Clean up after a cleared Reference. + if (prev == null) { + entries[i] = e.mNext; + } else { + prev.mNext = e.mNext; + } + removed++; + } else { + prev = e; + if (any) { + b.append(',').append(' '); + } + K key = e.mKey; + b.append(key).append('=').append(value); + any = true; + } + } + } + + mSize -= removed; + + b.append('}'); + return b.toString(); + } + + synchronized void removeCleared(Entry cleared) { + Entry[] entries = mEntries; + int index = (cleared.mHash & 0x7fffffff) % entries.length; + for (Entry e = entries[index], prev = null; e != null; e = e.mNext) { + if (e == cleared) { + if (prev == null) { + entries[index] = e.mNext; + } else { + prev.mNext = e.mNext; + } + mSize--; + return; + } else { + prev = e; + } + } + } + + private synchronized void cleanup() { + Entry[] entries = mEntries; + int removed = 0; + + for (int i=entries.length; --i>=0 ;) { + for (Entry e = entries[i], prev = null; e != null; e = e.mNext) { + if (e.get() == null) { + // Clean up after a cleared Reference. + if (prev == null) { + entries[i] = e.mNext; + } else { + prev.mNext = e.mNext; + } + removed++; + } else { + prev = e; + } + } + } + + mSize -= removed; + } + + private synchronized void rehash() { + Entry[] oldEntries = mEntries; + int newCapacity = oldEntries.length * 2 + 1; + Entry[] newEntries = new Entry[newCapacity]; + int removed = 0; + + for (int i=oldEntries.length; --i>=0 ;) { + for (Entry old = oldEntries[i]; old != null; ) { + Entry e = old; + old = old.mNext; + // Only copy entry if its value hasn't been cleared. + if (e.get() == null) { + removed++; + } else { + int index = (e.mHash & 0x7fffffff) % newCapacity; + e.mNext = newEntries[index]; + newEntries[index] = e; + } + } + } + + mEntries = newEntries; + mSize -= removed; + mThreshold = (int) (newCapacity * LOAD_FACTOR); + } + } + + private static class Entry extends Ref { + final Impl mCache; + final int mHash; + final K mKey; + Entry mNext; + + Entry(Impl cache, int hash, K key, V value, Entry next) { + super(value); + mCache = cache; + mHash = hash; + mKey = key; + mNext = next; + } + + @Override + void remove() { + mCache.removeCleared(this); + } + + boolean matches(K key, int hash) { + return hash == mHash && (key == null ? mKey == null : key.equals(mKey)); + } + } + + final static Evictor cEvictor; + + static { + Evictor evictor = new Evictor(); + evictor.setName("SoftValuedCache Evictor"); + evictor.setDaemon(true); + evictor.setPriority(Thread.MAX_PRIORITY); + evictor.start(); + cEvictor = evictor; + } + + private static abstract class Ref extends SoftReference { + Ref(T referent) { + super(referent, cEvictor.mQueue); + } + + abstract void remove(); + } + + private static class Evictor extends Thread { + final ReferenceQueue mQueue; + + Evictor() { + mQueue = new ReferenceQueue(); + } + + @Override + public void run() { + try { + while (true) { + ((Ref) mQueue.remove()).remove(); + } + } catch (InterruptedException e) { + } + } + } +} -- cgit v1.2.3