001
014
015 package com.liferay.portal.kernel.concurrent;
016
017 import com.liferay.portal.kernel.util.StringBundler;
018
019 import java.util.ArrayList;
020 import java.util.Collections;
021 import java.util.Comparator;
022 import java.util.HashMap;
023 import java.util.Iterator;
024 import java.util.List;
025 import java.util.Map.Entry;
026 import java.util.Map;
027 import java.util.concurrent.atomic.AtomicLong;
028 import java.util.concurrent.locks.Lock;
029 import java.util.concurrent.locks.ReentrantReadWriteLock;
030
031
034 public class ConcurrentLFUCache<K, V> {
035
036 public ConcurrentLFUCache(int maxSize) {
037 this(maxSize, 0.75F);
038 }
039
040 public ConcurrentLFUCache(int maxSize, float loadFactor) {
041 if ((maxSize <= 0) || (loadFactor <= 0) || (loadFactor >= 1)) {
042 throw new IllegalArgumentException();
043 }
044
045 _maxSize = maxSize;
046 _expectedSize = (int)(maxSize * loadFactor);
047
048 if (_expectedSize == 0) {
049 throw new IllegalArgumentException(
050 "maxSize and loadFactor are too small");
051 }
052
053 _readLock = _readWriteLock.readLock();
054 _writeLock = _readWriteLock.writeLock();
055 }
056
057 public void clear() {
058 _writeLock.lock();
059
060 try {
061 _cache.clear();
062 }
063 finally {
064 _writeLock.unlock();
065 }
066 }
067
068 public long evictCount() {
069 return _evictCount.get();
070 }
071
072 public int expectedSize() {
073 return _expectedSize;
074 }
075
076 public V get(K key) {
077 _readLock.lock();
078
079 try {
080 ValueWrapper valueWrapper = _cache.get(key);
081
082 if (valueWrapper != null) {
083 valueWrapper._hitCount.getAndIncrement();
084
085 _hitCount.getAndIncrement();
086
087 return valueWrapper._value;
088 }
089 }
090 finally {
091 _readLock.unlock();
092 }
093
094 _missCount.getAndIncrement();
095
096 return null;
097 }
098
099 public long hitCount() {
100 return _hitCount.get();
101 }
102
103 public int maxSize() {
104 return _maxSize;
105 }
106
107 public long missCount() {
108 return _missCount.get();
109 }
110
111 public void put(K key, V value) {
112 if (key == null) {
113 throw new NullPointerException("Key is null");
114 }
115
116 ValueWrapper valueWrapper = new ValueWrapper(value);
117
118 _writeLock.lock();
119
120 try {
121 if (!_cache.containsKey(key) && (_cache.size() >= _maxSize)) {
122 _cleanUp();
123 }
124
125 _cache.put(key, valueWrapper);
126 }
127 finally {
128 _writeLock.unlock();
129 }
130
131 _putCount.getAndIncrement();
132 }
133
134 public long putCount() {
135 return _putCount.get();
136 }
137
138 public int size() {
139 _readLock.lock();
140
141 try {
142 return _cache.size();
143 }
144 finally {
145 _readLock.unlock();
146 }
147 }
148
149 @Override
150 public String toString() {
151 StringBundler sb = new StringBundler();
152
153 sb.append("{evictCount=");
154 sb.append(_evictCount.get());
155 sb.append(", expectedSize=");
156 sb.append(_expectedSize);
157 sb.append(", hitCount=");
158 sb.append(_hitCount.get());
159 sb.append(", maxSize=");
160 sb.append(_maxSize);
161 sb.append(", missCount=");
162 sb.append(_missCount.get());
163 sb.append(", putCount=");
164 sb.append(_putCount.get());
165 sb.append(", size=");
166 sb.append(size());
167 sb.append("}");
168
169 return sb.toString();
170 }
171
172 protected void onRemove(K key, V value) {
173 }
174
175 private void _cleanUp() {
176 List<Entry<K, ValueWrapper>> valueWrappers =
177 new ArrayList<Entry<K, ValueWrapper>>(_cache.entrySet());
178
179 Collections.sort(valueWrappers, _entryComparator);
180
181 int cleanUpSize = _cache.size() - _expectedSize;
182
183 _evictCount.getAndAdd(cleanUpSize);
184
185 Iterator<Entry<K, ValueWrapper>> itr = valueWrappers.iterator();
186
187 while ((cleanUpSize-- > 0) && itr.hasNext()) {
188 Entry<K, ValueWrapper> entry = itr.next();
189
190 K key = entry.getKey();
191
192 V value = entry.getValue()._value;
193
194 _cache.remove(key);
195
196 onRemove(key, value);
197
198 itr.remove();
199 }
200 }
201
202 private Map<K, ValueWrapper> _cache = new HashMap<K, ValueWrapper>();
203 private final EntryComparator _entryComparator = new EntryComparator();
204 private final AtomicLong _evictCount = new AtomicLong();
205 private final int _expectedSize;
206 private final AtomicLong _hitCount = new AtomicLong();
207 private final int _maxSize;
208 private final AtomicLong _missCount = new AtomicLong();
209 private final AtomicLong _putCount = new AtomicLong();
210 private final Lock _readLock;
211 private final ReentrantReadWriteLock _readWriteLock =
212 new ReentrantReadWriteLock();
213 private final Lock _writeLock;
214
215 private class EntryComparator
216 implements Comparator<Entry<K, ValueWrapper>> {
217
218 @Override
219 public int compare(
220 Entry<K, ValueWrapper> entry1, Entry<K, ValueWrapper> entry2) {
221
222 ValueWrapper valueWrapper1 = entry1.getValue();
223 ValueWrapper valueWrapper2 = entry2.getValue();
224
225 long hitCount1 = valueWrapper1._hitCount.get();
226 long hitCount2 = valueWrapper2._hitCount.get();
227
228 return (int)(hitCount1 - hitCount2);
229 }
230
231 }
232
233 private class ValueWrapper {
234
235 public ValueWrapper(V v) {
236 _value = v;
237 }
238
239 private final AtomicLong _hitCount = new AtomicLong();
240 private final V _value;
241
242 }
243
244 }