ClockCache


1   /*
2    * Copyright (c) 1998-2006 Caucho Technology -- all rights reserved
3    *
4    * This file is part of Resin(R) Open Source
5    *
6    * Each copy or derived work must preserve the copyright notice and this
7    * notice unmodified.
8    *
9    * Resin Open Source is free software; you can redistribute it and/or modify
10   * it under the terms of the GNU General Public License as published by
11   * the Free Software Foundation; either version 2 of the License, or
12   * (at your option) any later version.
13   *
14   * Resin Open Source is distributed in the hope that it will be useful,
15   * but WITHOUT ANY WARRANTY; without even the implied warranty of
16   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE, or any warranty
17   * of NON-INFRINGEMENT.  See the GNU General Public License for more
18   * details.
19   *
20   * You should have received a copy of the GNU General Public License
21   * along with Resin Open Source; if not, write to the
22   *   Free SoftwareFoundation, Inc.
23   *   59 Temple Place, Suite 330
24   *   Boston, MA 02111-1307  USA
25   *
26   * @author Scott Ferguson
27   */
28  
29  package com.caucho.util;
30  
31  import java.util.ArrayList  ;
32  import java.util.Iterator  ;
33  
34  /**
35   * Cache with a clock replacement policy.
36   *
37   * <p>Null keys are not allowed.  LruCache is synchronized.
38   */
39  public class ClockCache<K,E extends ClockCacheItem> {
40    // array containing the keys
41    private K []_keys;
42    
43    // array containing the values
44    private E []_values;
45    
46    // maximum allowed entries
47    private int _capacity;
48    // number of items in the cache
49    private int _size;
50    private int _mask;
51  
52    private int _clock;
53    
54    /**
55     * Create the clock cache with a specific capacity.
56     *
57     * @param initialCapacity minimum capacity of the cache
58     */
59    public ClockCache(int initialCapacity)
60    {
61      int capacity;
62  
63      for (capacity = 16; capacity < initialCapacity; capacity *= 2) {
64      }
65  
66      _keys = (K []) new Object  [capacity];
67      _values = (E []) new Object  [capacity];
68      _mask = capacity - 1;
69  
70      _capacity = initialCapacity;
71    }
72  
73    /**
74     * Returns the current number of entries in the cache.
75     */
76    public int size()
77    {
78      return _size;
79    }
80  
81    /**
82     * Clears the cache
83     */
84    public void clear()
85    {
86      ArrayList  <E> listeners = null;
87  
88      synchronized (this) {
89        for (int i = 0; i < _values.length; i++) {
90          E item = _values[i];
91  
92          if (item != null) {
93        if (listeners == null)
94          listeners = new ArrayList  <E>();
95        listeners.add(item);
96          }
97          
98          _values[i] = null;
99        }
100 
101       _size = 0;
102     }
103 
104     for (int i = listeners == null ? -1 : listeners.size() - 1; i >= 0; i--) {
105       E listener = listeners.get(i);
106       listener.removeEvent();
107     }
108   }
109 
110   /**
111    * Get an item from the cache and make it most recently used.
112    *
113    * @param key key to lookup the item
114    * @return the matching object in the cache
115    */
116   public E get(K key)
117   {
118     int hash = key.hashCode() & _mask;
119     int count = _size + 1;
120 
121     synchronized (this) {
122       for (; count > 0; count--) {
123         E item = _values[hash];
124 
125         if (item == null)
126           return null;
127 
128         if (_keys[hash].equals(key)) {
129       item.setUsed();
130 
131           return item;
132         }
133 
134         hash = (hash + 1) & _mask;
135       }
136     }
137 
138     return null;
139   }
140 
141   /**
142    * Puts a new item in the cache.  If the cache is full, remove the
143    * LRU item.
144    *
145    * @param key key to store data
146    * @param value value to be stored
147    *
148    * @return old value stored under the key
149    */
150   public E put(K key, E value)
151   {
152     freeSpace();
153 
154     E item = putImpl(key, value);
155 
156     // forced resizing if 3/4 full
157     if (3 * _values.length <= 4 * _size) {
158       synchronized (this) {
159     K []oldKeys = _keys;
160     E []oldValues = _values;
161 
162     _keys = (K []) new Object  [2 * oldKeys.length];
163     _values = (E []) new Object  [2 * oldValues.length];
164 
165     _mask = _values.length - 1;
166     _size = 0;
167 
168     for (int i = oldValues.length - 1; i >= 0; i--) {
169       K oldKey = oldKeys[i];
170       E oldValue = oldValues[i];
171 
172       if (oldValue != null)
173         putImpl(oldKey, oldValue);
174     }
175       }
176     }
177 
178     if (item != null)
179       item.removeEvent();
180 
181     return item;
182   }
183 
184   /**
185    * Implementation of the put.
186    */
187   private E putImpl(K key, E value)
188   {
189     E item = null;
190 
191     int hash = key.hashCode() & _mask;
192     int count = _size + 1;
193 
194     synchronized (this) {
195       for (; count > 0; count--) {
196     item = _values[hash];
197 
198     // No matching item, so create one
199     if (item == null) {
200       _keys[hash] = key;
201       _values[hash] = value;
202       _size++;
203 
204       return null;
205     }
206 
207     // matching item gets replaced
208     if (_keys[hash].equals(key)) {
209       item.setUsed();
210 
211       _values[hash] = value;
212 
213       return item;
214     }
215 
216     hash = (hash + 1) & _mask;
217       }
218     }
219 
220     throw new IllegalStateException  ();
221   }
222 
223   private void freeSpace()
224   {
225     int i = _size - _capacity;
226     if (i > 16)
227       i = 16;
228     // remove LRU items until we're below capacity
229     while (i-- > 0 && removeItem()) {
230     }
231   }
232 
233   /**
234    * Remove an unused item from the LRU
235    */
236   private boolean removeItem()
237   {
238     int length = _values.length;
239     int clock = _clock;
240     ClockCacheItem item = null;
241 
242     for (int i = 0; i < length; i++) {
243       synchronized (this) {
244     item = _values[clock];
245 
246     if (item != null && ! item.isUsed()) {
247       _keys[clock] = null;
248       _values[clock] = null;
249       _size--;
250 
251       refillEntries(clock);
252 
253       break;
254     }
255       }
256 
257       if (item != null)
258     item.clearUsed();
259 
260       clock = (clock + 1) % length;
261       item = null;
262     }
263 
264     _clock = clock;
265 
266     if (item != null) {
267       item.removeEvent();
268       return true;
269     }
270     else
271       return false;
272   }
273 
274   /**
275    * Removes an item from the cache
276    *
277    * @param key the key to remove
278    *
279    * @return the value removed
280    */
281   public ClockCacheItem remove(K key)
282   {
283     int hash = key.hashCode() & _mask;
284     int count = _size + 1;
285 
286     ClockCacheItem item = null;
287 
288     synchronized (this) {
289       for (; count > 0; count--) {
290     item = _values[hash];
291 
292     if (item == null)
293       return null;
294 
295     if (_keys[hash].equals(key)) {
296       _keys[hash] = null;
297       _values[hash] = null;
298       _size--; 
299 
300       refillEntries(hash);
301       break;
302     }
303 
304     hash = (hash + 1) & _mask;
305       }
306     }
307 
308     if (count < 0)
309       throw new RuntimeException  ("internal cache error");
310 
311     item.removeEvent();
312 
313     return item;
314   }
315 
316   /**
317    * Put the item in the best location available in the hash table.
318    */
319   private void refillEntries(int hash)
320   {
321     for (int count = _size; count >= 0; count--) {
322       hash = (hash + 1) & _mask;
323 
324       if (_values[hash] == null)
325     return;
326 
327       refillEntry(hash);
328     }
329   }
330   
331   /**
332    * Put the item in the best location available in the hash table.
333    */
334   private void refillEntry(int baseHash)
335   {
336     K key = _keys[baseHash];
337     E value = _values[baseHash];
338     
339     _keys[baseHash] = null;
340     _values[baseHash] = null;
341     
342     int hash = key.hashCode() & _mask;
343     
344     for (int count = _size; count >= 0; count--) {
345       if (_values[hash] == null) {
346     _keys[hash] = key;
347     _values[hash] = value;
348     return;
349       }
350 
351       hash = (hash + 1) & _mask;
352     }
353   }
354 
355   /**
356    * Returns the values in the cache
357    */
358   public Iterator  <E> values()
359   {
360     ValueIterator<K,E> iter = new ValueIterator<K,E>();
361     iter.init(this);
362     return iter;
363   }
364 
365   /**
366    * Iterator of cache values
367    */
368   static class ValueIterator<K1,V1 extends ClockCacheItem> implements Iterator  <V1> {
369     ClockCache<K1,V1> _cache;
370     int _i;
371 
372     void init(ClockCache<K1,V1> cache)
373     {
374       _cache = cache;
375       _i = 0;
376     }
377 
378     public boolean hasNext()
379     {
380       V1 []values = _cache._values;
381       int len = values.length;
382       
383       for (; _i < len; _i++) {
384     if (values[_i] != null)
385       return true;
386       }
387       
388       return false;
389     }
390 
391     public V1 next()
392     {
393       V1 []values = _cache._values;
394       K1 []keys = _cache._keys;
395       int len = values.length;
396       
397       if (_i < values.length && values[_i] != null) {
398     V1 value = values[_i++];
399 
400     return value;
401       }
402 
403       return null;
404     }
405 
406     public void remove()
407     {
408       throw new UnsupportedOperationException  ();
409     }
410   }
411 }
412
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags