KickJava   Java API By Example, From Geeks To Geeks.

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


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