KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > caucho > util > LongKeyClockCache


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 JavaDoc;
32
33 /**
34  * Cache with a clock replacement policy.
35  *
36  * <p>Null keys are not allowed. LruCache is synchronized.
37  */
38 public class LongKeyClockCache<E extends ClockCacheItem> {
39   // array containing the keys
40 private long []_keys;
41   
42   // array containing the values
43 private E []_values;
44   
45   // maximum allowed entries
46 private int _capacity;
47   // number of items in the cache
48 private int _size;
49   private int _mask;
50
51   private int _clock;
52   
53   /**
54    * Create the clock cache with a specific capacity.
55    *
56    * @param initialCapacity minimum capacity of the cache
57    */
58   public LongKeyClockCache(int initialCapacity)
59   {
60     int capacity;
61
62     for (capacity = 16; capacity < 2 * initialCapacity; capacity *= 2) {
63     }
64
65     _keys = new long[capacity];
66     _values = (E []) new ClockCacheItem[capacity];
67     _mask = capacity - 1;
68
69     _capacity = initialCapacity;
70   }
71
72   /**
73    * Returns the current number of entries in the cache.
74    */
75   public int size()
76   {
77     return _size;
78   }
79
80   /**
81    * Clears the cache
82    */
83   public void clear()
84   {
85     ArrayList JavaDoc<E> listeners = null;
86
87     synchronized (this) {
88       for (int i = 0; i < _values.length; i++) {
89         E item = _values[i];
90
91         if (item != null) {
92       if (listeners == null)
93         listeners = new ArrayList JavaDoc<E>();
94       listeners.add(item);
95         }
96         
97         _values[i] = null;
98       }
99
100       _size = 0;
101     }
102
103     for (int i = listeners == null ? -1 : listeners.size() - 1; i >= 0; i--) {
104       E listener = listeners.get(i);
105       listener.removeEvent();
106     }
107   }
108
109   /**
110    * Get an item from the cache and make it most recently used.
111    *
112    * @param key key to lookup the item
113    * @return the matching object in the cache
114    */
115   public E get(long key)
116   {
117     int hash = getHash(key);
118     int count = _size + 1;
119
120     synchronized (this) {
121       for (; count > 0; count--) {
122         E item = _values[hash];
123
124         if (item == null)
125           return null;
126
127         if (_keys[hash] == key) {
128       item.setUsed();
129
130           return item;
131         }
132
133         hash = (hash + 1) & _mask;
134       }
135     }
136
137     return null;
138   }
139
140   /**
141    * Puts a new item in the cache. If the cache is full, remove the
142    * LRU item.
143    *
144    * @param key key to store data
145    * @param value value to be stored
146    *
147    * @return old value stored under the key
148    */
149   public E put(long key, E value)
150   {
151     freeSpace();
152
153     E item = putImpl(key, value);
154
155     // forced resizing if 3/4 full
156 if (3 * _values.length <= 4 * _size) {
157       synchronized (this) {
158     long []oldKeys = _keys;
159     E []oldValues = _values;
160     
161     _keys = new long[2 * oldKeys.length];
162     _values = (E []) new Object JavaDoc[2 * oldValues.length];
163
164     _mask = _values.length - 1;
165     _size = 0;
166
167     for (int i = oldValues.length - 1; i >= 0; i--) {
168       long oldKey = oldKeys[i];
169       E oldValue = oldValues[i];
170
171       if (oldValue != null)
172         putImpl(oldKey, oldValue);
173     }
174       }
175     }
176
177     if (item != null)
178       item.removeEvent();
179
180     return item;
181   }
182
183   private E putImpl(long key, E value)
184   {
185     E item = null;
186
187     int hash = getHash(key);
188     int count = _size + 1;
189
190     synchronized (this) {
191       for (; count > 0; count--) {
192     item = _values[hash];
193
194     // No matching item, so create one
195 if (item == null) {
196       _keys[hash] = key;
197       _values[hash] = value;
198       _size++;
199
200       return null;
201     }
202
203     // matching item gets replaced
204 if (_keys[hash] == key) {
205       item.setUsed();
206
207       _values[hash] = value;
208
209       return item;
210     }
211
212     hash = (hash + 1) & _mask;
213       }
214     }
215
216     throw new IllegalStateException JavaDoc();
217   }
218
219   private void freeSpace()
220   {
221     int i = _size - _capacity;
222     if (i > 16)
223       i = 16;
224     // remove LRU items until we're below capacity
225 while (i-- > 0 && removeItem()) {
226     }
227   }
228
229   /**
230    * Remove an unused item from the LRU
231    */
232   private boolean removeItem()
233   {
234     int length = _values.length;
235     int clock = _clock;
236     ClockCacheItem item = null;
237
238     for (int i = 0; i < length; i++) {
239       synchronized (this) {
240     item = _values[clock];
241
242     if (item != null && ! item.isUsed()) {
243       _clock = clock;
244       _values[clock] = null;
245       _size--;
246
247       refillEntries(clock);
248
249       break;
250     }
251       }
252
253       if (item != null)
254     item.clearUsed();
255
256       clock = (clock + 1) % length;
257       item = null;
258     }
259
260     _clock = clock;
261
262     if (item != null) {
263       item.removeEvent();
264       return true;
265     }
266     else
267       return false;
268   }
269
270   /**
271    * Removes an item from the cache
272    *
273    * @param key the key to remove
274    *
275    * @return the value removed
276    */
277   public ClockCacheItem remove(long key)
278   {
279     int hash = getHash(key);
280     int count = _size + 1;
281
282     ClockCacheItem item = null;
283
284     synchronized (this) {
285       for (; count > 0; count--) {
286     item = _values[hash];
287
288     if (item == null)
289       return null;
290
291     if (_keys[hash] == key) {
292       _values[hash] = null;
293       _size--;
294
295       refillEntries(hash);
296       break;
297     }
298
299     hash = (hash + 1) & _mask;
300       }
301     }
302
303     if (count < 0)
304       throw new RuntimeException JavaDoc("internal cache error");
305
306     item.removeEvent();
307
308     return item;
309   }
310
311   /**
312    * Put the item in the best location available in the hash table.
313    */
314   private void refillEntries(int hash)
315   {
316     for (int count = _size; count >= 0; count--) {
317       hash = (hash + 1) & _mask;
318
319       if (_values[hash] == null)
320     return;
321
322       refillEntry(hash);
323     }
324   }
325   
326   /**
327    * Put the item in the best location available in the hash table.
328    */
329   private void refillEntry(int baseHash)
330   {
331     long key = _keys[baseHash];
332     E value = _values[baseHash];
333     
334     _values[baseHash] = null;
335       
336     int hash = getHash(key);
337     
338     for (int count = _size; count >= 0; count--) {
339       if (_values[hash] == null) {
340     _keys[hash] = key;
341     _values[hash] = value;
342     return;
343       }
344
345       hash = (hash + 1) & _mask;
346     }
347   }
348
349   /**
350    * Returns the key's hash
351    */
352   private int getHash(long key)
353   {
354     long hash = key;
355     hash = hash * 0x5deece66dl + 0xbl + (hash >>> 32) * 137;
356
357     return (int) hash & _mask;
358   }
359 }
360
Popular Tags