1   /**
2    * Copyright (c) 2000-2010 Liferay, Inc. All rights reserved.
3    *
4    * This library is free software; you can redistribute it and/or modify it under
5    * the terms of the GNU Lesser General Public License as published by the Free
6    * Software Foundation; either version 2.1 of the License, or (at your option)
7    * any later version.
8    *
9    * This library is distributed in the hope that it will be useful, but WITHOUT
10   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11   * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
12   * details.
13   */
14  
15  package com.liferay.portal.kernel.concurrent;
16  
17  import com.liferay.portal.kernel.util.StringBundler;
18  
19  import java.util.concurrent.atomic.AtomicInteger;
20  import java.util.concurrent.atomic.AtomicLong;
21  import java.util.concurrent.locks.Lock;
22  import java.util.concurrent.locks.ReentrantReadWriteLock;
23  
24  /**
25   * <a href="ConcurrentLRUCache.java.html"><b><i>View Source</i></b></a>
26   *
27   * @author Shuyang Zhou
28   */
29  public class ConcurrentLRUCache<K, V> {
30  
31      public ConcurrentLRUCache(int maxSize) {
32          _maxSize = maxSize;
33  
34          _readLock = _readWriteLock.readLock();
35          _writeLock = _readWriteLock.writeLock();
36  
37          _headEntry._nextEntry = _lastEntry;
38          _lastEntry._previousEntry = _headEntry;
39      }
40  
41      public long evictCount() {
42          return _evictCount.get();
43      }
44  
45      public V get(K key) {
46          Entry<K, V> matchEntry = null;
47  
48          boolean requiresMove = false;
49  
50          _readLock.lock();
51  
52          try {
53              matchEntry = _lastEntry._previousEntry;
54  
55              while (matchEntry != _headEntry) {
56                  if (matchEntry._key.equals(key)) {
57                      if (matchEntry._nextEntry != _lastEntry) {
58                          requiresMove = true;
59                      }
60  
61                      _hitCount.getAndIncrement();
62  
63                      return matchEntry._value;
64                  }
65  
66                  matchEntry = matchEntry._previousEntry;
67              }
68          }
69          finally {
70              _readLock.unlock();
71  
72              if (requiresMove) {
73                  _writeLock.lock();
74  
75                  try {
76                      if (matchEntry._key != null) {
77                          _detachEntry(matchEntry);
78  
79                          _insertEntryBefore(_lastEntry, matchEntry);
80                      }
81                  }
82                  finally {
83                      _writeLock.unlock();
84                  }
85              }
86          }
87  
88          _missCount.getAndIncrement();
89  
90          return null;
91      }
92  
93      public long hitCount() {
94          return _hitCount.get();
95      }
96  
97      public int maxSize() {
98          return _maxSize;
99      }
100 
101     public long missCount() {
102         return _missCount.get();
103     }
104 
105     public void put(K key, V value) {
106         if (key == null) {
107             throw new NullPointerException("Key is null");
108         }
109 
110         _putCount.getAndIncrement();
111         _writeLock.lock();
112 
113         try {
114             Entry<K, V> currentEntry = _lastEntry._previousEntry;
115 
116             while (currentEntry != _headEntry) {
117                 if (currentEntry._key.equals(key)) {
118                     currentEntry._value = value;
119 
120                     if (currentEntry._nextEntry != _lastEntry) {
121                         _detachEntry(currentEntry);
122                         _insertEntryBefore(_lastEntry, currentEntry);
123                     }
124 
125                     return;
126                 }
127 
128                 currentEntry = currentEntry._previousEntry;
129             }
130 
131             while (_size.get() >= _maxSize) {
132                 _removeHeadEntry();
133             }
134 
135             _insertEntryBefore(_lastEntry, new Entry<K, V>(key, value));
136 
137             _size.getAndIncrement();
138         }
139         finally {
140             _writeLock.unlock();
141         }
142     }
143 
144     public long putCount() {
145         return _putCount.get();
146     }
147 
148     public int size() {
149         return _size.get();
150     }
151 
152     public String toString() {
153         StringBundler sb = new StringBundler();
154 
155         sb.append("{evictCount=");
156         sb.append(_evictCount);
157         sb.append(", hitCount=");
158         sb.append(_hitCount);
159         sb.append(", maxSize=");
160         sb.append(_maxSize);
161         sb.append(", missCount=");
162         sb.append(_missCount);
163         sb.append(", putCount=");
164         sb.append(_putCount);
165         sb.append(", size=");
166         sb.append(_size);
167         sb.append("}");
168 
169         return sb.toString();
170     }
171 
172     private void _detachEntry(Entry<K, V> entry) {
173         entry._previousEntry._nextEntry = entry._nextEntry;
174         entry._nextEntry._previousEntry = entry._previousEntry;
175         entry._nextEntry = entry._previousEntry = null;
176     }
177 
178     private void _insertEntryBefore(
179         Entry<K, V> referenceEntry, Entry<K, V> insertEntry) {
180 
181         insertEntry._previousEntry = referenceEntry._previousEntry;
182         insertEntry._nextEntry = referenceEntry;
183 
184         referenceEntry._previousEntry._nextEntry = insertEntry;
185         referenceEntry._previousEntry = insertEntry;
186     }
187 
188     private void _removeHeadEntry() {
189         Entry<K, V> entry = _headEntry._nextEntry;
190 
191         _detachEntry(entry);
192 
193         entry._key = null;
194         entry._value = null;
195 
196         _size.getAndDecrement();
197         _evictCount.getAndIncrement();
198     }
199 
200     private final AtomicLong _evictCount = new AtomicLong(0);
201     private final Entry<K, V> _headEntry = new Entry<K, V>(null, null);
202     private final AtomicLong _hitCount = new AtomicLong(0);
203     private final Entry<K, V> _lastEntry = new Entry<K, V>(null, null);
204     private final int _maxSize;
205     private final AtomicLong _missCount = new AtomicLong(0);
206     private final AtomicLong _putCount = new AtomicLong(0);
207     private final Lock _readLock;
208     private final ReentrantReadWriteLock _readWriteLock =
209         new ReentrantReadWriteLock();
210     private final AtomicInteger _size = new AtomicInteger(0);
211     private final Lock _writeLock;
212 
213     private static class Entry<K, V> {
214 
215         public Entry(K key, V value) {
216             _key = key;
217             _value = value;
218         }
219 
220         private K _key;
221         private Entry<K, V> _nextEntry;
222         private Entry<K, V> _previousEntry;
223         private V _value;
224 
225     }
226 
227 }