diff options
Diffstat (limited to 'src/main/java/com/amazon/carbonado/util/SoftValuedCache.java')
| -rw-r--r-- | src/main/java/com/amazon/carbonado/util/SoftValuedCache.java | 372 |
1 files changed, 372 insertions, 0 deletions
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) {
+ }
+ }
+ }
+}
|