001    /**
002     * Copyright (c) 2000-2013 Liferay, Inc. All rights reserved.
003     *
004     * This library is free software; you can redistribute it and/or modify it under
005     * the terms of the GNU Lesser General Public License as published by the Free
006     * Software Foundation; either version 2.1 of the License, or (at your option)
007     * any later version.
008     *
009     * This library is distributed in the hope that it will be useful, but WITHOUT
010     * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
011     * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
012     * details.
013     */
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;
026    import java.util.Map.Entry;
027    import java.util.concurrent.atomic.AtomicLong;
028    import java.util.concurrent.locks.Lock;
029    import java.util.concurrent.locks.ReentrantReadWriteLock;
030    
031    /**
032     * @author Shuyang Zhou
033     */
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    }