Introduce SoftValuedCache, which evicts more aggressively than SoftValuedHashMap.

4 files changed, 379 insertions, 9 deletions

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<T, E extends Exception> {

     private static final String REF_FIELD_NAME = "ref";

 

-    private static final Map<Class<?>, Class<?>> cWrapperCache;

+    private static final SoftValuedCache<Class<?>, 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<Class, Class<? extends Converter>> cCache = new SoftValuedHashMap();

+    private static final SoftValuedCache<Class, Class<? extends Converter>> 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<factory class, Map<object type, factory instance>>

     @SuppressWarnings("unchecked")

-    private static Map<Class<?>, Map<Class<?>, Object>> cCache = new WeakIdentityMap();

+    private static Map<Class<?>, SoftValuedCache<Class<?>, 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> F getInstance(Class<?> objectType, Class<F> factory) {

-        Map<Class<?>, Object> innerCache = cCache.get(factory);

+        SoftValuedCache<Class<?>, 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<K, V> {

+    // 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 <K, V> SoftValuedCache<K, V> newCache(int capacity) {

+        return new Impl<K, V>(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<K, V> extends SoftValuedCache<K, V> {

+        private static final float LOAD_FACTOR = 0.75f;

+

+        private Entry<K, V>[] 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<K, V>[] entries = mEntries;

+            int index = (hash & 0x7fffffff) % entries.length;

+            for (Entry<K, V> 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<K, V>[] entries = mEntries;

+            int index = (hash & 0x7fffffff) % entries.length;

+            for (Entry<K, V> e = entries[index], prev = null; e != null; e = e.mNext) {

+                if (e.matches(key, hash)) {

+                    V old = e.get();

+                    e.clear();

+                    Entry<K, V> newEntry;

+                    if (prev == null) {

+                        newEntry = new Entry<K, V>(this, hash, key, value, e.mNext);

+                    } else {

+                        prev.mNext = e.mNext;

+                        newEntry = new Entry<K, V>(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<K, V>(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<K, V>[] entries = mEntries;

+            int index = (hash & 0x7fffffff) % entries.length;

+            for (Entry<K, V> 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<K, V>[] entries = mEntries;

+            int removed = 0;

+            boolean any = false;

+

+            for (int i=entries.length; --i>=0 ;) {

+                for (Entry<K, V> 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<K, V> cleared) {

+            Entry<K, V>[] entries = mEntries;

+            int index = (cleared.mHash & 0x7fffffff) % entries.length;

+            for (Entry<K, V> 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<K, V>[] entries = mEntries;

+            int removed = 0;

+

+            for (int i=entries.length; --i>=0 ;) {

+                for (Entry<K, V> 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<K, V>[] oldEntries = mEntries;

+            int newCapacity = oldEntries.length * 2 + 1;

+            Entry<K, V>[] newEntries = new Entry[newCapacity];

+            int removed = 0;

+

+            for (int i=oldEntries.length; --i>=0 ;) {

+                for (Entry<K, V> old = oldEntries[i]; old != null; ) {

+                    Entry<K, V> 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<K, V> extends Ref<V> {

+        final Impl<K, V> mCache;

+        final int mHash;

+        final K mKey;

+        Entry mNext;

+

+        Entry(Impl<K, V> 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<T> extends SoftReference<T> {

+        Ref(T referent) {

+            super(referent, cEvictor.mQueue);

+        }

+

+        abstract void remove();

+    }

+

+    private static class Evictor extends Thread {

+        final ReferenceQueue<Object> mQueue;

+

+        Evictor() {

+            mQueue = new ReferenceQueue<Object>();

+        }

+

+        @Override

+        public void run() {

+            try {

+                while (true) {

+                    ((Ref) mQueue.remove()).remove();

+                }

+            } catch (InterruptedException e) {

+            }

+        }

+    }

+}