HashMapImpl


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.AbstractMap  ;
32  import java.util.AbstractSet  ;
33  import java.util.Collection  ;
34  import java.util.Iterator  ;
35  import java.util.Map  ;
36  import java.util.Set  ;
37  
38  /**
39   * HashMap which doesn't allocate a new DeployController per item.
40   */
41  public class HashMapImpl<K,V> extends AbstractMap  <K,V> {
42    // array containing the keys
43    private K []_keys;
44    
45    // array containing the values
46    private V []_values;
47  
48    private V _nullValue;
49    
50    // maximum allowed entries
51    private int _capacity;
52    // number of items in the cache
53    private int _size;
54    private int _mask;
55  
56    /**
57     * Create the hash map impl with a specific capacity.
58     *
59     * @param initialCapacity minimum capacity of the cache
60     */
61    public HashMapImpl()
62    {
63      this(16);
64    }
65  
66    /**
67     * Create the hash map impl with a specific capacity.
68     *
69     * @param initialCapacity minimum capacity of the cache
70     */
71    public HashMapImpl(int initialCapacity)
72    {
73      int capacity;
74  
75      for (capacity = 16; capacity < 2 * initialCapacity; capacity *= 2) {
76      }
77  
78      _keys = (K []) new Object  [capacity];
79      _values = (V []) new Object  [capacity];
80      _mask = capacity - 1;
81  
82      _capacity = initialCapacity;
83    }
84  
85    /**
86     * Returns the current number of entries in the cache.
87     */
88    public int size()
89    {
90      return _size;
91    }
92  
93    /**
94     * Clears the cache
95     */
96    public void clear()
97    {
98      if (_size > 0) {
99        for (int i = 0; i < _values.length; i++) {
100     _keys[i] = null;
101     _values[i] = null;
102       }
103 
104       _size = 0;
105     }
106 
107     _nullValue = null;
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 V get(Object   key)
117   {
118     if (key == null)
119       return _nullValue;
120     
121     int hash = key.hashCode() & _mask;
122     int count = _size + 1;
123 
124     K []keys = _keys;
125 
126     for (; count > 0; count--) {
127       K mapKey = keys[hash];
128 
129       if (mapKey == null)
130     return null;
131 
132       if (key.equals(_keys[hash]))
133     return _values[hash];
134 
135       hash = (hash + 1) & _mask;
136     }
137 
138     return null;
139   }
140 
141   /**
142    * Puts a new item in the cache.
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 V put(K key, V value)
150   {
151     if (key == null) {
152       V item = _nullValue;
153 
154       _nullValue = value;
155 
156       return item;
157     }
158     
159     V item = putImpl(key, value);
160 
161     // forced resizing if 3/4 full
162     if (3 * _values.length <= 4 * _size) {
163       K []oldKeys = _keys;
164       V []oldValues = _values;
165 
166       _keys = (K []) new Object  [2 * oldKeys.length];
167       _values = (V []) new Object  [2 * oldValues.length];
168 
169       _mask = _values.length - 1;
170       _size = 0;
171 
172       for (int i = oldValues.length - 1; i >= 0; i--) {
173     K oldKey = oldKeys[i];
174     V oldValue = oldValues[i];
175 
176     if (oldValue != null)
177       putImpl(oldKey, oldValue);
178       }
179     }
180 
181     return item;
182   }
183 
184   /**
185    * Implementation of the put.
186    */
187   private V putImpl(K key, V value)
188   {
189     V item = null;
190 
191     int hash = key.hashCode() & _mask;
192     int count = _size + 1;
193 
194     for (; count > 0; count--) {
195       item = _values[hash];
196 
197       // No matching item, so create one
198       if (item == null) {
199     _keys[hash] = key;
200     _values[hash] = value;
201     _size++;
202 
203     return null;
204       }
205 
206       // matching item gets replaced
207       if (_keys[hash].equals(key)) {
208     _values[hash] = value;
209 
210     return item;
211       }
212 
213       hash = (hash + 1) & _mask;
214     }
215 
216     throw new IllegalStateException  ();
217   }
218 
219   /**
220    * Removes an item from the cache
221    *
222    * @param key the key to remove
223    *
224    * @return the value removed
225    */
226   public V remove(Object   key)
227   {
228     if (key == null) {
229       V value = _nullValue;
230       _nullValue = null;
231       return value;
232     }
233     
234     int hash = key.hashCode() & _mask;
235     int count = _size + 1;
236 
237     V item = null;
238 
239     for (; count > 0; count--) {
240       item = _values[hash];
241 
242       if (item == null)
243     return null;
244 
245       if (_keys[hash].equals(key)) {
246     _keys[hash] = null;
247     _values[hash] = null;
248     _size--; 
249 
250     refillEntries(hash);
251     break;
252       }
253 
254       hash = (hash + 1) & _mask;
255     }
256 
257     if (count < 0)
258       throw new RuntimeException  ("internal cache error");
259 
260     return item;
261   }
262 
263   /**
264    * Put the item in the best location available in the hash table.
265    */
266   private void refillEntries(int hash)
267   {
268     for (int count = _size; count >= 0; count--) {
269       hash = (hash + 1) & _mask;
270 
271       if (_values[hash] == null)
272     return;
273 
274       refillEntry(hash);
275     }
276   }
277   
278   /**
279    * Put the item in the best location available in the hash table.
280    */
281   private void refillEntry(int baseHash)
282   {
283     K key = _keys[baseHash];
284     V value = _values[baseHash];
285     
286     _keys[baseHash] = null;
287     _values[baseHash] = null;
288     
289     int hash = key.hashCode() & _mask;
290     
291     for (int count = _size; count >= 0; count--) {
292       if (_values[hash] == null) {
293     _keys[hash] = key;
294     _values[hash] = value;
295     return;
296       }
297 
298       hash = (hash + 1) & _mask;
299     }
300   }
301 
302   /**
303    * Returns the entry set of the cache
304    */
305   public Set  <K> keySet()
306   {
307     return new KeySet(this);
308   }
309 
310   /**
311    * Iterator of cache values
312    */
313   static class KeySet<K1,V1> extends AbstractSet  <K1> {
314     private HashMapImpl<K1,V1> _map;
315 
316     KeySet(HashMapImpl<K1,V1> map)
317     {
318       _map = map;
319     }
320 
321     /**
322      * Returns the size.
323      */
324     public int size()
325     {
326       return _map.size();
327     }
328 
329     /**
330      * Returns true if the map contains the value.
331      */
332     public boolean contains(Object   key)
333     {
334       if (key == null)
335     return _map._nullValue != null;
336       
337       K1 []keys = _map._keys;
338 
339       for (int i = keys.length - 1 ; i >= 0; i--) {
340     K1 testKey = keys[i];
341 
342     if (key.equals(testKey))
343       return true;
344       }
345       
346       return false;
347     }
348 
349     /**
350      * Returns the iterator.
351      */
352     public boolean removeAll(Collection  <?> keys)
353     {
354       if (keys == null)
355     return false;
356       
357       Iterator  <?> iter = keys.iterator();
358       while (iter.hasNext()) {
359     Object   key = iter.next();
360 
361     _map.remove(key);
362       }
363 
364       return true;
365     }
366 
367     /**
368      * Returns the iterator.
369      */
370     public Iterator  <K1> iterator()
371     {
372       return new KeyIterator<K1,V1>(_map);
373     }
374   }
375 
376   /**
377    * Iterator of cache values
378    */
379   static class KeyIterator<K1,V1> implements Iterator  <K1> {
380     private HashMapImpl<K1,V1> _map;
381     private int _i;
382 
383     KeyIterator(HashMapImpl<K1,V1> map)
384     {
385       init(map);
386     }
387 
388     void init(HashMapImpl<K1,V1> map)
389     {
390       _map = map;
391       _i = 0;
392     }
393 
394     public boolean hasNext()
395     {
396       K1 []keys = _map._keys;
397       int len = keys.length;
398       
399       for (; _i < len; _i++) {
400     if (keys[_i] != null)
401       return true;
402       }
403       
404       return false;
405     }
406 
407     public K1 next()
408     {
409       K1 []keys = _map._keys;
410       int len = keys.length;
411       
412       for (; _i < len; _i++) {
413     K1 key = keys[_i];
414     
415     if (key != null) {
416       _i++;
417       
418       return key;
419     }
420       }
421 
422       return null;
423     }
424 
425     public void remove()
426     {
427       if (_i > 0)
428     _map.remove(_map._keys[_i - 1]);
429     }
430   }
431 
432   /**
433    * Returns the entry set of the cache
434    */
435   public Set  <Map.Entry  <K,V>> entrySet()
436   {
437     return new EntrySet(this);
438   }
439 
440   /**
441    * Iterator of cache values
442    */
443   static class EntrySet<K1,V1> extends AbstractSet  <Map.Entry  <K1,V1>> {
444     private HashMapImpl<K1,V1> _map;
445 
446     EntrySet(HashMapImpl<K1,V1> map)
447     {
448       _map = map;
449     }
450 
451     /**
452      * Returns the size.
453      */
454     public int size()
455     {
456       return _map.size();
457     }
458 
459     /**
460      * Returns the iterator.
461      */
462     public Iterator  <Map.Entry  <K1,V1>> iterator()
463     {
464       return new EntryIterator(_map);
465     }
466   }
467 
468   /**
469    * Iterator of cache values
470    */
471   static class EntryIterator<K1,V1> implements Iterator  <Map.Entry  <K1,V1>> {
472     private final Entry<K1,V1> _entry = new Entry<K1,V1>();
473     
474     private HashMapImpl<K1,V1> _map;
475     private int _i;
476 
477     EntryIterator(HashMapImpl<K1,V1> map)
478     {
479       init(map);
480     }
481 
482     void init(HashMapImpl<K1,V1> map)
483     {
484       _map = map;
485       _i = 0;
486     }
487 
488     public boolean hasNext()
489     {
490       K1 []keys = _map._keys;
491       int len = keys.length;
492       
493       for (; _i < len; _i++) {
494     if (keys[_i] != null)
495       return true;
496       }
497       
498       return false;
499     }
500 
501     public Map.Entry  <K1,V1> next()
502     {
503       K1 []keys = _map._keys;
504       int len = keys.length;
505       
506       for (; _i < len; _i++) {
507     if (keys[_i] != null) {
508       _entry.init(_map, _i++);
509 
510       return _entry;
511     }
512       }
513 
514       return null;
515     }
516 
517     public void remove()
518     {
519       if (_i > 0)
520     _map.remove(_map._keys[_i - 1]);
521     }
522   }
523 
524   static class Entry<K1,V1> implements Map.Entry  <K1,V1> {
525     private HashMapImpl<K1,V1> _map;
526     private int _i;
527 
528     void init(HashMapImpl<K1,V1> map, int i)
529     {
530       _map = map;
531       _i = i;
532     }
533 
534     /**
535      * Gets the key of the entry.
536      */
537     public K1 getKey()
538     {
539       return _map._keys[_i];
540     }
541 
542     /**
543      * Gets the value of the entry.
544      */
545     public V1 getValue()
546     {
547       return _map._values[_i];
548     }
549 
550     /**
551      * Sets the value of the entry.
552      */
553     public V1 setValue(V1 value)
554     {
555       V1 oldValue = _map._values[_i];
556       
557       _map._values[_i] = value;
558 
559       return oldValue;
560     }
561   }
562 }
563
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags