ReferenceMap


1   /**
2    *  Copyright 2001-2004 The Apache Software Foundation
3    *  Portions (modifications) Copyright 2004-2005 IBM Corp.
4    *
5    *  Licensed under the Apache License, Version 2.0 (the "License");
6    *  you may not use this file except in compliance with the License.
7    *  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   *  Unless required by applicable law or agreed to in writing, software
12   *  distributed under the License is distributed on an "AS IS" BASIS,
13   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   *  See the License for the specific language governing permissions and
15   *  limitations under the License.
16   *
17   * Contributors:
18   *    Apache Software Foundation - Initial implementation
19   *    Pascal Rapicault, IBM -  Pascal remove the entrySet() implementation because it relied on another class.
20   *    IBM - change to int keys, remove support for weak references, and remove unused methods
21   */
22  package org.eclipse.core.internal.registry;
23  
24  import java.lang.ref.*;
25  
26  /**
27   *  Hashtable-based map with integer keys that allows values to be removed 
28   *  by the garbage  collector.<P>
29   *
30   *  When you construct a <Code>ReferenceMap</Code>, you can 
31   *  specify what kind of references are used to store the
32   *  map's values.  If non-hard references are 
33   *  used, then the garbage collector can remove mappings
34   *  if a value becomes unreachable, or if the 
35   *  JVM's memory is running low.  For information on how
36   *  the different reference types behave, see
37   *  {@link Reference}.<P>
38   *
39   *  The algorithms used are basically the same as those
40   *  in {@link java.util.HashMap}.  In particular, you 
41   *  can specify a load factor and capacity to suit your
42   *  needs.
43   *
44   *  This map does <I>not</I> allow null values.  Attempting to add a null 
45   *  value to the map will raise a <Code>NullPointerException</Code>.<P>
46   *
47   *  This data structure is not synchronized.
48   *
49   *  @see java.lang.ref.Reference
50   */
51  public class ReferenceMap {
52  
53      /**
54       * IEntry implementation that acts as a hard reference.
55       * The value of a hard reference entry is never garbage
56       * collected until it is explicitly removed from the map.
57       */
58      private static class HardRef implements IEntry {
59  
60          private int key;
61          private IEntry next;
62          /**
63           * Reference value.  Note this can never be null.
64           */
65          private Object   value;
66  
67          public HardRef(int key, Object   value, IEntry next) {
68              this.key = key;
69              this.value = value;
70              this.next = next;
71          }
72  
73          public int getKey() {
74              return key;
75          }
76  
77          public IEntry getNext() {
78              return next;
79          }
80  
81          public Object   getValue() {
82              return value;
83          }
84  
85          public void setNext(IEntry next) {
86              this.next = next;
87          }
88  
89          public String   toString() {
90              return "HardRef(" + key + ',' + value + ')'; //$NON-NLS-1$
91          }
92      }
93  
94      /**
95       * The common interface for all elements in the map.  Both
96       * hard and soft map values conform to this interface.
97       */
98      private static interface IEntry {
99          /**
100          * Returns the integer key for this entry.
101          * @return The integer key
102          */
103         public int getKey();
104 
105         /**
106          * Returns the next entry in the linked list of entries
107          * with the same hash value, or <code>null</code>
108          * if there is no next entry.
109          * @return The next entry, or <code>null</code>.
110          */
111         public IEntry getNext();
112 
113         /**
114          * Returns the value of this entry.
115          * @return The entry value.
116          */
117         public Object   getValue();
118 
119         /**
120          * Sets the next entry in the linked list of map entries
121          * with the same hash value.
122          * 
123          * @param next The next entry, or <code>null</code>.
124          */
125         public void setNext(IEntry next);
126     }
127 
128     /**
129      * Augments a normal soft reference with additional information
130      * required to implement the IEntry interface.
131      */
132     private static class SoftRef extends SoftReference implements IEntry {
133         private int key;
134         /**
135          * For chained collisions
136          */
137         private IEntry next;
138 
139         public SoftRef(int key, Object   value, IEntry next, ReferenceQueue q) {
140             super(value, q);
141             this.key = key;
142             this.next = next;
143         }
144 
145         public int getKey() {
146             return key;
147         }
148 
149         public IEntry getNext() {
150             return next;
151         }
152 
153         public Object   getValue() {
154             return super.get();
155         }
156 
157         public void setNext(IEntry next) {
158             this.next = next;
159         }
160     }
161 
162     /**
163      *  Constant indicating that hard references should be used.
164      */
165     final public static int HARD = 0;
166 
167     /**
168      *  Constant indiciating that soft references should be used.
169      */
170     final public static int SOFT = 1;
171 
172     private int entryCount;
173 
174     /**
175      *  The threshold variable is calculated by multiplying
176      *  table.length and loadFactor.  
177      *  Note: I originally marked this field as final, but then this class
178      *   didn't compile under JDK1.2.2.
179      *  @serial
180      */
181     private float loadFactor;
182 
183     /**
184      *  ReferenceQueue used to eliminate stale mappings.
185      */
186     private transient ReferenceQueue queue = new ReferenceQueue();
187 
188     /**
189      *  Number of mappings in this map.
190      */
191     private transient int size;
192 
193     /**
194      *  The hash table.  Its length is always a power of two.  
195      */
196     private transient IEntry[] table;
197 
198     /**
199      *  When size reaches threshold, the map is resized.  
200      *  @see #resize()
201      */
202     private transient int threshold;
203 
204     /**
205      *  The reference type for values.  Must be HARD or SOFT
206      *  Note: I originally marked this field as final, but then this class
207      *   didn't compile under JDK1.2.2.
208      *  @serial
209      */
210     int valueType;
211 
212     /**
213      *  Constructs a new <Code>ReferenceMap</Code> with the
214      *  specified reference type, load factor and initial
215      *  capacity.
216      *
217      *  @param referenceType  the type of reference to use for values;
218      *   must be {@link #HARD} or {@link #SOFT}
219      *  @param capacity  the initial capacity for the map
220      *  @param loadFactor  the load factor for the map
221      */
222     public ReferenceMap(int referenceType, int capacity, float loadFactor) {
223         super();
224         if (referenceType != HARD && referenceType != SOFT)
225             throw new IllegalArgumentException  (" must be HARD or SOFT."); //$NON-NLS-1$
226         if (capacity <= 0)
227             throw new IllegalArgumentException  ("capacity must be positive"); //$NON-NLS-1$
228         if ((loadFactor <= 0.0f) || (loadFactor >= 1.0f))
229             throw new IllegalArgumentException  ("Load factor must be greater than 0 and less than 1."); //$NON-NLS-1$
230 
231         this.valueType = referenceType;
232 
233         int initialSize = 1;
234         while (initialSize < capacity)
235             initialSize *= 2;
236 
237         this.table = new IEntry[initialSize];
238         this.loadFactor = loadFactor;
239         this.threshold = (int) (initialSize * loadFactor);
240     }
241 
242     /**
243      * @param key
244      * @return
245      */
246     private Object   doRemove(int key) {
247         int index = indexFor(key);
248         IEntry previous = null;
249         IEntry entry = table[index];
250         while (entry != null) {
251             if (key == entry.getKey()) {
252                 if (previous == null)
253                     table[index] = entry.getNext();
254                 else
255                     previous.setNext(entry.getNext());
256                 this.size--;
257                 return entry.getValue();
258             }
259             previous = entry;
260             entry = entry.getNext();
261         }
262         return null;
263     }
264 
265     /**
266      *  Returns the value associated with the given key, if any.
267      *
268      *  @return the value associated with the given key, or <Code>null</Code>
269      *   if the key maps to no value
270      */
271     public Object   get(int key) {
272         purge();
273         for (IEntry entry = table[indexFor(key)]; entry != null; entry = entry.getNext())
274             if (entry.getKey() == key)
275                 return entry.getValue();
276         return null;
277     }
278 
279     /**
280      *  Converts the given hash code into an index into the
281      *  hash table.
282      */
283     private int indexFor(int hash) {
284         // mix the bits to avoid bucket collisions...
285         hash += ~(hash << 15);
286         hash ^= (hash >>> 10);
287         hash += (hash << 3);
288         hash ^= (hash >>> 6);
289         hash += ~(hash << 11);
290         hash ^= (hash >>> 16);
291         return hash & (table.length - 1);
292     }
293 
294     /**
295      * Constructs a new table entry for the given data
296      * 
297      * @param key The entry key
298      * @param value The entry value
299      * @param next The next value in the entry's collision chain
300      * @return The new table entry
301      */
302     private IEntry newEntry(int key, Object   value, IEntry next) {
303         entryCount++;
304         switch (valueType) {
305             case HARD :
306                 return new HardRef(key, value, next);
307             case SOFT :
308                 return new SoftRef(key, value, next, queue);
309             default :
310                 throw new Error  ();
311         }
312     }
313 
314     /**
315      *  Purges stale mappings from this map.<P>
316      *
317      *  Ordinarily, stale mappings are only removed during
318      *  a write operation; typically a write operation will    
319      *  occur often enough that you'll never need to manually
320      *  invoke this method.<P>
321      *
322      *  Note that this method is not synchronized!  Special
323      *  care must be taken if, for instance, you want stale
324      *  mappings to be removed on a periodic basis by some
325      *  background thread.
326      */
327     private void purge() {
328         Reference ref = queue.poll();
329         while (ref != null) {
330             doRemove(((IEntry) ref).getKey());
331             ref.clear();
332             ref = queue.poll();
333         }
334     }
335 
336     /**
337      *  Associates the given key with the given value.<P>
338      *  Neither the key nor the value may be null.
339      *
340      *  @param key  the key of the mapping
341      *  @param value  the value of the mapping
342      *  @throws NullPointerException if either the key or value
343      *   is null
344      */
345     public void put(int key, Object   value) {
346         if (value == null)
347             throw new NullPointerException  ("null values not allowed"); //$NON-NLS-1$
348 
349         purge();
350 
351         if (size + 1 > threshold)
352             resize();
353 
354         int index = indexFor(key);
355         IEntry previous = null;
356         IEntry entry = table[index];
357         while (entry != null) {
358             if (key == entry.getKey()) {
359                 if (previous == null)
360                     table[index] = newEntry(key, value, entry.getNext());
361                 else
362                     previous.setNext(newEntry(key, value, entry.getNext()));
363                 return;
364             }
365             previous = entry;
366             entry = entry.getNext();
367         }
368         this.size++;
369         table[index] = newEntry(key, value, table[index]);
370     }
371 
372     /**
373      *  Removes the key and its associated value from this map.
374      *
375      *  @param key  the key to remove
376      *  @return the value associated with that key, or null if
377      *   the key was not in the map
378      */
379     public Object   remove(int key) {
380         purge();
381         return doRemove(key);
382     }
383 
384     /**
385      *  Resizes this hash table by doubling its capacity.
386      *  This is an expensive operation, as entries must
387      *  be copied from the old smaller table to the new 
388      *  bigger table.
389      */
390     private void resize() {
391         IEntry[] old = table;
392         table = new IEntry[old.length * 2];
393 
394         for (int i = 0; i < old.length; i++) {
395             IEntry next = old[i];
396             while (next != null) {
397                 IEntry entry = next;
398                 next = next.getNext();
399                 int index = indexFor(entry.getKey());
400                 entry.setNext(table[index]);
401                 table[index] = entry;
402             }
403             old[i] = null;
404         }
405         threshold = (int) (table.length * loadFactor);
406     }
407 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags