BasicProxyMap


1   /**
2    *  Licensed to the Apache Software Foundation (ASF) under one or more
3    *  contributor license agreements.  See the NOTICE file distributed with
4    *  this work for additional information regarding copyright ownership.
5    *  The ASF licenses this file to You under the Apache License, Version 2.0
6    *  (the "License"); you may not use this file except in compliance with
7    *  the License.  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  package org.apache.geronimo.kernel.basic;
18  
19  import java.lang.ref.Reference  ;
20  import java.lang.ref.WeakReference  ;
21  import java.lang.ref.ReferenceQueue  ;
22  import java.util.Collection  ;
23  import java.util.Map  ;
24  import java.util.Set  ;
25  
26  /**
27   * Streamlined version of a WeakIdentityHashMap. Provides Identity semantics with 
28   * Weak References to keys. This allows proxies to be GC'ed when no longer referenced
29   * by clients. <code>BasicProxymanager.destroyProxy()</code> need not be invoked when a
30   * proxy is no longer needed. Note that this is not a full Map implementation. 
31   * The iteration and collection capabilities of Map have been discarded to keep the 
32   * implementation lightweight.
33   * <p>
34   * Much of this code was cribbed from the Commons Collection 3.1 implementation of 
35   * <code>ReferenceIdentityMap</code> and <code>AbstractReferenceMap</code>.
36   */
37  public class BasicProxyMap implements Map   {
38  
39      /** The default capacity to use. Always use a power of 2!!! */
40      private static final int DEFAULT_CAPACITY = 16;
41      /** The default load factor to use */
42      private static final float DEFAULT_LOAD_FACTOR = 0.75f;
43      /** The maximum capacity allowed */
44      private static final int MAXIMUM_CAPACITY = 1 << 30;
45      
46      /** Load factor, normally 0.75 */
47      private float loadFactor;
48      /** The size of the map */
49      private transient int size;
50      /** Map entries */
51      private transient ReferenceEntry[] data;
52      /** Size at which to rehash */
53      private transient int threshold;
54  
55      /**
56       * ReferenceQueue used to eliminate GC'ed entries.
57       */
58      private ReferenceQueue   purgeQueue;
59  
60      public BasicProxyMap() {
61          this.loadFactor = DEFAULT_LOAD_FACTOR;
62          this.data = new ReferenceEntry[DEFAULT_CAPACITY];
63          this.threshold = calculateThreshold(DEFAULT_CAPACITY, loadFactor);
64          this.purgeQueue = new ReferenceQueue  ();
65      }
66      
67      /**
68       * Gets the size of the map.
69       * 
70       * @return the size
71       */
72      public int size() {
73          purge();
74          return size;
75      }
76  
77      /**
78       * Checks whether the map is currently empty.
79       * 
80       * @return true if the map is currently size zero
81       */
82      public boolean isEmpty() {
83          purge();
84          return (size == 0);
85      }
86  
87      /**
88       * Checks whether the map contains the specified key.
89       * 
90       * @param key  the key to search for
91       * @return true if the map contains the key
92       */
93      public boolean containsKey(Object   key) {
94          purge();
95          ReferenceEntry entry = getEntry(key);
96          if (entry == null) {
97              return false;
98          }
99          return (entry.getValue() != null);
100     }
101 
102     /**
103      * Checks whether the map contains the specified value.
104      * 
105      * @param value  the value to search for
106      * @return true if the map contains the value
107      */
108     public boolean containsValue(Object   value) {
109         purge();
110         if (value == null || size == 0) {
111             return false;
112         }
113         ReferenceEntry [] table = data;
114         for (int i = 0; i < table.length; i++) {
115             ReferenceEntry entry = table[i];
116             while (entry != null) {
117                 if (value.equals(entry.getValue())) {
118                     return true;
119                 }
120                 entry = entry.next;
121             }
122         }
123         return false;
124     }
125 
126     /**
127      * Gets the value mapped to the key specified.
128      * 
129      * @param key  the key
130      * @return the mapped value, null if no match
131      */
132     public Object   get(Object   key) {
133         purge();
134         ReferenceEntry entry = getEntry(key);
135         if (entry == null) {
136             return null;
137         }
138         return entry.getValue();
139     }
140 
141 
142     /**
143      * Puts a key-value entry into this map.
144      * Neither the key nor the value may be null.
145      * 
146      * @param key  the key to add, must not be null
147      * @param value  the value to add, must not be null
148      * @return the value previously mapped to this key, null if none
149      */
150     public Object   put(Object   key, Object   value) {
151         assert key != null: "key is null";
152         assert value != null: "value is null";
153 
154         purge();
155 
156         int hashCode = hash(key);
157         int index = hashIndex(hashCode, data.length);
158         ReferenceEntry entry = data[index];
159         while (entry != null) {
160             if (entry.hashCode == hashCode && key == entry.getKey()) {
161                 return entry.setValue(value);
162             }
163             entry = entry.next;
164         }   
165             
166         createEntry(index, hashCode, key, value);
167         return null;
168     }
169     
170     /**
171      * Removes the specified mapping from this map.
172      * 
173      * @param key  the mapping to remove
174      * @return the value mapped to the removed key, null if key not in map
175      */
176     public Object   remove(Object   key) {
177         if (key == null) {
178             return null;
179         }
180         purge();
181         int hashCode = hash(key);
182         int index = hashIndex(hashCode, data.length);
183         ReferenceEntry entry = data[index];
184         ReferenceEntry previous = null;
185         while (entry != null) {
186             if (entry.hashCode == hashCode && (key == entry.getKey())) {
187                 Object   oldValue = entry.getValue();
188                 removeEntry(entry, index, previous);
189                 return oldValue;
190             }
191             previous = entry;
192             entry = entry.next;
193         }
194         return null;
195     }
196 
197     /**
198      * Clears the map, resetting the size to zero and nullifying references
199      * to avoid garbage collection issues.
200      */
201     public void clear() {
202         ReferenceEntry[] data = this.data;
203         for (int i = data.length - 1; i >= 0; i--) {
204             data[i] = null;
205         }
206         size = 0;
207         while (purgeQueue.poll() != null) {} // drain the queue
208     }
209 
210     public Collection   values() {
211         throw new UnsupportedOperationException  ();
212     }
213 
214     public void putAll(Map   t) {
215         throw new UnsupportedOperationException  ();
216     }
217 
218     public Set   entrySet() {
219         throw new UnsupportedOperationException  ();
220     }
221 
222     public Set   keySet() {
223         throw new UnsupportedOperationException  ();
224     }
225 
226     // end of public methods
227     
228     /**
229      * Gets the entry mapped to the key specified.
230      * @param key  the key
231      * @return the entry, null if no match
232      */
233     private ReferenceEntry getEntry(Object   key) {
234         if (key == null) {
235             return null;
236         }
237         int hashCode = hash(key);
238         ReferenceEntry entry = data[hashIndex(hashCode, data.length)];
239         while (entry != null) {
240             if (entry.hashCode == hashCode && (key == entry.getKey())) {
241                 return entry;
242             }
243             entry = entry.next;
244         }
245         return null;
246     }
247 
248     /**
249      * Creates a new ReferenceEntry.
250      * 
251      * @param index the index into the data map
252      * @param hashCode  the hash code for the new entry
253      * @param key  the key to store
254      * @param value  the value to store
255      * @return the newly created entry
256      */
257     private ReferenceEntry createEntry(int index, int hashCode, Object   key, Object   value) {
258         ReferenceEntry newEntry = new ReferenceEntry(this, data[index], hashCode, key, value);
259         data[index] = newEntry;
260         size++;
261         checkCapacity();
262         return newEntry;
263     }
264 
265     /**
266      * Removes an entry from the chain stored in a particular index.
267      * <p>
268      * This implementation removes the entry from the data storage table.
269      * The size is not updated.
270      * 
271      * @param entry  the entry to remove
272      * @param hashIndex  the index into the data structure
273      * @param previous  the previous entry in the chain
274      */
275     private void removeEntry(ReferenceEntry entry, int hashIndex, ReferenceEntry previous) {
276         if (previous == null) {
277             data[hashIndex] = entry.next;
278         } else {
279             previous.next = entry.next;
280         }
281         size--;
282         entry.next = null;
283         entry.clear();
284         entry.value = null;
285     }
286     
287     /**
288      * Checks the capacity of the map and enlarges it if necessary.
289      * <p>
290      * This implementation uses the threshold to check if the map needs enlarging
291      */
292     private void checkCapacity() {
293         if (size >= threshold) {
294             int newCapacity = data.length * 2;
295             if (newCapacity <= MAXIMUM_CAPACITY) {
296                 ensureCapacity(newCapacity);
297             }
298         }
299     }
300     
301     /**
302      * Changes the size of the data structure to the capacity proposed.
303      * 
304      * @param newCapacity  the new capacity of the array (a power of two, less or equal to max)
305      */
306     private void ensureCapacity(int newCapacity) {
307         int oldCapacity = data.length;
308         if (newCapacity <= oldCapacity) {
309             return;
310         }
311 
312         ReferenceEntry oldEntries[] = data;
313         ReferenceEntry newEntries[] = new ReferenceEntry[newCapacity];
314 
315         for (int i = oldCapacity - 1; i >= 0; i--) {
316             ReferenceEntry entry = oldEntries[i];
317             if (entry != null) {
318                 oldEntries[i] = null;  // gc
319                 do {
320                     ReferenceEntry next = entry.next;
321                     int index = hashIndex(entry.hashCode, newCapacity);  
322                     entry.next = newEntries[index];
323                     newEntries[index] = entry;
324                     entry = next;
325                 } while (entry != null);
326             }
327         }
328         threshold = calculateThreshold(newCapacity, loadFactor);
329         data = newEntries;
330     }
331 
332     /**
333      * Calculates the new threshold of the map, where it will be resized.
334      * This implementation uses the load factor.
335      * 
336      * @param newCapacity  the new capacity
337      * @param factor  the load factor
338      * @return the new resize threshold
339      */
340     private int calculateThreshold(int newCapacity, float factor) {
341         return (int) (newCapacity * factor);
342     }
343 
344     /**
345      * Gets the hash code for the key specified.
346      * <p>
347      * This implementation uses the identity hash code.
348      * 
349      * @param key  the key to get a hash code for
350      * @return the hash code
351      */
352     private int hash(Object   key) {
353         return System.identityHashCode(key);
354     }
355 
356     /**
357      * Gets the index into the data storage for the hashCode specified.
358      * This implementation uses the least significant bits of the hashCode.
359      * 
360      * @param hashCode  the hash code to use
361      * @param dataSize  the size of the data to pick a bucket from
362      * @return the bucket index
363      */
364     private int hashIndex(int hashCode, int dataSize) {
365         return hashCode & (dataSize - 1);
366     }
367 
368     // Code that handles WeakReference cleanup... Invoked prior to 
369     // any operation accessing the ReferenceEntry array...
370     
371     /**
372      * Purges stale mappings from this map.
373      * <p>
374      * Note that this method is not synchronized!  Special
375      * care must be taken if, for instance, you want stale
376      * mappings to be removed on a periodic basis by some
377      * background thread.
378      */
379     private void purge() {
380         Reference   entryRef = purgeQueue.poll();
381         while (entryRef != null) {
382             purge(entryRef);
383             entryRef = purgeQueue.poll();
384         }
385     }
386 
387     /**
388      * Purges the specified reference.
389      * 
390      * @param purgedEntry the reference to purge
391      */
392     private void purge(Reference   purgedEntry) {
393         int hash = ((ReferenceEntry)purgedEntry).hashCode;
394         int index = hashIndex(hash, data.length);
395         ReferenceEntry previous = null;
396         ReferenceEntry currentEntry = data[index];
397         while (currentEntry != null) {
398             if (currentEntry == purgedEntry) {
399                 currentEntry.purged();
400                 if (previous == null) {
401                     data[index] = currentEntry.next;
402                 } else {
403                     previous.next = currentEntry.next;
404                 }
405                 this.size--;
406                 return;
407             }
408             previous = currentEntry;
409             currentEntry = currentEntry.next;
410         }
411     }
412 
413     /**
414      * Each entry in the Map is represented with a ReferenceEntry.
415      * <p>
416      * If getKey() or getValue() returns null, it means
417      * the mapping is stale and should be removed.
418      * 
419      * @since Commons Collections 3.1
420      */
421     private static class ReferenceEntry extends WeakReference   {
422         /** The next entry in the hash chain */
423         private ReferenceEntry next;
424         /** The hash code of the key */
425         private int hashCode;
426         /** The value */
427         private Object   value;
428 
429         /**
430          * Creates a new entry object for the ReferenceMap.
431          * 
432          * @param parent  the parent map
433          * @param next  the next entry in the hash bucket
434          * @param hashCode  the hash code of the key
435          * @param key  the key
436          * @param value  the value
437          */
438         private ReferenceEntry(BasicProxyMap parent, ReferenceEntry next, int hashCode, Object   key, Object   value) {
439             super(key, parent.purgeQueue);
440             this.next = next;
441             this.hashCode = hashCode;
442             this.value = value;
443         }
444 
445         /**
446          * Gets the key from the entry.
447          * This method dereferences weak and soft keys and thus may return null.
448          * 
449          * @return the key, which may be null if it was garbage collected
450          */
451         private Object   getKey() {
452             return this.get();
453         }
454 
455         /**
456          * Gets the value from the entry.
457          * This method dereferences weak and soft value and thus may return null.
458          * 
459          * @return the value, which may be null if it was garbage collected
460          */
461         private Object   getValue() {
462             return value;
463         }
464 
465         /**
466          * Sets the value of the entry.
467          * 
468          * @param obj  the object to store
469          * @return the previous value
470          */
471         private Object   setValue(Object   obj) {
472             Object   old = getValue();
473             value = obj;
474             return old;
475         }
476 
477         /**
478          * Purges this entry.
479          */
480         private void purged() {
481             this.clear();
482             value = null;
483         }
484     }
485 }
486
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags